Experimental analysis of design elements of scalarizing function-based multiobjective evolutionary algorithms

In many areas, an optimal decision should take into consideration two or more conflicting objectives. A problem with multiple objectives is called a multiobjective combinatorial optimization problem (MOOP), if it has two characteristics. First, the decision variables are discrete, and second, the set of feasible solutions is finite. Combinatorial optimization finds applications in many real-world problems, e.g., scheduling, time tabling, production, facilities design, and routing (Yu 2013).

In multiobjective optimization, there is usually no solution for which all objectives have optimal values, so the preferences of the decision maker (DM) need to be taken into account in order to select the best compromise solution. It is a generally accepted assumption that the DM’s preferences are compatible with the dominance relation. Under this assumption, the most preferred solution belongs to the Pareto set. Thus, the goal of most multiobjective optimization algorithms is finding the Pareto set, or a good approximation of it, for further exploration by the DM.

Evolutionary algorithms are a promising option for solving multiobjective problems (Deb 2001). They process a population of candidate solutions in each iteration, so they are able to search for multiple (approximately) Pareto solutions concurrently in a single run.

In evolutionary algorithms, in each intermediate iteration, a selection process is performed in which good members of the population have a higher probability of survival (and generating offspring) and worse members have a higher probability of elimination. Thus, a mechanism for evaluation of intermediate solutions is necessary. In the single-objective case, intermediate solutions can naturally be evaluated with the value of the single-objective function. In the multiobjective case, there is no such obvious evaluation mechanism, so different mechanisms are used in different methods.

One frequently used type of evaluation mechanism is the Pareto dominance-based evaluation. A typical example is Pareto ranking used, e.g., in the NSGA2 algorithm (Deb et al. 2002). Pareto dominance-based evaluation is also used in PAES (Knowles and Corne 1999) and SPEA (Zitzler and Thiele 1999). Although Pareto dominance-based mechanisms have the advantage of not requiring the transformation of a MOOP into a single-objective problem, they may suffer from other weaknesses, such as losing selection pressure with the increasing number of objectives, needing an additional mechanism for preserving diversity, and difficult hybridization with local search (Neri et al. 2012).

Another type of evaluation mechanism is scalarizing function-based evaluation. In mechanisms of this type, a multiobjective optimization problem is transformed into a family of parametric single-objective optimization problems. In each problem, a nonnegative weight vector defines a single scalarizing function. Typically used scalarizing functions are described in the next section.

In the extreme case, two or more objectives may be combined with a single scalarizing function and the problem may be further treated as a single-objective problem, see, e.g., Abualigah et al. (2018). However, in the case of scalarizing function-based MOEAs, multiple scalarizing functions with various weight vectors are used to generate an approximation of the whole or a part of the Pareto front.

Two well-known examples of multiobjective evolutionary algorithms based on scalarizing functions are JMOGLS Jaszkiewicz (2002a) and MOEA/D Zhang and Li (2007). These methods proved to be very successful in multiple computational experiments (Gong et al. 2012; Ishibuchi et al. 2015; Ke et al. 2013; Zhang et al. 2010; Li et al. 2014; Ding and Wang 2013; Liu et al. 2014; Jaszkiewicz 2002b, 2003; Mei et al. 2011; Ishibuchi et al. 2011; Sindhya et al. 2011; Kafafy et al. 2012) and practical applications (Konstantinidis and Yang 2011; Sengupta et al. 2012, 2013; Carvalho et al. 2012; Trivedi et al. 2015). However, none of these computational experiments had the same goal as our study, which is understanding of the importance of the main design elements differentiating JMOGLS and MOEA/D.

Although the ways JMOGLS and MOEA/D presented in the original papers were very different, the two methods have a similar structure. In fact, they differ only in two main elements: the selection of the weight vectors defining scalarizing functions, and the selection of parents for recombination.

