Computational complexity of evolutionary algorithms, hybridizations, and swarm intelligence
Loading...
Date
2008-12-23T13:25:19Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Bio-inspired randomized search heuristics such as evolutionary algorithms, hybridizations
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. Evolutionary
algorithms simulate the natural evolution of species by iteratively applying
evolutionary operators such as mutation, recombination, and selection to a set of solutions
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
comprises ant colony optimization as well as particle swarm optimization. These modern
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 complexity.
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 understanding
of their dynamic behavior, and contribute to a rigorous theoretical foundation
of randomized search heuristics.
Description
Table of contents
Keywords
Computational complexity, theory, probabilistic analysis, evolutionary algorithms, hybridization, swarm intelligence