Jak sklasyfikować problem optymalizacji wejścia emulatora i z jakim algorytmem powinienem do niego podejść?

Ze względu na charakter pytania muszę podać wiele podstawowych informacji (ponieważ moje pytanie brzmi: jak to zawęzić?) To powiedziawszy, można je streścić (o ile wiem):

Jakie metody istnieją, aby znaleźć lokalne optimum na bardzo dużych kombinatorycznych przestrzeniach poszukiwań?

tło

W społeczności superplay wspieranych narzędziami staramy się zapewnić specjalnie spreparowane (nie generowane w czasie rzeczywistym) dane wejściowe do konsoli lub emulatora gier wideo, aby zminimalizować niektóre koszty (zwykle czas do ukończenia). Obecnie odbywa się to poprzez odtwarzanie gry klatka po klatce i określanie danych wejściowych dla każdej klatki, często wielokrotnie powtarzając części serii (na przykład ostatnio opublikowana seria gry The Legend of Zelda: Ocarina of Time ma łącznie 198 590 ponownych prób).

Osiągnięcie celu tych tras zwykle sprowadza się do dwóch głównych czynników: planowania trasy i przejścia. Pierwsza jest znacznie bardziej „kreatywna” niż druga.

Planowanie trasy określa sposób, w jaki gracz powinien ogólnie nawigować, aby ukończyć grę, i często jest najważniejszą częścią biegu. Jest to analogiczne do wyboru, na przykład, jakiej metody sortowania należy użyć. Najlepszy rodzaj bąbelków na świecie po prostu nie będzie lepszy od szybkiego sortowania na milionie elementów.

Jednak w dążeniu do perfekcji ogromnym czynnikiem jest również podróż (sposób, w jaki przebiega trasa). Kontynuując analogię, w ten sposób implementowany jest algorytm sortowania. Niektórych tras nie można nawet wykonać bez ściśle określonych ramek danych wejściowych. Jest to najbardziej żmudny proces wspomagania narzędzi i sprawia, że ​​produkcja ukończonego cyklu zajmuje miesiące, a nawet lata. Nie jest to trudny proces (dla człowieka), ponieważ sprowadza się do wypróbowania różnych odmian tego samego pomysłu, dopóki nie zostanie uznany za najlepszy, ale ludzie mogą wypróbować tyle różnych wariantów w zakresie uwagi. Zastosowanie maszyn do tego zadania wydaje się tutaj właściwe.

Moim celem jest teraz próba zautomatyzowania procesu przejścia ogólnie dla systemu Nintendo 64 . Przestrzeń poszukiwania tego problemu jest zdecydowanie za duża, aby atakować przy użyciu siły brutalnej. Segment n-ramki przebiegu N64 ma 2 ³⁰ⁿ możliwych danych wejściowych, co oznacza, że ​​zaledwie 30 ramek wejścia (druga przy 30 klatkach na sekundę) ma 2 ⁹⁰⁰ możliwych danych wejściowych; niemożliwe byłoby przetestowanie tych potencjalnych rozwiązań, nie mówiąc już o tych, które trwają dwie godziny.

Jednak nie jestem zainteresowany próbą (a raczej nie zamierzam nawet próbować) całkowitej globalnej optymalizacji pełnego uruchomienia. Chciałbym raczej, biorąc pod uwagę początkowe dane wejściowe, aproksymować lokalne optimum dla określonego segmentu przebiegu (lub najbliższe n lokalnych optimum dla pewnego rodzaju optymalizacji częściowo globalnej) . To znaczy, biorąc pod uwagę trasę i początkowe przejście tej trasy: przeszukaj sąsiadów tego przejścia, aby zminimalizować koszty, ale nie degeneruj się, aby wypróbować wszystkie przypadki, które mogłyby rozwiązać problem.

Mój program powinien zatem przyjąć stan początkowy, strumień wejściowy, funkcję oceny i wyprowadzić lokalne optimum poprzez zminimalizowanie wyniku oceny.

