Genetisches Programm [neue Version]

[CK_CK]

Ich möchte hier mal meinen ersten Versuch vorstellen, genetisch zu programmieren...

Das Programm funktioniert folgendermaßen:
Es soll der Weg von einem zum anderen Punkt gefunden werden.
Dazu wird eine Population erzeugt, von der jede Einheit eine vorgeschriebene Anzahl von Anweisungen bekommt (Buchstaben, die die Richtung beschreiben).
Diese Befehle sind z.B. folgendermaßen aufgebaut: "UDRRRRRLRUDLRDDDR" ("U" bedeutet 10 Pixel hoch [Up], "R" bedeutet 10 Pixel rechts [Right], usw.)
Wenn alle Einheiten ihren Weg hinter sich gebracht haben, wird geprüft, wie nah sie an das Ziel gekommen sind und bekommen dafür eine Bewertung.
Umso besser die Bewertung ist, desto öfter darf sich die betreffende Einheit fortpflanzen.
Die Fortpflanzung läuft folgendermaßen ab: Es wird jeder Befehl per Zufall entweder von Einheit 1, Einheit 2 oder einem Zufallswert genommen (um neue "Gene" zu bekommen).
Jede Einheit der neuen Population arbeitet jetzt ihre "mutierte" Befehlsreihe ab und wird wieder bewertet...
Einheiten, die das Bild am Ende des Weges verlassen haben werden mit neuen Zufallswerten erzeugt, sodass neue "Gene" in die Population kommen...

Das Programm zeichnet immer den Weg für jede Einheit an, außerdem kann man noch die meisten Faktoren ändern...

Ich hoffe, ich konnte die Funktionsweise gut beschreiben...
Viel Spaß beim zerpflücken des Codes und testen des Programms (wenn's jemand interessant findet...)

Schönen Abend noch,
Chris

[EDIT: NEUE VERSION]
Wenn eine Einheit das Ziel gefunden hat wird sie höher bewertet und muss auch nicht "weiterlaufen".
Die Einheiten werden jetzt auch nach ihrem Weg bewertet. Das funktioniert folgendermaßen:
Umso näher am Ziel, desto mehr Punkte; umso weniger Schritte, desto mehr Punkte.
Eine Einheit erhält z.B. 50 Punkte für's erreichen des Ziels und 25 Punkte, weil Sie 25 Schritte weniger als maximal zulässig benötigte. Sie erhält also 75 Punkte.

Dadurch habe ich es erreicht, dass jetzt idealere Wege gefunden werden (ich habe also den "Intelligenzquotienten" erhöht...). Das Ziel wird jetzt immer gefunden, der "ideale" Weg theoretisch auch (dauert nur ein wenig länger )

Außerdem kann man jetzt Pausieren und wieder Starten, ohne die Population zu löschen...

[Tubos]

Gefällt mir! Funktioniert und zeigt die grundlegende Funktionsweise auf.

Mich interessiert das besonders, da ich momentan an einer C#-Bibliothek für genetische Programmierung arbeite, die jedoch - anders als hier - Baumstrukturen als Programme verwendet. Man kann dabei die verwendeten Funktionen, Fortpflanzungsmethoden sowie die Programm-Generierung selbst schreiben und an die Bibliothek übergeben.
Soweit die Theorie - mal sehen, was daraus wird.

[lizardking]

Zitat von CK_CK:

Viel Spaß beim zerpflücken des Codes und testen des Programms (wenn's jemand interessant findet...)

Interessant auf jeden Fall ! Visualisierung gefaellt mir auch :)

NUR: 2 Denkansaetze

1. Du gehst meiner Meinung nach an einem Punkt den falschen Weg. Du willst das Problem loesen (moeglichst ohne Umwege) von Punkt A nach Punkt B zu kommen. In der Regel gehen genetische Algorythmen so vor, dass in jeder Population Individuen sind, die das Ziel erreichen. Die Anzahl der Schritte zu begrenzen ist gar nicht verkehrt, um Irrlaeufer aussterben zu lassen. Nehmen wir jedoch mal an, es handelt sich um ein Labyrinth, so sind Wege, die zwar sehr nah an das Ziel herankommen, jedoch dabei immer in eine Sackgasse laufen einfach Schei.... aehh.. ich wollte sagen suboptimal.
Die Fitness berechnet man daher meist nicht danach, wie nah man dem Ziel kommt, sondern wie weit die Strecke der Individuen ist, die ihr Ziel erreicht haben. Wer mit den vorgegebenen maximalen Schritten nicht auskommt, der stirbt im Zweifelsfall direkt aus.

2. Ohne mir den Code angeschaut zu haben, glaube ich Du hast viel zu viel Mutation. Die Mutation ist eigentlich hauptsaechlich dafuer da nicht in ausweglose Situationen zu gelangen in der Regel sollten sich bessere Loesungen durch "reine Fortpflanzung" und Auslese ergeben. Man sollte mit Mutationen eigentlich eher sparsam sein.
Meine Vermutung stuetzt sich darauf, dass auch nach zig Populationen in Deinem Programm die Wege EXTREM verschieden sind. Normal sollte es so sein, dass sich das ganze immer mehr einer geraden Linie von A nach B annaehert. Tut es aber nicht. Mal geht die Route eher oben rum, mal ziemlich weit unten, mal in der Mitte.

Ach ja, irgendwo sollte es auch noch eine Abbruchbedingung geben ;-)

