Im letzten Artikel gab es eine Einführung in die evolutionären Algorithmen, was man mit ihnen machen kann und wie sie generell funktionieren. Wir erinnern uns: Evolutionäre Algorithmen ermöglichen das Lösen selbst komplexer Optimierungsprobleme, indem immer neue Lösungskandidaten erstellt und modifiziert werden, wobei sich die neuen Kandidaten durch einen vorgegebenen Selektionsdruck langsam dem gewünschten Ziel – der Lösung – annähern. In diesem Artikel wollen wir nun etwas tiefer in die Materie einsteigen und schauen, was bei so einem Algorithmus im Detail geschieht.


Rekapitulation

Rekapitulieren wir zuerst noch einmal die Arbeitsweise eines evolutionären Algorithmus. Ausgehend von einer Anfangsgeneration
g0 werden sukzessive neue Generationen erstellt, indem aus der aktuellen Generation jeweils einige Individuen (die Lösungskandidaten) selektiert, also ausgewählt werden; Vertreter dieser Auswahl werden rekombiniert, also miteinander gekreuzt und das entstehende neue Individuum noch einmal mutiert, also verändert. Durch Wiederholung der Rekombination und Mutation entsteht eine neue Generation, welche die Ausgangsbasis für die nächste Iteration im Algorithmus darstellt. Das ganze wird so lange wiederholt, bis eine hinreichend gute Lösung gefunden wurde. Der Pseudocode hierfür sieht so aus:

(1)  Evolutionary Algorithm: g0TnT:
(2)    t ∈ T
(3)    g ∈ Tn, g ← g0
(4)    do:
(5)       g’, g” ∈ Tn
(6)       g’ ← select individuals from g
(7)       g” ← recombine individuals in g’
(8)       mutate individuals in g”
(9)       t ← select best individual in g”
(10)      g ← g”
(11)   while t not good enough
(12)   return t

 

Schauen wir uns doch die Schritte einmal in der Reihenfolge der Ausführung im Detail an. Anzumerken ist vorher, dass es für jeden Schritt die verschiedensten Strategien gibt, deren Anwendbarkeit meist eng mit der in den jeweils anderen Schritten gewählten Strategie zusammenhängt; bei manchen Strategien kann es sogar passieren, dass Selektion und Rekombination zu einem Schritt verschmelzen. Ich werde im Folgenden das allgemeine Vorgehen bei den einzelnen Schritten beschreiben und einige der möglichen Strategien vorstellen.

Das ganze möchte ich parallel an einem kleinen Beispiel demonstrieren. Bevor ich hier aber mit einem mathematischen Problem anfange und damit zusätzliche Verwirrung stifte, nehme ich lieber ein praktisches (und nicht ganz ernst gemeintes) Problem aus der realen Welt (welches zudem zumindest jedem Katzenbesitzer bekannt sein dürfte). Betrachten wir das folgende Bild (via icanhascheezburger.com):

Das Optimierungsproblem hier dürfte klar sein: wir sind eine Katze und möchten und so positionieren, dass wir den maximalen Platz auf dem Bett einnehmen, also genau in der Mitte liegen. Tun wir zudem so, als wüssten wir nicht genau, wo die Mitte ist und würden sie durch einen evolutionären Algorithmus bestimmen wollen. Das Optimierungsproblem ist also, eine Position genau in der Mitte zu finden; die Lösungskandidaten sind die verschiedenen möglichen Positionen auf dem Bett.

 

Selektion

Die Selektion ist der Schritt, in welchem aus der aktuellen Generation Individuen für die Rekombination ausgewählt werden. Grundsätzlich lassen sich hier zwei Vorgehensweisen unterscheiden, deren Wahl die genaue Funktionsweise der Rekombination beeinflusst. Zum einen kann zuerst die zu rekombinierende Menge an Individuen komplett ausgewählt werden; die Rekombination erfolgt dann in der Regel, indem jeweils zwei Individuen aus der selektierten Menge zufällig ausgewählt und miteinander gekreuzt werden. Zum anderen können Selektion und Rekombination auch gleichzeitig erfolgen, indem wiederholt zuerst zwei Individuen ausgewählt und diese direkt miteinander rekombiniert werden – die Zeilen (6) und (7) im Pseudocode würden also zu einer verschmelzen und es würde keine Zwischenmenge g’ entstehen.

In jedem Fall wird aber ein Kriterium gebraucht, nach welchem die Individuen ausgewählt werden sollen. Das einfachste wäre natürlich eine zufällige Selektion; dies würde aber vollkommen den Selektionsdruck (dieser entsteht nämlich durch die Strenge der Selektion) nehmen und damit zu einer ungerichteten Evolution führen – dem Ziel würde man damit nicht näher kommen. Ein anderes Selektionsverfahren ist also notwendig!

1 / 2 / 3 / 4 / Auf einer Seite lesen

