M. Sc. Konstantin Ernst
Barrierefreie Systeme – Intelligente Systeme
Fachhochschule Frankfurt am Main
info@konstantinernst.de

M. Sc. Benjamin Metka
Barrierefreie Systeme – Intelligente Systeme
Fachhochschule Frankfurt am Main
benjo@stud.fh-frankfurt.de

Genetische Algorithmen sind hervorragend geeignet um Optimierungsprobleme effizient zu lösen, bzw. sich der Lösung in einem zeitlich vertretbaren Rahmen zu nähern. Im Rahmen eines Hochschulprojektes wurde das Konzept des genetischen Algorithmus praktisch auf das Problem des Handlungsreisenden angewandt und implementiert. Das dabei erlangte Wissen wurde in dieser Arbeit dokumentiert. In der vorliegenden Arbeit wird zunächst der Ausgangspunkt, Anwendungsgebiete und Bestandteile des genetischen Algorithmus beschrieben. Hierbei wird auf die einzelnen Teilprozesse eingegangen und ihre Bedeutung im Gesamtkontext betrachtet. Anschließend wird auf unterschiedliche Codierungsformen eingegangen. Im Kapitel „Fitnessfunktion“ werden exemplarisch Fitnessfunktionen bestehender Implementationen aufgeführt und ihre Vor- und Nachteile beschrieben. Das Prinzip der Fitnessfunktion ist leicht verständlich, jedoch stellt ihre Definition bei jeder Implementierung eines genetischen Algorithmus eine besondere Herausforderung dar, deshalb wird hierauf besonderer Fokus gelegt. In den Kapiteln Rekombination (Crossover) und Mutation werden die unterschiedlichen Operatoren schrittweise erläutert: Zunächst wird ihr Konzept und der Grundgedanke allgemein beschrieben. Anschließend wird die Arbeitsweise anhand von Beispielen und Grafiken verdeutlicht. Permutationsoperatoren werden zusätzlich um Quellcodeausschnitte ergänzt, die zeigen, wie der jeweilige Operator im angesprochenen Hochschulprojekt implementiert wurde. Die Operatoren werden somit vom abstrakten Konzept bis hin zur Implementation erläutert. Der Fokus liegt auf Operatoren für Permutationsprobleme, da das Handlungsreisendenproblem, welches im Zentrum des Projektes steht, ein solches Permutationsproblem darstellt. Abgeschlossen wird die vorliegende Arbeit mit einer Auswertung, welche Effizienz, Beständigkeit und Konvergenzgeschwindigkeit ausgesuchter Kombinationen der vorgestellten Operatoren vergleicht.

Im Modul „Wissen“ des Studiengangs „Barrierefreie Systeme - Intelligente Systeme“ an der Fachhochschule Frankfurt am Main werden Bedeutung, Nutzen und die Anwendung genetischer Algorithmen gelehrt. Der Fokus wird hierbei besonders auf Gewicht und Einfluss der einzelnen Phasen und Operatoren in Hinblick auf Konvergenz gerichtet. Im Rahmen dieses Moduls entstand im Wintersemester 2010/11 ein Projekt, welches dieses Wissen praktisch auf das Problem des Handlungsreisenden anwendet und in dessen Rahmen dieses Paper entstand. Das Konzept des genetischen Algorithmus ist auf abstraktem Level einfach, klar und leicht verständlich. Die einzelnen Phasen des genetischen Algorithmus sind klar voneinander getrennt. Bei der praktischen Anwendung wurde schnell klar, dass Aufgabe und Zweck der einzelnen Phasen klar definiert ist, bei der Implementation aber Freiraum gewährt wird. Das verleitet schnell dazu, die Implementation individuell zu gestalten. Eine allgemeine Implementation wird zurzeit von Herrn Prof. Dr. Döben-Henisch, Fachhochschule Frankfurt am Main, entwickelt (vergleiche [2]). Der große Vorteil dieser allgemeinen Implementation ist, dass man sich lediglich darauf konzentrieren muss, die Individuen binär zu codieren und die Fitnessfunktion zu gestalten. Diese muss noch nicht einmal den Fitnesswert normieren. Die restlichen Operatoren müssen nicht angepasst werden. Im ersten Ansatz auf dem Weg der Problemlösung setzten wir das Programm von Herrn Prof. Dr. Döben-Henisch ein, codierten die Individuen binär und beschrieben die Fitnessfunktion. Zu beachten ist hier, dass es sich bei dem zu Grunde liegenden Problem um ein Permutationsproblem handelt. Ein Zusammenhang zwischen den einzelnen Genen lässt sich im Programm von Herrn Prof. Dr. Döben-Henisch nicht definieren und wird dementsprechend auch nicht in den Operatoren berücksichtigt. Die Definition von Relationen der Gene widerspricht dem Konzept einer maximal allgemeinen Implementierung. Es gibt keinen Beweis, der widerlegt, dass es möglich ist, mit einem genetischen Algorithmus, der die Relationen zwischen Genen nicht respektiert, trotzdem ein Reihenfolgenproblem zu lösen. Bisher wurde nicht bewiesen, der sagt, dass es nicht reicht, die Fitnessfunktion geeignet zu beschreiben. In den ersten Projektwochen konzentrierten wir uns ausschließlich auf die Formulierung eben dieser Fitnessfunktion, um das Problem der nicht-respektierten Relationen der Gene zu eliminieren.
Wir entwickelten mehrere Konzepte und formulierten die Fitnessfunktion auf viele erdenkliche Weisen, die Konvergenz ließ jedoch auf sich warten.
Wir sind jedoch davon überzeugt, dass dies dennoch möglich ist. Während der Recherchen nach Informationen und Hinweisen, die Aufschluss darüber geben sollten, wie man eine Fitnessfunktion für die Lösung des Handlungsreisendenproblems formuliert, und die leider sehr rar sind, stießen wir auf einfach formulierte Fitnessfunktionen, aber nur in Verbindung mit Ganzzahlcodierung und angepassten und nicht allgemeinen Crossover- und Mutations-Operatoren. Interessant hierbei war, dass die Individuen und Fitnessfunktionen (in Zusammenhand mit dem Handlungsreisendenproblem) sehr ähnlich oder gar gleich definiert waren, die Operatoren jedoch sehr unterschiedlich. Neben verschiedenen Papern findet man im Internet auch zahlreiche Implementationen, oft in Form von Java-Applets, die das Problem des Handlungsreisenden angehen. Die Vielfalt und grundsätzliche Unterschiedlichkeit der dort beschriebenen Operatoren weckte in uns die Frage, wie sich diese Operatoren im direkten Vergleich verhalten würden. Wann eignet sich welcher Operator? Falls sich ein Operator als effizientester herausstellt, kann er die Spitze auch nach Veränderung der Umwelt, wie beispielsweise eine Veränderung von Anzahl und Position der Städte, halten? Jede Quelle, die von der Lösung des Problems des Handlungsreisenden unter Verwendung des genetischen Algorithmus handelt, stellt lediglich vor, wie dort das Problem selbst gelöst wurde, vergleicht ihre Lösung aber nicht mit anderen Implementationen. Dies motivierte uns, unser Projekt daraufhin zu konzentrieren, die in den unterschiedlichen Quellen beschriebenen Operatoren Hinsichtlich ihrer Effizienz untereinander, und schließlich auch gegenüber dem Zufall zu vergleichen.
Dafür war es notwendig von Binär- auf Ganzzahlcodierung umzusteigen. Im Projektrahmen wurde der genetische Algorithmus auf das Handlungsreisendenproblem bezogen implementiert. Darüber hinaus wurden die gesammelten Operatoren und zwei Fitnessfunktionen implementiert. Diese lassen sich im erstellten Programm frei kombinieren und somit vergleichen.

Evolutionäre Algorithmen sind Methoden zur Lösung von Optimierungsproblemen, die sich dabei an der von Charles Darwin begründeten biologischen Evolutionstheorie orientieren, da die Evolution bereits in der Natur sehr gute Ergebnisse geliefert hat. Im Verlauf der Evolution wurden Individuen an ihre Umwelt und die damit verbundenen „Aufgaben“ angepasst, indem ihre Gene vererbt und teilweise modifiziert wurden. Diese Vorgehensweise hat es ermöglicht ein sehr schweres Optimierungsproblem zu lösen. Dieser biologische Prozess lässt sich grob in wenigen, einfachen Schritten abbilden: Selektion, Rekombination, Mutation. Diese Schritte wurden in die Informatik übertragen. Genetische Algorithmen zählen zu den Evolutionären Algorithmen. Sie eignen sich, um Probleme, die in der Komplexitätsklasse NP liegen, zu lösen, indem sie das Konzept der Evolution auf ein definiertes Ziel anwenden. Die Lösung von Problemen der Komplexitätsklasse NP durch deterministische Algorithmen erfordert exponentiellen Rechenaufwand. Durch die Anwendung genetischer Algorithmen können diese effizienter gelöst werden.

Interessanterweise ist bei der Lösung komplexer Probleme das Prinzip des Zufalls zu jedem Algorithmus immer noch ein harter Konkurrent.

Im Folgenden werden einige bekannte Optimierungsprobleme aufgeführt, für deren Lösungen sich der Einsatz eines genetischen Algorithmus eignet.

Das Rucksackproblem ist auch als Pack- oder Containerproblem bekannt. Dieses Problem tritt in verschiedenen Variationen auf. Grundsätzlich geht es darum, eine Menge Objekte, die in ihren äußeren Abmessungen definiert sind, in einen Raum mit definierten Abmessungen zu positionieren, und dabei das umschließende Volumen zu minimieren. In manchen Formulierungen wird dieses Problem um weitere Bedingungen erweitert, um beispielsweise einen pekunären Wert oder ein Gewicht der Objekte zu berücksichtigen. (Vergleiche [1])

Dieses Problem ist auch als Traveling Salesman Problem oder kurz TSP bekannt. Das Problem des Handlungsreisenden ist ein kombinatorisches Optimierungsproblem. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist. Was einfach klingt wird sehr schnell komplex. Folgende Rechnung soll die Komplexität dieses Problems verdeutlichen: Für n Städte gibt es (n - 1)! / 2 verschiedene Rundreisen, das sind bei 15 Städten über 43 Milliarden und bei 18 Städten bereits über 177 Billionen. Hat man einen Rechner, der die Lösung für 30 Städte in einer Stunde berechnet, dann braucht dieser für zwei zusätzliche Städte annähernd die tausendfache Zeit; das sind mehr als 40 Tage. Dieses Beispiel zeigt, dass sich spätestens ab einer bestimmten Anzahl von Städten der Einsatz eines Algorithmus, beispielsweise dem genetischen Algorithmus, empfiehlt.

