Non-dominated Sorting Genetic Algorithm (NSGA-II) Karthik Sindhya, PhD Postdoctoral Researcher Industrial Optimization Group Department of Mathematical Information Technology [email protected] http://users.jyu.fi/~kasindhy/ Objectives The objectives of this lecture is to: • Understand the basic concept and working of NSGA-II • Advantages and disadvantages 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 • Advantages: – Explicit diversity preservation mechanism – Overall complexity of NSGA-II is at most O(MN2) – Elitism does not allow an already found Pareto optimal solution to be deleted. • Disadvantage: – Crowded comparison can restrict the convergence. – Non-dominated sorting on 2N size.