遗传算法在求解最小生成树中的运用

以图论和遗传算法为基础,提出了求解最小生成树问题的遗传算法。该算法解决了常用二进制编码不能正确表达最小生成树的问题,利用Prufer数对生成树进行编码;在遗传操作中对变异算子进行了改进,避免了由于变异产生大量不可行解。从而提高了遗传算法的效率;通过数值试验,表明该算法简单,高效,收敛率高。     

求解多目标最小生成树的改进多目标蚁群算法

多目标最小生成树问题是典型的NP问题。针对此问题,提出一种改进的多目标蚁群算法。为获得更好的非劣前端,通过合理选取多个信息素扩散源与扩散策略来避免其早熟收敛,并引入非支配排序算子,提高种群多样性并避免算法过早陷入局部最优解。对比实验结果表明：对于多目标最小生成树问题,该算法是有效的,不但在求解效率和解的质量方面优于相关算法,而且随着问题规模的扩大,算法仍保持较好的性能。     

MSN网络的优化问题研究

研究了由MSN节点组成的应用层组播网络,讨论了度约束最小直径生成树(D-MDST)问题,并给出了求解该问题的BCT算法。提出了一种新的生成树编码方法——过程控制编码,该编码将启发式算法与遗传算法结合起来且具有编码简单、译码方便、适用常规遗传算子等优点。给出了基于该种编码的遗传算法,并将BCT算法作为过程控制编码的译码器。仿真结果表明了该遗传算法的有效性。     

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.     

交通选线优化算法的设计与实现

将交通选线问题求解转化为最小生成树（Minimun Spanning Tree,MST）的求解,对比了经典MST求解算法,以图论为基础,采取一种求最小生成树的改进遗传算法．该算法以二进制编码表示最小树问题,用深度优先搜索算法进行图的连通性判断,并采用相应的适应度函数、单亲换位算子和单亲逆转算子及多种控制进化策略,能在一次遗传进化过程中获得一批最小生成树,可供决策部门综合评价与决策．     

用基于多目标决策的遗传算法解网络拓扑结构设计问题

多点网络拓扑结构设计问题是NP-完全问题。该文提出了一个基于多目标决策的遗传算法(MCGA)来解决多点网络拓扑结构问题。和其它多目标遗传算法不同的是:首先,对网络节点进行预划分,使得Pareto优的节点归于候选分枝节点集合;其次,修改了Prüfer编码,使得编码中的码元代表候选分枝节点,以利于对分枝节点的搜索;最后,构造了分枝变异算子与非分枝变异算子作为主要的进化算子。该算法以概率1收敛于全局最优解集。数值实验表明该算法优于其它多目标遗传算法。     

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

针对度约束最小生成树问题的特征,设计了一种新的编码方式,并在此基础上提出了一个新遗传算法来求解该问题。该算法采用新的启发式杂交算子、变异算子和局部搜索算子,以概率1收敛到全局最优解。数值实验表明该算法优于文中提出的其他4种算法。     

一种求解多目标最小生成树问题的有效离散粒子群优化算法

提出一种求解多目标最小生成树问题的有效离散粒子群优化算法.为获得更好的非劣前端,设计一个基于目标共享函数的适应度评价函数.引入遗传算法的变异和交叉算子,提高种群多样性并避免算法过早陷入局部最优解.基于种群的随机状态转移过程,理论分析算法的全局收敛性.实验结果表明该算法是有效的,且随着问题规模的扩大算法仍保持较好的性能.     

最小生成树的算法

本文提出了一个利用集合运算生成最小生成树的算法。研究了实现集合运算的数据结构及施加在这个结构上的算法。该算法利用公式分组排序。利用路径压缩的方法进行查找，并运算。该算法将有Ｎ个顶点Ｅ条边的无向连通网络生成最小生成树的期望时间是Ｏ。     

多约束应用层组播的算法研究

研究了基于组播服务节点（MSN）的两层应用层组播网络,提出了度和时延联合约束的最小生成树问题（DDCMST问题）,并给出了求解该问题的启发式算法——DD-Prim算法。为了进一步提高求解的精度,在该算法中引入了偏置向量,得到了BDD-PRIM算法,并将其作为染色体编码的译码器应用到遗传算法中。仿真结果证明了遗传算法的有效性。     

求解多目标优化问题的自适应粒子群算法

