# An Evolutionary Algorithm with Clustering-Based Assisted Selection Strategy for Multimodal Multiobjective Optimization

Authors: Naili Luo; Wu Lin; Peizhi Huang; Jianyong Chen
Journal: Complexity
 (2021)

---

## Abstract

In multimodal multiobjective optimization problems (MMOPs), multiple Pareto optimal sets, even some good local Pareto optimal sets, should be reserved, which can provide more choices for decision-makers. To solve MMOPs, this paper proposes an evolutionary algorithm with clustering-based assisted selection strategy for multimodal multiobjective optimization, in which the addition operator and deletion operator are proposed to comprehensively consider the diversity in both decision and objective spaces. Specifically, in decision space, the union population is partitioned into multiple clusters by using a density-based clustering method, aiming to assist the addition operator to strengthen the population diversity. Then, a number of weight vectors are adopted to divide population intoN subregions in objective space (N is population size). Moreover, in the deletion operator, the solutions in the most crowded subregion are first collected into previous clusters, and then the worst solution in the most crowded cluster is deleted until there are N solutions left. Our algorithm is compared with other multimodal multiobjective evolutionary algorithms on the well-known benchmark MMOPs. Numerical experiments report the effectiveness and advantages of our proposed algorithm.


---

## Body

## 1. Introduction

Many real-world optimization problems often involve multiple (often conflicting) objectives [1–3], which are usually modeled as follows:(1)minx∈ΩFx=f1x,…,fmxT,where x is an n-dimensional decision vector in Ω∈ℝn and f1x,…,fmx are, respectively, the objective values of x by using a specific function mapping. Pareto optimal solutions (PS) are a set of nondominated solutions for an MOP, and Pareto optimal front (PF) represents their objective values [4–6]. To get the optimal solutions of an MOP, many multiobjective evolutionary optimization algorithms (MOEAs) are proposed to evolve a population with multiple solutions, aiming to approximate the true PF [7–9]. Due to the advantage of being able to optimize multiple solutions simultaneously, MOEAs have been a widely used approach to solve various kinds of optimization problems, that is, MOEAs based on Pareto dominance relation [10–13], MOEAs based on performance indicator [14–16], and MOEAs based on decomposition [17–25].Recently, some MOPs with different PSs or some accepted local PSs [26–28] have drawn much attention, which are called multimodal multiobjective optimization problems (MMOPs). In recent years, several studies considering the diversity in decision space are proposed to solve MMOPs. In Omni-optimizer [29], the crowding distance is regarded as the diversity indicator of solution in decision space and embedded into NSGA-II, which strengthens diversity of population. In DN-NSGA-II [30], it aims to maintain distinct solutions in decision space, while their objective values are equal. Moreover, in MOEA/D-AD [31], by incorporating the addition and deletion operators into MOEA/D, it can obtain multiple nondominated solutions being different in decision space, which strengthens the diversity of population in decision space. Furthermore, there are other heuristic algorithms having been getting more attention for MMOPs, that is, particle swarm optimization (PSO) algorithms [32–34]. For example, a PSO algorithm is proposed in [32] as an effective niching algorithm, which does not need any niching parameter. In MO_Ring_PSO_SCD [33], a ring topology and special crowding distance are incorporated into PSO algorithm, helping to ensure greater diversity. Similarly, in [34], the neighborhood in decision space is constructed by a self-organizing map network, aiming to approximate multiple PSs for solving MMOPs. Recently, in TriMOEA-TA&R [35], two archives are used to cooperatively balance the convergence in objective space and the diversity in both decision and objective spaces. Due to the complexities and unpredictability in decision-making, more solutions with good performance, that is, multiple distinct global PSs and even some local PSs with good quality, are supposed to provide for decision-making [35].However, for tackling MMOPs with at least one local PS, once global PSs are found in evolutionary process of the above multimodal MOEAs (MMOEAs) [29–35], all local PSs will not survive in next-generation population as local PSs are often dominated by global PS and they are usually replaced by some solutions with good convergence. To solve MMOPs, we develop a novel evolutionary algorithm with clustering-based assisted selection strategy for multimodal multiobjective optimization (MMOEA-CAS). In decision space, the union population is first partitioned into multiple clusters by a density-based clustering method, which will assist the addition operator to strengthen diversity of population. Then, a number of weight vectors divide population into N subregions in objective space (N is the population size), which is helpful to extend diversity of population. Moreover, in the deletion operator, the solutions in the most crowded subregion are collected into previous clusters, and then the worst solution in the most crowded cluster is deleted until there are N solutions left. Therefore, our approach is able to prevent the loss of local optimal solutions and help to realize a good balance in diversity of population. Here, the main contributions of our approach are stated as follows:(1)
Different from traditional environmental selection mechanisms, in MMOEA-CAS, a density-based clustering method is applied on the population to obtain multiple clusters according to their neighboring relationship in decision space. Based on those classified results, those solutions with better performance in each cluster have the priority to be selected in the addition operator. This way, the diversity in decision space can be ensured.(2)
The deletion operator proposed in our method considers the solutions’ density information from both decision and objective spaces. Firstly, a set of weight vectors are used to divide candidate solutions into different regions based on their locations in objective space; then solutions in most crowded subregion are classified into previous clusters and the crowded solution in this cluster is deleted. This way, the more promising solutions are reserved into next generation.Next, we give a brief introduction for organization of this paper. Some definitions about MMOPs and the introductions about the used clustering method are given in Section2. Then, the framework of our algorithm with the addition and deletion operators is described in Section 3. Experimental setup and results are presented and analyzed in Sections 4 and 5, respectively. At last, some conclusions and further directions are discussed in Section 6.


## 2. Preliminaries

### 2.1. MMOPs

In this subsection, we give a case of MMOPs, which is shown in Figure1. If any solution in a set PS1 cannot be dominated by any other solution in feasible regions, PS1 is regarded as global PS. The global PF is its objective vectors. Note that we marked global PS/PF with red color as shown in Figure 1. If any solution in a set PS cannot be dominated by any other solution in PS, PS is said to be local PS. The local PF is its objective vectors. As shown in Figure 1, we marked local PS/PF with blue color. Note that the local population is defined as the set including the neighboring solutions in the decision space. Thus, some MOPs with different PSs or local PSs [26–28] are called multimodal multiobjective optimization problems (MMOPs). For MMOPs, multiple different PSs, including global PSs and some good local PSs, should be provided for the decision-maker, which help to find more suitable solutions in making decision. Therefore, diversity of solutions in both objective and decision spaces should be considered equally important in the selection mechanisms of MOEAs for solving MMOPs.Figure 1
A case of MMOPs.


### 2.2. Density-Based Clustering Method

It is well known that DBSCAN [36] with the neighborhood parameters ε and MinPts (MinPts is positive integer) is a density-based clustering method, aiming to find the cluster defined to the maximal density-connected set of sample data deduced by the relationship of density-reachable. Considering each sample data x=x1,…,xn in a data set D, related definitions are given as follows:ε-Neighborhood: the ε-neighborhood Bx of x is defined as follows:(2)Bx=y∈U|distx,y≤ε,where dist(x, y) is Euclidean distance between x and y.Core objective: a sample data x is said to be core objective if it satisfies equation (3) as follows:(3)Bx≥MinPts.Directly density-reachable: if a sample data y is direct density-reachable from x, it must meet(4)y∈Bx,By≥MinPts.Density-reachable: the sample data y is said to be density-reachable from x if there are a set of sample data p1, p2, …, pn, where p1 = x, pn = y, and pi+1 is direct density-reachable from pi.Density-connected: the sample data x and y are said to be density-connected, if there is a sample data p where x and y are density-reachable from it.


## 2.1. MMOPs

