Geology Reference
In-Depth Information
as shown in Figure 3. Thus, the rank of a non-
dominated individual should be 1 and the other
dominated individuals are penalized by the degree
of the population density. The main selection
mechanism is that all the current individuals are
sorted according to the rank and assigned as fit-
ness to individuals by interpolating from the best
to the worst ones. The best will have the largest
value while the other individuals will be also as-
signed fitness values. The average fitness values
of same rank individuals are then calculated. The
average fitness value is assigned to the same rank
individuals. Therefore, all the individuals in same
rank have the same probability to be selected for
the next generation.
The main drawback of MOGA is that the block
type of the fitness assignment for individuals of
the same rank is exposed to large selection pres-
sure, resulting in premature convergence of the
population. It implies two different vectors with
the same objective function values and then per-
forms the sharing function. However, it cannot
exist simultaneously in the population under this
scheme. The performance of MOGA is dependent
on the value of the sharing factors (Srinivas and
Deb 1994; Coello et al. 2001). In other words, it
might be difficult for the traditional MOGA to
guarantee the unbiased and even Pareto sets. To
overcome this disadvantage, a non-dominated
sorting genetic algorithm (NSGA) is proposed.
Non-Dominate Sorting Genetic Algorithm
(NSGA)
Srinivas and Deb (1994) developed the non-
dominated sorting genetic algorithm (NSGA).
The NSGA offers an unbiased Pareto optimal
set. The NSGA only differs from the SGA in the
selection operators. The population is ranked on
the basis of its non-domination characteristics.
To keep specific individuals from the premature
convergence and in order to maintain diversity
and multiple optimal points, the procedure is (1)
The non-dominated individuals are found and then
each is given an equal reproductive potential value
(2) Then the sharing method is applied by assign-
ing a degraded fitness value that is obtained by
dividing the equal reproductive potential value by
a quantity proportional to the number of individu-
als around it using Equation (1) (Goldberg and
Richardson 1987). These classifying and sharing
processes are performed on the entire population.
Naturally, the second new dummy set fitness value
should be kept smaller than the minimum shared
dummy fitness set. However, this NSGA requires
complex optimization procedures, resulting in
high computational cost. Thus, Deb et al. (2000)
proposed a modification of the original NSGA,
namely, NSGA II.
Figure 3. Multi-objective ranking based on the
Pareto dominance
Non-Dominated Sorting Genetic Algorithm
2 (NSGA-II)
Deb at al. (2000) proposed an enhanced version
of the NSGA to remove the disadvantages of the
NSGA and improve its performance. The draw-
backs of the NSGA are (Deb at al. 2000)
High computational complexity of the non-
dominated sorting: in case of large popula-
Search WWH ::




Custom Search