Der genetische Algorithmus wird oft angewandt, um Optimierungsprobleme zu lösen. Seine Beliebtheit resultiert unter Anderem auf der Tatsache, dass das Konzept klar und einfach zu verstehen ist und die einzelnen Phasen klar voneinander getrennt sind, was eine einfache und leichte Implementation ermöglicht. In dieser Arbeit wird die Implementierung eines genetischen Algorithmus beschrieben. Die Reihenfolge der Kapitel orientiert sich am Ablauf des genetischen Algorithmus, der in folgender Abbildung schematisch dargestellt wird:

Individuum
Ein Individuum ist ein potentieller Lösungskandidat des zu optimierenden Problems. Es gibt hierfür unterschiedliche Codierungsform. Ein Individuum kann beispielsweise binär, ganzzahlig oder in Form eines Graphen abgebildet werden. Eine gemischte Codierung ist bisher nicht bekannt.

Individuum - Binäre Codierung
Binärcodierung stellt die einfachste Form der Codierung dar. Sie wird beispielsweise in [2] verwendet. Binärcodierung erleichtert die Implementation der weiteren Operatoren. Wenn die Gene eines binär codierten Individuums in ihrer Gesamtheit als eine Binärzahl interpretiert werden, empfiehlt es sich statt Standard-binär Gray-binär zu verwenden, sodass alle Gene gleich gewichtet sind. Somit haben Veränderungen durch Crossover oder Mutation gleichstarke Auswirkungen. Ein binär codiertes Individuum könnte beispielsweise folgendermaßen aussehen:



Individuum - Ganzzahlcodierung
Werden Individuen unter der Verwendung von Ganzzahlen codiert, bietet das die Möglichkeit, mehr Informationen in einem Gen festzuhalten. Gleichzeitig wird das Spektrum möglicher Operatoren erweitert (vergleiche Kapitel „Rekombination“). Ganzzahlcodierung wird beispielsweise häufig bei Reihenfolgenproblemen, wie dem Handlungsreisendenproblem, eingesetzt. Beispiel für ein Ganzzahlig codiertes Individuum:



Individuum - Graphcodierung
Die Form eines Graphen hebt die Codierung auf eine abstraktere Ebene. Sie wird häufig eingesetzt, da sich in Graphen viele Probleme leicht abbilden lassen. Während die Operatoren von Binär- und Ganzzahlcodierungen ähnlich sind, unterscheiden sich die Operatoren für als Graphen codierte Individuen grundsätzlich. Beispiel eines Individuums in Graphcodierung:



Die von uns gewählte Codierung
In unserer Implementierung beschreibt ein Individuum eine Route durch alle Städte. Eine Stadt wird hierbei eindeutig durch eine ID in Form einer Ganzzahl individualisiert. Somit haben wir in unserer Implementierung eine Ganzzahlcodierung gewählt, wobei in den Operatoren zu berücksichtigen ist, dass die Reihenfolge der Gene respektiert werden muss. Dies schließt die üblichen Operatoren für Ganzzahlcodierung aus. Für die Individuen wurde eine Klasse „Route“ angelegt. Die Route ist eine Liste, in der jedes Element die ID einer Stadt enthält.


Zusätzlich wird in jedem Individuum die individuelle Fitness festgehalten. Für die Städte wurde eine Klasse „City“ angelegt. Jede Stadt wird definiert durch eine eindeutige ID und Koordinaten. Dadurch lässt sich jede Stadt eindeutig definieren und die Distanzen zu anderen Städten berechnen.


In der Programmoberfläche kann zufällig eine gewünschte Menge von Städten generiert werden. Die Klasse „PredefinedCities“ stellt zudem vordefinierte Stadtkonstellationen zur Verfügung, um unterschiedliche Programmeinstellungen auf gleiche Umgebungen ausführen zu können.

Population
Eine Population stellt die gesamt Menge aller potentiellen Lösungskandidaten für ein Problem dar.
Die Population ist im Grunde genommen eine Liste von Individuen. Außer den Individuen muss keine weitere Information in der Population festgehalten werden. Deshalb reicht zur Implementierung der Population ein einfaches Array.

Gen
Wie in der Biologie bilden die Gene beim genetischen Algorithmus die einzelnen Bestandteile der Codierung eines Individuums. Die Beschaffenheit der Gene sind kann binär sein, wobei ein einzelnes Gen dann 0 oder 1 ist. Binäre Codierung hat den Vorteil, dass Prozesse wie Crossover und Mutation nicht aufwändig angepasst werden müssen. Weitere übliche Codierungsformen sind Ganzzahlen, Realzahlen oder Knoten eines Graphen.
In unserer Implementierung beschreibt die Reihenfolge der Gene einen Lösungsweg, also einen Pfad des Handlungsreisenden. Da der Handlungsreisende jede Stadt auf jeder Route genau einmal besucht, hat ein Individuum ebenso viele Gene wie es Städte gibt.

Generation
Eine Generation ist eine Population zu einem Zeitpunkt n. Im Kreislauf eines genetischen Algorithmus (vergleiche Abbildung 1) entsteht immer nach der Rekombination eine neue Generation von Individuen.

Allel
Als Allele werden die Elemente der Menge des Alphabets bezeichnet, aus denen die Gene gewählt werden. Ist ein Individuum binär codiert, d.h. ein Gen ist entweder 0 oder 1, dann bilden 0 und 1 die möglichen Allele.
In unserer Implementierung entspricht die Menge der Allele, also Ausprägungen eines Gens, der Menge der vorhandenen Stadt-ID’s.

Fitness
Jedes Individuum hat zu jedem Zeitpunkt eine bestimmte Fitness. Diese beschreibt die Tauglichkeit eines Individuums. In jedem Individuum ist eine mögliche Problemlösung codiert. Die Fitness eines jeden Individuums beschreibt, meist in einer Realzahl, die Qualität dieser Lösung bezogen auf das gestellte Problem.

Zu Beginn des Algorithmus wird eine Population mit Individuen erzeugt. Die Gene der Individuen werden zufällig aus der Menge der verfügbaren Allele gewählt. Soll der Algorithmus ein Reihenfolgeproblem lösen, gilt es hierbei natürlich zu beachten, dass jedes Individuum keine doppelten Gene enthält. Die Größe der Startpopulation wird nicht vorgeschrieben. In [2] wurde diese Frage nach einer geeigneten Populationsgröße mit der Anzahl der Gene eines Individuums beantwortet. Ob diese Methode Beständigkeit hat ist unklar.

In unserer Implementierung wird die Startpopulation aus zufällig erzeugten Individuen erzeugt. Ihre Größe kann in der Programmoberfläche eingestellt werden. Hierbei wird für jedes Individuum die Menge der verfügbaren Allele (Also Stadt-ID’s) in zufälliger Reihenfolge angeordnet. Jede Stadt-ID kommt somit genau einmal als Gen in jedem Individuum vor.

Die Fitnessfunktion bewertet die Güte eines Individuums, um diese vergleichen zu können und eventuell auf ein erfülltes Abbruchkriterium zu prüfen. Außerdem wird die Fitness häufig genutzt um die Fortpflanzungswahrscheinlichkeit eines Individuums zu bestimmen. Sie trägt eine sehr wichtige Rolle und beeinflusst die Konvergenz des genetischen Algorithmus massiv.

Definition der Fitnessfunktion
Ihre Definition stellt einen sehr wichtigen Prozess im genetischen Algorithmus dar. Die Findung einer geeigneten Fitnessfunktion ist problemspezifisch, es gibt hierfür kein klar definiertes Konzept. Daher stellt ihre Definition die wohl größte Schwierigkeit bei der Anwendung eines genetischen Algorithmus dar. Idealerweise berechnet die Fitnessfunktion einen numerischen Wert. Bemerkung: Erstaunlicherweise wird in einigen Papern trotz der hohen Bedeutung die Fitnessfunktion, ihre Herleitung und ihre Definition nicht dargestellt oder nur grob beschrieben. (vergleiche [2])

Nicht-normierte Fitness
Die Untersuchung verschiedener Paper über implementierte genetische Algorithmen auf ihre Fitnessfunktion hin hat gezeigt, dass es sowohl Fitnessfunktionen gibt, bei denen das Verhältnis zwischen Rückgabewert der Fitnessfunktion und daraus folgender Fitness proportional verläuft, als auch solche, bei denen dieses Verhältnis antiproportional ist. Bei manchen Implementationen bedeutet ein höherer Rückgabewert der Fitnessfunktion bessere, bei manchen schlechtere Fitness. Darüber hinaus ist der Wertebereich mancher Fitnessfunktionen negativ, bei manchen Fitnessfunktionen kann man auch einen Wertebereich betrachten, der weit in den positiven Bereich ragt. In diesen Fällen handelt es sich um nicht-normierte Fitness. Das hat den großen Nachteil, dass der Fitnesswert im weiteren Verlauf der Implementation individuell behandelt werden muss. Dabei ist es sehr einfach, die Fitness zu normieren. Dies muss nicht einmal in der Fitnessfunktion geschehen. Es lässt sich eine allgemeingültige Funktion definieren, die diese Aufgabe übernimmt (siehe Abbildung 10)

Normierte Fitness
Gibt die Fitnessfunktion keinen absoluten Fitnesswert zurück, sondern das Verhältnis der einzelnen Fitness zur Gesamtfitness der Population, spricht man von normierter Fitness. Der Rückgabewert der Fitnessfunktion verläuft hierbei proportional zur Fitness, der Wertebereich ist {x|0<x<1}. Die Fitness zu normieren hat den großen Vorteil, dass die Schnittstelle zu den weiteren Operatoren der Implementierung klar definiert ist. Die Fitness muss im weiteren Verlauf nicht problemspezifisch interpretiert werden. Mit folgender Formel lässt sich die normierte Fitness für ein Individuum berechnen:



