12Multiobjective Optimization

Previous chapters have developed methods for optimizing single-objective functions, but this chapter is concerned with multiobjective optimization, or vector optimization, where we must optimize with respect to several objectives simultaneously. Engineering is often a tradeoff between cost, performance, and timeto-market, and it is often unclear how to prioritize different objectives. We will
discuss various methods for transforming vector-valued objective functions toscalar-valued objective functions so that we can use the algorithms discussed inprevious chapters to arrive at an optimum. In addition, we will discuss algorithms
for identifying the set of design points that represent the best tradeoff between
objectives, without having to commit to a particular prioritization of objectives.
These design points can then be presented to experts who can then identify themost desirable design.1

12.1 Pareto Optimality
The notion of Pareto optimality is useful when discussing problems where there
are multiple objectives. A design is Pareto optimal if it is impossible to improvein one objective without worsening at least one other objective. In multiobjective
design optimization, we can generally focus our efforts on designs that are Pareto
optimal without having to commit to a particular tradeoff between objectives.
This section introduces some definitions and concepts that are helpful when
discussing approaches to identifying Pareto-optimal designs.

Additional methods are surveyed
in R. T. Marler and J. S. Arora, “Survey of Multi-Objective Optimization Methods for Engineering,”
Structural and Multidisciplinary Optimization, vol. 26, no. 6, pp. 369–
395, 2004. For a textbook dedicatedentirely to multiobjective optimization, see K. Miettinen, Nonlinear
Multiobjective Optimization. Kluwer
Academic Publishers, 1999.
1

212

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

12.1.1 DominanceIn single-objective optimization, two design points x and x′ can be ranked objectively based on their scalar function values. The point x′ is better whenever f (x′ )is less than f (x).
In multiobjective optimization, our objective function f returns an m-dimensional
vector of values y when evaluated at a design point x. The different dimensionsof y correspond to different objectives, sometimes also referred to as metrics orcriteria. We can objectively rank two design points x and x′ only when one isbetter in at least one objective and no worse in any other. That is, x dominates x′ if
and only if
f i (x) ≤ f i (x′ ) for all i in {1, . . . , m}
(12.1)
and f i (x) < f i (x′ ) for some ias compactly implemented in algorithm 12.1.
dominates(y, y′) = all(y .≤ y′) && any(y .< y′)Figure 12.1 shows that in multiple dimensions there are regions with dominance ambiguity. This ambiguity arises whenever x is better in some objectives
and x′ is better in others. Several methods exist for resolving these ambiguities.
Single Objective

Multiple Objectivesf (x)yf (x′ ) < f (x )x′ is betterf (x′ ) > f (x )x′ is worse

y2

f(x)

f (x′ ) > f (x )x′ is worse

Algorithm 12.1. A method forchecking whether x dominates x′ ,where y is the vector of objective
values for f(x) and y′ is the vectorof objective values for f(x′ ).

Figure 12.1. Design points canbe objectively ranked in singleobjective optimization but canbe objectively ranked in multiobjective optimization only insome cases.

f (x′ ) < f (x )x′ is bettery1© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 1. p a re to op ti ma l i ty 213

12.1.2

Pareto Frontier

In mathematics, an image of an input set through some function is the set of
all possible outputs of that function when evaluated on elements of that input
set. We will denote the image of X through f as Y , and we will refer to Y as
the criterion space. Figure 12.2 shows examples of criterion space for problems
with single and multiple objectives. As illustrated, the criterion space in singleobjective optimization is one dimensional. All of the global optima share a single
objective function value, y∗ . In multiobjective optimization, the criterion space ism-dimensional, where m is the number of objectives. There is typically no globally
best objective function value because there may be ambiguity when tradeoffs
between objectives are not specified.
Single Objective

Multiple Objectives

y∗

y2

Y

y

Y

Figure 12.2. The criterion space isthe set of all objective values obtained by feasible design points.
Well-posed problems have criterion spaces that are bounded frombelow, but they do not have to bebounded from above. The Pareto
frontier is highlighted in dark blue.

y1

