So, hier nun endlich – mit einiger Verspätung (ich weiß gar nicht, wie Florian neben der Arbeit noch so produktiv im Blog sein kann) – der vorerst letzte Teil der Reihe zu den evolutionären Algorithmen. Wir erinnern uns: in Teil 1 wurde vorgestellt, was sich überhaupt unter evolutionären Algorithmen vorgestellt werden kann. In Teil 2 wurde dann ihre allgemeine Funktionsweise besprochen und in Teil 3 habe ich vorgestellt, wie mit Hilfe aus der Genetik bekannten Mitteln die Arbeitsweise der Algorithmen verbessert und verallgemeinert werden kann. Zum Abschluss soll es heute nun noch darum gehen, welche Probleme bei der Nutzung von evolutionären Algorithmen auftreten können und wie sie sich – zumindest teilweise – vermeiden lassen.

Das generelle Problem evolutionärer Algorithmen (im weiteren auch einfach als EA bezeichnet) ist, dass sie nicht wirklich zielgerichtet arbeiten; nicht zielgerichtet heißt, dass der “Wert” der optimalen Lösung meist nicht bekannt ist und daher auch nicht gezielt danach gesucht werden kann. Es kann lediglich gesagt werden, welche von 2 möglichen Lösungen für ein Problem die bessere ist. Die eigentliche Problemlösung besteht also aus der Suche nach einer möglichst optimalen Lösung (daher der Name Optimierungsproblem) und nicht aus der Suche nach der optimalen Lösung (weil sie eben meist nicht bekannt ist).

Das ganze lässt sich auch grafisch sehr gut veranschaulichen. Ein Optimierungsproblem besitzt eine (endliche oder unendliche, das spielt keine Rolle) Menge an Lösungen (Individuen), wobei jede Lösung einen bestimmten Fitness-Wert hat. Zudem besitzt der Phänotyp – das Erscheinungsbild – der Lösungen eine bestimmt Anzahl von Parametern (im Katzenbeispiel waren es etwa 2: die x- und die y-Koordinate auf dem Bett). Bei nicht allzu vielen Parametern (im Grunde nur bei 1 oder 2) kann man zur Verdeutlichung der Problematik ein Diagramm anlegen, welches für jede Parameterwahl die Fitness anzeigt

Nehmen wir zum Einstieg das Katzenbeispiel; in diesem Fall besitzt der Phänotyp 2 Parameter (die x- und die y-Koordinate), stellt also ein zweidimensionales Problem dar. Zur Darstellung im Diagramm bietet sich hier zum Beispiel die Nutzung von Graustufen an; weiße Bereiche stellen “gute”, im Katzenbeispiel also zentrumsnahe Positionen dar, schwarze Bereiche eher “schlechte Positionen, also solche, die weiter Weg vom Zentrum sind. Für das Katzenbeispiel ergibt sich hier ein relativ homogenes Bild mit einem weißen Zentrum und gleichmäßig dunkler werdenden Bereichen:

i-4a3db2e8109aed53a8b8338fc6c28deb-01.png

 

Eine Anmerkung noch, bevor es weitergeht: wenn wir nicht nur auf 3 Dimensionen beschränkt wären, ließen sich auch Probleme mit mehr Parametern darstellen; so beschränken wir im Folgenden aber auf Grund physikalischer Gesetzmäßigkeiten auf 1 und 2 Dimensionen – alles gesagt ist aber natürlich ebenso auf komplexere Probleme anwendbar!

Jetzt ist das Katzenbeispiel relativ simpel, da der Kurvenverlauf für die Fitnesswerte relativ eindeutig ist: von jedem Punkt des Koordinatensystems aus werden die Werte zur Mitte hin besser und erreichen genau in der Mitte ihr Optimum. Reale, durch evolutionäre Algorithmen lösbare und gelöste Probleme haben diesen Luxus nicht. Ein (beliebiges) anderes Problem mit 2 Parametern könnte etwa das folgende Fitnessdiagramm aufweisen (welches natürlich so meist überhaupt nicht bekannt ist – wir tun nur einmal so, als würden wir es kennen):

i-62ced1e261feb87a5b8ae6b4484f0058-02.png

 

