Im vorherigen Artikel wurden genetische Algorithmen (GA) eingeführt und strukturiert erläutert bzw. in einen größeren Kontext von suchbasierten Algorithmen eingeordnet. Wem das etwas zu theoretisch war, bekommt hier eine Herleitung mit ganz konkreten Code-Beispielen zum selber ausprobieren.

Da ReTest genetische Algorithmen zur genetischen bzw. evolutionären Programmierung einsetzt, möchte ich im Folgenden die Vorteile eines solchen Algorithmus an einem passenden Beispiel veranschaulichen. Dieses Beispiel soll so einfach sein, dass es völlig verständlich und manuell nachvollziehbar ist. Gleichzeitig soll es eine echte Herausforderung darstellen und keineswegs trivial sein.

Die Türme von Hanoi

Die Türme von Hanoi sind ein mathematisches Knobelspiel für einen einzelnen Spieler. Es besteht aus drei Stäben — den drei Türmen von Hanoi — auf welchen unterschiedlich große Lochscheiben aufeinander liegen. Die Lochscheiben sind dabei der Größe nach sortiert; wobei die größte Scheibe unten liegt. Zu Beginn des Spieles liegen alle Scheiben auf einem Turm. Ziel des Spiels ist es alle Scheiben von einem Turm auf einen anderen Turm zu versetzen und dabei 1. immer nur eine Scheibe zu bewegen und 2. niemals eine größere auf eine kleinere Scheibe zu legen. Die Türme von Hanoi werden als eine Klasse in Python repräsentiert und alle möglichen Züge als einzelne Methoden:

class TuermeVonHanoi():
    def __init__(self):
        self.A = [6, 5, 4, 3, 2, 1]
        self.B = []
        self.C = []
    
    def AtoB(self): self.B.append(self.A.pop())
    
    def AtoC(self): self.C.append(self.A.pop())
    
    def BtoA(self): self.A.append(self.B.pop())
    
    def BtoC(self): self.C.append(self.B.pop())
    
    def CtoA(self): self.A.append(self.C.pop())
        
    def CtoB(self): self.B.append(self.C.pop())
        
    def valid(self):
        return all(self.A[i + 1] < self.A[i] for i in range(0, len(self.A)-1)) and \
            all(self.B[m + 1] < self.B[m] for m in range(0, len(self.B)-1)) and \
            all(self.C[n + 1] < self.C[n] for n in range(0, len(self.C)-1))

Im Konstruktor der Klasse in den Zeilen 3 – 5 werden die "Türme" mit den "Scheiben" definiert — hier ist ein Turm einfach ein Array und die Scheiben werden durch Zahlen repräsentiert. In den Zeilen 7 – 17 finden sich die entsprechenden Methoden zum Verschieben der Lochscheiben und in Zeile 19 – 22 eine Validierungsmethode die True zurückgibt, wenn keine größere auf einer kleineren Scheibe liegt — die Türme als regelkonform sind.

Die Türme von Hanoi sind ausgiebig theoretisch untersucht worden. Es gibt sowohl iterative als auch rekursive Algorithmen die eine optimale Lösung erzeugen. Hier ein rekursiver Algorithmus:

def bewege(schritte, i, a_name, b_name, c_name):
    if (i > 0):
        bewege(schritte, i-1, a_name, c_name, b_name)
        schritte.append('tuerme.' + a_name + 'to' + c_name + '()')
        bewege(schritte, i-1, b_name, a_name, c_name)
    return schritte

def algorithmus():
    return bewege([], 6, 'A', 'B', 'C')

Dieser Algorithmus erzeugt eine optimale Lösung in Form von 62 Schritten, die ausgeführt werden müssen um alle "Scheiben" vom Turm A zum Turm C zu bewegen, sodass dabei niemals eine größere Scheibe auf einer kleineren liegt:

