Im Allgemeinen kann man sagen, dass eher Individuen ausgewählt werden sollen, welche “besser”, also näher an der gewünschten Lösung dran sind. Um ein Individuum nach seiner Güte zu beurteilen, wird dazu die sogenannte Fitnessfunktion (meist mit f  bezeichnet) benutzt. Der Wortbestandteil “Funktion” entspricht hier ganz der mathematischen Bedeutung: die Fitnessfunktion ist eine mathematische Funktion, welche ein Individuum als Argument verlangt, dieses intern bewertet und seine Güte als einen Zahlenwert zurückgibt. Dieser Zahlenwert kann je nach Problem in einem begrenzten oder einem offenen Intervall liegen; ob die kleineren Werte “besser” sind oder die größeren, hängt auch vom Problem ab. Unabhängig davon aber können mit Hilfe der Fitnessfunktion sämtliche Individuen in der Generation bewertet und ihrer Güte nach sortiert werden – und das wird in der Regel auch zuerst gemacht.

Für die Selektion gibt es nun die verschiedensten Möglichkeiten. So können zum Beispiel streng die besten X Individuen für die weitere Rekombination ausgewählt werden, es können unter den besten X zufällig Individuen ausgewählt werden (auch mehrfach und damit auch mehr als X – ein Individuum kann sich ja wie ein Lebewesen auch mehrfach paaren) und es ist auch denkbar, unter allen Individuen beliebig zu wählen, wobei die Wahlwahrscheinlichkeit X eines Individuums umso höher ist, je höher seine Güte ist. Weitere Auswahlverfahren sind natürlich möglich; in jedem Fall wird man aber eine Menge von Individuen für die Rekombination erhalten, deren durchschnittliche Güte besser als der Durchschnitt ist – der Evolution wird damit eine Richtung gegeben. Je strenger übrigens der Parameter X gewählt wird, desto stärker ist der Selektionsdruck; im extremsten Fall wird nur noch das beste Individuum zur Rekombination ausgewählt (warum das keine gute Idee ist, sehen wir aber ein andermal). Schreiben wir die Selektion einmal im Pseudocode auf (f ist unsere Fitnessfunktion):

(1)  select individuals: g ∈ TnTn:
(2)    for all t ∈ g:
(3)      t.fitness ← f(t)
(4)    g’ ∈ Tn, g’ ← {}
(5)    while not enough elements in g’:
(6)       t ∈ T
(7)       t ← select element from g according to strategy
(7)       g’ ←  g’ ∪ {t}
(8)   return g’

Angewendet auf unser Katzenproblem haben wir als Fitnessfunktion natürlich diejenige Funktion, welche die Entfernung von einer Position zur Bettmitte bestimmt; niedrigere Zahlen sind also besser, die 0 wäre das Optimum. Wir nehmen an, dass die Funktion das auf magische Art und Weise bestimmt, da wir ja – wie abgesprochen – nicht wissen, wo die Mitte ist (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). Hier ein kleines Beispielbild mit einigen möglichen (zufällig generierten) Lösungskandidaten, ihrer Güte (geschätzte Entfernung zur Mitte) und (schwarz markiert) denjenigen Individuen, die für die Rekombination nach einer nicht näher benannten Strategie ausgewählt wurden (der schwarze Punkt in der Mitte ist, nun, die Mitte):

i-1e5dd3ae0b5d1b4a94abb9c6348abe41-Bett.gif

 

Rekombination

Wurde durch Selektion eine Menge von geeigneten Individuen ausgewählt, können wir nun daran gehen, diese miteinander zu (re-)kombinieren, sie miteinander zu kreuzen. Dazu wählt man jeweils zwei Individuen zufällig aus der selektierten Menge aus (oder selektiert, wie bereits erwähnt, erst an dieser Stelle 2 Individuen aus der Gesamtmenge) und vermischt ihre Eigenschaften miteinander, ganz so, wie es bei der natürlichen Fortpflanzung geschieht (das ist jetzt natürlich etwas vereinfachend dargestellt, aber als Analogie geeignet). Jedes Individuum hat in der Regel eine feste Menge an Eigenschaften, genau wie ein Lebewesen (zum Beispiel Haar- oder Fellfarbe, Körpergröße, Blütenblattfarbe und ähnliches) und genau wie in der realen Welt erbt ein erzeugtes Individuum eine Mischung der Eigenschaften seiner Eltern (an etwaig mitlesende Biologen: dominante und rezessive Vererbung spielen bei evolutionären Algorithmen keine Rolle, da jedes Individuum eher einer Keimzelle entspricht und damit haploid ist). Die Vermischung kann auch auf unterschiedliche Arten erfolgen, etwa, indem jede der möglichen Eigenschaften zufällig von einem der beiden Rekombinationspartner gewählt wird oder indem die erste Hälfte der Eigenschaften vom ersten und die zweite Hälfte vom zweiten Partner übernommen wird. Weitere Strategien sind denkbar und ich werde im nächsten Artikel noch eine Möglichkeit vorstellen, wie jede denkbare Rekombinationsstrategie unabhängig von den Eigenschaften ausgeführt werden kann. Hier soll es erst einmal genügen, wenn wir sagen, dass die Eigenschaften je zweier Individuen zu einem neuen Individuum kombiniert werden, welches dann eine Mischung aus Eigenschaften seiner beiden Eltern besitzt. Im Pseudocode sieht das so aus:

(1)  recombine individuals: g ∈ TnTn:
(2)    g’ ∈ Tn, g’ ← {}
(3)    while not enough elements in g’:
(4)       t, t1, t2 T
(5)       (t1, t2) ← select randomly from g
(6)       t ← recombine t1 and t2 randomly
(7)       g’ ←  g’ ∪ {t}
(8)   return g’

Insgesamt müssen natürlich genügend neue Individuen entstehen, damit die nächste Generation genauso mächtig ist wie die vorherige. Ist sie kleiner, würden irgendwann keine Individuen mehr übrig sein; ist sie größer, würde die Populationsgröße immer weiter zunehmen mit dem Ergebnis, dass irgendwann der Speicher des Computers voll wäre. Übrigens müssen nicht immer genau zwei Individuen miteinander rekombiniert werden; es können natürlich auch mehr sein – zwei hat sich aber als relativ günstige Zahl erwiesen.

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…