In multiobjective optimization, we can define the notion of Pareto optimality.
A design point x is Pareto-optimal when no point dominates it. That is, x ∈ X
is Pareto-optimal if there does not exist an x′ ∈ X such that x′ dominates x.
The set of Pareto-optimal points forms the Pareto frontier. The Pareto frontier isvaluable for helping decision-makers make design trade decisions as discussed inexample 12.1. In two dimensions, the Pareto frontier is also referred to as a Pareto
curve.
All Pareto-optimal points lie on the boundary of the criterion space. Some multiobjective optimization methods also find weakly Pareto-optimal points. Whereas
Pareto-optimal points are those such that no other point improves at least one ob© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

214

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

jective, weakly Pareto-optimal points are those such that no other point improves
all of the objectives (figure 12.3). That is, x ∈ X is weakly Pareto-optimal if there
does not exist an x′ ∈ X such that f(x′ ) < f(x). Pareto-optimal points are also
weakly Pareto optimal. Weakly Pareto-optimal points are not necessarily Pareto
optimal.
Several methods discussed below use another special point. We define theutopia point to be the point in the objective space consisting of the component-wise
optima:utopia= minimize f i (x)(12.2)yix∈X

The utopia point is often not attainable; optimizing one component typicallyrequires a tradeoff in another component.

y2

y1
Figure 12.3.
Weakly Paretooptimal points, shown in red,cannot be improved simultaneously in all objectives.

12.1.3 Pareto Frontier Generation
There are several methods for generating Pareto frontiers. A naive approachis to sample design points throughout the design space and then to identify
the nondominated points (algorithm 12.2). This approach is typically wasteful,leading to many dominated design points as shown in figure 12.4. In addition, thisapproach does not guarantee a smooth or correct Pareto frontier. The remainderof this chapter discusses more effective ways to generate Pareto frontiers.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 1. p a re to op ti ma l i ty 215

When constructing a collision avoidance system for aircraft, one must minimize both the collision rate and the alert rate. Although more alerts can resultin preventing more collisions if the alerts are followed, too many alerts canresult in pilots losing trust in the system and lead to decreased compliancewith the system. Hence, the designers of the system must carefully tradealerts and collision risk.

Example 12.1. An approximate
Pareto frontier obtained from
evaluating many different design
points for an aircraft collision
avoidance system.

Pareto dominated points(suboptimal)
collision ratecriterion space(denoted Y )IdealPareto Frontieralert rate

By varying the collision avoidance system’s design parameters, we canobtain many different collision avoidance systems, but, as the figure shows,some of these will be better than others. A Pareto frontier can be extracted
to help domain experts and regulators understand the effects that objective
tradeoffs will have on the optimized system.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

216 c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

Algorithm 12.2. A method forgenerating a Pareto frontier using
randomly sampled design points
xs and their multiobjective values
ys. Both the Pareto-optimal design
points and their objective values
are returned.

function naive_pareto(xs, ys)pareto_xs, pareto_ys = similar(xs, 0), similar(ys, 0)for (x,y) in zip(xs,ys)
if !any(dominates(y′,y) for y′ in ys)
push!(pareto_xs, x)
push!(pareto_ys, y)
end
end
return (pareto_xs, pareto_ys)
end

y2

12.2

Constraint Methods

Constraints can be used to cut out sections of the Pareto frontier and obtain asingle optimal point in the criterion space. Constraints can be supplied either
by the problem designer or automatically obtained based on an ordering of theobjectives.

12.2.1 Constraint Methody1Figure 12.4. Generating Pareto
frontiers with naively scatteredpoints is straightforward but inefficient and approximate.

The constraint method constrains all but one of the objectives. Here we choose f 1
without loss of generality:
minimizef 1 (x)subject tof 2 (x) ≤ c2x

f 3 (x) ≤ c3..
.

(12.3)f m (x) ≤ c mx∈XGiven the vector c, the constraint method produces a unique optimal pointin the criterion space, provided that the constraints are feasible. The constraint
method can be used to generate Pareto frontiers by varying c as shown in figure 12.5.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 2. c on stra i n t me thod s217

Figure 12.5. The constraint method
for generating a Pareto frontier.
This method can identify points inthe concave region of the Pareto
frontier.

y2c2 largeYc2 smally1

12.2.2 Lexicographic Method
The lexicographic method ranks the objectives in order of importance. A seriesof single-objective optimizations are performed on the objectives in order ofimportance. Each optimization problem includes constraints to preserve theoptimality with respect to previously optimized objectives as shown in figure 12.6.

