### Non-dominated Sorting Genetic Algorithm (NSGA-II)

```Non-dominated Sorting Genetic
Algorithm (NSGA-II)
Karthik Sindhya, PhD
Postdoctoral Researcher
Industrial Optimization Group
Department of Mathematical Information Technology
[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
http://users.jyu.fi/~kasindhy/
Objectives
The objectives of this lecture is to:
• Understand the basic concept and
working of NSGA-II
NSGA-II
• Non-dominated sorting genetic algorithm –II
was proposed by Deb et al. in 2000.
• NSGA-II procedure has three features:
– It uses an elitist principle
– It emphasizes non-dominated solutions.
– It uses an explicit diversity preserving mechanism
NSGA-II
• NSGA-II
Crossover &
Mutation
ƒ2
ƒ1
NSGA-II
• Crowded tournament selection operator
– A solution xi wins a tournament with another solution
xj if any of the following conditions are true:
• If solution xi has a better rank, that is, ri < rj .
• If they have the same rank but solution xi has a better
crowding distance than solution xj, that is, ri = rj and di > dj .
Objective space
NSGA-II
• Crowding distance
– To get an estimate of the density of solutions
surrounding a particular solution.
• Crowding distance assignment procedure
– Step 1: Set l = |F|, F is a set of solutions in a front.
Set di = 0, i = 1,2,…,l.
– Step 2: For every objective function m = 1,2,…,M,
sort the set in worse order of fm or find sorted
indices vector: Im = sort(fm).
NSGA-II
• Step 3: For m = 1,2,…,M, assign a large distance to
boundary solutions, i.e. set them to ∞ and for all
other solutions j = 2 to (l-1), assign as follows:
i-1
i
i+1
NSGA-II