4.1 Klassifikation von Populationsmodellen

In mehreren Arbeiten wurden Klassifikationen für Populationsmodelle (parallele Modelle) Evolutionärer Algorithmen vorgenommen, u.a. in [CF94], [Can95] und [Swm96]. Für die Parallelisierung der Berechnungen und damit die Unterteilung der Population wurden zwei Ansätze benutzt:

• Änderungen der Struktur der Population und
• neue Methoden zur Selektion der Individuen.

Chipperfield schlägt eine Unterteilung in folgende Gruppen vor [CF94]:

1. globales Modell (worker/farmer Algorithmus oder farming Modell),
2. Migrationsmodell und
3. Diffusionsmodell.

Cantu-Paz unterscheidet die folgenden Modelle [Can95]:

1. globales Modell,
2. grobkörniges Modell (coarse grained ),
3. feinkörniges Modell (fine grained ) und
4. hybrides Modell (Kombination von Teilen der ersten drei Modelle).

Von Schwehm wird ein Vergleich dieser und anderer Klassifikationen vorgenommen [Swm96]. Die von Schwehm neu vorgeschlagene Klassifikation unterscheidet danach, in welchem Bereich der Population die Auswahl der Individuen zur Generierung neuer Individuen stattfindet (Reichweite der Selektionsstrategien zur Auswahl der Eltern) und unterteilt sich in:

1. globales Modell,
2. regionales Modell und
3. lokales Modell.

Diese Unterteilung wird als die beste der bekannten Klassifikationen angesehen. Sie ermöglicht eine zutreffende und verständliche Unterscheidung der Populationsmodelle. Außerdem setzt die Benennung nicht auf Nebeneffekte oder Merkmale, die bei den einzelnen Populationsmodellen anzutreffen sind. Statt dessen wird hier ein Unterscheidungsmerkmal genutzt, das bei allen Populationsmodellen auftritt. Dadurch wird eine einheitliche Unterscheidung ermöglicht.

In Abbildung 4-1 wird die zur Unterscheidung der Populationsmodelle herangezogene Reichweite der Selektion (Selektionspool) dargestellt (nach [Swm96]). Beim globalen Modell findet die Auswahl der Eltern in der gesamten Population statt. Das regionale Modell beschränkt die Auswahl der Eltern auf voneinander getrennte Teile der Population, die Unterpopulationen genannt werden. Innerhalb der Unterpopulationen findet die Auswahl zwischen allen Individuen statt. Beim lokalen Modell findet die Auswahl der Eltern in lokalen Nachbarschaften statt.

Abbildung 4-1: Klassifikation der Populationsmodelle nach der Reichweite der Selektion

Der Vorteil der Klassifikation in globales, regionales und lokales Modell zeigt sich auch daran, daß sich die Klassifikationen von Chipperfield und Cantu-Paz direkt den entsprechenden Einträgen der Klassifikation von Schwehm zuordnen lassen. So entspricht das Migrations- bzw. grobkörnige Modell dem regionalen Modell von Schwehm, das Diffusions- bzw. feinkörnige Modell dem lokalen Modell.

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