Jump to content






Photo
- - - - -

Evolutionsalgorithmen: Basics

Posted by Mythos , 26. August 2012 · 1,331 views

evo evolutionsalgorithmen basics
Wie versprochen hier ein bissl was grundlegendes zu Evolutionsalgorithmen.

Gleich vorweg: Ich hab keine "Ausbildung" in dem Bereich. Alles was ich hier schreibe hab ich mir selbst erarbeitet. Es kann also leicht sein das meine Definitionen und Vorgehensweisen von den "offiziellen" abweichen. Das hier ist also die "Evolutionstheorie von mythos" Posted Image

Evolution at its best
Wenn man Evolutionsalgorithmen verstehen will, muss man zuerst die Evolution als solches verstehen. Jeder hat den Begriff schon gehört, aber ich bin mir nicht sicher ob jeder weiß wie die Evolution wirklich funktioniert.

Evolution basiert auf 2 Grundpfeilern: Überproduktion und natürliche Auslese
Überproduktion
Betrachtet man rein die "Geburtenraten" in der Natur, so gäbe es ein derart massives Wachstum der Populationen, das in wenigen Generationen die Erde zu klein wäre. (Sehen wir ja mit den Menschen zurzeit). Es kommen also viel mehr Exemplare einer Spezies auf die Welt, als "nötig" wären.

natürliche Auslese
Die "Evolution" ist kein hochintelligenter Apparat, der die Gene einer Spezies analysiert und entsprechend verbessert. Wenn ein neues Exemplar der Spezies gezeugt wird, setzen sich die Gene beider Seiten nicht zusammen und diskutieren welches das bessere ist. Die Gene der beiden Eltern werden einfach "zufällig" gemischt. Manche mutieren sogar zufällig und es kommt einfach eine neue Kombination raus. Ob diese Kombination jetzt gut war entscheidet die Umgebung durch die natürlich Auslese.
Ein Gnu das nicht laufen kann wird schnell Opfer eines Löwen -> die Gene dieses Gnu werden sich nicht weiter verbreiten.
Wenn es nicht bei der Herde bleibt sondern alleine rumläuft wird es auch schnell gefressen -> Gene verbreiten sich nicht.
Kann es gut laufen und bleibt in der Herde überlebt es lange genug seine Gene weiterzugeben. Dadurch kommen viel mehr Gnus mit guten Beinen und Herdenzusammenhalt auf die Welt. Die "Evolution" hat die schlechten Beine und Einzelgängertum aussortiert.

Evolution in der Praxis
Ein kleines Beispiel weil ich es so toll finde ;) (Keine Ahnung ob es 100% korrekt ist, veranschaulicht das ganze aber gut):
Birkenfalter sind Schmetterlinge die bevorzugt auf Birken sitzen. Normalerweise sind sie weiß, weil sie dadurch auf den weißen Birken gut getarnt sind. Jetzt ist es passiert das durch äußere Umwelteinflüsse die Birken sich dunkel gefärbt haben. Innerhalb von 2 Generation waren alle Birkenfalter schwarz. Nicht weil die "Evolution" gesehen hat das schwarze Falter jetzt besser sind. Schwarze Birkenfalter sind zuvor genauso (durch die zufälligen Mutationen) auf die Welt gekommen. Sie wurden nur immer schnell gefressen weil sie keine Tarnung hatten. Mit den dunklen Birken, hat sich das umgedreht und die schwarzen Falter überleben und pflanzen sich fort, während die Weißen gefressen werden.

Evolutionsalgorithmen vs. klassische Softwareentwicklung
Jetzt muss man das Ganze nur noch auf die Software übertragen. Ein "normales" Programm unterscheidet sich aber doch deutlich von einem lebenden Organismus. Vor allem weil ein Programm für einen konkreten Zweck geschrieben wird. Optimiert für diese Umgebungsbedingungen. Es implementiert normalerweise einen konkreten Lösungsweg, der lt. Entwickler der Beste für dieses Problem ist. Hier gibt es keine Überproduktion und keine Auslese.Es gibt eine konkrete Ausprägung der Spezies und aus.

