A FAST ELITIST MULTIOBJECTIVE GENETIC ALGORITHM:
NSGA-II
ARAVIND SESHADRI
1. Multi-Objective Optimization Using NSGA-II
NSGA ( [5]) is a popular non-domination based genetic algorithm for multi-
objective optimization. It is a very effective algorithm but has been generally
criticized for its computational complexity, lack of elitism and for choosing the
optimal parameter value for sharing parameter σ
share
. A modified version, NSGA-
II ( [3]) was developed, which has a better sorting algorithm , incorporates elitism
and no sharing parameter needs to be chosen a priori. NSGA-II is discussed in
detail in this.
2. General Description of NSGA-II
The population is initialized as usual. Once the population in initialized the
population is sorted based on non-domination into each front. The first front being
completely non-dominant set in the current population and the second front being
dominated by the individuals in the first front only and the front goes so on. Each
individual in the each front are assigned rank (fitness) values or based on front in
which they belong to. Individuals in first front are given a fitness value of 1 and
individuals in second are assigned fitness value as 2 and so on.
In addition to fitness value a new parameter called crowding distance is cal-
culated for each individual. The crowding distance is a measure of how close an
individual is to its neighbors. Large average crowding distance will result in better
diversity in the population.
Parents are selected from the population by using binary tournament selection
based on the rank and crowding distance. An individual is selected in the rank is
lesser than the other or if crowding distance is greater than the other
1
. The selected
population generates offsprings from crossover and mutation operators, which will
be discussed in detail in a later section.
The population with the current population and current offsprings is sorted again
based on non-domination and only the best N individuals are selected, where N is
the population size. The selection is based on rank and the on crowding distance
on the last front.
3. Detailed Description of NSGA-II
3.1. Population Initialization. The population is initialized based on the prob-
lem range and constraints if any.
1
Crowding distance is compared only if the rank for both individuals are same
1
