Transcript Multiobjective Evolutionary Algorithms (for NACST/Seq)

Multi-objective Evolutionary Algorithms
(for NACST/Seq)
2003.1.28
summarized by
Shin, Soo-Yong
Reference

Multi-Objective Optimization using
Evolutionary Algorithms, Kalyanmoy Deb,
John Wiley & Sons, LTD., 2002
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Multi-Objective Optimization

Optimization problems with multiple,
conflicting objectives.
Minimize/M aximize
subject to
f m ( x),
m  1,2,..., M ;
g j ( x)  0,
j  1,2,..., J ;
hk ( x)  0,
k  1,2,..., K ;
xi( L )  xi  xi(U ) , i  1,2,..., n;
T
M objective functions: f (x)  ( f1 (x), f 2 (x), , f M (x))
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Decision Space vs. Objective Space
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Objectives in Multi-Objective
Optimization

Two goals in a MOO
 To find a set as close as possible to the Paretooptimal front
 To find a set of solutions as diverse as possible
 Ex) airline route: cost vs. time
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Difference with Single-Objective
Optimization
Two goals instead of one
 Dealing with two search space

 objective space & decision space (for SOO)

No artificial fix-ups
 cf) weight-sum, ε-constraints method..
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Concept of Domination

A solution x(1) is said to dominate the other
solution x(2), if both conditions 1 and 2 are
true:
1. The solution x(1) is no worse that x(2) in all
objectives
2. The solution x(1) is strictly better than x(2) in at
least one objective
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Dominance Example
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Pareto-Optimality

Non-dominated set
 Among a set of solutions P, the non-dominated set
of solutions P’ are those that are not dominated by
any member of the set P.

Globally Pareto-optimal set
 The non-dominated set of the entire feasible
search space S is the globally Pareto-optimal set
 First level non-dominate front.

Locally Pareto-optimal set
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Pareto-Optimality Example
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Non-dominated Sorting of a
Population
1.
2.
Set all non-dominated sets Pj, (j=1,2,…) as empty sets.
Set non-domination level counter j = 1.
Find the non-dominated set P’ of P
1.
2.
3.
4.
3.
4.
Set solution counter i=1 and create an empty non-dominate
set P’.
For a solution j∈ P (but j ≠ i), check if solution j dominates
solution I, If y4s, go to Step 2-4.
If more solutions are left in P, increment j by one and go to
Step 2-2; otherwise, set P’=P’∪{i}.
Increment I by one. If i ≤N, go to Step 2-2; otherwise stop and
declare P’ as the non-dominated set.
Update Pj = P’ and P = P\P’.
If P ≠ Φ, increase j by one and go to Step 2. Otherwise,
stop and declare all non-dominated sets Pi, for
i=1,2,…,j.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Non-dominates Sorting Example
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Classical Methods for MOO







Weighted sum method
ε-constraints method
Weighted metric methods
Benson’s method
Value function method
Goal programming methods
Interactive methods
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Evolutionary Algorithms

Multi-modal function optimization
 Multi-modal functions have multiple optimum
solutions, of which many are local optimal
solutions
 Diversity through mutation
 Preselection
 Crowding model
 Sharing function model

Crowding & sharing function model are
useful to MOEA
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Non-Elitist Multi-Objective EA

Motivations:
 A user is usually not sure of an exact trade-off
relationship among objectives.
 Equi-spaced weight does not always result to
equi-spaced trade-off solutions.
 Especially,

in non-linear problems.
After finding diverse set of optimal solutions,
it is possible to calculate the associated
weights.
 Enables to choose from different trade-offs.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
MOEA: Early Suggestions

VEGA (Schaffer, 1984)
 First real implementation of a multi-objective
evolutionary algorithm.
 Bias towards independent champions.

Goldberg, 1989
 Suggested the concept of domination.
 Use of niching strategy among solutions of a nondominated class.
 Had impact on MOGA, NPGA, NSGA
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Vector Evaluated Genetic Algorithm

Evaluated an objective vector instead of a scalar
objective function.
 Each element of the vector represents each objective
function.

Simplest, straightforward extension of GA.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Vector Optimized Evolution Strategy
Modification to basic self-adaptive evolution
strategy for single-objective.
 Solution is represented by using a diploid
chromosome (dominant, recessive string).
 Keeps external set of non-dominated
solutions.

 Does not take part in genetic operations.