In this subsection, we give a case of MMOPs, which is shown in Figure1. If any solution in a set PS1 cannot be dominated by any other solution in feasible regions, PS1 is regarded as global PS. The global PF is its objective vectors. Note that we marked global PS/PF with red color as shown in Figure 1. If any solution in a set PS cannot be dominated by any other solution in PS, PS is said to be local PS. The local PF is its objective vectors. As shown in Figure 1, we marked local PS/PF with blue color. Note that the local population is defined as the set including the neighboring solutions in the decision space. Thus, some MOPs with different PSs or local PSs [26–28] are called multimodal multiobjective optimization problems (MMOPs). For MMOPs, multiple different PSs, including global PSs and some good local PSs, should be provided for the decision-maker, which help to find more suitable solutions in making decision. Therefore, diversity of solutions in both objective and decision spaces should be considered equally important in the selection mechanisms of MOEAs for solving MMOPs.Figure 1
A case of MMOPs.


## 2.2. Density-Based Clustering Method

It is well known that DBSCAN [36] with the neighborhood parameters ε and MinPts (MinPts is positive integer) is a density-based clustering method, aiming to find the cluster defined to the maximal density-connected set of sample data deduced by the relationship of density-reachable. Considering each sample data x=x1,…,xn in a data set D, related definitions are given as follows:ε-Neighborhood: the ε-neighborhood Bx of x is defined as follows:(2)Bx=y∈U|distx,y≤ε,where dist(x, y) is Euclidean distance between x and y.Core objective: a sample data x is said to be core objective if it satisfies equation (3) as follows:(3)Bx≥MinPts.Directly density-reachable: if a sample data y is direct density-reachable from x, it must meet(4)y∈Bx,By≥MinPts.Density-reachable: the sample data y is said to be density-reachable from x if there are a set of sample data p1, p2, …, pn, where p1 = x, pn = y, and pi+1 is direct density-reachable from pi.Density-connected: the sample data x and y are said to be density-connected, if there is a sample data p where x and y are density-reachable from it.


## 3. The Proposed Algorithm

### 3.1. General Framework

In this section, we introduce the general framework of MMOEA-CAS (Algorithm1). At first, N solutions are randomly generated in Ω∈ℝn, which form a population P=x1,…,xN in line 1. In line 2, multiple weight vectors w1,…,wN are initialized [37]. Then, the recombination operators are applied on parent population to generate offspring population P’. Next, a union population U is formed by merging P′ and P in line 5. In line 6, according to Pareto dominated relationship [10], those solutions in U are ranked into different Pareto fronts F1,…, Ft. As shown in lines 7-8, after normalizing U, DBSCAN is used to divide normalized population into multiple clusters C1,…, CK in decision space. Then, the addition operator is used to select the promising solutions into next-generation population P with more than N solutions in line 9. Next, in lines 10-11, after normalizing P, the association process with a set of weight vectors is used to divide P into N subregions in objective space. Finally, in line 12, the deletion operator is run on P to delete the most crowded solution each time until there are N solutions left in P. If the maximal number of evaluations is reached, P is regarded as the final solution set as shown in line 14. If the current evaluations are still smaller than the maximal evaluations, the above procedure in lines 4–12 will continue until the stopping criterion is met.Algorithm 1Algorithm 1: General framework.
Input: N (the number of solutions in population)Output: P (final population)(1)
initialize a populationP(2)
initialize weight vectorsW=w1,…,wN(3)
while the stopping criterion is not met(4)
P' = Crossover + Mutation (P)(5)
U = P∪P′(6)
(F1, …, Ft) = Non-dominated Sorting (U)(7)
normalizeU(8)
(C1, …, CK) = DBSCAN (U, ε, MinPts)(9)
P = Addition Operator//Algorithm 2(10)
normalizeP(11)
(Δ1,…,ΔN) = Association Process (P, W)//Algorithm 3(12)
P = Deletion Operator//Algorithm 4(13)
end while(14)
returnP


### 3.2. Addition Operator

In this section, the addition operator (Algorithm2) is introduced to select some promising solutions to maintain diversity of population. As described in lines 1-2, the nondominated solutions are first selected and then add them into an empty set P in line 2. To further strengthen the diversity, in lines 3–6, the nondominated solutions in each cluster Ck (k = 1,…, K) are also added to P. In addition, solutions with better convergence in objective space are further selected with higher priority until the size of solutions in P is not less than N. As shown in lines 8–11, solutions from F2 to Ft are used to fill P according to their respective priorities. When there are more than N solutions, the addition operator ends with returning the temporary population P.Algorithm 2Algorithm 2: Addition operator.
Output: P (updated population)(1)
setP to be an empty set(2)
P = P ∪ F1(3)
fork = 1 toK(4)
(f1, …, ft) = Non-dominated Sorting (Ck)(5)
P = P  ∪ f1(6)
end for(7)
i = 1(8)
while|P| < N(9)
i = i + 1(10)
P = P ∪ Fi(11)
end while(12)
returnP


### 3.3. Association Procedure

After the addition operator is run, the association procedure (Algorithm3) will be applied on normalized P to divide population into N subregions in objective space by a set of weight vectors. At first, N empty subregions Δ1,…,ΔN are initialized in line 1. Next, for each solution x∈P, its distances to all weight vectors are computed, and then x is associated with its closest subregion as shown in lines 3–7. When all solutions are associated with their closest subregions, association procedure ends and Δ1,…,ΔN are returned in line 9.Algorithm 3Algorithm 3: Association procedure.
Input: P (population), W (weight vectors)Output: Δ1,…,ΔN (clusters)(1)
initializeN empty subregions Δ1,…,ΔN(2)
for eachx ∈ P(3)
for eachw∈W(4)
computedx,w=x−wTx/w(5)
end for(6)
i=argminw∈Wdx,w(7)
Δi=Δi∪x(8)
end for(9)
returnΔ1,...,ΔN


### 3.4. Deletion Operator

AfterΔ1,…,ΔN are got by association procedure, deletion operator (Algorithm 4) will be used to prune P to get N final solutions. The HAD method [38] is used to reflect the crowding distances of each solution x in decision space. Thus, as shown in line 2-3, after normalizing P, the HAD values of solutions are computed by equation (5) as follows:(5)HADx=Pi−1∑y∈Piandy≠x,1/distx,y,where dist ⋅ is the Euclidian distance between two normalized solutions. In line 4, find the most crowded subregion Δi by equation (6) as follows:(6)i=argmaxi∈1,…,NΔi.Algorithm 4Algorithm 4: Deletion operator.
Output: P (updated population)(1)
while |P| >N(2)
normalizeP(3)
compute HAD values of solutions inP by equation (5)(4)
find the most crowded subregionΔi by equation (6)(5)
divide all solutions inΔi into S1, …, SK by equation (7)(6)
find the most crowded clusterSk by equation (8)(7)
findx with the smallest HAD value in Sk(8)
deletex from Δi and P(9)
end while(10)
returnPIn line 5, solutions inΔi are classified into S1, …, SK by equation (7) as follows:(7)Sk=x|x∈Ck,k=1,…,K.Then, in line 6, find the most crowded clusterSk by equation (8) as follows:(8)k=argmaxk∈1,…,KSk.In lines 7-8, the solutionx with the smallest HAD value in Sk will be deleted from Δi and P. Finally, deletion operator ends until there are N solutions left and P will be returned in line 10 as the final population.


## 3.1. General Framework