Implementierte Fitnessfunktionen
Im Folgenden werden exemplarisch Fitnessfunktionen implementierter genetischer Algorithmen dargestellt und kurz erläutert.

Fitnessfunktion des Handlungsreisenden
Die Lösung beim Problem des Handlungsreisenden besteht darin, einen möglichst kurzen Weg zwischen mehreren Städten zu finden. Im Hinblick auf die Fitnessfunktion gibt es hierzu unterschiedliche Konzepte: In [2] wird zunächst die Länge der zurückgelegten Strecke berechnet, wie sie im Individuum codiert ist:


Eine bessere Lösung, also ein kürzerer Weg, ergibt bei dieser Rechnung zunächst einen niedrigen Wert. Anschließend wird 1 und das Ergebnis geteilt und bewirkt zum Einen, dass eine höhere Fitness nun einen höheren Wert erzeugt, zum Anderen wird sichergestellt, dass der Fitnesswert immer zwischen 0 und 1 liegt, was die weiteren Schritte und Rechnungen vereinfacht. Jedoch wird die Fitness hier nicht normiert.

Fitnessfunktion des genetischen Algorithmus von Prof. Dr. Döben-Henisch
Prof. Dr. Döben-Henisch hat in einer allgemeinen Implementation des genetischen Algorithmus [9] exemplarisch eine Fitnessfunktion implementiert:


Die berechnete Fitness ist proportional zum berechneten Wert: Hoher Wert – hohe Fitness. Die Fitness wird nicht innerhalb der Fitnessfunktion, sondern anschließend in einer separaten Funktion normiert:

Dies räumt dem Entwickler, der dieses Programm als Basis für eigene Entwicklungen nutzen möchte einen größeren Freiraum ein. Er muss sich nicht um die Normierung kümmern, es reicht darauf zu achten, dass sich Fitness und berechneter Wert der Fitnessfunktion proportional zueinander verhalten.

Die Fitnessfunktion unserer Implementierung
Die Fitnessfunktion bewertet bekanntermaßen die Qualität eines Individuums. In unseren Individuen sind die Pfade des Handlungsreisenden codiert. Das primäre Qualitätsmaß ist die Länge der Gesamtstrecke: Je kürzer ein Pfad, desto höher die Fitness. Mit dieser Bedingung als einzigem Kriterium könnte man die Fitness eines Individuums berechnen als Summe der Distanzen der aufeinanderfolgenden Städte plus die Distanz der letzten Stadt zur ersten Stadt (da der Handlungsreisende zum Ausgangsort zurückkehrt), also als Gesamtstrecke der Route:


F = Fitness
D (a;b) = Distanz zwischen Gen/Stadt a und Gen/Stadt b
G = Gen/Stadt im Individuum
Durch den Ausdruck (k mod n) + 1 erhält man für jede Stadt k die nachfolgende Stadt k+1, mit Ausnahme der letzten Stadt der Route, für diese gibt der mathematische Ausdruck den Index der ersten Stadt zurück, sodass die Route geschlossen wird.
In anderen Implementationen wird die Distanz D bei der Berechnung quadriert. Dies bewertet eine größere Distanz strenger mit einer schlechteren Fitness, da das Verhältnis zwischen Streckenlänge und Fitness so nicht linear, sondern quadratisch verläuft:


Diese Inspiration haben wir in die Implementierung unserer Fitnessfunktion einfließen lassen. Die Quadrierung der Städtedistanzen lässt sich über einen Funktionsparameter steuern. Dieser Flag lässt sich über die Programmoberfläche einstellen:


Ein weiteres Qualitätsmerkmal stellen Überschneidungen dar: Kreuzt sich eine Route selbst, ist dies immer schlecht und ein klarer Hinweis dafür, dass diese Route nicht optimal ist. Auch dieses Kriterium haben wir anfangs in die Fitnessfunktion einfließen lassen. Dies brachte keinen sichtbaren Erfolg. Die definierte Fitnessfunktion berechnet nicht normierte Fitnesswerte. Der Rückgabewert ist antiproportional der Fitness: Niedriger Rückgabewert der Funktion → Hohe Fitness. Die Fitness ließe sich mit einer einfachen Rechnung normalisieren:


Die Fitness wird absichtlich nicht normalisiert, da für spätere Analysen und Vergleiche die absoluten Werte der Routenlängen von Bedeutung sind. Die Normierung ist eine nicht umkehrbare Funktion. Da bei bestimmten später eingesetzten Operatoren, wie zum Beispiel dem roulette-wheel-selection-Verfahren eine normierte Fitness sehr nützlich ist, wird diese Funktion zur Normierung erst dort angewandt.

Die Selektion entscheidet, welche Individuen der aktuellen Population gepaart werden, um die Nachkommen zu erzeugen. Das Selektionsverfahren beeinflusst die Konvergenzgeschwindigkeit der genetischen Algorithmen. Es gilt hier einen Kompromiss zu finden: Einerseits empfiehlt es sich natürlich, die Menge der zu paarenden Individuen aus solchen mit möglichst hoher Fitness zusammenzustellen. Gleichzeitig ist es Ziel, ein breites Spektrum an unterschiedlichen Individuen zu erstellen, um zu verhindern, dass sich der genetische Algorithmus zu früh in einem lokalen Maximum „festsetzt“. Diese Grenze gilt es geeignet zu bestimmen.

Der Schritt „Selektion“ unterteilt sich in zwei Prozesse

• Selektionsverfahren
• Heiratsverfahren

Im Selektionsverfahren wird bestimmt, welche Individuen der Population überhaupt zur Paarung zugelassen werden. Im Heiratsverfahren werden dann nach einem Heiratsschema die Paare gebildet.

Selektionsverfahren – fitnessproportionale Selektion
Im Selektionsverfahren wird festgelegt, mit welcher Wahrscheinlichkeit die einzelnen Individuen zur Paarung ausgewählt werden. In genetischen Algorithmen findet die fitnessproportionale Selektion häufig Verwendung. Je fitter ein Individuum ist, desto höher ist die Wahrscheinlichkeit, dass es im Heiratsverfahren gezogen wird. Dieses Verhältnis wird in [6] folgendermaßen formuliert:


Wobei F die Fitnessfunktion und I das Individuum ist, für den die Selektionswahrscheinlichkeit bestimmt wird. Dieses Verfahren wird beispielsweise in [9].

Selektionsverfahren – rangbasierte Selektion
Die Rangbasierte Selektion kann in diesem Fall als alternativ Verfahren eingesetzt werden. Bei diesem Verfahren ist die Selektionswahrscheinlichkeit nicht mehr im direkten Verhältnis zur Fitness gesetzt. Stattdessen werden die Individuen nach absteigendem Fitnesswert sortiert und durchnummeriert. Dann wird die Rangzahl der Individuen im direkten Verhältnis zur Selektionswahrscheinlichkeit gesetzt. [6]
Wir haben diesen Operator folgendermaßen implementiert:



Selektionsverfahren – Turnier Selektion
Ein weiteres Verfahren ist die Turnier Selektion. Hierbei spielt die absolute Fitness eines Individuums keine Rolle. Daher ist die Turnier Selektion keine fitnessproportionale Selektion. Zwischen mehreren Individuen werden Turniere ausgeführt. Sieger eines Turniers ist das Individuum mit der höchsten Fitness. Die Auswahl der Individuen, die an einem Turnier teilnehmen erfolgt durch zufällige, gleichwahrscheinliche Wahl von Individuen aus der Elternpopulation.

Selektionsverfahren – Truncation Selektion
In diesem Verfahren hängt die Auswahl der Individuen von ihrer Fitness ab. Die Individuen werden zunächst entsprechend ihrer Fitness sortiert. Alle Individuen, deren Fitness über einem Schwellenwert (Truncation-Schwelle) liegen, werden ausgewählt. Die restlichen Individuen werden verworfen. Demnach erhält ein Individuum im Selektions-pool entweder die
Selektionswahrscheinlichkeit 1 oder 0. Ähnlich wie bei der Turnier Selektion wird bei der Truncation Selektion nur die Rangfolge der Fitnesswerte der Individuen verwendet, der absolute Wert spielt wird nicht berücksichtigt.

Heiratsverfahren
Einer der gängigsten Heiratsverfahren ist das so genannte roulette-wheel-selection. Das Prinzip dieses Verfahren entspricht dabei einem Glückrad, das in n Abschnitte unterteilt ist, wobei n der Populationsgröße entspricht. Die Breite der Abschnitte ist von der Selektionswahrscheinlichkeit der einzelnen Individuen abhängig und bestimmt die Auswahlmöglichkeit der Individuen. Um die neue Elterngeneration zu erhalten wird nun n-mal am Rad gedreht. Die Wahrscheinlichkeit, das n identische Individuen gezogen werden ist sehr groß. Nichtsdestotrotz wird es in vielen Genetischen Algorithmen eingesetzt.

Wir haben das roulette-wheel-selection-Verfahren folgenermaßen implementiert:

Rekombination (bzw. Crossover) bezeichnet den Vorgang, in dem aus den Elternpaaren neue Individuen erzeugt werden. Meist werden zwei Elternpaare gewählt. Aus diesen werden ein (vergleiche [8]) oder mehrere Nachkommen erzeugt. Ziel ist es, durch Kombination der Eltern-Gene neue Individuen zu erzeugen, die eine höhere Fitness erreichen. Es gibt unterschiedliche Rekombinationsverfahren, die bestimmen, wie und aus welchen Informationen der Eltern sich die erzeugten Nachkommen zusammensetzen. Ob überhaupt eine Kreuzung stattfindet oder nicht, kann über eine Kreuzungswahrscheinlichkeit bestimmt werden. Meist wird eine Wahrscheinlichkeit gewählt, bei der eine Kreuzung wahrscheinlicher ist als keine (vergleiche [6]).
Je nach Anwendungsfall können die Individuen allgemein binärcodiert sein (Die einzelnen Gene bestehen aus 0 oder 1), oder eine spezielle, abstraktere Codierung aufweisen. Wann immer es möglich ist, empfiehlt es sich, die Gene eines Individuums binär zu codieren (vergleiche [9]), da die Codierung die Schnittstelle zu den weiteren Verfahren ist. Binäre Codierung ermöglicht, allgemeine Rekombinations- und Mutationsverfahren anzuwenden. Nicht jede Lösung lässt sich jedoch binär codieren, sodass die Gene auch aus Ganz- oder Realzahlen bestehen, oder die Knoten eines Graphen repräsentieren. Dies lässt einen allgemeinen Umgang mit den Individuen nur noch beschränkt zu. Für die jeweiligen Repräsentationen gibt es unterschiedliche Rekombinationsverfahren, von denen im Folgenden eine Auswahl vorgestellt wird.