提出了一种基于自适应惯性权重的多目标粒子群优化算法AWMOPSO,采用新的适应值分配机制,在搜索过程中根据粒子的适应值对粒子进行分类,动态调整粒子的惯性权重以控制粒子的开发和探索能力。用外部精英集保存非支配解,并通过拥挤距离维持解的多样性。引入精英迁移和局部扰动策略,提高收敛的速度和精度。典型的测试函数的计算结果表明了算法能够快速逼近Pareto最优前沿,是求解多目标优化问题的有效方法。     

Random-tree Diameter and the Diameter-constrained MST

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G , with n nodes and a positive integer, k , find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k ; 4 h k h ( n m 2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.     

Multi-objective sine-cosine algorithm (MO-SCA) for multi-objective engineering design problems

This paper proposes a novel and an effective multi-objective optimization algorithm named multi-objective sine-cosine algorithm (MO-SCA) which is based on the search technique of sine-cosine algorithm (SCA). MO-SCA employs the elitist non-dominated sorting and crowding distance approach for obtaining different non-domination levels and to preserve the diversity among the optimal set of solutions, respectively. The effectiveness of the method is measured by implementing it on multi-objective benchmark problems that have various characteristics of Pareto front such as convex, non-convex and discrete. This proposed algorithm is also checked for the multi-objective engineering design problems with distinctive features. Furthermore, we show the proposed algorithm effectively generates the Pareto front and is easy to implement and algorithmically simple.

     

基于高维空间稀疏最小生成树自适应覆盖模型的一类分类算法

最小生成树数据描述( MSTCD)在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供目标类样本分布描述,这种描述存在分支多、覆盖模型复杂的问题.针对该问题,依据特征空间中同类样本分布的连续性规律,文中提出基于稀疏最小生成树覆盖模型的一类分类算法.该方法首先构建目标类数据集的稀疏k近邻图表示,通过递归图分割...     

基于有序双循环链表的低代价最短路径树快速算法

低代价最短路径树是一种广泛使用的多播树。在FLSPT算法的基础上,通过选择有序双循环链表作为待发展节点序列Q的运算与存储中心,提出了基于有序双循环链表的低代价最短路径树快速算法DKFLSPT。该算法构造的最短路径树与FLSPT算法构造的最短路径树具有相同的性能,利用有序双循环链表的局部性原理来达到改进节点路径最小值的搜索过程。随机网络模型的仿真结果表明,DKFLSPT 算法效率平均可以提高19%。     

Improved RM-MEDA with local learning

In this paper, local learning is proposed to improve the speed and the accuracy of convergence performance of regularity model-based multiobjective estimation of distribution algorithm (RM-MEDA), a typical multi-objective optimization algorithm via estimation of distribution. RM-MEDA employs a model-based method to generate new solutions, however, this method is easy to generate poor solutions when the population has no obvious regularity. To overcome this drawback, our proposed method add a new solution generation strategy, local learning, to the original RM-MEDA. Local learning produces solutions by sampling some solutions from the neighborhood of elitist solutions in the parent population. As it is easy to search some promising solutions in the neighborhood of an elitist solution, local learning can get some useful solutions which help the population attain a fast and accurate convergence. The experimental results on a set of test instances with variable linkages show that the implement of local learning can accelerate convergence speed and add a more accurate convergence to the Pareto optimal.     

Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure

A self-adaptive differential evolution algorithm incorporate Pareto dominance to solve multi-objective optimization problems is presented. The proposed approach adopts an external elitist archive to retain non-dominated solutions found during the evolutionary process. In order to preserve the diversity of Pareto optimality, a crowding entropy diversity measure tactic is proposed. The crowding entropy strategy is able to measure the crowding degree of the solutions more accurately. The experiments were performed using eighteen benchmark test functions. The experiment results show that, compared with three other multi-objective optimization evolutionary algorithms, the proposed MOSADE is able to find better spread of solutions with better convergence to the Pareto front and preserve the diversity of Pareto optimal solutions more efficiently.     

基于IFI与FUA的Pareto遗传算法

在适应值快速辨识算法和基于聚类排挤的外部种群快速替换算法的基础上，提出了搜索Pareto最优解集的快速遗传算法。在该算法中，IFI算法实现个体适应值的快速辨识，FUA维持种群多样度和Pareto最优解集的均匀分布性。采用FPGA算法对多种多目标0/1背包问题进行仿真优化，FPGA算法能够以较少的计算成本搜索到高精度、分布均匀、高质量的Pareto非劣解集，收敛速度和收敛准确性均优于强度Pareto进化算法(SPEA)。