1 Introduction

Many real-world problems contain multiple objectives that should be optimized simultaneously. Problems that have more than one objective are called multi-objective optimization problems (MOOPs) or many-objective optimization problems (MaOPs) in case of more than three objectives [1,2,3]. Because of the nature of MOOPs, there is usually no single optimal solution [4,5,6]. Published studies of multi-objective optimization describe the development of Evolutionary Multi-Objective Optimization (EMO) algorithms that can solve two- or three-objective problems efficiently [4, 7,8,9,10].

Multi-objective optimization is considered to be an essential research topic in operations research [11] since most real-world problems are multi-objective in nature. However, many questions in this area have yet to be addressed and therefore more, and more researchers and practitioners are attracted to this area. The majority of the published studies of MOOPs were focused on solution algorithms.

There are two main categories of algorithms for addressing MOOPs, including population-based search algorithms and iterative point-wise search algorithms [12]. Although solving a MOOP using exact algorithms such as cutting-plane [13], polynomial-time approximation scheme [14], branch and bound [15, 16], and branch and cut [17] has been attempted, most MOOP methods are heuristics and meta-heuristics. For example, evolutionary computation [18,19,20,21], Pareto ant colony optimization [22], decomposition methods based on Lagrangian relaxation [23], diversity maximization approach [24], and zigzag search [12] have been employed for addressing MOOPs.

Some meta-heuristic algorithms are well-suited for solving global optimization problems such as non-convex and discontinuous problems [25,26,27]. Mete and Zabinsky [20] proposed a population-based algorithm to optimize MOOPs. They improved exploration of the solution space by employing Markov kernels, hit-and-run, and pattern hit-and-run. Pareto ordering rules were used to select the population and update the Pareto solutions. Random search algorithms efficiently optimize single ill-structured functions [28, 29] and multi-objective problems [8]. Many continuous and discrete MOOPs were addressed by population-based algorithms such as evolutionary algorithms [7, 8]. These approaches are well-suited to MOOPs because they generate a set of solutions in a single iteration.

Moreover, multi-objective evolutionary algorithms (MOEAs) can find a set of well-converged and diversified non-dominated solutions, known as Pareto solutions, in a short time and a single run because these algorithms have better performance in dealing with of some multi-objective optimization problems (such as huge search space, uncertainty, noise, disjoint Pareto curves) [7, 30, 31].

The early MOEAs based on Pareto ranking perform poorly in cases of more than three objectives. In recent years, the research emphasis has been placed upon improving the MOEAs to enable them to efficiently solve many-objective optimization problems [32]. There are some Limitation of MOEAs such as search capacity, and computational efficiency and difficulty visualizing the Pareto solutions.

Collectively, many-objective and multi-objective optimization problems have the same structure except for many-objective optimization problems with four or more objectives that require simultaneous optimization. However, increased numbers of objectives causes some difficulties, for example, most solutions become non-dominated, and distance metrics become less discriminatory. Therefore, scholars have recently focused on developing evolutionary algorithms that can handle many-objective problems.

Figures 1 and 2 present the distribution of documents and citations found in the Web of Science database based on the keywords “many-objective optimization” between 1974 and August 2018 (192 documents have been found in total). As it is clear from Figs. 1 and 2, since the year 2000 the researchers have focused seriously on this topic.

Fig. 1
figure 1

Distribution of documents by year (many-objective optimization)

Full size image
Fig. 2
figure 2

Distribution of citations by year (many-objective optimization)

Full size image

Here, we categorize eighteen MaOEAs based on some studies and apply them on three combinatorial optimization problems including MOKP, MOTSP, and mQAP with 3, 5, and 10 objectives. Meanwhile, the MOEAs are classified according to the characteristics (Dominance-based, Dominance and reference-based, Decomposition-based, Indicator-based, Preference-based). Moreover, the best classification of the algorithm for solving the problems is introduced according to the results.

This paper is organized as follows: Sect. 2 describes the research methodology; Sect. 3 contains empirical evaluations of the many-objective evolutionary algorithms using the MOKP, the MOTSP, and the mQAP; conclusions and future work are presented in Sect. 4.

2 Methodology

2.1 Methodology Framework

We compare MOEA methods and select the best algorithm relative to traditional approaches for solving three general multi-objective problems: MOKP, MOTSP, and mQAP. First, each algorithm was run on several instances of the problems. The number of objective functions and variables were two key factors of each problem. Additionally, two well-known quality performance evaluation metrics (inverted generational distance (IGD), and computational time (CT)) were used to assess the performance of the MOEAs.

