[Artikel] Simulierte Evolution

[Luckie]

Simulierte Evolution

Um was geht es dabei? Kurz gesagt geht es darum, dass sich Computerprogramme selber schreiben und verbessern. Sich also entwickeln, sich verbessern und sich der gestellten Aufgabe immer besser "anpassen" bzw. sie immer besser lösen können. Und faszinierend ist, was man damit zum Schluss in der Praxis selber, überraschenderweise oder auch nicht, erleben kann.

Artikel: Simulierte Evolution

[negaH]

Hm das Buch selber kenne ich nicht, weis aber von einer ähnlichen Gechichte. Zu DOS Zeiten gab es ein lustiges Kriegsspiel. In einer simulierten Welt aus Speicherzellen und einem vorgefertigten Set von Maschinenbefehlen war es die Aufgabe der Spieler=Programmierer möglichst effiziente Progrämchens zu coden die diesen Speicher auf eine Weise beackerten das sie sich 1.) vorpflanzten oder bewegten und 2.) Gegnerische Progrämchens dabei vernichteten. Der Programmierer dessen Program als letztes übrig blieb hatte gewonnen.

Zurück zum Thema, bei den EP/GPs sehe ich das große Problem darin

1.) eine Selektierungsfunktion zu definieren, immerhin evolutionieren die EP/GP so wie ich es verstanden haben ohne Aufsicht aus sich selbst heraus. Also ohne konkrete Zielsetzungen.
2.) die Geschwindigkeit/Dauer dieser Evolution und die Größe der notwenigen Population von solchen Programmen.
3.) die Kodierung und Syntax sollte sehr universell sein damit auch ungeahnte Programme rauskommen

Das sind Probleme die enormen Rechenpower benötigen werden. Denn wenn man wirklich kreative Programme erzeugen möchte, Programme wie die die wir jeden Tag erzeugen, dann benötigten wir um Magnituden mehr Speicher und Prozessorpower als das was wir heute haben.


Das Buch was ich damals zur Hand hatte heist:

"Genetische Algorithmen und Evolutionsstrategieen"
Eberhard Schöneberg, Frank Heinzmann, Sven Feddersen
1. Auflage 1994 im Addison-Wesley Verlag
ISBN 3-89319-493-2
481 Seiten stark
enthielt eine 5 Zoll Diskette mit C Sourcen und Programmen
Auf Seite 333 zb. "Auotmatische Erzeugung von Programmen in LSIP".

Sehr zu empfehlen da von den Grundlagen bis zu konkreten Anwendungen alles sehr verständlich beschrieben wird und nicht mit praktischen Beispielen, Diagrammen und Grafiken gegeizt wurde. Nur die DOS Software dürfte heutzutage wohl unmodern geworden sein.

Gruß Hagen

[Go2EITS]

@Danke hagen, für Deine Antwort, interessant, aber das war es nicht. Ich weiss, dass die Programme
über Rechner am Schluss die gesamte Rechenzeit übernahmen. Ich glaube, da war auch jedem Programm eine maximale Rechenzeit zugewiesen gewesen. Trotzdem kam es zum GAU.

Ein wenig habe ich michmit GA damit beschäftigt, ich habe meine Programme so aufgebaut:
a) Lernmodus
b) Aktionsmodus
Es gibt einen Pool mit Funtionen/Proceduren (siehe unten)
Einen Bewerter/Selector
Einen Populationspool/Programmepool

a) Im Lernmodus werden Ergebnisse gesucht/optimiert.

1. Functionen/Proceduren Pool,
die von den Populationen/Programmen aufgerufen werden können. Dabei: Die Überparameter werden in einem bestimmen Bereich akzeptiert. Übersteigt/unterschreitet ein Übergabeparameter den Wertebereich, wird auf dem höchsten/niedigsten erlaubten Wert gesetzt. Und: die Programme rufen per Zufall die Proceduren/Funktionen (d. h. mindestens eine Procedure/Function bis alle) mit zufälligen Werten auf.
Damit kristalisiert sich raus, ob eine Procedur/Funktion im Pool überhaupt Sinn macht. z. B. gleitender Durchschnitt auf Aktienkurse als alleiniges Kauf-/Verkaufskriterium einer Aktie ist
sinnlos und bringt je nach Aktie unterdurchschnittliche Renditen)

2. Bewerter/Selection
Der Bewerter will entweder
a) das Maximum eines Wertes. z.b. Hohe Rendite
b) das Minimum eines Wertes. z. B. Niedrigen Ölverbrauch
c) Ergebnis/Variable in der Nähe eine bestimmten Wertes/Zustandes

Danach richtet sich, welche Populationen/Programme letztendlich 'überleben'.
Diese Populationen speichern Ihre zufällig erzeugten Übergabeparameter und dürfen solange leben
bis eine Population dem Bewerter bessere Ergebisse bringt.

Sonderfälle:
Es gibt Sonderfälle, die bei bestimmten Situationen ausgelöst werden müssen und auf Populationen
aktiv werden, die nur in der Situation aktiv werden. z. B. Notfälle/Extremwerte
Diese dürfen nicht sterben, bzw. deren Werte dürfen nicht verändert werden.

