Neuronales Netzwerk - Genetischer Algorithmus

[MLP]

NN mit GA zu trainieren ist wirklich lahm, da ist ein MLP mit Back Propagation schon viel besser. Außerdem sind 2 Input Neuronen sehr wahrscheinlich viel zu wenig.

[otze]

NN mit Backprop funktioniert nicht wirklich gut. Es ist zwar schneller als evolutionäre algorithmen/genetische algorithmen, landet aber in schlechteren lokalen Optima - eben weil es nur stinknormalen Gradientenabstieg auf einer ekelhaften Fehlerfunktion macht. Zudem ist in dem Setting gar nicht klar, wie aussagekräftig der Gradient ist(verrauscht), oder wie man anhand der Fehlerfunktion den Gradient berechnen sollte. So offensichtlich differenzierbar ist die Funktion ja nicht.

Für ein reinforcement-learning setting wie hier sind EAs/GAs schon in Ordnung.

Ich würde aber auch sagen, das 2 Inputs echt wenig information für das Problem liefern. Ich mein, was ist die Information die du darin speicherst? Position auf dem Spielfeld? Dann weiß dein Panzer ja nicht, wo die Gegner sind. Ist kein Wunder, dass er da nichts gebacken kriegt. Du kriegst nur so viel raus, wie du vorher rein gesteckt hast.

[MLP]

otze schrieb:

NN mit Backprop funktioniert nicht wirklich gut. Es ist zwar schneller als evolutionäre algorithmen/genetische algorithmen, landet aber in schlechteren lokalen Optima - eben weil es nur stinknormalen Gradientenabstieg auf einer ekelhaften Fehlerfunktion macht. Zudem ist in dem Setting gar nicht klar, wie aussagekräftig der Gradient ist(verrauscht), oder wie man anhand der Fehlerfunktion den Gradient berechnen sollte. So offensichtlich differenzierbar ist die Funktion ja nicht.

Ja, simples BP funktioniert nicht so gut, musst ein bisschen pimpen. http://cs.uni-muenster.de/Studieren/Scripten/Lippe/wwwnnscript/modifikationen1.html

[otze]

Das ist ein anderer Algorithmus um Gradientenabstieg zu machen. Aber wie jeder Gradientenabstieg basierte Algorithmus bleibt dir das Ding in lokalen Optima hängen. Rprop, Quickprop, Newton, was auch immer erreichen das nur schneller. Aber das Grundproblem kannst du nicht lösen, solange du nur eine lokale Metrik hast. Evolutionäre Ansätze lösen das Problem. CMA zum Beispiel glättet die Funktion lokal um einen Suchpunkt und kann so lokale Optima zum Teil ignorieren. Aber die Verfahren sind alle weit vom Gradientenabstieg weg.

Die Verbesserungen ändern auch nichts daran, dass du in diesem Fall keine differenzierbare Fehlerfunktion hast, weil der Funktionswert diskret ist.

noch was zum topic:

Als Input habe ich mir überlegt, dass der Panzer die Distanz zum nächsten Gegner benötigt:
1. MeinPanzer.X - GegnerPanzer.x + MeinPanzer.y - GegnerPanzer.y

Und für die Entscheidung der Schussabgabe auch die aktuelle Ausrichtung des Panzers:
2. Aktuelle Ausrichtung des eignene Panzers

Was genau soll das Netz denn lernen? Du gibst dem panzer die Distanz, das is tokay. Die Ausrichtung ist auch hilfreich, aber: wenn sich dein Panzer einfach nur rotiert, dann bleibt die Distanz vom Gegner gleich. Der Panzer hat also keine Ahnung, in welcher Richtung der Gegner überhaupt ist. Das wäre kein Problem, wenn dein Netzwerk ein Gedächtnis hätte - hat es aber nicht.

An deiner Stelle würde ich noch irgendwie den Winkel hinzufügen. Ist immer noch ein echt schweres Problem, aber ohne den Winkel ist dein Problem so mehrdeutig, dass da einfach nichts geht.

