一种基于均匀分布策略的NSGAⅡ算法
|
摘要
针对局部搜索类改进型非劣分类遗传算法(Nondominated sorting genetic algorithm Ⅱ, NSGAⅡ)计算过程中种群分布不均的问题,提出一种基于均匀分布的NSGAⅡ (NSGAⅡ based on uniform distribution, NSGAⅡ-UID)多目标优化算法.首先,该算法将种群映射到目标函数对应的超平面,并在该平面上进行聚类以增加解的多样性.其次,为了提高解的分布性,将映射平面进行均匀分区.当分段区间不满足分布性条件时,需要激活分布性加强模块.与此同时在计算过程中分段区间可能会出现种群数量不足或无解的状况,为了保证每个区间所选个体数目相同.最后,采用将最优个体进行极限优化变异的方法来获得缺失个体.实验结果显示该算法可以保证种群跳出局部最优且提高收敛速度,并且在解的分布性和收敛性方面均优于文中其他多目标优化算法.
Because the population distribution is uneven during the local search process of nondominated sorting genetic algorithm Ⅱ(NSGAⅡ), a multi-objective optimization algorithm for NSGAⅡ based on uniform distribution(NSGAⅡUID) is proposed. Firstly, the population which has been clustered is mapped to the hyperplane of the corresponding objective function, then the diversity of population is increased. Secondly, in order to improve the distribution uniformity of the solution, the mapping plane is evenly partitioned. However, when the distribution condition is not satisfied in the corresponding partition, the distribution enhancement module is activated. At the same time the individuals may be insufficient or empty in the piecewise interval during the calculation process, in order to ensure that the number of selected individuals in each interval is the same, the local variation method of the best solution is proposed to get the missing individuals lastly. The experimental results show that the method ensures that the population can jump out the local optimal and the convergence speed can be improved. And the distribution and convergence of this algorithm is superior to the other multi-objective optimization algorithms.
Because the population distribution is uneven during the local search process of nondominated sorting genetic algorithm Ⅱ(NSGAⅡ), a multi-objective optimization algorithm for NSGAⅡ based on uniform distribution(NSGAⅡUID) is proposed. Firstly, the population which has been clustered is mapped to the hyperplane of the corresponding objective function, then the diversity of population is increased. Secondly, in order to improve the distribution uniformity of the solution, the mapping plane is evenly partitioned. However, when the distribution condition is not satisfied in the corresponding partition, the distribution enhancement module is activated. At the same time the individuals may be insufficient or empty in the piecewise interval during the calculation process, in order to ensure that the number of selected individuals in each interval is the same, the local variation method of the best solution is proposed to get the missing individuals lastly. The experimental results show that the method ensures that the population can jump out the local optimal and the convergence speed can be improved. And the distribution and convergence of this algorithm is superior to the other multi-objective optimization algorithms.
引文
1 Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms. In:Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale,NJ, USA:L. Erlbaum Associates, Inc., 1985. 93-100
2 Fonseca C M, Fleming P J. Genetic algorithms for multiobjective optimization:Formulation, discussion and generalization. In:Proceedings of the 5th International Conference. San Mateo, CA:Morgan Kauffman Publishers, 1993.416-423
3 Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 1994, 2(3):221-248
4 Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-II. In:Proceedings of the 6th International Conference on Parallel Problem Solving from Nature.Berlin, Heidelberg:Springer, 2000. 849-858
5 Ahmadi A. Memory-based adaptive partitioning(MAP)of search space for the enhancement of convergence in Paretobased multi-objective evolutionary algorithms. Applied Soft Computing, 2016, 41:400-417
6 Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization. In:Proceedings of the 2nd International Conference on Genetic Algorithms.Hillsdale, NJ, USA:L. Erlbaum Associates, Inc., 1987.41-49
7 Zhu Xue-Jun, Chen Tong, Xue Liang, Li Jun. Pareto multiobjective genetic algorithm with multiple individual participation. Acta Electronica Sinica, 2001, 29(1):106-109(朱学军,陈彤,薛量,李峻.多个体参与交叉的Pareto多目标遗传算法.电子学报, 2001, 29(1):106-109)
8 Corne D W, Knowles J D, Oates M J. The Pareto envelopebased selection algorithm for multiobjective optimization.In:Proceedings of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany:SpringerVerlag, 2000. 839-848
9 Knowles J, Corne D. Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Transactions on Evolutionary Computation, 2003, 7(2):100-116
10 Morse J N. Reducing the size of the nondominated set:pruning by clustering. Computers&Operations Research, 1980,7(1-2):55-66
11 Han H G, Lu W, Qiao J F. An adaptive multiobjective particle swarm optimization based on multiple adaptive methods.IEEE Transactions on Cybernetics, 2017, 47(9):2754-2767
12 Li San-Yi, Li Wen-Jing, Qiao Jun-Fei. A local search strategy based on density for NSGA2 algorithm. Control and Decision, 2018, 33(1):60-66(栗三一,李文静,乔俊飞.一种基于密度的局部搜索NSGA2算法.控制与决策, 2018, 33(1):60-66)
13 Sindhya K, Miettinen K, Deb K. A hybrid framework for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(4):495-511
14 Yang S X. Genetic algorithms with memory-and elitismbased immigrants in dynamic environments. Evolutionary Computation, 2008, 16(3):385-416
15 Helwig S, Branke J, Mostaghim S. Experimental analysis of bound handling techniques in particle swarm optimization.IEEE Transactions on Evolutionary Computation, 2013,17(2):259-271
16 Basu M. Economic environmental dispatch using multiobjective differential evolution. Applied Soft Computing,2011, 11(2):2845-2853
17 Kim H, Liou M S. Adaptive directional local search strategy for hybrid evolutionary multiobjective optimization. Applied Soft Computing, 2014, 19:290-311
18 Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197
19 Sindhya K, Miettinen K, Deb K. A hybrid framework for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(4):495-511
2 Fonseca C M, Fleming P J. Genetic algorithms for multiobjective optimization:Formulation, discussion and generalization. In:Proceedings of the 5th International Conference. San Mateo, CA:Morgan Kauffman Publishers, 1993.416-423
3 Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 1994, 2(3):221-248
4 Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-II. In:Proceedings of the 6th International Conference on Parallel Problem Solving from Nature.Berlin, Heidelberg:Springer, 2000. 849-858
5 Ahmadi A. Memory-based adaptive partitioning(MAP)of search space for the enhancement of convergence in Paretobased multi-objective evolutionary algorithms. Applied Soft Computing, 2016, 41:400-417
6 Goldberg D E, Richardson J. Genetic algorithms with sharing for multimodal function optimization. In:Proceedings of the 2nd International Conference on Genetic Algorithms.Hillsdale, NJ, USA:L. Erlbaum Associates, Inc., 1987.41-49
7 Zhu Xue-Jun, Chen Tong, Xue Liang, Li Jun. Pareto multiobjective genetic algorithm with multiple individual participation. Acta Electronica Sinica, 2001, 29(1):106-109(朱学军,陈彤,薛量,李峻.多个体参与交叉的Pareto多目标遗传算法.电子学报, 2001, 29(1):106-109)
8 Corne D W, Knowles J D, Oates M J. The Pareto envelopebased selection algorithm for multiobjective optimization.In:Proceedings of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany:SpringerVerlag, 2000. 839-848
9 Knowles J, Corne D. Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Transactions on Evolutionary Computation, 2003, 7(2):100-116
10 Morse J N. Reducing the size of the nondominated set:pruning by clustering. Computers&Operations Research, 1980,7(1-2):55-66
11 Han H G, Lu W, Qiao J F. An adaptive multiobjective particle swarm optimization based on multiple adaptive methods.IEEE Transactions on Cybernetics, 2017, 47(9):2754-2767
12 Li San-Yi, Li Wen-Jing, Qiao Jun-Fei. A local search strategy based on density for NSGA2 algorithm. Control and Decision, 2018, 33(1):60-66(栗三一,李文静,乔俊飞.一种基于密度的局部搜索NSGA2算法.控制与决策, 2018, 33(1):60-66)
13 Sindhya K, Miettinen K, Deb K. A hybrid framework for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(4):495-511
14 Yang S X. Genetic algorithms with memory-and elitismbased immigrants in dynamic environments. Evolutionary Computation, 2008, 16(3):385-416
15 Helwig S, Branke J, Mostaghim S. Experimental analysis of bound handling techniques in particle swarm optimization.IEEE Transactions on Evolutionary Computation, 2013,17(2):259-271
16 Basu M. Economic environmental dispatch using multiobjective differential evolution. Applied Soft Computing,2011, 11(2):2845-2853
17 Kim H, Liou M S. Adaptive directional local search strategy for hybrid evolutionary multiobjective optimization. Applied Soft Computing, 2014, 19:290-311
18 Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197
19 Sindhya K, Miettinen K, Deb K. A hybrid framework for evolutionary multi-objective optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(4):495-511