schritte = [\
'tuerme.AtoB()', \ #[654321][][] -> [65432][1][]
'tuerme.AtoC()', \ #[65432][1][] -> [6543][1][2]
'tuerme.BtoC()', \ #[6543][1][2] -> [6543][][21]
'tuerme.AtoB()', \ #[6543][][21] -> [654][3][21]
'tuerme.CtoA()', \ #[654][3][21] -> [6541][3][2]
'tuerme.CtoB()', \ #[6541][3][2] -> [6541][32][]
'tuerme.AtoB()', \ #[6541][32][] -> [654][321][]
'tuerme.AtoC()', \ #[654][321][] -> [65][321][4]
'tuerme.BtoC()', \ #[65][321][4] -> [65][32][41]
'tuerme.BtoA()', \ #[65][32][41] -> [652][3][41]
'tuerme.CtoA()', \ #[652][3][41] -> [6521][3][4]
'tuerme.BtoC()', \ #[6521][3][4] -> [6521][][43]
'tuerme.AtoB()', \ #[6521][][43] -> [652][1][43]
'tuerme.AtoC()', \ #[652][1][43] -> [65][1][432]
'tuerme.BtoC()', \ #[65][1][432] -> [65][][4321]
'tuerme.AtoB()', \ #[65][][4321] -> [6][5][4321]
'tuerme.CtoA()', \ #[6][5][4321] -> [61][5][432]
'tuerme.CtoB()', \ #[61][5][432] -> [61][52][43]
'tuerme.AtoB()', \ #[61][52][43] -> [6][521][43]
'tuerme.CtoA()', \ #[6][521][43] -> [63][521][4]
'tuerme.BtoC()', \ #[63][521][4] -> [63][52][41]
'tuerme.BtoA()', \ #[63][52][41] -> [632][5][41]
'tuerme.CtoA()', \ #[632][5][41] -> [6321][5][4]
'tuerme.CtoB()', \ #[6321][5][4] -> [6321][54][]
'tuerme.AtoB()', \ #[6321][54][] -> [632][541][]
'tuerme.AtoC()', \ #[632][541][] -> [63][541][2]
'tuerme.BtoC()', \ #[63][541][2] -> [63][54][21]
'tuerme.AtoB()', \ #[63][54][21] -> [6][543][21]
'tuerme.CtoA()', \ #[6][543][21] -> [61][543][2]
'tuerme.CtoB()', \ #[61][543][2] -> [61][5432][]
'tuerme.AtoB()', \ #[61][5432][] -> [6][54321][]
'tuerme.AtoC()', \ #[6][54321][] -> [][54321][6]
'tuerme.BtoC()', \ #[][54321][6] -> [][5432][61]
'tuerme.BtoA()', \ #[][5432][61] -> [2][543][61]
'tuerme.CtoA()', \ #[2][543][61] -> [21][543][6]
'tuerme.BtoC()', \ #[21][543][6] -> [21][54][63]
'tuerme.AtoB()', \ #[21][54][63] -> [2][541][63]
'tuerme.AtoC()', \ #[2][541][63] -> [][541][632]
'tuerme.BtoC()', \ #[][541][632] -> [][54][6321]
'tuerme.BtoA()', \ #[][54][6321] -> [4][5][6321]
'tuerme.CtoA()', \ #[4][5][6321] -> [41][5][632]
'tuerme.CtoB()', \ #[41][5][632] -> [41][52][63]
'tuerme.AtoB()', \ #[41][52][63] -> [4][521][63]
'tuerme.CtoA()', \ #[4][521][63] -> [43][521][6]
'tuerme.BtoC()', \ #[43][521][6] -> [43][52][61]
'tuerme.BtoA()', \ #[43][52][61] -> [432][5][61]
'tuerme.CtoA()', \ #[432][5][61] -> [4321][5][6]
'tuerme.BtoC()', \ #[4321][5][6] -> [4321][][65]
'tuerme.AtoB()', \ #[4321][][65] -> [432][1][65]
'tuerme.AtoC()', \ #[432][1][65] -> [43][1][652]
'tuerme.BtoC()', \ #[43][1][652] -> [43][][6521]
'tuerme.AtoB()', \ #[43][][6521] -> [4][3][6521]
'tuerme.CtoA()', \ #[4][3][6521] -> [41][3][652]
'tuerme.CtoB()', \ #[41][3][652] -> [41][32][65]
'tuerme.AtoB()', \ #[41][32][65] -> [4][321][65]
'tuerme.AtoC()', \ #[4][321][65] -> [][321][654]
'tuerme.BtoC()', \ #[][321][654] -> [][32][6541]
'tuerme.BtoA()', \ #[][32][6541] -> [2][3][6541]
'tuerme.CtoA()', \ #[2][3][6541] -> [21][3][654]
'tuerme.BtoC()', \ #[21][3][654] -> [21][][6543]
'tuerme.AtoB()', \ #[21][][6543] -> [2][1][6543]
'tuerme.AtoC()', \ #[2][1][6543] -> [][1][65432]
'tuerme.BtoC()'] \ #[][1][65432] -> [][][654321]