[nman]

otze schrieb:

Aber wie jeder Gradientenabstieg basierte Algorithmus bleibt dir das Ding in lokalen Optima hängen.

Ich wage zu behaupten, dass hier nicht die lokalen Optima das Problem sind.

Wie gesagt, hier ist soviel kaputt, dass ich ein anderes Problem als Einstieg in das Thema suchen wuerde, bei dem man leichter sieht welche Aenderungen was kaputtmachen oder verbessern.

[Neuro]

Hey,

vielen Dank für die ganzen Anregungen! Ich bin schon ein kleines Stückchen weitergekommen. Ich habe dem Netzwerk noch die Rotation als Input mitgegeben und die Art der Vererbung etwas verändert.

Tatsächlich ist ein gewisser Erfolg nun sichtbar. Vorher haben die Panzer wirklich immer das gleiche Verhalten gezeigt. Sie sind immer im Kreis gefahren und es gab keine Reaktion, wenn ein anderer Panzer in die Nähe kam.

Mit den Veränderungen sah es eben so aus, dass ein Panzer einen anderen abgeschossen hat und anschließend rückwärts gefahren ist. Er hat also auf den Wegfall des Panzers reagiert. Das freut mich schon mal sehr und ist so auch viel lustiger anzusehen. Denn der Panzer ist nicht mehr so berechenbar und bleibt auch einfach mal für einen Moment stehen

Aber dumm sind sie noch immer, aber ich könnte mir vorstellen, dass sie noch etwas schlauer werden, wenn ich die Gewichtung an die Verbindung und nicht mehr an die Neuronen hänge. Dadurch entstehen ja viel mehr Variationsmöglichkeiten und das ganze System wird noch flexibler.

[MLP]

otze schrieb:

Das ist ein anderer Algorithmus um Gradientenabstieg zu machen. Aber wie jeder Gradientenabstieg basierte Algorithmus bleibt dir das Ding in lokalen Optima hängen. Rprop, Quickprop, Newton, was auch immer erreichen das nur schneller. Aber das Grundproblem kannst du nicht lösen, solange du nur eine lokale Metrik hast. Evolutionäre Ansätze lösen das Problem. CMA zum Beispiel glättet die Funktion lokal um einen Suchpunkt und kann so lokale Optima zum Teil ignorieren. Aber die Verfahren sind alle weit vom Gradientenabstieg weg.

Über kleine lokale Minima kommst du schon drüber. Ich glaub ich hab am Ende BP und GA etwas gemischt und bin immer sehr schnell zu Ergebinssen gekommen. Nur GA wahr schon sehr lahm.

[Ein ehemaliger Benutzer]

Ich würde dir persönlich raten, das ganze trotzdem noch ein wenig mit genetischen Algorithmen zu versuchen, anstatt zu "klassischem" Training überzugehen, nachdem du paar Grundprobleme aussortiert hast (Gewichtungen). Das hat rein egoistische Gründe

Mir selbst wurde schon ein Forschungsprojekt zu adaptiven Spiking Neural Networks mithilfe von genetischen Algorithmen angeboten, was ich wahrscheinlich in Zukunft auch angehen werde (wenn mir bis dahin das Projekt keiner weggeschnappt hat), weshalb ich interessiert wäre zu welchen Ergebnissen du nach ner Weile kommst.

Nachdem du Gewichtungen richtig verarbeitest, solltest du mal an anderen Fehlerquellen suchen: Wie kodierst du die NNs im Moment als Individuen? Hier gibt es bestimmt guten Spielraum um Schemas ausnutzen zu können.

Wie führst du das Crossover im Moment durch? Zufällige Vermischung hört sich nicht so gut an.

[Dummie]

Hey,

da ich meistens keine Lust habe mich anzumelden, poste ich unregistriert. Aber ich oute mich an dieser Stelle mal

Mir macht das Thema echt sehr viel Spaß und es ist unheimlich interessant. Ich hab nun das gesamte Projekt von vorne begonnen.

