Improved NSGA-III Algorithm Based on Reference Point Selection Strategy
GENG Huantong1,2, DAI Zhongbin1, WANG Tianlei1, XU Ke1
1.School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044; 2.Nanjing Joint Center of Atmospheric Research, Meteorological Bureau of Jiangsu Province, Nanjing 210009
Abstract：The traditional multi-objective evolutionary algorithm ignores distribution information of the population in the decision space and Pareto front shape of the optimization problem is not taken into account. To solve the problems, an improved NSGA-III algorithm based on reference point selection strategy is proposed. Firstly, according to the entropy thought in information theory, the entropy difference between two adjacent generations is calculated in line with the distribution characteristics of the population in the decision-making space, and the evolutionary status of the population is determined. Then, in the light of the distribution characteristics of the population in the target space, the importance of reference points is evaluated via statistical information of the number of the individuals associated with reference points. Finally, redundant and invalid reference points are removed according to the importance characteristics of reference points in the middle and late period of population evolution. Reserved reference points can adapt to the population size and Pareto frontier, and the selected reference points are exploited to guide the evolution direction of the population and accelerate the convergence and optimization efficiency. Experiments on test function sets indicate the significant advantages of the proposed algorithm in convergence and distribution.
[1] ISHIBUCHI H, AKEDO N, NOJIMA Y, et al. Behavior of Multiobjective Evolutionary Algorithms on Many-Objective Knapsack Pro-blems. IEEE Transactions on Evolutionary Computation, 2015, 19(2): 264-283. [2] PIERRO F, KHU S, SAVIC D A, et al. An Investigation on Prefe-rence Order Ranking Scheme for Multiobjective Evolutionary Optimi-zation. IEEE Transactions on Evolutionary Computation, 2007, 11(1): 17-45. [3] YANG S X, LI M Q, LIU X H, et al. A Grid-Based Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 2013, 17(5): 721-736. [4] ZHANG X Y, TIAN Y, JIN Y C, et al. A Knee Point-Driven Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 2015, 19(6): 761-776. [5] ZHU C W, XU L H, GOODMAN E D, et al. Generalization of Pareto-Optimality for Many-Objective Evolutionary Optimization. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 299-315. [6] TIAN Y, CHENG R, ZHANG X Y, et al. A Strengthened Dominance Relation Considering Convergence and Diversity for Evolutio-nary Many-Objective Optimization. IEEE Transactions on Evolutio-nary Computation, 2019, 23(2): 331-345. [7] ZHANG Q F, LI H. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. [8] HO-HUU V, HARTJES S, VISSER H G, et al. An Improved MO-EA/D Algorithm for Bi-objective Optimization Problems with Complex Pareto Fronts and Its Application to Structural Optimization. Expert Systems with Applications, 2018, 92: 430-446. [9] LI H, ZHANG Q F, DENG J D, et al. Biased Multiobjective Optimization and Decomposition Algorithm. IEEE Transactions on Cybernetics, 2017, 47(1): 52-66. [10] ZHENG W, TAN Y Y, MENG L L, et al. An Improved MOEA/D Design for Many-Objective Optimization Problems. Applied Intelligence, 2018, 48(10): 3839-3861. [11] ZHOU Z B, LIU X H, XIAO H L, et al. A DEA-Based MOEA/D Algorithm for Portfolio Optimization. Cluster Computing, 2019, 22(6): 14477-14486. [12] YI J H, DEB S, DONG J Y, et al. An Improved NSGA-III Algorithm with Adaptive Mutation Operator for Big Data Optimization Problems. Future Generation Computer Systems, 2018, 88: 571-585. [13] YI J H, XING L N, WANG G G, et al. Behavior of Crossover Operators in NSGA-III for Large-Scale Optimization Problems. Information Sciences, 2020, 509: 470-487. [14] LOPEZ E M, COELLO C C A. IGD+-EMOA: A Multi-objective Evolutionary Algorithm Based on IGD+ // Proc of the IEEE Congress on Evolutionary Computation. Washington, USA: IEEE, 2016: 999-1006. [15] TIAN Y, CHENG R, ZHANG X Y, et al. An Indicator-Based Multiobjective Evolutionary Algorithm with Reference Point Adaptation for Better Versatility. IEEE Transactions on Evolutionary Computation, 2018, 22(4): 609-622. [16] SUN Y N, YEN G G, YI Z, et al. IGD Indicator-Based Evolutionary Algorithm for Many-Objective Optimization Problems. IEEE Transactions on Evolutionary Computation, 2019, 23(2): 173-187. [17] 黎 明,段茹茹,陈 昊,等.基于IGD+S指标的高维多目标进化算法.模式识别与人工智能, 2019, 32(9): 800-810. (LI M, DUAN R R, CHEN H, et al. Multi-objective Evolutionary Algorithm Based on IGD+S. Pattern Recognition and Artificial Intelligence, 2019, 32(9): 800-810.) [18] LI M Q, YANG S X, LIU X H. Pareto or Non-pareto: Bi-criterion Evolution in Multi-objective Optimization. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 645-665. [19] DEB K, JAIN H. An Evolutionary Many-Objective Optimization Al-gorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. [20] ZHANG Q F, ZHOU A M, ZHAO S Z, et al. Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition. Technical Report, CES-487. Colchester, UK: University of Essex, 2008. [21] HUBAND S, HINGSTON P, BARONE L, et al. A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506. [22] 耿焕同,陈 哲,陈正鹏,等.一种基于群体分布特征的自适应多目标粒子群优化算法.控制与决策, 2017, 32(8): 1386-1394. (GENG H T, CHEN Z, CHEN Z P, et al. A Self-adaptive Multi-objective Particle Swarm Optimization Algorithm Based on Swarm Distribution Characteristic. Control and Decision, 2017, 32(8):1386-1394.) [23] CHENG R, LI M Q, TIAN Y, et al. A Benchmark Test Suite for Evolutionary Many-Objective Optimization. Complex and Intelligent Systems, 2017, 3(1): 67-81. [24] SUN Y N, XUE B, ZHANG M J, et al. A New Two-Stage Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation, 2019, 23(5): 748-761. [25] HE Z N, YEN G G. Many-Objective Evolutionary Algorithm: Objective Space Reduction and Diversity Improvement. IEEE Transactions on Evolutionary Computation, 2016, 20(1): 145-160. [26] TIAN Y, CHENG R, ZHANG X Y, et al. PlatEMO: A MATLAB Platform for Evolutionary Multi-objective Optimization. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
2020, Vol. 33 