Stan obecny

Obecnie zajmuję się wszystkimi ramami. Obejmuje to ocenę strumienia wejściowego poprzez manipulację emulatorem, konfigurację i porzucenie, konfigurację itp. A jako swego rodzaju symbol zastępczy, optymalizator jest bardzo podstawowym algorytmem genetycznym. Po prostu ocenia populację strumieni wejściowych, przechowuje / zastępuje zwycięzcę i generuje nową populację poprzez mutowanie strumienia zwycięzcy. Proces ten trwa do momentu spełnienia dowolnych arbitralnych kryteriów, takich jak czas lub numer generacji.

Zauważ, że najwolniejszą częścią tego programu będzie zdecydowanie ocena strumienia wejściowego . Wynika to z emulacji gry dla n klatek. (Gdybym miał czas, napisałbym własny emulator, który zapewniał haczyki do tego rodzaju rzeczy, ale na razie pozostaję z syntezowaniem wiadomości i modyfikowaniem pamięci dla istniejącego emulatora z innego procesu.) Na moim głównym komputerze, który jest dość nowoczesny, ocena 200 klatek zajmuje około 14 sekund. Jako taki wolałbym algorytm (biorąc pod uwagę wybór), który minimalizuje liczbę ocen funkcji.

Stworzyłem system w ramach, który jednocześnie zarządza emulatorami. Jako taki mogę oceniać wiele strumieni jednocześnie za pomocą liniowej skali wydajności, ale praktycznie mówiąc, liczba działających emulatorów może wynosić tylko od 8 do 32 (a 32 to naprawdę naciska), zanim wydajność systemu spadnie. Oznacza to (biorąc pod uwagę wybór), że algorytm, który może przetwarzać dane podczas przeprowadzania oceny, byłby bardzo korzystny, ponieważ optymalizator może wykonać pewne operacje podnoszenia podczas oczekiwania na ocenę.

Jako test, moją funkcją oceny (w przypadku gry Banjo Kazooie ) było sumowanie, na klatkę, odległości od gracza do punktu bramkowego. Oznaczało to, że optymalnym rozwiązaniem było jak najszybsze zbliżenie się do tego punktu. Ograniczenie mutację tylko drążek analogowy, zajęło jeden dzień, aby uzyskać okay rozwiązanie. (Było to przed wdrożeniem współbieżności.)

Po dodaniu współbieżności włączyłem mutację naciśnięć przycisków A i wykonałem tę samą funkcję oceny w obszarze wymagającym przeskoku. Przy uruchomionych 24 emulatorach dotarcie do celu z początkowo pustego strumienia wejściowego zajęło około 1 godziny, ale prawdopodobnie musiałoby trwać kilka dni, aby osiągnąć poziom zbliżony do optymalnego.

Problem

Problem, przed którym stoję, polega na tym, że nie wiem wystarczająco dużo o matematycznym polu optymalizacji, aby wiedzieć, jak właściwie modelować mój problem optymalizacji ! Mogę z grubsza podążać za koncepcją wielu algorytmów opisaną na przykład w Wikipedii, ale nie wiem, jak skategoryzować mój problem lub wybrać najnowocześniejszy algorytm dla tej kategorii.

Z tego, co mogę powiedzieć, mam problem kombinatoryczny z bardzo dużym sąsiedztwem . Na początku, że funkcja oceny jest niezwykle nieciągłe, nie ma gradientu, i ma wiele płaskowyże . Ponadto nie ma wielu ograniczeń, choć chętnie dodam możliwość wyrażenia ich, jeśli pomoże to rozwiązać problem; Chciałbym pozwolić na określenie, że przycisk Start nie powinien być używany, na przykład, ale nie jest to ogólny przypadek.

Pytanie

