An Improved Multi-Objective Evolutionary Algorithm with Adaptable Parameters

by
Khoa Duc Tran

August 2006

Multi-Objective Evolutionary Algorithms (MOEAs) are not easy to use because they
require parameter tunings of three main parameters - population size, crossover
probability, and mutation probability - in order to achieve desirable solutions and
performance for an arbitrary complex problem. Moreover, the use of fixed parameter
settings may lead to slow convergence and sub-optimal solutions. This dissertation
develops a MOEA with self-adaptive crossover, self-adaptive mutation, and adaptive
population size parameters for automating the process of adjusting appropriate
parameter values in order to make the MOEA more efficient, simple to use and
available to more users. The MOEA with adaptable parameters is built on the NSGA-II
(Non-dominated Sorting Genetic Algorithm II) and named as ANSGA-II (Adaptable
NSGA-II). The NSGA-II is chosen because it is one of the best-known MOEAs. In the
ANSGA-II, the crossover and mutation parameters are attached to each solution in the
population and allowed to co-evolve with each solution. This enables the algorithm
to carry prior successful crossover and mutation for creating children solutions and
for adaptation of the parameters. Since good parameter values are associated with
good candidate solutions, better parameter values will survive because they produce
better solutions. The ANSGA-II selects the right population size by running several
populations with different population sizes simultaneously and allows the smaller
populations more time to run. Smaller populations may find diverse non-dominated
solution sets close to the Pareto-optimal front faster than the larger populations.
If a subsequent larger population identifies a better non-dominated solution set
then the algorithm stops running the smaller population since it is unlikely to
identify better solutions than the larger one due to genetic drift. Two performance
metrics are investigated for their effective use in comparing non-dominated solution
sets among different populations during the execution of the ANSGA-II. The
dissertation evaluates and discusses the performance of the ANSGA-II, in terms of
finding a diverse non-dominated solution set and converging to the true
Pareto-optimal front, by comparing the results obtained on a suite of thirteen
benchmark multi-objective problems with those obtained by the original NSGA-II. The
results demonstrate that the ANSGA-II out-performs the NSGA-II. The improvement
comes with the cost of longer execution time due to overheads of finding good
non-dominated solutions and learning good parameter values at the same time.
However, the execution time appears to be acceptable on all thirteen benchmark
multi-objective problems.