1 Introduction

Real-world problems usually involve multiple conflicting objectives, which are known as multiobjective optimization problems (MOPs) [1,2,3,4,5]. A minimization MOP with m objectives can be described as:

$$\begin{aligned} \begin{array}{ll} &{}\mathrm{minimize}~~~\mathbf{f} (\mathbf{x} ) = (f_1(\mathbf{x} ),f_2(\mathbf{x} ),\ldots ,f_m(\mathbf{x} )),\\ &{}\mathrm{subject}~\mathrm{to}~~~~\mathbf{x} \in \varOmega .\\ \end{array} \end{aligned}$$
(1)

where \(\varOmega \) is the decision space, \(\mathbf{x} \) = \((x_1,\ldots ,x_n) \in \varOmega \) is a candidate solution; \(\mathbf{f} : \varOmega \rightarrow R^m\) constitutes m real-value objective functions; \(R^m\) denotes the objective space. Usually there is no unique optimal solution which simultaneously optimizes all the m objective functions. Instead, there is a set of trade-off solutions called Pareto optimal solutions. The identification of the Pareto optimal solution is based on the Pareto dominance relationship. Given two solutions \(\mathbf{x} \) and \(\mathbf{y} \), \(\mathbf{x} \) is said to Pareto dominate \(\mathbf{y} \) (\(\mathbf{x} \succ \mathbf{y} \)) if \(f_i(\mathbf{x} )\le f_i(\mathbf{y} )\) for \(\forall ~ i\in \lbrace 1,\ldots ,m\rbrace \) and \(\exists ~ j\in \lbrace 1,\ldots ,m\rbrace \) satisfies \(f_j(\mathbf{x} )<f_j(\mathbf{y} )\). A solution is said to be the Pareto optimal solution if it cannot be dominated by any other solution. The set of all Pareto optimal solutions is called the Pareto set (PS), and the set of their corresponding objective vectors is called the Pareto front (PF).

The multimodal multiobjective optimization problem (MMOP) is a special kind of MOP whose PF corresponds to multiple PSs. That is, multiple Pareto optimal solutions are corresponding to the same objective vector [6,7,8]. These Pareto optimal solutions are equivalent to each other. In fact, the MMOP is often encountered in real-world applications, such as engine design [9,10,11], game map generation [12] and distillation plant layout [13]. For example, a product engineer is mainly interested in a solution set through covering the whole PSs since it can help to know if a certain design can be realized by different parameters setting of the production process.

Figure 1 illustrates an example of the MMOP problem. Two PSs, \(\mathrm{PS}_1\) and \(\mathrm{PS}_2\) in the decision space correspond to the same PF in the objective space. \(A_1\) and \(A_2\) are two equivalent Pareto optimal solutions corresponding to \(A^*\) in the objective space. B is an approximate solution corresponding to \(B^*\) in the objective space. Suppose that there are two solutions \(A_1\) and B in the current population, then B will be abandoned by general MOEAs since its objective vector \(B^*\) is too close to \(A^*\) and dominated by \(A^*\). In the multimodal multiobjective optimization scenario, the preservation of B may be helpful to find \(A_2\) or other Pareto optimal solutions on \(\mathrm{PS_2}\). Furthermore, it is also beneficial to improve the diversity of the whole solution set.

Fig. 1
figure 1

Illustration of MMOP

Full size image

In recent decades, various promising multiobjective evolutionary algorithms (MOEAs) [14,15,16,17,18,19] have been proposed. These algorithms can search for a well-converged solution set with great diversity in the objective space but do not consider the diversity in the decision space at all. Nevertheless, M. Preuss gave two conjectures in [20], in which one is that: diversity maintenance is not only needed in the objective space but also the decision space. To obtain a solution set with better diversity in the decision space when solving MMOPs, many algorithms have been proposed based on heuristic algorithms in recent years, including Omni-optimizer [21] and DN-NSGA-II [22]. But these algorithms still have some limitations. For example, too much attention is paid to the diversity of the solution set in the decision space but the performance in the objective space is neglected. A solution set with insufficient convergence is meaningless, even if its diversity is very good. The abilities that an algorithm needs for solving MMOPs were illustrated in [23]. Firstly, it can find solutions with good convergence. Then it should have the ability to find diverse solutions in the decision and objective spaces. How to make the solution set as diverse as possible and improve its convergence at the same time is a very significant issue.

This paper proposes an evolutionary optimization algorithm with decomposition in the decision space (EMO-DD) to solve MMOPs. In EMO-DD, a local optimization method is adopted within an evolutionary framework. This paper aims to explore the relationship of the solution set between its convergence and diversity in both the decision and objective spaces, and promote these two performances simultaneously.