Nun hat jede Verbindung eine eigene Gewichtung. Die Mutation gefällt mir aber noch nicht. Von den besten 3 werden halt zufällig die Gene vermischt... Ich bin am Überlegen, ob ich nicht lieber die besten 5 nehme. Man muss echt sehr viel experimentieren.

Als Input habe ich inzwischen foldenes:
1. Eigene Rotation
2. Entfernung von nächstem gegnerischen Panzer
3. Eigene Rotation
4. Eigene Gesundheit (dadurch kann der Panzer indirekt Treffer wahrnehmen)

Eventuell nehme ich noch die Gesundheit des gegnerischen Panzers dazu. Mich würd interessieren, ob dann alle Panzer auf den schwächeren Panzer in ihrer Nähe los gehen.

Trotzdem hat sich die "Performance" der Panzer schon deutlich verbessert. Es gibt bereits interessante Verhaltenweisen zu bestaunen.

Ein Panzer hat immer geschossen und sich dabei ein Stück gedreht und ist dann wieder zur Ausgangsrotation zurückgekehrt. Er hat also dadurch Salven verschossen. Ein anderer ist immer weite Kreise gefahren und hat den Gegnern dann den Weg abgeschnitten.

Aktuell kristalliseren sich aber Panzer heraus, die zum Rand des Spielfelds fahren und dort bleiben und von dort die Gegner beschießen. Auch hier findet sich oft die Salventechnik. Damit sind sie so erfolgreich, dass sie sich über Generationen immer mehr vermehren...

Ich konnte aber noch nicht wirklich viel testen, weil entweder ein Fehler auftauche oder mir etwas anderes auffiel. Oder was ich aktuell auch habe sind Endlosschleifen. Um Panzer für Treffer zu bestrafen bzw. zu belohnen kriegen sie Gesundheit abgezogen oder hinzuaddiert. Das ist teilweise problematisch. Dafür hab ich aber auch schon Ideen. Aber es ist natürlich ein Nachteil an der Geschichte, man muss immer von 0 beginnen oder eine Speicherfunktion einbauen

Ich bastel noch ein wenig rum und dann stelle ich vielleicht auch mal den Quellcode hier rein. Da ich für die Grafik SFML verwendet habe, sollte das auch jeder gut kompilieren können. Ich würd mir erhoffen, dass sich dann vielleicht noch ein paar Optimierungen finden könnten und

[nman]

Cool, dass du da dranbleibst. Wollte dich nicht irgendwie entmutigen, ist nur immer schwer zu sagen, wieviel Ausdauer Leute hier haben, wenn man sie nicht kennt und es gibt leichtere Einstiegsmöglichkeiten in das Thema.

Dummie schrieb:

Eventuell nehme ich noch die Gesundheit des gegnerischen Panzers dazu. Mich würd interessieren, ob dann alle Panzer auf den schwächeren Panzer in ihrer Nähe los gehen.

Wenn sie nur einen sehen eher unwahrscheinlich.

Wie schon gesagt: Am Crossover lässt sich bestimmt noch einiges verbessern.

Oder was ich aktuell auch habe sind Endlosschleifen.

Welcher Art?

[Dummie]

nman schrieb:

Oder was ich aktuell auch habe sind Endlosschleifen.

Welcher Art?

Die Panzer werden ja für einen Treffer belohnt bzw. bestraft.

Trifft ein Panzer einen anderen erhält er 10 Lebenspunkte dazu. Wird er getroffen werden 10 Lebenspunkte abgezogen. Im ungünstigsten Fall kann es passieren, dass sie sich so gegenseitig am Leben halten. Habe das aber nun so geändert: Jetzt kriegen sie 10 abgezogen bzw. 20 dazu. Eventuell ist damit der Kreislauf durchbrochen. Muss ich mal testen.

