4 Behandlung von Populationen

Zu Beginn der Arbeit mit Evolutionären Algorithmen wurde ausschließlich eine gesamte Population verwendet. Mit der Verfügbarkeit von Parallelrechnern wurden Versuche zur Parallelisierung der Berechnungen durchgeführt. Die Motivation dafür kam aus verschiedenen Bereichen. Zunächst stand der Gedanke dahinter, daß auf diese Weise die Berechnungen auf mehrere Prozessoren verteilt werden können, wodurch sich die Rechenzeiten deutlich verringern lassen. Dadurch ergab sich gleichzeitig die Möglichkeit, Evolutionäre Algorithmen auf deutlich größere Probleme als bisher anzuwenden.

Für die Parallelisierung der Berechnungen mußte eine Unterteilung der Gesamtpopulation vorgenommen werden. Es wurden verschiedene Modelle und Varianten der Unterteilung der Gesamtpopulation bzw. der Verteilung der Individuen auf die verschiedenen Prozessoren vorgestellt. Gemeinsam ist diesen Unterteilungen der Population, daß die Teile voneinander getrennt sind und trotzdem miteinander in Verbindung stehen. Je nach Unterteilung der Gesamtpopulation und der Art der Verbindung der Teile lassen sich verschiedene Populationsmodelle unterscheiden.

Bei frühen Anwendungen der Populationsmodelle wurden bald Vorteile dieser erweiterten Evolutionären Algorithmen gefunden, die mit einfachen Evolutionären Algorithmen nicht zu erreichen waren. Diese Vorteile konnten auf die verwendeten Populationsmodelle (und nicht auf die Parallelisierung der Berechnungen) zurückgeführt werden.

In diesem Kapitel werden die verschiedenen Populationsmodelle vorgestellt und teilweise ausführlich erläutert. Ausgehend davon werden Erweiterungen eines der Populationsmodelle eingeführt und ausführlich in Struktur, Funktion und Parametern sowie ihrer Anwendung erläutert. Die Beschreibungen in diesem Kapitel sind unabhängig davon, ob der Evolutionäre Algorithmus auf paralleler Hardware implementiert oder auf serielle Weise abgearbeitet wird. Die hier in einer seriellen Implementierung gewonnenen Erkenntnisse sind auf eine parallele Implementierung direkt übertragbar.

Im ersten Abschnitt wird eine Übersicht zu Klassifikationen von Populationsmodellen gegeben. Nach einer Bewertung der verschiedenen Klassifikationen wird die Unterteilung der Populationsmodelle nach dem Bereich der Selektion in globales, regionales und lokales Modell ausgewählt und als Grundlage für die weiteren Ausführungen ausführlicher erläutert.

In den nachfolgenden Abschnitten wird jeweils auf ein einzelnes Populationsmodell eingegangen. Besonders ausführlich werden das regionale und das lokale Modell vorgestellt. Die umfassenden Darstellungen der Verfahren und Parameter, verbunden mit der Erläuterung der Vor- und Nachteile, charakterisieren die Populationsmodelle ausführlich. "Neue" Populationsmodelle lassen sich dadurch leicht einem der vorgestellten Populationsmodelle zuordnen.

Nach der Vorstellung der Populationsmodelle werden Erweiterungen eines der Populationsmodelle, des regionalen Modells, vorgestellt. Zum ersten ist dies die Anwendung verschiedener Strategien, zum zweiten der Einsatz miteinander konkurrierender Unterpopulationen. Neben der Beschreibung der Prinzipien wird auf den Einsatz der Erweiterungen und deren Vorteile eingegangen. Die Erweiterungen des regionalen Modells stellen leistungsfähige Verfahren zur Untersuchung von verschiedenen Konfigurationen und zur Kombination der Vorteile mehrerer Verfahren in einem Lauf dar, die mit einer einheitlichen Population oder einem einfachen Populationsmodell nicht erreichbar wären. Weiterhin imitieren diese Erweiterungen Verfahren bzw. Prinzipien, die auch in der biologischen Evolution zu beobachten sind.

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).