Uniform reference vectors have an inherent property of reflecting great diversity. There are already a lot of MOEAs using predefined reference vectors to maintain the diversity of the solution set in the objective space. However, the advantage of reference vectors in diversity maintenance in the decision space is not utilized. Inspired by the great performance in the objective space, we attempt to utilize the property of uniform reference vectors in the decision space for solving MMOPs. In this paper, a well-distributed reference vector set is predefined in the decision space and decomposes it into several subregions. In each subregion, the solutions with excellent diversity in the decision space are retained.

Considering the maintenance of convergence and diversity in the decision space simultaneously, we attempt to quantify them into two different objectives and formulate them into a new bi-objective optimization problem. By optimizing this problem, well-converged solutions with good diversity in the decision space can be screened out. In each subregion, a special local optimization method is constructed, and the optimal solutions to the bi-objective problem are seemed as ones with good convergence and diversity in the decision space, and retained for the next generation evolution. It is well-known that the search ability of evolutionary algorithms can be improved by local optimization, which is one of the commonly used techniques in memetics. After maintaining the diversity of solution set in the decision space as much as possible, we select the solutions with better diversity in the objective space to achieve the balance between the two spaces.

The main contribution of this paper can be summarized as follows:

  1. 1.

    A decomposition method in the decision space is introduced to maintain the diversity of solution set in the decision space.

  2. 2.

    A bi-objective optimization problem is formulated to construct the relationship of solution set between its convergence and diversity.

  3. 3.

    A diversity archive and modified mating selection method are proposed to preserve and inherit solutions that perform better in both the decision and the objective space.

Systematic experiments are carried out on fifteen test problems. Compared with four other state-of-the-art multimodal multiobjective optimization algorithms, the experimental results show that the solution set obtained by EMO-DD has good diversity as well as great convergence.

The remainder of this paper is organized as below. Section 2 gives the related works on multimodal multiobjective optimization. Then the details of EMO-DD are described in Sect. 3. Section 4 presents the experimental study. Section 5 concludes this paper.

2 Related work

2.1 Prior works on multimodal multiobjective optimization

Most MOEAs paid attention to approximate the PF in the objective space rather than the diversity of PSs in the decision space. However, convergence and diversity maintenance in both the decision and objective spaces are very important for a good solution set. In recent years, a lot of works have been done on promoting the diversity of solutions in the decision space. Deb [21] proposed an algorithm called Omni-optimizer to solve MMOPs, in which the crowding distance in the decision space was used to maintain the diversity of solutions. Liang proposed an algorithm based on niching multiobjective optimization called DN-NSGA-II to locate the multiple PSs in the decision space. At the same time, two new multimodal multiobjective optimization problems called SS-UF1 and S-UF3 were proposed, which were the precursors of MMF [24]. Apart from these, many niching-based methods [25,26,27,28] have been proposed for solving MMOPs recently, such as fitness sharing [29] and crowding [30]. Lin [31] proposed an algorithm (MMOEA/DC) with dual clustering in the decision and objective spaces, in which both the global PSs and some good local PSs with acceptable quality were maintained. Liu et al. [32] proposed a general framework using two archives to guide the evolutionary search (TriMOEA-TA&R). The diversity archive simultaneously employed a clustering strategy to guarantee diversity in the objective space, and a niche-based clearing strategy to promote the same in the decision space. Xia [33] suggested a framework which included two crowding estimation methods, multiple selection methods for mating and search strategy for variation, to improve the MOEA’s searching ability and the diversity of its solutions. In [34], a niching sharing method was proposed for maintaining diversity in both the decision and objective spaces. However, these niching-based algorithms have potential problems. Firstly, they need extra niche parameters provided by decision-makers, and the value of these parameters has a great impact on the performance of algorithms. In addition, some niching-based algorithms even need extra fitness evaluations to maintain niche detection accuracy [35].

There are also many other MOEAs proposed for MMOPs in recent years. In [36], a new crossover method and two archives were adopted for maintaining the diversity of solution set in the objective and decision space. Liang et al. [37] proposed a new differential evolution optimization algorithm (MMODE) for MMOPs. A new decision-variable pre-selection mechanism and mutation-bound process were introduced for promoting the diversity of solutions. Tanabe and Ishibuchi [38] proposed a new decomposition-based MOEA, in which each decomposed subproblem can be assigned more than one solution to diversity.