The main contribution of this paper is a clear understanding which of the two above-mentioned design elements has the main influence on the performance of JMOGLS and MOEA/D. In order to answer this question, we propose a new method that is an intermediate method between JMOGLS and MOEA/D and differs from each of them in just one of the design elements. In the computational experiment, we use three different multiobjective combinatorial optimization problems, i.e., the multiobjective symmetric traveling salesperson problem, the traveling salesperson problem with profits, and the multiobjective set covering problem. The use of three different problems allows us to make more general conclusions. Wherever possible, we use instances from well-known libraries, such as multiobjective symmetric traveling salesperson problem instances from Lust’s library¹ (Lust and Teghem 2010) or multiobjective set covering problem instances from another library of the same author² (Lust and Tuyttens 2014). Some other instances have been generated for the purpose of this experiment, in a clearly described way. The most important result of the computational experiment is that the design element with the highest influence on the performance of the scalarizing function-based MOEAs is the choice of a mechanism for parents selection, while the selection of weight vectors, either random or evenly distributed, has practically negligible influence.

The rest of this paper is organized as follows. In the next section, some basic definitions are given. In Sect. 3, a short description of JMOGLS and MOEA/D is given. An intermediate method between JMOGLS and MOEA/D, called Evenly distributed MOGLS (EMOGLS), is introduced in Sect. 4. The computational experiments and discussion of the obtained results are presented in Sects. 5 and 6, respectively. The paper ends with conclusions and potential directions for future research.

The multiobjective optimization problem (MOOP) is an optimization problem which involves multiple objective functions and in mathematical terms can be formulated as:where solution\(x=[x_1,\ldots ,x_I]\) is a vector of decision variables and \(D\) is the set of feasible solutions.

The image of a solution \(x\) in the objective space is a point\(z^x = [z_1^x,\ldots ,z_J^x] = f(x)\) such that \(z_j^x = f_j(x),\quad j = 1,\ldots ,J\).

Point \(z^1\) dominates \(z^2\), \(z^1 \succ z^2 \), if \(\forall _j \quad z_j^1 \le z_j^2\) and \(z_j^1 < z_j^2\) for at least one j. A solution is a Pareto solution, if there does not exist another feasible solution which dominates it. The image of a Pareto solution in the objective space is called a non-dominated point. The set of all Pareto solutions is called the Pareto set, and the image of the Pareto set in the objective space is called the non-dominated frontier or the Pareto front. Two solutions are mutually non-dominated if neither of them dominates the other and their images in the objective space are different. In this paper, a set of mutually non-dominated solutions generated by a multiobjective evolutionary algorithm is called a Pareto archive.

Weighted linear scalarizing functions are defined in the following way:where \( \varLambda = [\lambda _1,\ldots ,\lambda _J] \forall \lambda _j \ge 0\) is a weight vector.

Each weighted linear scalarizing function has at least one global optimum belonging to the Pareto set (Steuer 1985).

Weighted Chebyshev scalarizing functions are defined in the following way:where \( z^*\) is a reference point and \( \varLambda = [\lambda _1,\ldots ,\lambda _j] \forall \lambda _j \ge 0\) is a weight vector.

Each weighted Chebyshev scalarizing function has at least one global optimum belonging to the Pareto set. For each Pareto solution x, there exists a weighted Chebyshev scalarizing function \(s_\infty \) such that x is a global optimum of \(s_\infty \) (Steuer 1985).

The above properties suggest an advantage of weighted Chebyshev scalarizing functions, since every Pareto solution may be obtained by optimizing this type of function. However, this property holds only if an exact optimum solution of the function can be obtained. In practice, when heuristic methods are used, linear scalarizing functions often perform better (Zhang and Li 2007; Jaszkiewicz 2002a).

The two classes of functions can also be combined, producing mixed scalarizing functions, defined in the following way:where \(w_1\) defines the weight of the linear scalarizing function and \(w_\infty \) defines the weight of the Chebyshev scalarizing function. The sum of these two weights should equal one.

The main idea of scalarizing function-based multiobjective algorithms is as follows: if we optimized all weighted Chebyshev scalarizing functions defined by all possible weight vectors, we would obtain the true Pareto set. Unfortunately, implementing this idea in practice is impossible, since the set of all weight vectors is infinite, and, in many cases, there exists no exact method for finding the optimum solution of a scalarizing function within a realistic time frame. However, we can still approximate the Pareto set by heuristic optimization of a set of various scalarizing functions defined by a set of well-distributed weight vectors.