minimizef 1 (x)

minimizef 2 (x)

minimizef 3 (x)subject tox∈Xsubject tof 1 (x) ≤ y1∗

subject tof 1 (x) ≤ y1∗

x

y1∗

x

x

f 2 (x) ≤ y2∗

x∈X

y2∗

Iterations are always feasible because the minimum point from the previous
optimization is always feasible. The constraints could also be replaced with equalities, but inequalities are often easier for optimizers to enforce. In addition, if the
optimization method used is not optimal, then subsequent optimizations may
encounter better solutions that would otherwise be rejected. The lexicographic
method is sensitive to the ordering of the objective functions.

x∈X

y3∗
Figure 12.6. The lexicographic
method for an optimization problem with three objectives.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

218 c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

12.3 Weight Methods
A designer can sometimes identify preferences between the objectives and encode
these preferences as a vector of weights. In cases where the choice of weights is not
obvious, we can generate a Pareto frontier by sweeping over the space of weights.
This section also discusses a variety of alternative methods for transforming
multiobjective functions into single-objective functions.

12.3.1 Weighted Sum Method
The weighted sum method (algorithm 12.3) uses a vector of weights w to convert f
to a single objective f :2
f (x ) = w⊤ f (x )(12.4)
where the weights are nonnegative and sum to 1. The weights can be interpreted
as costs associated with each objective. The Pareto frontier can be extracted byvarying w and solving the associated optimization problem with the objective inequation (12.4). In two dimensions, we vary w1 from 0 to 1, setting w2 = 1 − w1 .
This approach is illustrated in figure 12.7.

L. Zadeh, “Optimality and NonScalar-Valued Performance Criteria,” IEEE Transactions on AutomaticControl, vol. 8, no. 1, pp. 59–60,
1963.
2

Figure 12.7. The weighted sum
method used to generate a Pareto
frontier. Varying the weights allows us to trace the Pareto frontier.

Y
y2
w1
w1 = 0w2

y2

w1 = 1y1

In contrast with the constraint method, the weighted sum method cannot
obtain points in nonconvex regions of the Pareto frontier as shown in figure 12.8.

y1
Figure 12.8. The points in red are
Pareto optimal but cannot be obtained using the weighted sum
method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 3. w e i g ht me thod s

219

A given set of weights forms a linear objective function with parallel contour
lines marching away from the origin. If the feasible set bends away from theorigin, it will have other Pareto optimal points on the boundary that cannot berecovered by minimizing equation (12.4).
Algorithm 12.3. The weighted sum
method for generating a Pareto
frontier, which takes objective functions f1 and f2 and number of
Pareto points npts.

function weight_pareto(f1, f2, npts)
return [optimize(x->w1*f1(x) + (1-w1)*f2(x))
for w1 in range(0,stop=1,length=npts)]
end

12.3.2 Goal Programming
Goal programming3 is a method for converting a multiobjective function to a singleobjective function by minimizing an L p norm between f(x) and a goal point:
minimize f(x) − ygoalx∈Xp(12.5)

Goal programming generally
refers to using p = 1. An overview
is presented in D. Jones and M.
Tamiz, Practical Goal Programming.
Springer, 2010.
3

where the goal point is typically the utopia point. The equation above does not
involve a vector of weights, but the other methods discussed in this chapter can bethought of as generalizations of goal programming. This approach is illustrated
in figure 12.9.

12.3.3Weighted Exponential Sum

The weighted exponential sum combines goal programming and the weighted sum
method4mgoal pf (x) = ∑ wi f i (x) − y i(12.6)
i =1

where w is a vector of positive weights that sum to 1 and p ≥ 1 is an exponent
similar to that used in L p norms. As before, zero-valued weights can result in
weakly Pareto-optimal points.

P. L. Yu, “Cone Convexity, Cone
Extreme Points, and Nondominated Solutions in Decision Problems with Multiobjectives,” Journalof Optimization Theory and Applications, vol. 14, no. 3, pp. 319–377,
1974.
4© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

220 c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

Figure 12.9. Solutions to goal programming as the value for p ischanged.

y2

p=1
p=2
p=∞

ygoal
y1