Więc moje pytanie brzmi: jak to modelować? Jakiego rodzaju problem optymalizacji próbuję rozwiązać? Którego algorytmu mam użyć? Nie boję się czytać prac naukowych, więc daj mi znać, co powinienem przeczytać!

Intuicyjnie algorytm genetyczny nie może być najlepszy, ponieważ wydaje się, że tak naprawdę się nie uczy. Na przykład, jeśli naciśnięcie Start wydaje się zawsze pogarszać ocenę (ponieważ wstrzymuje grę), powinien istnieć jakiś projektant lub mózg, który uczy się: „naciśnięcie Start w dowolnym momencie jest bezużyteczne”. Ale nawet ten cel nie jest tak trywialny, jak się wydaje, ponieważ czasami naciśnięcie przycisku Start jest optymalne, na przykład w tak zwanych „pauzach w tył-długie skoki” w Super Mario 64 ! Tutaj mózg musiałby nauczyć się o wiele bardziej złożonego wzoru: „naciśnięcie przycisku Start jest bezużyteczne, z wyjątkiem sytuacji, gdy gracz znajduje się w tym bardzo specyficznym stanie i będzie kontynuował kombinację naciśnięć przycisków ”.

Wydaje się, że powinienem (lub maszyna mogłaby się tego nauczyć) reprezentować dane wejściowe w inny sposób, bardziej dostosowany do modyfikacji. Dane wejściowe na klatkę wydają się zbyt szczegółowe, ponieważ tak naprawdę potrzebne są „akcje”, które mogą obejmować kilka ramek ... jednak wiele odkryć dokonuje się na zasadzie klatka po klatce, więc nie mogę całkowicie wykluczyć ( wspomniana pauza w tył-skok w dal wymaga precyzji na poziomie klatki). Wydaje się również, że fakt, że dane wejściowe są przetwarzane szeregowo, powinien być czymś, co można wykorzystać, ale nie jestem pewien, jak to zrobić.

Obecnie czytam o (Reaktywnym) wyszukiwaniu Tabu, wyszukiwaniu sąsiedzkim na bardzo dużą skalę, optymalizacji opartej na nauczaniu i optymalizacji oraz optymalizacji kolonii mrówek.

Czy ten problem jest po prostu zbyt trudny do rozwiązania za pomocą innych niż przypadkowe algorytmy genetyczne? Czy jest to tak naprawdę trywialny problem, który został rozwiązany dawno temu? Dziękujemy za przeczytanie i z góry dziękuję za wszelkie odpowiedzi.

Z informacji podanych w pytaniu nie widzę, jak zastosować standardowe metody optymalizacji (o których wiem). Twoje obiekty nie są tak skomplikowane (więcej o tym później), ale twoja funkcja docelowa jest nieprzyjemna: jej wartości są zdefiniowane przez system zewnętrzny poza twoją kontrolą, jest mało prawdopodobne, aby miała jakieś miłe właściwości i tak dalej. Dlatego myślę, że stosowanie algorytmów genetycznych nie jest niewykonalne, a może nawet dobrym podejściem; często działają lepiej niż inne metody, jeśli nie masz pojęcia o strukturze problemu. Jest wiele rzeczy do rozważenia

• przestrzeń obiektowa,
• funkcja celu i
• parametry twojego algorytmu genetycznego,

więc pozwólcie mi rozwinąć.

Jakie są twoje przedmioty

Odpowiedziałeś już na to: patrzysz na sekwencję działań, z których każda zajmuje jedną klatkę. Myślę, że może to być zbyt drobnoziarniste; może wypróbować sekwencję akcji, z których każda ma czas trwania (w liczbie klatek). Pozwoliłoby to mieć mutacje takie jak „chodzić trochę dłużej”, aby mieć inne prawdopodobieństwo niż „wstawić naciśnięcie A” w naturalny sposób. Wypróbuj to, co działa najlepiej; być może będziesz musiał ponownie odwiedzić ten przedmiot po przemyśleniu innych składników.

