基于个体邻域的改进NSGA-Ⅱ算法
|
摘要
带有精英策略的非支配排序遗传算法(NSGA-II)是在NSGA的基础之上,提出拥挤度和拥挤度比较算子,代替了需要指定共享半径的适应度共享策略,是解决多目标优化问题的经典算法之一。但是NSGA-II算法在保持种群多样性时采取的拥挤距离排挤机制有着pareto前沿分布不均匀的缺陷,因此,提出一种基于个体邻域的改进NSGA-II算法SN-NSGA2。SN-NSGA2将密度聚类算法DBSCAN中邻域的思想应用到排挤机制中去,提出一种个体邻域的构建方法,采用相应的淘汰策略去除个体邻域中的其他邻居个体。实验结果表明相对于NSGA-II算法来说,新算法求出的pareto解集有着更好的分布性以及良好的收敛性。
The Non-dominated Sorting Genetic Algorithm with elite strategy(NSGA-II)based on NSGA is one of the classical algorithms to solve multi-objective optimization problems. Congestion and congestion comparison operator are proposed by NSGA-II, which replace the fitness sharing strategy which needs to specify the shared radius. However, the exclusion mechanism based on crowding distance in NSGA-II to maintain population diversity has a defect in the front of the pareto frontier. Therefore, an improved algorithm named SN-NSGA2 which considers individual neighborhood is proposed. The idea of neighborhood in the density clustering algorithm DBSCAN is applied to new exclusion mechanism,and simultaneously a method of constructing individual neighborhood with corresponding elimination strategy is put forward. Experimental results show that the new algorithm has better distribution and good convergence.
The Non-dominated Sorting Genetic Algorithm with elite strategy(NSGA-II)based on NSGA is one of the classical algorithms to solve multi-objective optimization problems. Congestion and congestion comparison operator are proposed by NSGA-II, which replace the fitness sharing strategy which needs to specify the shared radius. However, the exclusion mechanism based on crowding distance in NSGA-II to maintain population diversity has a defect in the front of the pareto frontier. Therefore, an improved algorithm named SN-NSGA2 which considers individual neighborhood is proposed. The idea of neighborhood in the density clustering algorithm DBSCAN is applied to new exclusion mechanism,and simultaneously a method of constructing individual neighborhood with corresponding elimination strategy is put forward. Experimental results show that the new algorithm has better distribution and good convergence.
引文
[1] Marler R T,Arora J S.Survey of multi-objective optimi-zation methods for engineering[J].Structural&Multidis-ciplinary Optimization,2004,26(6):369-395.
[2] Konak A,Coit D W,Smith A E.Multi-objective optimiza-tion using genetic algorithms:a tutorial[J].ReliabilityEngineering&System Safety,2006,91(9):992-1007.
[3] Li H,Zhang Q.Multiobjective optimization problemswith complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[4] Deb K,Mohan M,Mishra S.A fast multi-objective evolutionaryalgorithm for finding well-spread pareto-optimal solutions[R].Kanpur,India:Indian Institute of Technology,2003.
[5] Srinivas N,Deb K.Muiltiobjective optimization using non-dominated sorting in genetic algorithms[M].[S.l.]:MITPress,1994.
[6] Zitzler E,Thiele L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[7] Deb K,Agrawal S,Pratap A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objectiveoptimization:NSGA-II[C]//International Conference on Par-allel Problem Solving From Nature,2000:849-858.
[8]徐江雁,仲高艳,杨守峰.改进NSGA-Ⅱ算法及其在切削加工参数优化中的应用[J].计算机工程与应用,2017,53(13):227-234.
[9]陈志旺,黄兴旺,陈志兴,等.区间多目标优化非支配排序云模型算法[J].计算机工程与应用,2017,53(22):143-149.
[10]汪文文,方玺,何朗,等.NSGA-II算法的改进及其在应急管理中的应用[J].计算机工程与应用,2018,54(16):241-247.
[11]黄超,胡德敏,余星.一种基于向量空间模型的NSGA-Ⅱ改进算法[J].小型微型计算机系统,2015,36(2):391-396.
[12]王进,周宇轩,戴伟,等.NSGA-II算法的改进及其在风火机组多目标动态组合优化中的应用[J].电力系统及其自动化学报,2017,29(2):107-111.
[13] Yliniemi L,Tumer K.Multi-objective multiagent creditassignment in reinforcement learning and NSGA-II[J].Soft Computing,2016,20(10):1-19.
[14] Jensen M T.Reducing the run-time complexity of multi-objective EAs:the NSGA-II and other algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(5):503-515.
[15] Jeyadevi S,Baskar S,Babulal C K,et al.Solving multi-objective optimal reactive power dispatch using modifiedNSGA-II[J].International Journal of Electrical Power&Energy Systems,2011,33(2):219-228.
[16] Wang X D,Hirsch C,Kang S,et al.Multi-objective opti-mization of turbomachinery using improved NSGA-II andapproximation model[J].Computer Methods in AppliedMechanics&Engineering,2011,200(9/12):883-895.
[17] Ester M,Kriegel H P,Xu X.A density-based algorithmfor discovering clusters a density-based algorithm fordiscovering clusters in large spatial databases withnoise[C]//International Conference on Knowledge Discov-ery and Data Mining,1996:226-231.
[18] Ruiz C,Spiliopoulou M,Menasalvas E.Density-basedsemi-supervised clustering[J].Data Mining&Knowl-edge Discovery,2010,21(3):345-370.
[19]谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA2算法[J].计算机科学,2013,40(10):235-238.
[20] Schott J R.Fault tolerant design using single and multi-criteria genetic algorithm optimization[J].Cellular Immu-nology,1995,37(1):1-13.
[21] Veldhuizen D A V,Lamont G B.Evolutionary computa-tion and convergence to a pareto front[C]//Genetic Pro-gramming Conference,1998:221-228.
[2] Konak A,Coit D W,Smith A E.Multi-objective optimiza-tion using genetic algorithms:a tutorial[J].ReliabilityEngineering&System Safety,2006,91(9):992-1007.
[3] Li H,Zhang Q.Multiobjective optimization problemswith complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2009,13(2):284-302.
[4] Deb K,Mohan M,Mishra S.A fast multi-objective evolutionaryalgorithm for finding well-spread pareto-optimal solutions[R].Kanpur,India:Indian Institute of Technology,2003.
[5] Srinivas N,Deb K.Muiltiobjective optimization using non-dominated sorting in genetic algorithms[M].[S.l.]:MITPress,1994.
[6] Zitzler E,Thiele L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.
[7] Deb K,Agrawal S,Pratap A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objectiveoptimization:NSGA-II[C]//International Conference on Par-allel Problem Solving From Nature,2000:849-858.
[8]徐江雁,仲高艳,杨守峰.改进NSGA-Ⅱ算法及其在切削加工参数优化中的应用[J].计算机工程与应用,2017,53(13):227-234.
[9]陈志旺,黄兴旺,陈志兴,等.区间多目标优化非支配排序云模型算法[J].计算机工程与应用,2017,53(22):143-149.
[10]汪文文,方玺,何朗,等.NSGA-II算法的改进及其在应急管理中的应用[J].计算机工程与应用,2018,54(16):241-247.
[11]黄超,胡德敏,余星.一种基于向量空间模型的NSGA-Ⅱ改进算法[J].小型微型计算机系统,2015,36(2):391-396.
[12]王进,周宇轩,戴伟,等.NSGA-II算法的改进及其在风火机组多目标动态组合优化中的应用[J].电力系统及其自动化学报,2017,29(2):107-111.
[13] Yliniemi L,Tumer K.Multi-objective multiagent creditassignment in reinforcement learning and NSGA-II[J].Soft Computing,2016,20(10):1-19.
[14] Jensen M T.Reducing the run-time complexity of multi-objective EAs:the NSGA-II and other algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(5):503-515.
[15] Jeyadevi S,Baskar S,Babulal C K,et al.Solving multi-objective optimal reactive power dispatch using modifiedNSGA-II[J].International Journal of Electrical Power&Energy Systems,2011,33(2):219-228.
[16] Wang X D,Hirsch C,Kang S,et al.Multi-objective opti-mization of turbomachinery using improved NSGA-II andapproximation model[J].Computer Methods in AppliedMechanics&Engineering,2011,200(9/12):883-895.
[17] Ester M,Kriegel H P,Xu X.A density-based algorithmfor discovering clusters a density-based algorithm fordiscovering clusters in large spatial databases withnoise[C]//International Conference on Knowledge Discov-ery and Data Mining,1996:226-231.
[18] Ruiz C,Spiliopoulou M,Menasalvas E.Density-basedsemi-supervised clustering[J].Data Mining&Knowl-edge Discovery,2010,21(3):345-370.
[19]谢承旺,李凯,廖国勇.一种带差分局部搜索的改进型NSGA2算法[J].计算机科学,2013,40(10):235-238.
[20] Schott J R.Fault tolerant design using single and multi-criteria genetic algorithm optimization[J].Cellular Immu-nology,1995,37(1):1-13.
[21] Veldhuizen D A V,Lamont G B.Evolutionary computa-tion and convergence to a pareto front[C]//Genetic Pro-gramming Conference,1998:221-228.