Towards a theory of representations for genetic and evolutionary algorithms: development of basic concepts and their application to binary and tree representations.
Franz Rothlauf · Ausgezeichnete Informatikdissertationen · 2001
Die in dem vorliegenden Beitrag zusammengefasste Dissertationsschrift beschaftigt sich mit der Theorie von Reprasentationen fur Genetische und Evolutionare Algorithmen (GEA). GEAs sind leistungsfahige, naturanaloge heuristische Losungsraumsuchverfahren, welche insbesondere bei semiformalen Problemen, fur welche keine analytische Problembeschreibung vorliegen, effektiv eingesetzt werden konnen. GEAs imitieren die Prinzipien der naturlichen Evolution und wenden genetische Operatoren auf eine Reprasentation des zu losenden Problems an. Da bisher nur wenig theoretische Erkennntnisse uber Reprasentationen vorlagen, war die Entwicklung von geeigneten Reprasentationen bisher uberwiegend ein Ergebnis zufalligem Probierens. Im Folgenden werden grundlegende theoretische Konzepte fur Reprasentationen entwickelt. Im speziellen wird untersucht, wie redundante Reprasentationen, Reprasentationen mit unterschiedlich skalierten Allelen und Reprasentationen mit niedriger Lokalitat die Leistungsfahigkeit von GEAs beeinflussen. Mithilfe dieser Konzepte wird der Einflus der Reprasentation auf die Leistungsfahigkeit von GEAs fur ganzzahlige und baumformige Optimierungsprobleme untersucht. Abschliesend werden theoriegeleitet neue Reprasentationen fur Baume entwickelt. Es zeigt sich, dass durch die vorgestellten Modelle sowohl das Verhalten von GEAs vorhergesagt, als auch deren Leistungsfahigkeit vorteilhaft beeinflusst werden kann.