Gruesse,

Lizzy

[Tubos]

Zitat:

Ohne mir den Code angeschaut zu haben, glaube ich Du hast viel zu viel Mutation. Die Mutation ist eigentlich hauptsaechlich dafuer da nicht in ausweglose Situationen zu gelangen in der Regel sollten sich bessere Loesungen durch "reine Fortpflanzung" und Auslese ergeben. Man sollte mit Mutationen eigentlich eher sparsam sein.

Hast du auch Quellen für diese Behauptung?
Meinst du mit "reiner Fortpflanzung" die Kreuzung (engl. Crossbreed) zweier Individuen? In dem Fall kann ich auf einen Artikel mit dem Titel "Mutation vs Crossbreed in Genetic Programming" verweisen, dessen URL ich leider verlegt habe

[lizardking]

Zitat von Tubos:

Hast du auch Quellen für diese Behauptung?
Meinst du mit "reiner Fortpflanzung" die Kreuzung (engl. Crossbreed) zweier Individuen? In dem Fall kann ich auf einen Artikel mit dem Titel "Mutation vs Crossbreed in Genetic Programming" verweisen, dessen URL ich leider verlegt habe ;)

Nein, keine Quelle. Das war meine persoenliche Meinung und ich wollte nur nicht zu viel mit "meiner Meinung nach", "ich denke" etc. verwenden ;-)
Gerade im Forschungsfeld der genetischen Algorythmen kann man sich sowieso sehr nahe an der Natur bewegen (ist ja schliesslich das Vorbild). Ich bin einfach nur davon ausgegangen, was ich gesehen habe. Da gab es sehr grosse Schwankungen, was in der Natur nicht der Fall ist. Angenommen der "noerdliche Umweg" von A zu B ist bevoelkert von Dinosauriern, der "suedliche Umweg" vom Neandertaler. Der direkte Weg von A zu B sei dem Homo sapiens vorbehalten.
Ein genetischer Algorythmus wuerde wuerde vielleicht vom Dinosaurier durch Mutation irgendwie mal auf dem Pfad des Neandertalers landen und von dort aus zum Homo sapiens, wuerde aber andauernd dermassen hin und her schwanken. Alleine schon aus dem Grund, weil sich die Aufgabenstellung nicht geaendert hat.

Mutation hat von daher natuerlich auch noch eine wichtige Funktion, wenn sich die "Aufgabenstellung aendert".

Wie geschrieben: Quellen kann ich keine geben. Wenn Du die URL wiederfindest, dann bitte her damit, interessiert mich. Da wird es wahrscheinlich gerade um die Quote zwischen Mutation und Vererbung gehen, was mich interessieren wuerde.

