Multi-Objective Optimization
How to optimize
multiple
objectives?
Build Pareto-Front
INTRODUCTION
• We often have more than one objective
• When a change in design variable can affect opposite way
of different objectives
Which one is optimum?
What’s the definition of optimum?
f 1 , f2 1/Q
$$
$$
1
4 4
Pareto-frontier
3
2
3
Design 2 1 1/Q
218
Structural & Multidisciplinary Optimization Group
INTRODUCTION cont.
• This means that design points are no longer arranged in
strict hierarchy
• There are points that are clearly poorer than others
because all objectives are worse
• In optimization jargon we call these points dominated
• Points that are not dominated are called non-dominated or
Pareto optimal
219
Structural & Multidisciplinary Optimization Group
MULTI-OBJECTIVE DESIGN STRATEGY
• Vector of objective functions
F f1(b) f2 (b ) fm (b )
• In multi-objective optimization, objective functions are
competing each other
– We cannot improve one objective without deteriorating others
• We can combine them using weights, but often don’t know
them
f (b ) w1f1(b) w 2f2 (b) w m fm (b)
• Need to explore all possible combinations of competing
objectives
220
Structural & Multidisciplinary Optimization Group
MULTI-OBJECTIVE OPTIMIZATION
• Problem formulation
Minimize F(b )
subject to hi (b) 0
g j (b) 0
bL b bU
• If any objectives are competing, there is no unique solution
• Non-inferior solution: an improvement in one objective
requires a degradation of another
• The set of non-inferior solutions is called Pareto front
221
Structural & Multidisciplinary Optimization Group
EXAMPLE: DOMINATION
• We have two objectives that are to be minimized. The
following are the pairs of objectives at 10 design points.
Identify the dominated ones.
(67,71), (48,72), (29,88), (-106, 294), (32,13)
(-120,163), (103,-30), (-78,114), (-80,143), (75,-171)
300
200
100
-100
-200
-150 -100 -50 0 50 100 150
222
Structural & Multidisciplinary Optimization Group
EXAMPLE: DOMINATION
• Work choice: Minimize time and maximize fun so that you
make $100. Will need between 33.3 to 100 items. Time can
vary from 66.7 minutes to 300. Fun can vary between 33.3
and 300.
Item (task) Pay ($) Time (min) Fun index
1 1 3 3
2 2 5 1
3 1 2 2
4 3 2 1
Task 2 is dominated by Task 4!
223
Structural & Multidisciplinary Optimization Group
MULTI-OBJECTIVE FORMULATION
• Problem formulation
Minimize time 3b1 2b3 2b4
Maximize fun 3b1 2b3 b4
subject to pay b1 b3 3b4 100
bi 0
• Pay constraint in standard normalized form
1 (b1 b3 3b4 ) / 100 0 Item Pay Time Fun
• Common sense constraints 1 1 3 3
2 2 5 1
b1 100, b3 100, b4 33.3
3 1 2 2
4 3 2 1
224
Structural & Multidisciplinary Optimization Group
SOLUTION BY ENUMERATION
• In the range of three variables calculate time and fun for all
combinations that produce exactly $100.
• Pareto front is upper boundary and it is almost a straight
line.
• Matlab results
300
250
200
fun
150
100
50
0
50 100 150 200 250 300
time
225
Structural & Multidisciplinary Optimization Group
EXERCISE: PAY-FUN PROBLEM
• Formulate the problem of maximizing fun and pay for five
hours (300 minutes) including only non-dominated
variables.
• Obtain the Pareto front analytically or by enumeration and
writes its equation (fun as a function of pay).
226
Structural & Multidisciplinary Optimization Group
MORE EFFICIENT SOLUTION METHODS
• Methods that try to avoid generating the Pareto front
– Generate “utopia point”
– Define optimum based on some measure of distance from utopia
point
• Generating entire Pareto front
– Weighted sum of objectives with variable coefficients
– Optimize one objective for a range of constraints on the others
– Niching methods with population based algorithms
227
Structural & Multidisciplinary Optimization Group
EXAMPLE: UTOPIA POINT
• The utopia point is (66.7,300).
• One approach is to use it to form a compromise objective
time 300
Minimize
66.7 fun 300
250
• It gives
time=168 minutes, 200
fun=160 fun 150
(b1=0, b3=76,b4=8)
100
50
0
50 100 150 200 250 300
time
228
Structural & Multidisciplinary Optimization Group
SERIES OF CONSTRAINTS
Minimize time 3b1 2b3 2b4
subject to pay b1 b3 3b4 100
fun 3b1 2b3 b4 funk k 1,2,
bi 0
The next slides provides a Matlab segment for solving
this optimization problem using the function fmincon, but
without the requirement of integer variables.
How will you change the formulation so that a single
Matlab run will give us results for any required earning
level R?
229
Structural & Multidisciplinary Optimization Group
MATLAB SEGMENT
b0 = [10 10 10];
for fun_idx = [Link]
A = [-1 -1 -3; -3 -2 -1]; c = [-100;-fun_idx];
lb = zeros(3,1);
options = optimset('Display','off');
[b,fval,exitflag,output,lambda] =
fmincon('myfun’,b0,A,c,[],[],lb,[],[],options);
pareto_sol(fun_idx,:) = b;
pareto_fun(fun_idx,1) = fval;
pareto_fun(fun_idx,2) = 3*b(1) + 2*b(2) + b(3);
end
function f = myfun(b)
f = 3*b(1) + 2*b(2) + 2*b(3);
230
Structural & Multidisciplinary Optimization Group
EXERCISE: PARETO-FRONT
• Generate the Pareto front for the pay and fun maximization
using a series of constraints, and also find a compromise
point on it using the utopia point.
• What is responsible for the slope discontinuity in the Pareto
front on Slide 10?
231
Structural & Multidisciplinary Optimization Group
EXAMPLE
• Minimize time & maximize fun while you make at least $100
• Will need between 33.3 to 100 items
• Fun can vary between 33.3. Try first for 150
Item Pay ($) Time (min) Fun index
1 1 3 3
2 2 4 2
3 1 2 2
4 3 2 1
• Multi-objective optimization formulation
Minimize time 3b1 4b2 2b3 2b4
Maximize fun 3b1 2b2 2b3 b4
subject to pay b1 2b2 b3 3b4 100
232
Structural & Multidisciplinary Optimization Group
EXAMPLE
f1=zeros(1,100000);
f2=zeros(1,100000);
k=1; 400
for i1=[Link] 350
for i2=[Link]
for i3=[Link] 300
for i4=[Link]
250
pay=i1+2*i2+i3+3*i4;
Fun Index
if pay >= 100 200
f1(k)=3*i1+4*i2+2*i3+2*i4; Increase time
150
f2(k)=3*i1+2*i2+2*i3+i4; Increase fun
k=k+1; 100
end
50
end
end 0
0 100 200 300 400 500 600
end Time
end
k=k-1
plot(f1(1:k),f2(1:k),'b.');
233
Structural & Multidisciplinary Optimization Group
PARETO OPTIMALITY
• Point is a non-inferior solution if for some
*
b
neighborhood of b* there does not exist a Db such that
(b * b ) f (b* b ) f (b* ) i 1,, m
i i
f j (b* b ) f j (b* ) for some j
f1
b1
Non-inferior
C solutions
Feasible f1A A
set f1B B f1B f1A
D f2B f2A
b2
f2A f2B f2
• Multi-objective optimization: generation and selection of
non-inferior solution points
234
Structural & Multidisciplinary Optimization Group
SOLUTION METHODS
• Methods that try to avoid generating the Pareto front
– Generate “utopia point”
– Define optimum based on some measure of distance from utopia
point
• Generating entire Pareto front
– Weighted sum of objectives with variable coefficients
– Optimize on objective for a range of constraints on the others
– Niching methods with population based algorithms
235
Structural & Multidisciplinary Optimization Group
WEIGHTED SUM METHOD
• Convert F(b) to a scalar objective function using weights
m
Minimize f (b ) w i fi (b )
i 1
• By changing wi, different Pareto optimum points can be
found
f1
A Pareto front
f2
w1f1 + w2f2 = constant Problem with non-convex front
236
Structural & Multidisciplinary Optimization Group
EPSILON-CONSTRAINT METHOD
• Optimize a primary objective fp(b), while other objectives
are considered as constraints
f1
Minimize fp (b )
subject to fi (b) i , i p
f1s
2 f2
• Can find non-convex front
• If e2 is too small, there is no feasible point
237
Structural & Multidisciplinary Optimization Group
GOAL ATTAINMENT METHOD
• Try to achieve the design goal f* using weighted relaxation
Minimize
subject to fi (b) w i fi *
• Geometrically, starting from P = f*, find a feasible point in
the direction of w
f1 w
w = [w1, w2, …, wm] : weight
wig : slackness
f1 *
P
f2* f2
238
Structural & Multidisciplinary Optimization Group
MATLAB EXAMPLE
• Multiobjective optimization using the genetic algorithm
Minimize F(b ) [f1(b ), f2 (b )]
where f1( b ) ( b 2)2 10
f2 (b ) (b 2)2 20
1.5 b
239
Structural & Multidisciplinary Optimization Group
MATLAB EXAMPLE
function y = simple_multiobjective(b)
y(1) = (b+2)^2 - 10;
y(2) = (b-2)^2 + 20;
Fitness = @simple_multiobjective;
NV = 1; lb = -1.5; ub = 0;
options = gaoptimset('PlotFcns',{@gaplotpareto,@gaplotscorediversity});
gamultiobj(Fitness, NV,[],[],[],[],lb, ub, options);
240
Structural & Multidisciplinary Optimization Group
Elitist Non-dominated Sorting
Genetic Algorithm: NSGA-II
Multi-objective optimization problem
• Problems with more than one objective – typically
conflicting objectives
– Cars: Luxury vs. price
• Mathematical formulation
•
– where 𝐅 𝐛 𝑓 , 𝑖 1, ⋯ , 𝑀
𝐛 𝑏 , 𝑗 1, ⋯ , 𝑁
• Subject to
–𝐠 𝐛 0, 𝐠 𝑔 ,𝑘 1, ⋯ 𝑃
–𝐡 𝐛 0, 𝐡 ℎ ,𝑙 1, ⋯ 𝑄
242
Structural & Multidisciplinary Optimization Group
PARETO OPTIMAL FRONT
• Many optimal solution
• Usual approaches: weighted sum strategy, multiple-
constraints modeling
• Alternative: Multi-objective GA
Min f2
• Algorithm requirements:
– Convergence
– Spread
Min f1 243
Structural & Multidisciplinary Optimization Group
RANKING
• Children and parents are combined.
• Non-dominated points belong to first rank.
• The non-dominated solutions from the remainder are in
second rank, and so on.
f2
f1
244
Structural & Multidisciplinary Optimization Group
ELITISM
• Elitism: Keep the best individuals from the parent and child
population f2
Parent
Child
f1
245
Structural & Multidisciplinary Optimization Group
NICHING FOR LAST RANK
• Niching is an operator that gives preference to solutions
that are not crowded f2
• Crowding distance
c=a+b
• End points have infinite
crowding distance
• Solutions from last rank are a
selected based on niching
b
f1
246
Structural & Multidisciplinary Optimization Group
Flowchart of NSGA-II
Begin: initialize Evaluate objective Rank
population (size N) functions population
Child population created
Selection
Crossover
Report final
population and
Mutation
Stop
No
Evaluate objective
function
Stopping Elitism
criteria
Yes met? Combine parent and
Select N child populations,
individuals rank population
247
Structural & Multidisciplinary Optimization Group
Elitism process
248
Structural & Multidisciplinary Optimization Group
Problems NSGA-II
• Sort all the individuals in slide 263 into ranks, and denote
the rank on the figure in the slide next to the individual.
• Describe how the 10 individuals were selected, and check if
any individuals were selected based on crowding distance.
249
Structural & Multidisciplinary Optimization Group
Example: Bicycle frame design
• Objectives
– Minimize area
– Minimize max. deflection
• Constraints
– Components should be a
valid geometry
– Max. stress Allowable stress
𝜎 𝜎
– Max. deflection Allowable deflection
𝛿 𝛿
250
Structural & Multidisciplinary Optimization Group
Problem modeling
• Shapes are represented by binary strings, where ‘0’
represents void region and ‘1’ represents material region
• Example : A typical binary string is
01110 11111 10001 11111
Left to right representation Shape corresponding to binary string
251
Structural & Multidisciplinary Optimization Group
Material properties and GA parameters
• Material Properties
– Yield Stress 𝜎 140 MPa
– Max Deflection 𝛿 5 mm
– Young’s Modulus 𝐸 80GPa
– Poisson’s Ratio 𝜈 0.25
• GA Parameters
– Binary String Size 𝐿 14x9
– Population Size 30
– Crossover Probability 0.95
– Mutation Probability 1/L
– # of Generations 150
252
Structural & Multidisciplinary Optimization Group
Pareto optimal front
• Small increase in
weight leads to a large
drop in deflection
• Similarly small change
in deflection allows
significant reduction
of the weight
253
Structural & Multidisciplinary Optimization Group
Optimal shapes
Different conceptual designs can be found!
254
Structural & Multidisciplinary Optimization Group
Some more engineering applications
• Structural designs of mechanical components
• Design of turbo-machinery components
• Bioinformatics – protein unfolding
• VLSI circuit designs
• Packaging
• …
255
Structural & Multidisciplinary Optimization Group
Other related topic of interest
• Real-coded genetic algorithms
• Other multi-objective evolutionary algorithms
– Pareto archived evolutionary strategies (PAES)
– Strength Pareto evolutionary algorithm (SPEA)
– 𝜖–multi-objective evolutionary algorithm (𝜖-MOEA)
• Hybrid GAs
• Particle swarm algorithms
• Ant colony optimization
256
Structural & Multidisciplinary Optimization Group
Constrained Particle Swarm
Optimization
Is animal
behavior
optimized?
Learn from the
social behavior of
a bird flock or fish
PARTICLE SWARM OPTIMIZATION
• Mimicking social behavior of insects or birds
258
Structural & Multidisciplinary Optimization Group
CONSTRAINED PARTICLE SWARM OPTIMIZATION
• Based on Venter, G. and Haftka, R.T., (2010), Structural
and Multidisciplinary Optimization, Vol. 40(1-6), 65-76.
• Lecture will cover particle swarm optimization, a good
global search algorithm for continuous problems.
• Constraints are treated using a bi-objective approach that
minimizes both the objective function and a measure of the
violation of the constraints.
259
Structural & Multidisciplinary Optimization Group
PARTICLE SWARM OPTIMIZATION
• Based on a simplified social model: swarm adapts to
underlying environment by returning to promising regions
previously found
• Robust algorithm
• Global optimizer
• Easy to implement
• Parameter tuning
• High computational cost
• Unconstrained algorithm
260
Structural & Multidisciplinary Optimization Group
ALGORITHM OVERVIEW
261
Structural & Multidisciplinary Optimization Group
MOVING TOWARDS PERSONAL BEST AND GROUP BEST
xik position of ith particle in kth step
pi best past position of ith particle
p kg best current position of swarm
YouTube visualization [Link]/watch?v=_Y4A8Q2j0wA
262
Structural & Multidisciplinary Optimization Group
EXERCISE: PARTICLE SWAM OPTIMIZATION
• Minimize the Rosenbrock Banana function using PSO
starting with 30 particles distributed randomly in the region -
. Use
.
263
Structural & Multidisciplinary Optimization Group
WHAT IS BEST WHEN CONSTRAINTS ARE PRESENT?
• Constrained optimization problem
Minimize f (b )
subject to g j ( x ) 0 j 1,, K
• Penalty function approach
K
f (b ) f (b ) max(0, g j (b ))
j 1
• Not easy to pick good w
• Creates canyons in design space that can trap swarm
264
Structural & Multidisciplinary Optimization Group
BI-OBJECTIVE OR FILTER APPROACH
• Replace
K
f (b ) f (b ) max(0, g j (b ))
j 1
• By
Minimize f (b )
K
Minimize h(b ) max(0, g j (b))
j 1
• Fletcher R., Leyffer, S. (2002) Nonlinear programming
without a penalty function, Math Program 91(2);239-269
• Advantage is in allowing less constrained search in design
space.
265
Structural & Multidisciplinary Optimization Group
MULTI-OBJECTIVE PSO
• The bi-objective formulation requires a multi-objective PSO
(MOPSO)
• Each iteration has multiple equally good “leaders”, non-
dominated solutions
• Based on general algorithm by Reyes-Sierra and Coello
Coello (2005)
• Create archive of non-dominated solutions
• Select leader for each particle based on a binary
tournament
• Makes use of the crowding distance to maintain and select
leaders
266
Structural & Multidisciplinary Optimization Group
CROWDING DISTANCE
• First sort non-dominated points by objective function
values.
• Crowding distance of point i is the distance between two
nearest neighbors (i-1, to i+1)
267
Structural & Multidisciplinary Optimization Group
EXAMPLE: MOPSO
• MOPSO with two objective functions
f1(b ) b 2 f2 (b ) (b 2)2 b 100,100
With this large range
of b, how come the
two objectives have
such small values?
268
Structural & Multidisciplinary Optimization Group
EXERCISE: CROWDING DISTANCE
• Generate 100 random b values in [0,2] and the
corresponding values of f1(b) and f2(b) of the functions on
the previous slide. Choose a point with the maximum
crowding distance, then the next point with the maximum
crowding distance, and so on until you reach 20 points. Plot
the resulting Pareto front. Why is it the Pareto front?
269
Structural & Multidisciplinary Optimization Group
CONSTRAINT SPECIALIZED BI-OBJECTIVE PSO
• We are not interested in complete Pareto front, but mostly
in part that has low constraint violations.
• Bias algorithm to such points
– Select leaders based on both constraint violation and crowding
distance
– Binary tournament based on
constraint violation
• Goal is to place more particles
near feasible domain
270
Structural & Multidisciplinary Optimization Group
EXAMPLE
• Composite laminate design (q1/q2/q3)s, with three angles
and three thicknesses as design variables.
– Maximize the transverse in-plane stiffness A22
– Constraints on ply angles and effective Poisson’s ratio
• Methods compared
– Standard PSO with penalty function
– MOPSO algorithm of Reyes-Sierra and Coello-Coello
– Modified MOPSO algorithm
• 100 runs, each with 30 particles and 100 generations.
• 10% probability of mutation, w = 0.5, c1 = 1.75, c2 = 2.25
271
Structural & Multidisciplinary Optimization Group
OPTIMIZATION FORMULATION
• See relation between stiffness and Poisson’s ratio and
design variables in the paper.
Maximize A22
subject to 0.48 eff 0.52
5o k 5o or
40o k 50o or
85o k 95o
0.001 t k 0.05"
272
Structural & Multidisciplinary Optimization Group
RESULTS: PENALTY FUNCTION
• 108 is the best penalty multiplier
273
Structural & Multidisciplinary Optimization Group
RESULTS: BI-OBJECTIVE FORMULATION
• Without focus of the Pareto front on the near feasible
designs, there are many wasted evaluations on deeply
infeasible designs.
274
Structural & Multidisciplinary Optimization Group