Crossoveroperatoren für Binär- und Ganzzahlcodierte Individuen
Bei Binär- und Ganzzahloperatoren arbeiten nach den gleichen Prinzipien, daher werden sie hier nicht explizit unterschieden, sondern gemeinsam dargestellt. Die Beispiele zeigen stets binär codierte Eltern dar.

Crossoveroperatoren Binär- und Ganzzahlen – 1-Punkt-Crossover
Dieser Operator wählt am Anfang eine zufällige Kreuzungsstelle im Individuum. An diesem Kreuzungspunkt werden die beiden Elternpaare aufgeteilt und vererben wechselweise ihre Informationen an die beiden Nachkommen. Dies wird in folgender Abbildung an einem Beispiel graphisch demonstriert:



Crossoveroperatoren Binär- und Ganzzahlen – n-Punkt-Crossover
Dieser Crossoveroperator unterscheidet sich vom 1-Punkt-Crossover durch die Tatsache, dass hier nicht ein einzelner, sondern n Kreuzungspunkte gewählt werden. Folgende Abbildung stellt dies exemplarisch dar:



Crossoveroperatoren Binär- und Ganzzahlen – Uniform Crossover
Bei diesem Operator werden keine Gen-Sequenzen gebildet. Stattdessen wird für jedes einzelne Gen der Eltern überprüft, ob diese getauscht werden sollen. Dies geschieht, indem für jedes Gen der Eltern ein Zufallswert zwischen 0 und 1 bestimmt wird. Ist dieser Wert >= 0,5, dann findet an dieser Stelle ein Austausch der Gene statt.



Crossoveroperatoren Permutationen
Crossoveroperatoren, die auf Individuen angewand werden, bei denen die Information in der Reihenfolge der Gene liegt, sind in der Regel deutlich aufwändiger als die bisher beschriebenen Operatoren. Sie werden daher Schrittweise anhand eines Beispiels erklärt.

Crossoveroperatoren Permutationen – partially mapped crossover (PMX)
Der partially mapped Crossover Operator tauscht eine Sequenz von Genen direkt aus und passt anschließende die restlichen Gene der Individuen an. Um redundante Gene zu vermeiden wird mit einer mapped table gearbeitet. Dies wird im Folgenden anhand eines Beispiels demonstriert:

Wir gehen von folgenden Eltern-Individuen aus:


Die Gene dieser beiden Individuen werden nun nach PMX rekombiniert. Dazu wird zunächst zufällig eine Gen-Sequenz ausgewählt, beispielsweise von Gen 4 bis Gen 6.


Die Sequenzen werden in die Nachkommen übernommen: A‘ bekommt die Sequenz von B, B‘ die von A. Die restlichen Gene bleiben bis hierhin noch unbestimmt.


Die Gen-Sequenzen werden in eine „mapping table“ übernommen.

Nun werden die fehlenden Gene der Nachkommen aufgebaut. Die fehlenden Gene von Nachkomme A‘ werden aus dem Elternteil A aufgebaut. Da die Individuen B und B‘ für diesen Vorgang nicht von Belangen sind, werden sie zur Verbesserung der Übersicht vorübergehens ausgeblendet. Für den Aufbau der Gene von A‘ werden nur Elternteil A und die mapping Table benötigt. Für das erste Gen von A‘ wird das erste Gen von A betrachtet.


Das erste Gen von A soll nach Möglichkeit nach A‘ übernommen werden. Es muss jedoch sichergestellt werden, dass dieses Gen nicht doppelt in A‘ vorkommt. Das geschieht über die mapping table. Hier kann leich festgestellt werden, ob das Gen so wie es ist übernommen werden kann, und falls nicht, welcher Wert stattdessen in A‘ geschrieben wird. Dazu wird der Wert des Gens, nämlich 1, in der ersten Zeile der mapping table gesucht. Ist dort eine 1 vorhanden, bedeutet das, dass der Wert nicht direkt in A‘ übernommen werden kann, weil er dort bereits existiert. In unserem Beispiel ist das der Fall:


Stattdessen wird der „gemappte“ Wert darunter genommen. Damit nicht am Ende die 4 doppelt vorkommt, muss sie natürlich ebenfalls in der mapping table gesucht werden und eventuell das darunterstehende Gegenstück gewählt werden. Solange bis der Wert nicht mehr in der ersten Zeile der mapping table vorkommt. Da sie in der oberen Zeile nicht vorkommt, kann sie bedenkenlos übernommen werden:


Damit ist das erste Gen von A‘ bestimmt. Das zweite Gen von A hat den Wert 2. Dieser Kommt nicht in der mapping Table vor, daher kann er direkt übernommen werden:


Für die restlichen Gene wird gleichermaßen verfahren. Ebenso für Nachkommen B‘. Das Ergebnis sieht folgendermaßen aus:



Crossoveroperatoren Permutationen – partially mapped crossover (PMX) – Implementation
Wir haben den PMX-Operator folgendermaßen implementiert:





Crossoveroperatoren Permutationen – Greedy Sub Tour Crossover
Bei diesem Crossoveroperator ist zu beachten, dass aus zwei Eltern nur ein Nachkomme erzeugt wird. Das Konzept dieses Crossovers und der Ablauf lassen sich am leichtesten wieder an einem Beispiel nachvollziehen.

Wir gehen von folgenden Eltern-Individuen aus:


Zuerst wird zufällig ein Allel ausgewählt und das entsprechende Gen beider Eltern markiert. Dies könnte beispielsweise das Allel „3“ sein:



Der Nachkomme, der nun aufgebaut wird, besteht zunächst nur aus diesem markierten Gen:


Nun wird der Nachkomme um weitere Gene ergänzt. Dazu werden die Gene der Eltern, ausgehend von dem markierten Gen, abwechselnd angefügt. Bei dem Elternteil A wird vom markierten Gen mit dem Wert „3“ nach links gelesen, vom Elternteil B nach rechts:


Mit Elternteil A wird gestartet, im ersten Gen, welches ausgelesen wird, steht der Wert „1“. Dieser Wert kommt im Individuum noch nicht vor, also wird er links angefügt:


Nun ist Elternteil B an der Reihe. Sein erstes Gen nach der markierten „3“ ist „4“. Da auch dieses Gen noch nicht im Nachkomme vorkommt, kann es direkt übernommen werden. Es wird rechts angefügt:


Nun folgt Elternteil A mit dem nächsten Gen „2“, Elternteil B mit Gen „7“ und im zuge der Abwechslung wieder Elternteil A mit „8“. Diese Gene können problemlos angefügt werden, da sie ebenfalls noch nicht im Nachkomme enthalten sind:


Nun ist Elternteil B an der Reihe mit Gen „8“. Da bereits ein Gen mit diesem Wert im Individuum vorhanden ist, kann dieses nicht übernommen und rechts angefügt werden. Nun stoppt die Auslese von Genen von Elternteil B.


Wir haben von Elternteil also von dem zuerst ausgewählten Gen mit dem Wert „3“ nach rechts so lange Gene ausgewählt und auf den Nachkomme übertragen, bis wir auf ein Gen gestoßen sind, dessen Wert im nachkomme bereits vorhanden ist. Nun werden nur noch Gene des anderen Elternteils A angefügt, bis wir auch hier auf ein Gen stoßen, das bereits vorhanden ist. Zufällig ist das bereits bei dem nächsten Gen der Fall:


Sobald beide Eltern soweit ausgelesen wurden, bis sie auf bereits vorhandene Gene im Nachkomme stoßen, wie es nun der Fall ist, wird ermittelt, welche Allele noch nicht im Nachkomme vorhanden sind. Dies sind „5“ und „6“. Diese werden anschließend in zufälliger Reihenfolge ans (rechte) Ende des Individuums angefügt. Das Crossover ist vollendet:



Crossoveroperatoren Permutationen – Greedy Sub Tour Crossover – Implementation
Den Greedy Sub Tour Crossover haben wir folgendermaßen implementiert:





Crossoveroperatoren Permutationen – Greedy Crossover
Wie beim Greedy Sub Tour Crossover wird auch bei diesem Operator aus zwei Eltern nur ein Nachkomme erzeugt. Der Greedy Crossover Operator hat ein eigenes Konzept, welches, trotz des ähnlichen Namens, keine weitere Gemeinsamkeit mit dem Greedy Sub Tour Crossover Operator teilt. Der Ablauf lässt sich am leichtesten wieder an einem Beispiel nachvollziehen.

Wir gehen von folgenden Eltern-Individuen aus:


Zuerst wird das erste Allel des Elternteils A ausgewählt und direkt an erste Stelle in das entstehende Kind übernommen:


Die Gene des Nachkommen werden nach rechts orientiert aufgebaut. Nun wird im Elternteil B das Gen mit dem Wert 4 gesucht:


Von beiden Eltern wird nun die Distanz des markierten Gens zum direkten rechten Nachbarn ermittelt. Im Beispiel des Hanglungsreisenden wäre das also Im Elternteil A die Distanz von Stadt 4 zu Stadt 8 und im Elternteil B die Distanz von Stadt 4 zu Stadt 7. Hierfür benötigt man Informationen zu den Bedeutungen der Gene, zum Beispiel die Koordinaten der Städte. Wir gehen an dieser Stelle davon aus, dass die Distanz von Stadt 4 zu Stadt 7 geringer ist, als von Stadt 4 zu Stadt 8. In diesem Fall wird dem Nachkommen ein weiteres gen mit dem Allel 7 angehängt:


Wie zu Beginn wird erneut das zuletzt übernommene Gen in beiden Elternteilen markiert:


Es wird erneut berechnet, welche Distanz der rechts folgenden Gene der beiden Elternteile zum markierten Gen mit dem Allel 7 die geringste Distanz aufweist. Dieses wird wieder in den Nachkommen übernommen. Dieser Schritt wird wiederholt bis der Nachkomme vollständig ist, oder man auf ein Gen stößt, welches bereits im Nachkommen vorhanden ist. Im letzen Fall wird aus der Menge der noch nicht im Nachkommen enthaltenen Allel zufällig eines ausgewählt, in den Nachkommen übernommen und in beiden Elternteilen markiert, um wie gewohnt fortfahren zu können.