From another point of view, JMOGLS and MOEA/D are based on the single-objective genetic local search (sGLS) algorithm (Kolen and Pesch 1994; Jaszkiewicz and Kominek 2000). In each iteration of sGLS, two solutions (parents) are chosen for recombination from a population of solutions being relatively good on the objective function. The offspring is generated by a recombination of the parents and then improved by a local search.

A single iteration in both JMOGLS and MOEA/D is almost the same as a single iteration in sGLS, i.e., in each iteration the algorithms select two solutions which are relatively good on the current scalarizing function, and the offspring is then improved by a local search guided by the same function. However, for each iteration, a different weight vector, and thus a different scalarizing function, is selected. Furthermore, both JMOGLS and MOEA/D use special mechanisms for parents selection. These mechanisms are a necessity, as the populations used in multiobjective algorithms are relatively large and contain solutions that are dispersed over various regions of the objective space, only some of them being good on the current scalarizing function (while in single-objective algorithms all solutions in the population are usually relatively good on the single-objective function). In short, JMOGLS and MOEA/D use two specific mechanisms: one for choosing weight vectors, and another for choosing two parents which are relatively good on the current scalarizing function. The two mechanisms differ in each method.

JMOGLS was proposed by Jaszkiewicz (2002a) and further developed in Jaszkiewicz (2004). It is based on the algorithm proposed by Ishibuchi and Murata (1998). Both methods choose weight vectors defining the scalarizing functions at random, but JMOGLS uses an aggressive tournament selection (instead of roulette wheel selection, used by Ishibuchi and Murata) to select very good solutions for recombination. The selection is aggressive in the sense that a relatively large number of solutions take part in the tournament, and only the best and second best solutions (according to the current scalarizing function) are selected as parents.

The original version (Jaszkiewicz 2002a) used a so-called temporary population, selected in each iteration, to achieve an aggressive selection. The tournament selection was proposed in the updated version of JMOGLS (Jaszkiewicz 2004). Since the tournament selection is less time-consuming than the original mechanism, it is what we chose to use it in this paper.

MOEA/D, proposed by Zhang and Li (2007), generates a finite set of evenly distributed weight vectors defining a set of scalarizing functions. Zhang et al. interpret it as a decomposition of the MOOP into a number of single-objective subproblems corresponding to particular weight vectors, giving rise to its name.

Note that the two methods do not simply perform an independent optimization of a number of scalarizing functions. In each iteration, the parents are selected from a common population, so a parent could have been obtained with the use of another scalarizing function defined by a weight vector different (but usually similar) to the one currently used. In other words, solutions obtained during the optimization of a given scalarizing function help optimize other, similar scalarizing functions.

As stated above, our goal is to experimentally assess which of the two elements differentiating JMOGLS and MOEA/D has a greater influence on performance and which versions of these elements yield better results. However, if we observed differences in the performance of the two methods, we would not know which of the two different elements is the main source of these differences. Therefore, we propose an intermediate method, called Evenly distributed MOGLS (EMOGLS), which is different in just one element from both JMOGLS and MOEA/D. EMOGLS selects weight vectors from a set of evenly distributed weight vectors similarly to MOEA/D, but it chooses the solutions for recombination in the same way as JMOGLS.

We could also consider another intermediate combination of the design elements, i.e., a method that would select weight vectors like JMOGLS and select solutions for recombination like MOEA/D. We do not see, however, any straightforward way to implement such a combination, since in MOEA/D the selection of solutions for recombination is strongly linked with the existence of evenly distributed weight vectors and association of solutions with these weight vectors.

Evenly distributed weight vectors were also used in some other MOGLS algorithms (Murata et al. 2001; Ishibuchi et al. 2009), but these methods differ from JMOGLS and MOEA/D in other aspects.

In order to experimentally assess the influence of different elements in JMOGLS and MOEA/D, we compare the algorithms on instances of three different multiobjective combinatorial problems, i.e., multiobjective symmetric traveling salesperson problem (TSP), traveling salesperson problem with profits, and multiobjective set covering problem. To avoid the influence of implementation details, all methods were implemented in Java, sharing as much of the code as possible.