Solange die Umgebung gleich bleibt, und der Entwickler zu Beginn wirklich den besten Lösungsweg kennt ist das Programm auch optimal. Da wäre Evolution fehl am Platz. Wer will schon einen Taschenrechner der immer wieder mal ein anderes Ergebnis liefert und schaut obs jetzt näher an der Lösung ist.

Hat man aber ein Problem mit veränderlicher Umgebung, und dessen Lösung nicht so leicht analysierbar ist, dann ist das Prinzip der Evolution sehr hilfreich. Bleibt die Frage wie ein Evolutionsalgorithmus funktioniert.

Der generische Evolutionsalgorithmus
Wir brauchen als erstes einmal Gene, die man verbessern kann. Also Parameter für unseren Algorithmus. Das müssen aber nicht nur Parameter im Sinn von Zahlen sein. Hier können/sollen auch ganze Teile der Logik als Parameter vorkommen. Es kann also sein das es nicht nur den Parameter "Stärke der Beine" gibt sondern auch einen "Habe ich Beine?". Bzw. Tradingrelevanter: "SL Entfernung" oder "Gibt es überhaupt einen SL?". Oder "Welche Einstiegslogik wird verwendet?".

Dann braucht es die natürliche Auslese. Oder technischer ausgedrückt: Wir benötigen eine Bewertungsmöglichkeit der einzelnen Genkombinationen. In der Natur erhält ein Tier eine "hohe Bewertung" wenn es lange überlebt. In der Softwareentwicklung gibt es eben eine hohe Bewertung je besser der resultierende Algorithmus das Problem löst.

Kommen wir zur Überproduktion: Jene Genkombinationen, welche die besten Bewertungen haben, werden miteinander "gekreuzt" und teils mutiert. Diese Kreuzung und Mutation muss dermaßen ablaufen das wieder ein lauffähiger Algorithmus entsteht (zumindest meistens, Fehlgeburten gibt es in der Natur auch häufig). Je besser die Bewertung einer Kombination, desto öfter wird sie weitergegeben.

Die neue Generation wird nun erneut bewertet und die besten Genkombinationen dürfen sich wieder fortpflanzen, die schlechten werden aussortiert.

Und fertig ist der Evolutionsalgorithmus. Sofern alles passt hat man nach ein paar (hundert/tausend/keineAhnung) Generationen einen Satz von Algorithmen, die das Problem gut lösen. Das gute daran: es ist keine Blackbox. Man schaut sich die Genkombination an und weiß was der Algo tut. In der laufenden Praxis kann man damit dann natürlich Algorithmus ständig an geänderte Umgebungsbedingungen anpassen. Es gibt einfach regelmäßig Fortpflanzungen und die Algos werden laufend bewertet. Schlechte Algos sterben aus, gute dürfen sich fortpflanzen... ein ewiger Kreislauf.

Im Gegensatz zur klassischen Entwicklung hat man damit zwar immer einen kleinen Teil von Algos die nicht optimal laufen, aber dafür ist man flexibel und das System (Softwaretechnisch) findet selbstständig funktionierende Algos und passt sich somit automatisch an eine veränderte Umgebung an.

Soweit die Theorie. Zur Anwendung im konkreten Projekt kommen wir im nächsten Eintrag.

thx for reading.

  • 1



Sehr interessant

Lutz
    • 0
  • Report

December 2021

M T W T F S S
  12 3 45
6789101112
13141516171819
20212223242526
2728293031  

Recent Comments

Recent Entries

0 user(s) viewing

0 members, 0 guests, 0 anonymous users

Categories

Latest Visitors

  • Photo
    eurix
    14. Apr 2017 - 21:50 Uhr
  • Photo
    chimbonda
    03. Jul 2016 - 11:49 Uhr
  • Photo
    tompaul
    21. May 2016 - 16:37 Uhr
  • Photo
    fatlemming
    24. Jan 2016 - 17:41 Uhr
  • Photo
    compulsorytrading
    11. Dec 2014 - 09:33 Uhr