Crossoveroperatoren Permutationen – Greedy Crossover – Implementation
Wir haben diesen Operator wie folgt implementiert:





Crossoveroperatoren Graphen
Individuen können in Form von Graphen codiert sein. Graphcodierung bietet eine Reihe von Vorteilen und wird daher vermehrt eingesetzt. Diese Form der Codierung erfordert angepasste Crossover. Da dieses Thema sehr speziell und komplex ist, soll an dieser Stelle auf eine ausführliche Erklärung verzichtet werden. Wir verweisen auf [17] und [18], zwei sehr interessante Artikel, die sich mit Graphcrossover beschäftigen.

Mutation bedeutet im Rahmen der genetischen Algorithmen, ein Individuum zufällig zu ändern. Dies wird über die Mutationswahrscheinlichkeit bestimmt, die fest vorgegeben wird. Mutation ermöglicht es, potentielle Lösungen zu finden, die nur durch Rekombination alleine nicht erzeugt werden können. Außerdem ist Mutation ein nützliches Konzept, um eine Population, die sich nur durch Anwendung von Rekombination in einem lokalen Fitness-Maximum „festgesetzt“ hat, hieraus zu lösen. „Mutation ist der primäre Antrieb bei der Erkundung neuer Gebiete im Parameterraum“ [10]. In vielen Darstellungen des genetischen Algorithmus wird sich bei der Beschreibung der Mutation und möglicher Verfahren auf das bit-flipping beschränkt. Nur in wenigen Papern findet man Mutationsoperatoren für Permutationsprobleme und meist sind diese nicht ausreichend klar beschrieben. Das motivierte uns, hier vor allem Mutationsverfahren vorzustellen, die auf nicht binär codierte Individuen und Individuen, die eine Reihenfolge codieren anwendbar sind.

Verschiedene Konzepte
In den meisten Implementierungen wird Mutation von Beginn an eingesetzt. Prof. Dr. Döben-Henisch hat in seinem Programm (vergleiche [9]) ein anderes Konzept verfolgt: Zunächst wird die Mutationswahrscheinlichkeit auf 0 gesetzt. Es findet keine Mutation der Individuen statt. Neue Individuen entstehen nur durch Rekombination. Sobald sich die Fitness gar nicht mehr oder nur noch gering ändert, wird die Mutationswahrscheinlichkeit dann erhöht. Dieses Verfahren hat gezeigt, dass der Algorithmus schneller konvergiert und trotzdem im Stande ist, ein „festgesetzten“ Verlauf zu stören um neue Individuen mit eventuell höherer Fitness zu finden.

Mutationsformen
Das Konzept der Mutation ist für alle Codierungsformen gleich, die konkrete Ausprägung hängt jedoch von der gewählten Codierungsform der Individuen ab. Aus diesem Grund werden im Folgenden Mutationsoperatoren für ausgewählte Codierungen vorgestellt.

Anwendung
Der erste Schritt der Anwendung von Mutation ist bei den verschiedenen Mutationsverfahren gleich (Mit Ausnahme von Mutationsverfahren, die bei Reihenfolgenproblem eingesetzt werden). Es wird vorausgesetzt, dass die Mutationswahrscheinlichkeit p festgelegt wurde. Für jedes Individuum werden zunächst die Gene ermittelt, die verändert werden. Hierzu wird für jedes Gen ein Zufallswert zwischen 0 und 1 bestimmt. Liegt dieser Wert unter der Mutationswahrscheinlichkeit, wird dieses Gen „markiert“ und im nächsten Schritt verändert. Liegt keiner der Zufallswerte unter der Mutationswahrscheinlichkeit, bleibt das Individuum unverändert. Folgende Abbildung stellt diesen Vorgang schematisch dar:



Mutationsoperatoren – Binär – bitflipping
Für binär codierte Probleme wird häufig das so genannte bitflipping eingesetzt. Hierbei wird jedes zu mutierende Gen invertiert:



Mutationsoperatoren – Ganzzahlen – Random resetting
Aus Ganzzahlen bestehende Gene können mit dem Random resetting mutiert werden. Hierbei wird jedes zu mutierenden Gen durch einen zufällig aus der Menge der verfügbaren Allele gewählten Wert ersetzt:



Mutationsoperatoren – Ganzzahlen – Creep Mutation
Dieses Mutationsverfahren bewirkt kontrollierte, geringe Änderungen der Gene, da es die zu mutierenden Gene nicht neu ersetzt, sondern nur abändert. Für jedes zu mutierendes Gen wird zunächst zufällig aus einer Menge von Ganzzahlen (gewöhnlich symmetrisch um den Nullpunkt verteilt) einen Wert k ermittelt. Das neue Gen setzt sich aus der Summe des alten Gens und des ermittelten Wertes k zusammen. Ist der Wert des neuen Gens nicht Element der Menge der Verfügbaren Allele, wird der Vorgang wiederholt.



Mutationsoperatoren – Permutationen
Permutations-Operatoren sind spezielle Operatoren. Sie eignen sich für Reihenfolgenprobleme, bei denen die Gene eines Individuums nicht getrennt voneinander betrachtet werden können. Einem Gen darf nicht einfach ein neuer Wert zugewiesen werden, stattdessen müssen die Gene untereinander vertauscht werden, um die Gültigkeit des Individuums zu erhalten. Die Mutationswahrscheinlichkeit wird bei diesen Verfahren nicht auf jedes einzelne Gen angewandt, sondern entscheidet im Vorfeld, ob ein Individuum mutieren soll oder nicht. Im Folgenden werden verschiedene Mutationsoperatoren für Permutationen vorgestellt.

Mutationsoperatoren – Permutationen – Swap Mutation
Bei diesem Verfahren werden zunächst 2 Gene des zu mutierenden Individuums ermittelt. Diese beiden Gene tauschen anschließend ihre Positionen. Folgende Abbildung zeigt dieses Verfahren an einem Beispiel:



Mutationsoperatoren – Permutationen – Swap Mutation – Implementation
Wir haben den Swap Mutation Operator folgendermaßen implementiert:



Mutationsoperatoren – Permutationen – Insert Mutation
Bei Anwendung dieses Mutationsoperators wird ein zufällig bestimmtes Gen aus dem Individuum entfernt und an einer beliebigen Stelle wieder eingefügt. Die Zahlen, die sich zwischen der alten und neuen Position dieses Elements befinden, verschieben sich dabei um eine Stelle nach links bzw. rechts.



Mutationsoperatoren – Permutationen – Insert Mutation – Implementation
Wir haben den Insert Mutation Operator folgendermaßen implementiert:



Mutationsoperatoren – Permutationen – Sequence Scramble Mutation
Bei der Sequence Scramble Mutation wird zunächst zufällig zwei Gene ausgewählt. Diese und alle dazwischenliegenden Genen werden anschließend gemischt, also zufällig in ihrer Reihenfolge getauscht. Dies soll in folgender Abbildung veranschaulicht werden:



Mutationsoperatoren – Permutationen – Sequence Scramble Mutation – Implementation
Wir haben den Sequence Scramble Mutation Operator folgendermaßen implementiert:



Mutationsoperatoren – Permutationen – Scramble Mutation
In [7] wird dieses Konzept in einer modifizierten Weise beschrieben: Hier wird keine Sequenz ausgewählt, sondern eine beliebige Menge von Genen, deren Positionen zufällig vertauscht werden.



Mutationsoperatoren – Permutationen – Reverse Mutation
Wie bei Scramble Mutation wird auch hier zunächst zufällig eine Gen-Sequenz ermittelt. Im Gegensatz zur Scramble Mutation werden die Gene dieser Sequenz jedoch nicht gemischt, sondern ihre Reihenfolge wird invertiert:



Mutationsoperatoren – Permutationen – Reverse Mutation – Implementation
Wir haben den Reverse Mutation Operator folgendermaßen Implementiert:



Mutationsoperatoren – Permutationen – Ring Mutation
Das Prinzip der Ring Mutation lässt sich am einfachsten nachvollziehen, wenn man sich vorstellt, dass man einen Papierstreifen in Händen hält, auf dem die Gene notiert sind. Nun klebt man den Papierstreifen zusammen, sodass sich ein Ring ergibt und schneidet ihn an einer beliebigen Stelle wieder auseinander. Somit wird eine Gen-Sequenz vom Anfang des Individuums entfernt und am Ende angefügt:


Dieses Mutationsverfahren eignet sich nicht für das Reihenfolgenproblem des Handlungsreisenden, da dieser nach Besuch der letzten Stadt zur ersten Stadt zurückkehrt.

Der Schritt der Reproduktion wird in manchen Schriften einfach vernachlässigt (vergleiche [15]), dabei ist er von entscheidender Wichtigkeit. Denn was nützt es, die besten Individuen zu zeugen, wenn man keine gute Strategie hat, um sie in die Population einfließen zu lassen. Neue Individuen werden in der Hoffnung erzeugt, dass sie die gestellte Aufgabe besser lösen als ihre Vorfahren. Es gibt zwei gebräuchliche Konzepte, eine neue Generation aus Eltern und Nachkommen zu erzeugen:

Generational replacement
Hierbei besteht die neue Generation ausschließlich aus neu erzeugten Individuen.

Generational replacement – Implementation
Die Implementation dieses Operators ist denkbar einfach:



Steady-state replacement
Bei dieser Strategie werden nur ein paar ausgewählte Individuen der bestehenden Population durch neu erzeugte Individuen ersetzt. Es gibt mehrere Varianten dieser Strategie. Meist werden die beiden Individuen der bestehenden Population mit der niedrigsten Fitness durch die beiden Nachkommen mit höchster Fitness ersetzt.

Steady-state replacement – Implementation
Wir haben diesen Operator folgendermaßen implementiert:



Simple Reproduction
Dieser Operator läuft folgendermaßen ab: Zunächst werden die Individuen der Elterngeneration und die erzeugten Nachkommen in einer Liste vereint. Die Elemente dieser Liste werden nach ihrer Fitness sortiert. Diese Liste wird zweigeteilt, die Hälfte mit den fitteren Individuen wird als neue Generation übernommen.

