Genetischer Algorithmus
-
Hi
Suche ein einfaches Problem, um es mit einem genetischen Algorithmus zu lösen, zwecks Übung.
Es sollte aber in der Konsole machbar sein. Ein Beispiel hab ich im Netz gefunden, das versucht aus den Zahlen 0-9 und + - * / eine bestimmte Zahl zu errechnen.
Ich suche also etwas ähnliches von der Schwierigkeit her, bin kein Mathegenie
Danke
MfG
-
TSP ist recht beliebt (also Problem des Handlugsreisenden).
Als Mutation kann man entweder die Reihenfolge einzelner Knoten in der Besuchsliste vertauschen, oder ganz Sequenzen rumdrehen (oder beides).
-
Danke.
WIe kann ich da testen welches die richtige (die schnellste?) Lösung ist?
-
kleine beispiele nehmen die du auch per brute force ausrechenen kannst oder die du im kopf loesen kannst..
-
Hmm ja schon.
Ich meinte aber im Algo: wie weiss das Programm, wann es die "richtige" Lösung gefunden hat?
Oder lass ichs einfach eine bestimmte Zahl Generationen laufen, und nehm es dann als best gefundene, aber nicht die beste überhaupt?
-
BlinggBlingg schrieb:
Hmm ja schon.
Ich meinte aber im Algo: wie weiss das Programm, wann es die "richtige" Lösung gefunden hat?
Oder lass ichs einfach eine bestimmte Zahl Generationen laufen, und nehm es dann als best gefundene, aber nicht die beste überhaupt?du kanst aufhören, wenn sich die ergebnisse nicht mehr signifikant verändern bzw. schlechter werden.
-
Das TSP ist so schwer, daß man meistens garkeine optimale Lösung sucht. Oft reicht es, wenn man einfach eine "gute" Lösung hat.
-
Folgender Artikel dürfte dich vielleicht interessieren http://www.genarts.com/karl/papers/siggraph91.html
Haber ich vor ein paar Tagen schon im Spiele- und Grafikforum gepostet. Aber mit so was können die ganzen Gam0rs wohl nichts anfangen
-
Smart Sweeper ist recht amüsant und lehrreich (Grafik: einfachstes WinAPI): http://www.ai-junkie.com/ann/evolved/nnt5.html
Ebenfalls auf dieser Page: http://www.ai-junkie.com/ga/intro/gat1.html (gibt es auch in deutscher Übersetzung: http://www.ai-junkie.com/ga/intro/de-gat1.html )