Diese Schritte kann man in Python mittels der Methode eval ausführen:

def fuehre_aus(schritte):
    tuerme = TuermeVonHanoi()
    eval_locals = {'tuerme': tuerme}
    for schritt in schritte:
        eval(schritt, {}, eval_locals)
        if not tuerme.valid():
            raise Exception('Ungueltiger Turm!')
    return tuerme

Die Methode fuehre_aus erzeugt ein neues TuermeVonHanoi Objekt (in Zeile 2) und legt dieses im Ausführungskontext unter der Variablen tuerme ab (Zeile 3). Dann werden die Schritte im übergebenen Array einzeln ausgeführt (Zeilen 4 und 5) und jeweils geprüft ob das Resultat noch ein gültiger Turm ist (Zeilen 6 und 7).

Damit ist der grundsätzliche Rahmen der Aufgabe abgesteckt. Wie bereits erläutert, wollen wir diese Lösung von 62 Schritten jedoch nicht vorgeben. Vielmehr wollen wir untersuchen, ob ein intelligenter Algorithmus von selbst auf diese Lösung kommt. Der Suchraum dieser Aufgabe ist unendlich groß, d.h. es gibt unendliche viele Lösungskandidaten wie auch unendlich viele Lösungen. Damit sind lokale Suchalgorithmen die richtige Wahl.

Wie im vorherigen Artikel erläutert, geht es bei den genetischen Algorithmen um Optimierungsprobleme. Wir brauchen also eine Zielfunktion um die Lösungskandidaten zu bewerten und miteinander zu vergleichen.

def min_zielfunktion(tuerme): return (21 - sum(tuerme.C))

Bei uns ist diese Zielfunktion denkbar einfach. Wie bereits im vorherigen Artikel erläutert, kann man jedes Problem als Minimierungs- oder Maximierungsproblem definieren. Da wir eine optimale Lösung erkennen, nämlich wenn alle Türme von A zum Turm C bewegt wurden, wollen wir unsere Aufgabe als Minimierungsproblem definieren. Die Summe aller fünf Scheiben ist 1 + 2 + 3 + 4 + 5 + 6 = 21. D.h. wir haben eine optimale Lösung, sobald die Summe der Scheiben auf dem Turm C gleich 21 ist. Die Zielfunktion macht aber nicht nur Lösungskandidaten vergleichbar, sie definiert auch die Form bzw. die Landschaft des Suchraumes.

