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...

[CK_CK]

Zitat von 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.

Das ist ja genau der Sinn des Programms. Ich will keine ideale Lösung, sondern es soll so gerechnet werden, wie es die Natur machen würde (oder macht...).

@DennisHB: Ja, du hast recht. Eine neue Version, die jetzt recht gut funktioniert gibt's im ersten Post...

Viel Spaß beim testen (wenn jemand Lust hat ),
Chris

[Neutral General]

HI,

Also interessantes Programm über ein sehr interessantes Thema
Aber eigentlich soll doch ein Weg gefunden werden oder?
Ich weiß nicht ob das so geplant war (oder in der neuen Version besser ist (gleich mal ausprobier)) aber bei mir war meine Population in der 11.000ten Generation nicht viel näher am Ziel als ein paar tausend Generationen davor

Soll das so?^^

Gruß
Neutral General

[CK_CK]

Wow, 11.000 Generationen... Du machst mich fertig
So lange hab' ich das nicht ausgehalten... (Wie lange hat das gedauert?)
Den Screenie muss ich gleich mal speichern...

Ja, der Fehler ist in der neuen Version weg. Es werden aber immer wieder ein paar neue "Gene" eingefügt, sodass zwischendurch auch mal eine Einheit "abhauen" kann. Diese wird aber sofort gelöscht (darf sich nicht fortpflanzen)...

[jfheins]

Wie wäre es, wenn du den Grad an zufllsmutation einstellen lässt?

Weil es für mich aussieht, dass es immernoch zuviel ist ...

Die Dinger sind auf richtigen Weg, und dann gehen sie auf einmal alle wieder komplett inne falsche richtung ....

(Irgendwer hat glaube ich mal was von optimalerweise 3% gesagt ....)

[CK_CK]

Ich weiß, das habe ich auch gelesen. Bei mir sind es 2 Prozent...

Es sieht vielleicht so aus, als wäre die Mutation zu hoch, jedoch verschwinden diese "Ausfälle" sofort (spätestens nach 5 Generationen sind sie weg...)

...Aber ich baue einen Zufalls-Regler gerne noch ein...

[Neutral General]

Zitat von CK_CK:

Wow, 11.000 Generationen... Du machst mich fertig
So lange hab' ich das nicht ausgehalten... (Wie lange hat das gedauert?)
Den Screenie muss ich gleich mal speichern...

Ja, der Fehler ist in der neuen Version weg. Es werden aber immer wieder ein paar neue "Gene" eingefügt, sodass zwischendurch auch mal eine Einheit "abhauen" kann. Diese wird aber sofort gelöscht (darf sich nicht fortpflanzen)...

Ehm ka hat 3 oder 4 Stunden gedauert oder so

[lizardking]

Zitat von Tubos:

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

*oehm* *naja* das ist aber auch 'ne sehr grobe und ungenaue Zusammenfassung. Hab's jetzt einmal grob ueberflogen, aber es stellt sich schon ein wenig anders dar. Es geht um ein Verhaeltnis 90% zu 10% und nicht 100% zu 0%. Ersteres wuerde auch wenig Sinn machen, da 100% auf ein reines Trial and Error-Prinzip hinauslaufen wuerde.

Auf Anhieb interessant an dem Papier fand ich, dass die Komplexitaet des Problems ausschlaggebend dafuer ist, in wie weit eine hoehere Mutationsrate Einfluss auf den Erfolg hat. Eigentlich sogar recht logisch: Wenn ich einen grossen Loesungsraum habe (wie bei komplexen Problemen ueblich), dann helfen viele Mutationen dabei, eine grosse Flaeche abzudecken.
Angenommen es geht wieder um das Labyrinth. Stellen wir uns vor es hat 100 Eingaenge. Wenig Mutation wuerde bedeuten, dass wir unter Umstaenden in sehr wenigen Eingaengen sehr lange nach dem kuerzesten Weg suchen. Bei vielen Mutationen waere die Wahrscheinlichkeit auch andere Eingaenge zu erforschen um einiges hoeher.

Das ist nur mal zusammengefasst, was ich so auf den ersten Eindruck von dem Papier mitgenommen hab ;-). Steckt bestimmt noch mehr drin, aber nicht um diese Uhrzeit *g*

Gruesse,

Lizzy