Decomposition Multi-objective Evolutionary Algorithm Based on Differentiated Neighborhood Strategy
WANG Liping1,2, WU Feng1,2, ZHANG Mengzi1,2, QIU Feiyue3
1.College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023 2.Institute of Information Intelligence and Decision Optimization, Zhejiang University of Technology, Hangzhou 310014 3.College of Educational Science and Technology, Zhejiang University of Technology, Hangzhou 310023
Abstract：The performance of the decomposition-based multi-objective evolutionary algorithm is easily affected by the neighborhood of a subproblem. When the neighborhood is too large, the new solutions generated by the population propagation deviate from the Pareto set and the frequency of comparison between new solutions and old solutions in the neighborhood is increased for the updating subproblems. Consequently, the computational complexity of the algorithm is increased. If the neighborhood is too small, the algorithm easily falls into the local optimum. To solve this problem, a decomposed multi-objective evolutionary algorithm based on differentiated neighborhood strategy(MOEA/D-DN) is proposed. The suitable parameters are selected by analyzing the influence of different neighborhood sizes on the algorithm performance and different sizes of neighborhood for each subproblem are set according to the angle between their weight vectors and the central vector. Thus, the resource of algorithm is allocated more rationally and the velocity of searching for the optimal solution is also improved. Finally, the experimental results on the test functions of 2 dimensional ZDT and 3-5 dimensional DTLZ show that the convergence rate and the performance of MOEA/D-DN algorithm are improved obviously and the computational resource allocation of the algorithm is more reasonable. The overall solution quality is better.
[1] COELLO COELLO C. Evolutionary Multi-objective Optimization: A Historical View of the Field. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36. [2] WANG R, FLEMING P J, PURSHOUSE R C. General Framework for Localised Multi-objective Evolutionary Algorithms. Information Sciences, 2014, 258: 29-53. [3] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm[J/OL]. [2017-07-20]. http://kdd.cs.ksu.edu/Courses/Spring-2007/CIS830/Handouts/P8.pdf. [4] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. [5] DEB K, SUNDAR J. Reference Point Based Multi-objective Optimization Using Evolutionary Algorithms // Proc of the 8th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 2006: 635-642. [6] BEUMEA N, EMMERRICH M. SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume. European Journal of Operational Research, 2007, 181(3): 1653-1669. [7] BADER J, ZITZLER E. HypE: An Algorithm for Fast Hypervo-lume-Based Many-Objective Optimization. Evolutionary Computation, 2011, 19(1): 45-76. [8] ZITZLER E, KNZLI S. Indicator-Based Selection in Multiobjective Search // YAO X, BURKE E K, LOZANO J A, et al., eds. Pa- rallel Problem Solving from Nature-PPSN VIII. Berlin, Germany: Springer, 2004: 832-842. [9] ZHANG Q F, LI H. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731. [10] LI H, ZHANG Q F. Multiobjective Optimization Problems with Complicated Pareto Sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302. [11] QI Y T, MA X L, LIU F, et al. MOEA/D with Adaptive Weight Adjustment. Evolutionary Computation, 2014, 22(2): 231-264. [12] WANG Z K, ZHANG Q F, GONG M G, et al. A Replacement Strategy for Balancing Convergence and Diversity in MOEA/D // Proc of the IEEE Congress on Evolutionary Computation. Washington, USA: IEEE, 2014: 2132-2139. [13] YUAN Y, XU H, WANG B, et al. Balancing Convergence and Diversity in Decomposition-Based Many-Objective Optimizers. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 180-198. [14] ZHANG Q F, LIU W D, LI H. The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances // Proc of the IEEE Congress on Evolutionary Computation. Washington, USA: IEEE, 2009: 203-208. [15] ZHAO S Z, SUGANTHAN P N, ZHANG Q F. Decomposition-Based Multiobjective Evolutionary Algorithm with an Ensemble of Neighborhood Sizes. IEEE Transactions on Evolutionary Computation, 2012, 16(3): 442-446. [16] ZITZLER E, DEB K, THIELE L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 2000, 8(2): 173-195. [17] DEB K, THIELE L, LAUMANNS M, et al. Scalable Test Problems for Evolutionary Multiobjective Optimization // ABRAHAM A, JAIN L, GOLDBERG R, eds. Evolutionary Multiobjective Optimization. Berlin, Germany: Springer, 2006: 105-145. [18] VAN VELDUIZEN D A, LAMONT G B. On Measuring Multiobjective Evolutionary Algorithm Performance // Proc of the Congress on Evolutionary Computation. Washington, USA: IEEE, 2002: 204-211. [19] SCHOTT J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master Dissertation. Boston, USA: Massachusetts Institute of Technology, 1995. [20] YU G Y, LI P, HE Z, et al. Advanced Evolutionary Algorithm Used in Multi-objective Constrained Optimization Problem. Computer Integrated Manufacturing Systems, 2009, 15(6): 1172-1178. [21] TAN Y Y, JIAO Y C, LI H, et al. MOEA/D+Uniform Design: A New Version of MOEA/D for Optimization Problems with Many Objectives. Computers & Operations Research, 2013, 40(6): 1648-1660.
2017, Vol. 30 