The weighted exponential sum weighs each component of the distance between
the solution point and the goal point in the criterion space. Increasing p increases
the relative penalty of the largest coordinate deviation between f(x) and the goal
point. While portions of the Pareto-optimal set can be obtained by continuously
varying p, we are not guaranteed to obtain the complete Pareto frontier, and it isgenerally preferable to vary w using a constant p.

12.3.4 Weighted Min-Max Method
Using higher values of p with the weighted exponential sum objective tends
to produce better coverage of the Pareto frontier because the distance contours
are able to enter nonconvex regions of the Pareto frontier. The weighted min-max
method, also called the weighted Tchebycheff method, is the limit as p approaches
infinity:5h 
if (x) = max wiigoal
f i (x) − y i(12.7)The maximization can be removed by including an additionalparameter λ:

5The weighted min-max method can provide the complete Pareto-optimal set
by scanning over the weights but will also produce weakly Pareto-optimal points.
The method can be augmented to produce only the Pareto frontier
h 
i
goal
f (x) = max wi f i (x) − yi
+ ρ f(x)⊤ ygoal(12.8)i© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

minimizex,λλsubject to x ∈ X
w ⊙ f(x) − ygoal − λ1 ≤ 012. 4 . mu l ti obj e c ti ve p op u l a ti on me thod s

221where ρ is a small positive scalar with values typically between 0.0001 and 0.01.
The added term requires that all terms in ygoal be positive, which can be accomplished by shifting the objective function. By definition, f(x) ≥ ygoal for all
x. Any weakly Pareto-optimal point will have f(x)⊤ ygoal larger than a strongly
Pareto-optimal point closer to ygoal .

12.3.5 Exponential Weighted Criterion
The exponential weighted criterion6 was motivated by the inability of the weighted
sum method to obtain points on nonconvex portions of the Pareto frontier. It
constructs a scalar objective function according tomf (x) = ∑ (e pwi − 1)e p f i (x)(12.9)i =1

T. W. Athan and P. Y. Papalambros, “A Note on Weighted Criteria Methods for Compromise Solutions in Multi-Objective Optimization,” Engineering Optimization, vol. 27, no. 2, pp. 155–176,
1996.
6Each objective is individually transformed and reweighted. High values of p canlead to numerical overflow.

12.4

Multiobjective Population Methods

Population methods have also been applied to multiobjective optimization.7 We
can adapt the standard algorithms to encourage populations to spread over the
Pareto frontier.

Population methods are coveredin chapter 9.
712.4.1 Subpopulations
Population methods can divide their attention over several potentially competing
objectives. The population can be partitioned into subpopulations, where each
subpopulation is optimized with respect to different objectives. A traditional
genetic algorithm, for example, can be modified to bias the selection of individuals
for recombination toward the fittest individuals within each subpopulation. Those
selected can form offspring with individuals from different subpopulations.
One of the first adaptations of population methods to multiobjective optimization is the vector evaluated genetic algorithm8 (algorithm 12.4). Figure 12.10 shows
how subpopulations are used in a vector evaluated genetic algorithm to maintain
diversity over multiple objectives. The progression of a vector evaluated genetic
algorithm is shown in figure 12.11.

8
J. D. Schaffer, “Multiple Objective
Optimization with Vector Evaluated Genetic Algorithms,” in International Conference on Genetic Algorithms and Their Applications, 1985.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

222

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

population

parent pairs

subpopulations

new population

1

Figure 12.10. Using subpopulations in a vector evaluated genetic
algorithm.

2
select m subpopulations..
.

shufflecrossover andmutationmfunction vector_evaluated_genetic_algorithm(f, population,
k_max, S, C, M)
m = length(f(population[1]))m_pop = length(population)m_subpop = m_pop ÷ m
for k in 1 : k_max
ys = f.(population)
parents = select(S, [y[1] for y in ys])[1:m_subpop]
for i in 2 : m
subpop = select(S,[y[i] for y in ys])[1:m_subpop]
append!(parents, subpop)
end

Algorithm 12.4.
The vector
evaluated genetic algorithm,
which takes a vector-valued
objective function f, an initial
population, number of iterations
k_max, a SelectionMethod S,
a CrossoverMethod C, and a
MutationMethod M. The resulting
population is returned.