In this section, we introduce the general framework of MMOEA-CAS (Algorithm1). At first, N solutions are randomly generated in Ω∈ℝn, which form a population P=x1,…,xN in line 1. In line 2, multiple weight vectors w1,…,wN are initialized [37]. Then, the recombination operators are applied on parent population to generate offspring population P’. Next, a union population U is formed by merging P′ and P in line 5. In line 6, according to Pareto dominated relationship [10], those solutions in U are ranked into different Pareto fronts F1,…, Ft. As shown in lines 7-8, after normalizing U, DBSCAN is used to divide normalized population into multiple clusters C1,…, CK in decision space. Then, the addition operator is used to select the promising solutions into next-generation population P with more than N solutions in line 9. Next, in lines 10-11, after normalizing P, the association process with a set of weight vectors is used to divide P into N subregions in objective space. Finally, in line 12, the deletion operator is run on P to delete the most crowded solution each time until there are N solutions left in P. If the maximal number of evaluations is reached, P is regarded as the final solution set as shown in line 14. If the current evaluations are still smaller than the maximal evaluations, the above procedure in lines 4–12 will continue until the stopping criterion is met.Algorithm 1Algorithm 1: General framework.
Input: N (the number of solutions in population)Output: P (final population)(1)
initialize a populationP(2)
initialize weight vectorsW=w1,…,wN(3)
while the stopping criterion is not met(4)
P' = Crossover + Mutation (P)(5)
U = P∪P′(6)
(F1, …, Ft) = Non-dominated Sorting (U)(7)
normalizeU(8)
(C1, …, CK) = DBSCAN (U, ε, MinPts)(9)
P = Addition Operator//Algorithm 2(10)
normalizeP(11)
(Δ1,…,ΔN) = Association Process (P, W)//Algorithm 3(12)
P = Deletion Operator//Algorithm 4(13)
end while(14)
returnP


## 3.2. Addition Operator

In this section, the addition operator (Algorithm2) is introduced to select some promising solutions to maintain diversity of population. As described in lines 1-2, the nondominated solutions are first selected and then add them into an empty set P in line 2. To further strengthen the diversity, in lines 3–6, the nondominated solutions in each cluster Ck (k = 1,…, K) are also added to P. In addition, solutions with better convergence in objective space are further selected with higher priority until the size of solutions in P is not less than N. As shown in lines 8–11, solutions from F2 to Ft are used to fill P according to their respective priorities. When there are more than N solutions, the addition operator ends with returning the temporary population P.Algorithm 2Algorithm 2: Addition operator.
Output: P (updated population)(1)
setP to be an empty set(2)
P = P ∪ F1(3)
fork = 1 toK(4)
(f1, …, ft) = Non-dominated Sorting (Ck)(5)
P = P  ∪ f1(6)
end for(7)
i = 1(8)
while|P| < N(9)
i = i + 1(10)
P = P ∪ Fi(11)
end while(12)
returnP


## 3.3. Association Procedure

After the addition operator is run, the association procedure (Algorithm3) will be applied on normalized P to divide population into N subregions in objective space by a set of weight vectors. At first, N empty subregions Δ1,…,ΔN are initialized in line 1. Next, for each solution x∈P, its distances to all weight vectors are computed, and then x is associated with its closest subregion as shown in lines 3–7. When all solutions are associated with their closest subregions, association procedure ends and Δ1,…,ΔN are returned in line 9.Algorithm 3Algorithm 3: Association procedure.
Input: P (population), W (weight vectors)Output: Δ1,…,ΔN (clusters)(1)
initializeN empty subregions Δ1,…,ΔN(2)
for eachx ∈ P(3)
for eachw∈W(4)
computedx,w=x−wTx/w(5)
end for(6)
i=argminw∈Wdx,w(7)
Δi=Δi∪x(8)
end for(9)
returnΔ1,...,ΔN


## 3.4. Deletion Operator

AfterΔ1,…,ΔN are got by association procedure, deletion operator (Algorithm 4) will be used to prune P to get N final solutions. The HAD method [38] is used to reflect the crowding distances of each solution x in decision space. Thus, as shown in line 2-3, after normalizing P, the HAD values of solutions are computed by equation (5) as follows:(5)HADx=Pi−1∑y∈Piandy≠x,1/distx,y,where dist ⋅ is the Euclidian distance between two normalized solutions. In line 4, find the most crowded subregion Δi by equation (6) as follows:(6)i=argmaxi∈1,…,NΔi.Algorithm 4Algorithm 4: Deletion operator.
Output: P (updated population)(1)
while |P| >N(2)
normalizeP(3)
compute HAD values of solutions inP by equation (5)(4)
find the most crowded subregionΔi by equation (6)(5)
divide all solutions inΔi into S1, …, SK by equation (7)(6)
find the most crowded clusterSk by equation (8)(7)
findx with the smallest HAD value in Sk(8)
deletex from Δi and P(9)
end while(10)
returnPIn line 5, solutions inΔi are classified into S1, …, SK by equation (7) as follows:(7)Sk=x|x∈Ck,k=1,…,K.Then, in line 6, find the most crowded clusterSk by equation (8) as follows:(8)k=argmaxk∈1,…,KSk.In lines 7-8, the solutionx with the smallest HAD value in Sk will be deleted from Δi and P. Finally, deletion operator ends until there are N solutions left and P will be returned in line 10 as the final population.


## 4. Experimental Settings

### 4.1. Test Instances and Parameter Settings

In experiments, a series of MMOPs from CEC 2019 [28] are used to validate the performance of all compared algorithms, that is, some MMOPs with many distinct PSs, some MMOPs with irregular shape of PSs (i.e., MMF1_e, MMF1_z, and MMF5-7), and some MMOPs with existing global and local PSs (MMF10-13, MMF15, and MMF15_a).Our proposed algorithm MMOEA-CAS is, respectively, compared with four MMOEAs (i.e., Omni-optimizer [29], DN-NSGA-II [30], MO_Ring_PSO_SCD [33], and TriMOEA-TA&R [35]) on all the MMOPs adopted. The parameter settings of compared algorithms are suggested in their references, which are given in Table 1.Table 1
Parameters setting of all compared algorithms.
Omnioptimizerηc=ηm=20,pc=1,pm=1/nDN-NSGA-IICF=0.5,ηc=ηm=20,pc=1,pm=1/nMO-ring-PSO-SCDC1=C2=2.05,W=0.7298TriMOEA-TA&Rpcon=0.5,δniche=0.1,εpeak=0.01,NR=100,NCA=20,NIA=6MMOEA-CASηc=ηm=20,pc=1,pm=1/n,MinPts = 3Note that simulated binary crossover (SBX) and polynomial-based mutation [10] are used as recombination operators for producing offspring in MMOEA-CAS. For DBSCAN, the neighborhood parameter MinPts is set to be 3, and ε is set by an adaptive strategy as follows:(9)r=∑i=1nximax−ximinn×0.1,where ximin and ximax are the minimum and maximum values in i-th dimension.In addition, the population size is equal to 100 ×n for different test problems with n-dimensional decision variables and the maximum evaluation is equal to 5000 × n. In order to avoid exceptional situation, we collect 21 times of experimental results for each algorithm on solving each test problem.


### 4.2. Performance Indicator

In our experiments, we select the inverted generational distance (IGD [39, 40]) as performance indicator. To evaluate the quality of obtained solutions in decision space or objective space, IGD is, respectively, applied on two different spaces. When computing IGD, sampling reference points on the true PS or PF is necessary.IfP∗ is composed of sampling reference points on PS and P is the final set of decision variables in decision space, the distance between P∗ and P is named IGDX. If P∗ is composed of sampling reference points on PF and P is the final set of objective values in objective space, the distance between them is named IGDF. In general, we compute the IGD value according to the following equation:(10)IGDP,P∗=∑i=1P∗minj=1Adpi,xjP∗,where d(pi, xj) is Euclidean distance between pi and xj (pi belongs to P∗ and xj to belongs P). The lower IGDX or IGDF values indicate the better performance of P.


## 4.1. Test Instances and Parameter Settings

