Algorytm genetyczny w python ( problem robota & butelek ) - jak zoptymalizować?

Question

Witam, mój projekt znajduje się tu. Symulacja jest stworzona w JS a sam algorytm w python. W związku z tym można to dopalić gdziekolwiek ( jedynie plik run_server to skrót jaki sobie zrobiłem pod ubuntu, ale oczywiście na windows wystarczy usunąć nagłówek i zmienić rozszerzenie lub ręcznie wpisać komendę python -m http.server [adr] w miejscu tego pliku, ale to oczywiste... ).

Ideą projektu jest robot który ma zbierać z planszy butelki, aktualnie plansza jest 10x10 a butelek jest 15. Robot widzi tylko 5 pól ( swoje i po czterech stronach w około, lecz nie widzi po skosie ). Plik *.dna zawiera w sobie akcje jaką ma podjąć robot w każdej możliwej sytuacji ( akcje to kierunki ruchu w cztery strony lub podniesienie butelki ). Robot może wykonać tylko 50 akcji. W Python jest cały algorytm nauki, JS to sama symulacja ( animacja ) na podstawie już gotowego wygenerowanego pliku. Istotne jest więc to żeby dla obu skryptów były takie same parametry jeśli chodzi o wielkość mapy, oznaczenia akcji i pól, liczbę butelek oraz ilość możliwych ruchów dla robota. Na razie jest to mało profesjonalne ale potem oczywiście dodam jakiś wspólny plik JSON.

Właściwie swój pomysł oparłem na tym filmiku.

Kod jest bardzo prosty, w source/core jest algorytm oraz wygenerowany plik genotype.dna. W JS wystarczy tylko go wybrać. Wiem że nawy katalogów na razie głupie, ale to wszystko to tylko eksperyment prowizorki ;)

No więc przejdę do sedna, jestem początkujący w algorytmach genetycznych i wykorzystuje je na zasadzie prób i błędów. Po kilku godzinach "nauki" został wygenerowany plik w którym robot średnio zbierał ~9/15 butelek na plansze. Wynik niby nie jest zły, widać rzecz jasna efekt w porównaniu z losowo wygenerowanym plikiem.

Wszystko jednak trwało bardzo długo a wciąż zdarzają się patowe sytuacje w których robot wpada w "nieskończoną pętle akcji" i podróżuje w kółko wytracając całą energię. A tak się dzieje po 1000 generacjach, dla 40 osobników/jednostek na 100 losowych planszach dla każdego. Nie za bardzo wiem jakie proporcje dla algorytmu będą najlepsze ( np. stosunek przeniesionych do nowej generacji jednostek do ich liczby, lub też prawdopodobieństwo losowej mutacji itd... ). Nie wiem jaka konfiguracja się sprawdzi najlepiej...

Nie mam pojęcia czy jest jakaś uniwersalna formuła do wyznaczania tych parametrów dla algorytmów genetycznych, a może to jest kompletnie zależne od problemu...

Jeśli macie jakieś rady co powinienem zmienić to będę bardzo wdzięczny, jeśli natomiast nie ma żadnej formuły to cóż... będę nadal eksperymentował i czekał godzinami aż coś się poprawi ;)

Z góry dziękuje za pomoc i życzę zdrowia w tym trudnym czasie.

Comments

Jeśli są jakieś pytanie to śmiało piszcie.

---

@Jakub 0, Super fajny projekt. Niestety nie pomogę ci ponieważ jestem początkujący w Pythonie. Mam nadzieję że twoje pytanie zostanie odpowiedziane. Pozdrawiam :-).