p = randperm(2m_pop)
p_ind=i->parents[mod(p[i]-1,m_pop)+1][(p[i]-1)÷m_pop + 1]
parents = [[p_ind(i), p_ind(i+1)] for i in 1 : 2 : 2m_pop]
children = [crossover(C,population[p[1]],population[p[2]])for p in parents]
population = [mutate(M, c) for c in children]

end

end
return population© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 4 . mu l ti obj e c ti ve p op u l a ti on me thod s

Gen 3

Gen 2

Gen 1

223

Gen 4

2

y2

1.5
1
0.5
0

0

0.5

1
y1

1.5

2

0

0.5

1
y1

1.5

2

0

0.5

1
y1

1.5

12.4.2 Nondomination Ranking
One can compute naive Pareto frontiers using the individuals in a population.
A design point that lies on the approximate Pareto frontier is considered better
than a value deep within the criterion space. We can use nondomination ranking(algorithm 12.5) to rank individuals according to the following levels:9
Level 1. Nondominated individuals in the population.
Level 2. Nondominated individuals except those in Level 1.

2

0

0.5

1
y1

1.5

2

Figure 12.11. A vector evaluated genetic algorithm applied tothe circle function defined in appendix B.8. The Pareto frontier isshown in blue.

9
K. Deb, A. Pratap, S. Agarwal, andT. Meyarivan, “A Fast and Elitist
Multiobjective Genetic Algorithm:
NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2,
pp. 182–197, 2002.

Level 3. Nondominated individuals except those in Levels 1 or 2.
..
.

Level k. Nondominated individuals except those in Levels 1 to k − 1.

Level 1 is obtained by applying algorithm 12.2 to the population. Subsequentlevels are generated by removing all previous levels from the population andthen applying algorithm 12.2 again. This process is repeated until all individuals
have been ranked. An individual’s objective function value is proportional to its
rank.
The nondomination levels for an example population are shown in figure 12.12.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

224

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

function get_non_domination_levels(ys)L, m = 0, length(ys)levels = zeros(Int, m)
while minimum(levels) == 0
L += 1for (i,y) in enumerate(ys)if levels[i] == 0 &&!any((levels[i] == 0 || levels[i] == L) &&dominates(ys[i],y) for i in 1 : m)levels[i] = L
end
end
end
return levels
end

Algorithm 12.5. A function for getting the nondomination levels ofan array of multiobjective function
evaluations, ys.

Figure 12.12. The nondominationlevels for a population. Darker levels have lower (better) rankings.

y2

Level 10

Level 1

Level 2y1

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 4 . mu l ti obj e c ti ve p op u l a ti on me thod s 225

12.4.3

Pareto Filters

Population methods can be augmented with a Pareto filter, which is a populationthat approximates the Pareto frontier.10 The filter is typically updated with every
generation (algorithm 12.7). Individuals in the population that are not dominatedby any individuals in the filter are added. Any dominated points in the filter are
removed. Individuals from the Pareto filter can be injected into the population,
thereby reducing the chance that portions of the Pareto frontier are lost between
generations.
The filter often has a maximum capacity.11 Filters that are overcapacity can be
reduced by finding the closest pair of design points in the criterion space andremoving one individual from that pair. This pruning method is implemented
in algorithm 12.6. A Pareto filter obtained using a genetic algorithm is shown infigure 12.13.
function discard_closest_pair!(xs, ys)
index, min_dist = 0, Inf
for (i,y) in enumerate(ys)for (j, y′) in enumerate(ys[i+1:end])
dist = norm(y - y′)
if dist < min_dist
index, min_dist = rand([i,j]), dist
end
end
end
deleteat!(xs, index)
deleteat!(ys, index)
return (xs, ys)
end

10
H. Ishibuchi and T. Murata,“A Multi-Objective Genetic Local
Search Algorithm and Its Application to Flowshop Scheduling,”
IEEE Transactions on Systems, Man,
and Cybernetics, vol. 28, no. 3,
pp. 392–403, 1998.

Typically the size of the population.

11

Algorithm 12.6.

The method

discard_closest_pair! is used toremove one individual from a filter that is above capacity. The
method takes the filter’s list of design points xs and associated objective function values ys.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

226 c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