2.2 Multi-objective Problems

MOKP: the many-objective D-item knapsack problem was developed by Ishibuchi, Akedo [33] according to the following mathematical program [33]:

$$ Maxf\left( x \right) = \left( {f_{1} \left( x \right),f_{2} \left( x \right), \ldots , f_{M} \left( x \right)} \right) $$
(1)
$$ s.t. \mathop \sum \limits_{j = 1}^{D} b_{ij} x_{j} \le c_{i} ,\quad i = 1,2, \ldots ,M $$
(2)
$$ x_{j} \in \left\{ {0,1} \right\},\quad j = 1,2, \ldots ,D $$
(3)

where

$$ f_{i} \left( x \right) = \mathop \sum \limits_{j = 1}^{D} a_{ij} x_{j} ,\quad i = 1,2, \ldots ,M $$
(4)

where x is a D-dimensional binary vector, bij represents the weight of item j inside knapsack i, aij is the profit of item j inside knapsack i, and ci is the capacity of knapsack i.

MOTSP: a many-objective traveling salesman problem [34] includes finding a tour to minimize the costs, as follows:

$$ Minz_{k} \left( \rho \right) = \mathop \sum \limits_{i = 1}^{D - 1} c_{{\rho \left( i \right),\rho \left( {i + 1} \right)}}^{k} + c_{\rho \left( D \right),\rho \left( 1 \right)}^{k} ,\quad k = 1,2, \ldots ,M $$
(5)

where D denotes the number of cities visited, the cost k for traveling from city i to city j is denoted by \( c_{i,j}^{k} \), and \( \rho \) is the cyclic permutation of cities. In this problem, a tour is defined by the cyclic permutation \( \rho \) of D cities. Additionally, there are M costs associated with traveling between two cities. M objectives are defined according to M costs.

mQAP: a many-objective quadratic assignment problem was developed by Knowles and Corne [35] as follows:

$$ Minc^{o} \left( \pi \right) = \mathop \sum \limits_{i = 1}^{D} \mathop \sum \limits_{j = 1}^{D} a_{ij} b_{{\pi_{i} \pi_{j} }}^{o} , o = 1,2, \ldots ,M $$
(6)

where D represents the number of facilities and aij is defined by an N × N matrix that is related to the distance between locations i and j. Additionally, matrix \( B = \left( {B^{1} , \ldots , B^{M} } \right) \) is represented for an mQAP with M flows where \( B^{o} = \left( {b_{ij}^{o} } \right) \) and the k-th flow matrix from facility i to j is denoted by \( b_{ij}^{o} \).Also, \( \pi \) is the permutation of D facilities, \( \pi_{i} \) is the i-th element of \( \pi \), and \( c^{o} \) represents an objective function \( o \in \left\{ {1,2, \ldots ,M} \right\} \).

2.3 Description of Applied MOEAs