Zur besseren Veranschaulichung der Landschaft, habe ich diese zweidimensional am Beispiel der oben entworfenen optimalen Lösung dargestellt. Da klassische Algorithmen von Maximierungsproblemen ausgehen und entsprechend benannt sind (z.B. Bergsteigeralgorithmus), habe ich die Landschaft zur besseren Veranschaulichung umgedreht. Wie ersichtlich ist, gibt es hierbeit zehn lokale Maxima/Minima und mehrere Plateaus. Der Algorithmus muss zum Erreichen des globalen Maximums/Minimums mindestens drei Mal den höchsten Stand des Zielwertes in Kauf nehmen. Oder anders formuliert: Der Turm C wird im Verlauf mindestens 3 Mal wieder vollständig leer sein.

Verschiedene lokale Suchalgorithmen

Wie im vorherigen Artikel erläutert, hat der Bergsteigeralgorithmus seinen Namen von der Eigenschaft, dass er sich in der Lanschaft des Lösungsraums (bei einem Maximierungsproblem) immer in Richtung aufsteigendem Zielwert bewegt. Da wir unser Problem jedoch als Minimierungsproblem definiert haben, bewegt sich unser Algorithmus immer in Richtung absteigendem Zielwert.

def algorithmus():
    aktueller_zustand = []
    aktueller_zielwert = max_wert
    idx = 0
    while idx < len(optionen) and aktueller_zielwert > 0:
        neuer_zustand = kopiere(aktueller_zustand)
        neuer_zustand.append(optionen[idx])
        neuer_zielwert = berechne_zielwert(neuer_zustand) 
        if neuer_zielwert < aktueller_zielwert:
            aktueller_zustand = neuer_zustand
            aktueller_zielwert = neuer_zielwert
            idx = 0
        idx += 1
    return aktueller_zustand

Dieser Algorithmus beginnt mit einem zufälligen bzw. bei uns mit einem leeren Zustand (Zeile 2) und probiert einfach alle Optionen der Reihe nach durch (Zeile 5). Sobald sich der Zustand dadurch verbessert, wird auf diesen besseren Zustand gewechselt (Zeilen 9 – 12). Wenn der neue Zustand keine Verbesserung darstellt wird er verworfen (implizit, da der alte Zustand in Zeile 6 kopiert wurde). Dieses Verhalten nennt man gierig (eng. greedy). Im gegebenen Fall kommt der Algorithmus nach 10 Versuchen auf folgende Lösung:

['tuerme.AtoB()', 'tuerme.AtoC()', 'tuerme.BtoC()'] -> [6543][][21], Anzahl Schritte: 3, Zielwert: 18

Diese Lösung hängt natürlich davon ab, in welcher Reihenfolge die Optionen probiert werden und ist damit abhängig von der konkreten Implementierung. Man kann den Algorithmus etwas verbessern, indem man die zu testende Option zufällig auswählt. Dieser Algorithmus heißt dann stochastischer Bergsteigeralgorithmus.

import random
random.seed(0)

def algorithmus():
    aktueller_zustand = []
    aktueller_zielwert = max_wert
    count = 0
    while count < versuche and aktueller_zielwert > 0:
        neuer_zustand = kopiere(aktueller_zustand)
        neuer_zustand.append(random.choice(optionen))
        neuer_zielwert = berechne_zielwert(neuer_zustand) 
        if neuer_zielwert < aktueller_zielwert:
            aktueller_zustand = neuer_zustand
            aktueller_zielwert = neuer_zielwert
        count += 1
    return aktueller_zustand

Dieser Algorithmus ist nur an wenigen Stellen geändert. So wurde das random Modul für Zufälle importiert. Damit der Code trotzdem wiederholgenau ist, wird der Pseudozufallszahlengenerator mit einem festen Startwert initialisiert (Zeile 2). Außerdem wurde die idx Variable, die sich auf den Array von Optionen bezog durch eine count Variable ersetzt, die die Anzahl der Versuche zählt (Zeilen 7 und 15). Der Code wird einfach versuche Mal durchlaufen, dafür brauchen wir uns nicht zu merken, welche zufällig gewählte Option (Zeile 10) schon probiert wurde. Wenn man diesen Algorithmus ausführt, so ist man zwar nicht mehr von der konkreten Implementierung abhängig, kann aber wie am Ergebnis zu sehen "Pech" haben — im gegebenen Fall bleibt der Algorithmus sofort in einem lokalen Minimum hängen.

