2.4 Genetische Algorithmen

Genetische Algorithmen sind der am weitesten bekannte Typ Evolutionärer Algorithmen. Der Begriff Genetischer Algorithmus geht auf eine der frühen Arbeiten von Bagley [Bag67] zurück. In ihrer heute bekannten Form wurden sie aber von John H. Holland an der University of Michigan, USA, entwickelt. Breite Aufmerksamkeit erhielten Genetische Algorithmen ab 1975. Zu diesem Zeitpunkt erschien Holland's Buch ,,Adaptation in natural and artificial systems" [Hol75], in dem er seine Arbeiten zur Adaption in natürlichen und künstlichen Systemen zusammenfaßte. Dieses auch heute noch lesenswerte Buch zeigt dabei nicht nur, wie die natürlichen Suchalgorithmen zur Bearbeitung praktischer Probleme verwendet werden können, sondern wirft viele weitere Fragen auf, die bis heute der Beantwortung harren.

Holland's Ziel war weit gesteckt. Er versuchte, eine allgemeine Theorie adaptiver Systeme zu entwickeln. Das Ziel der Arbeit war dabei zweigeteilt:

1. Erklärung der adaptiven Prozesse in der Natur (Theorie) und
2. Entwicklung von Software, welche die Mechanismen der natürlichen Systeme beibehält und die unbegrenzte Fähigkeit hat, sich den verschiedensten Gegebenheiten anzupassen.

Eines der herausragenden Ergebnisse von Holland's Arbeit war die Formulierung des Schema-Theorems. Damit wurde der Versuch einer Erklärung unternommen, wie und warum Genetische Algorithmen funktionieren und arbeiten.

Ein weiterer Meilenstein bei der Erforschung Genetischer Algorithmen ist die Dissertation von De Jong [DeJ75]. Er analysierte eine Klasse von genetisch adaptiven Systemen. Dabei kombinierte er Holland's Schema-Theorem mit seinen eigenen Experimenten. De Jong stellte eine Testsuite von 5 Funktionen zusammen (De Jong's Funktionen 1-5), die unterschiedliche Charakteristika aufwiesen und untersuchte das Verhalten verschiedenster Parametereinstellungen eines Genetischen Algorithmus. Das Verhalten des Genetischen Algorithmus wurde mittels zweier Kriterien quantifiziert (online und offline Performanz) und machte es damit vergleichbar. Weiterhin untersuchte De Jong die Verfahren elitism und crowding. De Jong's Experimente können als Grundlage vieler weiterer Experimente und Arbeiten mit Genetischen Algorithmen angesehen werden.

Die Arbeit De Jong's gab Genetischen Algorithmen sowie deren Anwendung eine sichere Grundlage. Ausgehend von seinen Ergebnissen wurden viele Erweiterungen und Verbesserungen Genetischer Algorithmen erarbeitet.

Goldberg beschrieb in seiner Dissertation 1983 [Gol83] die erste erfolgreiche Anwendung Genetischer Algorithmen. Er beschäftigte sich mit der Optimierung der Steuerung von Gasleitungssystemen. Der verwendete Optimierungsalgorithmus war ein einfacher Genetischer Algorithmus mit proportionaler Selektion, binärer Mutation und Rekombination. Die Population bestand aus 50 Individuen. Beschränkungen wurden durch eine quadratische Wichtungsfunktion einbezogen. Für die untersuchten Probleme erreichte Goldberg Ergebnisse, die sehr nah am Optimum lagen.

In den folgenden Jahren nahm das Interesse am Einsatz Genetischer Algorithmen stetig zu. Es wurden Anwendungen aus vielen Bereichen berichtet. Eine chronologische Übersicht der frühen Arbeiten und der Anwendung Genetischer Algorithmen in den verschiedensten Bereichen wurde von Goldberg in [Gol89], S.126-129 zusammengestellt.

Diese Dokument ist Teil der Dissertation von Hartmut Pohlheim "Entwicklung und systemtechnische Anwendung Evolutionärer Algorithmen". This document is part of the .
The is not free.
© Hartmut Pohlheim, All Rights Reserved, (hartmut@pohlheim.com).