EVOLUTIONARY DYNAMIC MULTI­MODAL MULTI­OBJECTIVE OPTIMIZATION

Multi-modal multi-objective optimization problems (MMOPs) have become a popular research topic in recent years. This special class of multi-objective optimization problems is characterized by having multiple equivalent Pareto sets in the decision space, which poses new challenges for algorithm designers. When handling MMOPs, in addition to ensuring a good solution distribution over the Pareto front, an algorithm also needs to ensure the diversity in the decision space to cover as many Pareto sets as possible. Since multi-modal multi-objective optimization is a relatively new research area, only a few number of algorithms are available in the literature. This thesis aims to fill this gap by introducing several novel approaches for solving MMOPs efficiently.

First, in Chapter 3 and Chapter 4, we propose two novel decomposition-based multi-modal multi-objective evolutionary algorithms (MMEAs) based on the well-known MOEA/D algorithm. Experimental results indicate that our proposed algorithms show promising performance on various test problems. Second, in Chapter 5, we point out that the mechanisms in standard multi-objective evolutionary algorithm to estimate the population diversity are inefficient on MMOPs. We suggest the use of a niching mechanism to alleviate this issue. In the course of these research work mentioned earlier, we discover that there is a clear trade-off between the diversity of the population in the decision and the objective spaces. How to strike a balance between the diversity in these two spaces is important for solving MMOPs efficiently. Thus, in Chapter 6, we propose a diversity-enhanced subset selection framework for further enhancing the performance of state-of-the-art MMEAs. We then integrate this framework into multiple state-of-the-art MMEAs and investigate its effectiveness. Computational experiments indicate that the performance of these algorithms is clearly improved with the proposed framework.

Finally, in Chapter 7, we further consider the case where the environment of an MMOP changes continuously, which means that the Pareto set and/or Pareto front may change over time. Such kind of optimization problems is not uncommon in real-world applications. By introducing dynamic environments into MMOPs, we develop a novel and interesting research topic, namely, dynamic multi-modal multi-objective optimization. To facilitate the development of dynamic MMEAs, we provide a systematic approach for constructing dynamic MMOPs. We also suggest a test suite containing 12 novel dynamic MMOPs with various characteristics. We believe that our proposed test suite can help researchers develop efficient algorithms for solving dynamic MMOPs in the future.

近些年来，多模态多目标优化问题已经成为了一个热门的研究领域。这一类特殊的多目标优化问题的特点是在决策空间中有多个等价的帕累托最优解集，这给算法设计者带来了许多新的挑战。在使用进化算法来处理这类问题时，算法除了需要保证种群在帕累托前沿有良好的分布之外，还需要进一步保证种群在决策空间的多样性，以覆盖尽可能多的帕累托最优解集。由于目前多模态多目标优化仍是一个相对较新的研究领域，目前文献中只有少数的算法可以解决这类问题。本论文旨在通过提出几种有效的新方法来填补这一空白。

首先，在本文第三章和第四章中，我们在著名的 MOEA/D 算法的基础上提出了两种新型的基于分解的多模态多目标进化算法。实验结果表明，我们提出的算法在多个测试问题上表现出了良好的性能。其次，本文第五章指出，标准多目标进化算法中估计种群多样性的机制在多模态多目标优化问题上是低效的。我们建议使用引入小生境的机制来缓解这一问题。在前面提到的这些研究工作过程中，我们发现在解决多模态多目标优化问题时，种群在决策空间和目标空间的多样性存在明显的权衡关系。如何在这两个空间的多样性之间取得平衡对于有效解决多模态多目标优化问题是至关重要的。为了解决这个问题，本文第六章中提出了一个基于子集选择的框架来进一步提高已有的多模态多目标优化算法的性能。为了验证本文提出的框架是否有效，我们其整合到了多个前沿算法中。实验结果表明，这些算法的性能得到了明显的提高。