No further study.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Weight-Based Genetic Algorithm

GA string represents both decision variable
and weights.
 Fitness: weighted sum of objectives.

Maintain diversity in the weight vectors
among population.
 Niching method on substring for weights –
sharing function approach
 Subpopulation for different pre-defined weight
vectors – vector evaluated approach
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Random Weighted GA
Similar to WBGA
 Each solution is associated with random
normalized weight vector.

 Emphasize solutions which may lead to different
solutions in Pareto-optimal region.

Unable to find Pareto-optimal solutions in nonconvex problems.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Multiple Objective GA
Use the non-dominated classification of a GA
population.
 Explicitly caters to emphasize non-dominated
solutions and simultaneously maintains
diversity in the non-dominated solutions.

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Non-Dominated Sorting GA
Before selection, the population is ranked on
the basis of domination (Pareto ranking)
 All nondominated individuals are classified
into one category.
 To maintain the diversity of the population,
these classified individuals are shared with
their dummy fitness values

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Niched-Pareto GA
Uses a binary tournament selection scheme
based on Pareto dominance.
 Solutions are selected if they dominate both
the other and some small group of randomly
selected solutions, but fitness sharing occurs
only in the cases when both solutions are
(non)dominated.

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Predator-Prey ES
Concept of predator-prey model is used.
 This algorithm does not use a domination
check to assign fitness to a solution.

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Elitist MOEA

The presence of elites
 GAs converge to the global optimal solution
 enhance the probability of creating better
offspring

Which solutions are elites in the context of
multi-objective optimization?
 A solution can be evaluated based on nondomination rank in the population
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Elitist NSGA: NSGA-II

Uses an explicit diversity-preserving
mechanism.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Distance-Based Pareto GA
Progress towards the Pareto-optimal front
 Maintain diversity among solutions


Elite size is not restricted
 Increase the complexity

Fitness assignment scheme is sensitive to the
ordering of individuals in a population
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Strength Pareto EA
Uses an archive containing non-dominated
solutions previously found.
 At each generation, non-dominated
individuals are copied to the external nondominated set.
 For each individual, a strength value is
computed (ranking value).
 Clustering technique is used to keep diversity.

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Thermodynamical GA

The fitness function is motivated from the
thermodynamic equilibrium condition
F  E  HT
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Pareto-Archived ES
(1+1)-ES
 Uses only mutation
 Single parent and a single offspring

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Multi-Objective Messy GA

MOO version of Messy GA
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Constrained MOEA

Constraints
 Divides search spaces into two divisions
 Feasible
vs. infeasible regions
 Equality vs. inequality
 Hard vs. soft
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Constraint Handling MOEAs
•
Ignoring infeasible solutions
 Difficult to find any feasible solution.
•
•
•
•
Penalty function approach
Jiménez-Verdegay-Goméz-Skarmeta’s
method
Constrained tournament approach
Ray-Tai-Seow’s method
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Salient Issues of MOEA











Illustrative representation of non-dominated
solutions
Development of performance measures
Test problem design for unconstrained and
constrained multi-objective optimization
Comparative studies of different MOEAs
Decision variable vs. objective space niching
Preference of a particular region in the Paretooptimal front
Single-objective constraint handling using MOEAs
Scaling issues of MOEAs in more than two objectives
Design of convergent MOEAs
Controlled elitism in elitist MOEAs
Design of MOEAs
for scheduling problems.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Difficulties in Converging to the
Pareto-Optimal Front
Multi-modality
 Deception
 Isolated optimum
 Collateral noise

© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Searching for Preferred Solutions


How does one choose a particular solution from the
obtained set of non-dominated solutions?
Post-optimal techniques
 Compromise programming
 Pseudo-weight vector approach

Optimization-level techniques




Utility functions
Biased sharing approach
Guided domination approach
Weighted domination approach
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Scaling Issues

The problem difficulties varies rather
interestingly with the number of objectives.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Scaling:
Non-Dominated Solutions in a Population

As increase the number of objectives, the number of
non-dominated solutions in the initial random
population will also increase.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Scaling:
Population Sizing

Too many initial non-dominated
solution..
 Increase the population size
 Modify algorithm
 About 30% of initial pop is good.



Objective space sharing vs. Parameter
space sharing
Tricky generation of initial population
(if the information is given)
Dynamic population sizing
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlling Elitism