In experiments, a series of MMOPs from CEC 2019 [28] are used to validate the performance of all compared algorithms, that is, some MMOPs with many distinct PSs, some MMOPs with irregular shape of PSs (i.e., MMF1_e, MMF1_z, and MMF5-7), and some MMOPs with existing global and local PSs (MMF10-13, MMF15, and MMF15_a).Our proposed algorithm MMOEA-CAS is, respectively, compared with four MMOEAs (i.e., Omni-optimizer [29], DN-NSGA-II [30], MO_Ring_PSO_SCD [33], and TriMOEA-TA&R [35]) on all the MMOPs adopted. The parameter settings of compared algorithms are suggested in their references, which are given in Table 1.Table 1
Parameters setting of all compared algorithms.
Omnioptimizerηc=ηm=20,pc=1,pm=1/nDN-NSGA-IICF=0.5,ηc=ηm=20,pc=1,pm=1/nMO-ring-PSO-SCDC1=C2=2.05,W=0.7298TriMOEA-TA&Rpcon=0.5,δniche=0.1,εpeak=0.01,NR=100,NCA=20,NIA=6MMOEA-CASηc=ηm=20,pc=1,pm=1/n,MinPts = 3Note that simulated binary crossover (SBX) and polynomial-based mutation [10] are used as recombination operators for producing offspring in MMOEA-CAS. For DBSCAN, the neighborhood parameter MinPts is set to be 3, and ε is set by an adaptive strategy as follows:(9)r=∑i=1nximax−ximinn×0.1,where ximin and ximax are the minimum and maximum values in i-th dimension.In addition, the population size is equal to 100 ×n for different test problems with n-dimensional decision variables and the maximum evaluation is equal to 5000 × n. In order to avoid exceptional situation, we collect 21 times of experimental results for each algorithm on solving each test problem.


## 4.2. Performance Indicator

In our experiments, we select the inverted generational distance (IGD [39, 40]) as performance indicator. To evaluate the quality of obtained solutions in decision space or objective space, IGD is, respectively, applied on two different spaces. When computing IGD, sampling reference points on the true PS or PF is necessary.IfP∗ is composed of sampling reference points on PS and P is the final set of decision variables in decision space, the distance between P∗ and P is named IGDX. If P∗ is composed of sampling reference points on PF and P is the final set of objective values in objective space, the distance between them is named IGDF. In general, we compute the IGD value according to the following equation:(10)IGDP,P∗=∑i=1P∗minj=1Adpi,xjP∗,where d(pi, xj) is Euclidean distance between pi and xj (pi belongs to P∗ and xj to belongs P). The lower IGDX or IGDF values indicate the better performance of P.


## 5. Experimental Studies

### 5.1. Results and Discussion