Comparative research was implemented by using eighteen state-of-the-art MOEAs in the experiment. These approaches are described below:

  • HypE: Hypervolume-based estimation algorithm [36].This is a fast search algorithm that employs Monte Carlo simulation to approximate the exact hyper-volume values. This method makes a trade-off between the accuracy of the estimates and the available computing resources.

  • PICEA-g: Preference-inspired co-evolutionary algorithm with goals [37]. In this algorithm, a population of candidate solutions and preference sets with a fixed size, N and NGoal as parameters are evolved for a fixed number of generations, termed Maxgen. In each generation, parents are subjected to (representation appropriate) genetic variation operators to produce offspring. Simultaneously, NGoal new preference sets are randomly regenerated based on the initial bounds.

  • GrEA: Grid-based evolutionary algorithm [38]. In this algorithm, the potential of the grid-based approach is exploited to strengthen the selection pressure toward the optimal direction while an extensive and uniform distribution is maintained among solutions. Two key concepts were introduced by the authors to determine the mutual relationship of individuals in a grid structure: (i) grid dominance and (ii) grid difference. In contrast, three grid-based metrics were applied into the fitness of individuals to distinguish them in mating and in the environmental selection process: (i) grid ranking, (ii) grid crowding distance, and (iii) grid coordinate point distance.

  • NSGA-III: Non-dominated sorting genetic algorithm III [39].The authors used a few novel approaches and a number of viable directions to develop a potential EMO algorithm for addressing many-objective optimization problems. The authors proposed a reference-point-based many-objective evolutionary algorithm, termed NSGA-II.

  • A-NSGA-III: Adaptive NSGA-III [40].The authors extended NSGA-III to address generic constrained many-objective optimization problems. The authors also suggested three types of constrained test problems that are scalable to any number of objectives and so, several kinds of challenges were provided to a many-objective optimizer by using these test problems.

  • SPEA2 + SDE:SPEA2 with shift-based density estimation [41].The authors focused on modifying the diversity maintenance mechanism in the algorithm and proposed a shift-based density estimation (SDE) strategy.

  • BiGE: Bi-goal evolution [42]. This algorithm converts a many-objective optimization problem into a bi-goal (objective) optimization problem regarding proximity and diversity requirements. This algorithm applies the Pareto dominance relation in the bi-objective domain.

  • EFR-RR: Ensemble fitness ranking with ranking restriction [43].The authors proposed an algorithm that explicitly maintains the desired diversity of solutions in their evolutionary process by exploiting the perpendicular distance from the solution to the weight vector in the objective space, which achieves a better balance between convergence and diversity in many-objective optimization.

  • I-DBEA: Improved decomposition based evolutionary algorithm [44].The authors introduced a decomposition based evolutionary algorithm in which uniformly distributed reference points are generated via systematic sampling, the balance between convergence and diversity is maintained using two independent distance measures, and a simple preemptive distance comparison scheme is used for association.

  • KnEA: Knee point driven evolutionary algorithm [45]. In this algorithm, the authors proposed a strategy in which knee points are preferred among non-dominated solutions, assuming that no explicit user preferences are given. The authors discussed that bias towards the knee points in the non-dominated solutions in the current population is an approximation of a bias towards a large hyper-volume. No additional diversity maintenance mechanisms were required because one solution will be identified as a knee point in the vicinity of each solution in the non-dominated Pareto front. Therefore, the computational complexity is considerably decreased.

  • MaOEA-DDFC: Many-objective evolutionary algorithm based on directional diversity and favorable convergence [46]. In this algorithm, a mating selection based on favorable convergence is applied to strengthen selection pressure while an environmental selection based on directional diversity and favorable convergence is designed to balance diversity and convergence.

  • MOEA-DD: Multi-objective evolutionary algorithm based on dominance and decomposition [47]. In this algorithm, a unified paradigm is defined that combines dominance- and decomposition-based approaches for many-objective optimization. The purpose of this method is to exploit the merits from both the dominance- and decomposition-based approaches to balance the convergence and diversity of the evolutionary process.

  • MOMBI-II: Many-objective meta-heuristic based on the R2 indicator II [48]. In this algorithm, the authors presented an improved version of an MOEA based on the R2 indicator, which takes into account two key aspects (low computational cost and weak-Pareto compatibility) using the scalarizing achievement function and statistical information about the population’s proximity to the true Pareto optimal front.

  • MaOEA-R&D: Many-objective evolutionary algorithm based on objective space reduction and diversity improvement [49]. This algorithm consists of two stages: (i) the whole population quickly approaches a small number of “target” points near the true Pareto front and then (ii) the proposed diversity improvement strategy is applied to facilitate the spread and distribution of individuals.

  • RVEA: Reference vector guided evolutionary algorithm [50]. In this method, the authors applied the reference vectors to decompose the original MOOP into a number of single-objective sub-problems. Moreover, user preferences are elucidated to target a preferred subset of the whole Pareto front. Besides, an approach, termed angle penalized distance, is applied to balance the convergence and the diversity of the solutions in the high-dimensional objective space.

  • RVEA-a: RVEA embedded with the reference vector regeneration strategy [50]. In this approach, the RVEA has been modified by embedding a new strategy.

  • SPEA-R: Strength Pareto evolutionary algorithm based on reference direction [51]. In this algorithm, the authors revived a previously developed and computationally expensive strength Pareto based evolutionary algorithm by introducing an efficient reference direction-based density estimator, a new fitness assignment scheme, and a new environmental selection strategy.

  • \( \theta \)-DEA: \( \theta \)-dominance based evolutionary algorithm [52]. In this algorithm, the convergence of NSGA-III is enhanced by exploiting the fitness evaluation scheme in the multi-objective evolutionary algorithm based on decomposition. The NS scheme based on the introduced new dominance relation is applied for ranking solutions in the environmental selection stage, ensuring convergence as well as diversity.

