求解度约束最小生成树的单亲遗传算法

提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了它求解TSP问题的具体步骤和实例。     

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题，介绍了一种基于竞争造就优化和决策左右结果的新型算法——竞争决策算法，利用竞争决策算法的通用模型，给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法，经过数据测试和验证，并与其它算法的结果进行了比较，得到了较好的结果．     

广义最小生成树的遗传算法求解及应用

介绍了最小生成树的概念,分析了最小生成树在实际应用中的局限性。引入了节点的度的定义,据此提出了广义最小生成树的概念。采用遗传算法来求解最小生成树,并针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略。通过一个有线电视网络的建模与仿真,表明了广义最小生成树模型的适用性。分别采用普通遗传算法和改进后的遗传算法进行求解,并将结果进行比较,证明了改进后的遗传算法的有效性。     

基于最小生成树的LAPLACE谱图像匹配算法

提出了一种基于最小生成树的Laplace谱图像匹配算法.首先分别对两幅待匹配图像的特征点集构造完全图,其次寻找最小生成树,然后通过各自的最小生成树构造Laplace矩阵,接下来进行分解并利用分解结果构造匹配矩阵,最后通过匹配矩阵实现两幅图像匹配.实验验证了该算法能够降低匹配的时间复杂度和获得较高的匹配精度.     

启发式交叉求解TSP问题的混合遗传算法

在给出度约束最小生成树的快速生成方法的基础上，设计了一种启发式交叉求解TSP问题的混合遗传算法．该算法在交叉操作的设计上，与其他遗传算法有本质的不同，该交叉操作是在不违反度约束和不形成圈的前提下，每次从父代基因所拥有的边中加入权最小的边，从而形成子代．利用该算法得到了TSP CHN144问题迄今为止最好的解．     

基于最小生成树与概率松弛结合的谱匹配算法

提出了一种基于最小生成树与概率松弛结合的谱匹配算法。该算法分别对给定的两个待匹配的特征点集构建最小生成树,通过最小生成树构造Laplace矩阵,由奇异值分解该矩阵得到的特征值和特征向量,计算出特征点匹配的初始概率,利用概率松弛迭代法,获得最终匹配结果。用大量的真实序列图像进行比较实验,结果验证了该算法的有效性和准确性。     

求解TSP问题的最近邻域与插入混合算法

研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合算法. 分析了混合算法的合理性、复杂度及参数取值, 并分别采用以上三种算法求解了TSPLIB标准库中多个算例, 结果表明混合算法的求解速度接近最近邻域算法, 对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当, 而对大规模TSP问题的求解质量明显优于插入算法.     

对称型TSP下界的快速估算法

在数学推导和证明的基础上,给出了一个求解对称型TSP问题下界的快速算法,利用该算法求解了TSP标准问题库中部分对称型问题,给出了计算结果并与标准问题库中公布的最好解进行了比较,获得了令人满意的效果.     

求解连续函数优化问题的改进蚁群算法及仿真

蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法,该算法采用分布式并行计算和正反馈机制,易于与其它方法结合,目前虽然已经在离散空间优化领域中得到了广泛应用,但是在求解连续空间优化问题方面的研究相对较少.在介绍基本蚁群算法机制原理和数学模型的基础上,对信息素更新方式进行了改进,采用动态局部信息素更新方式和自适应调节信息素挥发的全局信息素更新方式相结合,并将各条寻优路径上可能的残留信息素数量限制在一个最大最小区间,以提高改进后蚁群算法的全局收敛性能.仿真实验表明,提出的改进蚁群算法能更快地找到连续空间优化问题更优良的全局解,从而为蚁群算法求解这类问题提供了一条可行有效的新途径.     

求解度限制最小生成树问题的启发式遗传搜索算法

CM（1,1）模型一般以模型还原值与实际值平均相对误差检验模型的模拟精度。本文以模型还原值与实际值平均相对误差最小化为目标函数将CM（1,1）模型转化成一个不用进行灰微分方程参数辨识的优化模型，称之为改进的GM（1,1）模型，简称IGM（1,1）。IGM（1,1）避开了灰微分方程参数辨识时传统的优化无法求解，本文针对IGM（1,1）模型的直接建模。由于IGM（1,1）目标函数非连续，不可导，用传统的优化无法求解，本文针对IGM（1,1）模型的模拟特性设计了求解该优化模型的遗传算法并进行了算例验证，秋解结果表明了IGM（1,1）模型IGM（1,1）模型。     

Algorithms for degree-constrained Euclidean Steiner minimal tree

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed,which is quite useful in several fields.Although it is slightly different from the traditional degree-constrained minimal spanning tree,it is aho NP-hard.Two intelligent algorithms are proposed in an attempt to solve this difficult problem.Series of numerical examples are tested,which demonstrate that the algorithms also work well in practice.     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

Mean-variance model based on filters of minimum spanning tree

This study aims to reduce the statistical uncertainty of the correlation coefficient matrix in the mean-variance model of Markowitz. A filtering algorithm based on minimum spanning tree (MST) is proposed. Daily data of the 30 stocks of the Hang Seng Index (HSI) and Dow Jones Index (DJI) from 2004 to 2009 are selected as the base dataset. The proposed algorithm is compared with the Markowitz method in terms of risk, reliability, and effective size of the portfolio. Results show that (1) although the predicted risk of portfolio built with the MST is slightly higher than that of Markowitz, the realized risk of MST filtering algorithm is much smaller; and (2) the reliability and the effective size of filtering algorithm based on MST is apparently better than that of the Markowitz portfolio. Therefore, conclusion is that filtering algorithm based on MST improves the mean-variance model of Markowitz.     

Algorithms for degree-constrained Euclidean Steiner minimal tree

A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.     

Steiner最小树问题的量子蚁群算法

Steiner最小树问题是组合优化中一个经典的NP难题,本文在蚁群算法的基础上结合量子计算提出一种求解欧氏Steiner最小树问题的量子蚁群算法.将量子比特、量子逻辑门以及Grover量子算法引入到蚁群算法中去,有效提高了算法的全局搜索能力,搜索速度也有显著的提高.一系列数据实例计算与比较表明,量子蚁群算法较蚁群算法在Steiner最小树问题的求解上具有更好的性能.