['tuerme.AtoC()'] -> [65432][][1], Anzahl Schritte: 1, Zielwert: 20

Die nächste Verbesserung besteht logischerweise darin, den Algorithmus mehrmals auszuführen, mit unterschiedlichen Startwerten. Ein solcher Algorithmus nennt sich Zufalls-Neustart Algorithmus.

def zufalls_neustart(algorithmus):
    bester_zustand = []
    bester_zielwert = max_wert
    for x in range(0, neustarts):
        random.seed(x)
        aktueller_zustand = algorithmus()
        aktueller_zielwert = berechne_zielwert(aktueller_zustand)
        if aktueller_zielwert < bester_zielwert:
            bester_zielwert = aktueller_zielwert
            bester_zustand = aktueller_zustand
    return bester_zustand

Obiger Code nimmt einen beliebigen zufallsbasierten Algorithmus und führt diesen neustarts Mal aus (Zeile 6). Dabei wird jeweils der Startwert des Pseudozufallszahlengenerators neu gesetzt (Zeile 5), um dabei möglicherweise zu einem anderen Ergebnis zu gelangen. Das jeweils beste Ergebnis der verschiedenen Ausführungen wird zurückgegeben.

Wenn man diesen Code ausführt stellt sich heraus, dass wir in der ersten Version des Bergsteigeralgorithmus "Glück" hatten, weil wir sofort die beste Lösung erhielten, die mit diesem Algorithmus möglich ist. Offensichtlich besteht das Problem darin, dass wir beim Erreichen bzw. Generieren einer Lösung kurzzeitig einen schlechteren Wert tolerieren müssen. Ein solcher Algorithmus, der mit einer gewissen Wahrscheinlichkeit einen Folgezustand wählt der schlechter ist als der aktuelle, nennt sich Zufallsbewegung (eng. random walk).

def algorithmus():
    aktueller_zustand = []
    aktueller_zielwert = max_wert
    count = 0
    while count < versuche and aktueller_zielwert > 0:
        neuer_zustand = kopiere(aktueller_zustand)
        neuer_zustand.append(random.choice(optionen))
        neuer_zielwert = berechne_zielwert(neuer_zustand)
        if neuer_zielwert < aktueller_zielwert or \
        	(neuer_zielwert < max_wert and random.choice([True, False])):
            aktueller_zustand = neuer_zustand
            aktueller_zielwert = neuer_zielwert
        count += 1
    return aktueller_zustand

Dieser Algorithmus unterscheidet sich vom Bergsteigeralgorithmus nur darin, dass wir mit 50% Wahrscheinlichkeit auch eine schlechtere Lösung akzeptieren (Zeile 10). Wenn man diesen Algorithmus 10 Mal ausführt (Zufalls-Neustart), so erhält man nach 66.000 Versuchen als beste Lösung die folgende:

[tuerme.AtoB(), tuerme.BtoC(), tuerme.CtoB(), tuerme.BtoA(), tuerme.AtoB(), ...] -> [51][][6432], Anzahl Schritte: 2018, Zielwert: 6

Wie man sieht funktioniert dieser Ansatz schon relativ gut und kommt der Lösung des Problems schon deutlich näher als rein gierige Algorithmen. Eine Verbesserung des Ansatzes besteht darin, die Wahrscheinlichkeit mit der ein schlechterer Zustand angenommen wird über die Zeit geringer werden zu lassen. Das hat zur Folge, dass am Anfang der Suche über lokale Maxima "hinweg gesprungen" wird, aber verhindert, dass ein solcher "Sprung" kurz vor Ende zu einem subobtimalen Ergebnis führt. Dieser Ansatz heißt simulierte Abkühlung (eng. simulated annealing).