As shown in Table2, the compared results of other MMOEAs (i.e., Omni-optimizer, DN-NSGA-II, MO_Ring_PSO_SCD, and TriMOEA-TA&R) and MMOEA-CAS in terms of IGDX and IGDF metrics are summarized. In order to get more intuitional information from the statistical data, we use “+/–/∼” to record the compared results between other four competitors and MMOEA-CAS, where Wilcoxon’s rank-sum test with α = 0.05 is used in comparison. According to the overall statistic results in the last row in Table 2, we can observe that MMOEA-CAS showed better performance than four other compared algorithms in 31, 32, 25, and 32 out of 44 cases, and it was similar to them in 4, 3, 5, and 2 cases. Conversely, the results obtained by MMOEA-CAS were significantly worse than those obtained by other MMOEAs in 9, 9, 14, and 10 out of 44 cases. The above comparison results demonstrate that our proposed MMOEA-CAS can get more uniformly and widely distributed solutions in decision space without deteriorating distributions in objective space, which confirms its superiority and effectiveness in solving most of MMOPs adopted.Table 2
The summarized results of other MMOEAs with MMOEA-CAS.
AlgorithmOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&R+/−/∼(IGDX)0/21/10/21/19/11/25/17/0+/−/∼(IGDF)9/10/39/11/25/14/35/15/2+/−/∼(All)9/31/49/32/314/25/510/32/2Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.The detailed IGDX and IGDF values of MMOEA-CAS and four MMOEAs are reported in Tables3 and 4, respectively. To be much clearer, we marked the best value in bold for each test problem. In Table 3, MMOEA-CAS achieved the best IGDX values in 10 cases, that is, Omnitest, MMF2, MMF4, MMF7, MMF10-13, MMF15, and MMF15_a; MO_Ring_PSO_SCD got best IGDX values in 8 cases, that is, SYM-PART rotated, MMF5-6, and MMF8; TriMOEA-TA&R only obtained best IGDX values in 4 cases, that is, SYM-PART simple and MMF9. The remaining compared algorithms could not obtain best IGDX value in any case. Similarly, we could also observe from Table 4 that MMOEA-CAS obtained the best IGDF values in 10 cases, that is, MMF4, MMF7, MMF10-15, MMF14_a, and MMF15_a; Omnioptimizer got the smallest IGDF values in 9 cases, that is, SYM-PART simple, MMF1_z, MMF2, MMF5-6, and MMF8-9; MO_Ring_PSO_SCD obtained the smallest IGDF values on MMF1 and MMF3, while TriMOEA-TA&R only obtained the smallest IGDF value on MMF1_e; DN-NSGA-II could not obtain best IGDX value in any case. Thus, we could conclude that MMOEA-CAS achieved best IGDX values and best IGDF values on MMOPs with existing global and local PSs, that is, MMF10-13, MMF15, and MMF15_a. By collecting the best values on all MMOPs in terms of IGDX and IGDF, we can conclude that the overall performance of our proposed MMOEA-CAS is better than other compared algorithms on these test problems. In addition, the above comparison results based on the best performance on each test problem demonstrate that the environmental selection mechanism of MMOEA-CAS can reserve more promising solutions, while those classical environmental selection criteria have no ability to solve these MMOPs well.Table 3
Results obtained by four other MMOEAs and MMOEA-CAS on IGDX.
BenchmarkOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&RMMOEA-CASSYM-PART simple5.558e + 00 (2.61e + 00)−3.810e + 00 (9.39e−01)−1.663e−01 (2.19e−02)−2.181e−02 (3.01e−03) +7.633e−02 (4.92e−03)SYM-PART rotated4.405e + 00 (1.22e + 00)−4.613e + 00 (1.99e + 00)−1.972e−01 (3.50e−02)+1.674e + 00 (9.48e−01)−4.240e−01 (6.09e−01)Omnitest1.501e + 00 (2.29e−01)−1.410e + 00 (2.10e−01)−4.057e−01 (8.74e−02)−2.536e−01 (1.09e−01)−1.092e−01 (3.23e−03)MMF19.905e−02 (1.81e−02)−9.963e−02 (1.70e−02)−4.951e−02 (2.06e−03)+7.290e−02 (8.54e−03)−5.350e−02 (5.06e−03)MMF1_z7.949e−02 (1.57e−02)−7.898e−02 (1.01e−02)−3.576e−02 (2.13e−03)+7.040e−02 (1.17e−02)−5.593e−02 (6.27e−03)MMF1_e1.314e + 00 (7.26e−01)∼1.055e + 00 (4.70e−01)∼5.709e−01 (2.57e−01)+1.940e + 00 (7.07e−01)−1.074e + 00 (2.73e−01)MMF21.266e−01 (1.01e−01)−1.389e−01 (8.51e−02)−3.802e−02 (1.72e−02)∼7.150e−02 (2.82e−02)−3.370e−02 (1.36e−02)MMF39.213e−02 (4.50e−02)−9.220e−02 (3.53e−02)−3.164e−02 (1.19e−02)+9.315e−02 (3.98e−02)−4.730e−02 (1.46e−02)MMF48.358e−02 (2.70e−02)−8.963e−02 (2.55e−02)−2.705e−02 (1.71e−03)−1.008e−01 (1.43e−01)−2.221e−02 (1.91e−03)MMF51.763e−01 (2.39e−02)−1.703e−01 (2.06e−02)−8.615e−02 (5.66e−03)∼1.114e−01 (8.42e−03)−8.754e−02 (8.77e−03)MMF61.441e−01 (1.68e−02)−1.471e−01 (1.66e−02)−7.260e−02 (3.87e−03)+9.006e−02 (9.24e−03) +1.136e−01 (2.14e−02)MMF74.629e−02 (9.25e−03)−5.681e−02 (1.40e−02)−2.610e−02 (1.54e−03)−4.468e−02 (2.13e−02)−2.428e−02 (3.96e−03)MMF83.286e−01 (1.65e−01)−3.012e−01 (9.95e−02)−6.719e−02 (5.03e−03)+3.438e−01 (1.04e−01)−1.448e−01 (3.29e−02)MMF92.200e−02 (1.09e−02)−2.529e−02 (1.32e−02)−7.882e−03 (3.55e−04)+3.124e−03 (9.15e−05) +8.759e−03 (1.30e−03)MMF101.646e−01 (3.31e−02)−1.617e−01 (4.48e−02)−1.004e−01 (3.69e−02)−2.014e−01 (7.52e−05)−2.755e−02 (4.78e−02)MMF112.502e−01 (3.58e−04)−2.505e−01 (4.85e−04)−2.169e−01 (2.72e−02)−2.524e−01 (5.79e−05)−9.196e−03 (1.25e−03)MMF122.396e−01 (1.68e−02)−2.467e−01 (9.44e−04)−1.875e−01 (4.53e−02)−2.477e−01 (6.84e−04)−3.120e−03 (1.84e−04)MMF132.858e−01 (9.42e−03)−2.895e−01 (1.54e−02)−2.325e−01 (1.43e−02)−2.714e−01 (6.55e−03)−1.055e−01 (1.46e−02)MMF148.873e−02 (6.29e−03)−9.794e−02 (9.76e−03)−5.329e−02 (1.86e−03)−3.651e−02 (4.92e−04) +4.651e−02 (1.11e−03)MMF14_a1.110e−01 (9.66e−03)−1.196e−01 (5.83e−03)−5.997e−02 (1.97e−03)+5.604e−02 (1.59e−03) +7.757e−02 (4.54e−03)MMF152.471e−01 (2.10e−02)−2.238e−01 (2.59e−02)−1.562e−01 (1.63e−02)−2.711e−01 (2.53e−04)−5.256e−02 (7.43e−03)MMF15_a2.133e−01 (1.99e−02)−2.086e−01 (1.46e−02)−1.641e−01 (1.31e−02)−2.194e−01 (2.83e−03)−9.684e−02 (6.43e−03)best/all0/220/228/224/2210/22+/–/∼0/21/10/21/19/11/25/17/0– –Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.Table 4
Results obtained by four other MMOEAs and MMOEA-CAS on IGDF.
BenchmarkOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&RMMOEA-CASSYM-PART simple1.216e−02 (1.72e−03)+1.230e−02 (1.78e−03)+4.042e−02 (5.50e−03)−3.414e−02 (4.99e−03)−2.628e−02 (3.07e−03)SYM-PART rotated1.252e−02 (1.70e−03)+1.539e−02 (2.12e−03)+4.604e−02 (4.32e−03)−2.843e−02 (3.88e−03)+3.201e−02 (5.92e−03)Omnitest6.776e−03 (2.47e−04)+7.911e−03 (5.10e−04)+4.232e−02 (5.35e−03)−1.841e−02 (4.18e−03)+2.953e−02 (2.03e−03)MMF13.788e−03 (5.27e−04)+4.451e−03 (4.07e−04)+3.707e−03 (1.58e−04)+4.926e−03 (9.72e−04)∼4.762e−03 (5.42e−04)MMF1_z3.231e−03 (4.30e−04)+3.649e−03 (4.91e−04)+3.603e−03 (1.57e−04)+4.418e−03 (9.38e−04)+5.427e−03 (1.06e−03)MMF1_e1.701e−02 (9.98e−03)+2.171e−02 (1.52e−02)+1.229e−02 (1.50e−03)+6.981e−03 (1.42e−03)+1.191e−01 (5.32e−02)MMF21.801e−02 (9.68e−03)∼3.691e−02 (3.43e−02)∼1.994e−02 (4.34e−03)∼2.521e−02 (8.18e−03)−1.839e−02 (3.99e−03)MMF32.203e−02 (2.40e−02)∼2.320e−02 (1.42e−02)∼1.614e−02 (3.22e−03)∼5.876e−02 (7.78e−02)−1.990e−02 (9.70e−03)MMF42.818e−03 (2.63e−04)−3.209e−03 (1.81e−04)−3.652e−03 (3.93e−04)−3.445e−02 (6.70e−02)−2.694e−03 (4.49e−04)MMF53.471e−03 (6.47e−04)+3.793e−03 (3.10e−04)+3.748e−03 (1.94e−04)+4.220e−03 (6.03e−04)∼4.284e−03 (5.54e−04)MMF63.154e−03 (3.20e−04)+3.747e−03 (2.97e−04)+3.538e−03 (1.34e−04)+4.602e−03 (2.06e−03)+7.700e−03 (2.43e−03)MMF73.162e−03 (2.96e−04)−3.957e−03 (4.17e−04)−3.830e−03 (3.43e−04)−4.273e−03 (1.25e−03)−2.937e−03 (6.51e−04)MMF83.145e−03 (1.88e−04)+3.983e−03 (5.03e−04)+4.838e−03 (2.83e−04)∼5.667e−03 (7.00e−03)−5.583e−03 (1.69e−03)MMF91.271e−02 (1.28e−03)∼1.441e−02 (1.84e−03)−1.562e−02 (1.42e−03)−6.975e−02 (4.17e−03)−1.332e−02 (1.42e−03)MMF101.822e−01 (4.17e−02)−1.938e−01 (4.11e−02)−1.297e−01 (1.51e−02)−2.285e−01 (5.05e−03)−3.839e−02 (3.63e−02)MMF119.565e−02 (9.39e−04)−9.823e−02 (2.07e−03)−8.508e−02 (6.16e−03)−1.633e−01 (7.27e−03)−2.827e−02 (3.10e−03)MMF128.611e−02 (8.13e−03)−8.404e−02 (2.68e−03)−6.431e−02 (1.27e−02)−8.601e−02 (1.47e−03)−5.118e−03 (3.54e−04)MMF131.472e−01 (2.08e−03)−1.507e−01 (4.40e−03)−9.329e−02 (1.73e−02)−2.431e−01 (6.87e−03)−4.139e−02 (9.33e−03)MMF149.765e−02 (3.95e−03)−1.080e−01 (8.20e−03)−8.042e−02 (2.94e−03)−8.616e−02 (1.12e−03)−6.788e−02 (1.14e−03)MMF14_a1.049e−01 (4.57e−03)−1.178e−01 (6.69e−03)−7.818e−02 (2.50e−03)−7.878e−02 (1.15e−03)−7.506e−02 (1.69e−03)MMF152.010e−01 (7.37e−03)−2.162e−01 (1.14e−02)−1.741e−01 (3.27e−03)−2.067e−01 (7.10e−04)−1.134e−01 (1.21e−02)MMF15_a2.074e−01 (8.92e−03)−2.259e−01 (1.05e−02)−1.744e−01 (3.72e−03)−1.936e−01 (3.67e−03)−1.483e−01 (3.59e−03)best/all9/220/222/221/2210/22+/–/∼9/10/39/11/25/14/35/15/2– –Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.Based on the experimental results in terms of IGDX, we can find that Omni-optimizer and DN-NSGAII could not perform better than MMOEA-CAS on any case, showing the drawbacks of their selection mechanisms when solving those test problems. It can be concluded that the fast nondominated sorting approach used in Omni-optimizer and DN-NSGA-II failed to maintain the diversity in decision space, since it always intended to choose the solutions with better convergence and diversity in objective space. Thus, regarding the performance of final population obtained in decision space, the above two algorithms always obtain poor performance on all test problems because they neglect the importance of diversity in decision space. To address this issue, MMOEA-CAS used the density-based clustering method to divide clusters where the similar solutions are likely to be collected into the same cluster. At the same time, in the addition operator, the solutions with good performance in the same cluster even if it is worse in the whole population can be still seen as promising candidate solutions. This way, MMOEA-CAS can guarantee the diversity of population in decision space. This also explains why Omni-optimizer and DN-NSGA-II showed the advantages on MMOPs with multiple PSs (i.e., SYM-PART simple, SYM-PART rotated, Omni-test, MMF1, MMF5-6, and MMF8) when comparing the quality of population in objective space, while they showed poor performance on some MMOPs with local and global PSs (i.e., MMF10-13, MM15, and MMF15_a) in terms of IGDX. Due to the comprehensive consideration of the diversity in both decision and objective spaces, MMOEA-CAS achieves better performance on most MMOPs at the expense of diversity in objective space when solving some problems with multiple PSs.In order to improve the diversity in decision space, MO_Ring_PSO_SCD used the special crowding distance, while it still followed the principle of convergence first in objective space. The local Pareto optimal solutions are always lost during the evolutionary process of MO_Ring_PSO_SCD. Similarly, in TriMOEA-TA&R, nondominated solutions still replace dominated solutions in objective space, so it also failed to strike the balance between the diversity in decision and objective spaces. To avoid the local Pareto optimal solutions being replaced by the solutions with better convergence during the evolutionary process, the proposed addition and deletion operators in MMOEA-CAS collaboratively select more promising solution into next generation according to the information of clustering results classified by the density-based clustering method in decision space and the subregions divided by weight vectors in objective space. Therefore, only the solutions that are always performing worse in both two spaces are abandoned, and those solutions having good performance in either space could get to survive. Although MO_Ring_PSO_SCD and TriMOEA-TA&R performed better than MMOEA-CAS on some problems with multiple PSs, they still obtained poor performance when compared with MMOEA-CAS on MMOPs having global and local PSs. As shown in Tables3 and 4, when compared with MMOEA-CAS, it is obvious that MO_Ring_PSO_SCD and TriMOEA-TA&R achieved worse results on most MMOPs, especially on these MMOPs having global and local PSs. Thus, these compared results validate the effectiveness of MMOEA-CAS and it is able to gain solutions with better overall performance in decision space and objective space when compared to other MMOEAs on most MMOPs.


