3.1 Übersicht
3.1 Übersicht |
|
Evolutionäre Algorithmen sind stochastische Suchverfahren, die an die Prinzipien der natürlichen biologischen Evolution angelehnt sind. Evolutionäre Algorithmen arbeiten gleichzeitig auf einer Anzahl von potentiellen Lösungen, der Population von Individuen. Auf diese Individuen (Lösungen) wird das Prinzip "Der Stärkere überlebt!" angewendet, um im Sinne einer Zielfunktion immer bessere Individuen zu erzeugen, die am Ende zu einer guten Lösung führen.
Nach einer Initialisierungsphase zu Beginn wird in einem Prozeß über mehrere Generationen eine Suche durchgeführt. In jeder Generation wird eine Anzahl neuer Lösungen erstellt. Dies erfolgt durch die Auswahl von Individuen entsprechend ihrer Fitneß, aus denen nachfolgend durch die Anwendung evolutionärer Reproduktionsoperatoren neue Individuen erzeugt werden. Diese Individuen werden in die Population eingefügt, wodurch eine neue Population entsteht. Die neue Population dient als Ausgangspunkt für die Erstellung neuer Individuen in der nächsten Generation. Dieser Prozeß führt zur Evolution (Entwicklung) von Populationen von Individuen, die immer besser an die jeweilige Zielstellung angepaßt sind, als die Individuen, von denen sie erzeugt wurden. Dies entspricht der natürlichen Anpassung. Da Evolutionäre Algorithmen mit Populationen von Individuen arbeiten, wird die Suche im Problemraum in einer parallelen Art und Weise durchgeführt.
Evolutionäre Algorithmen modellieren verschiedene natürliche Prozesse, z.B. Selektion, Reproduktion, Rekombination, Mutation, Migration, Lokalität, Nachbarschaft, Parallelität und Konkurrenz. Jeder dieser Prozesse kann in einer Vielzahl von Varianten auftreten.
Abbildung 3-1 zeigt die Struktur eines einfachen Evolutionären Algorithmus. Diese Struktur ist die Minimalvariante eines Evolutionären Algorithmus, die als Ausgangspunkt für die folgenden Erläuterungen dient. Erweiterungen lassen sich in diese Struktur später gut eingliedern.
Abbildung 3-1: Struktur eines einfachen Evolutionären Algorithmus
Zu Beginn der Arbeit eines Evolutionären Algorithmus erfolgt die Initialisierung. Diese beinhaltet neben der Parametrierung vor allem die Erstellung der Anfangspopulation. Normalerweise werden die Individuen der Anfangspopulation zufällig im Definitionsbereich der Variablen initialisiert. Allerdings können für diese Initialisierung auch problemspezifische Verfahren verwendet werden. Die erstellte Anfangspopulation wird durch die Zielfunktion bewertet. Damit ist die Population der ersten Generation produziert.
Wenn das definierte Abbruchkriterium noch nicht erreicht ist, beginnt die Erstellung einer neuen Generation und damit der evolutionäre Kreislauf. Jedem Individuum wird entsprechend seines Zielfunktionswertes und im Vergleich zu allen anderen Individuen der Population eine Fitneß zugewiesen. Entsprechend dieser Fitneß werden die Individuen (Eltern) für die Produktion von neuen Individuen (Nachkommen) ausgewählt (Selektion). Die Eltern produzieren unter Anwendung evolutionärer Operatoren (Rekombination, Mutation) die Nachkommen. Durch Rekombination werden die Nachkommen erstellt und diese werden dann durch Mutation mit einer gewissen Wahrscheinlichkeit verändert. Die neuen Individuen werden durch die Zielfunktion bewertet und in die Population eingefügt, wobei Individuen der Population durch die Nachkommen ersetzt werden. Damit ist eine neue Population erstellt. Wenn das Abbruchkriterium noch nicht erfüllt ist, beginnt der Prozeß der Erstellung einer neuen Population von vorn.
Ein einfacher Evolutionärer Algorithmus, wie er gerade beschrieben wurde, ist leistungsstark und arbeitet auf einer breiten Klasse von Problemen gut.
Abbildung 3-2: Struktur eines erweiterten Evolutionären Algorithmus
Allerdings gibt es eine Anzahl von Erweiterungen, durch die bessere Ergebnisse erzielt werden können. Dies beinhaltet vor allem eine erweiterte Behandlung der Population, z.B. Unterteilung der Population in Unterpopulationen, Anwendung verschiedener Strategien für jede Unterpopulation und miteinander konkurrierende Unterpopulationen. In diesen Erweiterungen verhält sich jede Unterpopulation wie die Gesamtpopulation in einem einfachen Evolutionären Algorithmus, es werden nur zusätzliche Elemente eingeführt.
Die erweiterten Evolutionären Algorithmen sind leistungsfähiger als einfache Evolutionäre Algorithmen. Außerdem modellieren sie die Evolution in einer Art, die der in der Natur vorhandenen ähnlicher ist, als dies bei einfachen Evolutionären Algorithmen der Fall ist.
Evolutionäre Algorithmen unterscheiden sich in einigen Punkten von traditionellen Such- und Optimierungsverfahren. Die wichtigsten Unterschiede sind:
Im folgenden werden die einzelnen Operatoren eines Evolutionären Algorithmus mit einigen wichtigen Verfahren aufgezählt. Die Erläuterung der einzelnen Verfahren erfolgt in den nachfolgenden Abschnitten.
Die Selektion entscheidet, welche Individuen für die Fortpflanzung ausgewählt werden und wieviele Nachkommen jedes der selektierten Individuen produziert. Der erste Schritt ist die Fitneßzuweisung für jedes Individuum durch eines der folgenden Verfahren:
Die direkte Auswahl (Selektion) der Individuen wird im nächsten Schritt durchgeführt. Eltern werden entsprechend ihrer Fitneß mittels eines der folgenden Verfahren ausgewählt:
Durch die Rekombination werden aus den Eltern die Nachkommen erstellt. Dazu wird die Information der Eltern miteinander kombiniert (die Eltern sind die Paarungspopulation). In Abhängigkeit der Repräsentation der Variablen in den Individuen und des Einsatzzweckes (Art der Zielfunktion) können verschiedenen Verfahren angewendet werden:
Nach der Rekombination werden die Nachkommen einer Mutation unterzogen. Dabei werden die Variablen der Nachkommen durch kleine Störungen (Mutationsschritt) verändert. Diese Veränderungen geschehen mit einer geringen Wahrscheinlichkeit. In Abhängigkeit von der Repräsentation der Variablen und der Art der Zielfunktion können u.a. die folgenden Verfahren verwendet werden:
Nachdem die Nachkommen produziert wurden, müssen sie in die Population eingefügt werden. Dies ist besonders dann wichtig, wenn die Nachkommen nicht einfach die Elternpopulation ersetzen, sondern z.B. weniger Individuen produziert wurden, als in der Population enthalten sind oder wenn nicht alle produzierten Nachkommen in die Population eingefügt werden sollen. Durch das Wiedereinfügeverfahren wird entschieden, welche Nachkommen in die Population eingefügt werden und welche Individuen der Population ersetzt werden ("sterben").
Durch die erweiterte Behandlung von Populationen lassen sich eine Anzahl von Erweiterungen für den Evolutionären Algorithmus definieren, die zur Leistungssteigerung in der Anwendung beitragen.
Es lassen sich folgende Erweiterungen unterscheiden:
Eine ausführliche Behandlung dieser Erweiterungen erfolgt in Kapitel 4, ab S..
Im engeren Sinne gehört die Auswertung der während der Arbeit des Evolutionären Algorithmus entstandenen Datenmengen nicht zum Evolutionären Algorithmus. Allerdings entscheiden gerade diese Auswertungsverfahren und -methoden, wie gut die verschiedenen Operatoren und ihre Kombinationen angewendet werden können. Die Entwicklung bzw. Zusammenstellung spezieller Evolutionärer Algorithmen, die an bestimmte Aufgabenstellungen oder Problemklassen angepaßt sind, ist ohne leistungsfähige Visualisierungsmethoden nur schwer möglich. Weiterhin müssen für die Archivierung von Ergebnissen geeignete Protokollierungsmethoden bereitgestellt werden, die alle notwendigen und nur die notwendigen Daten aufzeichnen.
Eine ausführliche Behandlung von Visualisierungsmethoden wird in Kapitel 5, ab S. vorgenommen. Im Abschnitt 5.6, ab S. wird auf die Protokollierung von Daten und Ergebnissen eingegangen.
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).