Theoretische Analyse evolutionärer Algorithmen unter dem Aspekt der Optimierung in diskreten Suchräumen

Abstract

Evolutionäre Algorithmen (EA) sind allgemeine, randomisierte Suchverfahren, die unter anderem zur Optimierung eingesetzt werden können. Ein hier verfolgter Ansatz, der zu einem besseren Verständnis führen soll, ist die theoretische Analyse. Dabei werden vor allem einfache EA auf konkreten, typischen Zielfunktionen bezüglich ihrer Effizienz untersucht. Die Analyse beginnt nach einer Diskussion der Grenzen und Möglichkeiten evolutionärer Algorithmen mit dem vielleicht einfachsten EA. Wir sprechen wesentliche Ergebnisse für den so genannten (1+1) EA an und erklären, wie man davon ausgehend das weite Feld evolutionärer Algorithmen erschließen kann mittels Analyse von Variationen des (1+1) EA. Ein Höhepunkt ist die Analyse eines speziellen EA mit Crossover, für den man an einem Beispiel nachweisen kann, dass er mutations-basierte Algorithmen bei weitem schlägt.