Convergence properties of evolutionary algorithms

Viac o knihe

Evolutionäre Algorithmen sind iterative stochastische Optimierungsverfahren, die von biologischen Evolutionsprinzipien inspiriert sind. Eine Population von Elementen wird durch Mutation und Rekombination variiert, bevor die schlechteren Elemente selektiert werden, sodass die besseren die Grundlage für die nächste Iteration bilden. Diese Algorithmen finden Anwendung bei Optimierungsproblemen, für die keine Spezialverfahren existieren oder bei denen traditionelle Methoden versagen. Ihre Robustheit und die inhärente Parallelität haben sie zur beliebten Wahl für schwierige Optimierungsaufgaben gemacht. Die theoretische Fundierung bleibt jedoch hinter den praktischen Anwendungen zurück. Diese Arbeit zielt darauf ab, die theoretische Basis der evolutionären Algorithmen zu vertiefen. Zunächst werden sie als Markoffsche Prozesse modelliert, wobei Fragen zur Erreichbarkeit optimaler Lösungen und globaler Konvergenz behandelt werden. Die Laufzeitanalyse konzentriert sich auf spezifische Problemklassen, wobei für pseudoboolesche modulare, submodulare und unimodale Probleme Abschätzungen zur erwarteten Absorptionszeit abgeleitet werden. Eine kritische Würdigung der klassischen Schematheorie und quantitativen Genetik folgt. Die Untersuchung der Konvergenzgeschwindigkeit bei reellen Entscheidungsvariablen beschränkt sich auf die Minimierung stark konvexer Funktionen. Hierbei werden auch temporale Verschlechterungen betrachtet, wobei die The