function update_pareto_filter!(filter_xs, filter_ys, xs, ys;
capacity=length(xs),)
for (x,y) in zip(xs, ys)
if !any(dominates(y′,y) for y′ in filter_ys)
push!(filter_xs, x)
push!(filter_ys, y)
end
end
filter_xs, filter_ys = naive_pareto(filter_xs, filter_ys)
while length(filter_xs) > capacity
discard_closest_pair!(filter_xs, filter_ys)
end
return (filter_xs, filter_ys)
end

Algorithm 12.7. A method for
updating a Pareto filter withdesign points filter_xs, corresponding objective function values
filter_ys, a population withdesign points xs and objectivefunction values ys, and filter
capacity capacity which defaults
to the population size.

Figure 12.13. A Pareto filter usedon the genetic algorithm in figure 12.11 to approximate the Pareto
frontier.

1.5

y2

1

0.5

0

0

0.5

1

1.5

y1

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 4 . mu l ti obj e c ti ve p op u l a ti on me thod s

227

12.4.4 Niche Techniques
The term niche refers to a focused cluster of points, typically in the criterion space,as shown in figure 12.14. Population methods can converge on a few niches, which
limits their spread over the Pareto frontier. Niche techniques help encourage aneven spread of points.
In fitness sharing,12 shown in figure 12.15, an individual’s objective values are
penalized by a factor equal to the number of other points within a specified
distance in the criterion space.13 This scheme causes all points in a local region toshare the fitness of the other points within the local region. Fitness sharing canbe used together with nondomination ranking and subpopulation evaluation.
Equivalence class sharing can be applied to nondomination ranking. When comparing two individuals, the fitter individual is first determined based on the
nondomination ranking. If they are equal, the better individual is the one withthe fewest number of individuals within a specified distance in the criterion space.
Another niche technique has been proposed for genetic algorithms in which
parents selected for crossover cannot be too close together in the criterion space.
Selecting only nondominated individuals is also recommended.14
1.5

y2

y1
Figure 12.14. Two clear niches fora population in a two-dimensional
criterion space.
Fitness is inversely related to theobjective being minimized.

1213
D. E. Goldberg and J. Richardson,“Genetic Algorithms with Sharing
for Multimodal Function Optimization,” in International Conference on
Genetic Algorithms, 1987.

S. Narayanan and S. Azarm,“On Improving Multiobjective Genetic Algorithms for Design Optimization,” Structural Optimization,
vol. 18, no. 2-3, pp. 146–155, 1999.
14

Figure 12.15. The results of applying fitness sharing to the Pareto filter in figure 12.13, thereby significantly improving its coverage.

y2

1

0.5

0

0

0.5

1

1.5

y1

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

228 c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

12.5 Preference Elicitation
Preference elicitation involves inferring a scalar-valued objective function frompreferences of experts about the tradeoffs between objectives.15 There are manydifferent ways to represent the scalar-valued objective function, but this section
will focus on the weighted sum model where f (x) = w⊤ f(x). Once we identify
a suitable w, we can use this scalar-valued objective function to find an optimal
design.

12.5.1 Model Identification
A common approach for identifying the weight vector w in our preference model
involves asking experts to state their preference between two points a and b in thecriterion space Y (figure 12.16). Each of these points is the result of optimizing
for a point on the Pareto frontier using an associated weight vector wa and wb .
The expert’s response is either a preference for a or a preference for b. There areother schemes for eliciting preference information, such as ranking points in thecriterion space, but this binary preference query has been shown to pose minimal
cognitive burden on the expert.16

This chapter overviews nonBayesian approaches to preference
elicitation. For Bayesian approaches, see: S. Guo and S.
Sanner, “Real-Time Multiattribute
Bayesian Preference Elicitation
with
PairwiseComparison
Queries,” in International Conference on Artificial Intelligenceand Statistics (AISTATS), 2010.
J. R. Lepird, M. P. Owen, and
M. J. Kochenderfer, “Bayesian
Preference Elicitation for Multiobjective Engineering Design
Optimization,” Journal of Aerospace
Information Systems, vol. 12, no. 10,
pp. 634–645, 2015.
15

V. Conitzer, “Eliciting SinglePeaked Preferences Using Comparison Queries,” Journal of Artificial Intelligence Research, vol. 35, pp. 161–
191, 2009.
16

Figure 12.16. Preference elicitation schemes often involve asking
experts their preferences between
two points in the criterion space.

y1

y2

y3

y4

y5

y1

y2

a

y3

y4

y5

b

Suppose the outcomes of the expert queries have resulted in a set of criterion
pairs
n
o

( a(1) , b(1) ) , . . . , ( a( n ) , b( n ) )(12.10)where a(i) is preferable to b(i) in each pair. For each of these preferences, theweight vector must satisfyw⊤ a(i) < w⊤ b(i) =⇒ (a(i) − b(i) )⊤ w < 0(12.11)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 5 . p re fe re n c e e l i c i ta ti on 229

In order to be consistent with the data, the weight vector must satisfy(i )(i ) ⊤(a − b ) w < 0 for all i in {1, . . . , n}
1⊤ w = 1(12.12)w≥0

Many different weight vectors could potentially satisfy the above equation.
One approach is to choose a w that best separates w⊤ a(i) from w⊤ b(i)nminimizew

subject to∑ ( a( i ) − b( i ) ) ⊤ w

i =1
(i )

(a

− b(i) )⊤ w < 0 for i ∈ {1, . . . , n}

1⊤ w = 1(12.13)w≥0

It is often desirable to choose the next weight vector such that it minimizes the
distance from the previous weight vector. We can replace the objective function inequation (12.13) with kw − w(n) k1 , thereby ensuring that our new weight vectorw(n+1) is as close as possible to our current one.17

12.5.2Paired Query Selection

We generally want to choose the two points in the criterion space so that theoutcome of the query is as informative as possible. There are many different
approaches for such paired query selection, but we will focus on methods that
attempt to reduce the space of weights consistent with expert responses, preference
information supplied by a domain expert.
We will denote the set of weights consistent with expert responses as W ,which is defined by the linear constraints in equation (12.12). Because weights
are bounded between 0 and 1, the feasible set is an enclosed region forming a
convex polytope with finite volume. We generally want to reduce the volume of
W in as few queries as possible.
Q-Eval18 , shown in figure 12.17, is a greedy elicitation strategy that heuristicallyseeks to reduce the volume of W as quickly as possible with each iteration. It
chooses the query that comes closest to bisecting W into two equal parts. The
method operates on a finite sampling of Pareto-optimal design points. The procedure for choosing a query pair is:

The previous weight vector
may or may not be consistent
with the added constraint(a(n) − b(n) )⊤ w < 0.
17

V. S. Iyengar, J. Lee, and M.
Campbell, “Q-EVAL: Evaluating
Multiple Attribute Items Using
Queries,” in ACM Conference on
Electronic Commerce, 2001.
18© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

230

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

1. Compute the prime analytic center c of W , which is the point that maximizes
the sum of the logarithms of the distances between itself and the closest pointon each nonredundant constraint in W :nc = arg max ∑ ln (b(i) − a(i) )⊤ w
w∈W

(12.14)i =1

2. Compute the normal distance from the bisecting hyperplane between eachpair of points and the center.
3. Sort the design-point pairs in order of increasing distance.
4. For each of the k hyperplanes closest to c, compute the volume ratio of the two
polytopes formed by splitting W along the hyperplane.
5. Choose the design-point pair with split ratio closest to 1.
Set of Consistent Weights W

w2

Analytic Center and Bisecting Hyperplane

w2

w2

wa c

W

w1

Two Regions under Query a vs. b

wb

w1

The polyhedral method19 works by approximating W with a bounding ellipsoid

centered at the analytic center of W as shown in figure 12.18. Queries are designed
to partition the bounding ellipsoid into approximately equal parts and to favor
cuts that are perpendicular to the longest axis of the ellipsoid to reduce both
uncertainty and to balance the breadth in each dimension.

12.5.3 Design Selection
The previous section discussed query methods that select query pairs for efficiently reducing the search space. After query selection is complete, one muststill select a final design. This process is known as design selection.

w1
Figure 12.17. Visualizations of the
Q-Eval greedy elicitation strategy.
The figure progression shows theinitial set of weights W consistent
with previous preferences, a pairof weight vectors and their corresponding bisecting hyperplane,
and the two polytopes formed by
splitting along the bisecting hyperplane. The algorithm considers all possible pairs from a finite
sampling of Pareto-optimal design
points and chooses the query thatmost evenly splits W .

