Hypervolume based metaheuristics for multiobjective optimization
Loading...
Date
2012-01-31
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The purpose of multiobjective optimization is to find solutions that are optimal
regarding several goals. In the branch of vector or Pareto optimization all these
goals are considered to be of equal importance, so that compromise solutions that
cannot be improved regarding one goal without deteriorating in another are Paretooptimal.
A variety of quality measures exist to evaluate approximations of the Paretooptimal
set generated by optimizers, wherein the hypervolume is the most significant
one, making the hypervolume calculation a core problem of multiobjective
optimization. This thesis tackles that challenge by providing a new hypervolume algorithm
from computational geometry and analyzing the problem’s computational
complexity.
Evolutionary multiobjective optimization algorithms (EMOA) are state-of-the-art
methods for Pareto optimization, wherein the hypervolume-based algorithms belong
to the most powerful ones, among them the popular SMS-EMOA. After its
promising capabilities have already been demonstrated in first studies, this thesis
is dedicated to deeper understand the underlying optimization process of the
SMS-EMOA and similar algorithms, in order to specify their performance characteristics.
Theoretical analyses are accomplished as far as possible with established
and newly developed tools. Beyond the limitations of rigorous scrutiny, insights
are gained via thorough experimental investigation. All considered problems are
continuous, whereas the algorithms are as well applicable to discrete problems.
More precisely, the following topics are concerned. The process of approaching
the Pareto-optimal set of points is characterized by the convergence speed, which
is analyzed for a general framework of EA with hypervolume selection on several
classes of bi-objective problems. The results are achieved by a newly developed
concept of linking single and multiobjective optimization. The optimization on the
Pareto front, that is turning the population into a set with maximal hypervolume,
is considered separately, focusing on the question under which circumstances the
steady-state selection of exchanging only one population member suffices to reach a
global optimum. We answer this question for different bi-objective problem classes.
In a benchmarking on so-called many-objective problems of more than three objectives,
the qualification of the SMS-EMOA is demonstrated in comparison to other
EMOA, while also studying their cause of failure. Within the mentioned examinations,
the choice of the hypervolume’s reference point receives special consideration
by exposing its influence. Beyond the study of the SMS-EMOA with default setup,
it is analyzed to what extent the performance can be improved by parameter tuning
of the EMOA anent to certain problems, focusing on the influence of variation operators.
Lastly, an optimization algorithm based on the gradient of the hypervolume
is developed and hybridized with the SMS-EMOA.
Description
Table of contents
Keywords
Evolutionäre Algorithmen, Evolutionary computing, Hypervolume, Hypervolumen, Mehrzieloptimierung, Multiobjective optimization, Search heuristic, Suchheuristik