Außerdem habe ich jetzt eine Beschleunigungsfunktion eingebaut. Wobei ich mir nicht sicher bin, ob das auch die Entwicklung beeinflusst. Bei zu großen Werten ist evtl. die Auflösung von float zu klein, so das die Berechnungen nicht mehr passen. Kann ja sein, dass sich dann das Optimum für diese Beschleunigung bildet, keine Ahnung. Aber mit 10x müsste es wohl hinhauen.

Aktuell mache ich das Crossover so:

void PanzerControllerAI::Mutate(const PanzerControllerAI& panzer)
{
	for (std::size_t i = 0; i < panzer.GetInputNeurons().size(); ++i)
	{
		for (std::size_t j = 0; j < panzer.GetHiddenNeurons().size(); ++j)
		{
			if (GetRandom(0, 1) == 1)
				myInput[i].connections[j].weight = panzer.GetInputNeurons()[i].connections[j].weight;
			else
				myInput[i].connections[j].weight = GetRandom(-100, 100) / 100.f;
		}
	}

	for (std::size_t i = 0; i < panzer.GetHiddenNeurons().size(); ++i)
	{
		for (std::size_t j = 0; j < panzer.GetOutputNeurons().size(); ++j)
		{
			if (GetRandom(0, 1) == 1)
				myHidden[i].connections[j].weight = panzer.GetHiddenNeurons()[i].connections[j].weight;
			else
				myHidden[i].connections[j].weight = GetRandom(-100, 100) / 100.f;

		}
	}
}

Es wird also zufällig die Gewichtung übernommen oder eine neue generiert.

[hustbaer]

Ich glaube dass es für das NN viel einfacher wäre brauchbaren Output zu erzeugen, wenn du den Winkel zum Gegner relativ zur eigenen Ausrichtung angeben würdest.

Wobei ich dazusagen sollte dass ich von NN so-gut-wie keine Ahnung habe

[Dummie]

hustbaer schrieb:

Ich glaube dass es für das NN viel einfacher wäre brauchbaren Output zu erzeugen, wenn du den Winkel zum Gegner relativ zur eigenen Ausrichtung angeben würdest.

Wobei ich dazusagen sollte dass ich von NN so-gut-wie keine Ahnung habe

Genau das hab ich mir vor ein paar Minuten auch gedacht. Gedankenübertragung

Es gibt natürlich sehr viele Schrauben, wo man dran drehen kann. Das macht die Sache sehr experimentell. Außerdem kann man immer schlecht sagen, ob das was die Panzer jetzt machen auch richtig ist oder ob es einfach nur so eine Phase ist, die wieder vorbei geht.

Ich hab z.B. gerade einen Bug gefunden: Bei der Suche des nächsten Panzers war ich nämlich sehr erfolgreich. Der Panzer hat sich selber als den nächsten Panzer bestimmt. Hab das nur durch Zufall rausgefunden, weil ich Linien anzeigen wollte, die das nächste Ziel markieren. Nur waren keine zu sehen. Und dann hat es bei mir Click gemacht.

[nman]

Dummie schrieb:

Aktuell mache ich das Crossover so[...]

Kommt mir persoenlich fast ein bisschen sehr random vor. Ich habe von dem Thema zwar nicht viel keine Ahnung, aber schau dir mal das hier an, das koennte dir helfen:
http://www.complex-systems.com/pdf/07-4-1.pdf

Finde ich halbwegs verstaendlich geschrieben und deckt ganz gut das ab, was du machen moechtest.

[Dummie]

Ja, das stimmt natürlich. Danke

Ich habe inzwischen sehr viel verändert und es hat sich auch teilweise eine Besserung eingestellt.

Fakt ist aber, dass das Ergebnis noch nicht so wirklich berauschend ist. Die Gründe reichen wohl von (noch immer) fehlerhafter Implementierung von schlecht gewählten Werten oder auch ungenügender Iterationen. Das ist etwas frustrierend.

Ich hab schon nach Büchern gesucht, aber bin noch auf keins gestoßen, was mich überzeugt hat.

Ansonsten experimentiere ich nebenbei weiter und versuche noch einiges an der Simulation selber zu optimieren.