Combinatorial optimization and the analysis of randomized search heuristics [Elektronische Ressource] / Frank Neumann

Sujets

• Mathematics

Informations

• Publié par: christian-albrechts-universitat_zu_kiel
• Publié le: 01 janvier 2006
• Nombre de lectures: 8
• Langue: English

Extrait

Combinatorial Optimization
and the Analysis of
Randomized Search Heuristics
Dissertation
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
(Dr. Ing.)
der Technischen Fakult¨at
der Christian-Albrechts-Universit¨at
zu Kiel
Frank Neumann
Kiel
20061. Gutachter: Prof. Dr. Rudolf Berghammer
2. Gutachter: Prof. Dr. Ingo Wegener
3. Gutachter: Priv.-Doz. Dr. Benjamin Doerr
Tag der mu¨ndlichen Pru¨fung: 19. Juli 20063
Abstract
Randomized search heuristics have widely been applied to complex engineering problems
as well as to problems from combinatorial optimization. We investigate the runtime be-
havior of randomized search heuristics and present runtime bounds for these heuristics
on some well-known combinatorial optimization problems. Such analyses can help to un-
derstand better the working principle of these algorithms on combinatorial optimization
problems as well as help to design better algorithms for a newly given problem. Our anal-
yses mainly consider evolutionary algorithms that have achieved good results on a wide
class of NP-hard combinatorial optimization problems. We start by analyzing some easy
single-objective optimization problems such as the minimum spanning tree problem or the
problem of computing an Eulerian cycle of a given Eulerian graph and prove bounds on
the runtime of simple evolutionary algorithms. For the minimum spanning tree problem
we also investigate a multi-objective model and show that randomized search heuristics
find minimum spanning trees easier in this model than in a single-objective one. Many
polynomial solvable problems become NP-hard when a second objective has to be opti-
mized at the same time. We show that evolutionary algorithms are able to compute good
approximations for such problems by examining the NP-hard multi-objective minimum
spanning tree problem. Another kind of randomized search heuristic is ant colony opti-
mization. Up to now no runtime bounds have been achieved for this kind of heuristic. We
investigate asimple antcolonyoptimizationalgorithmandpresent a firstruntime analysis.
At the end we turn to classical approximation algorithms. Motivated by our investigations
of randomized search heurisitics for the minimum spanning tree problem, we present a
multi-objective model for NP-hard spanning tree problems and show that the model can
help to speed up approximation algorithms for this kind of problems.4Contents
1 Introduction 7
I Basics 13
2 Combinatorial Optimization 15
2.1 Single-objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Multi-objective optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Randomized Search Heuristics 23
3.1 Evolutionary algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Ant colony optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Other randomized search heuristics . . . . . . . . . . . . . . . . . . . . . . 31
II Algorithms and Basic Methods for the Analysis 35
4 Algorithms to be analyzed 37
4.1 Single-objective optimization problems . . . . . . . . . . . . . . . . . . . . 37
4.2 Multi-objective optimization problems . . . . . . . . . . . . . . . . . . . . 43
5 Basic Methods for the Analysis 47
5.1 Fitness-based partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.2 Chernoff bounds and coupon collectors . . . . . . . . . . . . . . . . . . . . 49
5.3 Expected multiplicative weight decrease . . . . . . . . . . . . . . . . . . . 50
III Single-Objective Optimization Problems 53
6 Eulerian Cycles 55
6.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2 Analysis of RLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57p
6.3 Analysis of (1+1) EA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61p
6.4 Mutation using exchange operations . . . . . . . . . . . . . . . . . . . . . . 64
56 CONTENTS
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7 Minimum Spanning Trees 67
7.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.2 Properties of local changes of spanning trees . . . . . . . . . . . . . . . . . 69
7.3 The analysis of RLS and (1+1) EA . . . . . . . . . . . . . . . . . . . . . 71b b
7.4 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8 A Simple ACO Algorithm 79
8.1 1-ANT and (1+1) EA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80b
8.2 Exponential lower bounds for OneMax . . . . . . . . . . . . . . . . . . . . 82
8.3 Polynomial upper bounds for OneMax . . . . . . . . . . . . . . . . . . . . 85
8.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
IV Multi-Objective Optimization Problems 89
9 Multi-Objective Minimum Spanning Trees 91
9.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
9.2 The extremal points of the convex hull . . . . . . . . . . . . . . . . . . . . 93
9.3 Analysis of GSEMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
10 Minimum Spanning Trees Made Easier 103
10.1 A two-objective model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
10.2 The analysis of the expected optimization time. . . . . . . . . . . . . . . . 105
10.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
11 NP-hard Spanning Forest Problems 113
11.1 Minimizing the maximum degree . . . . . . . . . . . . . . . . . . . . . . . 114
11.2 Nonuniform degree bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
11.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
12 Summary and Future Work 127
A Mathematical Background 129
A.1 Probability distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
A.2 Deviation inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
A.3 Other useful formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
B ACO Algorithms 133
B.1 Modifications of the Hoeffding Lemma . . . . . . . . . . . . . . . . . . . . 133Chapter 1
Introduction
The subject of this thesis is the runtime analysis of randomized search heuristics on dif-
ferent combinatorial optimization problems. Randomized search heuristics are general-
purpose algorithms which often yield good solutions for problems whose structure is not
known very well. Evolutionary algorithms (EAs) belonging to this class of algorithms
have become quite popular since the ’60s of the last century. Their main advantage is the
fast application to different problem domains. Using an appropriate encoding for a given
problem and some standard variation operators together with a fitness function for the
considered problems, one can often come up with good solutions for the problem. Evo-
lutionary algorithms have widely been applied to complex engineering problems as well
as to problems from combinatorial optimization. In the case of a complex engineering
problem the structure of the problem is often not known. Then the quality of a certain
parameter setting can often only be evaluated by experiments or simulations. Such prob-
lems are considered in the field of black-box optimization, where the value of a parameter
setting can only be given after having executed some experiments or simulations. EAs
have shown to be very successful on many problems from black-box optimization. In the
case of combinatorial optimization, often much more is known about the structure of a
given problem and the function to be optimized can be given and analyzed. Nevertheless
it is often difficult to obtain good solutions for such problems, especially if the problem is
new and there are not enough resources (such as time, knowledge, money) to design spe-
cific algorithms for the given problem. In this case, the application of randomized search
heuristics oftenyields satisfying results. Evolutionary algorithmsandallotherrandomized
search heuristics investigated in this thesis have shown to be very successful in obtaining
good solutions, especially for new NP-hard optimization problems.
In contrast to the work done in the classical algorithm community, the work on evo-
lutionary computation is mainly driven by experiments. A lot of work has been done in
considering different encodings for some popular problems like NP-hard variants of the
minimum spanning tree problem. The advantage of the newly created algorithm is then
shown by reporting the results of experiments done on random graphs or some benchmark
instances. Until the ’90s of the last century the theoretical work in the area of evolution-
78 CHAPTER 1. INTRODUCTION
ary computation was concentrated on showing that an algorithm converges to an optimal
solution after a finite number of steps. On the other hand it has been considered what
happens in one iteration of the algorithms. Although these are interesting investigations,
both aspects do not allow to give upper or lower bounds on the