Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 10, No. 1, 2024 54 A Survey on Multimodal Multiobjective Optimization Algorithm Jiaying Wang, Yinxing Chen and Weijie Wu College of Computer Science, Guangdong University of Science and Technology, Dongguan Guangdong 523083, China Abstract: With the diversification of industrial production and daily life needs, traditional single modal multi-objective optimization algorithms are no longer able to meet complex decision-making requirements. Multimodal multi-objective optimization algorithms (MMOPAs) provide decision- makers with more options by offering multiple feasible Pareto optimal solution sets. This article provides a detailed analysis of the research background and related concepts of multimodal multi- objective optimization algorithms. It analyzes the current development status of multimodal multi-objective optimization algorithms, introduces commonly used benchmark problems and evaluation indicators, and finally explaines future research directions. Keywords: Multimodal Multi-objective; Optimization Algorithms; Benchmark Problems. 1. Introduction Multi-objective optimization problems (MOPs) refer to a class of optimization problems that require the simultaneous consideration of multiple objective functions that typically conflict with each other [1,2]. When solving such problems, there is usually no solution that can optimize all objectives simultaneously. Decision makers need to weigh these objectives and find a satisfactory set of solutions called the Pareto optimal solution sets. As the complexity of the problem increases, a single Pareto optimal solution set may not be able to meet the diverse needs of decision-makers, thus leading to the emergence of multimodal multi-objective optimization problems (MMOPs). MMOPs have multiple Pareto optimal solution sets in the target space, which may be far apart in the decision space, providing decision-makers with more choices [3]. This type of problem occurs in many fields, such as path planning problem [4], feature selection problem [5], shop Scheduling [6], etc. The research on multimodal multi-objective optimization algorithms aims to find as many Pareto optimal solutions as possible to provide decision-makers with more choices. This type of algorithm needs to balance the diversity and convergence of solutions, while considering the characteristics of the decision space and the objective space. This article will provide a detailed introduction to the relevant concepts, research progress, testing functions, and evaluation indicators of multimodal multi-objective optimization algorithms. 2. Related Work The difficulty in solving multi-objective optimization problems is to find a compromise solution that maximizes all objectives under certain constraints. Taking minimizing the optimization objective as an example, a multi-objective optimization problem with dimensional decision variables and objective variables can be defined as: minimize F ,⋯ , T subject to ∈ Ω (1) where Ω ⊂ R represents decision space; , , . . . , is a decision vector; R representing the target space, F is the objective function that maps the m- dimensional decision space to the target space. For a multi-objective optimization problem (MOP), if there exists a Pareto optimal solution x and another solution y in the decision space, such that x and y differ very little in the objective function values (  ||)()(|| yfxf , where  is a very small non negative threshold given by the decision maker), the problem is called a multimodal multi-objective optimization problem [7]. The difficulty of solving multimodal multi-objective optimization problems lies in improving the global search capability of the algorithm, avoiding premature convergence to a local optimal solution set, while preserving the solution sets of different decision spaces corresponding to the same Pareto front, ensuring the diversity of solutions. In order to visually demonstrate the characteristics of multimodal multi-objective optimization problems, Figure 1 provides a schematic diagram of the multimodal multi- objective optimization problem. The points A1 and A2 in the decision space on the left side of the figure represent the optimal solutions in two solution sets, both of which map to point A' in the target space on the right side Although A1 and A2 are relatively far apart in the decision space, their distance in the target space is zero, allowing decision-makers to make different choices based on their own needs. 3. Research Progress The key challenge of multimodal multi-objective optimization problems is how to balance the distribution of solutions in the decision space and the objective space. Traditional multi-objective evolutionary algorithms typically adopt a strategy of "convergence before diversity", which may weaken the algorithm's exploration ability in the decision space and make it difficult to discover all Pareto optimal solution sets. To address this issue, researchers have proposed various multimodal multi-objective evolutionary algorithms (MMOEAs) that improve their coverage in the decision space through different diversity maintenance techniques. According to its algorithmic features, it can be roughly divided into three categories: pareto dominance based, objective decomposition based, and new evolutionary 55 paradigms based. Fig 1. Multimodal and multi-objective problem description 3.1. Pareto Dominance based MMOEAs This type of algorithm uses Pareto dominance to sort individuals in a population, removing dominant solutions, and then using environmental selection mechanisms to select non dominant solutions, in order to select a set of solutions with good convergence and diversity from the remaining solutions. Representative algorithms are described below. In [8], the Omni-optimizer proposed by Deb is a general optimizer based on NSGA-II, which uses Latin hypercube sampling to initialize the population and introduces a method of crowding distance combined with non-dominated sorting in the decision space to select better individuals as the next generation evolutionary population. DN-NSGAII [9] first uses fast non-dominated sorting to divide the solution into several layers, and then improves the two-choice competition method by adopting the decision space niche method. It increases the probability of solutions with longer decision space distances entering the mating pool to select better individuals, allowing the population to search for different Pareto optimal solutions in different habitats and improving the search ability of the algorithm. In [10], the main idea of the MO-Ring-PSO-SCD proposed by Liang Jing et al. is to adopt a ring topology structure based on index indexing, and consider crowding distance in both decision space and target space. Combining non dominated sorting, the algorithm selects the optimal solution to enter the next generation evolutionary population, in order to maintain the diversity of the distribution of the optimal solution set. At the same time, a multi-modal multi-objective optimization problem testing function and new evaluation indicators were proposed. LOMMODE_NCD [11], it is a multimodal multi-objective optimization algorithm based on the local optimal neighborhood crowding distance differential evolution algorithm. Firstly, utilizing the characteristics of heuristic random search, an adaptive partitioning strategy in the initialization stage is proposed to ensure the rapid finding of local optimal solutions in multiple PSs. Secondly, combining reverse learning with differential mutation to generate vectors accelerates the convergence speed of the population towards the optimal solution. Finally, a method was designed to calculate the crowding distance of neighborhoods on different Pareto ranks. MT-MMEA [12] adopts a non-dominated sorting strategy and introduces an  -based auxiliary task. Through knowledge transfer, solutions within a specific range are considered equivalent solutions, maximizing the diversity of the decision space with acceptable sacrifices in the target space and finding well distributed individuals. The Pareto dominated method is still widely used in solving MMOEAs, with its main advantages being strong applicability, simple operation, and convergence. 3.2. Objective Decomposition based MMOEAs The core idea of this type of algorithm is to generate a set of weight vectors, transform MMOP into multiple simple subproblems, and assign multiple individuals to solve each subproblem. Representative algorithm statements are as follows. Tanabe et al.proposed MOEA/D-AD [13], which assigns one or more individuals to the same sub-problem based on its position in the target space. The sub-problem is compared with its adjacent sub problems in the solution space, and environment selection is performed on individuals who are close to each other in the solution space. The population size can be dynamically adjusted during the search process. [14] is to assign k solutions to each weight vector in the MOEA/D variant, where k is determined by the dependency problem. The solution is evaluated by the minimum distance to other solutions with the same weight vector and the average distance to adjacent solutions in the grid with the same weight vector. A solution partitioning mechanism is introduced in the decision space for solving. [15] applies clustering methods to divide the population, explores different regions of the decision space through multiple subgroups, and guides the search behavior of subgroups with adaptively updated guidance vectors. The guidance vectors of each subgroup provide efficient convergence in the search space. [16] adopts partition search method to maintain diversity in the decision space. Randomly select some decision variables of MMOP, divide the entire search space into multiple subspaces, and search each subspace separately. In the decision space, population diversity can be maintained and the complexity of the problem can be reduced. MMOPSO-ZSMS [17] adopts a partitioning strategy to divide the entire search space into multiple subspaces, independently using a multi-modal multi-objective particle swarm algorithm based on multiple subpopulations to search for more potential equivalent Pareto solutions in each subspace. [18] transformed the original multimodal multi-objective optimization problem into a bi objective optimization problem, with one objective being to construct it using the decomposition or metric methods in MOEAs to ensure the convergence of the population; Another goal is the diversity 56 index, which is used to maintain the diversity of the population and adaptively select the best individuals during the evolution process. This type of algorithm generally maintains diversity by using uniformly distributed weight vectors, but the dependency problem determines the number of allocated individuals or the size of the neighborhood, resulting in slow computation and longer running time. 3.3. New Evolutionary Paradigms based MMOEAs This type of algorithm involves transplanting high- performance evolutionary algorithms and swarm intelligence algorithms into solving multimodal multi-objective optimization problems. Representative algorithms are described below. MMODE [19] adds individual pre selection mechanism and mutation boundary processing method on the basis of standard difference evolution algorithm to increase the diversity of solutions. Select superior individuals through crossover and selection mechanisms to participate in evolution until all optimal solutions are found. In [20], CNMM which uses particle swarm optimization algorithm to obtain the next generation evolutionary population, adopts improved differential evolution strategy to expand the search range, and uses nearest neighbor movement strategy to make particles approach the optimal solution and evolve locally, thus achieving the goal of optimization. In [21], TriMOEA-TA&R algorithm adopts an evolutionary algorithm based on two profiles and a recombination strategy. It uses clustering to maintain diversity profiles and employs niche techniques to maintain diversity in the solution set. The convergence profile and diversity profile are recombined to locate multiple optimal solutions. MMO-CLRPSO [22] adopts a new decision variable clustering method to form multiple subpopulations, uses particle swarm optimization algorithm to evolve the subpopulations separately, and uses a ring topology structure to enhance the information exchange ability between subpopulations, in order to find multiple Pareto optimal solutions. Yao et al. [23] proposed an effective multi-objective evolutionary algorithm based on special environment selection, which adopts a special environment selection strategy to select offspring and maintain diversity. In [24], a new multi-stage evolutionary algorithm with two improved optimization strategies has been proposed. Firstly, the decision space is explored to detect multiple PSs, and then the diversity of solutions is enhanced through the utilization of historical individuals and new differential evolution designs. An improved DE operator is designed to push individuals from crowded areas to sparse and undetected areas in the decision space. This type of algorithm can fully utilize the advantages of evolutionary algorithms and swarm intelligence algorithms to find more and better distributed optimal solution sets, achieving better results. 4. Benchmark Problems and Evaluation Metrics 4.1. Benchmark Problems In the process of researching algorithms, in order to evaluate the performance of multimodal multi-objective algorithms, researchers have designed some test questions covering different features to verify the performance of the algorithms. At present, scholars have conducted more research on the Pareto solution set of the target space, while there is less research on the Pareto solution set of the decision space. In order to test the importance of Pareto solution sets, researchers designed test functions with complex shaped Pareto solution sets that possess the characteristics of multiple local and global Pareto optimal solution sets. The most commonly used test set is currently the one from the 2019 CEC competition [25], which is scalable in both objective and decision variables. MMF1-13, MMF1_z, MMF1-e, SYM-PART_Simple, SYM-PART_rotated, and Omni_test are dual objective functions, while MMF14-15, MMF14_a, and MMF15_a are triple objective functions; The dimensions of MMF1-12, MMF1_z, MMF1-e, SYM-PART_Simple, and SYM- PART_rotated are 2 dimensions, while the dimensions of MMF13-15, MMF14_a, MMF15_a, and Omni_test are 3 dimensions. 4.2. Evaluation Metrics Evaluation indicators can quantify the performance of different algorithms and play a very important role in algorithm evaluation and comparison The commonly used evaluation metrics for multi-objective algorithms can only measure the distribution of the population in the target space, but cannot effectively measure the distribution of the population in the decision space. Therefore, new evaluation metrics are needed to evaluate different multimodal multi- objective algorithms. In order to better evaluate the performance of multimodal multi-objective optimization algorithms and reflect the distribution of Pareto optimal solution sets, this article introduces commonly used evaluation metrics for multimodal multi-objective algorithms, including Hypervolume Indicator (HV) [26], Inverse Generative Distance in the Decision Space (IGDx) [27], and Pareto Set Proximity (PSP). The HV index is used to measure the distance between the solution set found by the algorithm and the true Pareto front. The calculation formula is as follows: ⋃ ,∈ … , (2) The HV value is the volume of the bounded region dominated by the solution set. The larger the hypervolume and HV, the better the performance of this set of solutions. The average distance between the Pareto approximate solution set obtained by IGDx calculation and the real PS is calculated as follows: , ∗ | ∗| ∑ ,∈ ∗ (3) Where O is the approximate PS obtained by the algorithm, ∗ is the PS obtained by the algorithm in the decision space, and | ∗| is the number of intermediate elements. According to the definition, the smaller the value of IGDx, the better the solution obtained by the algorithm. PSP represents the degree of approximation between the Pareto optimal solution set obtained by the algorithm and the true Pareto optimal solution set in the decision space, and evaluates the convergence of the PS obtained by the algorithm. (4) represents the coverage between the PS obtained by the algorithm and the true PS of the multimodal multi-objective 57 testing function. The larger the value, the larger the PSP value, which can reflect the better performance of the algorithm. Although researchers have proposed some evaluation metrics for multimodal multi-objective optimization algorithms, most of them require the PS and PF of the known problem and select reference points or reference vectors based on them. However, in practical problems, PS and PF are unknown, so how to design reasonable performance indicators is a direction for future research. 5. Conclusion Multimodal multi-objective optimization algorithms are effective tools for solving complex decision-making problems in the real world, providing decision-makers with more solutions by maintaining diversity and convergence of solutions. Although some research progress has been made, most existing MMOEAs have achieved good distribution in the decision space, but have sacrificed some performance in the target space. How to maintain diversity in both the target space and decision space remains a research focus. In the future, we will continue to research multimodal and multi- objective optimization algorithms, apply them to more fields, and promote the development of related technologies. Acknowledgments This work was supported in part by the Guangdong University of Science and Technology campus level research project under Grant No. GKY-2023KYQNK-3. References [1] Jing Liang, Yuyang Zhang, Boyang Qu, et al. A Multiform Optimization Framework for Multiobjective Feature Selection in Classification. IEEE Transactions on Evolutionary Computation. 2024, Vol. 28(No. 4), p. 1024-1038. [2] Kangjia Qiao, Jing Liang, Kunjie Yu, et al. Benchmark problems for large-scale constrained multi-objective optimization with baseline results. Swarm and Evolutionary Computation. 2024, Vol.86, p.1-16. [3] Caitong Yue, Jing Liang, Boyang Qu, et al. A survey on multimodal multiobjective optimization. 2021, Vol. 36 (No. 11), p. 2577-2588. [4] Nouhaila Adil, Halima Lakhbab. A Discrete Bat Algorithm for the Multi-Compartment Vehicle Routing Problem. 2020 IEEE 6th International Conference on Optimization and Applications. Beni Mellal Morocco, 2020, p. 1-5. [5] Caitong Yue, Jing Liang, Boyang Qu, et al. Multimodal Multiobjective Optimization in Feature Selection. 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington New Zealand, 2019, p. 302-309. [6] Yuyan Han, Dunwei Gong, Yaochu Jin, et al. Evolutionary Multiobjective Blocking Lot- Streaming Flow Shop Scheduling With Machine Breakdowns. IEEE Transactions on Cybernetics. 2019, Vol. 49 (No. 1), p. 184-197. [7] Wenhua Li,Tao Zhang,Rui Wang, et al. Multimodal multi- objective optimization: Comparative study of the state-of-the- art. Swarm and Evolutionary Computation. 2023, Vol. 77, p. 1- 15. [8] Kalyanmoy Deb, Santosh Tiwari. Omni-optimizer: a procedure for single and multi-objective optimization. Evolutionary Multi-criterion Optimization. India, 2005, p. 47-61. [9] Jing Liang, Caitong Yue, Boyang Qu. Multimodal multi- objective optimization: A preliminary study. Evolutionary Computation. Vancouver Canada, 2016, p. 2454-2461. [10] Caitong Yue, Boyang Qu, Jing Liang, et al. A Multi-objective Particle Swarm Optimizer Using Ring Topology for Solving Multimodal Multi-objective Problems. IEEE Transactions on Evolutionary Computation. 2018, Vol. 22 (No. 5), p. 805-817. [11] Qinghua Gu, Yifan Peng, Qian Wang, et al. Multimodal multi- objective optimization based on local optimal neighborhood crowding distance differential evolution algorithm. Neural Comput & Applic. 2024, Vol. 36, p. 461-481. [12] Xinyi Wu, Fei Ming, Wenyin Gong. A Multi-task Framework for Solving Multimodal Multiobjective Optimization Problems. Neural Information Processing. Lecture Notes in Computer Science. 2024, Vol. 14449, p. 300-313. [13] Ryoji Tanabe, Hisao Ishibuchi. A Decomposition-Based Evolutionary Algorithm for Multi-modal Multi-objective Optimization. 15th International Conference. Cham, 2018, p. 249-261. [14] Chenxu Hu, Hisao Ishibuchi. Incorporation of a decision space diversity maintenance mechanism into MOEA/D for multi- modal multi-objective optimization. Genetic and Evolutionary Computation Conference Companion. 2018, p.1898-1901. [15] Ye Tian, Ruchen Liu, Xingyi Zhang, et al. A multipopulation evolutionary algorithm for solving large-scale multimodal multiobjective optimization problems. IEEE Transactions on Evolutionary Computation. 2021, Vol. 25 (No. 3), p. 405-418. [16] Qinqin Fan, Xuefeng Yan. Solving multimodal multiobjective problems through zoning search. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2021, Vol. 51 (No. 8), p. 4836–4847. [17] Hao Yuan, Wentao Huang, Qingchao Jiang, et al. A multimodal multi-objective particle swarm optimization algorithm based on zoning search and multi-subpopulation. Control Engineering of China. 1-12 .https://doi.org/10. 14107/j. cnki. kzgc.20230470. [18] Zhifang Wei, Weifeng Gao, Jingwei Xu, et al. BiOM: A framework for multimodal multiobjective optimization. Information Sciences, 2024, Vol. 653, p. 1-20. [19] Jing Liang, Weiwei Xu, Caitong Yue, et al. Multimodal multiobjective optimization with differential evolution. Swarm and Evolutionary Computation, 2019, Vol. 44, p.1028-1059. [20] Juan Zou, Deng Qi, Jinhua Zheng, et al. A close neighbor mobility method using particle swarm optimizer for solving multimodal optimization problems. Information Sciences, 2020, Vol. 519, p. 332-347. [21] Yiping Liu, Gary Yen, Dunwei Gong. A Multi-Modal Multi- Objective Evolutionary Algorithm Using Two-Archive and Recombination Strategies. IEEE Transactions on Evolutionary Computation. 2018, Vol. 23 (No. 04), p. 660-674. [22] Weizheng Zhang, Guoqing Li, Weiwei Zhang, et al. A cluster based PSO with leader updating mechanism and ring-topology for multimodal multi-objective optimization. Swarm Evolutionary Computation. 2019, Vol. 50, p.1-13. [23] Xingyi Yao, Wenhua Li, Xiaogang Pan. Multimodal multi- objective evolutionary algorithm for multiple path planning. 2022, Vol. 169, p. 1-10. [24] Tianyong Wu, Fei Ming, Hao Zhang, et al. Multimodal multi- objective optimization with multi-stage-based evolutionary algorithm. Memetic Comp. 2023, Vol. 15, p. 377-389. [25] Jing Liang, Boyang Qu. Problem definitions and evaluation criteria for the CEC 2019 special session on multimodal multiobjective optimization. 2019. 58 [26] Zitzler Eckart, Thiele Lothar. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation. 1999, Vol. 4 (No. 3), p. 257-271. [27] Zhou Aimin, Zhang Qingfu, Jin Yaochu. Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm. IEEE Transactions on Evolutionary Computation. 2009, Vol. 5 (No. 15), p. 1167-1189.