Jaka jest twoja funkcja docelowa?

Ten jest naprawdę kluczowy. Co chcesz zoptymalizować? Czas do celu? Liczba różnych działań? Liczba zebranych gwiazd? Kombinacja kilku czynników? Gdy tylko zdobędziesz wiele celów, rzeczy stają się owłosione - tam (zwykle) nie ma już optymów!

Wspomniałeś o czasie do celu. Prawdopodobnie wcale nie jest to dobra funkcja celu. Dlaczego? Ponieważ większość sekwencji nawet nie osiągnie celu, więc osiągną wartość końcową do jakiejś stałej, tworząc krajobraz fitness taki jak ten (szkic koncepcyjny w jednym wymiarze):

^{[ źródło ]}

$0$$0$

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

$0$$1$$1$

Jak mierzysz odległość? Odległość liniowa może wydawać się kusząca, ale ma swoje problemy; ponownie mogą zostać wysłane niewłaściwe sygnały. Rozważ ten prosty scenariusz:

^{[ źródło ]}

Każda sekwencja, która zaczyna się od skoku do górnego korytarza, poprawia się, dopóki nie osiągnie miejsca tuż nad celem, ale tak naprawdę nigdy nie może dotrzeć do celu! Co gorsza, spośród wszystkich sekwencji, które nie osiągają celu, te, które idą w górę, są tak dobre, jak te, które spadają, więc GA nie może odrzucić sekwencji, które są wyraźnie skazane na zagładę. Innymi słowy, odległość liniowa tworzy szczególnie złe lokalne optymima, które mogą uwięzić GA, jeśli na poziomie są ślepe zaułki.

Dlatego sugeruję, abyś nałożył siatkę na swój poziom i łączył punkty sąsiadów, jeśli postać gry może przejść od jednego do drugiego. Następnie obliczasz odległość od celu na podstawie długości najkrótszej ścieżki od punktu najbliższego miejsca, w którym sekwencja wyląduje postacią do punktu najbliższego celowi. Jest to łatwe do obliczenia, a wkraczanie w deadends (lokalne optima) jest natychmiast karane¹. Oczywiście potrzebujesz dostępu do danych poziomu, ale zakładam, że je masz.

Jak działa twoja GA?

Teraz możemy przejść do faktycznego algorytmu genetycznego. Kluczowe kwestie to populacja, selekcja, reprodukcja / mutacja i kryterium zatrzymania.

Populacja

Jak duża będzie Twoja populacja? Jeśli jest za mały, może nie zapewniać różnorodności niezbędnej do znalezienia dobrego rozwiązania. Jeśli jest zbyt duży, bardziej prawdopodobne jest, że będziesz nosić ze sobą bezużyteczne śmieci, co spowolni proces.

Jak zainicjować swoją populację? Czy wybierasz losowe sekwencje akcji? Jeśli tak, o jakiej długości? Czy masz (niewielką) liczbę ręcznie wygenerowanych, rozsądnych rozwiązań do wysiewu, być może takich, które osiągną cel?

Wybór

$k$

Podstawową koncepcją tutaj jest presja selekcyjna : jak trudno jest przetrwać? Zrób to za małe, a nie zużyjesz badziewnych rozwiązań. Ustaw ją zbyt wysoko, a utrudnisz zmianę (w szczególności przemieszczanie się między lokalnymi optymami).

Rozmnażanie i mutacja

Po wybraniu ocalałych z jednej rundy musisz stworzyć z nich kolejne pokolenie (czy rodzice przeżyją i są częścią następnego pokolenia?). Istnieją dwie główne strategie: mutacja i rekombinacja.

