快速提高NSGA-II算法双目标优化效率的方法

doi:10.3778/j.issn.1002-8331.2009.34.015

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (34): 47-49.DOI: 10.3778/j.issn.1002-8331.2009.34.015

快速提高NSGA-II算法双目标优化效率的方法

刘敏¹，陈宝兴¹，郑金华²

1.漳州师范学院计算机科学与工程系，福建漳州 363000
2.湘潭大学信息工程学院，湖南湘潭 411105

收稿日期:2008-07-08 修回日期:2009-01-08 出版日期:2009-12-01 发布日期:2009-12-01
通讯作者: 刘敏

Approach to improve bi-objective optimization efficiency of NSGA-II

LIU Min¹，CHEN Bao-xing¹，ZHENG Jin-hua²

1.Department of Computer Science and Engineering，Zhangzhou Normal College，Zhangzhou，Fujian 363000，China
2.Institute of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China

Received:2008-07-08 Revised:2009-01-08 Online:2009-12-01 Published:2009-12-01
Contact: LIU Min

摘要/Abstract

摘要： NSGA-II是一种性能优良的多目标进化算法，近年来非常流行。为了进一步改进NSGA-II在双目标优化时的效率，采取了按需分层的策略，提出了一种新的非支配前沿集分层方法以替代NSGA-II原有的分层方法。与NSGA-II的时间复杂度O（N²）相比，新方法的时间复杂度减少为O（kN＋NlogN），k为所分前沿层数（k<<N）。实验结果也表明，新方法与NSGA-II相比具有更少的非支配前沿层数，支配比较次数和运行时间。

关键词: 多目标进化, 非支配前沿, 按需分层

Abstract: NSGA-II is a multi-objective evolutionary algorithm，and its performance is so good that it has become very popular in the last few years.To improve its bi-objective optimization efficiency，in this paper，a layering strategy according to need is adopted and so a new algorithm to construct the set of non-dominated fronts is proposed to replace the original method of NSGA-II.Compared with the NSGA-II’s computational complexity（O（N²）），the new algorithm’s computational complexity is reduced to O（kN＋NlogN），k is the number of fronts，and k<<N.The experiment results also show that there are fewer layers of non-dominated fronts，counts of dominate compare and much less running-time in the new approach compared with NSGA-II.

Key words: multi-objective evolution, non-dominated front, layering strategy according to need

中图分类号:

TP18

刘敏¹，陈宝兴¹，郑金华². 快速提高NSGA-II算法双目标优化效率的方法[J]. 计算机工程与应用, 2009, 45(34): 47-49.

LIU Min¹，CHEN Bao-xing¹，ZHENG Jin-hua². Approach to improve bi-objective optimization efficiency of NSGA-II[J]. Computer Engineering and Applications, 2009, 45(34): 47-49.

[1]	吉训生，蔡益青. 利用历史信息和限制算子求解MOFJSP[J]. 计算机工程与应用, 2020, 56(2): 272-278.
[2]	耿焕同，周利发，丁洋洋，周山胜. 一种基于新型差分进化模型的MOEA/D改进算法[J]. 计算机工程与应用, 2019, 55(8): 138-146.
[3]	肖俊明，高洪洋，朱永胜，瞿博阳. 考虑新能源接入的电力多目标优化调度[J]. 计算机工程与应用, 2019, 55(23): 241-247.
[4]	顾春华，刘鑫平，罗飞，丁炜超. 基于同步更新外部归档集的NSGA-II改进算法[J]. 计算机工程与应用, 2018, 54(20): 28-34.
[5]	王俊，赵凤. 基于半监督的多目标进化模糊聚类算法[J]. 计算机工程与应用, 2017, 53(22): 40-44.
[6]	许峰，吴福芳. 自适应协同进化多目标进化算法[J]. 计算机工程与应用, 2016, 52(6): 26-30.
[7]	王超学，田利波. 一种改进的多目标合作型协同进化遗传算法[J]. 计算机工程与应用, 2016, 52(2): 18-23.
[8]	赵凤，韩文超，惠房臣. 基于分水岭的多目标核聚类图像分割[J]. 计算机工程与应用, 2015, 51(18): 151-155.
[9]	吴坤安，严宣辉，陈振兴. 一种基于Pareto排序的混合多目标进化算法[J]. 计算机工程与应用, 2015, 51(1): 62-68.
[10]	李志强，蔺想红. 多目标优化非支配集构造方法的研究进展[J]. 计算机工程与应用, 2013, 49(19): 31-35.
[11]	梁浩，林丹，马楠. 基于ε-支配的自适应多目标进化算法[J]. 计算机工程与应用, 2011, 47(34): 39-43.
[12]	薛胜军，杨明. 改进的自适应邻域的多目标进化算法[J]. 计算机工程与应用, 2011, 47(25): 49-53.
[13]	李亚林，陈静，罗彪，任亚峰，李密青. 一种求解鲁棒优化问题的多目标进化方法[J]. 计算机工程与应用, 2011, 47(24): 58-61.
[14]	文诗华，郑金华. NSGA-II中一种改进的分布性保持策略[J]. 计算机工程与应用, 2010, 46(33): 49-53.
[15]	龚正，王毅，周佳. 一种改进的多目标演化算法[J]. 计算机工程与应用, 2010, 46(26): 43-45.

快速提高NSGA-II算法双目标优化效率的方法

Approach to improve bi-objective optimization efficiency of NSGA-II

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics