| 求解多目标最小生成树的一种新的遗传算法 |
| |
| 引用本文： | 余荣祖,王唯良,陈冰.求解多目标最小生成树的一种新的遗传算法[J].计算机工程与应用,2009,45(16):48-49. |
| |
| 作者姓名： | 余荣祖 王唯良 陈冰 |
| |
| 作者单位： | 1. 西安空军工程大学,理学院,数理系,应用数学教研室,西安,710051
2. 西安理工大学,应用数学系,西安,710048 |
| |
| 摘 要： | 在改进的非支配排序遗传算法(NSGA-Ⅱ)的基础上,提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明:对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。
|
| 关 键 词： | 多目标最小生成树 改进的非支配排序遗传算法(NSGA-Ⅱ) 最小生成树 Pareto最优解 |
| 收稿时间： | 2008-4-2 |
| 修稿时间： | 2008-5-30
|
New NSGA-II on Multi-Objective Minimum Spanning Tree problem |
| |
| YU Rong-zu,WANG Wei-liang,CHEN Bing.New NSGA-II on Multi-Objective Minimum Spanning Tree problem[J].Computer Engineering and Applications,2009,45(16):48-49. |
| |
| Authors: | YU Rong-zu WANG Wei-liang CHEN Bing |
| |
| Affiliation: | YU Rong-zu1,WANG Wei-liang1,CHEN Bing2 1.Department of Applied Mathematics , Physics,Colleges of Science,Air Force Engineering University,Xi'an 710051,China 2.Department of Applied Mathematics,Xi'an University of Technology,Xi'an 710048,China |
| |
| Abstract: | A novel multi-objective evolutionary algorithm on multi-objective minimum spanning tree problem is proposed which is based on a fast elitist Non-dominated Sorting Genetic Algorithm for multi-objective optimization（NSGA-II）.It adopts the edge-sets as the tree encoding and a new crossover operator and a fast elitist non-dominated sorting algorithm to make the GA search give out all Pareto optimal solutions distributed all along the Pareto frontier.The experimental results show that this algorithm has faster convergent speed and better diversity of solutions than the algorithm based on PrimRST. |
| |
| Keywords: | Multi-Objective Minimum Spanning Tree（MO-MST） Non-dominated Sorting Genetic Algorithm II（NSGA-II） Minimum Spanning Tree（MST） Pareto optimal solution |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
