HTW Dresden > GaFrame
 

Implementierte Verfahren

Trotz Austauschbarkeit und Flexibilität ist es nicht sinnvol,l alle Standardverfahren, die im Gebiet der Genetischen Algorithmen bekannt und bewährt sind, für jeden Anwendungsfall neu zu schreiben. Aus diesem Grund haben wir einige dieser Verfahren direkt in GaFrame eingebaut, damit ein Nutzer möglichst schnell zu Ergebnissen gelangen kann.

Natürlich haben wir nicht alle uns bekannten Verfahren für die einzelnen Phasen implementiert, sondern nur diese, die uns als sinnvoll erschienen und die wir in den parallel laufenden Belegen nutzen wollten.

Im Folgenden wollen wir die gewählten Verfahren weiter erläutern.

Initialisierung

Zur Initialisierung des Evolutionsprozesses haben wir zwei Implementierungen beigefügt. Das Standardverfahren, welches verwendet wird, arbeitet nach dem Zufallsprinzip. Hierbei wird die Bit-Kombination des Chromosoms zufällig bestimmt und anschließend die Fitness für die Individuen berechnet. Weiterhin gestattet es eine Überinitialisierung, deren Grad mittels der Methode void setInitializationCoeff(double initializationCoeff) gesetzt werden kann. Als Standardwert ist hier 1.0 vorgegeben, was zu keiner Überinitialisierung führt. Dies hat den Grund, dass die Fitnessberechnung unter Umständen sehr lange dauern kann und ein zu optimistisch gewählter Wert das System extrem ausbremsen würde. Nach der Initialisierung werden dann die fittesten Individuen dem Evolutionsprozess zugeführt (entsprechend der Populationsgröße).

Das zweite Verfahren ist kein Initialisierungsverfahren im klassischen Sinne. Es stellt lediglich die Möglichkeit dar, eine als XML-Datei abgespeicherte Population zu laden, um einen vorangegangenen Evolutionsprozess weiter zu führen. Diese Klasse nutzt dabei die Funktionalität, welche durch eine Util-Klasse des GaFrames angeboten wird. Nähere Informationen finden Sie hierzu in der javadoc-Dokumentation für die Klasse de.htwdd.ga.util.GaXmlUtil.

Selektion

Auch für den Prozess der Selektion haben wir zwei Verfahren implementiert und dem GaFrame beigefügt. Die RandomSelection stellt eine einfache und performante Variante dar, die Paare von Heiratskandidaten zufällig bestimmt und auswählt. Dieses Verfahren sollte zum Experimentieren genutzt werden. Sind die Ergebnisse nicht befriedigend, sollten Sie die RankingSelection nutzen. Die rangbasierte Selektion hat eine höhere Laufzeitkomplexität, welche sich, je nach Problem, durch besserer Konvergenz relativieren kann.

Rekombination (Crossover)

Zum eigentlichen "verheiraten" der Individuen haben wir zwei einfache Crossover-Verfahren eingebaut. Standardmäßig wird SinglePointCrossover genutzt, es steht aber ebenfalls die Klasse TwoPointCrossover zur Verfügung. Eine Darstellung über die Wirkungsweise finden Sie unter "Optionale Konfigurationsmöglichkeiten" (Kreuzungsverfahren) im Abschnitt Nutzung.

Ersetzungsschema

Wir haben uns hier für den Elitismus entschieden und in der Klasse Elitism implementiert. Dieses Verfahren schien uns am sinnvollsten. Das Verfahren bildet eine Folgepopulation für die nächste Generation im Evolutionsprozess. Hierzu führt es die aktuelle Population (population) und die Kinder (children) zusammen. Natürlich unter Einhaltung der Populationsgröße, die den Einschränkungen entsprechend konstant sein soll.

Mutation

Die Mutation ist direkt in der Klasse Individual untergebrach und die entsprechende Methode des Individuums wird ausgeführt, nachdem das Ersetzungsschema die Folgepopulation erstellt hat. Nach dem Mutieren muss eventuell erneut geprüft werden, ob die Fitness der Individuen noch aktuell ist. Andernfalls muss sie neu berechnet werden.

Natürlich wird in GaFrame nicht jedes Individuum mutiert, sondern es wird mittels einer Mutationswahrscheinlichkeit angegeben, wie hoch die Wahrscheinlichkeit sein soll, dass ein Individuum mutiert werden soll. Wurde ein Individuum für die Mutation ausgewählt, wird zufällig ein Bit ermittelt und "umgekippt".

Graycodierung

Es ist auch die Möglichkeit vorgesehen, die Chromosomen mittels einer Graycodierung zu verschlüsseln. Hierzu genügt es, der statischen Methode void doGrayCoding(BitSet bitSet) der Klasse de.htwdd.ga.util.BitSetUtil aufzurufen. Zum Entschlüsseln in der Fitnessfunktion können Sie das Chromosom mittels void doInvGrayCoding(BitSet bitSet) zurück transformieren.