To improve the performance of some traditional MOEAs for tackling MaOPs, new methods have been applied, and these MOEAs are divided into some groups based on their approaches. To categorize the algorithms, the recent literature was reviewed and compared. (Li et al., 2015) presented a categorization for MaOEAs in which GrEA is classified into two different groups including the relaxed dominance-based and diversity based methods. Also, SPEA2 + SDE is classified into diversity-based method. In another group namely reference set based, NSGA-III, A-NSGA-III, RVEA, and RVEA* are inserted. Also, HypE and MOMBII-II are categorized in the indicator-based group, and moreover, PICEA-g is put in the preference-based class. In another study [50] three groups are introduced. The first group includes the algorithms that are dominance based such as GrEA, SPEA2 + SDE, KnEA, MaOEA-DDFC, MaOEA-R&D, and SPEA-R. The second group contains algorithms such as NSGA-III, A- NSGA-III, EFR-RR, I-DBEA, MOEA-DD, RVEA, RVEA*, t-DEA. In this group, the decomposition approaches are employed to enhance the performance of the algorithm. The third group is known as the Indicator-based methods like HypE and MOMBI-II. The PICEA-g is not classified into any of the four categories. This is classified in the fifth group. Also, there are a few algorithms that employ a different approach in addition to their primary method. For example, both dominance and decomposition-based methods are applied in the MOEA-DD, and unlike most MOEAs, in SPEA-R, a diversity-first-convergence-second selection strategy was adopted to enhance the algorithm in quantifying solutions’ diversity and convergence. Most existing MOEAs adopt a convergence-first-and diversity-second selection strategy [53] to balance convergence and diversity, and since the proportion of non-dominated solutions is very high, and diversity preservation is very likely to be carried out only on non-dominated solutions, so, this strategy generally works well in MOOPs [51]. In a recent study, Tanabe, Ishibuchi [54] five criteria are introduced to categorize the MaOEAs including Pareto dominance based, relaxed dominance based, decomposition based, indicator based, and reference based. In this classification, NSGA-III, SPEA2 + SDE, GrEA, KnEA, SPEA/R and t-DEA are put in Pareto dominance-based and furthermore, NSGA-III, t-DEA and SPEA/R are categorized in reference-based group. On the other hand, GrEA is put in a relaxed dominance based class. I-DBEA, MOEA-DD, RVEA, and RVEA* are classified in decomposition based and moreover, I-DBEA, as well as MOEA-DD, are put in Pareto dominance based while RVEA, and RVEA* are reference based in addition to decomposition based. Last group namely, indicator-based includes HypE, BiGE, and MOMBII-II so that both HypE and BiGE are inserted to Pareto dominance based. Therefore, we present five main criteria to classify applied MaOEAs according to the literature; Dominance-based (C1) including Pareto (C1-a), diversity (C1-b), and relaxed (C1-c), Reference-set (C2), Decomposition-based (C3), Indicator-based (C4), and Preference-based (C5). As a consequence, four main classes are determined for eighteen algorithms. Also, three sub-criteria of the first criterion are denoted by a, b, c as indicated in Table 1.

Table 1 Categorization of MaOE algorithms
Full size table

2.4 Performance Evaluation Metrics

This section introduces the performance metrics used to evaluate the quality of the obtained non-dominated solutions in the Pareto repository set of the MOEAs. Several important metrics of multiple objective problems have been described in the literature like inverted generational distance (IGD), hyper-volume (HV), normalized hyper-volume (NHV), spacing metric (SM), diversity metric (DM), and potential non-dominated (PND); the metric of IGD is described below:

  • Inverted Generational distance (IGD). This metric was employed by Srinivas and Deb [55] to measure the average distance between the solutions in the PF and the closest solution in the PFknown. Mathematically, let P* be a reference set that represents the PF. The value of IGD value from P* to the PFknown is calculated as follows:

    $$ IGD = \frac{{\mathop \sum \nolimits_{{z \in P^{*} }} d\left( {z,P} \right)}}{{\left| {P^{*} } \right|}} $$
    (7)

    where |P*| denotes the number of individuals in P* and d(z, P) is the nearest Euclidean distance from z to P (PFknown). The value ofIGD reflects the comprehensive performance of an algorithm. Smaller IGD values result in a better solution set, which indicates that PFknown is close to PFtrue and has a good distribution.

3 Computational Experiments

To compare the performance of the algorithms, all of them were run on random instances and then the results were analyzed. For this purpose, we used PlatEMO v. 1.5, introduced by Tian et al. [56], to run the 18 algorithms described in Sect. 2.3. Also, the instances were generated using this platform.

3.1 Parameter Setting of Applied Algorithms

