Computational complexity of evolutionary algorithms, hybridizations, and swarm intelligence

dc.contributor.advisorJansen, Thomas
dc.contributor.authorSudholt, Dirk
dc.contributor.refereeRudolph, Günter
dc.date.accepted2008-12-15
dc.date.accessioned2008-12-23T13:25:19Z
dc.date.available2008-12-23T13:25:19Z
dc.date.issued2008-12-23T13:25:19Z
dc.description.abstractBio-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.en
dc.identifier.urihttp://hdl.handle.net/2003/25954
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-866
dc.identifier.urnurn:nbn:de:hbz:290-2003/25954-9
dc.language.isoende
dc.subjectComputational complexityen
dc.subjecttheoryen
dc.subjectprobabilistic analysisen
dc.subjectevolutionary algorithmsen
dc.subjecthybridizationen
dc.subjectswarm intelligenceen
dc.subject.ddc004
dc.titleComputational complexity of evolutionary algorithms, hybridizations, and swarm intelligenceen
dc.typeTextde
dc.type.publicationtypedoctoralThesisde
dcterms.accessRightsopen access

Files

Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
dissertation-sudholt.pdf
Size:
2.06 MB
Format:
Adobe Portable Document Format
Description:
DNB
No Thumbnail Available
Name:
Sudholt.tar
Size:
10.38 MB
Format:
tar-Archivdatei
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.93 KB
Format:
Item-specific license agreed upon to submission
Description: