基于最小生成树NSGA-2算法的改进

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (24): 32-36.

基于最小生成树NSGA-2算法的改进

李密青，郑金华

湘潭大学信息工程学院，湖南湘潭 411105

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-08-21 发布日期:2007-08-21
通讯作者: 李密青

Improved NSGA-2 algorithm based on minimum spanning tree

LI Mi-qing，ZHENG Jin-hua

Institute of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-08-21 Published:2007-08-21
Contact: LI Mi-qing

摘要/Abstract

摘要： 多目标进化算法（MOEA）的一个关键就是保持解的分布度，提出了一种用最小生成树的边的权值来表示个体聚集距离的方法，并且对NSGA-2的交叉算子和变异率进行了改进。实验结果表明，与NSGA-2相比该方法（MST-NSGA-2）在解的分布度上有较大的提高，并且有着良好的收敛性。

关键词: 多目标进化算法, 聚集距离, 最小生成树, 非均匀算术交叉

Abstract: The key of Multi-Objective Evolutionary Algorithm（MOEA） is how to keep diversity of solutions.In this paper，it suggests a new approach to measure individual crowding distance by edge weight of minimum spanning tree，and it is also improved crossover operator and mutation rate for NSGA-2.It’s shown by experimental results that the convergence and diversity of this algorithm is more efficient than NSGA-2.

Key words: Multi-Objective Evolutionary Algorithm（MOEA）, crowding distance, minimum spanning tree, nonuniform arithmetical
crossover

李密青，郑金华. 基于最小生成树NSGA-2算法的改进[J]. 计算机工程与应用, 2007, 43(24): 32-36.

LI Mi-qing，ZHENG Jin-hua. Improved NSGA-2 algorithm based on minimum spanning tree[J]. Computer Engineering and Applications, 2007, 43(24): 32-36.

[1]	吉训生，蔡益青. 利用历史信息和限制算子求解MOFJSP[J]. 计算机工程与应用, 2020, 56(2): 272-278.
[2]	邓宇，谌贵辉，李忠兵，张军豪，亢宇欣，夏旭洪. 基于颜色与边缘融合的非局部立体匹配算法[J]. 计算机工程与应用, 2020, 56(10): 199-204.
[3]	宋森森1，贾振红1，杨杰2，Nikola KASABOV3. 结合Ostu阈值法的最小生成树图像分割算法[J]. 计算机工程与应用, 2019, 55(9): 178-183.
[4]	耿焕同，周利发，丁洋洋，周山胜. 一种基于新型差分进化模型的MOEA/D改进算法[J]. 计算机工程与应用, 2019, 55(8): 138-146.
[5]	肖俊明，高洪洋，朱永胜，瞿博阳. 考虑新能源接入的电力多目标优化调度[J]. 计算机工程与应用, 2019, 55(23): 241-247.
[6]	顾春华，刘鑫平，罗飞，丁炜超. 基于同步更新外部归档集的NSGA-II改进算法[J]. 计算机工程与应用, 2018, 54(20): 28-34.
[7]	曹戴，陈丽芳. 基于杰卡德度量的智能拼图改进算法[J]. 计算机工程与应用, 2018, 54(2): 188-192.
[8]	王俊，赵凤. 基于半监督的多目标进化模糊聚类算法[J]. 计算机工程与应用, 2017, 53(22): 40-44.
[9]	陈卉，胡立坤，黄钰雯. 采用高斯混合模型及树结构的立体匹配算法[J]. 计算机工程与应用, 2017, 53(20): 195-200.
[10]	郑淼1，郑成增2. 粒子寻优和最小生成树聚类下的WSN能量优化[J]. 计算机工程与应用, 2017, 53(15): 106-110.
[11]	许峰，吴福芳. 自适应协同进化多目标进化算法[J]. 计算机工程与应用, 2016, 52(6): 26-30.
[12]	邵　　超，万春红，李洁颖. 用于多流形分类的核等距映射算法[J]. 计算机工程与应用, 2016, 52(4): 121-128.
[13]	王超学，田利波. 一种改进的多目标合作型协同进化遗传算法[J]. 计算机工程与应用, 2016, 52(2): 18-23.
[14]	赵凤，韩文超，惠房臣. 基于分水岭的多目标核聚类图像分割[J]. 计算机工程与应用, 2015, 51(18): 151-155.
[15]	吴坤安，严宣辉，陈振兴. 一种基于Pareto排序的混合多目标进化算法[J]. 计算机工程与应用, 2015, 51(1): 62-68.