6.4 Zentralfunktion
6.4 Zentralfunktion |
|
Von allen Toolboxfunktionen wird jeweils die Zentralfunktion der Toolbox aufgerufen:
In der Zentralfunktion findet die gesamte Verwaltungsarbeit statt. Aus den übergebenen Parametern werden Datenstrukturen erstellt, die von den untergeordneten Funktionen benutzt werden. Die Namen der geforderten Operatoren werden ermittelt und zugewiesen. Die Initialisierung der Population wird durchgeführt. Danach folgt die Ausführung des Evolutionären Algorithmus mit der einhergehenden Anzeige und Sicherung von Daten und Ergebnissen.
Von der Zentralfunktion werden für die Ausführung des Evolutionären Algorithmus nur high-level Funktionen aufgerufen. Dies ermöglicht eine einfache Unterstützung der verschiedenen Konzepte zur Behandlung von Populationen, speziell des regionalen Modells. Der Ablauf des Evolutionären Algorithmus läßt sich durch die folgenden Schritte und die korrespondierenden Funktionen untergliedern:
Innerhalb der high-level Funktionen werden die parametrisierten evolutionären Operatoren (low-level Funktionen) aufgerufen.
6.4.1 Initialisierung |
|
Eine Initialisierung findet in der Zentralfunktion an zwei Stellen statt. Zuerst werden die übergebenen Parameter für die einzelnen Operatoren und die Arbeitsweise des Evolutionären Algorithmus den internen Parameterstrukturen zugewiesen. Danach erfolgt die Erstellung bzw. Initialisierung der Individuen der ersten Generation.
Die Initialisierung der Parameter (Mapping von Parameterzahlen auf Namen der Operatorfunktionen) findet in der Funktion gatbxini statt.
Die Initialisierung der Individuen der ersten Generation kann zufällig mit einer in der Toolbox enthaltenen Funktion oder durch eine benutzerspezifische Funktion erfolgen:
Funktion |
Beschreibung |
initrp |
initialisiert eine Population von Individuen mit reellen Variablen |
initbp |
initialisiert eine Population von Individuen mit binären/ganzzahligen Variablen |
initdopi |
benutzerspezifische Funktion zur Initialisierung einer Population von Individuen (hier Initialisierung passend zur Zielfunktion objdopi - Optimierung der Steuerung des Doppelintegrators) |
Tabelle 6-4: Initialisierungsfunktionen für Individuen
6.4.2 Fitneßzuweisung |
|
Für die Fitneßzuweisung wird nur eine Funktion benötigt:
Diese verwendet in Abhängigkeit des parametrierten Selektionsdruckes lineares oder nichtlineares Ranking. Eine low-level Funktion wird nicht benötigt.
6.4.3 Selektion |
|
Eine einheitliche Schnittstelle für alle Selektionsoperatoren wird durch eine high-level Funktion bereitgestellt:
In Abhängigkeit des parametrierten Selektionsalgorithmus ruft diese Funktion für jede Unterpopulation den jeweiligen Selektionsoperator auf, der dann die direkte Auswahl der Individuen durchführt.
Funktion |
Beschreibung |
selsus |
stochastic universal sampling |
selrws |
Rouletteselektion |
seltrunc |
Truncation-Selektion |
seltour |
Turnierselektion |
sellocal |
lokale Selektion (lokales Modell) |
Tabelle 6-5: Selektionsoperatoren
6.4.4 Rekombination |
|
Für alle Rekombinationsverfahren steht mit einer high-level Funktion eine einheitliche Schnittstelle zur Verfügung:
Je nach parametriertem Rekombinationsalgorithmus wird für jede Unterpopulation der entsprechende Rekombinationsoperator aufgerufen. Hierbei muß darauf geachtet werden, daß die Variablen der Individuen durch den jeweiligen Operator sinnvoll rekombinierbar sind. Soweit möglich werden entsprechende Kompatibilitätstests durchgeführt. (Durch die Verwendung fertiger Toolboxfunktionen kann dieses Problem leicht umgangen werden.)
Funktion |
Beschreibung |
recdis |
diskrete Rekombination |
recint |
intermediäre Rekombination |
reclin |
Linien-Rekombination |
reclinex |
erweiterte Linien-Rekombination |
recfuzzy |
Fuzzy-Rekombination |
xovsp |
single point crossover |
xovdp |
double point crossover |
xovsh |
shuffle crossover |
xovsprs |
single point crossover mit reduced surrogate |
xovdprs |
double point crossover mit reduced surrogate |
xovshrs |
shuffle crossover mit reduced surrogate |
xovbin |
crossover für binäre Variablen |
Tabelle 6-6: Rekombinationsoperatoren
Alle Rekombinationsoperatoren für binäre Variablen (xov* - Crossoverfunktionen) sind intern auf eine Funktion, xovbin, zurückgeführt, die alle Rekombinationsalgorithmen für binäre Variablen implementiert und jeweils nur mit anderen Parametern aufgerufen wird.
Für ganzzahlige Variablen werden im Moment keine speziellen Rekombinationsoperatoren bereitgestellt. Allerdings kann für diese die diskrete Rekombination, recdis, genutzt werden (wie für alle anderen Repräsentationen auch). Einfacher ist dagegen die Umwandlung der ganzzahligen Variablen in entsprechende binäre Variablen und die Verwendung der Operatoren für binäre Variablen. Dieses Vorgehen wird von der GEA Toolbox durch Angabe eines Parameters automatisch und damit transparent für den Nutzer durchgeführt.
6.4.5 Mutation |
|
Genau wie die Rekombination wird die Mutation über eine high-level Funktion aufgerufen, die eine einheitliche Schnittstelle für die verschiedenen Mutationsoperatoren bietet:
Trotz einer recht unterschiedlichen Arbeitsweise, verschiedener Parameter und anderer Datenstruktur wird durch die Integration innerhalb der GEA Toolbox eine einheitliche Handhabung aller Mutationsoperatoren ermöglicht. Jede Unterpopulation wird mit dem jeweils festgelegten Mutationsoperator bearbeitet (regionales Modell). Für reelle Variablen stehen verschiedene Mutationsoperatoren zur Auswahl.
Funktion |
Beschreibung |
mutbmd |
diskrete Mutation des Breeder Genetic Algorithm [MSV93a] |
mutbmc |
kontinuierliche Mutation des Breeder Genetic Algorithm [SVM96] |
mutevo1 |
Mutation einer Evolutionsstrategie "derandomized ES-algorithm with individual step sizes" [OGH93] |
mutevo2 |
Mutation einer Evolutionsstrategie "derandomized mutative step-size control using accumulated information" [OGH93] |
mutbint |
Mutation binärer und ganzzahliger (integer) Variablen |
Tabelle 6-7: Mutationsoperatoren
6.4.6 Wiedereinfügen |
|
Zum Einfügen der Nachkommen in die Population wird eine high-level Funktion bereitgestellt:
Entsprechend dem verwendeten Populationsmodell wird von dieser Funktion eine low-level Funktion zum Einfügen der Nachkommen aufgerufen:
Die Wahl der Wiedereinfügefunktion hängt nur von der Art des Selektionsoperators ab. Bei der Verwendung einer lokalen Selektion muß auch das lokale Wiedereinfügen verwendet werden. Diese Entscheidung wird in der high-level Wiedereinfügefunktionen automatisch vorgenommen.
6.4.7 Migration - regionales Modell |
|
Das regionale Modell wird durch die Zentralfunktion sowie alle high-level Funktionen unterstützt. Für den Austausch von Individuen zwischen den Unterpopulationen (Migration) wird eine Funktion bereitgestellt, die alle Fähigkeiten enthält, die in Unterabschnitt 4.3, ab S., erläutert wurden:
Die Funktionsweise der Migration kann mit wenigen Parametern komplett von außen gesteuert werden.
6.4.8 Konkurrenz zwischen Unterpopulationen |
|
Für die Durchführung der Konkurrenz zwischen den Unterpopulationen wird eine Funktion bereitgestellt, welche die gesamte Funktionalität aus Unterabschnitt 4.6, ab S., beinhaltet:
Die Anwendung dieser Funktion setzt die Nutzung des regionalen Modells voraus.
Die Funktionsweise der Konkurrenz zwischen den Unterpopulationen kann mit wenigen Parametern komplett von außen gesteuert werden.
Die Verwendung verschiedener Strategien für die einzelnen Unterpopulationen ist direkter Bestandteil der Parametrierung der GEA Toolbox. Eine Definition verschiedener Operatoren oder Parameter für die einzelnen Unterpopulationen führt zum Einsatz verschiedener Strategien je Unterpopulation.
6.4.9 Visualisierung |
|
Die GEA Toolbox unterstützt alle Visualisierungsmöglichkeiten, die in Abschnitt 5, ab S. beschrieben wurden. Alle Grafikfunktionen sind in einer Funktion implementiert:
Die Anzeige problemspezifischer Ergebnisse (Zustandsgrafiken) erfolgt mit speziellen Funktionen, die für jede Zielfunktion einzeln zu definieren sind, z.B.:
6.4.10 Protokollierung |
|
Die Protokollierung von Zwischen- und Endergebnisse ist direkter Bestandteil der Zentralfunktion.
Es besteht die Möglichkeit zur Anzeige der Ergebnisse auf dem Bildschirm. Dadurch ist der Nutzer über den Fortgang und Stand der Berechnungen auf dem Laufenden. Im Vergleich zur Visualisierung werden hierbei nur wenige wichtige Daten angezeigt (Generation, Anzahl der Zielfunktionsaufrufe, Zielfunktionswert des besten Individuums, bei Konkurrenz bzw. unterschiedlichen Strategien auch Größe und Reihenfolge der Unterpopulationen).
Dieselben Angaben, die zur Anzeige auf den Bildschirm kommen, können in einer Textdatei gesichert werden. Dabei wird zusätzlich das beste Individuum (Variablen des Individuums) mit abgespeichert.
Zu Beginn der Berechnungen erfolgt jeweils eine vollständige Anzeige bzw. Speicherung aller Parameter des aktuellen Laufs. Am Ende wird eine Auswertung mit Angabe des besten Individuums, seines Zielfunktionswertes und in welcher Generation es gefunden wurde, gegeben. Außerdem wird die aufgewendete Rechenzeit angezeigt.
Mit diesen Angaben ist einmal eine gute Kontrolle der fortschreitenden Berechnungen möglich und zum anderen durch die Speicherung in eine Textdatei die problemlose spätere Auswertung. Durch die Speicherung der wichtigsten Angaben erfolgt gleichzeitig eine Dokumentation der durchgeführten Berechnungen.
Zusätzlich können alle Daten, die für die Visualisierung benötigt werden, in einer binären Datei (Mat-Datei, spezifisches Format von Matlab) gespeichert werden. Durch einen Parameter wird angegeben, wie oft diese Daten gespeichert werden. Eine spezielle Funktion dient dem späteren Auslesen und Aufbereiten dieser Daten sowie dem Aufruf der Visualisierungsfunktion:
Damit ist die Möglichkeit gegeben, längere Berechnungen ohne Visualisierung durchzuführen und sich hinterher schnell und einfach die Ergebnisse anzuschauen. Gleichzeitig werden dadurch die Möglichkeiten der genauen Dokumentation des Verlaufs und der Ergebnisse verbessert.
6.4.11 Terminierung |
|
Für den Abbruch der Berechnungen werden von der Toolbox verschiedene Möglichkeiten unterstützt, die alle von einer Funktion getestet werden, die von der Zentralfunktion aufgerufen wird:
Mit dieser Funktion kann getestet werden, ob:
Alle diese Kriterien können einzeln oder zusammen angewendet werden. Sobald eines der Kriterien erfüllt ist, werden die Berechnungen beendet. Ein Hinweis über den Grund des Endes der Berechnungen wird in der Auswertung angegeben.
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).
