Chapter 10
MULTI-OBJECTIVE OPTIMIZATION
Kalyanmoy Deb
Kanpur Genetic Algorithms Laboratory (KanGAL) Department of Mechanical Engineering
Indian Institute of Technology, Kanpur, India
10.1 INTRODUCTION
Many real-world search and optimization problems are naturally posed as non-linear programming problems having multiple objectives. Due to the lack of suitable solution techniques, such problems were artificially converted into a single-objective problem and solved. The difficulty arose because such prob- lems give rise to a set of trade-off optimal solutions (known as Pareto-optimal solutions), instead of a single optimum solution. It then becomes important to find not just one Pareto-optimal solution, but as many of them as possible. This is because any two such solutions constitutes a trade-off among the ob-
jectives and users would be in a better position to make a choice when many such trade-off solutions are unveiled.
Classical methods use a very different philosophy in solving these problems, mainly because of a lack of a suitable optimization methodology to find multi- ple optimal solutions efficiently. They usually require repetitive applications of an algorithm to find multiple Pareto-optimal solutions and on some occasions such applications do not even guarantee finding certain Pareto-optimal solu- tions. In contrast, the population approach of evolutionary algorithms (EAs) allows an efficient way to find multiple Pareto-optimal solutions simultane- ously in a single simulation run. This aspect has made the research and appli- cation in evolutionary multi-objective optimization (EMO) popular in the past decade. The motivated readers may explore current research issues and other important studies from various texts (Deb, 2001; Coello et al., 2002; Bagchi, 1999), conference proceedings (Fonseca et al., 2003; Zitzler et al., 2001a) and numerous research papers (archived and maintained in Coello, 2003).
In this tutorial, we discuss the fundamental differences between single- and multi-objective optimization tasks. The conditions for optimality in a multi- objective optimization problem are described and a number of state-of-the-art
274
DEB
Figure 10. L
Hypothetical trade-off solutions for a car-buying decision-making problem.
90%
0A/
c B ^^
06 u
40%
/m /
/ /
– ‘^’^ lOk
m //
Cost
multi-objective optimization techniques, including one evolutionary method, are presented. To demonstrate that the evolutionary multi-objective methods are capable and ready for solving real-world problems, we present a couple of interesting case studies. Finally, a number of important research topics in the area of evolutionary are discussed.
A multi-objective optimization problem (MOOP) deals with more than one objective function. In most practical decision-making problems, multiple ob- jectives or multiple criteria are evident. Because of a lack of suitable solution methodologies, a MOOP has been mostly cast and solved as a single-objective optimization problem in the past. However, there exist a number of fundamen- tal differences between the working principles of single- and multi-objective optimization algorithms because of which a MOOP must be attempted to solve using a multi-objective optimization technique. In a single-objective optimiza- tion problem, the task is to find one solution (except in some specific multi- modal optimization problems, where multiple optimal solutions are sought) which optimizes the sole objective function. Extending the idea to multi- objective optimization, it may be wrongly assumed that the task in a multi- objective optimization is to find an optimal solution corresponding to each objective function. Certainly, multi-objective optimization is much more than
this simple idea. We describe the concept of multi-objective optimization by using an example problem.
Let us consider the decision-making involved in buying an automobile car. Cars are available at prices ranging from a few thousand to few hundred thou- sand dollars. Let us take two extreme hypothetical cars, i.e. one costing about ten thousand dollars (solution 1) and another costing about a hundred thousand dollars (solution 2), as shown in Figure 10.1. If the cost is the only objective of this decision-making process, the optimal choice is solution 1. If this were
100k
MULTI’OBJECTIVE OPTIMIZATION 275
the only objective to all buyers, we would have seen only one type of car (so- lution 1) on the road and no car manufacturer would have produced any expen- sive cars. Fortunately, this decision-making process is not a single-objective one. Barring some exceptions, it is expected that an inexpensive car is likely to be less comfortable. The figure indicates that the cheapest car has a hypo- thetical comfort level of 40%. To rich buyers for whom comfort is the only objective of this decision-making, the choice is solution 2 (with a hypothetical maximum comfort level of 90%, as shown in the figure). This so-called two- objective optimization problem need not be considered as the two independent optimization problems, the results of which are the two extreme solutions dis- cussed above. Between these two extreme solutions, there exist many other solutions, where a trade-off between cost and comfort exists. A number of such solutions (solutions A, B, and C) with differing costs and comfort levels are also shown in the figure. Thus, between any two such solutions, one is bet- ter in terms of one objective, but this betterment comes only from a sacrifice on the other objective. In this sense, all such trade-off solutions are optimal solutions to a multi-objective optimization problem. Often, such trade-off so- lutions provide a cloax front on an objective space plotted with the objective values. This front is called the Pareto-optimal front and all such trade-off so- lutions are called Pareto-optimal solutions.
10.1.1 How Is It Different From Single-Objective Optimization?
It is clear from the above description that there exist a number of differences between a single- and a multi-objective optimization task. The latter has the following properties:
1 cardinality of the optimal set is usually more than one,
2 there are two distinct goals of optimization, instead of one, and 3 it possesses two different search spaces.
We discuss each of the above properties in the following paragraphs.
First of all, we have seen from the above car-buying example that a multi- objective optimization problem with conflicting objectives, results in a number of Pareto-optimal solutions, unlike the usual notion of only one optimal so- lution associated with a single-objective optimization task. However, there exist some single-objective optimization problems which also contain multi- ple optimal solutions (of equal or unequal importance). In a certain sense, multi-objective optimization is similar to such multi-modal optimization tasks. However, in principle, there is a difference, which we would like to highlight here. In most MOOPs, the Pareto-optimal solutions have certain similarities
276 DEB
in their decision variables (Deb, 2003). On the other hand, between one local or global optimal solution and another in a multi-modal optimization problem, there may not exist any such similarity. For a number of engineering case studies (Deb, 2003), an analysis of the obtained trade-off solutions revealed the following properties:
1 Among all Pareto-optimal solutions, some decision variables take identi- cal values. Such a property of the decision variables ensures the solution to be an optimum solution.
2 Other decision variables take different values causing the solutions to have a trade-off in their objective values.
Secondly, unlike the sole goal of finding the optimum in a single-objective optimization, here there are two distinct goals:
• convergence to the Pareto-optimal solutions and
• maintenance of a set of maximally-spread Pareto-optimal solutions.
In some sense, both the above goals are independent to each other. An op- timization algorithm must have specific properties for achieving each of the goals.
One other difference between single-objective and multi-objective optimiza- tion is that in multi-objective optimization the objective functions constitute a multi-dimensional space, in addition to the usual decision variable space com- mon to all optimization problems. This additional space is called the objec- tive space, Z. For each solution x in the decision variable space, there ex- ists a point in the objective space, denoted by f(x) = z = (zi, Z2, •.., ^M)T. The mapping takes place between an n-dimensional solution vector and an M- dimensional objective vector. Figure 10.2 illustrates these two spaces and a mapping between them. Although the search process of an algorithm takes place on the decision variables space, many interesting algorithms, particu- larly multi-objective EAs (MOEAs), use.the objective space information in their search operators. However, the presence of two different spaces intro- duces a number of interesting flexibilities in designing a search algorithm for multi-objective optimization.
10.2 TWO APPROACHES TO MULTI-OBJECTIVE OPTIMIZA TION
Although the fundamental difference between single and multiple objective optimization lies in the cardinality in the optimal set, from a practical stand- point a user needs only one solution, no matter whether the associated opti- mization problem is single-objective or multi-objective. In the case of multi- objective optimization, the user is now in a dilemma. Which of these optimal
MULTI-OBJECTIVE OPTIMIZATION 111 Decision space Objective space
Figure 10.2. Representation of the decision variable space and the corresponding objective space.
solutions must one choose? Let us try to answer this question for the case of the car-buying problem. Knowing the number of solutions that exist in the market with different trade-offs between cost and comfort, which car does one buy? This is not an easy question to answer. It involves many other consider- ations, such as the total finance available to buy the car, distance to be driven each day, number of passengers riding in the car, fuel consumption and cost, depreciation value, road conditions where the car is to be mostly driven, phys- ical health of the passengers, social status, and many other factors. Often, such higher-level information is non-technical, qualitative and experience-driven. However, if a set of trade-off solutions are already worked out or available, one can evaluate the pros and cons of each of these solutions based on all such non-technical and qualitative, yet still important, considerations and compare them to make a choice. Thus, in a multi-objective optimization, ideally the effort must be made in finding the set of trade-off optimal solutions by con- sidering all objectives to be important. After a set of such trade-off solutions are found, a user can then use higher-level qualitative considerations to make a choice. In view of these discussions, we suggest the following principle for an ideal multi-objective optimization procedure:
Step 1 Find multiple trade-off optimal solutions with a wide range of values for objectives.
Step 2 Choose one of the obtained solutions using higher-level information.
Figure 10.3 shows schematically the principles in an ideal multi-objective optimization procedure. In Step 1 (vertically downwards), multiple trade-off
278
DEB
Multi-objective optimization problem
Minimize £^ Minimize £,
Minimize f^ subject to constraints
IDEAL Multi-objective optimizer
Multriple trade-off solutions found
Choose one solution
Higher-levelJ information
Step 2
Figure 103. Schematic of an ideal multi-objective optimization procedure.
solutions are found. Thereafter, in Step 2 (horizontally, towards the right), higher-level information is used to choose one of the trade-off solutions. With this procedure in mind, it is easy to realize that single-objective optimization is a degenerate case of multi-objective optimization. In the case of single- objective optimization with only one global optimal solution. Step 1 will find only one solution, thereby not requiring us to proceed to Step 2. In the case of single-objective optimization with multiple global optima, both steps are necessary to first find all or many of the global optima and then to choose one from them by using the higher-level information about the problem.
If thought of carefully, each trade-off solution corresponds to a specific or- der of importance of the objectives. It is clear from Figure 10.1 that solution A assigns more importance to cost than to comfort. On the other hand, solution C assigns more importance to comfort than to cost. Thus, if such a relative pref- erence factor among the objectives is known for a specific problem, there is no need to follow the above principle for solving a multi-objective optimization problem. A simple method would be to form a composite objective function as the weighted sum of the objectives, where a weight for an objective is propor- tional to the preference factor assigned to that particular objective. This method of scalarizing an objective vector into a single composite objective function converts the multi-objective optimization problem into a single-objective op- timization problem. When such a composite objective function is optimized, in most cases it is possible to obtain one particular trade-off solution. This procedure of handling multi-objective optimization problems is much simpler.
MULTI-OBJECTIVE OPTIMIZATION
279
Multi-objjective /optimizatio»n problem Minimize f^ Minimi e f,
Minimi:
subject to cons
/ /
^^^Higher-levelI j H ^ ^ information
Estimate a relative dLmportance
vector
U Single-objective optimization problem
a Wj fJ + Wjfj +• • •+ ^’M*!
a composite function
Single-objectivej optimizer
/ onstraints/
Figure 10,4, Schematic of a preference-based multi-objective optimization procedure.
though still more subjective than the above ideal procedure. We call this pro- cedure a preference-based multi-objective optimization. A schematic of this procedure is shown in Figure 10.4. Based on the higher-level information, a preference vector w is first chosen. Thereafter, the preference vector is used to construct the composite function, which is then optimized to find a single trade-off optimal solution by a single-objective optimization algorithm. Al- though not often practiced, the procedure can be used to find multiple trade-off solutions by using a different preference vector and repeating the above proce- dure.
It is important to realize that the trade-off solution obtained by using the preference-based strategy is largely sensitive to the relative preference vector used in forming the composite function. A change in this preference vector will result in a (hopefully) different trade-off solution. Besides this difficulty, it is intuitive to realize that finding a relative preference vector itself is highly sub-
jective and not straightforward. This requires an analysis of the non-technical, qualitative and experience-driven information to find a quantitative relative preference vector. Without any knowledge of the likely trade-off solutions, this is an even more difficult task. Classical multi-objective optimization methods which convert multiple objectives into a single objective by using a relative preference vector of objectives work according to this preference-based strat- egy. Unless a reliable and accurate preference vector is available, the optimal solution obtained by such methods is highly subjective to the particular user.
The ideal multi-objective optimization procedure suggested earlier is less subjective. In Step 1, a user does not need any relative preference vector in- formation. The task there is to find as many different trade-off solutions as possible. Once a well-distributed set of trade-off solutions is found. Step 2 then requires certain problem information in order to choose one solution. It is
280 DEB
important to mention that in Step 2, the problem information is used to evaluate and compare each of the obtained trade-off solutions. In the ideal approach, the problem information is not used to search for a new solution; instead, it is used to choose one solution from a set of already obtained trade-off solutions. Thus, there is a fundamental difference in using the problem information in both ap- proaches. In the preference-based approach, a relative preference vector needs to be supphed without any knowledge of the possible consequences. However, in the proposed ideal approach, the problem information is used to choose one solution from the obtained set of trade-off solutions. We argue that the ideal approach in this matter is more methodical, more practical, and less subjective. At the same time, we highlight the fact that if a reliable relative preference vec- tor is available to a problem, there is no reason to find other trade-off solutions. In such a case, a preference-based approach would be adequate.
In the next section, we make the above qualitative idea of multi-objective optimization more quantitative.
10.3 NON-DOMINATED SOLUTIONS AND PARETO-OPTIMAL SOLUTIONS
Most multi-objective optimization algorithms use the concept of dominance in their search. Here, we define the concept of dominance and related terms and present a number of techniques for identifying dominated solutions in a finite population of solutions.
10.3.1 Special Solutions
Wefirstdefine some special solutions which are often used in multi-objective optimization algorithms.
Ideal Objective Vector For each of the M conflicting objectives, there ex- ists one different optimal solution. An objective vector constructed with these individual optimal objective values constitutes the ideal objective vector.
DEFINITION 1 The mth component of the ideal objective vector z* is the con- strained minimum solution of the following problem:
Minimize /^(x) 1 subjectto Xe S \
Thus, if the minimum solution for the mth objective function is the decision vector x*^'”^ with function value /^, the ideal vector is as follows:
z* = r = (fin,….fl,f
In general, the ideal objective vector (z*) corresponds to a non-existent solution (Figure 10.5). This is because the minimum solution of (10.1) for each objec-
MULTI-OBJECTIVE OPTIMIZATION
281
Figure 10.5. The ideal, Utopian, and nadir objective vectors.
tive function need not be the same solution. The only way an ideal objective vector corresponds to a feasible solution is when the minimal solutions to all objective functions are identical. In this case, the objectives are not conflicting with each other and the minimum solution to any objective function would be the only optimal solution to the MOOR Although the ideal objective vector is usually non-existent, it is also clear from Figure 10.5 that solutions closer to the ideal objective vector are better. Moreover, many algorithms require the knowledge of the lower bound on each objective function to normalize objec- tive values in a common range.
Utopian Objective Vector The ideal objective vector denotes an array of the lower bound of all objective functions. This means that for every objective function there exists at least one solution in the feasible search space sharing an identical value with the corresponding element in the ideal solution. Some algorithms may require a solution which has an objective value strictly bet- ter than (and not equal to) that of any solution in the search space. For this purpose, the Utopian objective vector is defined as follows.
DEFINITION 2 A Utopian objective vector z** has each of its components marginally smaller than that of the ideal objective vector, or z** = z* — 6, with €i > Ofor all i = 1,2,…, M.
Figure 10.5 shows a Utopian objective vector. Like the ideal objective vector, the Utopian objective vector also represents a non-existent solution.
Nadir Objective Vector Unlike the ideal objective vector which represents the lower bound of each objective in the entire feasible search space, the nadir objective vector, z”^”, represents the upper bound of each objective in the entire Pareto-optimal set, and not in the entire search space. A nadir objective vector
—-•(C^fr)
282 DEB
must not be confused with a vector of objectives (marked as W in Figure 10.5) found by using the worst feasible function values, Z,””^”, in the entire search space. The nadir objective vector may represent an existent or a non-existent solution, depending on the convexity and continuity of the Pareto-optimal set. In order to normalize each objective in the entire range of the Pareto-optimal region, the knowledge of nadir and ideal objective vectors can be used as fol- lows:
y-norm ^ JLIA. (10.2) •^’ _nad_* ^^
10.3.2 Concept of Domination
Most multi-objective optimization algorithms use the concept of domina- tion. In these algorithms, two solutions are compared on the basis of whether one dominates the other or not. We will describe the concept of domination in the following paragraph.
We assume that there are M objective functions. In order to cover both minimization and maximization of objective functions, we use the operator < between two solutions / and j as / < j to denote that solution / is better than solution j on a particular objective. Similarly, / > j for a particular objective implies that solution / is worse than solution j on this objective. For example, if an objective function is to be minimized, the operator < would mean the " < " operator, whereas if the objective function is to be maximized, the operator < would mean the ">” operator. The following definition covers mixed problems with minimization of some objective functions and maximization of the rest of them.
DEFINITION 3 A solution x^^^ is said to dominate the other solution x^^\ if both conditions 1 and 2 are true:
1 The solution x^^^ is no worse than x^^^ in all objectives: that is, fj (x(‘)) ^ fj (x(2)) forallj = h2,…,M
2 Thesolutionx^^^isstrictlybetterthanx^^^inatleastoneobjective,or fjix^^^) < fjix^^^)for at least one j e {1,2, ..., M)
If either of the above conditions is violated, the solution x^^^ does not dom- inate the solution x^'^^ If x^^^ dominates the solution x^^^ (or mathematically x(i) ^ x^^^), it is also customary to write any of the following:
• x^^^ is dominated by x^^\
• x^^^ is non-dominated by x^^\ or
MULTI-OBJECTIVE OPTIMIZATION
283
•
Figure 10.6. A set of five solutions and the correspon(iing non-(Jominate(i fronts. x^^^ is non-inferior to x^^^.
£2 (minimize)
--!-#3 I.!\ L
£2 (minimize)
2 6 10 14 18
£^ (maximize)
(b)
2 6 10 14 18 f-j^(maximize)
(a)
Let us consider a two-objective optimization problem with five different so- lutions shown in the objective space, as illustrated in Figure 10.6(a). Let us also assume that the objective function 1 needs to be maximized while the objective function 2 needs to be minimized. Five solutions with different ob-
jective function values are shown in this figure. Since both objective functions are of importance to us, it is usually difficult to find one solution which is best with respect to both objectives. However, we can use the above definition of domination to decide which solution is better among any two given solutions in terms of both objectives. For example, if solutions 1 and 2 are to be compared, we observe that solution 1 is better than solution 2 in objective function 1 and solution 1 is also better than solution 2 in objective function 2. Thus, both of the above conditions for domination are satisfied and we may write that solution 1 dominates solution 2. We take another instance of comparing solu- tions 1 and 5. Here, solution 5 is better than solution 1 in the first objective and solution 5 is no worse (in fact, they are equal) than solution 1 in the second objective. Thus, both the above conditions for domination are also satisfied and we may write that solution 5 dominates solution L
It is intuitive that if a solution x^^^ dominates another solution x^^^, the so- lution x^^^ is better than x^^^ in the parlance of multi-objective optimization. Since the concept of domination allows a way to compare solutions with multi- ple objectives, most multi-objective optimization methods use this domination concept to search for non-dominated solutions.
10.3.3 Properties of Dominance Relation
Definition 3 defines the dominance relation between any two solutions. There are three possibilities that can be the outcome of the dominance check between two solutions 1 and 2. i.e. (i) solution 1 dominates solution 2, (ii) so- lution 1 gets dominated by solution 2, or (iii) solutions 1 and 2 do not dominate
284 DEB each other. Let us now discuss the different binary relation properties (Gormen
et al., 1990) of the dominance operator.
Reflexive The dominance relation is not reflexive, since any solution p does not dominate itself according to Definition 3. The second condition of dominance relation in Definition 3 does not allow this property to be satisfied.
Symmetric The dominance relation is also not symmetric, because p < q does not imply q < p. In fact, the opposite is true. That is, if p dom- inates q, then q does not dominate p. Thus, the dominance relation is asymmetric.
Antisymmetric Since the dominance relation is not symmetric, it cannot be antisymmetric as well.
Transitive The dominance relation is transitive. This is because if p 4and0(N logA^)forM=2and3.
A Non-dominated Sorting Procedure Using the above procedure, each front can be identified with at most O(MN^) computations. In certain sce- narios, this procedure may demand more than 0{MN^) computational effort for the overall non-dominated sorting of a population. Here, we suggest a com- pletely different procedure which uses a better bookkeeping strategy requiring O(MN^) overall computational complexity.
First, for each solution we calculate two entities: (i) domination count «,, the number of solutions which dominate the solution i, and (ii) Si, a set of solutions which the solution / dominates. This requires 0{MN^) comparisons. At the end of this procedure, all solutions in the first non-dominated front will have their domination count as zero. Now, for each of these solutions (each solution i with ni = 0), we visit each member (j) of its set 5, and reduce its domination count by one. In doing so, if for any member j the domination count becomes zero, we put it in a separate list P’. After such modifications on Si are performed for each / with n, = 0, all solutions of P’ would belong to the second non-dominated front. The above procedure can be continued with each member of P’ and the third non-dominated front can be identified. This process continues until all solutions are classified.
An O(MN^) Non-Dominated Sorting Algoritlim
Step1ForeachieP,ni =0andinitialize5,=0.Forallj7^/and
j e P, perform Step 2 and then proceed to Step 3.
Step 2 If / :< y, update Sp = Sp'O {j}. Otherwise, if j < i, set«, =
n/ + l.
Step 3 If «, = 0, keep / in the first non-dominated front Pi (we called
this set P ' in the above paragraph). Set a front counter k = I. Step 4 While P^ ^^^ 0, perform the following steps.
MULTI-OBJECTIVE OPTIMIZATION 289 Step 5 Initialize g = 0 for storing next non-dominated solutions. For
eachi € P^andforeachj e Si,
Step 5a Update rij = rij — I.
Step5b Ifrij=0,keepj inQ,orperform Q= QU {j}.
Step6 Setk=k-\-\ SindPk= Q.GotoStep4.
Steps 1 to 3 find the solutions in the first non-dominated front and require 0{MN^) computational complexity. Steps 4 to 6 repeatedly find higher fronts and require at most O(N^) comparisons, as argued below. For each solution / in the second or higher-level of non-domination, the domination count n, can be at most N — \. Thus, each solution i will be visited at most N — I times before its domination count becomes zero. At this point, the solution is assigned a particular non-domination level and will never be visited again. Since there are at most N — I such solutions, the complexity of identifying second and more fronts is 0{N^). Thus, the overall complexity of the proce- dure is O(MN^). It is important to note that although the time complexity has reduced to O(MN^), the storage requirement has increased to OiN'^).
When the above procedure is applied to the five solutions of Figure 10.6(a), we shall obtain three non-dominated fronts as shown in Figure 10.6(b). From the dominance relations, the solutions 3 and 5 are the best, followed by solu- tions 1 and 4. Finally, solution 2 belongs to the worst non-dominated front. Thus, the ordering of solutions in terms of their non-domination level is as fol- lows: ((3,5), (1,4), (2)). A recent study (Jensen, 2003b) suggested a divided- and-conquer method to reduce the complexity of sorting to 0(A'^log^~^ A^).
10.4 SOME APPROACHES TO MULTI-OBJECTIVE OPTIMIZATION
In this section, we briefly mention a couple of commonly-used classical multi-objective optimization methods and thereafter present a commonly-used EMO method.
10.4.1 Classical Method; Weighted-Sum Approach
The weighted sum method, as the name suggests, scalarizes a set of ob- jectives into a single objective by pre-multiplying each objective with a user- supplied weight. This method is the simplest approach and is probably the most widely used classical approach. If we are faced with the two objectives of minimizing the cost of a product and minimizing the amount of wasted material in the process of fabricating the product, one naturally thinks of min- imizing a weighted sum of these two objectives. Although the idea is simple, it introduces a not-so-simple question. What values of the weights must one
290 DEB
use? Of course, there is no unique answer to this question. The answer de- pends on the importance of each objective in the context of the problem and a scaling factor. The scaling effect can be avoided somewhat by normalizing the objective functions. After the objectives are normahzed, a composite objective function F(x) can be formed by summing the weighted normalized objectives and the problem is then converted to a single-objective optimization problem as follows:
Minimize
subject to gy(x)>0
^(X) = E;:=1 Wmfmix) hk(x) = 0
; = l,2,. • ,J k = l,2,.. .,K i = h2,.. . ,n
(10.3)
;cJ^U;c,
hk{x)=0
Xi < Xi < Xf
U(x),
m=l,2, ..., M andm y^fi
j = l,2,..
k = l,2,.. .,K 1 I = 1,2,.. • ,n \
(10.4)
In the above formulation, the parameter 6^ represents an upper bound of the value of fm and need not necessarily mean a small value close to zero.
Let us say that we retain /2 as an objective and treat /i as a constraint: /i(x) < 6i. Figure 10.10 shows four scenarios with different €\ values. Let us consider the third scenario with ei = e^ first. The resulting problem with this constraint divides the original feasible objective space into two portions, f\ < el and f\ > e^. The left portion becomes the feasible solution of the resulting problem stated in (10.4). Now, the task of the resulting problem is to find the solution which minimizes this feasible region. From Figure 10.10, it is
clear that the minimum solution is C. In this way, intermediate Pareto-optimal solutions can be obtained in the case of non-convex objective space problems by using the 6-constraint method.
292
DEB
Figure 10.10. The e-constraint method.
One of the difficulties of this method is that the solution to the problem stated in (10.4) largely depends on the chosen € vector. Let us refer to Fig- ure 10.10 again. Instead of choosing ef, if e” is chosen, there exists no feasible solution to the stated problem. Thus, no solution would be found. On the other hand, if ^f is used, the entire search space is feasible. The resulting problem has the minimum at D. Moreover, as the number of objectives increases, there exist more elements in the e vector, thereby requiring more information from the user.
10.4.3 Evolutionary Multi-objective Optimization Method
Over the years, researchers have suggested a number of MOEAs empha- sizing non-dominated solutions in a EA population. In this section, we shall describe one state-of-the-art algorithm popularly used in EMO studies.
Elitist Non-dominated Sorting GA (NSGA-II) The non-dominated sorting GA or NSGA-II procedure (Deb et al., 2002a) for finding multiple Pareto- optimal solutions in a multi-objective optimization problem has the following three features:
1 it uses an ehtist principle,
2 it uses an expUcit diversity preserving mechanism, and 3 it emphasizes the non-dominated solutions.
In NSGA-II, the offspring population Qt is first created by using the parent population P, and the usual genetic operators (Goldberg, 1989), see also Chap- ter 4. Thereafter, the two populations are combined together to form Rt of
MULTI-OBJECTIVE OPTIMIZATION 293
Non-dominated Crowding sorting distance
sorting
•^ •^-
r.
Rejected
Ot
size 2N. Then, a non-dominated sorting is used to classify the entire popula- tion Rt. Once the non-dominated sorting is over, the new population is filled by solutions of different non-dominated fronts, one at a time. The filling starts with the best non-dominated front and continues with solutions of the second non-dominated front, followed by the third non-dominated front, and so on. Since the overall population size of Rt is 2iV, not all fronts may be accommo- dated in N slots available in the new population. All fronts which could not be accommodated are simply deleted. When the last allowed front is being considered, there may exist more solutions in the last front than the remaining slots in the new population. This scenario is illustrated in Figure 10.11. Instead of arbitrarily discarding some members from the last acceptable front, the so- lutions which will make the diversity of the selected solutions the highest are chosen. The NSGA-II procedure is outlined in the following.
NSGA-II
Step 1 Combine parent and offspring populations and create R^ = P^U Qt. Perform a non-dominated sorting to Rt and identify different
fronts: J^i.i = \,2,…, etc.
Step 2 Set new population P^-^i = 0. Set a counter / = 1.
Until |Pr+il + \^i\ < N, perform P,+i = P,+i U J^, and / = / + 1.
Step 3 Perform the Crowding-sort(JT^,
The first condition ensures that the chosen solution lies on a better non-domin- ated front. The second condition resolves the tie of both solutions being on the same non-dominated front by deciding on their crowded distance. The one residing in a less crowded area (with a larger crowding distance di) wins. The crowding distance 4 can be computed in various ways. However, in NSGA-II, we use a crowding distance metric, which requires O(MNlogN) computa- tions.
To obtain an estimate of the density of solutions surrounding a particular solution i in the population, we take the average distance of two solutions on either side of solution / along each of the objectives. This quantity di serves as an estimate of the perimeter of the cuboid formed by using the nearest neigh- bors as the vertices (we call this the crowding distance). In Figure 10.12, the crowding distance of the ith solution in its front (marked with filled circles) is the average side-length of the cuboid (shown by a dashed box). The following algorithm is used to calculate the crowding distance of each point in the set J^.
Crowding Distance Assignment Procedure; crowding-sort(JT, <^) Step CI Call the number of solutions in ^ as / = |^|. For each / in the
set, first assign di = 0.
Step C2 For each objective function m = 1, 2,..., M, sort the set in worse order of /^ orfindthe sorted indices vector I^ = sort(/^, >).
MULTI-OBJECTIVE OPTIMIZATION
295
i-l«-
o
o
Cuboid
, o
:i..
I. •’
fl
Figure JO.J2. The crowding distance calculation.
Step C3 For m = 1, 2,…, M, assign a large distance to the boundary solutions, or drm = dm = oo, and for all other solutions / = 2 to (I — 1), assign
, J,Jm Jm dim = dim -| :
] J fma\ fmm Jm Jm
The index Ij denotes the solution index of the yth member in the sorted hst. Thus, for any objective, /] and // denote the lowest and highest objective func- tion values, respectively. The second term on the right-hand side of the last equation is the difference in objective function values between two neighbor- ing solutions on either side of solution Ij. Thus, this metric denotes half of the perimeter of the enclosing cuboid with the nearest neighboring solutions placed on the vertices of the cuboid (Figure 10.12), It is interesting to note that for any solution / the same two solutions («’ + 1) and (/ — 1) need not be neighbors in all objectives, particularly for M > 3. The parameters f^^^ and /^'” can be set as the population-maximum and population-minimum values of the mth objective function. The above metric requires M sorting calcula- tions in Step C2, each requiring 0(N\ogN) computations. Step C3 requires A^’ computations. Thus, the complexity of the above distance metric computa- tion is 0(MN log A’^) and the overall complexity of one generation of NSGA-II is 0(MA^^), governed by the non-dominated sorting procedure,
10.4.4 Sample Simulation Results
In this section, we show the simulation results of NSGA-II on two test prob- lems. The first problem (SCHl) is a simple two-objective problem with a convex Pareto-optimal front:
Minimize fi(x) = x’^
SCHl : •! Minimize f2(x) = (x – 2)^ (10.5)
-10^
-X2 +9;ci>1 TNK
Minimize /i(x) =xx Minimize /2(X) = X2
xl +xl-l- -j^cosAetan-^ f^) ^ ^ (jci- 0.5)2^ (^2_0.5)2