### 5.2. Further Discussion

To clearly demonstrate the performance of different MMOEAs, the final populations obtained in decision and objective spaces by different algorithms are plotted in Figures2–3, which qualitatively show the effectiveness and advantages of our proposed algorithm on solving these MMOPs. For example, a MMOP with multiple PSs, that is, SYM-PART rotated, is shown in Figure 2, and a MMOP with local PS, that is, MMF10, is shown in Figure 3, respectively. From Figure 2, it was found that the diversity of final population obtained by MMOEA-CAS is more uniform in decision space. Although Omnioptimizer and DN-NSGA-II found better solutions in objective space, they failed to maintain other PSs in decision space. Similarly, the population obtained by TriMOEA-TA&R also missed some PSs in decision space. MO_Ring_PSO_SCD found all PSs, but the final solutions cannot uniformly cover all the true PSs. Thus, we can conclude that MMOEA-CAS gets better results in terms of the comprehensive performance in both decision and objective spaces on SYM-PART rotated.Figure 2
The final populations obtained in decision and objective spaces on SYM-PART rotated.
(a)(b)(c)(d)(e)Figure 3
The final populations obtained in decision and objective spaces on MMF10.
(a)(b)(c)(d)(e)Furthermore, for MMF10, the final populations obtained are also shown in Figure3. It is obvious that the performance of final population obtained by MMOEA-CAS is significantly better than other MMOEAs. Other compared algorithms mainly pick solutions with faster convergence rates in objective space, which will cause some local optimal solutions always to be eliminated by the global optimal solutions. Thus, only MMOEA-CAS maintained some promising local optimal solutions. To summarize, MMOEA-CAS shows some superiorities on two cases, especially on MM10.


## 5.1. Results and Discussion