Several parameter values of the applied algorithms were checked. There are two parameter categories for MOEAs: general and private parameters. The number of function evaluations (NFE) and population size (nPOP) are classified as public group parameters. The rate of knee points for KnEA, the number of neighbors for estimating density for MaOEA-DDFC, and the number of nearest weight vectors for EFR-RR are examples for private group parameters. In this work, the NFE is set to10,000 and nPOP was set accordingly to 200 to obtain a better Pareto solution for all problems. Public parameters were set using trial and error and, after several trials, the best parameters were determined. In the strategy used to set parameters, the NFE was set first, and its value was fixed, then the second parameter (i.e., nPOP) was set. Private parameters were set according to recommended values that were previously set by researchers of PlatEMO (Tian, Cheng [56]. Algorithms such as PICEA-g, GrEA, NSGA-III, A-NSGA-III, SPEA2 + SDE, BiGE, I-DBEA, MaOEA-R&D, SPEA/R, and t-DEA do not contain any private parameters but were tested for public parameter settings while the rest of the algorithms were tested for private and public parameter settings. Therefore, NFE as well as nPOP were set to 10000 and 200, respectively, for all algorithms. All final private parameters of the MaOEAs are displayed in Table 2.

Table 2 Private parameters of each MaOE algorithm
Full size table

3.2 Comparison Between Algorithm’s Performance on All Considered Instances

This section describes the experimental results of all algorithms tested on the MOKP, MOTSP, and mQAP. Mean and standard deviation values of IGD with 3, 5, and 10 objectives are presented. In the tables, the best-performing algorithms are shown with a bold background and the second best-performers are shown with a italics background. As shown in Table 3, I-DBEA from the decomposition-based group was the best-performing algorithm for the MOKP with three objectives while SPEA-R from the dominance and reference-based group was the second-best performer on this same MOPK. Moreover, SPEA-R was the best-performing algorithm on the MOKP with five objectives and EFR-RR the second-best. For MOKP with 10 objectives, KnEA and SPEA-R were the top and second-best performing algorithms, respectively. Since the homogeneity of variances of algorithms was rejected according to the Levene test at the 0.05 significance level, the Dunnett T3 test was used to show significance between different results at the 0.05 significance level. The last row of each table shows p values presenting the test value of all the algorithms on Dunnett T3 test. A p value of 0 indicates a significant difference between the mean of the best-performing algorithm and the other algorithms (indicated by #). The computational results of ANOVA are shown in Supplementary File (S2), Tables 1–9.

Table 3 The values of IGD (mean and standard deviation) of the Pareto solutions of the algorithms on the MOKP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Figures 3, 5, and 6 present median and inter-quartile range (IQR) values of the algorithms on the test problems with 3, 5, 10 objectives (subplots a, b, and c, respectively, in each figure). The size of each rectangle represents the IQR. The short line at each end of each rectangle indicate maximum and minimum values, and the short line represents median in each rectangle. The figures contain some interesting patterns. For example, in Fig. 3a, I-DBEA occupies the lowest position in the graph as compared to the other algorithms while RVEA* occupies the highest position. Furthermore, the MOEA-DD rectangle occupies the smallest area, indicating that the MOEA-DD data has the smallest degree of variance.

Fig. 3
figure 3

Boxplot of values of IGD on 3, 5, and 10 objective 500 dimension MOKP

Full size image
Fig. 4
figure 4

The best performing algorithms relative to the IGD metric for the MOKP,MOTSP, mQAP with 3,5, and 10 objectives

Full size image
Fig. 5
figure 5

Boxplots of value of IGD on 3, 5, and 10 objective 500 dimension MOTSP

Full size image
Fig. 6
figure 6

Boxplots of IGD value on 3, 5, and 10 objective 500 dimension mQAP

Full size image

Figure 4 shows the distribution of the solution sets in the Pareto Front. Nine plots show the values corresponding to the number of objectives for the most efficient algorithms for MOKP, MOTSP, and mQAP. Three figures show scatter plots of the best objective values for the three problems above. Figure 4a, d, g presents results of A-NSGA-III on a 3-objective MOTSP, a 5-objective mQAP, and results of IDBEA on a 3-objectiveMOKP, respectively. Figure 4b, e, h depicts results of EFRRR on a 5-objective MOTSP, a 5-objective mQAP, and results of SPEAR on a 5-objective MOKP, respectively. Figure 4c, f, i depicts results of KnEA on a 10-objective MOKP, HypE on a 10-objective mQAP, and SPEAR on a 10-objective MOTSP, respectively. Based on Fig. 4a, d, A-NSGA-III is well-converged and has a proper distribution on MOTSP as compared to mQAP. Based on Fig. 4b, e on 5-objective problems, EFRRR is well-converged on MOTSP as compared to mQAP. Moreover, It can be seen from the first and second columns two algorithms have fine performance on two problems, 4-(a),(d) and 4-(b), (e) while for the 10-objective, three different algorithms perform best on three different problems. The plots of the algorithms are shown in Supplementary File S1: Figures 1–52.

Table 4 presents the mean and standard deviation values of computational time for all algorithms considering 3, 5, and 10 objectives on MOKP. MaOEA-R&D from dominance based group obtained Pareto sets in the lowest amount of time for 3-objective and RVEA from decomposition based group obtained a Pareto solution for 5 and 10 objectives in the lowest amount of time. RVEA was the second-best performing algorithm for 3 objectives on MOKP and MaOEA-R&D was the second-best performing algorithm for 5 and 10 objectives on MOKP.

Table 4 The CT (mean and standard deviation) of the Pareto solutions of the algorithms on the MOKP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Table 5 presents the mean and standard deviation values of IGD for all algorithms considering 3, 5, and 10 objectives on MOTSP. As shown, A-NSGA-III and NSGA-III from dominance and reference based were the first- and second-best performing algorithms on MOKP with 3 objectives, EFR-RR from the decomposition based and SPEA-R from dominance and reference based were the first- and second-best performing algorithms with 5 objectives and SPEA-R and KnEA were the first- and second-best performing algorithms on MOTSP with 10 objectives (Fig. 5).

Table 5 The values of IGD (mean and standard deviation) of the Pareto solutions of the algorithms on the MOTSP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Table 6 shows the mean and standard deviation values of computational time for all algorithms considering 3, 5, 10 objectives on MOTSP. As shown, t-DEA from the dominance and reference based group obtained Pareto sets in the lowest amount of time for problems with 3, 5, and 10 objectives, while RVEA from decomposition based was the second-best performing algorithm for obtaining Pareto solution for problems with 5 and 10 objectives. BiGA was the second-best performing algorithm for 3 objectives on MOTSP.

Table 6 The CT (mean and standard deviation) of the Pareto solutions of the algorithms on the MOTSP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Table 7 presents the mean and standard deviation values of IGD for all algorithms considering 3, 5, and 10 objectives on mQAP. The A-NSGA-III from dominance and reference-based, EFR-RR from decomposition-based, and HypE from indicator based group were the best-performing algorithms on mQAP with 3, 5, and 10 objectives while GrEA from dominance and reference-based, MOEA-DDFC from dominance-based group, and KnEA from indicator-based group were the second-best performing algorithms with the same number of objectives on mQAP, respectively (Fig. 6).

Table 7 The values of IGD (mean and standard deviation) of the Pareto solutions of the algorithms on the mQAP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Table 8 presents the mean and standard deviation values of computational time for all algorithms considering 3, 5, and 10 objectives on mQAP. As indicated, KnEA from dominance-based, PICEA-g from preference-based, and EFR-RR from decomposition based group obtained Pareto sets in the lowest amount of time for 3, 5, and 10 objectives, while NSGA-III from dominance and reference-based, EFR-RR from decomposition-based, and A-NSGA-III from dominance and reference-based group obtained Pareto solution in the second-lowest amount of time for 3, 5, and 10 objectives on mQAP, respectively.

Table 8 The CT (mean and standard deviation) of the Pareto solutions of the algorithms on the mQAP problem in which bold and italics backgrounds indicate the first and second-best performing algorithm for each condition
Full size table

Table 9 presents ranking changes for all algorithms on MOKP, MOTSP, and mQAP considering the metrics: IGD and CT separately. In Table 9, indicator A indicates the number of objectives changes from 3 to 5 and indicator B shows the number of objectives changes from 5 to 10. For example, the first row, which starts with algorithm HypE, indicates a slight decrease of − 3 on indicator A and − 3 on indicator B (i.e., A from 3 to 5 and B from 5 to 10) on MOKP, whereas on CT, both A and B are zero, indicating there was no change for this metric when the number of objectives was changed. While there was a significant decrease of − 4 in the value for an index of A on MOTSP, the value of indicator B decreased to − 1. However, CT value for both indicator A and B on MOTSP are zero. The rankings of mQAP from 3 objectives to 5 objectives and 5 objectives to 10 objectives have values of − 2 for indicator A and − 10 for indicator B for the value; ranking of CT for the same problem revealed an increase of + 1 for indicator A and + 3 for indicator B. Description of other rows in Table 8 is the same. More details of Table 8 are provided in Supplementary File S1 (Figures 53–55).

Table 9 Rank changes of MOEAs versus objective changes on all problems considering IGD and CT metrics
Full size table

3.3 Discussion

In this section, we discuss the class of the MaOEAs that outperforms others in solving each problem according to the significant statistical results.

To solve the MOKP, we can observe the better results among the third category such as I-DBEA, MOEA-DD, EFR-RR, since the decomposition based algorithms outperform others in solving 3-objective samples. As the size of the objectives increases to 5, not only the rank of the dominance based algorithms such as KnEA and MaOEA-DDFC or dominance and reference based such as SPEA/R ameliorates but also SPEA/R, and MaOEA-DDFC outperform the second group significantly. For example, after increasing the objectives from 3 to 5 the rank of the I-DBEA and MOEA-DD is exacerbated (+ 5) and (+ 11) respectively while, the rank of the KnEA, SPEA/R, and MaOEA-DDFC is enhanced (− 6), (− 1), and (− 5). Although, the rank of the indicator based group is improved but the results of those underperform by the dominance and reference based group for 5-objective MOKP. As can be seen from Table 3, there is no significant difference between first and second positions for 10 objectives MOKP problem, we can conclude the MaOEAs that are dominance based as well as reference set based, obtain the best IGD with less standard deviation for MOKP. On the other hand, the rank of the PICEA-g is changed (− 13) with increasing objectives from 5 to 10, and the behavior of this algorithm indicates the promising performance for solving the 10-objective MOKP. Although the rank of the indicator based group is ameliorated approximately in many-objective KP, the second group outperforms all groups. Therefore, we can point out the dominance and reference based category are promising to tackle many-objective KP in comparison with other groups. Furthermore, the improved MaOEAs such as SPEA/R occupy the best rank among other algorithms of this group since a diversity-first-convergence second selection strategy is adopted in SPEA/R, unlike most MOEAs. As it is found from Table 8, the SPEA/R shows a slight decrease (− 1) of the rank to solve the problem from 3 to 5 objectives, and a slight increase (+ 1) of the rank for solving the MOKP from 5-objective to 10-objective which justify the robustness of this algorithm. However, the mentioned algorithms do not perform well in comparison with RVEA and MaOEA-R&D from the aspect of time. We found that the decomposition based category such as RVEA, I-DBEA saves time in solving MOKP in comparison with other groups.

For tackling the 3-objective MOTSP, we must point out that most algorithms of the second group such as A-NSGA-III, NSGA-III, SPEA/R obtain better results in comparison with the other groups. Besides, the SPEA/R, GrEA from the second class and KnEA and MaOEA-DDFC from the first class obtain better positions for 5 and 10-objective MOTSP. Although the average of EFR-RR as decomposition based is better than that of SPEA/R for 5-objectives, the St. Dev. of SPEA/R is less than that of EFR-RR. On the other hand, SPEA/R has a slight decrease (− 1) of the rank to solve MOTSP not only from 3 to 5, but also from 5 to 10 objectives and therefore, this result shows the robustness of this algorithm for solving MOTSP with many objectives. To solve MOTSP, since there is no significant difference between the first and the second positions for each problem (3, 5, 10) objectives according to the results of Table 5, we conclude the MaOEAs that are dominance based as well as reference set based, obtain the best IGD with less standard deviation for MOTSP. On the other hand, an improvement of the performance is seen in the behavior of the PICEA-g for solving 10-objective MOTSP, and so this method can be promising to tackle many-objective TSP as behaved for MOKP. As it is shown in the results, we can observe as the objectives increase from 3 to 5, the rank of the second group such as GrEA, and SPEA/R is enhanced to (− 9) and (− 1) respectively and as objectives increase from 5 to 10, the rank of the KnEA and SPEA2 + SDE from the first group is improved to (− 10) and (− 5) respectively. Also, it is shown that the rank of the indicator based group is improved after increasing the objectives nonetheless; the second group outperforms all of them and therefore, this group is promising to tackle many-objective TSP in comparison with other groups. However, the mentioned algorithms do not perform well in saving time in comparison with t-DEA, RVEA. Therefore, we found that the second and third category such as t-DEA and RVEA saves time to solve 3, 5, and 10-objective MOTSP in comparison with other categories.

To solve the 3-objective mQAP, the MaOEAs such as A-NSGA-III, NSGA-III, GrEA, EFR-RR, and I-DBEA obtain the best positions in comparison with others. According to Table 7, there is no significant difference between first and second positions of these algorithms. Therefore, the dominance and reference based group outperforms other groups with less standard deviation for 3-objective mQAP. To tackle the 5-objective mQAP, we could not determine the best group since there is no significant difference between results of some representative of categories and for example, MaOEA-DDFC is the best for solving the 5-objective mQAP in comparison with EFR-RR since the St. Dev. of the MaOEA-DDFC is less than that of the EFR-RR. On the other hand, SPEA2 + SDE, MaOEA-DDFC from the first group have a mutation of the rank (− 4) and EFR-RR from third class and NSGA-III from the second class have a change of the rank (− 3) and (− 2), whereas I-DBEA from the third group and A-NSGA-III and GrEA from the second group have the change of the rank (+ 3), (+ 4), and (+ 7). As a consequence, some dominance based algorithm can be promising to solve 5-objective mQAP in comparison with others.

As it is indicated from Table 7, there is no significant difference between first and second positions for 10 objectives mQAP problem, and as a consequence, the MaOEAs that are dominance-based, presents the best IGD with less standard deviation for mQAP. For example, HypE outperforms others for solving 10-objective mQAP according to its average although; KnEA from the first group has the better St. Dev. In total, there is no significant difference between the results of HypE and some of the first class such as KnEA, MaOEA-DDFC and so, we can observe that the first group, as well as HypE from the indicator based group, outperforms others when the objectives of mQAP are increased from 5 to 10. Although, the rank of the RVEA* as well as MOEA-DD is ameliorated (− 5) but both of them underperformed by the mentioned algorithms from first class. However, KnEA, PICEA-g, and EFR-RR solve the 3, 5, and 10-objective mQAP at the savings in time. As indicated, the performance of the dominance based, decomposition based, and preference-based classes in saving time for many-objective QAP is better than other classes.

Table 10 displays the best algorithms for different many objective problems. We found from this table that the dominance and reference based algorithms such as SPEA/R, NSGA-III, and GrEA are suitable algorithms to tackle MOTSP and mQAP with 3 objectives. However, decomposition based such as I-DBEA and MOEA-DD are promising for 3-objective MOKP. On the other hand, the dominance and reference based algorithms such as SPEA/R, NSGA-III, and GrEA are promising algorithms to tackle MOKP and MOTSP with 5 and 10 objectives as the size of the objectives increases. While, the dominance based such as MaOEA-DDFC as well as the indicator-based algorithms such as HypE are promising to solve mQAP with 5 and 10 objectives although, both the first and the second have no significant difference to solve 5-objective mQAP. Lastly, the performance of the second group at saving time is the best on all problems when the size of objectives increases.

Table 10 the best class of the algorithms for solving the problems on different many objectives
Full size table

4 Conclusion

In this work, the search behavior of well-known MaOEAs algorithms (NSGA-III, MOEA-DD, SPEA-R,HypE, PICEA-g, GrEA, A-NSGA-III, SPEA2 + SDE, BiGE, EFR-RR, I-DBEA, KnEA, MaOEA-DDFC, MOMBI-II, RVEA, RVEA*, and t-DEA) on many-objective MOKP, MOTSP, and mQAP with 3, 5, and 10 objectives was examined. The experimental results on many-objective problems (MOKP, MOTSP, mQAP) were consistent with the following frequently reported result: when the number of objectives was increased, the performance of Pareto dominance-based algorithms deteriorated severely. When IGD was considered, the decomposition-based algorithms performed best on MOKP with 3 objectives, and the dominance and reference based algorithms worked the best with 5 and 10 objectives, respectively. For MOTSP, when IGD was considered, some of dominance and reference based as well as decomposition based worked best with 3 objectives and some of dominance and reference based performed best with 5 and 10 objectives, respectively. For mQAP, When IGD was considered, while the second class worked best with 3 objectives, some of first and third class worked best with 5 objectives and dominance based as well as indicator based group worked the best with 10 objectives. For the CT metric, although the MaOEA-R&D from the first class worked best on MOKP with 3 objectives, the RVEA, as well as some of the third class, had the best performance on the same problem with 5 and 10 objectives. Some of the second group such as t-DEA had best performance on MOTSP with 3, 5, and 10 objectives. Although the KnEA worked best on mQAP with 3 objectives, PICEA-g and EFR-RR had the best performance on the same problem with 5 and 10 objectives. It is valuable to note that the results above mentioned are based on ANOVA test. In short, it is concluded that convergence-based algorithms have better performance on MOKP while the number of objectives increases; considering MOTSP dominance and reference based algorithms present better performance compared with other algorithms with increasing the number of objectives; and finally indicator-based as well as dominance based perform better than others on mQAP with increasing the number of objectives. Among the eighteen algorithms tested in this study, SPEA-R has a better ranking on the three problems while the number of objectives increases.