Wenden wir nun den Rekombinationsalgorithmus auf unsere selektierten Positionen des Katzenproblems an. Eine Position hat dabei in der Regel lediglich zwei Eigenschaften, nämlich die vertikale und die horizontale Position auf dem Bett. Die Rekombination zweier Eltern soll also immer so geschehen, dass vom ersten Elter die vertikale und vom zweiten Elter die horizontale Position genommen und zu einem neuen Individuum vermischt werden. Wir erhalten damit aus den alten Individuen (grau, diese werden nach diesem Schritt verworfen) die neuen (schwarz), wobei einige der Rekombinationen zweier Eltern mit ihrem Ergebnis durch Pfeile gekennzeichnet sind. Eine Güte wurde für die neuen Kinder jetzt noch nicht eingetragen, da sie noch nicht berechnet wurde (wir sehen aber schon, dass einige der neu generierten Individuen besser sind als ihre Eltern); wie man sieht, stehen die im vorherigen Schritt nicht selektierten Individuen gar nicht mehr zur Diskussion:

i-c6cd5470e67c14f4dea7005d046ea64b-Bett2.gif

 

Mutation

Damit bleibt noch ein letzter Schritt zu klären: die Mutation. Sie sorgt dafür, dass in den vorhandenen Pool an Eigenschaften (den Genpool) etwas Bewegung kommt und neue Eigenschaften entstehen. Ohne die Mutation würde sich der evolutionäre Algorithmus nämlich im Kreis drehen, da immer nur Individuen mit den gleichen Eigenschaften entstehen würden.

Die Mutation an sich ist relativ simpel: jedes der bei der Rekombination entstandenen Individuen wird hergenommen und eine, einige oder alle seiner Eigenschaften zufällig verändert. Die Stärke der Mutation ist dabei oft ein einstellbarer Parameter, da je nach Problem stärkere oder schwächere Mutationen von Vorteil sein können. Auch hier existiert wie bei der Rekombination ein Verfahren, welches unabhängig von den tatsächlichen Eigenschaften der Individuen (also für alle denkbaren Individuen aller möglichen Probleme) eine Mutation durchführen kann und welches ich im nächsten Artikel vorstellen werde. Der Pseudocode für die Mutation sieht denkbar einfach aus:

(1)  mutate individuals: g ∈ TnTn:
(2)    for all t ∈ g:
(3)      t ← mutate t randomly
(4)    return g

Bei unserem Katzenproblem sind die mutierbaren Eigenschaften natürlich wieder die vertikale und die horizontale Position auf dem Bett. Jedes der bei der Rekombination entstandenen Individuen wird nun mutiert, also ein klein wenig auf dem Bett in eine zufällige Richtung verschoben (da wir ja, wie abgesprochen, gar nicht wissen, wo die Mitte ist, können wir auch nicht einfach pauschal “zur Mitte hin” schieben). Bildlich ausgedrückt sieht das so aus (zugegeben, es wirkt etwas chaotisch, aber die Intention sollte erkennbar sein); grau sind die “alten” (rekombinierten) Individuen, der Pfeil zeigt die Schieberichtung an und die schwarzen Kreise markieren die Individuen, welche die nächste Generation bilden werden.

i-1a4317622e522e9cf827871e338e20ba-Bett3.gif

 

Abschluss

Der Algorithmus würde nun von vorne beginnen und aus den neu erstellten Individuen wiederum eine geeignete Auswahl treffen, diese rekombinieren und mutieren – so lange, bis ein genügend gutes Individuum gefunden wurde. “Genügend gut” liegt hier natürlich immer im Auge des Problemlösers. Ist die Güte der besten Lösung bekannt (im Katzenbeispiel etwa die Entfernung zur Mitte), kann so lange gerechnet werden, bis ein Individuum mit genau dieser Güte oder einer um nicht mehr als X% abweichenden Güte gefunden wurde. Ist die beste Güte dagegen nicht bekannt (was bei vielen Optimierungsproblemen der Fall ist), kann eine bestimmte Anzahl von zu berechnenden Generationen vorgegeben werden, in der Hoffnung, dass nach dieser Zeit bereits ein relativ guter Lösungskandidat gefunden wurde. Alternativ kann das Abbruchkriterium auch sein, dass sich über eine bestimmte Anzahl von Generationen hinweg der durchschnittliche Gütewert einer Generation nicht mehr wesentlich ändert; das kann nämlich auch passieren, dann ist man in einem sogenannten lokalen Optimum gelandet (was das ist, besprechen wir auch ein andermal).

Evolutionäre Algorithmen haben die Eigenschaft, dass für ansonsten schwierig zu berechnende Probleme auf relativ einfache Art und Weise eine gute Lösung gesucht werden kann. Ihr größter Vorteil ist hierbei vor allem die Geschwindigkeit der Berechnung; die traditionelle Suche nach einer guten Lösung eines schwierigen Problems verschlingt meist so viel Zeit, dass sie nicht praktikabel ist. Ein evolutionärer Algorithmus bietet hier einen Ausweg, der zwar nicht zwangsläufig die beste Lösung findet, aber zumindest eine hinreichend gute, und das in annehmbarer Zeit. Betrachten wir zum Beispiel das Katzenproblem; innerhalb einer einzigen Generation wurden aus diesen zufällig generierten Lösungskandidaten

1 / 2 / 3 / 4

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…