def algorithmus():
    aktueller_zustand = []
    aktueller_zielwert = max_wert
    count = 0
    while count < versuche and aktueller_zielwert > 0:
        neuer_zustand = kopiere(aktueller_zustand)
        neuer_zustand.append(random.choice(optionen))
        neuer_zielwert = berechne_zielwert(neuer_zustand)
        if neuer_zielwert < aktueller_zielwert or \
            (neuer_zielwert < max_wert and randint(0, versuche) > count):
            aktueller_zustand = neuer_zustand
            aktueller_zielwert = neuer_zielwert
        count += 1
    return aktueller_zustand

Dieser Algorithmus unterscheidet sich von dem Zufallsbewegungsalgorithmus nur in Zeile 10. Das Ergebnis nach 66.000 Versuchen (was schon eine ganze Zeit dauert) sieht wie folgt aus:

[tuerme.AtoB(), tuerme.AtoC(), tuerme.BtoA(), tuerme.AtoB(), tuerme.BtoA(), ...] -> [6][][54321], Anzahl Schritte: 1869, Zielwert: 6

Eine andere Möglichkeit die Suche effizienter zu gestalten, besteht darin, nicht 10 separate Suchen laufen zu lassen, sondern 10 Suchen gleichzeitig, und ergebnislose Suchen schneller zu verwerfen bzw. die Ressourcen dort zu konzentrieren, wo der meiste Fortschritt gemacht werden kann. Ein solcher Algorithmus heißt Balkensuchalgorithmus.

Damit sieht unsere Balkensuche aus wie folgt:

def algorithmus():
    aktuelle_zustaende = [(max_wert, []) for i in range(0, k)]
    count = 0
    while count < versuche and aktuelle_zustaende[0][0] > 0:
        neue_zustaende = []
        for (aktueller_zielwert, aktueller_zustand) in aktuelle_zustaende:
            neuer_zustand = kopiere(aktueller_zustand)
            neuer_zustand.append(random.choice(optionen))
            neuer_zielwert = berechne_zielwert(neuer_zustand)
            if neuer_zielwert < aktueller_zielwert or \
                (neuer_zielwert < max_wert and randint(1, versuche) > count):
                insert(neue_zustaende, neuer_zielwert, neuer_zustand)
            else:
                insert(neue_zustaende, aktueller_zielwert, aktueller_zustand)
        count += 1
        insert(neue_zustaende, aktuelle_zustaende[0][0], aktuelle_zustaende[0][1])
        aktuelle_zustaende = neue_zustaende
    return aktuelle_zustaende[0][1]

Die Balkensuche pflegt dabei das Array: neue_zustaende. Die Funktion insert fügt neue Zustände und Zielwerte so ein, dass das Array immer sortiert ist. Wenn man die Balkensuche so ausführt, erhält man nach 90.000 Versuchen als Ergebnis:

[tuerme.AtoB(), tuerme.BtoA(), tuerme.AtoC(), tuerme.AtoB(), tuerme.CtoA(), ...] -> [6][3][5421], Anzahl Schritte: 98, Zielwert: 9

Leider hat noch keine Suche zum gewünschten Ergebnis geführt.

Genetische Algorithmen

Wie im vorherigen Artikel beschrieben: Wenn man einen Folgezustand als Nachkomme (eng. offspring) bezeichnet und die Zielfunktion als Fitness, dann gleicht stochastische Balkensuche einem evolutionären Prozess mit asexueller Reproduktion und natürlicher Selektion. Ein Genetischer Algorithmus oder GA macht daraus eine sexuelle Reproduktion, indem zwei Elternzustände oder Individuen kombiniert werden anstatt einen einzelnen Zustand zu modifizieren. Diese Kombination wird Rekombination (eng. crossover) genannt. Rekombination birgt den Vorteil, dass verschiedene Teile von Individuen, die sich unabhängig entwickelt haben um sinnvolle Funktionen zu erfüllen, kombiniert werden und dabei die Granulariät mit der die Suche operiert erhöht wird.