As shown in Table2, the compared results of other MMOEAs (i.e., Omni-optimizer, DN-NSGA-II, MO_Ring_PSO_SCD, and TriMOEA-TA&R) and MMOEA-CAS in terms of IGDX and IGDF metrics are summarized. In order to get more intuitional information from the statistical data, we use “+/–/∼” to record the compared results between other four competitors and MMOEA-CAS, where Wilcoxon’s rank-sum test with α = 0.05 is used in comparison. According to the overall statistic results in the last row in Table 2, we can observe that MMOEA-CAS showed better performance than four other compared algorithms in 31, 32, 25, and 32 out of 44 cases, and it was similar to them in 4, 3, 5, and 2 cases. Conversely, the results obtained by MMOEA-CAS were significantly worse than those obtained by other MMOEAs in 9, 9, 14, and 10 out of 44 cases. The above comparison results demonstrate that our proposed MMOEA-CAS can get more uniformly and widely distributed solutions in decision space without deteriorating distributions in objective space, which confirms its superiority and effectiveness in solving most of MMOPs adopted.Table 2
The summarized results of other MMOEAs with MMOEA-CAS.
AlgorithmOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&R+/−/∼(IGDX)0/21/10/21/19/11/25/17/0+/−/∼(IGDF)9/10/39/11/25/14/35/15/2+/−/∼(All)9/31/49/32/314/25/510/32/2Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.The detailed IGDX and IGDF values of MMOEA-CAS and four MMOEAs are reported in Tables3 and 4, respectively. To be much clearer, we marked the best value in bold for each test problem. In Table 3, MMOEA-CAS achieved the best IGDX values in 10 cases, that is, Omnitest, MMF2, MMF4, MMF7, MMF10-13, MMF15, and MMF15_a; MO_Ring_PSO_SCD got best IGDX values in 8 cases, that is, SYM-PART rotated, MMF5-6, and MMF8; TriMOEA-TA&R only obtained best IGDX values in 4 cases, that is, SYM-PART simple and MMF9. The remaining compared algorithms could not obtain best IGDX value in any case. Similarly, we could also observe from Table 4 that MMOEA-CAS obtained the best IGDF values in 10 cases, that is, MMF4, MMF7, MMF10-15, MMF14_a, and MMF15_a; Omnioptimizer got the smallest IGDF values in 9 cases, that is, SYM-PART simple, MMF1_z, MMF2, MMF5-6, and MMF8-9; MO_Ring_PSO_SCD obtained the smallest IGDF values on MMF1 and MMF3, while TriMOEA-TA&R only obtained the smallest IGDF value on MMF1_e; DN-NSGA-II could not obtain best IGDX value in any case. Thus, we could conclude that MMOEA-CAS achieved best IGDX values and best IGDF values on MMOPs with existing global and local PSs, that is, MMF10-13, MMF15, and MMF15_a. By collecting the best values on all MMOPs in terms of IGDX and IGDF, we can conclude that the overall performance of our proposed MMOEA-CAS is better than other compared algorithms on these test problems. In addition, the above comparison results based on the best performance on each test problem demonstrate that the environmental selection mechanism of MMOEA-CAS can reserve more promising solutions, while those classical environmental selection criteria have no ability to solve these MMOPs well.Table 3
Results obtained by four other MMOEAs and MMOEA-CAS on IGDX.
BenchmarkOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&RMMOEA-CASSYM-PART simple5.558e + 00 (2.61e + 00)−3.810e + 00 (9.39e−01)−1.663e−01 (2.19e−02)−2.181e−02 (3.01e−03) +7.633e−02 (4.92e−03)SYM-PART rotated4.405e + 00 (1.22e + 00)−4.613e + 00 (1.99e + 00)−1.972e−01 (3.50e−02)+1.674e + 00 (9.48e−01)−4.240e−01 (6.09e−01)Omnitest1.501e + 00 (2.29e−01)−1.410e + 00 (2.10e−01)−4.057e−01 (8.74e−02)−2.536e−01 (1.09e−01)−1.092e−01 (3.23e−03)MMF19.905e−02 (1.81e−02)−9.963e−02 (1.70e−02)−4.951e−02 (2.06e−03)+7.290e−02 (8.54e−03)−5.350e−02 (5.06e−03)MMF1_z7.949e−02 (1.57e−02)−7.898e−02 (1.01e−02)−3.576e−02 (2.13e−03)+7.040e−02 (1.17e−02)−5.593e−02 (6.27e−03)MMF1_e1.314e + 00 (7.26e−01)∼1.055e + 00 (4.70e−01)∼5.709e−01 (2.57e−01)+1.940e + 00 (7.07e−01)−1.074e + 00 (2.73e−01)MMF21.266e−01 (1.01e−01)−1.389e−01 (8.51e−02)−3.802e−02 (1.72e−02)∼7.150e−02 (2.82e−02)−3.370e−02 (1.36e−02)MMF39.213e−02 (4.50e−02)−9.220e−02 (3.53e−02)−3.164e−02 (1.19e−02)+9.315e−02 (3.98e−02)−4.730e−02 (1.46e−02)MMF48.358e−02 (2.70e−02)−8.963e−02 (2.55e−02)−2.705e−02 (1.71e−03)−1.008e−01 (1.43e−01)−2.221e−02 (1.91e−03)MMF51.763e−01 (2.39e−02)−1.703e−01 (2.06e−02)−8.615e−02 (5.66e−03)∼1.114e−01 (8.42e−03)−8.754e−02 (8.77e−03)MMF61.441e−01 (1.68e−02)−1.471e−01 (1.66e−02)−7.260e−02 (3.87e−03)+9.006e−02 (9.24e−03) +1.136e−01 (2.14e−02)MMF74.629e−02 (9.25e−03)−5.681e−02 (1.40e−02)−2.610e−02 (1.54e−03)−4.468e−02 (2.13e−02)−2.428e−02 (3.96e−03)MMF83.286e−01 (1.65e−01)−3.012e−01 (9.95e−02)−6.719e−02 (5.03e−03)+3.438e−01 (1.04e−01)−1.448e−01 (3.29e−02)MMF92.200e−02 (1.09e−02)−2.529e−02 (1.32e−02)−7.882e−03 (3.55e−04)+3.124e−03 (9.15e−05) +8.759e−03 (1.30e−03)MMF101.646e−01 (3.31e−02)−1.617e−01 (4.48e−02)−1.004e−01 (3.69e−02)−2.014e−01 (7.52e−05)−2.755e−02 (4.78e−02)MMF112.502e−01 (3.58e−04)−2.505e−01 (4.85e−04)−2.169e−01 (2.72e−02)−2.524e−01 (5.79e−05)−9.196e−03 (1.25e−03)MMF122.396e−01 (1.68e−02)−2.467e−01 (9.44e−04)−1.875e−01 (4.53e−02)−2.477e−01 (6.84e−04)−3.120e−03 (1.84e−04)MMF132.858e−01 (9.42e−03)−2.895e−01 (1.54e−02)−2.325e−01 (1.43e−02)−2.714e−01 (6.55e−03)−1.055e−01 (1.46e−02)MMF148.873e−02 (6.29e−03)−9.794e−02 (9.76e−03)−5.329e−02 (1.86e−03)−3.651e−02 (4.92e−04) +4.651e−02 (1.11e−03)MMF14_a1.110e−01 (9.66e−03)−1.196e−01 (5.83e−03)−5.997e−02 (1.97e−03)+5.604e−02 (1.59e−03) +7.757e−02 (4.54e−03)MMF152.471e−01 (2.10e−02)−2.238e−01 (2.59e−02)−1.562e−01 (1.63e−02)−2.711e−01 (2.53e−04)−5.256e−02 (7.43e−03)MMF15_a2.133e−01 (1.99e−02)−2.086e−01 (1.46e−02)−1.641e−01 (1.31e−02)−2.194e−01 (2.83e−03)−9.684e−02 (6.43e−03)best/all0/220/228/224/2210/22+/–/∼0/21/10/21/19/11/25/17/0– –Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.Table 4
Results obtained by four other MMOEAs and MMOEA-CAS on IGDF.
BenchmarkOmnioptimizerDN-NSGA-IIMO-Ring-PSO-SCDTriMOEA-TA&RMMOEA-CASSYM-PART simple1.216e−02 (1.72e−03)+1.230e−02 (1.78e−03)+4.042e−02 (5.50e−03)−3.414e−02 (4.99e−03)−2.628e−02 (3.07e−03)SYM-PART rotated1.252e−02 (1.70e−03)+1.539e−02 (2.12e−03)+4.604e−02 (4.32e−03)−2.843e−02 (3.88e−03)+3.201e−02 (5.92e−03)Omnitest6.776e−03 (2.47e−04)+7.911e−03 (5.10e−04)+4.232e−02 (5.35e−03)−1.841e−02 (4.18e−03)+2.953e−02 (2.03e−03)MMF13.788e−03 (5.27e−04)+4.451e−03 (4.07e−04)+3.707e−03 (1.58e−04)+4.926e−03 (9.72e−04)∼4.762e−03 (5.42e−04)MMF1_z3.231e−03 (4.30e−04)+3.649e−03 (4.91e−04)+3.603e−03 (1.57e−04)+4.418e−03 (9.38e−04)+5.427e−03 (1.06e−03)MMF1_e1.701e−02 (9.98e−03)+2.171e−02 (1.52e−02)+1.229e−02 (1.50e−03)+6.981e−03 (1.42e−03)+1.191e−01 (5.32e−02)MMF21.801e−02 (9.68e−03)∼3.691e−02 (3.43e−02)∼1.994e−02 (4.34e−03)∼2.521e−02 (8.18e−03)−1.839e−02 (3.99e−03)MMF32.203e−02 (2.40e−02)∼2.320e−02 (1.42e−02)∼1.614e−02 (3.22e−03)∼5.876e−02 (7.78e−02)−1.990e−02 (9.70e−03)MMF42.818e−03 (2.63e−04)−3.209e−03 (1.81e−04)−3.652e−03 (3.93e−04)−3.445e−02 (6.70e−02)−2.694e−03 (4.49e−04)MMF53.471e−03 (6.47e−04)+3.793e−03 (3.10e−04)+3.748e−03 (1.94e−04)+4.220e−03 (6.03e−04)∼4.284e−03 (5.54e−04)MMF63.154e−03 (3.20e−04)+3.747e−03 (2.97e−04)+3.538e−03 (1.34e−04)+4.602e−03 (2.06e−03)+7.700e−03 (2.43e−03)MMF73.162e−03 (2.96e−04)−3.957e−03 (4.17e−04)−3.830e−03 (3.43e−04)−4.273e−03 (1.25e−03)−2.937e−03 (6.51e−04)MMF83.145e−03 (1.88e−04)+3.983e−03 (5.03e−04)+4.838e−03 (2.83e−04)∼5.667e−03 (7.00e−03)−5.583e−03 (1.69e−03)MMF91.271e−02 (1.28e−03)∼1.441e−02 (1.84e−03)−1.562e−02 (1.42e−03)−6.975e−02 (4.17e−03)−1.332e−02 (1.42e−03)MMF101.822e−01 (4.17e−02)−1.938e−01 (4.11e−02)−1.297e−01 (1.51e−02)−2.285e−01 (5.05e−03)−3.839e−02 (3.63e−02)MMF119.565e−02 (9.39e−04)−9.823e−02 (2.07e−03)−8.508e−02 (6.16e−03)−1.633e−01 (7.27e−03)−2.827e−02 (3.10e−03)MMF128.611e−02 (8.13e−03)−8.404e−02 (2.68e−03)−6.431e−02 (1.27e−02)−8.601e−02 (1.47e−03)−5.118e−03 (3.54e−04)MMF131.472e−01 (2.08e−03)−1.507e−01 (4.40e−03)−9.329e−02 (1.73e−02)−2.431e−01 (6.87e−03)−4.139e−02 (9.33e−03)MMF149.765e−02 (3.95e−03)−1.080e−01 (8.20e−03)−8.042e−02 (2.94e−03)−8.616e−02 (1.12e−03)−6.788e−02 (1.14e−03)MMF14_a1.049e−01 (4.57e−03)−1.178e−01 (6.69e−03)−7.818e−02 (2.50e−03)−7.878e−02 (1.15e−03)−7.506e−02 (1.69e−03)MMF152.010e−01 (7.37e−03)−2.162e−01 (1.14e−02)−1.741e−01 (3.27e−03)−2.067e−01 (7.10e−04)−1.134e−01 (1.21e−02)MMF15_a2.074e−01 (8.92e−03)−2.259e−01 (1.05e−02)−1.744e−01 (3.72e−03)−1.936e−01 (3.67e−03)−1.483e−01 (3.59e−03)best/all9/220/222/221/2210/22+/–/∼9/10/39/11/25/14/35/15/2– –Wilcoxon’s rank-sum test (α=0.05) is used for experimental comparison where +, −, and = represent that the performance of the results obtained by competitors is better, worse, or similar.Based on the experimental results in terms of IGDX, we can find that Omni-optimizer and DN-NSGAII could not perform better than MMOEA-CAS on any case, showing the drawbacks of their selection mechanisms when solving those test problems. It can be concluded that the fast nondominated sorting approach used in Omni-optimizer and DN-NSGA-II failed to maintain the diversity in decision space, since it always intended to choose the solutions with better convergence and diversity in objective space. Thus, regarding the performance of final population obtained in decision space, the above two algorithms always obtain poor performance on all test problems because they neglect the importance of diversity in decision space. To address this issue, MMOEA-CAS used the density-based clustering method to divide clusters where the similar solutions are likely to be collected into the same cluster. At the same time, in the addition operator, the solutions with good performance in the same cluster even if it is worse in the whole population can be still seen as promising candidate solutions. This way, MMOEA-CAS can guarantee the diversity of population in decision space. This also explains why Omni-optimizer and DN-NSGA-II showed the advantages on MMOPs with multiple PSs (i.e., SYM-PART simple, SYM-PART rotated, Omni-test, MMF1, MMF5-6, and MMF8) when comparing the quality of population in objective space, while they showed poor performance on some MMOPs with local and global PSs (i.e., MMF10-13, MM15, and MMF15_a) in terms of IGDX. Due to the comprehensive consideration of the diversity in both decision and objective spaces, MMOEA-CAS achieves better performance on most MMOPs at the expense of diversity in objective space when solving some problems with multiple PSs.In order to improve the diversity in decision space, MO_Ring_PSO_SCD used the special crowding distance, while it still followed the principle of convergence first in objective space. The local Pareto optimal solutions are always lost during the evolutionary process of MO_Ring_PSO_SCD. Similarly, in TriMOEA-TA&R, nondominated solutions still replace dominated solutions in objective space, so it also failed to strike the balance between the diversity in decision and objective spaces. To avoid the local Pareto optimal solutions being replaced by the solutions with better convergence during the evolutionary process, the proposed addition and deletion operators in MMOEA-CAS collaboratively select more promising solution into next generation according to the information of clustering results classified by the density-based clustering method in decision space and the subregions divided by weight vectors in objective space. Therefore, only the solutions that are always performing worse in both two spaces are abandoned, and those solutions having good performance in either space could get to survive. Although MO_Ring_PSO_SCD and TriMOEA-TA&R performed better than MMOEA-CAS on some problems with multiple PSs, they still obtained poor performance when compared with MMOEA-CAS on MMOPs having global and local PSs. As shown in Tables3 and 4, when compared with MMOEA-CAS, it is obvious that MO_Ring_PSO_SCD and TriMOEA-TA&R achieved worse results on most MMOPs, especially on these MMOPs having global and local PSs. Thus, these compared results validate the effectiveness of MMOEA-CAS and it is able to gain solutions with better overall performance in decision space and objective space when compared to other MMOEAs on most MMOPs.


