Title:
Theory and Applications of Efficient Multi-objective Evolutionary Algorithms

Author:
Jian-Hung Chen
Department of Information Engineering and Computer Science,
Feng Chia University, Taichung, Taiwan, R.O.C.


Advisors:
Shinn-Ying Ho and David E. Goldberg

Abstract
Many real-world optimization problems involve multiple incommensurable and
often competent objectives in nature; these problems are known as
multi-objective optimization problems (MOOPs). Instead of obtaining a single
optimal solution, the ultimate goal of solving MOOPs is to find a complete
set of Pareto-optimal solutions. Recently, multi-objective evolutionary
algorithms (MOEAs) have been recognized to be well-suited for solving MOOPs
because their abilities to exploit and explore multiple solutions in
parallel and to find a widespread set of non-dominated solutions in a single
run. This dissertation emphasizes on advancing the understanding of MOEAs to
design effective and efficient MOEAs. Three major contributions of this
dissertation are summarized as follows.

First, a quality-time analysis of MOEAs based on schema theorem and building
blocks (BBs) hypothesis is developed. Convergence time, first and last
hitting time models are constructed for analyzing the performance of MOEAs.
Population sizing model is constructed for determining appropriate
population sizes. The theoretical results indicate how the convergence time
and population size of a MOEA scale up with the problem size, the
dissimilarity of Pareto-optimal solutions, and the number of Pareto-optimal
solutions of a MOOP. A preliminary theoretical analysis on the convergence
time of MOOPs with scale, length and linkage disequilibriums are also
investigated. The results demonstrate that disequilibriums between multiple
objectives affect the convergence time of MOEAs and may pose difficulties to
MOEAs in maintaining the diversity of population.

Second, a novel approach to multi-objective evolutionary optimization,
intelligent multi-objective evolutionary algorithm IMOEA, is analyzed. IMOEA
combines the concept of BBs identification/mixing, elitism and a novel
fitness assignment strategy in a unique manner. IMOEA efficiently identify
good BBs of parents and then generate good children by taking advantage of
the reasoning ability of orthogonal experimental design in selecting the
potentially best combination of better levels of factors. Empirical studies
of several state-of-the-art MOEAs and IMOEA on well-known multi-objective
knapsack problems and test functions show that IMOEA has high performance in
solving the foregoing problems. Two real-world applications are conducted
using IMOEA: multi-objective production planning of flexible manufacturing
systems and multi-objective design of nearest neighbor classifiers. The
experimental results demonstrate the efficiency of IMOEA in solving
large-scale problems.

Finally, an efficiency enhancement technique for MOEAs, fitness inheritance,
is proposed to improve the performance of MOEAs. Because computational time
of MOEAs are usually bounded by the numbers of function evaluations, the
concept of fitness inheritance is to reduce computation costs of MOEAs by
inheriting objective function values of offsprings from their parents. The
convergence time and population sizing models of MOEAs using fitness
inheritance are derived to determine the optimal proportion of fitness
inheritance and speed-up of MOEAs using fitness inheritance. Theoretical
results are compared with experimental results in two cases: fitness
inheritance with/without fitness sharing. The results indicate that fitness
inheritance can speed-up the convergence time of MOEAs around 25%.

This dissertation presents the following achievements: the theoretical
developments that improve our understanding of the effects of problem
characteristics on MOEAs; the development of IMOEA that demonstrates the
advantage of using BBs identification/mixing; and the development of fitness
inheritance to enhance the performance of MOEAs. These developments can be
guidelines in designing efficient MOEAs to obtain high-quality solutions.

Keywords: Multi-objective optimization, evolutionary algorithms,
convergence, population sizing, orthogonal experimental design, intelligent
multi-objective evolutionary algorithm, intelligent evolutionary algorithm,
flexible manufacturing systems, production planning, data mining, nearest
neighbor classifier, fitness inheritance.