Tables 2, 3, 4, 5 and 6 present the mean and the standard deviation of quality indicators values obtained by MOMSLS, JMOGLS, EMOGLS, and MOEA/D on MSTSP, TSPWP, and MOSCP instances. The best results for each instance are highlighted.

The main observations are:In order to test the statistical significance of the differences, we performed the nonparametric Wilcoxon signed-rank test, with \(\alpha =0.05\). We found, in all cases, that MOEA/D was significantly worse than JMOGLS and EMOGLS. The two latter methods did not differ in any cases except of the ClusterABC300 instance of MSTSP, for which EMOGLS was slightly better. As can be seen in Table 3, the difference between EMOGLS and JMOGLS in this instance was, however, much smaller than the difference between MOEA/D and any other method.

The main observation from the whole experiment is that the main design element which influences the performance of scalarizing function-based multiobjective evolutionary algorithms is the choice of the mechanism for parents selection. MOEA/D and EMOGLS differ only in this mechanism, and their performance differs significantly.

Furthermore, since EMOGLS performs better than MOEA/D, and the two methods differ only in parents selection, we may conclude that the selection mechanism used in EMOGLS (and JMOGLS) is a better choice for the problems considered in this paper. In our opinion, this is mainly due to the fact that in JMOGLS and EMOGLS parents are selected from a larger population of solutions, i.e., from the Pareto archive, while in MOEA/D the population is bounded by the predefined number of weight vectors. Selecting parents from the Pareto archive ensures better diversity and allows us to avoid a premature convergence in JMOGLS and EMOGLS.

On the other hand, since EMOGLS and JMOGLS perform very similarly, we may conclude that selecting weight vectors either at random or from a set of evenly distributed weight vectors does not substantially influence algorithm performance.

Note, however, that the number of weight vectors should be large enough to ensure that EMOGLS works comparably to JMOGLS. To illustrate it, in Table 7 we present the results for instance 2scp81A with 101, 201, and 301 weight vectors obtained with JMOGLS, EMOGLS, and MOEA/D with a constant total number of iterations. Note that, in the case of JMOGLS, the number of weight vectors influences only the number of initial solutions. These results show that, with 101 and 201 weight vectors, results of EMOGLS are worse than those of JMOGLS and, at the same time, significantly better than results of MOEA/D. However, for 301 weight vectors, results of JMOGLS and EMOGLS are similar but at the same time significantly better than results of MOEA/D. Also note that the performance of MOEA/D improves with the growing number of weight vectors, probably due to an increasing population size from which parents are selected. The performance of MOEA/D improves, however, more slowly than the performance of EMOGLS.

In the paper, we experimentally compared the performance of JMOGLS and MOEA/D algorithms. We used three different multiobjective combinatorial problems, i.e., the multiobjective symmetric traveling salesperson problem, traveling salesperson problem with profits, and multiobjective set covering problem. In this comparison, we focused on identifying the main design elements which influence their performance. To our best knowledge, this is the first such systematic comparison of these algorithms. Such analysis provides deeper insight into the sources of variation between different methods.

Our results indicate that the main factor influencing the performance of algorithms is the selection of parents. The choice of parents with tournament selection used in JMOGLS and EMOGLS performed better on all three problems used in the experiment.

We have also proposed a slight modification of JMOGLS in which parents are selected from the Pareto archive without the use of an additional population of solutions.

We have obtained similar results for three different multiobjective combinatorial problems. Without a doubt, further computational studies on other combinatorial and continuous problems, including problems with higher numbers of objectives, would be beneficial to assess whether the same pattern holds in other cases.

Recently, Zhang et al. proposed (Li et al. 2015) certain extended versions of MOEA/D in which the selection of solutions for the current population is performed differently, explicitly taking into account both the quality and diversity of solutions associated with particular weight vectors (subproblems). Thus, an interesting direction for further research would be to compare JMOGLS/EMOGLS with this new version of MOEA/D.