-
摘要: 针对局部搜索类改进型非劣分类遗传算法（Nondominated sorting genetic algorithm Ⅱ，NSGAⅡ）计算过程中种群分布不均的问题，提出一种基于均匀分布的NSGAⅡ（NSGAⅡ based on uniform distribution，NSGAⅡ-UID）多目标优化算法.首先，该算法将种群映射到目标函数对应的超平面，并在该平面上进行聚类以增加解的多样性.其次，为了提高解的分布性，将映射平面进行均匀分区.当分段区间不满足分布性条件时，需要激活分布性加强模块.与此同时在计算过程中分段区间可能会出现种群数量不足或无解的状况，为了保证每个区间所选个体数目相同.最后，采用将最优个体进行极限优化变异的方法来获得缺失个体.实验结果显示该算法可以保证种群跳出局部最优且提高收敛速度，并且在解的分布性和收敛性方面均优于文中其他多目标优化算法.
-
关键词:
- 改进型非劣分类遗传算法 /
- 映射 /
- 聚类 /
- 分布性加强 /
- 局部变异
Abstract: 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) 本文责任编委 付俊 -
表 1 测试函数参数
Table 1 Paramter setting of the test function
函数 pareto前沿特征 维度 种群规模 变量 目标 ZDT1 凸 30 2 1 000 ZDT2 凹 30 2 1 000 ZDT3 凸且非连续 30 2 536 ZDT4 凸 30 2 1 000 ZDT6 凹 10 2 420 DTLZ2 凹 10 3 5 000 DTLZ7 多峰且非连续 20 3 4 700 
下载: 导出CSV
表 2 NSGAII-UID与其他局部搜索算法的ZDT和DTLZ系列实验IGD结果
Table 2 ZDT and DTLZ series performance IGD comparison of different algorithms
算法 NSGAII-UID NSGAII-DLS[13] NSGAII[18] AMOPSO[11] MODE[16] ZDT1 最大值 6.526E-03 9.728E-03 6.466E-03 6.153E-03 4.94E-02 最小值 2.528E-03 4.259E-03 5.367E-03 3.562E-03 4.04E-03 平均值 3.229E-03 6.427E-03 5.755E-03 4.009E-03 4.54E-03 标准差 6.700E-05 3.090E-04 3.390E-04 5.700E-05 2.58E-04 ZDT2 最大值 2.732E-03 7.036E-03 5.806E-03 2.493E-03 3.12E-02 最小值 1.126E-03 4.226E-03 5.134E-03 1.539E-03 3.79E-03 平均值 1.854E-03 5.026E-03 5.355E-03 1.983E-03 4.31E-04 标准差 4.970E-05 1.950E-04 2.020E-04 5.200E-05 2.64E-03 ZDT3 最大值 9.236E-03 9.123E-03 6.105E-03 9.160E-03 1.48E-02 最小值 2.526E-03 5.228E-03 5.447E-03 2.752E-03 3.01E-03 平均值 4.016E-03 6.326E-03 5.834E-03 3.982E-03 6.24E-03 标准差 3.623E-03 2.013E-04 2.020E-04 3.623E-03 7.13E-05 ZDT4 最大值 4.237E-03 4.659E-03 1.117E-01 5.845E-03 8.144E-02 最小值 9.926E-04 4.123E-03 4.623E-03 1.851E-03 3.145E-03 平均值 3.256E-03 4.326E-03 1.655E-02 4.147E-03 1.021E-02 标准差 3.160E-04 1.065E-02 3.174E-02 2.980E-04 2.145E-02 ZDT6 最大值 4.735E-03 5.321E-03 1.498E-02 2.110E-04 1.024E-02 最小值 8.669E-04 2.768E-03 1.119E-02 9.310E-05 6.119E-03 平均值 1.126E-03 3.412E-03 1.286E-02 1.754E-04 8.155E-03 标准差 1.075E-04 9.875E-04 1.004E-03 8.600E-05 4.121E-03 DTLZ2 最大值 2.065E-02 1.2334E-01 2.74E-01 9.991E-02 1.221E-01 最小值 8.431E-02 2.435E-02 7.831E-02 2.180E-02 6.152E-02 平均值 6.271E-02 1.026E-01 1.059E-01 6.595E-02 9.251E-02 标准差 6.241E-04 6.345E-03 8.383E-03 7.241E-04 9.251E-03 DTLZ7 最大值 1.015E-02 1.068E-02 3.208E-02 1.552E-02 4.97E-02 最小值 3.109E-03 3.259E-03 6.14E-03 6.055E-03 7.02E-03 平均值 1.206E-02 1.365E-02 1.799E-02 1.215E-02 2.87E-02 标准差 9.324E-04 1.013E-03 1.294E-03 8.600E-04 2.01E-03
下载: 导出CSV
表 3 NSGAII-UID与其他局部搜索算法的ZDT和DTLZ系列实验SP结果
Table 3 ZDT series performance SP comparison of different algorithms
算法 NSGAII-UID NSGAII[18] AMOPSO[11] cdMOPSO[15] MODE[16] ZDT1 最大值 1.067E-02 7.538E-02 2.907E-02 1.023E-01 1.01E-01 最小值 8.687E-03 4.340E-02 1.512E-02 7.732E-02 4.06E-02 平均值 9.764E-03 5.830E-02 2.551E-02 8.561E-02 5.21E-02 标准差 5.712E-04 9.385E-03 6.710E-04 1.425E-02 1.43E-02 ZDT2 最大值 9.671E-03 8.287E-03 3.336E-02 2.377E-02 2.25E-02 最小值 7.248E-03 6.015E-03 1.999E-02 1.012E-02 1.01E-02 平均值 6.795E-03 7.241E-03 2.257E-02 1.097E-02 1.06E-02 标准差 7.918E-04 7.410E-04 3.245E-03 6.420E-04 4.02E-04 ZDT3 最大值 1.095E-01 1.066E-01 9.957E-02 8.745E-01 7.63E-01 最小值 7.264E-02 8.157E-02 6.489E-02 1.036E-01 1.40E-01 平均值 8.738E-02 9.222E-02 7.025E-02 3.568E-01 3.64E-01 标准差 8.276E-03 8.415E-03 7.171E-03 2.247E-01 2.14E-01 ZDT4 最大值 9.173E-03 4.425E-02 2.954E-02 3.010E-01 6.251E-02 最小值 7.968E-03 3.139E-02 2.130E-02 1.369E-01 3.103E-02 平均值 8.624E-03 3.838E-02 2.654E-02 2.046E-01 3.210E-02 标准差 6.5316E-04 3.837E-03 4.998E-04 9.556E-02 3.914E-3 ZDT6 最大值 8.734E-03 1.013E-02 4.742E-02 4.021E-02 1.214E-02 最小值 6.974E-03 6.851E-03 3.218E-02 1.240E-02 3.899E-03 平均值 7.598E-03 8.266E-03 3.651E-02 3.457E-02 9.145E-03 标准差 9.648E-04 9.180E-04 1.363E-03 3.884E-03 3.251E-04 DTLZ2 最大值 4.598E-02 7.314E-01 3.553E-01 5.897E-01 7.516E-01 最小值 8.431E-02 2.145E-02 7.569E-02 9.32E-02 3.145E-02 平均值 6.271E-02 4.162E-01 2.399E-01 3.562E-01 4.021E-01 标准差 8.381E-04 3.655E-02 9.732E-03 1.772E-02 4.215E-02 DTLZ7 最大值 6.983E-01 7.466E-01 7.564E-01 9.307E-01 9.31E-01 最小值 4.027E-02 6.32E-02 4.491E-02 1.347E-01 1.35E-01 平均值 9.921E-02 4.191E-01 3.758E-01 5.972E-01 5.97E-01 标准差 8.169E-03 7.961E-03 7.593E-03 2.133E-01 2.45E-01
下载: 导出CSV
表 4 NSGAII-UID与其他局部搜索算法的函数计算次数结果
Table 4 Function calculation comparison of different algorithms
下载: 导出CSV
-
[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 doi: 10.1162/evco.1994.2.3.221 [4] Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-Ⅱ. 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 Pareto-based multi-objective evolutionary algorithms. Applied Soft Computing, 2016, 41:400-417 doi: 10.1016/j.asoc.2016.01.029 [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] 朱学军, 陈彤, 薛量, 李峻.多个体参与交叉的Pareto多目标遗传算法.电子学报, 2001, 29(1):106-109 doi: 10.3321/j.issn:0372-2112.2001.01.029Zhu Xue-Jun, Chen Tong, Xue Liang, Li Jun. Pareto multiobjective genetic algorithm with multiple individual participation. Acta Electronica Sinica, 2001, 29(1):106-109 doi: 10.3321/j.issn:0372-2112.2001.01.029 [8] Corne D W, Knowles J D, Oates M J. The Pareto envelope-based selection algorithm for multiobjective optimization. In: Proceedings of the International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer-Verlag, 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 doi: 10.1109/TEVC.2003.810755 [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 doi: 10.1109/TCYB.2017.2692385 [12] 栗三一, 李文静, 乔俊飞.一种基于密度的局部搜索NSGA2算法.控制与决策, 2018, 33(1):60-66 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201801007Li 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 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201801007 [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 doi: 10.1109/TEVC.2012.2204403 [14] Yang S X. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evolutionary Computation, 2008, 16(3):385-416 doi: 10.1162/evco.2008.16.3.385 [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 doi: 10.1109/TEVC.2012.2189404 [16] Basu M. Economic environmental dispatch using multi-objective differential evolution. Applied Soft Computing, 2011, 11(2):2845-2853 doi: 10.1016/j.asoc.2010.11.014 [17] Kim H, Liou M S. Adaptive directional local search strategy for hybrid evolutionary multiobjective optimization. Applied Soft Computing, 2014, 19:290-311 doi: 10.1016/j.asoc.2014.02.019 [18] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017 [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 doi: 10.1109/TEVC.2012.2204403 -
图(7) / 表(4)
计量
- 文章访问数: 2727
- HTML全文浏览量: 436
- PDF下载量: 498
- 被引次数: 0
