Computer Science ›› 2019, Vol. 46 ›› Issue (10): 222-228.doi: 10.11896/jsjkx.181001852

• Artificial Intelligence • Previous Articles     Next Articles

Improved NSGA-II Algorithm Based on Loser Group and Hybrid Coding Strategy

LIU Xin-ping, GU Chun-hua, LUO Fei, DING Wei-chao   

  1. (School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)
  • Received:2018-10-07 Revised:2019-03-07 Online:2019-10-15 Published:2019-10-21

Abstract: The congestion coefficient operator of NSGA-II in elite selection can not optimize the distribution of local congestion area effectively,and some individuals closer to Pareto optimal solution set will be eliminated.An improved algorithm based on loser group and hybrid encoding strategy (LGHC-NSGA-II) was proposed to overcome the shortcomingthat excellent individuals are not retained in the congestion coefficient operator.Referring to the double-losing elimination system in chess games,an external archive set of loser group is constructed.After the iteration,the archive set is merged with the last generation parent population,and the distribution coefficient is optimized by cyclic congestion coefficient ranking strategy.At the same time,a hybrid coding strategy was proposed to overcome the shortcomings of traditional coding methods in global or local space,which effectively improves the convergence of the algorithm.The test results on ZDT series problems show that the improved algorithm is superior to eight multi-objective evolutionary algorithms in convergence,distribution and robustness.

Key words: Cyclic congestion coefficient ranking, Hybrid coding, Loser group, Multi-objective evolutionary algorithm, NSGA-II

CLC Number: 

  • TP301
[1]ZITZLER E,THIELE L.Multi-objective evolutionary algo-rithms:A comparative case study and the strength pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[2]CORNE D W,KNOWLES J D,OATES M J.The Pareto Envelope-Based Selection Algorithm for Multiobjective Optimization[C]//International Conference on Parallel Problem Solving From Nature.Springer-Verlag,2000:839-884.
[3]SRINIVAS N,DEB K.Multi-objective optimization using non-dominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.
[4]COELLO C A C,PULIDO G T,LECHUGA M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.
[5]DEB K,AGRAWAL S,PRATAP A,et al.A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization:NSGA-II//International Conference on Parallel Problem Solving from Nature.Springer,2002.
[6]ZHANG Q,LI H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[7]COELLO C A C.Evolutionary multi-objective optimization:a historical view of the field.IEEE Computational Intelligence Magazine,2006,1(1):28-36.
[8]DEB K,JAIN H.An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach,Part I:Solving Problems With Box Constraints[J].IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.
[9]LI M,ZHENG J,WU J.Improving NSGA-II Algorithm Based on Minimum Spanning Tree[C]//Asia-Pacific Conference on Simulated Evolution and Learning.Springer Berlin Heidelberg,2008:170-179.
[10]LUO C Y,CHEN M Y,ZHANG C Y.Improved NSGA-Ⅱ algorithm with circular crowded sorting[J].Control and Decision,2010,25(2):227-231.(in Chinese)
罗辞勇,陈民铀,张聪誉.采用循环拥挤排序策略的改进NSGA-Ⅱ算法[J].控制与决策,2010,25(2):227-231.
[11]SATO Y,SATO M,MIYAKAWA M.Distributed NSGA-II with migration using compensation on many-core processors for improving performance and accuracy[C]//the Genetic and Evolutionary Computation Conference Companion.2017:161-162.
[12]KUMAR M,GURIA C.The elitist non-dominated sorting ge-netic algorithm with inheritance(i-NSGA-II)and its jumping gene adaptations for multi-objective optimization[J].Information Sciences,2017,s382-383:15-37.
[13]XIE C W,LI K,LIAO G Y.Improved NSGA2 Algorithm with Differential Evolution Local Search[J].Computer Science,2013,40(10):235-238.(in Chinese)
谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA2算法[J].计算机科学,2013,40(10):235-238.
[14]SCHOTT J R.Fault Tolerant Design Using Single and Multicr-iteria Genetic Algorithm Optimization[J].Cellular Immunology,1995,37(1):1-13.
[15]VACHHANI V L,DABHI V K,PRAJAPATI H B.Improving NSGA-II for solving multi objective function optimization problems[C]//International Conference on Computer Communication and Informatics.IEEE,2016:1-6.
[16]LAI W X,DENG Z M.Improved NSGA2 Algorithm Based on Dominant Strength[J].Computer Science,2018,45(6):187-192.(in Chinese)
赖文星,邓忠民.基于支配强度的NSGA2改进算法[J].计算机科学,2018,45(6):187-192.
[17]ZITZLER E,DEB K,THIELE L.Comparison of Multiobjective Evolutionary Algorithms:Empirical Results[J].Evolutionary Computation,2000,8(2):173-195.
[18]HOLLAND J H.Adaptation in natural and artificial systems [J].Ann Arbor,1992,6(2):126-137.
[19]GRAY F.Pulse code communication[P].U.s.patent2,1953.
[20]ZITZLER E,THIELE L.Multiobjective evolutionary algo-rithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[21]ZHOU H,MENG L M,WANG L P,et al.Multi-objective Evolutionary Algorithm Based on Decomposition Using Dynamic Neighbor[J].Mini-micro Systems,2017,38(9):2039-2044.(in Chinese)
周欢,孟利民,王丽萍,等.动态邻域的分解多目标进化算法[J].小型微型计算机系统,2017,38(9):2039-2044.
[22]NEBRO A J,DURILLO J J,GARCIA-NIETO J,et al.SMPSO:A new PSO-based metaheuristic for multi-objective optimization[C]//Computational Intelligence in Miulticriteria Decision-ma-king,IEEE,2009:66-73.
[23]HU W,YEN G G,ZHANG X.Multiobjective Particle Swarm Optimization Based on Pareto Entropy[J].Journal of Software,2014,25(5):1025-1050.(in Chinese)
胡旺,YEN G G,张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报,2014(5):1025-1050.
[24]LIN Q,CHEN J,ZHAN Z H,et al.A Hybrid Evolutionary Immune Algorithm for Multiobjective Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2016,20(5):711-729.
[25]MA Y F,LI A R,YU H M,et al.Dynamic Crowding Distance-based Hybrid Immune Algorithm for Multi-objective Optimization Problem[J].Computer Science,2018,45(6):63-68.(in Chinese)
马元锋,李昂儒,余慧敏,等.基于动态拥挤距离的混合多目标免疫优化算法[J].计算机科学,2018,45(6):63-68.
[26]VAN D A,GARY V,LAMONT B.Multiobjective Evolutionary Algorithm Research:A History and Analysis[J].Evolutionary Computation,1998,8(2):125-147.
[27]VAN VELDHUIZEN D A,LAMONT G B.Evolutionary computation and convergence to a pareto front[C]//Koza J R.Late Breaking Papers at the Genetic Programming 1998 Conference.Stanford University,California,1998:221-228.
[1] LAI Wen-xing, DENG Zhong-min. Improved NSGA2 Algorithm Based on Dominant Strength [J]. Computer Science, 2018, 45(6): 187-192.
[2] MA Qing. Multi-objective Evolutionary Algorithm Based Weight Vectors Generation Method of MOEA/D [J]. Computer Science, 2016, 43(Z11): 117-122.
[3] AI Hao-jun,GONG Su-wen and YUAN Yuan-ming. Research of Cloud Computing Virtual Machine Allocated Strategy on Multi-objective Evolutionary Algorithm [J]. Computer Science, 2014, 41(6): 48-53.
[4] . Pareto-based Multi-object Clonal Evolutionary Algorithm [J]. Computer Science, 2012, 39(Z6): 489-492.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!