To ensure better convergence, a search algorithm
may need diversity in both aspects – along the
Pareto-optimal front and lateral to the Paretooptimal front.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlling Elitism in NSGA-II
Restrict the number of individuals in the
current best non-dominated front adaptively.
 Maintain a predefined distribution of number
of individuals in each front.

N i  rN i 1
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlling Elitism in NSGA-II
1.
The population Rt=Pt Qt
1. pop size = 2N, number of front = k
Ni  N
1  r i 1
r
1 rk
2. If there are more solutions than allowed, choose
Ni solutions by using the crowded tournament
selection.
3. Otherwise, choose all solutions and count the
number of remaining slots. The maximum
allowed number of individuals in the next front
is increased by remaining slots.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Non-dominated Sorting Genetic
Algorithm (NSGA)
NSGA procedure
1.
Sort the population P according to non-domination

2.
All solutions in the first set belong to the best nondominated set in the population
Fitness assignment
1.
2.
3.
Choose sharing parameter σshare and a small positive
number ε and initialize Fmin = N + ε. Set front counter j = 1/
Classify population P according to non-domination:
For each q ∈ Pj
1.
2.
Assign fitness Fj(q) = Fmin- ε.
Calculate niche count ncq using equation
N
nci   Sh(dij ),
j 1
1 
Sh(d )  
0,
 
d
 share

, if d   share
otherwise
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA procedure
3.
4.
5.
Calculate shared fitness Fj’(q) = Fj(q) /ncq
Fmin = min(Fj’(q) : q∈Pj) and set j=j+1.
If j ≤ ρ, go to Step 3. Otherwise, the process is complete.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA

Advantages
 The assignment of fitness according to nondominated sets
 Since better non-dominated sets are emphasized
systematically, an NSGA progresses to the Paretooptimal region.
 Performing sharing in the parameter space allows
phenotypically diverse solutions to emerge.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA

Disadvantages
 The sharing function approach requires the
sharing parameter.
 Performance of an NSGA is sensitive to the
sharing parameter
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA-II: Elitist NSGA
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA-II Procedure
Pt : parent population
Qt : offspring population
Rt : Pt  Qt
Create Rt, perform a non-dominated sorting
to Rt, identify different fronts Fi
2. Pt+1 = , i=0. Until | Pt+1 | + | Fi | < N,
perform Pt+1 = Pt+1  Fi i=i+1
1.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA-II Procedure
Perform the crowding-sort (Fi , <c), include
the most widely spread (N-|Pt+1|)
solutions
4. Create Qt+1 from Pt+1 (using the crowed
tournament selection, crossover, mutation)
3.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA-II Procedure: Crowded Tournament
Selection Operator

A solution i wins a tournament with another
solution j if any of the following conditions
are true :
 If solution i has a better rank, that is, ri < rj
 If they have the same rank but solution i has a
better crowding distance than solution j, that is, ri
= rj and di > dj
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NSGA-II Procedure: Crowded Tournament
Selection Operator
1.
2.
3.
Call the number of solutions in F as l = |F|. For each i
in the set, first assign di=0.
For each objective function sort the set in worse order,
or find the sorted indices vector: Im = sort (fm, >).
Assign a large distance to the boundary solutions, and
for all other solutions j=2 to (l-1) :
f f
dI  dI 
f f
m
m
j
j
(I m
j 1 )
(I m
j 1 )
m
max
m
min
m
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
m
NSGA-II

Advantages
 No extra niching parameter is required
 Crowding distance can be implemented in the
parameter space

Disadvantages
 If pop size is small, NSGA-II shows the poor
exploration power.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlled Elitist NSGA-II
Restrict the number of individuals in the
current best non-dominated front adaptively.
 Maintain a predefined distribution of number
of individuals in each front.

N i  rN i 1
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlled Elitist NSGA-II
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
Controlled Elitist NSGA-II
1.
The population Rt=Pt Qt
1. pop size = 2N, number of front = k
Ni  N
1  r i 1
r
1 rk
2. If there are more solutions than allowed, choose
Ni solutions by using the crowded tournament
selection.
3. Otherwise, choose all solutions and count the
number of remaining slots. The maximum
allowed number of individuals in the next front
is increased by remaining slots.
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/
NACST/Seq

Controlled elitist NSGA-II with clustering
 Simple k-means clustering with threshold
© 2002, SNU BioIntelligence Lab, http://bi.snu.ac.kr/