Abstract
This thesis deals with the analysis and applications of
evolutionary algorithms for optimization problems with
multiple objectives. Many application problems involve
(i) a system model that is not given in a close analytical
form and (ii) multiple, often conflicting optimization
criteria. Both traits hamper the application of classical
optimization techniques, which require a certain structure
of the problem and are mostly designed to handle only a
single objective. For this problem domain, the class of
randomized search heuristics, to which evolutionary
algorithms also belong, have become popular. Due to their
population concept, evolutionary algorithms can process
multiple solutions in parallel and can therefore cope
with different objectives more naturally.
Like most randomized search algorithms, evolutionary
algorithms are easy to describe and implement, but hard to
analyze theoretically. Despite much empirical knowledge
and successful application, only few theoretical results
concerning their effectiveness and efficiency are available.
This holds especially in the multiobjective case where
these questions have not been investigated yet. However,
even from a practical point of view is important to
distinguish:
* whether a given algorithm is capable of solving a given
problem (effectiveness); and
* the computational complexity (measured in computation
time and memory requirements) of an algorithm to solve a
given problem (efficiency).
The aim of this work is to contribute to the
understanding of evolutionary algorithms for multiobjective
optimization problems with respect to these questions.
Specifically, the following topics are covered:
* Based on known concepts from decision theory, the topic
of quality measurement is addressed, with respect to
single solutions (via fitness functions) and sets of
solutions (via quality indicators). The common mathematical
framework allows us to compactly describe existing fitness
functions and quality indicators as well as to analyze
them theoretically.
* Convergence properties are investigated for the limit
case of inifinite running time, but finite memory
resources. Based on the concept of e-approximations, new
selection operators are proposed that guarantee the
convergence of randomized search strategies to a well-
defined discrete solution set with simultaneous consideration
of diversity.
* In order to facilitate a running time analysis, simple
model algorithms and problems are proposed and suitable
proof techniques developed and applied. The results achieved
concerning the expected running time show that through
special selection operators, population-based approaches
can be advantageous over multistart-strategies.
* Three case studies from the field of automotive engineering
demonstrate how evolutionary algorithms can systematically
be exploited in the design process. The applications
underline the practical relevance of some results from the
previous theoretical investigations.