## 5.2. Further Discussion

To clearly demonstrate the performance of different MMOEAs, the final populations obtained in decision and objective spaces by different algorithms are plotted in Figures2–3, which qualitatively show the effectiveness and advantages of our proposed algorithm on solving these MMOPs. For example, a MMOP with multiple PSs, that is, SYM-PART rotated, is shown in Figure 2, and a MMOP with local PS, that is, MMF10, is shown in Figure 3, respectively. From Figure 2, it was found that the diversity of final population obtained by MMOEA-CAS is more uniform in decision space. Although Omnioptimizer and DN-NSGA-II found better solutions in objective space, they failed to maintain other PSs in decision space. Similarly, the population obtained by TriMOEA-TA&R also missed some PSs in decision space. MO_Ring_PSO_SCD found all PSs, but the final solutions cannot uniformly cover all the true PSs. Thus, we can conclude that MMOEA-CAS gets better results in terms of the comprehensive performance in both decision and objective spaces on SYM-PART rotated.Figure 2
The final populations obtained in decision and objective spaces on SYM-PART rotated.
(a)(b)(c)(d)(e)Figure 3
The final populations obtained in decision and objective spaces on MMF10.
(a)(b)(c)(d)(e)Furthermore, for MMF10, the final populations obtained are also shown in Figure3. It is obvious that the performance of final population obtained by MMOEA-CAS is significantly better than other MMOEAs. Other compared algorithms mainly pick solutions with faster convergence rates in objective space, which will cause some local optimal solutions always to be eliminated by the global optimal solutions. Thus, only MMOEA-CAS maintained some promising local optimal solutions. To summarize, MMOEA-CAS shows some superiorities on two cases, especially on MM10.


## 6. Conclusion

We have developed a novel evolutionary algorithm with clustering-based assisted selection strategy for multimodal multiobjective optimization, in which addition operator and deletion operator are proposed to comprehensively consider the diversity in both decision and objective spaces. Specifically, a density-based clustering method is used to divide population into multiple clusters in decision space, aiming to assist addition operator to strengthen diversity of population. Then, weight vectors are used to divide population intoN subregions in objective space (N is population size). Moreover, in deletion operator, the solutions in the most crowded subregion are collected into previous clusters, and then the worst solution in the most crowded cluster is deleted until there are N solutions left. The numerical values on both IGDX and IGDF have reported the effectiveness of MMOEA-CAS. Most existing MMOEAs cannot search for local Pareto optimal solutions because they are often dominated and replaced by global optimal solutions with good convergence, while our proposed algorithm is capable of preserving more uniformly and widely distributed solutions in decision space without deteriorating their distributions in objective space, which confirms its superiority on most of MMOPs.Finally, some more effective frameworks, enhanced search operators, and other techniques will be further studied and developed to fill in the gaps in the field of multimodal multiobjective optimization. In addition, we will further extend our proposed algorithm to solve other more complicated multimodal multiobjective optimization problems.



---

*Source: 4393818-2021-01-13.xml*