Simple Reproduction – Implementation
Wir haben diesen Operator folgendermaßen implementiert:



Mutation – Ein Konzept von Prof. Dr. Döben-Henisch
Verwendet man ausschließlich Selektion, kann der Algorithmus konvergieren. In diesem Fall ist es sehr wahrscheinlich, dass sich der Verlauf jedoch in einem lokalen Minimum festsetzt. Hieraus kann sich ohne den Einsatz von Mutation nicht befreit werden. Herr Prof. Dr. Döben-Henisch, Fachhochschule Frankfurt am Main, hat nun folgendes Konzept entwickelt: Unabhängig vom eingesetzten Mutationsoperator wird die Mutationswahrscheinlichkeit zunächst auf 0% gesetzt. Die Mutationswahrscheinlichkeit wächst erst, sobald sich über ein Fenster von mehreren Generationen die Fitness der Population nicht mehr ändert (vergleiche [9]). Dies lässt vermuten, dass der Algorithmus in einem Maximum liegt. Die dann erhöhte Mutationsrate ermöglicht es, sich hieraus zu lösen. Dies kann einen Erfolg bringen, falls eine bessere Lösung existiert. Wir haben dieses Konzept implementiert und in unsere Auswertung einfließen lassen.

Konvergenz ist der Prozess der Angleichung von Allelen in den Genen der Chromosomen einer Population. Haben z.B. 90% der Population in demselben Gen dasselbe Allel, so ist dieses Gen zu 90% konvergiert. Der Begriff ist auch auf ein komplettes Chromosom übertragbar. Einfache Genetische Algorithmen lassen ihre Populationen relativ schnell zu einer Lösung hinkonvergieren, ganz im Gegensatz zu natürlichen Evolutionsprozessen, welche aufgrund von großen Populationen, räumlicher Trennung und Nischenphänomenen eine Vielzahl an Arten hervorbringen und auch halten können. [16]

Im Folgenden wird die Nutzung unserer Implementation näher beschrieben und ausgesuchte Kombinationen von Einstellungen, wie Populationsgröße und Mutationsrate, und Operatoren hinsichtlich ihres Konvergenzverhaltens und ihrer Qualität untersucht.

Wie bereits erwähnt haben wir den genetischen Algorithmus und eine Auswahl an verschiedenen Operatoren und Fitnessfunktionen implementiert. In dieser Implementation können die Bestandteile des genetischen Algorithmus frei zusammengestellt werden, um ihr Zusammenspiel zu untersuchen und auszuwerten. Das Programm teilt sich in zwei Modi: Zum Einen kann das Programm mit graphischer Benutzeroberfläche gestartet werden. Hier lassen sich Einstelllungen komfortabel tätigen. Die graphischen Ausgaben wie Landkarte (Vergleiche Bereich 1 in Abbildung 64) und Koordinatensystem visualisieren die Zwischen- und Endergebnisse des gestarteten genetischen Algorithmus. Im anderen Modus lässt sich das Programm ohne graphische Oberfläche per Kommandozeile aufrufen. Hier können die gleichen Einstellungen getätigt werden. Sie werden als Parameter übergeben. Die Ausgabe erfolgt in diesem Modus nicht graphisch. Detaillierte Informationen über Generationen werden in eine Datei geschrieben. Dies ermöglicht, beispielsweise in einem Batch-Job, viele Programmdurchführungen zu organisieren. Wir nutzen dieses Feature für unsere Auswertungen. Auf beide Modi wird im Folgenden eingegangen.

Die Programmoberfläche zeigt sich wie folgt:


Zu Veranschaulichung stellt diese Abbildung einen Programmzustand nach einem Durchlauf dar. Die Programmoberfläch lässt sich in 4 Bereiche gliedern:

Das Programm kann ohne graphische Oberfläche über die Kommandozeile aufgerufen werden. Alle Einstellungen können in Form von Parametern getätigt werden. Das Ergebnis wird in eine Datei geschrieben. Hier werden Informationen über die durchschnittliche Fitness der einzelnen Generationen über alle Durchläufe und die zugehörige Standardabweichung dokumentiert. Darüber hinaus wird der Durchschnitt der besten Fitnesswerte über alle Durchläufe protokolliert, und in welcher Generation dieser zum ersten Mal erreicht wurde. Diese Informationen lassen bereits aussagekräftige Analysen und Vergleiche zu. Das Feature des Programmaufrufs per Kommandozeile eröffnet die Möglichkeit, eine große Menge von Programmdurchläufen mit unterschiedlichen Konstellationen von Einstellungen komfortabel durchlaufen zu lassen.
Der Aufruf des Programms über die Kommandozeile erfolgt folgendermaßen:

java -jar Travelling_Salesman.jar [Karte] [Populationsgröße] [Anzahl Generationen] [Fitnessfunktion] [Selektionsverfahren] [Crossoveroperator] [Mutationsoperator] [Mutationsrate] [Konzept Döben-Henisch] [Reproduktionsoperator] [Anzahl der Durchläufe] [Dateiname für Ausgabe]

Ein Kommandozeilenaufruf könnte folgendermaßen aussehen:

java -jar Travelling_Salesman.jar QUAD 32 2000 false Truncation Greedy SequenceScrumble 0.2 simple 100 tsp_result_file

Jeder Programmaufruf per Kommandozeile erzeugt eine Ausgabedatei. Diese enthält komprimierte Informationen über alle Durchläufe (Für solide statistische Aussagen macht es Sinn das Programm mit den gleichen Einstellungen mehrfach durchlaufen zu lassen, siehe Parameter „Anzahl der Durchläufe“). Folgende Informationen werden dabei abgespeichert:

Mittelwert der Fitness besten Individuen aller Durchläufe pro Generation
Für jeden Durchlauf wird der beste Fitnesswert jeder Generation ermittelt. Nach der gewünschten Anzahl von Durchläufen wird dieser dann für jede Generation gemittelt. Dadurch ergibt sich ein Durchschnittlicher Fitnessverlauf über alle Generationen.

Standardabweichung der Fitness besten Individuen aller Durchläufe pro Generation
Jeder Durchlauf erzeugt einen eigenen Fitnessverlauf, wobei nur die beste Fitness protokolliert wird. Am Ende aller Durchläufe wird von allen Verläufen die Standardabweichung für jede einzelne Generation berechnet. Dies gibt Aufschluss darüber, wie weit die einzelnen Verläufe voneinander abweichen.

Durchschnitt der Fitness des besten Individuums aller Durchläufe
In jedem Durchlauf gibt es ein bestes Individuum. Der Durchschnitt von diesen Fitnesswerten wird abgespeichert. Daran lässt sich erkennen, zu welchem besten Ergebnis der Algorithmus durchschnittlich kommt.

Durchschnitt der besten Generation
Es wird berechnet, in welcher Generation durchschnittlich der beste Fitnesswert auftrat. Dies bringt Aufschluss über die Konvergenzgeschwindigkeit des Algorithmus. Außerdem ist dies ein wichtiger Wert um später mit dem Zufall vergleichen zu können.

Absolut beste Fitness aller Generationen und aller Durchläufe
Von allen Durchläufen und allen Generationen wird der absolut beste Fitnesswert gespeichert.

Nun ist es interessant, wie sich unterschiedliche Kombinationen von Operatoren auf den Erfolg des genetischen Algorithmus auswirken. Um einen Vergleich von Konstellationen aufzustellen und um diejenige Konstellation zu finden, die das Problem des Handlungsreisenden am effizientesten Löst, haben wir einen Vergleich gestartet. Wir haben ein Versuchsaufbau erstellt, der es uns ermöglicht, die Operatoren untereinander, und anschließend gegenüber dem Zufall zu bewerten.

Zur Vorbereitung haben wir eine Auswahl von insgesamt 27 unterschiedlichen Kombinationen von Operatoren aufgestellt. Um einen aussagekräftigen Vergleich anstellen zu können, müssen die Randbedingungen für alle Konkurrenten gleich sein. Um den Versuch in einem zeitlich vertretbaren Rahmen ausführen zu können, haben wir folgende Operatoren ausgesucht, von denen jeder mit jedem kombiniert wurde:

Für die übrigen Parameter wurden folgende Werte gewählt:

Die 27 Operatorkombinationen werden mit diesen Einstellungen auf der Karte „QUAD“ und „RANDOMLY_ORDERED“ ausgeführt. Diese werden im Folgenden gezeigt.

Karte „QUAD“
Diese Karte wurde manuell erstellt, der optimale Weg ist für den Menschen offensichtlich. Diese Karte eignet sich beispielsweise, um eine einzelne Konstellation von Operatoren und Einstellungen bewerten zu können, da die Qualität des Ergebnisses direkt sichtbar ist. Die folgenden Grafiken zeigen die Karte im Ausgangszustand und mit optimaler Lösung:





Karte „RANDOMLY_ORDERED“
Die Städte dieser Karte wurden zufällig positioniert, der optimale Weg ist für den Menschen nicht offensichtlich. Im Gegensatz zur Karte „QUAD“ eignet sich diese Karte nicht, um eine einzelne Konstellation von Operatoren und Einstellungen zu bewerten, da die Qualität des Ergebnisses nicht direkt sichtbar ist. Es ist spannend, verwendet man diese Karte in der Programmoberfläche, glaubt man öfters, der gestartete Algorithmus hat den optimalen Weg gefunden. Dieser Glaube hält auch noch an, wenn der Algorithmus ein völlig neuen Weg ermittelt. So einfach lässt sich das menschliche Auge täuschen. Die folgenden Grafiken zeigen die Karte im Ausgangszustand und mit optimaler Lösung:





Vergleich mit dem Zufall
Um die gleichen Auswertungen wie für die Operatoren auch für den absoluten Zufall treffen zu können, haben wir im Programm den Crossover- und Mutationsoperator deaktiviert und bei der Reproduktion unseren Zufallsgenerator benutzt, den wir auch zur Generierung der Startpopulation verwenden. Die restlichen Einstellungen gleichen natürlich jenen anderen Versuche und entsprechen der obenstehenden Tabelle.

Bemerkung
Damit entstehen 56 Programmausführungen â 100 Durchläufen â 2000 Generationen. Der Rechenaufwand betrug ca. 20 Stunden. Es wäre noch interessant, unterschiedliche Werte in den Einstellungen zu testen, jedoch entwickelt sich der Aufwand exponentiell und sprengt den Rahmen dieser Ausarbeitung.

