Ersetzungsverfahren in Kontext von Genetischen Algorithmen

Nachdem wir im letzten Artikel Nachkommen für unsere Population erzeugt haben, muss nun entschieden werden welche dieser Nachkommen in der neuen Generation verwendet werden sollen. Dafür verwendet man sogenannte Ersetzungsverfahren (Replacement Schema). Diese wollen wir uns in diesem Artikel etwas genauer anschauen.

Ersetzungsverfahren im Allgemeinen

Mittels des Ersetzungsverfahren soll ermittelt werden, welche Individuen in der aktuellen Generation ersetzt werden sollen.

Hier gibt es ganz verschiedene Ansätze um dies zu realisieren. Ich habe mich in meinem Projekt mit den folgenden vier Verfahren beschäftigt und diese auch alle in C# realisiert.

• General Replacement
• Principle of the Elites
• Weak Elitism
• delete-n-latest Schema

Da ich hier im Quellcode einige Verschachtelungen mit den Rekombinationsverfahren habe, verzichte ich in diesem Artikel auf Quellcode Beispiele. Ihr könnt euch aber die gesamte Klasse im Repository auf GitHub anschauen.

General Replacement

Dies ist aus meiner Sicht das einfachste Verfahren. Hier werden alle Individuen der vorhanden Generation durch die Individuen im Marting Pool (Kinder) ersetzt

Hierbei besteht allerdings die Gefahr, gute Individuen aus der alten Generation zu verlieren. Dadurch wird auch die durchschnittliche Qualität der gesamten Generation verringert.

Man hat aber den Vorteil, dass die Wahrscheinlichkeit in einem lokalen Maximum stecken zu bleiben relativ gering ist.

Principle of the Elites

Bei diesem Verfahren bleibt eine Teilmenge der Elterngeneration erhalten. Meistens handelt es sich dabei um die Individuen mit der besten Fitness.

Es werden also n Individuen mit der schlechtesten Fitness aus der Elterngeneration mit Kindern aus dem Marting Pool ersetzt.

Hier ist die Gefahr in einem lokalen Maximum hängen zu bleiben relative hoch, da immer die besten Individuen in die neue Generations überführt werden.

Weak Elitism

Der schwache Elitismus funktioniert im wesentlich genau so wie das Principle of the Elites.

Der Unterschied ist, dass die aus der vorherigen Generation übernommenen Individuen mutiert werden.

delete-n-latest Schema

In diesem Verfahren werden alle generierten Kinder in die neue Generation übernommen. Die n schlechtesten Kinder werden dabei durch Individuen aus der vorherigen Generations ersetzt.

Falls euch der Artikel gefallen hat, ist vielleicht die ganze Artikelserie für euch interessant. Schaut doch mal in den ersten Artikel Grundlagen Genetische Algorithmen rein.