Was evolutionäre Algorithmen überhaupt sind und wie sie funktionieren, haben wir in den letzten beiden Artikeln besprochen. Das Problem mit der bisherigen Erklärung von evolutionären Algorithmen ist jedoch, dass sie sehr problemgebunden sind; für jedes zu lösende Problem muss ein neues Programm geschrieben werden, da insbesondere die Mutation und Rekombination von den jeweiligen Eigenschaften der Individuen – der Lösungskandidaten – abhängen. Dass dies eleganter zu lösen ist, habe ich ja schon das letzte Mal angedeutet. Heute möchte ich nun auch darlegen, wie sich das bewerkstelligen lässt.

Rekapitulieren wir noch einmal das Problem. Um die Eigenschaften eines Individuums zu mutieren, muss natürlich jede einzelne Eigenschaft bekannt und zudem vorgegeben sein, wie und vor allem in welchem Rahmen sie geändert werden darf. Auch für die Rekombination – die Verschmelzung der Eigenschaften zweier Individuen zu einem Kind – müssen natürlich sämtliche Eigenschaften der Individuen bekannt sein. Prinzipiell ist das natürlich kein Problem, führt jedoch dazu, dass ein einmal geschriebenes Programm nur zur Lösung exakt des Problems geeignet ist, für welches es entworfen wurde. Hinzu kommt, dass die Rekombination einzelner Eigenschaften zu einer insgesamt geringeren Variabilität zwischen den einzelnen Generationen von Individuen führt. Denken wir etwa an das Beispiel aus dem letzten Artikel: ein Individuum bestand bestand dort aus jeweils 2 Eigenschaften – der vertikalen und der horizontalen Position -, deren Rekombination nur zu ganz bestimmten Kindern führen konnte, wobei pro Elternpaar jeweils nur 2 verschiedene Kinder überhaupt möglich waren. Mit steigender Anzahl von Eigenschaften würde übrigens auch der Programmieraufwand immer weiter ansteigen, da die Funktionen zum Mutieren und Rekombinieren immer mehr Eigenschaften beachten müssten. Ein Ansatz, der sowohl allgemeingültig (und damit problemunabhängig) ist und auch problemlos auf “größere” Individuen angewandt werden kann, wäre also von Vorteil.

i-6d1fed853021397b133e70249f869c31-DNA.png

Zur Lösung der genannten Problematik(en) haben sich schlaue Informatiker einmal mehr in der Natur umgeschaut und von dort ein “Verfahren” übernommen, welches auch passenderweise bereits die Grundlage für die Evolution liefert: die Genetik. Wie wir alle wissen, werden die Erbinformationen eines jeden Lebewesens durch die DNA gespeichert. Die DNA ist – vereinfacht gesagt – eine Kette, bestehend aus den Nukleinbasen Adenin, Thymin, Cytosin und Guanin, in welcher durch die sequentielle Anordnung der vier Basen Informationen codiert werden (siehe Bild rechts, via Wikipedia). Diese Informationen bestimmen zu einem großen Teil, wie das Lebewesen später aussieht und sich verhält; die DNA bildet somit den Genotyp – die Gesamtheit der Gene – eines Lebewesens und codiert seinen Phänotyp, sein Erscheinungsbild. Denkt man aber einmal genauer darüber nach, so stellt die DNA nichts anderes als eine Kette von Werten dar, wobei jeweils 4 Werte für jede Position in der Kette zur Verfügung stehen. Die DNA ähnelt damit einer einfachen Bitkette, nur dass bei letzterer eben für jede Position nur 2 Werte – 0 und 1 – möglich sind. Und genau hier setzen die evolutionären Algorithmen an.

Die Idee ist relativ einfach: anstatt ein Individuum durch seine konkreten Eigenschaften – seinen Phänotyp – zu beschreiben, werden diese Eigenschaften in Form einer Bitkette codiert. Im Kontext unseres Beispiels aus dem letzten Artikel (wer sich nicht erinnert, möge noch einmal nachlesen) würde das bedeuten, dass die beiden Positionen (die vertikale und die horizontale) einfach durch Bitketten repräsentiert und aneinandergereiht werden. Nehmen wir an, ein Individuum hat die Position (12,7) und die möglichen Positionen befinden sich im Intervall (0,0) bis (15,15); es reichen also 4 Bit aus, um eine Komponente der Position zu beschreiben (wir erinnern uns). Dual codiert erhalten wir damit die Position (1100,0111); in einer einzigen Bitkette zusammengefasst können wir also durch die Kette 11000111 das Individuum beschreiben, welches an Position (12,7) liegt. Diese codierte Bitkette wollen wir – analog zur Genetik – als Genom bezeichnen.