Mutacja jest dość wyraźna, chociaż jej specyfika może się różnić. Dla każdej pozycji w sekwencji danej osoby mutuj ją z pewnym prawdopodobieństwem. Możesz to zrobić niezależnie dla każdej pozycji, lub losowo wybrać liczbę mutacji, lub możesz wykonać różne mutacje z różnymi prawdopodobieństwami (np. Wstawienie nowego elementu, usunięcie jednego, zmiana jednego, ...). Mutacja zwykle dotyczy małych zmian.

Rekombinacja, która łączy aspekty dwóch lub więcej rozwiązań w nowe, jest trudniejsza, ale może pozwolić na duże kroki, to znaczy opuszczenie jednej „góry fitness” i przejście bezpośrednio na zbocze drugiej (która może być wyższa). Klasycznym pomysłem jest crossover ; Nie wiem, czy ma to sens (wydaje mi się, że zamiana prefiksu danej sekwencji na coś innego najprawdopodobniej obniży przyrostek). Być może możesz wykorzystać wiedzę o poziomie i pozycjach postaci w różnych punktach sekwencji, aby to poprowadzić, to znaczy tworzyć punkty podziału tylko wtedy, gdy postać znajduje się w tej samej pozycji w obu sekwencjach.

Zakończenie

$N$$k$$1$$n$

Jak widać, wszystkie te rzeczy przeplatają się, aby wpływać na rzeczywistą wydajność. Jeśli prowadzisz wiele populacji równolegle, możesz nawet pomyśleć o wprowadzeniu dryfu genetycznego z powodu migracji i / lub katastrof. Niewiele jest teorii, które mogłyby pokierować twoją drogą, więc musisz wypróbować różne konfiguracje i sprawdzić, gdzie cię to zaprowadzi. Mam nadzieję, że to, co działa na jednym poziomie, będzie działać również na innych. Miłego majsterkowania!

Nota bene: Spójrz na BoxCar 2D w świetle powyższego. Robią niektóre rzeczy całkiem dobrze (inne, ale nie tak) i można uzyskać intuicję, w jaki sposób parametry GA mogą wpływać na jego wydajność.

1. W rzeczywistości chciwe konstruowanie sekwencji przy użyciu tej sprawności, czyli wybieranie akcji minimalizującej dystans do celu spośród wszystkich możliwych następnych akcji, może działać całkiem dobrze. Wypróbuj to przed użyciem GA!
2. Oczywiście jako obserwator zawsze pamiętasz najlepsze rozwiązanie, jakie kiedykolwiek spotkałem.

Więcej informacji na temat metody optymalizacji opartej na nauczaniu i uczeniu się (TLBO) i jej kodzie można znaleźć w następującym artykule:

Elitarny algorytm optymalizacyjny oparty na nauczaniu i uczeniu się do rozwiązywania złożonych ograniczonych problemów optymalizacyjnych R. Venkata Rao i V. Patela; International Journal of Industrial Engineering Computations 3 (4): 535–560 (2012)

Do dodatkowej lektury:

• Algorytm optymalizacji oparty na nauczaniu i uczeniu się dla nieograniczonych i ograniczonych problemów z optymalizacją rzeczywistych parametrów R. Venkata Rao, VJ Savsani i J. Balic; Optymalizacja inżynierska (2012)
• Mechaniczna optymalizacja projektu przy użyciu zaawansowanych technik optymalizacji R. Venkata Rao, JV Savsani; Springer-Verlag London (2012); ISBN 978-1-4471-2747-5
• Wielozadaniowa optymalizacja wymienników ciepła przy użyciu zmodyfikowanego algorytmu optymalizacji opartego na nauczaniu i uczeniu się autorstwa R. Venkata Rao i V. Patela; Applied Mathematical Modeling (2012)
• Wielozadaniowa optymalizacja dwustopniowych termoelektrycznych chłodnic przy użyciu zmodyfikowanego algorytmu optymalizacji opartego na nauczaniu i uczeniu się, opracowanego przez R. Venkata Rao i V. Patela; Zastosowania inżynierii sztucznej inteligencji (2012)