In addition to the above studies, there are some researches on multimodal multiobjective optimization based on particle swarm optimization (PSO) [39,40,41,42]. PSO is a population-based optimization algorithm that simulating the swarm behaviour of insects and birds. These groups search for food in a cooperative way. Each member of the swarm changes its search mode by learning its own and other members’ experiences. To solve MMOPs, Yue proposed a multiobjective particle swarm optimizer using ring topology and special crowding distance (MO_Ring_PSO_SCD), in which the ring topology helps to induce stable niches to locate much more Pareto optimal solutions, and the special crowding distance considers the crowding distance in both the decision and objectives spaces to maintain multiple PSs. Qu proposed a self-organized speciation based multiobjective particle swarm optimizer [43] to locate multiple Pareto optimal solutions for solving MMOPs, in which the self-organized mechanism is used for improving the efficiency of the species formulation as well as the performance of the algorithm. Liang et al. [44] proposed a new multiobjective PSO with a self-organizing mechanism called SMPSO-MM, in which a self-organizing map network is used to find the diversity structure of the population and build the neighbourhood in the decision space. PSO algorithm is indeed a suitable choice to optimize the MMOPs. But the particles in PSO share information through the current search to the best, and the whole search and update process is following the current optimal solution. So it is a single sharing mechanism to a large extent, which may fall into local optimum.

2.2 Decomposition of multiobjective optimization

The idea of decomposition has been used in many methods for solving MOPs [45,46,47], in which the most representative are MOEA/D [48] and NSGA-III [49]. By specifying a set of reference vectors in the objective space, MOEA/D decomposes the MOP into several single-objective optimization subproblems and solves them in a collaborative manner. At each generation, the population is composed of the best solutions to each subproblem. Many scalar aggregation functions can be used as decomposition methods for converting MOPs into several scalar optimization problems. Weighted Sum Approach, Tchebycheff Approach (TCH) [50], and Boundary Intersection Approach are three representatives used in MOEAs with decomposition. In this paper, we use the TCH approach for decomposing a MOP if necessary. The TCH is formed as:

$$\begin{aligned}&\mathrm{minimize} ~~ g^{tch}(\mathbf{x} \vert \mathbf{w} ,\mathbf{z} ^*)={\mathop {\mathrm{max}}\limits _{1\le i\le m}}\lbrace \omega _i \vert f_i(\mathbf{x} )-z_i^*\vert \rbrace , \nonumber \\&\mathrm{subject}~\mathrm{to}~~\mathbf{x} \in \varOmega . \end{aligned}$$
(2)

where \(\mathbf{z} ^{*}=(z_1^*,\ldots ,z_m^*)\) is the reference point. \(\mathbf{w} =(\omega _1,\ldots ,\omega _m)\) is a reference vector in the objective space, \(\omega _i\ge \) 0 for \(\forall ~i \in \lbrace 1,\ldots ,m\rbrace \) and \(\sum _{i=1}^m\omega _i= 1\).

The above approaches all have the ability to decompose the approximation of the PF into several scalar optimization problems. Based on a large number of predefined evenly distributed reference vectors, solutions are guided to converge to the scaler problem corresponding to its bounded reference vector. All optimized scalar problem solutions can compose into a well-distributed set. This decomposition method does have great performance both on convergence and diversity in the objective space, while the diversity of solution set in the decision space is rarely considered. This makes it possible that the obtained solutions are only a local set but cannot represent the whole PSs.

3 Proposed algorithm

In this section, we present the details of our proposed algorithm, EMO-DD. It is composed of four main components: the decision subregion allocation, the update mechanism of the diversity archive, the environmental selection, and the mating selection. The details are shown in the following subsections.

Fig. 2
figure 2

Flowchart of EMO-DD

Full size image

3.1 General framework

To maintain the diversity of solutions in the decision space, we borrow the idea from decomposition-based MOEAs to divide the decision space into several subregions and optimize the solutions in different subregions collaboratively. To make sure the solutions with good convergence and diversity can be preserved and inherited, we propose a new diversity archive to store them, and use a modified mating selection method to select parents from them.

The overall flowchart of EMO-DD is presented in Fig. 2. The EMO-DD starts with an initial parent population P and diversity archive DA. Then the offspring population is reproduced by P and DA while the stopping criterion is not met. After the offspring population reproduction, all solutions are allocated into different decision subregions (Sect. 3.2), and both DA and P are updated based on it (Sects. 3.3 and 3.4). The population P will be reported in the last generation.

3.2 Decision subregion allocation

Before the decision subregion allocation, we need to normalize each solution \(\mathbf{x} \) to make sure it has reached the requirement to be assigned subregion. Normalization can eliminate the effects of different ranges or scales. The normalized solution \(\hat{\mathbf{x }}=(\hat{x}_1,\ldots ,\hat{x}_n)\) is defined as:

$$\begin{aligned} \hat{x}_i = \frac{x_i - l_i + \varphi }{u_i - l_i + \varphi },~i\in \lbrace ,2,\ldots , n\rbrace . \end{aligned}$$
(3)

where \(l_i\) and \(u_i\) are respectively the minimum and maximum values of the i-th variable among all solutions. To meet the case where \(l_i\) = \(u_i\), a minimal positive number \(\varphi \) is used here. In this paper, we set it to \(10^{-5}\). After normalization, \(\hat{\mathbf{x }}\) is in \((0,1]^n\).

To allocate each solution into different decision subregions, we use N well-distributed reference vectors WX = \(\lbrace \mathbf{wx} ^1,\ldots , \mathbf{wx} ^N\rbrace \) on the canonical simplex to divide the decision space into N subregions. The reference vectors can be generated by the same method used in decomposition-based MOEAs, i.e., the two-layer weight vector generation method [51]. Specifically, for each reference vector \(\mathbf{wx} ^i\), we assign it a subregion \(\varDelta ^i\) in decision space as follows:

$$\begin{aligned} \varDelta ^i = \lbrace \mathbf{x} \in \varOmega | \langle \hat{\mathbf{x }},\mathbf{wx} ^i \rangle \le \langle \hat{\mathbf{x }},\mathbf{wx} ^j \rangle \rbrace ,~j\in \lbrace 1,\ldots , N\rbrace \end{aligned}$$
(4)

where \(\langle \hat{\mathbf{x }},\mathbf{wx} \rangle \) is the acute angle between \(\hat{\mathbf{x }}\) and \(\mathbf{wx} \). By using this definition, each solution \(\mathbf{x} \) of a population can easily be resided in its unique subregion \(\varDelta ^k\), whose index k is defined as:

$$\begin{aligned} k = {\mathop {\mathrm{argmin}}\limits _{i\in \lbrace 1,\ldots , N\rbrace }}\langle \hat{\mathbf{x }},\mathbf{wx} ^i \rangle \end{aligned}$$
(5)

The pseudo-code of decision subregion allocation mechanism is given in Algorithm 1.

figure a

3.3 Update mechanism of the DA

To keep solutions with good diversity in the decision space when searching for the Pareto optimal solutions in MMOPs, we introduce a temporary diversity archive DA. The DA aims at preserving solutions as much convergent and diversified as possible in the decision space. Algorithm 2 is the pseudo-code of the update mechanism of the DA. After the reproduction mechanism, the offspring population Q is incorporated into the diversity archive DA. Then solutions in DA reside in the corresponding decision subregions (line 2). For each subregion \(\varDelta _i\), the best solution is chosen into a temporary archive S and deleted from it if it is not empty (lines 3–8). In this process, the idea of MOEA/D is adopted to decompose the objective space and TCH function is used as the indicator of each candidate solution. Solution with minimum TCH value is chosen as the best one in each subregion. Note that any other scalarizing functions or fitness assignment can also be adopted as the indicator, i.e., the BPI approach used in [48] or fitness assignment used in [52].

figure b

After the above selection operation, if the size of S is less than N, then a new bi-objective optimization problem is formulated as follows:

$$\begin{aligned} \mathrm{minimize}~~ \mathbf{g} (\mathbf{x} ) = (g_1(\mathbf{x} ),g_2(\mathbf{x} )), \end{aligned}$$

where