Gruesse,

Lizzy

[Nicolai1234]

aber irgendwas an dieser sparsame-Mutationsbenutzungs-Theorie muss ja dran sein. Ich bin jetzt bei der ca. 450. Generation und der hat den Weg immernoch nicht. Da wäre ja ein systematischer Weg besser, auch wenn das jetzt nicht hierher gehört.
Mich wundert es nur, da auf dem Weg ja nicht einmal Hindernisse oder dergleichen sind...

Edit: Generation 1500 und immer noch keine Lösung, aber jetzt geh ich ins Bett

[Go2EITS]

Also, ich habe den Source nicht angesehen , aber ich würde von Grund auf anders vorgehen, da Du
via Zufall (Mutation) den Weg bestimmst.

1. Die Reichweite der Individuen sollte Größer als das zu suchende Objekt (Futter) sein
2. Der Wege sollte per über einen Pool an Eigenschaften der Individiuen gefunden werden:
- 10 vor,zurück, links rechts
- 5 Sichtweite links reckts vor zurück
- Merken Objekt gefunden
- Kürzesten Weg zurück = Neuer Suchpfad.
- Hindernisse merken


Ziel ist es, mit so wenig Energie, bzw. Wegpunkten das Ziel zu finden. Und das Ziel ändert sich
nach einer gewissen Zeit. z. B. Apfel fällt vom Baum = neues Ziel
Das Individum versucht auch nicht nur 10 Schritte zu gehen, sondern wird nach besten Kräften
mit seinem Energievorat auf Suche gehen, da sonst, sagen wir mal, alle "Verhungern", wenwenn alle nur kurze Wege gehen und das Ziel nicht gefunden wird.

Generell mutiere ich den Pool an Eigenschaften und nicht den Weg. Der Wege wird erarbeitet und im Gedächnis (auch eine Eigenschaft) gemerkt. Bei der Mutation kann man z. B. statt 10 Punkte 8 Punkte und "VOR" sowie z. b. 3 Punkte "LINKS/RECHTS" in Richtung Ziel einstellen. Die Werte in den Eigenschaften sind um einem gewissen Prozentsatz veränderbar. Die Population mit den effektivsten Eigenschaften "gewinnt".

Sonst ist das Ganze nett gemacht.
Ach ja, bei Generation 2000 und noch nicht gefunden...

Viele Grüße von G02EITS

[Tubos]

Zitat:

Nein, keine Quelle. Das war meine persoenliche Meinung und ich wollte nur nicht zu viel mit "meiner Meinung nach", "ich denke" etc. verwenden

Alles klar.

Zitat:

Wie geschrieben: Quellen kann ich keine geben. Wenn Du die URL wiederfindest, dann bitte her damit, interessiert mich. Da wird es wahrscheinlich gerade um die Quote zwischen Mutation und Vererbung gehen, was mich interessieren wuerde.

Genau, um diese Quote geht es darin. Zusammenfassung: Man kann sowohl mit 100% Mutation und 0% Kreuzung, als auch umgekehrt ans Ziel kommen. Die Unterschiede sind nicht groß.
http://ftp.cs.umd.edu/users/seanl/pa...comparison.pdf

[CK_CK]

Guten Morgen,
erstmal vielen Dank für eure Kommentare

Ich werde das Bewertungssystem der Individuen mal so umbauen, dass die verbrauchte Strecke mit einfließt und Hindernisse mit hinzu kommen...

Mal sehen, was draus wird...
Vielleicht erreicht dann ja auch mal eine Einheit das Ziel genau; das sie "klüger" werden sieht man ja, nur erreichen sie nie die 100%...

[DennisHB]

Hi,

mir ist aufgefallen das einige Einheiten über das Ziel laufen, da sie aber anscheinend noch nicht alle Anweisungen abgearbeitet haben, stur weiter laufen.

Bzw Stoppt das Programm überhaupt selbstständig wenn das Ziel erreicht worden ist?