3.5 Wiedereinfügen (Reinsertion)

Nachdem die Nachkommen produziert und bewertet wurden, müssen sie in die Population eingefügt werden. Durch das Wiedereinfügen wird entschieden:

• wieviele und welche Nachkommen in die Population eingefügt werden und
• welche Individuen der Population durch die einzufügenden Nachkommen ersetzt werden.

Eine Auswahl der Nachkommen muß nur durchgeführt werden, wenn nicht alle produzierten Nachkommen in die Population eingefügt werden sollen. Der Parameter dafür ist die Wiedereinfügerate (insertion rate). Die Wiedereinfügerate gibt an, wieviele der Individuen einer Population maximal durch Nachkommen zu ersetzen sind. Bei einer Wiedereinfügerate von 1.0 hieße dies, daß alle Individuen der Population durch Nachkommen ersetzt werden können. Wenn die Populationsgröße konstant sein soll, kann die Wiedereinfügerate maximal einen Wert von 1.0 annehmen.

Wieviele Nachkommen produziert wurden, hängt vom Parameter generation gap (engl.: ,,Generationslücke") ab.

Beide Parameter zusammen - generation gap und Wiedereinfügerate - bestimmen, wieviele der Nachkommen eingefügt werden. Ist die Wiedereinfügerate _ generation gap, so werden alle Nachkommen in die Population eingefügt. Ist die Wiedereinfügerate dagegen kleiner als das generation gap, so wird nur ein Teil der Nachkommen in die Population eingefügt.

Diese verallgemeinernde Betrachtungsweise durch beide Parameter, generation gap und Wiedereinfügerate, ermöglicht die einschließende Angabe verschiedener Varianten, die bisher als eigenständige Einheiten betrachtet wurden.

1. einfaches Wiedereinfügen (pure reinsertion):
• generation gap = 1.0 und Wiedereinfügerate = 1.0,
• es werden genau so viele Nachkommen wie Individuen in der Population erzeugt und alle Nachkommen ersetzen alle Individuen der Population.
2. zufälliges bzw. elitest Wiedereinfügen (uniform bzw. elitest reinsertion):
• generation gap < 1.0 oder Wiedereinfügerate < 1.0,
• es werden weniger Nachkommen als Individuen in der Population in die Population eingefügt, die Individuen der Population werden durch die Nachkommen gleichverteilt zufällig (uniform reinsertion) ersetzt bzw. die schlechtesten Individuen der Population (elitest reinsertion) werden ersetzt.
3. Wiedereinfügen mit Auswahl der Nachkommen (reinsertion with offspring selection):
• generation gap > Wiedereinfügerate,
• es wird nur ein Teil der Nachkommen [Wiedereinfügerate/generation gap %] in die Population eingefügt. Zum Einfügen werden die besten Nachkommen verwendet (Truncation-Selektion).

Das einfache Wiedereinfügen wird in vielen einfachen Evolutionären Algorithmen verwendet. Jedes Individuum hat dabei eine Lebensdauer von genau einer Generation. Da die bisher besten Individuen in jeder Generation durch Nachkommen ersetzt werden, ist nicht gesichert, daß ihre Information in der Population erhalten bleibt. Die Güte des besten Individuums der Population kann schlechter werden.

Dies kann durch den Einsatz des elitest Wiedereinfügen verhindert werden. Dabei wird sichergestellt, daß die bisher besten Individuen der Population in der Population verbleiben und nur ersetzt werden, wenn bessere Individuen gefunden wurden. Das elitest Wiedereinfügen entspricht dem, was in vielen Veröffentlichungen als elitest Selektion bezeichnet wird. Vom algorithmischen Ablauf her hat dies aber nichts mit der Selektion zu tun, sondern muß im Zusammenhang des Wiedereinfügen betrachtet werden. Das elitest Wiedereinfügen wird bei vielen Evolutionären Algorithmen verwendet, um sicherzustellen, daß das beste Individuum/die besten Individuen nicht verloren gehen. Dazu wird das generation gap auf einen Wert knapp unter eins gesetzt, es werden fast so viele Nachkommen wie Individuen in der Population erzeugt und alle Nachkommen werden in die Population eingefügt, wobei die besten Individuen nicht ersetzt werden. Es sollte beachtet werden, daß das beste Individuum nicht in die neue Population übernommen wird, sondern die Nachkommen ersetzen das beste Individuum der Population nicht. Einen Spezialfall davon stellen die steady-state Evolutionären Algorithmen dar. Bei diesen ist das generation gap so klein, daß nur wenige Individuen pro Generation produziert werden, die danach in die Population eingefügt werden (zufälliges oder elitest Wiedereinfügen bzw. Ersetzen der Eltern).

Die dritte Variante, bei der nur ein Teil der Nachkommen zum Einfügen ausgewählt wird, kann einmal zu einer vollständigen Ersetzung der Individuen der Population führen (Wiedereinfügerate = 1.0) oder es wird das elitest Wiedereinfügen (Wiedereinfügerate < 1.0) verwendet. Durch die Selektion zwischen den Nachkommen, bevor diese in die Population eingefügt werden, erhalten die schlechten Nachkommen keine Chance zur Produktion von eigenen Nachkommen. Diese Variante wird dann benutzt, wenn ein Individuum im Durchschnitt mehrere Nachkommen produziert, wie dies z.B. bei den Verfahren der Evolutionsstrategie der Fall ist, siehe Unterabschnitt 3.4.2, S.. Jedes Individuum produziert dabei z.B. fünf Nachkommen (generation gap = 5), von denen im Durchschnitt nur eins ausgewählt wird (Wiedereinfügerate = 1.0). Durch diese Sichtweise ist es möglich, den Ablauf einer Evolutionsstrategie im selben Kontext wie andere Evolutionäre Algorithmen zu betrachten.

Beim Wiedereinfügen ist zu beachten, daß die Nachkommen in genau den Selektionspool eingefügt werden, aus dem die Eltern ausgewählt wurden (globales Modell: gesamte Population; regionales Modell: Unterpopulation; lokales Modell: Nachbarschaft). Für das globale und regionale Modell gelten direkt die hier gemachten Angaben, auf die Besonderheiten des lokalen Wiedereinfügen, das bei der Verwendung einer lokalen Selektion verwendet werden muß, wird in Unterabschnitt 4.4.4, S. eingegangen.

Die bisherigen Varianten des Wiedereinfügen können erweitert werden, wenn das Alter eines Individuums mit in Betracht gezogen wird. Dazu wird zuerst betrachtet, wie lange bzw. wieviele Generationen bei den bisherigen Varianten ein Individuum in der Population bleibt:

• einfaches Wiedereinfügen:
• die Lebensdauer eines Individuums beträgt genau eine Generation,
• elitest Wiedereinfügen: die durchschnittliche Lebensdauer eines Individuums ist umgekehrt proportional zum Anteil der neuen Individuen pro Generation,
• bei einem generation gap nahe 1 (Wiedereinfügerate wird auf 1.0 gesetzt) beträgt die Lebensdauer der meisten Individuen nur eine Generation, die besten Individuen können aber viele Generationen in der Population verbleiben (elitest Selektion),
• bei einem sehr kleinen generation gap (Wiedereinfügerate wird auf 1.0 gesetzt), dies entspricht einem steady-state Algorithmus, würden die Individuen viele Generationen in der Population verbleiben.

Die durchschnittliche Lebensdauer eines Individuums der Population ergibt sich damit aus:

(3-23)

Wenn das Alter der Individuen berücksichtigt wird, kann ein maximales Alter für ein Individuum angegeben werden. Diese maximale Lebensdauer sollte im Vergleich zur durchschnittlichen Lebensdauer angegeben werden und muß immer größer 1 sein. Sobald ein Individuum die maximale Lebensdauer erreicht hat, wird es zuerst von neuen Nachkommen ersetzt, noch bevor jüngere Individuen ersetzt werden (auch wenn die jüngeren Individuen schlechter als die zu alten Individuen sind).

Durch die Definition eines maximalen Lebensalters kann verhindert werden, daß einmal sehr gute Individuen für eine zu große Zahl an Generationen in der Population verbleiben. Dies wird besonders dann wichtig, wenn mit einem kleinen generation gap, elitest Wiedereinfügen und einem höheren Selektionsdruck gearbeitet wird. Die wenigen bisher guten Individuen werden immer wieder als Eltern ausgewählt und die Nachkommen ersetzen immer nur die schlechtesten Individuen, der Algorithmus kann steckengeblieben. Durch ein Ersetzen und damit Verwerfen der alten Individuen nach einiger Zeit kann mehr neue Information in die Population eingebracht und unter Umständen ein Steckenbleiben verhindert werden.

Das Prinzip der Einbeziehung des Alters von Individuen findet sich überall in der Natur. Bei einfachen Lebewesen leben Individuen oft nur über eine Generation bzw. die gleichzeitig in einer Population lebenden Individuen haben alle etwa ein Alter. Bei etwas höher entwickelten Lebewesen können einzelne besonders gute Individuen mehrere Generationen erleben bzw. ein höheres Alter im Vergleich zu den anderen Individuen erreichen. Bei den höheren Lebewesen wird auf einmal nur ein kleiner Teil der Population neu gebildet und jedes Individuum erreicht ein Alter, daß in etwa proportional seiner Güte ist. Dieses Alter umfaßt im Allgemeinen ein mehrfaches dessen, was jeweils an Zeit zur Produktion von Nachkommen benötigt wird. Trotzdem kann ein maximales Alter nicht überschritten werden bzw. ab einem bestimmten Alter können keine Nachkommen mehr erzeugt werden. Es spricht damit einiges dafür, abgesehen von den Bemerkungen im vorigen Absatz, daß besonders bei komplexeren Algorithmen bzw. Problemen die Berücksichtigung des Alters sinnvoll ist.

Ähnliche Überlegungen wurden auch in anderen Arbeiten angestellt, u.a. in [SK92] ("Verhinderung eines genetischen Einfrierens").

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