Kommentare (10)

  1. #1 Donnamara
    Dezember 11, 2011

    Das Katzenbeispiel ist völlig daneben. Eine umständlichere Programmierung des Bettproblems habe ich noch nie gesehen. Außerdem werden unzulässige apriori Voraussetzungen gemacht. Und schon gar nicht können die jeweiligen Randbedingungen auch nur annähernd gewichtet werden und zudem weiß niemand, was eine Katze sich überhaupt denkt!

    Der erfahrene Katzenbeobachter (nicht Liebhaber) weiß, daß bar jeglicher Logik eines Möchtegernprogrammierers die Standardabweichung der mittleren Positionslage mehr als 13 cm beträgt. Von Tag zu Tag und nicht von Katze zu Katze!

    Heutige Programmierer vestehen sich offensichtlich noch schlechter auf Katzenpsychologie als auf die Untergrundströmungsverhältnisse einer Staumauer, wobei sie in diesem Fall von diesem Problem noch nicht einmal etwas gehört haben. Aber in Mutchens Küche lief eben eine Katze herum, deren Eigenarten sie auch nicht berechnen können.

  2. #2 Christian A.
    Dezember 11, 2011

    Schöner Artikel! Aber ah grr! Dieser Artikel endet mal wieder mit zwei üblen Cliffhangern(*)!

    Mich interessiert beide angekündigten Themen:
    – Wie geht man mit lokalen Optima um?
    Um im Katzenbeispiel zu bleiben, könnte man sagen dass die Katze möglichst tief auf einem ungemachten Bett liegen will, dann hätte man eine gute Ausrede eine wellige (Energie-, Fitness-) Landschaft einzuführen 😉
    – Und wie kann man sein Evolutionsprogramm so schreiben, dass es gut verallgemeinert? Da ich keine Ahnung von Programmieren habe, bin ich an praktischen Lösungen immer interessiert 😉

    (*) Bevor das jemand falsch versteht: “übel” bedeutet hier nur, dass ich es nicht abwarten kann, bis der nächste Teil kommt.

  3. #3 Marcus Frenkel
    Dezember 11, 2011

    @Christian A.
    Danke für die Anregung mit der Schlafhöhe; das werde ich vielleicht so ähnlich übernehmen (nicht mit Tiefe, sondern mit Höhe, da Katzen gerne hoch liegen 😉 ).

  4. #4 Gustav
    Dezember 11, 2011

    Naja, Katzen leigen auch gern In Gruben und Höhlen. Zum Beispiel Kisten oder im Bett,wenn sie zwischen Falten der Bettdecke liegen… und das am besten hoch, also eine Grupe in der Höhe oder so. 😉

  5. #5 Gustav
    Dezember 11, 2011

    Grube nicht Grupe… [ausrede]meine Katze ist mir gerade über die Tastatur gelaufen[/ausrede]

  6. #6 BreitSide
    Dezember 12, 2011

    @Gustav: Deine auch?

    Meine setzte (leider ist sie seit zwei Wochen eine Ex-Katze) sich immer gerne komplett auf die Tastatur meines Netbooks. Das gab dann immer schöne lange Buchstabenreihen, und einmal hatte sie die Maus(!) ausgeschaltet, und ich hab sich nicht wieder zum Laufen gebracht.

    Die Abhilfe war ein Brett auf dem Schoß, das hat sie einigermaßen akzeptiert. Ich musste nur blitzschnell das Netbook wegziehen, wenn sie ankam…

    Aber das bed spacing beherrschte sie perfekt. Zum Glück nur bei meiner Frau…

  7. #7 Dr. Webbaer
    Dezember 12, 2011

    Dr. W hätte hier eher eher die Arithmetik bemüht und den “maximalen Platz auf dem Bett” vorab definiert, womöglich als Strecke, die unverfügbar gemacht werden soll, wenn eine Katze auf der Fläche liegt…

    D.h. wohl dass man zumindest mit diesem Beispiel nicht direkt warm werden muss, solange man die Tiefe der Überlegung und Herangehensweise nicht komplett verstanden hat.

    Näherungsweises Vorgehen hätte Dr. W bspw. eher bei der Routenplanung vermutet.

    MFG
    Dr. Webbaer

  8. #9 Stefan W.
    Dezember 12, 2011

    Der Artikel gefällt mir recht gut. Ein Applet wäre natürlich nicht schlecht, mit ausgelosten Startpositionen, schrittweisem Blättern durch die Generationen oder als Animation, Anzahl Katzen und Ablaufgeschwindigkeit einstellbar.

    Nicht klar wird im Beispiel, wie man eine Fitnessfunktion haben kann, die die Güte eines Individuums bestimmt, ohne aus der Funktion das Optimum schlicht abzuleiten – sicherlich weil es ein didaktisch einfaches Beispiel werden sollte. Hier müßte man wohl eher ein vermutlich NP-vollständiges Problem auswählen.

  9. #10 Marcus Frenkel
    Dezember 12, 2011

    @Stefan W.
    Ja, ein interaktives Beispiel wäre wohl besser, aber das würde wieder so lange dauern, bis man es programmiert hat. Vielleicht am Ende dieser kurzen Serie, mal sehen.

    Zur Fitness-Funktion:

    bei der Lösung realer Probleme weiß man in der Regel auch nicht, wie die beste Lösung aussieht, kann aber die Güte der Individuen trotzdem meist auf die ein oder andere Art berechnen oder wenigstens schätzen

    Die Knackpunkte sind hier “auf die ein oder andere Art” und vor allem “schätzen”. Die genaue Berechnung der Güte ist in der Tat extrem Problemabhängig; man beötigt nicht einmal NP-vollständige Probleme, um eine “bessere” Fitnessfunktion zu demonstrieren, aber ja, ich habe aus didaktischen Gründen dieses Beispiel genommen, es gibt mit Sicherheit bessere zur Diskussion der Fitnessfunktion. Aber die ist ja sowieso nochmal ein ganz eigenes Thema, mit dem man Stunden zubringen kann…