Das Ergebnis wurde Tabellarisch zusammengefasst. Da der Fitnesswert nicht normalisiert ist, lassen sich die Ergebnisse der eingesetzten Karten untereinander nicht vergleichen. Aus diesem Grund wird das Ergebnis in zwei Tabellen dargestellt: Die erste Tabelle zeigt die Werte der versuche mit Karte „QUAD“, die zweite die mit Karte „RANDOMLY_ORDERED“.

Aufbau der Ergebnisübersicht
Aufgrund der voluminösen Ergebnisdaten erfolgt zunächst eine Übersicht in Tabellenform. In den ersten Spalten werden die verwendete Karte und die Operatoren beschrieben. Jede Konstellation wurde 100 Mal ausgeführt. In den Spalten „Durchschnittliche Fitness“ und „Durchschnitt beste Generation“ stehen die mittleren Werte dieser 100 Durchläufe. Die Spalte „Absolut beste Fitness“ steht der Fitnesswert der besten Generation von allen Durchläufen. Dies zeigt die Erfolgsspitze dieser Konstellation. Hieran lässt sich erkennen, welcher allerbester Wert irgendwann einmal erreicht wurde. Nochmal zur Erinnerung: Der Fitnesswert entspricht der Wegstrecke, das bedeutet, kleiner Wert = kurze Strecke = hohe Fitness.

In der letzten Spalte steht ein berechneter Wert. Dieser Wert ist das Produkt aus durchschnittlich bester Fitness und durchschnittlich bester Generation. Zur Erhöhung der Übersichtlichkeit wurde dieser Wert durch 1000 geteilt. Je besser die durchschnittliche Fitness und je früher das Auftreten im Verlauf des gestarteten Algorithmus, desto effizienter arbeitet der Algorithmus. Je kleiner dieser Wert, desto besser der Algorithmus. Dieser Wert bestimmt die Rangfolge. Die folgenden Tabellen mit den Ergebnissen sind aufsteigend nach diesem Wert sortiert, sodass die beste Zeile oben steht.

Zufall
Um hervorzuheben, in welchem Rang sich der Zufall eingliedert, wurde dieser extra markiert.

Ergebnisübersicht





Ergebnisse im Detail - Aufbau
Um die einzelnen Konstellationen der Operatoren genauer untersuchen zu können, folgt eine detailliertere Ergebnisdarstellung. Hierbei wurden für jede Zeile der Tabellen (siehe Abbildung 69, 70) jeweils zwei Graphen erstellt. Die zu Grunde liegenden Daten hierfür entstammen der Ausgabe, die das Programm bei Aufruf über die Kommandozeile erzeugt.
Der erste Graph stellt den Verlauf der Wegstrecken /Fitnesswerte über die Generationen dar. Die Werte zeigen das Mittelmaß aller 100 Durchläufe. Hieran lässt sich das durchschnittliche Konvergenzverhalten optisch erkennen. Je tiefer der Graph im Verlauf der X-Achse sinkt, desto effektiver, je schneller er sinkt, desto effizienter der Algorithmus.
Der zweite Graph zeigt den Verlauf der absoluten Standardabweichung der Wegstrecken /Fitnesswerte der Generationen. Da der erste Graph Durchschnittswerte darstellt, bleibt die Frage, wie weit die Ergebnisse der einzelnen Durchläufe streuen. Diese Frage wird durch den zweiten Graph beantwortet. Je niedriger der Graph, desto geringer die Abweichung und zuverlässiger der Algorithmus.
Die Reihenfolge orientiert sich an den Tabellen der Ergebnisübersicht(Abbildungen 69 und 70): Die Ergebnisse sind nach verwendeter Karte und aufsteigend nach Effizienzwert sortiert.

Ergebnisse im Detail

Ziel des aufgeführten Versuches war es festzustellen, welche Operatoren sich für den Einsatz des genetischen Algorithmus zur Lösung des Handlungsreisendenproblems am besten eignen. Ein weiteres Ziel war es zu prüfen, ob die Operatoren mit dem Ergebnis korrelieren. Das Ergebnis (Siehe Abbildungen 69, 70) reicht aus, um eine Vermutung hierüber anzustellen, für zuverlässige Aussagen wäre ein deutlich umfangreicherer Versuchsaufbau notwendig. Da der Versuchsaufbau zwischen zwei grundsätzlich unterschiedlichen Karten unterscheidet, werden diese Fragen zunächst kartenrein betrachtet. Anschließend findet ein Vergleich hierüber statt. Das Kapitel wird mit einer Schlussbetrachtung und offenen bleibenden Fragen abgeschlossen.

Ergebnisbetrachtung der Versuche mit der Karte „QUAD“ Die Karte „QUAD“ wurde manuell erzeugt und ist damit „nicht natürlich“. Der genetische Algorithmus wird u.a. in der Industrie eingesetzt wird, wo es Wege durch Karten mit klar vorgegebenen Punkten zu optimieren gilt. Diese Punkte bilden wahrscheinlich meist ein festes Muster und sind nicht zufällig verteilt. Die Karte „QUAD“ repräsentiert eine solche, geplante Karte.

Nur 3 der eingesetzten Konstellationen von Operatoren haben bei jedem Durchlauf den optimalen Weg durch alle Städte gefunden. Das sind 7%. Bemerkenswert ist, dass die beste Konstellation mehr ca. 10-mal so effizient ist wie die schlechteste Konstellation.

Nun ist interessant, ob der Effizienzwert von den Operatoren abhängt.

Die Crossoveroperatoren verteilen sich relativ gleichmäßig über die Effizienzwerte. Hier ist kein direkter Zusammenhang erkennbar. Das lässt vermuten, dass der Erfolg des Algorithmus nicht primär vom verwendeten Crossoveroperator abhängt. Für eine solidere Aussage wäre an dieser Stelle ein umfangreicherer Versuchsaufbau nützlich.

Bei den Mutationsoperatoren sieht das Bild anders aus. Der Reverse-Operator häuft sich im oberen Teil, der Sequence-Scrubmle im unteren Teil der nach Effizienz sortierten Tabelle. Der Insert-Operator verteilt sich relativ gleichmäßig. Dies lässt erkennen, dass ein Zusammenhang von Mutation und Effizienz erkennen.

Die Reproduktionsoperatoren scheinen ebenfalls Einfluss auf den Erfolg des Algorithmus auszuüben. Die Effizientesten Ergebnisse resultieren verhäuft aus Konstellationen, die den simply-Operator zu Reproduktion der Generationen einsetzen. Der Steady-State-Operator gibt ein relativ gleichmäßig verteiltes Bild, der Generational-Operator tritt vermehrt bei den schlechteren Ergebnissen auf.

Doch auch die schlechteste Strategie ist in diesem Fall besser als der Programmdurchlauf, bei dem Crossover- Mutations- und Reproduktionsoperatoren deaktiviert wurden. Hier wurde jede neue Generation durch den Zufallsgenerator erstellt.

Zusammenfassend über alle Operatoren lässt sich sagen, dass der Einsatz des Crossoveroperator das Ergebnis im hiesigen Versuch kaum oder gar nicht beeinflusst und dass sich der Einsatz von Reverse-Mutation und simply-Reproduktion empfiehlt.

Ergebnisbetrachtung der Versuche mit der Karte „RANDOMLY_ORDERED“
Die Karte „RANDOMLY_QUAD“ wurde erzeugt, indem Punkte mit zufälligen Koordinaten auf der Karte positioniert wurden. Durch den Einsatz des Zufalls an dieser Stelle unterscheidet sich diese Karte deutlich von der Karte „QUAD“. Es ist interessant herauszufinden, ob sich der genetische Algorithmus bei der Verwendung einer Karte mit einer so grundsätzlich anderen Entstehungsgeschichte ebenso verhält wie bei der Karte „QUAD“.

Unter näherer Betrachtung der Ergebnisübersicht mit Fokus auf die Crossoveroperatoren lässt erneut erkennen, dass es keinen klaren Zusammenhang zum Effizienzwert gibt.

Ganz im Gegensatz zum Mutationsoperator. Die Effizienteren Durchläufe setzen vermehrt Reverse-Mutation ein, bei den schlechteren wird verhäuft der Sequence-Scrumble-Operator verwendet. Der Insert-Operator hält sich vornehmlich im mittleren Bereich auf. Er ist damit nicht an den guten, aber auch nicht an den schlechten Ergebnissen beteiligt.

Erstaunlich ist hier, dass einige Strategien bei diesem Versuchsaufbau durch den Zufall geschlagen werden. Das Ergebnis des Zufallsexperiments ist besser als knapp 20% der Programmdurchläufe, bei denen überlegte Strategien angewendet wurden. Dies ist erstaunlich und wirft die Frage auf, wie sich dieses Verhältnis bei Veränderung der Umwelt verhält.

Bei den Reproduktionsoperatoren ist keine klare Korrelation ersichtlich, die mit der vorhandenen Datenmenge zuverlässig getroffen werden könnte. Im oberen Teil der Ergebnistabelle, in dem die besseren Ergebnisse stehen, werden vornehmlich simple- und SteadyState-Reproduktion eingesetzt. Diese beiden Operatoren kommen jedoch auch bei den schlechtesten Algorithmen vor. Daher lässt keine klare Korrelation definieren.

Schlussbetrachtung
Bei der Verwendung unterschiedlicher Konstellationen von Operatoren im genetischen Algorithmus auf zwei unterschiedliche Karten haben sich folgende Gemeinsamkeiten und Unterschiede gezeigt: Der Crossoveroperator hat in beiden Fällen nur geringen bis keinen Einfluss auf das Ergebnis. Deutlich schwerer wirkt sich die Verwendung unterschiedlicher Mutationsoperatoren aus. Hierbei liegt Reverse-Mutation klar an der Spitze, egal welche Karte verwendet wurde. Insert-Mutation liefert ebenfalls sehr gute Ergebnisse. An den schlechtesten Ergebnisse ist stets SequenceScrumble-Mutation beteiligt.