Im Bild erkennen wir, dass neben dem “besten” Optimum links oben noch ein “weniger gutes” Optimum rechts unten existiert (für die Sprachpedanten unter den Lesern: ich weiß, dass es kein “bestes” oder “weniger gutes” Optimum geben kann – die Begriffe sind hier eher umgangssprachlich gemeint; man möge mir verzeihen). Das Optimum oben links wollen wir im Folgenden als globales Optimum bezeichnen, da es global (also im ganzen Diagramm) das beste ist; das Optimum rechts unten ist dementsprechend ein lokales Optimum, da es lokal (unmittelbar in seiner Umgebung) den besten Wert darstellt (das globale Optimum ist somit auch gleichzeitig ein lokales). Gängige Probleme der Realität haben nicht nur 2 lokale Optima, sondern viel viel mehr, und leider weiß man in der Regel nicht, wo denn diese lokalen Optima liegen.

1 / 2 / 3 / Auf einer Seite lesen

Kommentare (12)

  1. #1 Andreas
    Januar 22, 2012

    Interessante Reihe, lass dich doch mal verpodcasten.

  2. #2 BreitSide
    Januar 22, 2012

    xxx

  3. #3 Franz
    Januar 22, 2012

    Die Farben in den Bildern sind ziemlich ungünstig gewählt. Da kriegt man ja Augenkrebs, wenn man zu lange drauf guckt.

  4. #4 Marcus Frenkel
    Januar 22, 2012

    @Franz
    Ja, ich weiß. Ich habe die Bilder mal durch andere mit Graustufen ersetzt – vielleicht ist das ja besser.

  5. #5 Phyiker
    Januar 23, 2012

    Danke!
    Sehr interessante Artikelreihe – werd’ demnächst mal so einen EA programmieren.

  6. #6 kereng
    Januar 23, 2012

    In diesem Zusammenhang muss ich einfach http://boxcar2d.com/ verlinken. Das wurde doch noch nicht erwähnt, oder?
    Wenn dort mit ungünstig angebrachten Rädern erste Erfolge erzielt wurden, befindet man sich auch auf einem lokalen Optimum und wirklich gute Rennautos haben kaum noch eine Chance. Unter Umständen hilft es dann, die Mutationsrate raufzusetzen.

  7. #7 Marcus Frenkel
    Januar 23, 2012

    @Physiker
    Ich bin gespannt, ob es klappt. 🙂

    @kereng
    Ah, an die Box Cars habe ich gar nicht mehr gedacht. Schönes Beispiel für einen EA, vielen Dank fürs Posten.
    Allerdings würde ich vermuten, dass die Box Cars keine Rekombination benutzen, was ich ein wenig schade finde – da hätte man bestimmt noch mehr herausholen können.

  8. #8 Silly Human
    Januar 24, 2012

    Sehr interessant, danke.

  9. #9 kereng
    Januar 24, 2012

    Doch, die Boxcars machen Rekombination, und zwar den uns vertrauten Spezialfall mit zwei Elternteilen. Der Erfinder nennt es hier “Crossover”:
    http://boxcar2d.com/about.html#crossover

  10. #10 Marcus Frenkel
    Januar 24, 2012

    Tatsächlich. Wunderlich. Von der Verteilung und dem Aussehen der Nachkommen her hätte ich gesagt, dass keine Rekombination stattfindet, da die Nachkommen immer ähnlich ihren Eltern an der gleichen Position waren und sich die Population nicht gemeinschaftlich in eine bestimmte Richtung bewegt hat. So kann man sich irren.

  11. #11 Man könnte...
    April 11, 2012

    … doch auch einen EA für den EA schreiben. Der die Parameter variiert und so einen deutlich größeren Rahmen ausfüllt. Allerdings hat man dann das Problem “nur” auf eine andere Ebene verschoben. Dennoch denke ich, dass das erfolgreich sein könnte. Spätestens bei der unendlichen Ebene, sollte gute Chance da sein, das globale Optimum zu finden 😉

  12. #12 ich hatte...
    April 20, 2012

    @Man_könnte Lustig! Genau die selbe Idee kam mir auch beim Lesen.
    Einfach das Problem der Parameterwahl mit einem evolutionären Algorithmus lösen 🙂