def algorithmus():
    aktuelle_zustaende = generiere_initiale(k)
    count = 0
    while count < versuche and min_zielfunktion(aktuelle_zustaende[0][2][-1]) > 0: 
        neue_zustaende = []
        neue_zielwerte = []
        for idx in xrange(len(aktuelle_zustaende)):
            neuer_zustand = ziehe(aktuelle_zustaende)
            if random() <= 0.75:
                neuer_zustand = rekombiniere(neuer_zustand, ziehe(aktuelle_zustaende))
            neuer_zustand = mutiere(neuer_zustand)
            insert_prob(neue_zustaende, neue_zielwerte, neuer_zustand)
            count += 1
        insert_prob(neue_zustaende, neue_zielwerte, aktuelle_zustaende[0])
        aktuelle_zustaende = neue_zustaende
    return aktuelle_zustaende[0][1]

Dieser Code erreicht nun endlich unser Ziel und generiert nach ca. 65.000 Versuchen eine gültige Lösung für unsere Türme von Hanoi:

[tuerme.AtoC(), tuerme.AtoB(), tuerme.BtoA(), tuerme.CtoA(), tuerme.AtoC(), ...] -> [][][654321], Anzahl Schritte: 955, Zielwert: 0

Die einzelnen Methoden zu Mutation (Zeile 11) und Rekombination (Zeile 10) sind zwar umfänglich aber relativ intuitiv — einzig zu beachten ist, dass ein Rekombination zwischen zwei Schrittfolgen nur an Stellen erfolgen kann, an denen dies prinzipiell auch möglich ist, d.h. dass in beiden Sequenzen eine Stelle gesucht wird, an denen alle möglichen Folgeoperationen gleich sind. Auf eine ausführliche Darstellung und Erläuterung wird aber an dieser Stelle verzichtet; wer an den Details Interesse hat, kann sich den Code herunter laden und direkt anschauen.

Dem geneigten Leser wird aufgefallen sein, dass im Code (sowohl oben als auch im Code im Download) diverse Magic Numbers vorkommen (z.B. die Wahrscheinlichkeit einer Rekombination in Zeile 9). Bleibt zu erläutern, wie diese Magischen Zahlen zustande kommen. Tatsächlich handelt es sich um heuristisch ermittelte Werte, mit denen der Algorithmus besonders gut funktioniert. Bei der Implementierung eines genetischen Algorithmus hat man sehr viele Freiheitsgrade. Jede Änderung führt zu einem anderen Genetischen Algorithmus, weshalb man auch nie von dem Genetischen Algorithmus spricht, immer nur von einem Genetischen Algorithmus. Letztendlich gibt es keinen einzelnen Superalgorithmus, der immer allen anderen Algorithmen in jeder Situation überlegen ist. Auch ein Genetischer Algorithmus muss immer wieder für ein Problem kalibriert werden. Im vorliegen Fall geschah dies schlicht durch ausprobieren — in der Natur ist diese Kalibrierung Teil des Algorithmus!

Download:

Tagged in : Programmierung, Genetische Algorithmen,

Dr. Jeremias Rößler
Dr. Jeremias Rößler

ist Software Ingenieur – spezialisiert auf das Erstellen und die Pflege von großen, komplexen Softwaresystemen, die unter akzeptablen Kosten stabil und zuverlässig funktionieren. Er besitzt über sechs Jahre Berufserfahrung in der Entwicklung von Individualsoftware. 2013 hat er am Lehrstuhl für Softwaretechnik an der Universität des Saarlandes promoviert. Seine Forschung beschäftigt sich mit dem Auffinden und der Analyse von Fehlern, indem Software-Systeme mittels generierter Tests systematisch ausgeführt und dabei Fehler aufgedeckt und analysiert werden. Er ist Gründer von ReTest, einem IT-Dienstleistungsunternehmen, das Software programmunterstützt testet.