19
D. Braziunas and C. Boutilier,“Elicitation of Factored Utilities,”
AI Magazine, vol. 29, no. 4, pp. 79–
92, 2009.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.

2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 5 . p re fe re n c e e l i c i ta ti on 231

w2
wa
Figure 12.18.
The polyhedral
method uses a bounding ellipsoidfor W .

wb

w1
One such method, decision quality improvement,20 is based on the idea that if
we have to commit to a particular weight, we should commit to the one for which
the worst-case objective value is lowest:x∗ = arg min max w⊤ f(x)
x∈X

w∈W

(12.15)This minimax decision is robust because it provides an upper bound on the objective
value.
The minimax regret21 instead minimizes the maximum amount of regret theuser can have when selecting a particular design:x∗ = arg min max max w⊤ f(x) − w⊤ f(x′ )w∈W x′ ∈X
x∈X
{z
}
|

(12.16)maximum regret

20
D. Braziunas and C. Boutilier,“Minimax Regret-Based Elicitationof Generalized Additive Utilities,”in Conference on Uncertainty in Artificial Intelligence (UAI), 2007.

C. Boutilier, R. Patrascu, P.
Poupart, and D. Schuurmans,“Constraint-Based Optimizationand Utility Elicitation Using the
Minimax Decision Criterion,”
Artificial Intelligence, vol. 170,
no. 8-9, pp. 686–713, 2006.
21

where w⊤ f(x) − w⊤ f(x′ ) is the regret associated with choosing design x insteadof design x′ under the preference weight vector w. Minimax regret can be viewed
as accounting for the decision system’s uncertainty with respect to the designer’strue utility function.
The minimax regret can be used as stopping criteria for preference elicitation
strategies. We can terminate the preference elicitation procedure once the minimax
regret drops below a certain threshold.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

232

c ha p te r 12. mu l ti obj e c ti ve op ti mi z a ti on

12.6 Summary• Design problems with multiple objectives often involve trading performance
between different objectives.
• The Pareto frontier represents the set of potentially optimal solutions.
• Vector-valued objective functions can be converted to scalar-valued objectivefunctions using constraint-based or weight-based methods.
• Population methods can be extended to produce individuals that span the
Pareto frontier.
• Knowing the preferences of experts between pairs of points in the criterion
space can help guide the inference of a scalar-valued objective function.

12.7

Exercises

Exercise 12.1. The weighted sum method is a very simple approach, and it is indeed used by engineers for multiobjective optimization. What is one disadvantageof the procedure when it is used to compute the Pareto frontier?
Exercise 12.2. Why are population methods well-suited for multiobjective optimization?
Exercise 12.3. Suppose you have the points {[1, 2], [2, 1], [2, 2], [1, 1]} in the criterion space and you wish to approximate a Pareto frontier. Which points are Pareto
optimal with respect to the rest of the points? Are any weakly Pareto-optimal
points?
Exercise 12.4. Multiobjective optimization is not easily done with second-ordermethods. Why is this the case?
Exercise 12.5. Consider a square criterion space Y with y1 ∈ [0, 1] and y2 ∈ [0, 1].
Plot the criterion space, indicate the Pareto-optimal points, and indicate the weakly
Pareto optimal points.
Exercise 12.6. Enforcing w ≥ 0 and kwk1 = 1 in the weighted sum method
is not sufficient for Pareto optimality. Give an example where coordinates withzero-valued weights find weakly Pareto-optimal points.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

12. 7. e x e rc i se s 233

Exercise 12.7. Provide an example where goal programming does not produce a
Pareto-optimal point.
Exercise 12.8. Use the constraint method to obtain the Pareto curve for the optimization problem:
minimize [ x2 , ( x − 2)2 ](12.17)x

Exercise 12.9. Suppose we have a multiobjective optimization problem where
the two objectives are as follows:f 1 ( x ) = −( x − 2) sin( x )2f 2 ( x ) = −( x + 3) sin( x )(12.18)(12.19)With x ∈ {−5, −3, −1, 1, 3, 5}, plot the points in the criterion space. How many
points are on the Pareto frontier?

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com