$$\begin{aligned}&\left\{ \begin{array}{ll} g_1(\mathbf{x} )=1/ \big ( {\mathop {\mathrm{argmin}}\limits _\mathbf{y \in \varDelta ^i,\mathbf{y} \ne \mathbf{x} }}||\mathbf{x} -\mathbf{y} ||\big ) \\ g_2(\mathbf{x} ) = g^{tch}(\mathbf{x} \vert \varvec{\lambda },\mathbf{z} ^*) \end{array} \right. \nonumber \\&\mathbf{x} \in \varDelta ^i,i = \lbrace 1,\ldots ,N\rbrace . \end{aligned}$$
(6)

In Eq. (6), \(g_1(\mathbf{x} )\) quantifies the distribution density of solution \(\mathbf{x} \) in the decision space, and \(g_2(\mathbf{x} )\) reflects its convergence degree. The optimal solutions to this bi-objective problem represent the most decentralized and best convergent ones. We do not mention the diversity of solution set in the objective space here does not mean it is unimportant. A solution set, which is widely distributed in the decision space and reflects the whole PSs, will not have a bad diversity in the objective space. In other words, the optimal solutions to Eq. (6) are also widely distributed in the objective space to a certain extent.

Same as the best solution selection indicator mentioned above, \(g_2(\mathbf{x} )\) can also be defined in more than one way. Based on Eq. (6), all solutions in each subregion are reformulated (lines 10–15). Then the non-dominated sorting is used to divide all solutions into several fronts (line 16). Starting from the first front, non-dominated solutions are chosen into S front by front until \(|S| \ge N\) (lines 17–20). Then exceeded solutions in S are abandoned. In this paper, we choose solutions with the largest \(g_2(\mathbf{x} )\) as the worst ones and delete them from S (lines 21–24). Finally, DA is updated by assigning S to it.

3.4 Environmental selection

After the update mechanism of diversity archive DA, we choose solutions with great diversity in the objective space as well as good convergence from the offspring population Q and DA. Figure 3 gives an illustration diagram about the environmental selection procedure. Firstly, a combined population of size 2N is formed based on DA and Q. Then we use the non-dominated sorting and crowding distance sorting procedure to select N best solutions into the next generation population P. Algorithm 3 gives the pseudo-code of the environmental selection procedure.

Fig. 3
figure 3

Environmental selection

Full size image
figure c

3.5 Mating selection

Mating selection plays an important role in the offspring reproduction process. It is usually implemented by selecting promising solutions from the current population to form a mating pool [53]. In this paper, we adopt the mating selection method derived from Li et al. [54] by selecting parents from both the diversity archive DA and the current population P. Algorithm 4 is the pseudo-code of mating selection procedure. Firstly, the proportions of non-dominated solutions in the DA (\(\rho _{da}\)) and P (\(\rho _p\)) are evaluated (lines 1 to 2). \(\rho _{da}>\rho _p\) means the convergence of DA is better than P, then the first parent \(\mathbf{p} _1\) is randomly selected from DA; Otherwise it is selected from P (lines 3 to 7). The selection of the second parent \(\mathbf{p} _2\) depends on \(\rho _{da}\). A random decimal between 0 and 1 is generated, and \(\mathbf{p} _2\) comes from DA if \(\rho _{da}\) is larger than it; or \(\mathbf{p} _2\) is selected from P (lines 8 to 12). By this mating selection, solutions with good diversity in DA can have a greater probability to be inherited without neglecting the convergence.

figure d

4 Experimental study

In this section, contrast experiments are conducted to investigate the performance of the proposed algorithm. At first, test benchmark problems are given. Then the pros and cons of the three metrics used in the experiments are illustrated. Comparative experimental results and analyses are given in the last subsection.

Table 1 Characteristics of fifteen multimodal multiobjective test problems
Full size table

4.1 Test problems

In this paper, we used the following fifteen multimodal multiobjective test problems to test the performance of our proposed algorithm including eight MMF problems (MMF1-8), four IDMP problems [55], two SYM-PART problems [56] and two-objective Omni-test problem [21]. Table 1 shows their different geometric characteristics, including the number of decision variables, objectives, and PSs. Among these test problems, MMF suit is simpler than others. It is worth noting that the PSs of MMF3 and MMF6 are overlapped in every dimension. The difficulty of Omni-test stems from its large number of PSs. SYM-PART-rotated is a variant of SYM-PART-simple by simply rotating all the PSs. Rather than others, the complexity of finding equivalent PSs are different on IDMP test problems. So it is hard for those convergence-first MOEAs to find all PSs on IDMP.

4.2 Performance metrics

HV [57] and IGD [58] are two main metrics used in MOEAs since they can reflect the diversity and convergence of the obtained solution set in the objective space simultaneously. But they do not apply to multimodal multiobjective problems because they evaluate the performance of algorithms that focuses on the objective space while the decision space is ignored [59].

IGDX [60] is a variant of IGD, and it represents the average Euclidean distance between the obtained solutions and Pareto optimal solutions in the decision space. By measuring this distance, IGDX can evaluate both the convergence and the diversity in the decision space of the approximate solution set.

However, it is worth noting that the other one of the two conjectures [20] mentioned in Sect. 1 is: there are situations where the PS does not share the aspired nice properties of the received PF the user normally pay the attention to. This means a solution set well-performed in the decision space does not imply a well-performance in the objective space. According to the example given in [23], a solution set uniformly distributed on all may correspond to a few objective vectors. This example gave us a hint, that a solution set with very bad diversity in the objective space may still get a great IGDX value. So IGDX is not an applicable metric used alone in multimodal multiobjective optimization.

Recently, Liu et al. [32] proposed a new metric for multimodal multiobjective optimization called IGDM. IGDM is a metric that integrating IGD and IDX, and considering performance not only in the objective space but also in the decision space. The smaller the IGDM value is, the more diverse and convergent the solution set performs in both the objective and decision spaces. This implies that IGDM is a comprehensive performance metric, which reflects the global performance in the two spaces by a numerical value. Per contra, IGDM cannot explain the specific quality of the solution set in any single space. In order to explore the specific performance of the algorithms in dealing with MMOPs, we use IGD, IGDX and IGDM metrics for assessing the performance, respectively.

Considering \(F^*=\lbrace \mathbf{f} _1^*,\ldots ,\mathbf{f} _q^*\rbrace \) is a set of well distributed reference points on the true PF, where q is the number of these points. Then the corresponded set of Pareto optimal solutions is \(X^*=\lbrace \mathbf{x} _{1,1}^*,\mathbf{x} _{1,2}^*,\ldots ,\mathbf{x} _{1,a_1}^*,\mathbf{x} _{2,1}^*,\ldots ,\mathbf{x} _{q,a_q}^*\rbrace \), where \(a_i,i=1,2,\ldots ,q\) is the number of Pareto optimal solutions to each point in \(F^*\). For an approximate solution set \(P=\lbrace \mathbf{x} _1, \mathbf{x} _2,\ldots ,\mathbf{x} _N\rbrace \) obtained by an optimization algorithm, the IGD is defined as:

$$\begin{aligned} \mathrm{IGD}(P,F^*)=\frac{1}{\vert F^*\vert }\left\{ \sum \limits _\mathbf{f ^*\in F^*}{\mathop {\mathrm{min}}\limits _\mathbf{x \in P}}( ed_f(\mathbf{f} (\mathbf{x} ),\mathbf{f} ^*))\right\} , \end{aligned}$$
(7)

where \(ed_f(\mathbf{f} (\mathbf{x} ),\mathbf{f} ^*)\) is the Euclidean distance between \(\mathbf{f} (\mathbf{x} )\) and \(\mathbf{f} ^*\) in the objective space.

The IGDX is defined as:

$$\begin{aligned} \mathrm{IGDX}(P,X^*)=\frac{1}{\vert X^*\vert }\left\{ \sum \limits _\mathbf{x ^*\in X^*}{\mathop {\mathrm{min}}\limits _\mathbf{x \in P}}( ed_x(\mathbf{x} ,\mathbf{x} ^*))\right\} , \end{aligned}$$
(8)

where \(ed_x(\mathbf{x} ,\mathbf{x} ^*)\) is the Euclidean distance between \(\mathbf{x} \) and \(\mathbf{x} ^*\) in the decision space.

The IGDM is defined as:

$$\begin{aligned} \mathrm{IGDM}(P,F^*,X^*)=\frac{1}{\vert X^*\vert }\left\{ \sum _\mathbf{f _i^*\in F^*}\sum _{j=1,\ldots ,a_i}d(\mathbf{f} _i^*,\mathbf{x} _{i,j}^*,P)\right\} , \end{aligned}$$
(9)

where

$$\begin{aligned} d(\mathbf{f} _i^*,\mathbf{x} _{i,j}^*,P)&= \left\{ \begin{array}{ll} d_{max}, ~~~\hbox {if } P_{i,j}=\emptyset ,\\ \mathrm{min}\lbrace d_{max},ed(\mathbf{f} _i^*,P_{i,j})\rbrace ,~~~\hbox {if } P_{i,j}\ne \emptyset ; \end{array} \right. \nonumber \\ P_{i,j}=\lbrace \mathbf{x} _k: j&= {\mathop {\mathrm{argmin}}\limits _{l=1,\ldots ,a_i}}ed_x(\mathbf{x} _{i,l}^*,\mathbf{x} _k),\mathbf{x} _k\in P\rbrace . \end{aligned}$$
(10)

The \(ed(\mathbf{f} _i^*,P_{i,j})\) in Eq. (10) is the minimal Euclidean distance between \(\mathbf{f} _i^*\) and \(P_{i,j}\). \(d_{max}\) is a parameter defined by the user, and is set to 1 in this paper.

4.3 Comparison results with other algorithms

To demonstrate the effectiveness of EMO-DD, four state-of-the-art multimodal multiobjective optimization algorithms are chosen as comparative algorithms: Omni-optimizer [21], DN-NSGA-II, MO_Ring_PSO_SCD, and TriMOEA-TA&R [32]. In addition, MOEA/D-TCH is adopted for comparing their performance in the objective space. Simulated binary crossover [61] and polynomial mutation [62] operators are used (except in MO_Ring_PSO_SCD) with a distribution index of 20. The crossover probability is 1.0, and the mutation probability is 0.2. The generation of each run is set to 100, and the population size is set to 800. The crowding factor in DN-NSGA-II is set to half of the population size according to [22]. In TriMOEA-TA&R, \(p_{con}\), \(\sigma _{niche}\) and \(\epsilon _{peak}\) are 0, 0.5 and 0.01, respectively. For each test problem, 30 independent runs are implemented on PlatEMO [63] with Matlab code. The experimental results of IGD, IGDX and IGDM are shown in Table 2, 3 and 4, respectively, where the best mean and standard deviation are highlighted in bold and the second best are colored in italic.

Table 2 shows that all IGD results obtained by EMO-DD are highlighted in bold and italic. Other algorithms except MOEA/D-TCH have significantly worse IGD results than EMO-DD. This means that the solution sets obtained by EMO-DD are more convergent and diverse in the objective space than other compared multimodal multiobjective optimization algorithms. Comparing with MOEA/D-TCH, we can see EMO-DD is not worse in convergence, even better on some problems. The evaluations of IGD are not very ideal for the remaining four algorithms, extremely on Omni-optimizer, DN-NSGA-II and MO_Ring_PSO_SCD.

Table 3 shows that EMO-DD and MO_Ring_PSO_SCD are the top two algorithms on the IGDX metric. Most of the IGDX values obtained by these two algorithms are highlighted in bold and italic, in which MO_Ring_PSO_SCD prefers MMF and EMO-DD prefers others. The other three multimodal multiobjective optimization algorithms perform similarly, though TriMOEA-TA&R gets the best IGDX values on two problems.

Table 4 shows that more than half of the IGDM results (11/15) obtained by EMO-DD are highlighted in bold, and the others are in italic (except on MMF3), which means that the solution sets searched by EMO-DD can have good performance in both the decision and objective spaces. The second best is TriMOEA-TA&R, on which most of the IGDM results are highlighted except IDMP. The third one, MO_Ring_PSO_SCD, also gets good IGDM values on several problems, especially on IDMP.

Table 2 Comparison results on IGD metric (mean and standard deviation)
Full size table
Table 3 Comparison results on IGDX metric (mean and standard deviation)
Full size table
Table 4 Comparison results on IGDM metric (mean and standard deviation)
Full size table

To further analyze the results mentioned above, the rank frequency distribution [64] is used for reorganizing the results of the three performance metrics. Tables 5, 6 and 7 are the rank frequencies for the IGD, IGDX and IGDM cases, respectively. The number in Rank i (i = 1,2, \(\ldots \) ,m) under an algorithm indicates the times of the algorithm’s performance ranked as i, where Rank 1 represents the best one, Rank 2 the second and so on. The rank score shown on the last row is calculated by formula \(\sum _{i=1}^5\big ( i\cdot (Rank~ i)\big )\), which is an overall evaluation of the algorithms’ performance. In general, a lower rank score represents a better performance the algorithm has.

Table 5 Rank frequency distribution analysis on IGD case
Full size table
Table 6 Rank frequency distribution analysis on IGDX case
Full size table
Table 7 Rank frequency distribution analysis on IGDM case
Full size table
Fig. 4
figure 4

Obtained solution set and corresponded objective vectors on MMF6

Full size image
Fig. 5
figure 5

Obtained solution set and corresponded objective vectors on two-objective Omni-test

Full size image
Fig. 6
figure 6

Obtained solution set on SYM-PART-rotated

Full size image
Fig. 7
figure 7

Obtained solution set on IDMP-T3

Full size image

We synthesize the rank information of the three tables. In Table 5, MO_Ring_PSO_SCD gets a much larger IGD rank score than others. Then in Table 6, the lowest IGDX rank score is marked under MO_Ring_PSO_SCD, and the gap between others is very obvious except EMO-DD. These mark scores indicate that the solution set obtained by MO_Ring_PSO_SCD has a great performance in the decision space but not the objective space. By contrast, MOEA/D-TCH gets a very low IGD rank score but the highest IGDX rank score. This indicates that MOEA/D-TCH is good at finding solutions with good performance in the objective space while ignoring the decision space. The IGD and IGDX rank scores obtained by the remaining four algorithms are not polarized like MOEA/D-TCH or MO_Ring_PSO_SCD. Two of the most noteworthy are TriMOEA-TA&R and EMO-DD. The former gets not bad rank scores on both IGD and IGDX cases but is not much better when compared with the latter. From the rank frequency distribution analysis, we can see EMO-DD has the ability to find a solution set with good performance in both the decision and objective spaces.

In summary, from the above analysis, we can conclude that MO_Ring_PSO_S CD improves its diversity in the decision space at the cost of greatly sacrificing the convergence. Such a big sacrifice may not be desirable since ensuring the Pareto optimality of solutions is the primary aim of solving MMOPs. TriMOEA-TA&R has considered improving the performance in both the decision and the objective space. But when comparing it with EMO-DD, we can find that it does not enough. EMO-DD can get a solution set with better performance in the two spaces than TriMOEA-TA&R simultaneously. This gives us some enlightenment, that the performance improvement in the objective and decision spaces may not be completely conflicting when solving MOPs. Table 7 also verifies our thought by numerical analysis. MO_Ring_PSO_SCD and TriMOEA-TA&R do have good IGDM rank scores, but they are not better than EMO-DD.

To demonstrate the performance of these algorithms in both the decision and objective spaces further, the obtained solution sets and the corresponding objective vector fronts onto MMF6 (Fig. 4) and Omni-test (Fig. 5) are taken as examples for analysis, where the blue asterisks are well-distributed reference points extracted from PSs (the upper layer) and PF (the lower layer), and the red circles are obtained solutions (the upper layer) and the corresponding objective vectors (the lower layer), respectively.

In Fig. 4, the solutions obtained by MO_Ring_PSO_SCD almost cover the whole PSs. The solution sets obtained by the other four multimodal multiobjective optimization algorithms also can distribute to all parts of the PSs, although they are not as diverse as MO_Ring_PSO_SCD’s. But when turn to the objective space, the other four algorithms all converge to the PF well, while some solutions searched by MO_Ring_PSO_SCD are even far away from it. It is worth noting that MOEA/D-TCH is even unable to find complete PS. That is the reason why it gets a very bad value on IGDX metric.

Omni-test is a tough problem that has 27 PSs. In Fig. 5, Omni-optimizer and DN-NSGA-II even cannot search out all the PSs. That means these two algorithms are not suitable once the problem becomes complex. The solutions found by MOEA/D-TCH are not even on the PSs, which indicates all the solutions are not Pareto but local optimal solutions. However, the rest three algorithms can find the locations of all PSs, although the distribution of solutions on each PS part is different.

Figure 6 is presented for exploring the performance of the three algorithms, EMO-DD, MO_Ring_PSO_SCD and TriMOEA-TA&R, in dealing with multi-PS MMOPs. On the SYM-PART-rotated problem, Omni-optimizer and DN-NSGA-II cannot find the center part PS while the other three algorithms all fit the shape of the whole PSs. Not surprisingly, the diversity of solution set obtained by MO_Ring_PSO_SCD is the best. As for TriMOEA-TA&R, the proportion of solutions located on different PS part is various. Some PS parts are completely covered but some may only spot with several solutions. When turning to EMO-DD, it almost balances the coverage ratio of solutions on different PS part, although is not as good as MO_Ring_PSO_SCD.

IDMP represents a type of MMOPs with different search difficulty on each PS part. Figure 7 shows the solution set results on IDMP-T3, whose PSs consist of two parts and the upper right part (marked as EPS1) is more difficult to find than the bottom left one (marked as EPS2). It can be seen in Fig. 7 that all solutions found by MOEA/D-TCH are on EPS1. This is because MOEA/D-TCH blindly emphasizes the performance in the objective space, and discards all solutions on EPS2 after searched for EPS1. On the contrary, Omni-optimizer, DN-NSGA-II and MO_Ring_PSO_SCD are cheated by EPS1, though they can find EPS2. TriMOEA-TA&R can find the location of EPS1, but diversity is not satisfactory. Only EMO-DD finds both EPS1 and EPS2, and give them equal distribution. This shows that EMO-DD is better than others to jump local optimum and deal with this kind of deceptive problem.

5 Conclusion

In this paper, we have proposed an algorithm (EMO-DD) by using the decomposition method in the decision space to solve MMOPs. The whole population is decomposed and resided into several decision subregions and optimized collaboratively. In each subregion, solutions with good convergence and diversity in the decision space are screened out by optimizing a bi-objective problem. The two objectives of the problem reflect the convergence degree and distribution density of solutions, respectively. To ensure the well-performed solutions are preserved and inherited, a diversity archive and modified mating selection are proposed. The performance of EMO-DD has been analyzed and investigated through a series of comparative experiments with five state-of-the-art algorithms on fifteen problems. The experimental results show that EMO-DD has the ability to find diverse solutions with great convergence.