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

Computational Complexity ofEvolutionary Algorithms, Hybridizations,and Swarm IntelligenceDissertationzur Erlangung des Grades einesDoktors der Naturwissenschaftender Technischen Universit¨at Dortmundan der Fakult¨at f¨ur InformatikvonDirk SudholtDortmund2008Tag der mu¨ndlichen Pru¨fung: 15. Dezember 2008Dekan: Prof. Dr. Peter BuchholzGutachter: Juniorprof. Dr. Thomas JansenProf. Dr. Gu¨nter RudolphDedicated to the memory of Ingo Wegener (1950–2008)iiSummaryBio-inspired randomized search heuristics such as evolutionary algorithms, hybridiza-tions with local search, and swarm intelligence are very popular among practitionersas they can be applied in case the problem is not well understood or when there isnot enough knowledge, time, or expertise to design problem-specific algorithms. Evo-lutionary algorithms simulate the natural evolution of species by iteratively applyingevolutionary 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 withlocal search to refine newly constructed solutions by hill climbing. Swarm intelligencecomprisesantcolonyoptimization aswellasparticleswarmoptimization. Thesemodernsearch paradigms rely on the collective intelligence of many single agents to find goodsolutions for the problem at hand.