Computational complexity of evolutionary algorithms, hybridizations, and swarm intelligence [Elektronische Ressource] / Dirk Sudholt

Dirk Sudholt

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_dortmund
• Publié le: 01 janvier 2008
• Nombre de lectures: 40
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Computational Complexity of
Evolutionary Algorithms, Hybridizations,
and Swarm Intelligence
Dissertation
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
der Technischen Universit¨at Dortmund
an der Fakult¨at f¨ur Informatik
von
Dirk Sudholt
Dortmund
2008Tag der mu¨ndlichen Pru¨fung: 15. Dezember 2008
Dekan: Prof. Dr. Peter Buchholz
Gutachter: Juniorprof. Dr. Thomas Jansen
Prof. Dr. Gu¨nter RudolphDedicated to the memory of Ingo Wegener (1950–2008)iiSummary
Bio-inspired randomized search heuristics such as evolutionary algorithms, hybridiza-
tions with local search, and swarm intelligence are very popular among practitioners
as they can be applied in case the problem is not well understood or when there is
not enough knowledge, time, or expertise to design problem-specific algorithms. Evo-
lutionary algorithms simulate the natural evolution of species by iteratively applying
evolutionary operators such as mutation, recombination, and selection to a set of solu-
tions for a given problem. A recent trend is to hybridize evolutionary algorithms with
local search to refine newly constructed solutions by hill climbing. Swarm intelligence
comprisesantcolonyoptimization aswellasparticleswarmoptimization. Thesemodern
search paradigms rely on the collective intelligence of many single agents to find good
solutions for the problem at hand. Many empirical studies demonstrate the usefulness
of these heuristics for a large variety of problems, but a thorough understanding is still
far away.
We regard these algorithms from the perspective of theoretical computer science and
analyze the random time these heuristics need to optimize pseudo-Boolean problems.
This is done in a mathematically rigorous sense, using tools known from the analysis of
randomized algorithms, and it leads to asymptotic bounds on their computational com-
plexity. This approach has been followed successfully for evolutionary algorithms, but
the theory of hybrid algorithms and swarm intelligence is still in its very infancy. Our
results shed light on the asymptotic performance of these heuristics, increase our under-
standing of their dynamic behavior, and contribute to a rigorous theoretical foundation
of randomized search heuristics.
iiiivAcknowledgments
I would like to express my gratitude to several people that directly or indirectly con-
tributed to this thesis. I thank Hans-Paul Schwefel and his former staff members for
the opportunity to start my Ph.D. work at the chair Systems Analysis/Algorithm Engi-
neering during the year 2005. I am indebted to my advisor Ingo Wegener for his steady
support through many years and many lessons I could learn from him. He passed away
inNovember 2008 afteralongbattle withcancer. He hasalways beenashiningexample
to me in every respect. I warmly thank Thomas Jansen for his advice and support, in
particular during the first years of my Ph.D. work.
IwouldliketothankmycoauthorsBenjaminDoerr,TobiasFriedrich, ThomasJansen,
Pietro Oliveto and, especially, Frank Neumann and Carsten Witt for introducing me to
theruntimeanalysisofswarmintelligence. Ithankallcurrentandformermembersofthe
chairEfficient Algorithms and Complexity Theory fortheenjoyableworkingatmosphere,
and in particular Thomas Jansen and Carsten Witt for many fruitful discussions and
insights.
Finally, I gratefully acknowledge financial support from the Deutsche Forschungs-
gemeinschaft (DFG) throughthecollaborative researchcenter“DesignandManagement
of Complex Technical Processes and Systems by Means of Computational Intelligence
Methods” (SFB 531).
vviNomenclature
ib String with i concatenations of the letter b
δ The local search depth in memetic algorithms
E(X) Expectation of the random variable X
e Euler’s number e=exp(1) =2.7182...
f =Ω(g) Function f grows at least as fast as g, see Definition 2.1.3
f =ω(g) Function f grows faster than g, see Definition 2.1.3
f =Θ(g) Functions f and g have the same order of growth, see Definition 2.1.3
f =O(g) Function f grows at most as fast as g, see Definition 2.1.3
f =o(g) Function f grows slower than g, see Definition 2.1.3
nf A function f transformed according to f (x) =f(x⊕a) for x,a∈{0,1}a a
nH(x,y) Hamming distance between x and y for x,y∈{0,1}
λ The number of offspring created in one generation
ln(x) Natural logarithm of x, i.e., logarithm of x to the base e
log(x) Logarithm of x to the base 2
The size of the population
n The number of bits in the search space, also called problem dimension
N(x) Open Hamming neighborhood of x (excluding x)
∗N (x) Closed Hamming neighborhood of x (including x)
N Neighborhood containing all points with Hamming distance exactly kk
N The set of natural numbers,N={1,2,3,...}
N The set of natural numbers including 00
viip The mutation probability with which each bit is flipped in a mutationm
Prob(A) Probability of the event A
R The set of reals
+
R The set of positive reals
+
R The set of positive reals including 00
ρ The evaporation factor in ant colony optimization
τ Function indicating pheromones on edges in ant colony optimization
τ Reciprocal of the local search frequency in memetic algorithms
v The maximum velocity value of a particle swarm optimizermax
|x| The number of bits with value 1 in x1
|x| The number of bits with value 0 in x0
{X} An infinite sequence of random variables X ,X ,X ,...t t≥0 0 1 2
Z The set of integers,Z={...,−2,−1,0,1,2,...}
viii