Scribd
Upload
7 views15 pages

NSGA-II: Elitist Genetic Algorithm Overview

The document discusses the Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II), which is used to solve multi-objective optimization problems involving conflicting objectives. It describes the key aspects of NSGA-II, including non-domination ranking, crowding distance, elitism, and the overall algorithm flow. An example application is given of using NSGA-II to design an optimal bicycle frame that minimizes area and deflection within given constraints.

Uploaded by

Subrat Nayak
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views15 pages

NSGA-II: Elitist Genetic Algorithm Overview

The document discusses the Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II), which is used to solve multi-objective optimization problems involving conflicting objectives. It describes the key aspects of NSGA-II, including non-domination ranking, crowding distance, elitism, and the overall algorithm flow. An example application is given of using NSGA-II to design an optimal bicycle frame that minimizes area and deflection within given constraints.

Uploaded by

Subrat Nayak
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Elitist Non-dominated Sorting

Genetic Algorithm: NSGA-II


Tushar Goel
tusharg@[Link] 2
Multi-objective optimization problem
Problems with more than one objectives typically
conflicting objectives
Cars: Luxury vs. Price
Mathematical formulation
Minimize F(x),
where F(x) = {f
i
: i = 1, M},
x= {x
j
: j = 1, N}
Subject to:
C(x) 0, where C = {C
k
: k = 1, P}
H(x) = 0, where H = {H
l
: l = 1, Q}
tusharg@[Link] 3
Pareto optimal front
Many optimal solutions
Usual approaches:
weighted sum strategy,
-constraint modeling,
Multi-objective GA
Algorithm requirements:
Convergence
Spread
M
i
n

f
2
Min f
1
tusharg@[Link] 4
Terminology
Non-domination
criterion
Ranking
f
2
f
1
tusharg@[Link] 5
Terminology
Niching parametric
Crowding distance
c = a + b
Ends have infinite
crowding distance
f
2
f
1
a
b
tusharg@[Link] 6
Elitism
Elitism: Keep
the best
individuals
from the
parent and
child
population
f
2
f
1
Parent
Child
tusharg@[Link] 7
Flowchart of NSGA-II
Begin: initialize
population (size N)
Evaluate objective
functions
Selection
Crossover
Mutation
Evaluate objective
function
Stopping
criteria
met?
Yes
No
C
h
i
l
d

p
o
p
u
l
a
t
i
o
n

c
r
e
a
t
e
d
Rank
population
Combine parent and
child populations,
rank population
Select N
individuals
Elitism
Report final
population and
Stop
tusharg@[Link] 8
Elitism Process
Rank 1
Rank 2
Rank 3
Rank 4
Rank 1
Rank 2
Rank 3
Rank 5+
Rank 4
C
h
i
l
d

p
o
p
u
l
a
t
i
o
n
P
a
r
e
n
t

p
o
p
u
l
a
t
i
o
n
Rank 1
Rank 2
Rank 3
Rank 4
Rank 5
Rank 6
Rank 7+
Combined
population
Rank 1
Rank 2
Rank 3
Elitist selection
New
population
tusharg@[Link] 9
Example: Bicycle Frame Design
Objectives
Minimize area
Minimize max. deflection
Constraints
Component should be a
valid geometry
Maximum stress < Yield
stress
Maximum deflection <
Allowed deflection
m
m
( )
max allowed
<
( )
max allowed
<
10 kN
Plate thickness = 20 mm
tusharg@[Link] 10
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
tusharg@[Link] 11
Material Properties and GA Parameters
Material Properties
Yield Stress 140 MPa
Max Deflection 5 mm
Youngs Modulus (E) 80GPa
Poissons Ratio 0.25
GA Parameters
Binary String Size (L) 14x9
Population Size 30
Crossover Probability 0.95
Mutation Probability 1/L
# of Generations 150
( )
allowed

( )
allowed

( )

tusharg@[Link] 12
Pareto Optimal Front
Small increase in
weight leads to large
drop in deflection
Similarly small
change in deflection
allows significant
reduction of the
weight
tusharg@[Link] 13
Different conceptual designs
Different conceptual designs
Optimal shapes
Least weight
Least deflection
tusharg@[Link] 14
Some More Engineering Applications
Structural designs of mechanical components
Design of turbo-machinery components
Bioinformatics protein unfolding
VLSI circuit designs
Packaging

tusharg@[Link] 15
Other related topics 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

You might also like