一种均匀聚集距离的改进NSGA-Ⅱ算法

doi:10.3969/j.issn.1001-2400.2016.03.009

西安电子科技大学学报 ›› 2016, Vol. 43 ›› Issue (3): 49-54+130.doi: 10.3969/j.issn.1001-2400.2016.03.009

一种均匀聚集距离的改进NSGA-Ⅱ算法

王明昭;王宇平;王晓丽;卫珍

(西安电子科技大学计算机学院，陕西西安 710071)

收稿日期:2015-03-10 出版日期:2016-06-20 发布日期:2016-07-16
通讯作者: 王明昭
作者简介:王明昭(1978-)，男，西安电子科技大学博士研究生， E-mail: whaoazj@vip.sina.com．
基金资助:
国家自然科学基金资助项目(61402350, U1404622)；中央高校基本科研业务费专项资金资助项目(BDZ021430)

Improved NSGA-Ⅱ algorithm based on the uniformly crowding distance

WANG Mingzhao;WANG Yuping;WANG Xiaoli;WEI Zhen

(School of Computer Science and Technology, Xidian Univ., Xi'an 710071, China)

Received:2015-03-10 Online:2016-06-20 Published:2016-07-16
Contact: WANG Mingzhao

摘要/Abstract

摘要：

遗传算法已经在多目标优化问题中得到了广泛应用及深入研究，NSGA-Ⅱ是求解多目标优化问题的代表算法之一，其中聚集距离在收敛性和分布均匀性上均起到了重要作用，但算法没有充分考虑微观的个体本身和宏观的种群整体的作用．为了能更合理地估计区域密度，使所求解集更好更均匀地收敛于Pareto最优边界，笔者基于均匀聚集区间和基尼权重构造了一种均匀聚集距离算子，并基于该算子提出了一种改进的NSGA-Ⅱ算法．最后，通过对6个标准多目标测试问题的实验验证了算法的有效性．

关键词: 均匀聚集区间, 基尼权重, 均匀聚集距离, 多目标优化

Abstract:

With the wide application and further study of the genetic algorithm in multi-objective optimization problems, the NSGA-Ⅱ has been one of the representative evolutionary algorithms for multi-objective optimization problems. Crowding distance in the NSGA-Ⅱ plays an important role in convergence and uniform distribution of the solutions, but the NSGA-Ⅱ does not fully take the effect of each individual and the whole population into consideration. To estimate the region density more reasonably so as to make the solution set more uniformly converge to the Pareto optimal front, we design a uniformly crowding distance operator based on the uniformly crowding range and Gini weight, and propose an improved NSGA-Ⅱ algorithm. Finally, the effectiveness of the proposed algorithm is verified by experiments on six multi-objective optimization test functions.

Key words: uniformly crowding range, Gini weight, uniformly crowding distance, multi-objective optimization

王明昭;王宇平;王晓丽;卫珍. 一种均匀聚集距离的改进NSGA-Ⅱ算法[J]. 西安电子科技大学学报, 2016, 43(3): 49-54+130.

WANG Mingzhao;WANG Yuping;WANG Xiaoli;WEI Zhen. Improved NSGA-Ⅱ algorithm based on the uniformly crowding distance[J]. Journal of Xidian University, 2016, 43(3): 49-54+130.

参考文献

［1］ BANDYOPADHYAY S, MAULIK U, COELLO C A, et al. Guest Editorial: Special Issue on Advances in Multiobjective Evolutionary Algorithms for Data Mining ［J］. IEEE Transactions on Evolutionary Computation, 2014, 18(1): 1-3.
［2］ SINDHYA K, MIETTINEN K, DEB K. A Hybrid Framework for Evolutionary Multiobjective Optimization ［J］. IEEE Transactions on Evolutionary Computation, 2013, 17(4): 495-511.
［3］ LIAO H L, WU Q H. Multi-objective Optimization by Learning Automata ［J］. Journal of Global Optimization, 2013, 55(2): 459-487.
［4］李蕊, 史小卫, 徐乐, 等. 竞争差分进化算法及其在共形阵综合中的应用［J］. 西安电子科技大学学报, 2012, 39(3): 114-119.
LI Rui, SHI Xiaowei, XU Le, et al. Synthesis of a Conformal Antenna Array Using the Competition Differential Evolution Strategy ［J］. Journal of Xidian University, 2012, 39(3): 114-119.
［5］郭金维, 蒲绪强, 高祥, 等. 一种改进的多目标决策指标权重计算方法［J］. 西安电子科技大学学报, 2014, 41(6): 118-125
GUO Jinwei, PU Xuqiang, GAO Xiang, et al. Improved Method on Weights Determination of Indexes in Multi-objective Decision ［J］. Journal of Xidian University, 2014, 41(6): 118-125.
［6］ SRINIVAS N, DEB K. Muiltiobjective Optimization Using Nondominated Sorting In Genetic Algorithms ［J］. Evolutionary Computation, 1994, 2(3): 221-248.
［7］ DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
［8］ RODRIGUEZ J G, SALAS R. The Gini Coefficient: Majority Voting and Social Welfare ［J］. Journal of Economic Theory, 2014, 152: 214-223.
［9］ THAKUR M, MEGHWANI S S, JALOTA H. A Modified Real Coded Genetic Algorithm for Constrained Optimization ［J］. Applied Mathematics and Computation, 2014, 235: 292-317.
［10］ KIM H, LIOU M S. Adaptive Directional Local Search Strategy for Hybrid Evolutionary Multiobjective Optimization［J］. Applied Soft Computing, 2014, 19: 290-311.
［11］ DEB K, JAIN S. Running Performance Metrics for Evolutionary Multiobjective Optimization［R］. KanGAL Report, Kanpur: Indian Institute of Technology, 2002.
［12］ LEUNG Y W, WANG Y P. U-measure: A Quality Measure for Multiobjective Programming［J］. IEEE Transacions on Systems, Man, and Cybernetics: Part C, 2003, 33(3): 337-343.

[1]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[2]	杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.
[3]	杨五四,陈莉,王毅,张茂省. 一种适应度排序的高维多目标粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(3): 78-84.
[4]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[5]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.
[6]	韩亚敏;柴争义;李亚伦;朱思峰. 长尾群组推荐的免疫多目标优化实现[J]. 西安电子科技大学学报, 2018, 45(3): 109-116.
[7]	王丹青;李萍. 利用GEK代理模型的天线快速多目标优化设计[J]. 西安电子科技大学学报, 2018, 45(2): 129-134+165.
[8]	雷雨;焦李成;公茂果;李玲玲. 求解多目标考试时间表问题的NNIA改进算法[J]. 西安电子科技大学学报, 2016, 43(2): 157-161+192.
[9]	代才;王宇平;何晓光. 高维多目标问题的排序新方法[J]. J4, 2014, 41(6): 89-94.
[10]	董宁;王宇平. 求解约束优化问题的偏好多目标进化算法[J]. J4, 2014, 41(1): 98-104+188.
[11]	陈国强;王宇平. 分解多目标优化揭示复杂网络社区层次结构[J]. J4, 2013, 40(3): 205-211.
[12]	刘若辰;焦李成;雷七峰;方玲芬. 一种新的差分进化约束优化算法[J]. J4, 2011, 38(1): 47-53.
[13]	马晶晶;杨咚咚;焦李成. 免疫非支配自适应粒子群多目标优化[J]. J4, 2010, 37(5): 846-851.
[14]	尚荣华;焦李成;吴建设;马文萍;李阳阳. 用于非监督特征选择的免疫克隆多目标优化算法[J]. J4, 2010, 37(1): 18-22.
[15]	尚荣华;马文萍;焦李成;张伟. 用于求解多目标优化问题的克隆选择算法 [J]. J4, 2007, 34(5): 716-721.

一种均匀聚集距离的改进NSGA-Ⅱ算法

Improved NSGA-Ⅱ algorithm based on the uniformly crowding distance

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10