Towards a theory of representations for genetic and evolutionary algorithms: development of basic concepts and their application to binary and tree representations

Abstract

Die in dem vorliegenden Beitrag zusammengefasste Dissertationsschrift beschäftigt sich mit der Theorie von Repräsentationen für Genetische und Evolutionäre Algorithmen (GEA). GEAs sind leistungsfähige, naturanaloge heuristische Lösungsraumsuchverfahren, welche insbesondere bei semiformalen Problemen, für welche keine analytische Problembeschreibung vorliegen, effektiv eingesetzt werden können. GEAs imitieren die Prinzipien der natürlichen Evolution und wenden genetische Operatoren auf eine Repräsentation des zu lösenden Problems an. Da bisher nur wenig theoretische Erkennntnisse über Repräsentationen vorlagen, war die Entwicklung von geeigneten Repräsentationen bisher überwiegend ein Ergebnis zufälligem Probierens. Im Folgenden werden grundlegende theoretische Konzepte für Repräsentationen entwickelt. Im speziellen wird untersucht, wie redundante Repräsentationen, Repräsentationen mit unterschiedlich skalierten Allelen und Repräsentationen mit niedriger Lokalität die Leistungsfähigkeit von GEAs beeinflussen. Mithilfe dieser Konzepte wird der Einfluß der Repräsentation auf die Leistungsfähigkeit von GEAs für ganzzahlige und baumförmige Optimierungsprobleme untersucht. Abschließend werden theoriegeleitet neue Repräsentationen für Bäume entwickelt. Es zeigt sich, dass durch die vorgestellten Modelle sowohl das Verhalten von GEAs vorhergesagt, als auch deren Leistungsfähigkeit vorteilhaft beeinflusst werden kann.