Interessant ist, dass sich die Konvergenz unter Verwendung einer manuell erstellten „unnatürlichen“ Karte und einer Karte mit zufällig erstellten Punkten unterscheidet. Das unterschiedliche Verhalten des genetischen Algorithmus auf beiden Karten lässt vermuten, dass die Konvergenz von Position und Anzahl der Städte beeinflusst wird. Der vorgestellte Versuch eröffnet in dieser Hinsicht eine Vermutung, für eine solide Aussage diesbezüglich reicht der Vergleich von nur zwei Karten jedoch nicht aus, zumal sich bei diesen sowohl Beschaffenheit, als auch Anzahl der Städte unterscheiden.

Für alle Auswertungen bleibt die Frage offen, ob die hier getroffenen Aussagen unter Veränderung der Umwelt, und mit anderen Werten für Populationsgröße, Anzahl der Generationen, Mutationsrate, Fitnessfunktion und Verwendung des Mutationskonzeptes von Herrn Prof. Dr. Döben-Henisch konstant bleiben. Dies ließe sich durch eine Modifikation der Versuchsdurchführung, wie in dieser Arbeit beschrieben, ermitteln.

Abbildung 1: Schematische Darstellung des genetischen Algorithmus
Abbildung 2: Beispiel eines binärcodierten individuums
Abbildung 3: Beispiel eines ganzzahlcodierten individuums
Abbildung 4: Beispiel eines graphcodierten Individuums
Abbildung 5: Private Variablen der Klasse Route
Abbildung 6: Konstruktor der Klasse City
Abbildung 7: Formel zur Berechnung normierter Fitness
Abbildung 8: TSP: Berechnung der Fitness, [2]
Abbildung 9: Fitnessfunktion, [9]
Abbildung 10: Funktion zur Normierung der Fitness, [9]
Abbildung 11: Klasse, welche unsere Fitnessfunktion implementiert
Abbildung 12: Unsere Funktion zur Normalisierung der Fitness
Abbildung 13: Berechnung der Selektionswahrscheinlichkeit, [6]
Abbildung 14: Unsere Klasse für rangbasierte Selektion
Abbildung 15: Unsere Funktion, welche das Heiratsschema roulette-wheel-selection implementiert
Abbildung 16: Schematische Darstellung 1-Punkt-Crossover
Abbildung 17: Schematische Darstellung n-Punkt-Crossover
Abbildung 18: Schematische Darstellung Uniform-Crossover
Abbildung 19: Anwendung PMX, Schritt 1
Abbildung 20: Anwendung PMX, Schritt 2
Abbildung 21: Anwendung PMX, Schritt 3
Abbildung 22: Anwendung PMX, mapping table, Schritt 4
Abbildung 23: Anwendung PMX, Schritt 5
Abbildung 24: Anwendung PMX, Schritt 6
Abbildung 25: Anwendung PMX, Schritt 7
Abbildung 26: Anwendung PMX, Schritt 8
Abbildung 27: Anwendung PMX, Schritt 9
Abbildung 28: Unsere Implementation des Partially Mapped Crossover
Abbildung 29: Anwendung Greedy Sub Tour Crossover, Schritt 1
Abbildung 30: Anwendung Greedy Sub Tour Crossover, Schritt 2
Abbildung 31: Anwendung Greedy Sub Tour Crossover, Schritt 3
Abbildung 32: Anwendung Greedy Sub Tour Crossover, Schritt 4
Abbildung 33: Anwendung Greedy Sub Tour Crossover, Schritt 5
Abbildung 34: Anwendung Greedy Sub Tour Crossover, Schritt 6
Abbildung 35: Anwendung Greedy Sub Tour Crossover, Schritt 7
Abbildung 36: Anwendung Greedy Sub Tour Crossover, Schritt 8
Abbildung 37: Anwendung Greedy Sub Tour Crossover, Schritt 9
Abbildung 38: Anwendung Greedy Sub Tour Crossover, Schritt 10
Abbildung 39: Unsere Implmenetation des Greedy Sub Tour Crossover
Abbildung 40: Anwendung Greedy Crossover, Schritt 1
Abbildung 41: Anwendung Greedy Crossover, Schritt 2
Abbildung 42: Anwendung Greedy Crossover, Schritt 3
Abbildung 43: Anwendung Greedy Crossover, Schritt 4
Abbildung 44: Anwendung Greedy Crossover, Schritt 5
Abbildung 45: Unsere Implementation des Greedy Crossover
Abbildung 46: Mutation, Auswahl zu mustierender Gene
Abbildung 47: Anwendung bitflipping
Abbildung 48: Anwendung Random resetting
Abbildung 49: Anwendung Creep Mutation
Abbildung 50: Anwendung Swap Mutation
Abbildung 51: Unsere Implementation der Swap Mutation
Abbildung 52: Anwendung Insert Mutation
Abbildung 53: Unsere Implementation der Insert Mutation
Abbildung 54: Anwendung Sequence Scramble Mutation 1
Abbildung 55: Unsere Implementation der Sequence Scramble Mutation
Abbildung 56: Anwendung Scramble Mutation 2
Abbildung 57: Anwendung Reverse Mutation
Abbildung 58: Unsere Implementation der Reverse Mutation
Abbildung 59: Anwendung Ring Mutation
Abbildung 60: Unsere Implementation von Generational replacement
Abbildung 61: Unsere Implementation des Steady-state replacement
Abbildung 62: Unsere Implementation der Simple Reproduction
Abbildung 63: Benutzeroberfläche unserer Programms
Abbildung 64: Die Bereiche in der Programmoberfläche
Abbildung 65: Karte „QUAD“ im Ausgangszustand
Abbildung 66: Karte „QUAD“ mit optimaler Lösung
Abbildung 67: Karte „RANDOMLY_ORDERED“ im Ausgangszustand
Abbildung 68: Karte „RANDOMLY_ORDERED“ mit Lösung
Abbildung 69: Versuchsergebnistabelle 1
Abbildung 70: Versuchsergebnistabelle 2

[1] Michael Heck: The Nemhauser-Ullmann Algorithm and Generalizations; 31. August 2007; Bachelorarbeit; Fachhochschule Trier

[2] P. Wolf: Handlungsreisenden-Problem per genetischem Algorithmus; 6. Dezember 2010; Universität Bielefeld

[3] Omar M. Sallabi, Younis El-Haddad: An Improved Genetic Algorithm to Solve the Traveling Salesman Problem; 2009; World Academy of Science, Engineering and Technology

[4] Aybars Ugur, Serdar Korukoglu, Ali Caliskan, Muhammed Cinsdikici, Ali Alp: GENETIC ALGORITHM BASED SOLUTION FOR TSP ON A SPHERE; 2009; Department of Mathematics, Faculty of Science, International Computer Institute, University of Edge, 35100 Bornova-Izmir, Türkei

[5] Fozia Hanif Khan, Nasiruddin Khan, Syed Inayatullah, Shaikh Tajuddin Nizami: SOLVING TSP PROBLEM BY USING GENETIC ALGORITHM; International Journal of Basic & Applied Sciences IJBAS Vol: 9 No: 10

[6] Prof. Dr. H. Kleine Büning, Oliver Kramer, Chuan-Kang Ting, Daniel Aslan: Genetische Algorithmen; Universität Paderborn

[7] Karsten Weicker: Evolutionäre Algorithmen; 2., überarbeitete und erweiterte Auflage; Teubner Verlag 2007; ISBN 978-3-8351-0219-4

[8] Rahul Kala, Harsh Vazirani, Anupam Shukla, Ritu Tiwari: Offline Handwriting Recognition using Genetic Algorithm; März 2010; IJCSI International Journal of Computer Science Issues; Soft Computing and Expert System Laboratory, Indian Institute of Information Technology and Management Gwalior, Gwalior, Madhya Pradesh-474010, India

[9] G.Doeben-Henisch: General (Behavior Based) Computational Learning Theory (G(B^2)CLT); May 5, 2011; University of Applied Sciences Frankfurt am Main (Germany) Faculty of Computer Science and Engineering, Nibelungenplatz 1, D-60318 Frankfurt am Main, Germany

[10] Christian Rodemeyer: Entwicklung und Erprobung eines Evolutionären Algorithmus zur rechnergestützten Optimierung der Maschinenbelegung in einem Druckgußwerk; Wintersemester 1994/95; Diplomarbeit DI; Universität Gesamthochschule Essen

[11] J. Homberger: Eine Evolutionsstrategie für das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen; FernUniversität Hagen

[12] Sascha Riexinger: Einführung in Evolutionäre Algorithmen; Universität Stuttgart

[13] Heinz Mühlenbein, Hans-Michael Voigt: Gene Pool Recombination in Genetic Algorithms; GMD 53754 St. Augustin, Germany; T.U. Berlin 13355 Berlin, Germany

[14] Bharat Kondeti: TRAVELING SALES-MAN PROBLEM USING GENETIC ALGORITHMS; Available via http from http://ethoughts.brinkster.net/my/tsp/tsp.html

[15] Barbara Czogalla: Einführung in Genetische Algorithmen; 30.November 2005; ETH Zürich

[16] Samir W. Mahfoud: PhD Thesis: Niching Methods for Genetic Algorithms (IlliGAL Report No. 95001); May 1995; Department of General Engineering, University of Illinois at Urbana-Champaign.

[17] John Lawton, Todd Wipke: Graph Crossover; University of California at Santa Cruz; Al Globus, CSC at NASA Ames Research Center, Sean Atsatt, Sierra Imaging, Inc.

[18] Francisco B. Pereira (ISEC), Penousal Machado (ISEC), Ernesto Costa (CISUC), Amílcar Cardoso (CISUC); Graph Based Crossover – A Case Study with the Busy Beaver Problem; ISEC Qta. da Nora, 030 Coimbra, Portugal; CISUC Dep. de Eng. Informática, Univ. of Coimbra, Polo II, 3030 Coimbra, Portugal

[19] Darrel Whitley: A Genetic Algorithm Tutorial; November 10, 1993; Technical Report CS-93-103 (Revised); Department of Computer Science, Colorado State University, Fort Collins, US

[20] Dusan Saiko: Traveling Salesman Problem; 23.08.2005; Available via http from http://code.google.com/p/java-traveling-salesman/

[21] Hiroaki Sengoku, Ikuo Yoshihara: A fast TSP Solver Using GA on JAVA; Systems Development Laboratory, Hitachi, Ltd, Kawasaki, 215 Japan;

Download Programm Ernst Metka