Genetische Verfahren

Zurück zum Inhaltsverzeichnis

Genetische Verfahren

Genetische Verfahren stellen im Grunde genommen eine Suchheuristik dar. Da sie allerdings eine völlig andere Funktionsweise haben als andere Heuristiken, ist ihnen ein eigenes Kapitel gewidmet.

Die Grundidee der genetischen Verfahren ist der biologischen Evolution entlehnt. Biologische Systeme haben einen hohen Grad an Robustheit und Flexibilität entwickelt. Anpassung und Reproduktion sind in der Natur alltäglich – in der rechnergestützten Geographie bisher eher selten.

Genetische Algorithmen können bei jeder Art von Optimierungsaufgaben eingesetzt werden. Dazu ist es notwendig, daß zu jeder Lösung ein Wert ermittelt werden kann, der die Güte der Lösung beschreiben kann. Soll ein Genetischer Algorithmus zum Beispiel die Zahl 100 erraten, dann kann die Güte der Lösung als Abstand zum Wert 100 beschrieben werden. Die Zahl 98 ist wäre keine richtige Lösung, aber wohl eine sehr gute, während die Zahl 50 eine schlechte Lösung wäre, aber keine falsche. Die Begriffe "richtig" und "falsch" sind für Lösungen, die mittels eines genetischen Algorithmus gefunden wurden nicht vorgesehen. Es sind nur relative Aussagen möglich.

Das Grundprinzip imitiert die Mechanismen der Selektion und der Genetik. Zu einem Suchproblem wird eine Anfangspopulation von zufällig generierten Lösungen entworfen. Der Lösungsansatz jedes Individuums wird mittels einer Evaluierungsfunktion bewertet. Diejenigen Individuen, deren Lösungen vergleichsweise gut sind, vermehren sich. Bei der Vermehrung wird die Lösung der Eltern an die der Kinder in leicht mutierter Form weitergegeben. Die erfolgreichen Kandidaten reproduzieren sich oft. Diejenigen Individuen, deren Bewertung durch die Evaluierungsfunktion schlecht ausfällt, sterben über einen gewissen Zeitraum hinweg aus. Durch die ständige zufällige Mutation und Selektion entstehen auf evolutionäre Weise nach mehreren Generationen Lösungen, die gut an ihre Evaluierungsfunktion angepaßt sind. Die so generierten Lösungen sind, je nach verwendetem Zufallsgenerator, nicht zwingend reproduzierbar. Auch ist eine absolute Bewertung der Lösungen nicht möglich, da die optimale Lösung nach wie vor nicht bekannt ist. Es läßt sich lediglich die Aussage treffen, daß eine Lösung besser ist, als eine andere. Dies ist zugegebener Maßen eine unzufriedenstellende Tatsache, aber das Verfahren ermöglicht das Finden suboptimaler Lösungen zu Problemen, die bisher als unlösbar galten.

Der Ablauf im Detail:

• Initialisierung: Eine ausreichend große Anzahl von Individuen (Lösungskandidaten) wird erzeugt.
• Evaluation: Jedes Individuum wird anhand einer geeigneten Evaluierungsfunktion bewertet. Sie beinhaltet eine mathematische Formulierung der Definition einer guten Lösung.
• Selektion: schwache Lösungskandidaten werden entweder sofort oder nach Ablauf einer Gnadenfrist verworfen .
• Reproduktion: Je nach Verfahren reproduzieren sich nur die erfolgreichsten oder aber alle Lösungskandidaten. Während des Reproduktionsvorgangs werden einzelne Parameter einer Lösung mehr oder weniger stark mutiert. Es ist auch möglich, sofern die Problemstellung es plausibel erscheinen läßt, neue Lösungskandidaten durch Kombination von Lösungsparametern zweier oder mehr Individuen zu erzeugen (crossover).
• Die genannten Schritte werden beliebig oft wiederholt. Zu jedem Zeitpunkt kann der Kandidat, der nach Durchlaufen der Evaluierungsfunktion den höchsten Wert erzielt, als beste vorhanden Lösung präsentiert werden.

Das Verfahren ist sehr effizient, da es sich um eine parallel ablaufende Suche handelt. Es werden nur die Bereiche des Suchraums untersucht, die sich gegenüber den bisherigen Lösungen behaupten konnten. Denkbare Anwendungsbereiche sind Standortoptimierungsverfahren oder gar Optimierung von Plänen.