最后，本文第七章进一步考虑了多模态多目标优化过程中，环境发生动态变化的情况。这意味着其帕累托最优解集及其帕累托前沿可能会随着时间而发生变化。这种情形在现实世界的应用中并不少见。通过将动态变化的性质引入多模态多目标优化问题中，本文开创性的提出了一类全新的优化问题：动态多模态多目标优化问题。为了促进这一全新领域的算法研究，本文提供了一个构建动态多模态多目标基准测试问题的系统方法。本文还提供了一个易用的基准测试套件，其中包含了 12 个具有多种特性的新测试问题。我们相信，本文提供的测试套件可以为研究人员在未来开发解决动态多模态多目标优化问题的高效算法提供帮助。

[1] MIKKOLA J H. Portfolio Management of R&D Projects: Implications for Innovation Management[J]. Technovation, 2001, 21(7): 423­435.
[2] STEWART T J, JANSSEN R. A Multiobjective GIS­based Land Use Planning Algorithm[J].Comput. Environ. Urban Syst., 2014, 4: 25­34.
[3] DEB K, SUNDAR J. Reference Point Based Multi­objective Optimization Using Evolutionary Algorithms[C]//Proc. of the 8th annual conference on Genetic and evolutionary computation. 2006: 635­642.
[4] DEB K. Multi­objective Optimization Using Evolutionary Algorithms[M]. John Wiley & Sons, Inc., 2001.
[5] YAN X, CAI B, NING B, et al. Moving Horizon Optimization of Dynamic Trajectory Planning for High­speed Train Operation[J]. IEEE Trans. Intell. Transp. Syst., 2016, 17(5): 1258­1270.
[6] NGUYEN S, ZHANG M, JOHNSTON M, et al. Automatic Design of Scheduling Policies for Dynamic Multi­objective Job Shop Scheduling Via Cooperative Coevolution Genetic Programming[J]. IEEE Trans. Evol. Comput., 2014, 18(2): 193­208.
[7] LIANG J J, YUE C T, QU B Y. Multimodal Multi­objective Optimization: A Preliminary Study [C]//Proc. of 2016 IEEE Congress on Evolutionary Computation. 2016: 2454­2461.
[8] SCHÜTZE O, VASILE M, COELLO C A C. Computing the Set of Epsilon­efficient Solutions in Multiobjective Space Mission Design[J]. J. Aerosp. Comput. Inf. Commun., 2011, 8(3): 53­70.
[9] JASZKIEWICZ A. On the Performance of Multiple­objective Genetic Local Search on the 0/1 Knapsack Problem ­ a Comparative Experiment[J]. IEEE Trans. Evol. Comput., 2002, 6(4): 402­412.
[10] TIAN Y, LIU R, ZHANG X, et al. A Multi­population Evolutionary Algorithm for Solving Large­scale Multi­modal Multi­objective Optimization Problems[J]. IEEE Tran. Evol. Comput., 2020, 25(3): 405­418.
[11] EMMERICH M T, DEUTZ A H. A Tutorial on Multiobjective Optimization: Fundamentals and Evolutionary Methods[J]. Nat Comput., 2018(17): 585­609.
[12] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm:NSGA­II[J]. IEEE Trans. Evol. Comput., 2002, 6(2): 182­197.
[13] CORNE D W, JERRAM N R, KNOWLES J D, et al. PESA­II: Region­based Selection in Evolutionary Multiobjective Optimization[C]//Proc. of the 3rd Annual Conference on Genetic and Evolutionary Computation. 2001: 283­290.
[14] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm[J]. TIK­report, 2001, 103.
[15] ZITZLER E, SIMON K. Indicator­based Selection in Multiobjective Search[C]//Proc. of Parallel Problem Solving from Nature ­ PPSN VIII. 2004: 832­842.
[16] BEUME N, NAUJOKS B, EMMERICH M. SMS­EMOA: Multiobjective Selection Based on Dominated Hypervolume[J]. Eur .J. Oper. Res., 2007, 181(3): 1653­1669.
[17] ZITZLER E, THIELE L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[J]. IEEE Trans. Evol. Comput., 1999, 3(4): 257­271.
[18] ZHANG Q, LI H. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Trans. Evol. Comput., 2007, 11(6): 712­731.
[19] COELLO C A C, SIERRA M R. A Study of the Parallelization of a Coevolutionary Multiobjective Evolutionary Algorithm[C]//Proc. of MICAI 2004: Advances in Artificial Intelligence. 2004: 688­697.
[20] SHANG K, ISHIBUCHI H, NI X. R2­based Hypervolume Contribution Approximation[J].IEEE Trans. Evol. Comput., 2020, 24(1): 185­192.
[21] ISHIBUCHI H, IMADA R, SETOGUCHI Y, et al. How to Specify a Reference Point in Hypervolume Calculation for Fair Performance Comparison[J]. Evol. Comput., 2018, 26(3): 411­440.
[22] BADER J, ZITZLER E. HypE: An Algorithm for Fast Hypervolume­based Many­objective Optimization[J]. Evol. Comput., 2011, 19(1): 45­76.
[23] ISHIBUCHI H, MASUDA H, TANIGAKI Y, et al. Modified Distance Calculation in Generational Distance and Inverted Generational Distance[C]//Proc. of Evolutionary Multi­Criterion Optimization. 2015: 110­125.
[24] NGUYEN T T. Continuous Dynamic Optimization Using Evolutionary Algorithms[D]. The University of Birmingham, 2010.
[25] RAQUEL C, YAO X. Dynamic Multi­objective Optimization: A Survey of the State­of­the­art [M]//Evolutionary Computation for Dynamic Optimization Problems. Springer, 2013: 85­106.
[26] DEB K, N. U B R, KARTHIK S. Dynamic Multi­objective Optimization and Decision­making Using Modified NSGA­II: A Case Study on Hydro­thermal Power Scheduling[C]//Proc. of Evolutionary Multi­Criterion Optimization. 2007: 803­817.
[27] MORRISON R W. Designing Evolutionary Algorithms for Dynamic Environments[M].Springer, 2004.
[28] JIANG S, YANG S. A Steady­state and Generational Evolutionary Algorithm for Dynamic Multiobjective Optimization[J]. IEEE Trans. Evol. Comput., 2016, 21(1): 65­82.
[29] GOH C, TAN K C. A Competitive­cooperative Coevolutionary Paradigm for Dynamic Multiobjective Optimization[J]. IEEE Trans. Evol. Comput., 2008, 13(1): 103­127.
[30] AZZOUZ R, BECHIKH S, SAID L B. A Dynamic Multi­objective Evolutionary Algorithm Using a Change Severity­based Adaptive Population Management Strategy[J]. Soft Comput., 2017, 21: 885­906.
[31] HATZAKIS I, WALLACE D. Dynamic Multi­objective Optimization with Evolutionary Algorithms: A Forward­looking Approach[C]//Proc. of the 8th Annual Conference on Genetic and Evolutionary Computation. 2006: 1201­1208.
[32] LI Q, ZOU J, YANG S, et al. A Predictive Strategy Based on Special Points for Evolutionary Dynamic Multi­objective Optimization[J]. Soft Comput., 2019, 23: 3723­3739.
[33] RUAN G, YU G, ZHENG J, et al. The Effect of Diversity Maintenance on Prediction in Dynamic Multi­objective Optimization[J]. Appl. Soft Comput., 2017, 58: 631­647.
[34] BRANKE J, KAUSSLER T, SMIDT C, et al. A Multi­population Approach to Dynamic Optimization Problems[C]//Proc. of Evolutionary Design and Manufacture. 2000: 299­307.
[35] SHIR O M. Niching in Evolutionary Algorithms[M]//Handbook of Natural Computing.Springer, 2012: 1035­1069.
[36] LIU Y, ISHIBUCHI H, NOJIMA Y, et al. A Double­niched Evolutionary Algorithm and Its Behavior on Polygon­based Problems[C]//Proc. of Parallel Problem Solving from Nature ­ PPSNXV. 2018: 262­273.
[37] GOLDBERG D E, RICHARDSON J. Genetic Algorithms with Sharing for Multimodal Function Optimization[C]//Proc. of the Second International Conference on Genetic Algorithms and Their Application. 1987: 41­49.
[38] LIN Q, LIN W, ZHU Z, et al. Multimodal Multi­objective Evolutionary Optimization with Dual Clustering in Decision and Objective Spaces[J]. IEEE Trans. Evol. Comput., 2021, 25(1): 130­144.
[39] DEB K, TIWARI S. Omni­optimizer: A Generic Evolutionary Algorithm for Single and Multiobjective Optimization[J]. Eur. J. Oper. Res., 2008, 185(3): 1062­1087.
[40] YUE C, QU B, LIANG J. A Multiobjective Particle Swarm Optimizer Using Ring Topology for Solving Multimodal Multiobjective Problems[J]. IEEE Trans. Evol. Comput., 2018, 22(5): 805­817.
[41] TANABE R, ISHIBUCHI H. A Review of Evolutionary Multimodal Multiobjective Optimization[J]. IEEE Trans. Evol. Comput., 2020, 24(1): 193­200.
[42] ZHOU A, ZHANG Q, JIN Y. Approximating the Set of Pareto­optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm[J]. IEEE Trans. Evol. Comput., 2009, 13(5): 1167­1189.
[43] PENG Y, ISHIBUCHI H, SHANG K. Multi­modal Multi­objective Optimization: Problem Analysis and Case Studies[C]//Proc. of IEEE Symposium Series on Computational Intelligence. 2019: 1865­1872.
[44] TANABE R, ISHIBUCHI H. A Decomposition­based Evolutionary Algorithm for Multi­modal Multi­objective Optimization[C]//Proc. of Parallel Problem Solving from Nature ­ PPSN XV. 2018: 249­261.
[45] HU C, ISHIBUCHI H. Incorporation of a Decision Space Diversity Maintenance Mechanism into MOEA/D for Multi­modal Multi­objective Optimization[C]//Proc. of Genetic and Evolutionary Computation Conference Companion. 2018: 1898­1901.
[46] PETROWSKI A. A Clearing Procedure As a Niching Method for Genetic Algorithms[C]//Proc.of IEEE International Conference on Evolutionary Computation. 1996: 798­803.
[47] ISHIBUCHI H, PENG Y. A Scalable Multimodal Multiobjective Test Problem[C]//Proc. of 2019 IEEE Congress on Evolutionary Computation. 2019: 302­309.
[48] RUDOLPH G, NAUJOKS B, PREUSS M. Capabilities of EMOA to Detect and Preserve Equivalent Pareto Subsets[C]//Proc. of 2007 International Conference on Evolutionary MultiCriterion Optimization. 2007: 36­50.
[49] TIAN Y, CHENG R, ZHANG X, et al. PlatEMO: A MATLAB Platform for Evolutionary Multiobjective Optimization[J]. IEEE Comput. Intell. Mag., 2017, 12(4): 73­87.
[50] MAHFOUND S W. Crowding and Preselection Revisited[C]//Proc. of Parallel Problem Solving from Nature ­ PPSN II. 1992: 27­36.
[51] LI H, ZHANG Q. Multiobjective Optimization Problems with Complicated Pareto Sets, MOEA/D and NSGA­II[J]. IEEE Trans. Evol. Comput., 2009, 13(2): 284­302.
[52] STORN R, PRICE K. Differential Evolution – a Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J]. J. Global Optim., 1997, 11: 341­359.
[53] EPITROPAKIS M G, PLAGIANAKOS V P, VRAHATIS M N. Finding Multiple Global Optima Exploiting Differential Evolution’s Niching Capability[C]//Proc. of 2011 IEEE Symposium on Differential Evolution. 2011: 1­8.
[54] URSEM R K. Multinational Evolutionary Algorithms[C]//Proc. of the 1999 IEEE Congress on Evolutionary Computation. 1999: 1633­1640.
[55] SINGH H K, BHATTACHARJEE K S, RAY T. Distance­based Subset Selection for Benchmarking in Evolutionary Multi/many­objective Optimization[J]. IEEE Trans. Evol. Comput., 2019, 23(5): 904­912.
[56] TANABE R, ISHIBUCHI H, OYAMA A. Benchmarking Multi­ and Many­objective Evolutionary Algorithms under Two Optimization Scenarios[J]. IEEE Access, 2017, 5: 19597­19619.
[57] YUE C, QU B, YU K, et al. A Novel Scalable Test Problem Suite for Multimodal Multiobjective Optimization[J]. Swarm Evol. Comput., 2019, 48: 62­71.
[58] LI M, YANG S, LIU X. Shift­based Density Estimation for Pareto­based Algorithms in Manyobjective Optimization[J]. IEEE Trans. Evol. Comput., 2014, 18(3): 348­365.
[59] SILVERMAN B W. Density Estimation for Statistics and Data Analysis[M]. CRC press, 1986.
[60] GRIMME C, KERSCHKE P, TRAUTMANN H. Multimodality in Multi­objective Optimization – More Boon Than Bane?[C]//Proc. Evol. Multi Crit. Optim. 2019: 126­138.
[61] KERSCHKE P, WANG H, PREUSS M, et al. Search Dynamics on Multimodal Multi­objective Problems[J]. Evol. Comput., 2019, 27(4): 577­609.
[62] BRINGMANN K, FRIEDRICH T, KLITZKE P. Generic Postprocessing Via Subset Selection for Hypervolume and Epsilon­indicator[C]//Proc. Int. Conf. Parallel Probl. Solving. Nat. 2014: 518­527.
[63] BRINGMANN K, FRIEDRICH T. Approximating the Volume of Unions and Intersections of High­dimensional Geometric Objects[J]. Comput. Geom., 2010, 43(6–7): 601­610.
[64] CHEN W, ISHIBUCHI H, SHANG K. Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets[C]//Proc. Int. Conf. Congr. Evol. Comput. 2020: 1­8.
[65] BRINGMANN K, FRIEDRICH T. An Efficient Algorithm for Computing Hypervolume Contributions[J]. Evol. Comput., 2010, 3(3): 383­402.
[66] DEB K, JAIN H. An Evolutionary Many­objective Optimization Algorithm Using Referencepoint­based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints [J]. IEEE Trans. Evol. Comput., 2014, 18(4): 577­601.
[67] DAS I. On Characterizing the “knee” of the Pareto Curve Based on Normal­boundary Intersection[J]. Struct. Optim., 1999, 18(2): 107­115.
[68] CHENG R, JIN Y, OLHOFER M, et al. A Reference Vector Guided Evolutionary Algorithm for Many­objective Optimization[J]. IEEE Trans. Evol. Comput., 2016, 20(5): 773­791.
[69] DAS I, DENNIS J E. Normal­boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems[J]. SIAM J. Optim., 1998, 8(3): 631­657.
[70] BLANK J, DEB K, DHEBAR Y, et al. Generating Well­spaced Points on a Unit Simplex for Evolutionary Many­objective Optimization[J]. IEEE Trans. Evol. Comput., 2020.
[71] CHEN W, ISHIBUCHI H, SHANG K. Modified Distance­based Subset Selection for Evolutionary Multi­objective Optimization Algorithms[C]//Proc. Int. Conf. Congr. Evol. Comput. 2020: 1­8.
[72] SHIR O M, PREUSS M, NAUJOKS B, et al. Enhancing Decision Space Diversity in Evolutionary Multiobjective Algorithms[C]//Proc. Evol. Multi Crit. Optim. 2009: 95­109.
[73] HANSEN N, OSTERMEIER A. Completely Derandomized Self­adaptation in Evolution Strategies[J]. Evol. Comput., 2001, 9(2): 159­195.
[74] ULRICH T, BADER J, THIELE L. Defining and Optimizing Indicator­based Diversity Measures in Multiobjective Search[C]//Proc. of Parallel Problem Solving from Nature – PPSN XI. 2010: 707­717.
[75] SOLOW A R, POLASKY S. Measuring Biological Diversity[J]. Environ. Ecol. Stat., 1994, 1:95­103.
[76] CHAN K P, RAY T. An Evolutionary Algorithm to Maintain Diversity in the Parametric and the Objective Space[C]//Proc. Int. Conf. Comput. Robot. Auton. Syst. 2005: 1­6.
[77] ESTER M, KRIEGEL H P, SANDER J, et al. A Density­based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//Proc. Data Min. Knowl. Discov. 1996: 226­231.
[78] ZHANG K, CHEN M, XU X, et al. Multi­objective Evolution Strategy for Multi­modal Multiobjective Optimization[J]. Appl. Soft Comput., 2021, 101: 107004.
[79] ISHIBUCHI H, IMADA R, MASUYAMA N, et al. Comparison of Hypervolume, IGD and + IGD from the Viewpoint of Optimal Distributions of Solutions[C]//Proc. Evol. Multi Crit. Optim. 2009: 332­345.
[80] TANABE R, ISHIBUCHI H. An Analysis of Quality Indicators Using Approximated Optimal Distributions in a 3­D Objective Space[J]. IEEE Trans. Evol. Comput., 2020, 24(5): 853­867.
[81] ISHIBUCHI H, PANG L M, SHANG K. Solution Subset Selection for Final Decision Making in Evolutionary Multi­objective Optimization[J]. arXiv:2006.08156, 2020.
[82] FRIEDRICH T, NEUMANN F. Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms[J]. Evol. Comput., 2015, 23(4): 543­558.
[83] QIAN C, YU Y, ZHOU Z H. Subset Selection by Pareto Optimization[C]//Proc. Adv. Neural Inf. Process. Syst. 2015: 1765­1773.
[84] QIAN C, SHI J C, YU Y. Parallel Pareto Optimization for Subset Selection[C]//Proc. Int. Jt.Conf. Artif. Intell. 2016: 1939­1945.
[85] QIAN C. Distributed Pareto Optimization for Large­scale Noisy Subset Selection[J]. IEEE Trans. Evol. Comput., 2020, 24(4): 694­707.
[86] FARINA M, DEB K, AMATO P. Dynamic Multiobjective Optimization Problems: Test Cases, Approximations, and Applications[J]. IEEE Trans. Evol. Comput., 2004, 5(8): 425­442.
[87] JIANG S, YANG S. Evolutionary Dynamic Multiobjective Optimization: Benchmarks and Algorithm Comparisons[J]. IEEE Trans. Cybern., 2017, 47(1).
[88] S.JIANG, S.YANG, X.YAO, et al. Benchmark Problems for CEC’2018 Competition on Dynamic Multiobjective Optimisation[C]//Technical Report. 2018: 249­261.
[89] ISHIBUCHI H, MATSUMOTO T, MASUYAMA N, et al. Many­objective Problems Are Not Always Difficult for Pareto Dominance­based Evolutionary Algorithms[C]//Proc. 24th European Conference on Artificial Intelligence. 2020.
[90] HUBAND S, BARONE L, WHILE L, et al. A Scalable Multi­objective Test Problem Toolkit [C]//Proc. of Evolutionary Multi­Criterion Optimization. 2005.