1 / 2 / 3 / Auf einer Seite lesen

Kommentare (11)

  1. #1 Dr. Weihnachtswebbaer
    Dezember 21, 2011

    Mit dem hier beschriebenen Verfahren ist es also möglich, einen einmal programmierten evolutionären Algorithmus auf jedes beliebige Problem anwenden zu können.

    Rein philosophisch angemerkt: Alleslöser haben die Eigenschaft nichts zu lösen, hier auch erkennbar an der sog. Fitnessfunktion, die die Problemspezifität kapseln soll.

  2. #2 Engywuck
    Dezember 21, 2011

    Sorry, Wb, aber hier liegst du falsch.
    Der Vorteil an den “Alleslösern” liegt in diesem Fall darin, dass man nicht für jeden Fall *alles* neu schreiben muss, sondern “nur” noch die Fitnessfunktion, sowie evtl. ein, zwei Parameter (variable/feste Genomlänge, welche Arten Crossover…).
    Den ganzen restlichen lästigen Schmodder (wie *genau* wird vererbt oder mutiert), der im Katzenbeispiel schon bei Berücksichtigung auch nur einer dritten Dimension komplett neu hätte programmiert werden müssen kann man nun dank “Genom” in eine Bibliothek auslagern, die dann evtl. sogar hochoptimiert (z.B. in Assembler oder GPGPU) werden kann.

    Nebenbei auch nicht wirklich anders als beim biologischen Genom: *wie* kopiert und in Eiweiße umgesetzt wird ist quasi eine uralte, hochspezialisierte Bibliothek. Das einzige was sich wirklich ändert und zwischen Individuen wie Arten unterscheidet ist der Inhalt des Genoms. Die Fitnessfunktion ist IRL natürlich hochvariabel und unter anderem von allen anderen derzeit lebenden oder (kürzlich) verstorbenen Genomträgern und deren Vorgeschichte abhängig. Aber im Prinzip ist das was real stattfindet auch “nur” eine enorm gigantisch komplexere Version des simplifizierten Genom – Library zum kopieren/mutieren – Fitnessfunktion im Artikel.

  3. #3 Marcus Frenkel
    Dezember 21, 2011

    @Engywuck
    Danke für die Ausführung, ich hätte es nicht besser sagen können.
    Ich habe trotzdem den Text ein klein wenig angepasst, um Missverständnissen vorzubeugen.

  4. #4 Dr. Weihnachtswebbaer
    Dezember 21, 2011

    @Engywuck
    Wurde schon halbwegs korrekt hier so verstanden, war wohl ein wenig zynisch gemeint; das ganze Vorhaben ist ja der KI oder AI zuzuordnen und dort ist man ja eher mäßig erfolgreich.
    Die Problemspezifität bleibt trotzdem in der “Fitness”.

    MFG
    Dr. Wwb (der zudem noch das hier in den Ohren hat)

  5. #5 Physiker
    Dezember 22, 2011

    Vielen Dank für diese hervorragend erklärte Artikel-Serie. Ich bin schon ganz gespannt auf den nächsten Teil.
    Wenn ich mir etwas wünschen darf (es ist ja kurz vor Weihnachten), dann würde es mich freuen, etwas konkreter darüber zu lesen, welche Regeln (viel/wenig Mutation, Populationsgrösse, etc.) erfahrungsgemäss zu optimalen Ergebnissen führen. Denn offensichtlich gibt es bei evolutionären Algorithmen besonders viele Parameter, die man frei wählen kann (und das ist eigentlich sehr unbefriedigend). Ausserdem würde mich ein Vergleich mit “konventionellen” Algorithmen interessieren und/oder die Abgrenzung, welche Probleme sich z.B. nicht/ganz schlecht mit den üblichen/einfachen Optimierungsverfahren wie z.B. Simmulated Annealing lösen lassen. Um beim Simmulated Annealing zu bleiben: Dort ist es nämlich bekannt, wie die Parameter (z.B. Verlauf der Temperatur) zu wählen sind um brauchbare oder optimale Ergebnisse zu erziehlen. Meinem Vorurteil nach, sind konventionelle Optimierungsalgorithmen den evolutionären praktisch immer überlegen.

  6. #6 Marcus Frenkel
    Dezember 22, 2011

    @Physiker
    Wünschen darf man immer, nicht nur zu Weihnachten. 😉

    Zum Thema Parameterwahl gibt es im nächsten Artikel etwas, wenn nämlich die Problematik der lokalen Optima behandelt wird. Aber gleich zur Warnung: eine den Wunsch 100%ig befriedigende Antwort wird es wohl nicht geben, da gerade die Wahl der Parameter die Schwierigkeit bei den evolutionären Algorithmen ist. Man kann allerdings einige allgemeine Aussagen zur Parameterwahl treffen – das mache ich das nächste mal dann.

    Den Unterschied der EA zur simulierten Abkühlung (SA) kann ich gleich hier erklären. Beide Algorithmen sind sich eigentlich ziemlich ähnlich; der Unterschied besteht darin, dass SA lediglich ein einzelnes Individuum betrachtet. Man kann sagen, dass die SA ein EA mit einer Populationsgröße von 1 ist. Hinzu kommt, dass die SA im Gegensatz zu den EA (das hängt aber von der Implementierung ab) in den Mutationen etwas zielgerichteter ist, da bei den EA rein zufällig mutiert wird (bei geeigneter Wahl des Selektionsoperators entfällt dieses Problem aber). Und im Gegensatz zur SA decken EA ein größeres Gebiet bei der Suche ab. Dafür ist die SA im Allgemeinen der “schnellere” Algorithmus, heißt, bei gleicher, “kurzer” Zeit für beide Algorithmen wird mit der SA eine bessere Lösung gefunden. Hat man mehr Zeit zur Verfügung, werden meist die EA besser. Das hängt aber auch immer etwas vom Problem ab.

  7. #7 Engywuck
    Dezember 23, 2011

    welche Regeln (viel/wenig Mutation, Populationsgrösse, etc.) […] zu optimalen Ergebnissen führen.

    Das ist doch ganz einfach herauszufinden: Du nimmst deine Problemstellung, die du als evolutionären Algorithmus samt Fitnessfunktion etc erstellt hast und erstellst zusätzich ein weiteres Genom, das alle variablen Parameter codiert. Als Fitnessfunktion dieses Genoms nimmst du einfach die Fitness der Poulationen des ursprünglichen Problems (wenn du ganz gut drauf bist erzeugst du ein weiteres Genom, das dann noch entscheidet, ob durchschnittliche oder beste oder Median oder oder oder heranzuziehen ist und nach wievielen Generationen nachgeschaut wird ;-)).
    Dann lässt du einfach das ganze sich evolutionär entwickeln und voila, schon hast du die idealen Parameter dieses Problems *und* gleichzeitig noch das Ursprungsproblem gelöst.
    Ja, das ist etwas aufwendig, aber doch wohl die Sache wert, oder?

    😉

  8. #8 Marcus Frenkel
    Dezember 23, 2011

    @Engywuck
    So aufwändig ist das gar nicht. Wenn ich mich gerade richtig erinnere, gibt es sogar Verfahren, die diesem Ansatz folgen. Zwar nicht ganz so, dass die Parameter auch evolutionär bestimmt werden, aber immerhin durch einen anderen Algorithmus entsprechend der aktuellen Entwicklung in den Generationen angepasst werden.

  9. #9 Engywuck
    Dezember 23, 2011

    durch nen anderen Algorithmus angepasst… wie langweilig 😉
    Und wie wurden die Parameter des anderen Algorithmus bestimmt? 😀

  10. #10 Dr. Weihnachtswebbaer
    Dezember 23, 2011

    Durch die “Fitness” eben, btw: morgen ist Heilige Nacht, Weihnachten kommt oder droht, je nach Aufstellung, Dr. Weihnachtswebbaer wünscht auch hier gerne:
    Frohe Weihnachtstage!

    Rudolph schon ganz spitz,
    MFG
    Dr. Weihnachtswebbaer

  11. #11 Engywuck
    Dezember 25, 2011

    zumThema “Evolution” halbwegs passend ein Weihnachtsgruß, den ich heute gehört habe:

    “Vogelgrippe, Schweinepest – nur das Beste für das Fest”

    In diesem Sinne…