Analysis of a Multimodal Multiobjective Evolutionary Algorithm
A multimodal multiobjective evolutionary algorithm based on neighborhood
and enhanced special crowding distance
1
Research Background
The multimodal multiobjective problem (MMOPs) is a special form of multiobjective optimization problem (MOPs), characterized by multiple Pareto optimal solutions (PSs) corresponding to the same objective function value. These multiple sets of equivalent optimal solutions provide decision-makers with a broader choice space (e.g., resource allocation schemes in different scenarios), ultimately achieving resource savings, which is of significant value in practical decision-making. However, such problems require simultaneous attention to the diversity of solutions in the decision space (finding multiple sets of equivalent PSs) and the convergence of the objective space (approaching the true Pareto front PF), making them more complex than ordinary MOPs. Existing multiobjective evolutionary algorithms (such as NSGA-II, MOEA/D) can effectively solve ordinary MOPs but cannot be directly applied to MMOPs.
Existing multimodal multiobjective evolutionary algorithms (MMOEAs) still face two core challenges when addressing MMOPs. The first is the difficulty in balancing convergence and diversity; most algorithms struggle to find solutions that are both convergent (approaching true PS/PF) and evenly distributed in the decision space. The second challenge is the bias in crowding distance calculation and local crowding issues; traditional crowding distance (CD) is suitable for scenarios with regular PF distributions, but the multiple sets of equivalent PSs in MMOPs lead to complex individual distributions, reducing the accuracy of CD calculations and easily misremoving individuals with good diversity. Additionally, local areas of the decision space often experience individual crowding, leading to imbalanced resource allocation under a fixed population size, further affecting algorithm performance.
These issues have prompted the proposal of a new algorithm, MMO_NESCD, which integrates “Enhanced Special Crowding Distance (ESCD)” and “Adaptive Neighborhood Strategy (ANS)” to break through existing technical bottlenecks.
2
Current Research Status
Currently, researchers have proposed several evolutionary algorithms specifically designed to solve multimodal multiobjective problems (MMOEAs), which can be categorized into three main types.
The first type consists of algorithms that select solutions based on “Pareto dominance,” such as the Omni-optimizer and DN-NSGAII, which are improvements based on NSGA-II, as well as MO_Ring_PSO_SCD, which does not require tuning of habitat parameters. Most of these algorithms focus on enhancing the diversity of the decision space by optimizing the “crowding distance” or adding “small habitat techniques,” but some require manual parameter tuning, and others do not handle complex distributions well.
The second type includes algorithms that decompose the problem into smaller subproblems, such as MOEA/D-AD, which assigns multiple individuals to each subproblem, allowing for solutions that are close in the objective space but distant in the decision space. There are also algorithms that use dynamic small habitat distances to avoid solution overlap, but the collaboration efficiency of the decomposed subproblems still has room for improvement.
The third type consists of algorithms guided by “performance metrics,” such as those using hypervolume metrics or those that combine decision space and objective space metrics with weighted combinations, which can balance convergence and diversity. However, some of these metrics require manual weighting, making them less flexible.
Overall, these algorithms each have their methods, but they generally have shortcomings. Some require manual parameter tuning, some have weak capabilities in handling local crowding in the decision space and complex solution distributions, and they are prone to misremoving key solutions that are clustered but far from other groups.
3
Research Methodology
This paper proposes the MMO_NESCD algorithm to solve multimodal multiobjective optimization problems. This algorithm incorporates a clustering-based enhanced special crowding distance mechanism in the environmental selection phase and introduces an adaptive neighborhood strategy in the archive update mechanism.
Specifically, MMO_NESCD uses DBSCAN clustering to divide the population into multiple small habitats to enhance diversity; then, within each small habitat, a non-dominated sorting based on enhanced special crowding distance (ESCD) is applied to improve the diversity and convergence of the population in both the decision space and objective space; simultaneously, an adaptive neighborhood strategy is employed in the environmental selection phase to further optimize individual distribution, ultimately yielding a high-quality Pareto set.
3.1 Main Process of MMO_NESCD
The core process of the proposed multimodal multiobjective evolutionary algorithm MMO_NESCD is shown in Algorithm 1, which is used to solve multimodal multiobjective optimization problems (MMOPs).
The environmental selection aims to filter the core process of the next generation population by combining DBSCAN clustering and non-dominated sorting to select individuals that balance convergence and diversity from the merged set of parents and offspring, as shown in Algorithm 2.
The flowchart of environmental selection and Pareto archive updating in the MMO_NESCD algorithm is shown in Fig. 3, illustrating the iterative process from the candidate set S to the next generation population P, and then to the optimal archive OA, which can be broken down into three stages: “clustering → selection → updating”.
3.2 Enhanced Special Crowding Distance
The calculation of crowding distance is done by projecting the current population onto each dimension, determining the neighboring individuals for each individual in each dimension, and then calculating the distances between these neighbors. Finally, the distances across all dimensions are summed to obtain the crowding distance.
Traditional crowding distance only considers local distances in the objective space, which can misinterpret the “true diversity of the decision space” as “crowding” in multimodal (cross-cluster) and vertical/gradient distribution scenarios within a single modality.
Enhanced special crowding distance integrates the “global total distance” and “local nearest neighbor distance” through MEDx, allowing it to identify the dispersion across modalities (as shown in Fig. 4a and 4b) while retaining diversity within a single modality (as shown in Fig. 4c and 4d), ultimately enabling the algorithm to select high-quality solutions that are “completely covering multimodal and evenly distributed within a single modality”.
3.3 Adaptive Neighborhood Strategy
An optimal Pareto archive (OA) is established to store the PSs found in each iteration, which will be continuously updated. An uneven population means that individuals are crowded in certain areas while others are not. The size of the optimal archive is fixed, meaning that if we manage individuals in crowded areas, we can free up more space for individuals in other areas. This approach is also used to enhance diversity.
In Fig. 5, individuals E and F are very close to each other but far from other individuals. This situation may lead to a very small NearDistX between individuals E and F, resulting in a small MEDx. Individuals E and F play a crucial role in supplementing sparse areas; however, they may be removed during the environmental selection process. This removal could create gaps within sub-regions, negatively impacting the diversity of the population in the decision space.
Therefore, an Adaptive Neighborhood Strategy (ANS) is designed to address the issue of excessive density in specific sub-regions and assist MEDx in executing more effectively. ANS determines the neighborhood of each individual through neighborhood radius (NR), thus managing individuals within each individual’s neighborhood. NR should not remain static but should be adaptively adjusted based on population changes. If two individuals are closest to each other and far from the rest of the population, we define this distance as the mutual nearest distance (MND). However, being closest to each other does not necessarily indicate that these two individuals are crowded together. Therefore, we calculate the average of the minimum distances from all individuals in the population to other individuals as a threshold to exclude individuals with relatively large MNDs. Finally, we compute the average of all qualifying MNDs.
The core process of cleaning redundant individuals in the decision space and protecting multimodal diversity in MMO_NESCD is shown in Algorithm 3, which accurately handles local crowded areas through dynamic neighborhood radius + differential deletion rules.
In the early stages of evolution, the OA contains both non-dominated and dominated individuals. ANS prioritizes population diversity, facilitating the exploration of more potential optimal individuals while expanding the search range. In the later stages of evolution, the OA may mainly consist of non-dominated individuals. Under the premise of good convergence in the population, ANS helps achieve a more uniform distribution of individuals, enhancing diversity. Fig. 6(a) shows an MMOP. After applying the neighborhood strategy, as shown in Fig. 6(b), individuals 2, 5, 9, and 11 in the decision space are removed. This removal not only avoids the aforementioned MEDX drawbacks but also improves the issue of population distribution crowding, preserving individuals with good diversity in sub-regions. Furthermore, when applying the ESCD strategy, it allows the algorithm to select truly crowded individuals during environmental selection, enhancing diversity in both the decision space and objective space. ANS addresses crowded areas and avoids situations where a few individuals are close to each other but far from others, which could lead to their exclusion during environmental selection. This approach enhances population diversity and promotes a more even distribution of individuals.
4
Experiments in This Study
This study conducted four experiments to verify the effectiveness of the proposed method, including comparative experiments between MMO_NESCD and competitive MMOEAs, validation experiments for the core strategies of the algorithm, and parameter sensitivity analysis experiments applied to location optimization problems.
4.1 Comparative Experiments Between MMO_NESCD and Competitive MMOEAs
Table 1 summarizes the comparison results between MMO_NESCD and competitive algorithms.
Fig. 7 also provides the comparison results in a more understandable geographic histogram format. These values represent the average and standard deviation of each algorithm’s performance over 31 independent runs on each problem.
Tables 1 and 2 provide IGDX and rPSP results with Wilcoxon rank-sum tests. MMO_NESCD outperforms DN-NSGAII and MO_Ring_PSO_SCD on 22 problems. Compared to MMODE_ICD, HREA, and MMOCDE, MMO_NESCD is superior on 15, 13, and 18 test problems, respectively. This finding indicates that MMO_NESCD can find diverse and convergent PSs when dealing with MMOPs.
Additionally, MMO_NESCD achieves the best IGDX and rPSP values in 8 out of 22 test problems. The PSs generated by these problems are either convergent or distributed across the decision space, demonstrating the effectiveness of the proposed algorithm. HREA achieves global optimality on 6 problems, MMODE_ICD on 7 problems, and MMOCDE on 1 problem. Therefore, MMO_NESCD improves the method of diversity discrimination for individuals, ensuring the retention of truly excellent individuals while optimizing performance in crowded areas and handling nearly duplicate individuals. This result not only provides potential for superior population evolution but also saves computational resources, allowing for more space for individuals in sparse areas. In contrast, comparative algorithms still face issues of insufficient diversity discrimination when retaining individuals, leading to a less dispersed distribution of retained individuals. Tables 3 and 4 report the comparison of IGD and rHV values of MMO_NESCD with five other algorithms.
In Table 3, MMO_NESCD outperforms DN-NSGAII, MO_Ring_PSO_SCD, MMODE_ICD, HREA, and MMOCDE on 22, 22, 11, 22, and 12 test problems, respectively. Furthermore, MMO_NESCD achieves the best IGD value in 10 out of 22 test problems, while MMODE_ICD and MMOCDE achieve the best IGD value in 5 and 7 problems, respectively.
For the rHV values presented in Table 4, MMO_NESCD outperforms comparative algorithms on 17, 19, 7, 21, and 13 problems, and achieves the best rHV value in 7 problems. Additionally, MMODE_ICD and MMOCDE produce the best rHV for 8 and 6 problems, respectively. The performance of MMO_NESCD in terms of IGD and rHV values emphasizes its good diversity and convergence in the objective space. However, MMO_NESCD does not achieve significantly better performance than MMODE_ICD, primarily because MMODE_ICD considers all surrounding individuals rather than just those from the same Pareto front, leading to more accurate CD assessments. HREA performs poorly on IGD, possibly because the algorithm needs to explore the entire decision domain while attempting to find local PSs, ultimately obtaining some individuals from the local PF. The proposed algorithm enhances its advantages in the objective domain by balancing population diversity in both spaces. A well-distributed set of solutions can guide them to cover the objective space more evenly, thereby improving the diversity and quality of solutions.
In the test problem MMF3, the PSs and PFs obtained by the proposed algorithm and its competitive algorithms are compared. The distribution is shown in Fig. 8, where each algorithm’s population runs independently 31 times, selecting the population corresponding to the median in IGDx. This method intuitively represents the differences in algorithm performance. For the first two algorithms, it is challenging to find a complete PS, leading to dense areas of individual distribution. MMODE_ICD and HREA found well-distributed PFs, but the PSs need to maintain better diversity. MMOCDE performed the best among all comparative algorithms, finding a complete PS and uniformly distributed PF. However, due to the advantages of ESCD and ANS, the proposed algorithm can achieve a more complete population.
Furthermore, Fig. 9 displays the Friedman average rank test results for IGDX and IGD (two performance metrics) for MMO_NESCD and each comparative algorithm. Here, A represents the algorithm DN-NSGAII, B represents the algorithm MO_Ring_PSO_SCD, C represents the algorithm MMODE_ICD, D represents the algorithm HREA, and E and F represent the algorithms MMOCDE and the proposed MMO_NESCD, respectively. This figure clearly indicates that MMO_NESCD consistently has a significant advantage in the “ranking of IGDX and IGD metrics.”
4.2 Validation Experiments for Core Strategy Effectiveness
To validate the effectiveness of the Enhanced Special Crowding Distance (ESCD) and Adaptive Neighborhood Strategy (ANS), experimental analyses were conducted to explore the impact of these two strategies. As shown in Table 4, we first performed a rank-sum test on the rPSP (normalized Pareto set similarity) metric to visually reflect the advantages of the proposed algorithm; this table also displays the performance metrics of MMO_NESCD and its three variant algorithms.
Compared to the multimodal multiobjective evolutionary algorithm (MMOEA) that only uses special crowding distance (SCD), MMO_NESCD shows significant advantages in 17 out of 22 test problems, with only 2 problems showing significant disadvantages. Compared to the MMOEA that only uses ESCD, MMO_NESCD significantly improves performance on 11 problems, and its performance on all test problems is not worse than MODE_ESCD; this indicates that adding ANS brings absolute performance improvements to the algorithm. Additionally, compared to the variant algorithm that only uses ANS, MMO_NESCD achieves optimal results on 13 test problems, with only 3 problems performing poorly, indicating that the Enhanced Special Crowding Distance (ESCD) is more advantageous.
Furthermore, to analyze the performance of this strategy in more detail, we plotted the curves of the normalized Pareto set similarity (rPSP) metrics for three multimodal multiobjective evolutionary algorithms (MMOEAs) as a function of iteration count. In Fig. 10, the red line represents the proposed MMO_NESCD algorithm, while the green and blue lines represent the MMOEA that only uses ESCD and the MMOEA that only uses ANS, respectively. It can be observed that as the number of iterations increases, the rPSP value of MMO_NESCD decreases more significantly than the two variant algorithms, and it remains at an optimal level even at the end of evolution; this indicates that the algorithm has stronger convergence performance, further proving its effectiveness.
4.3 Parameter Sensitivity Analysis Experiments
We used DBSCAN clustering to partition the population. This clustering requires determining two parameters, Minpts and Eps. To successfully achieve population clustering, we set Minpts to a specific minimum value, which is the dimensional value of the decision variables plus one. For the clustering radius Eps, if it is set too small, it may produce a large number of noise points after clustering; if set too large, it may fail to achieve the desired clustering effect. Therefore, we used the K-nearest neighbors method (KNN) to determine Eps: calculating the distances between each individual and its k nearest neighbors, and then averaging all these distances to obtain Eps. In this way, we can calculate Eps based on population changes and the distribution of individuals around them, thus achieving adaptive adjustment of Eps.
We also need to consider the selection of k values, for which we set k to 4, 6, 8, 10, and 12, and performed rank-sum tests on the rPSP (normalized Pareto set similarity) metric values for these five cases, with results shown in Table 5. The experimental results indicate that when k is set to 8 and 10, the algorithm performs optimally; however, k set to 10 requires more computational resources, so the final value of k is determined to be 8.
4.4 Application Experiments in Location Optimization Problems
A location problem was designed based on real scenarios, which is also a practical multimodal multiobjective optimization problem. Therefore, we further used this test problem to verify the performance of the MMO_NESCD algorithm. Fig. 11 illustrates this practical problem, which includes 6 primary schools, 3 secondary schools, 13 supermarkets, and 6 stations. The problem requires minimizing four objectives, namely the distances to primary schools, secondary schools, supermarkets, and stations. These locations are crucial for residents’ daily lives, and finding a location close to these four types of places will greatly facilitate residents’ travel.
The population distribution map is drawn based on the results of 31 independent runs, corresponding to the results selected based on the median in the IGDx metric. Fig. 12 shows that the red and blue markers represent the true Pareto optimal region and the Pareto optimal region obtained by the algorithm, respectively. Compared to other algorithms, MMO_NESCD performs better in handling map-based problems: its population almost covers all Pareto regions, and the population distribution is uniform. Therefore, MMO_NESCD is a high-performance algorithm for handling map-based problems.
5
Summary and Outlook
5.1 Summary
This paper proposes the MMO_NESCD algorithm, which integrates Enhanced Special Crowding Distance (ESCD) and Adaptive Neighborhood Strategy (ANS) in environmental selection. It first clusters the population in the decision space using DBSCAN to enhance diversity, then combines ESCD for non-dominated sorting to select individuals, balancing diversity and convergence in both decision and objective spaces. On 22 problems from the CEC2019 test suite, this algorithm outperforms five advanced multimodal multiobjective evolutionary algorithms (such as DN-NSGAII, MMOCDE, etc.), achieving Pareto sets (PS) that are both diverse and convergent, as well as uniformly distributed Pareto fronts (PF).
5.2 Outlook
This paper points out the shortcomings of MMO_NESCD: insufficient attention to performance in the objective space leading to suboptimal PF shapes, not studying multimodal multiobjective optimization problems (MMOPs) with local Pareto sets (local PS), and the potential ineffectiveness of ESCD in high-dimensional MMOPs. Future research will focus on local MMOPs with local PS (balancing the convergence of local optimal solutions) and designing effective handling mechanisms for high-dimensional MMOPs to enhance algorithm performance.
Authors: Yue C, Song J, Liang J, et al. A multimodal multiobjective evolutionary algorithm based on neighborhood and enhanced special crowding distance[J]. Knowledge-Based Systems, 2025, 315: 113340.
Editor: Wu Junyi
Illustration: Wu Junyi
Review: Wei Xinping
Click the blue text to follow us