3. Populationen/Programme
Dürfen solange leben, bis eine Population/Programm bessere Ergebnise bringt. Bei mir dürften 10 Programme/Populationen Ihre Ergebnisse liefern.


b) Aktionsmodus
Dabei rufen die besten 10 Populationen die erlaubten Functionen/Proceduren aus dem Pool
mit den optimierten (zuvor gespeicherten) Parametern auf und der Bewerter liefert die Ergebnisse.


Generell:
Ungeahnte Ergebnisse sind dabei nicht erwünscht. Die Populationsgröße ist auf 100 begrenzt,
die Durchläufe, um Optimierungen zu finden ist, je nach Anzahl der zu optimierenden Variablen
Parameter auf 10 Mio. beläuft, wobei man sich anzeigen kann, wie schnell das Optimum gefunden wird, und entsprechend den Wert runtersetzt. Ist eine Population besser als die im 100er Pool, wird dieser eingetragen, dabei 'stirbt' der Letzte. Dabei können auch Programme, die weniger Code/Zeit
oder Proceduren aus dem Pool benötigen, bevorzugt werden, wenn gleiche Ergebnisse vorliegen.

So mache ich es vorerst. Beste Grüße
G02EITS

[Boombuler]

Offtopic:

Zitat von negaH:

Zu DOS Zeiten gab es ein lustiges Kriegsspiel. In einer simulierten Welt aus Speicherzellen und einem vorgefertigten Set von Maschinenbefehlen war es die Aufgabe der Spieler=Programmierer möglichst effiziente Progrämchens zu coden die diesen Speicher auf eine Weise beackerten das sie sich 1.) vorpflanzten oder bewegten und 2.) Gegnerische Progrämchens dabei vernichteten. Der Programmierer dessen Program als letztes übrig blieb hatte gewonnen.

Du meinst nicht zuuuuufällig CoreWar? (http://de.wikipedia.org/wiki/Corewar)

Greetz
Boombuler

PS: sollte wer daran intresse haben ich hab noch n interpreter für Redcode...

[negaH]

Doch das scheint es zu sein, allerdings hätte ich gedacht das das Teil schon längst tot und vergessen ist.
Ich meine aber das es früher nicht "CoreWar" hieß.

Gruß Hagen

[Neutral General]

Mal grad etwas off-Topic: Ich hab mir mal den Link zu Wiki angeguckt zum Thema Corewars. Und ich bin fasziniert!
Ich bin grade ein paar Tutorials am durchlesen und glaube es zu verstehen. Aber gibt es vielleicht irgendwo ein deutsches Corewar Forum? Weil ich würde gerne wissen ob ich eins wirklich verstehe oder ob ich das falsch verstehe...
Oder meint ihr ich kann sowas auch hier fragen? Ist ja im Prinzip Assembler.. ?!

Gruß
Neutral General

[negaH]

Das Ding ist schon über 20 Jahre alt, ich hatte es vor mehr als 15 Jahren getestet ! Ich glaube also kaum das es heut noch Foren dafür gibt, aber sag niemals nie. Der Eintrag im Wiki ist schon erstaunlich genug.

Gruß Hagen

[Boombuler]

BTW: Man könnte ja mal n DP internes Tunier für CoreWar anstreben

[Neutral General]

Fände ich gut
Btw: *Schleichwerbung mach*
Hab mal en CoreWar Forum gemacht weil ich selbst Anfänger bin und sowas gebraucht hätte und da ist auch Platz für Kämpfe etc..
www.CoreWar-Space.de.vu. Nur wie schon innem anderen Thread beschrieben gibts das Problem das man bei der Anmeldung kein
Passwort zugeschickt bekommt... aber das bin ich grad am lösen...

[Go2EITS]

Ich habe mal für Euch etwas Leichteres als CoreWars gesucht, nämlich Pascal Robots!
Die lassen sich leicht programmieren, wenn ich richtig sehe unter Turbo Pascal und Dos. Ein Win Robots gibt es wohl noch nicht. Eine Portierung nach Delphi wäre mal eine Herausforderung für Euch. Evtl. ist es ein Thema für eine Gemeinschaftsarbeit. Hier der InfoLink dazu. Es ist leider kein Download möglich, die Seite wird nicht mehr gepflegt. Es müsste aber irgendwo eine Pascalversion geben. Vielleicht findet jemand etwas dazu und gibt uns einen Link dazu.
Pascal Robots

Ihr findet bestimmt noch etwas...

Meine Ergänzung zum Thema Programmierspiele: PcRobots
Pc Robots
PcRobots Deutsch

Ganz viele Links mit sehr interessanten Inhalten:
Sammlung
Vielleicht findet ja jemand die jüngsten Sourcen zu Pascal Robots.
Viel Vergnügen!
Go2EITS

[TurboMartin]

Du hasst die die URLs nicht angeschaut. Die sind alle gleich, bis auf den Downloadlink, da hättest du aus "zeus" "www" machen müssen. Allerdings läuft die Version nicht unter Win.
Trotzdem mal als Anhang dabei, da kaum jemand ARJ-Dateien öffnen kann.
Ich versuch es dann mal zu übersetzen.

[edit]WinProblem herausgefunden: PRobots unterstütz nur Rechner mit bis 200 MHz[/edit]