Szybki przykład ewolucji genetycznej w JavaScript: Let's Make a Baby.

„Proces mutacji jest jedynym znanym źródłem nowych materiałów o zmienności genetycznej, a więc i ewolucji”. - Dobżański, 1957.

Algorytmy ewolucji genetycznej są dla mnie naprawdę fascynujące. Umiejętność programowania wirtualnego DNA to fenomenalne osiągnięcie informatyki. Zdolność do pisania, w kodzie, teorii ewolucji Darwina i faktycznego przeżycia najsilniejszego modelu w akcji jest po prostu zdumiewająca.

Nigdy wcześniej tak naprawdę nie zajmowałem się algorytmami genetycznymi i zdecydowałem, że nadszedł czas, aby zacząć. A czy jest lepsze miejsce na start niż na początek, prawda? W tym samouczku utworzę „kij”, a ten kij chce dotrzeć do „koła”. Wnioskuj z tego, co będziesz, ale piszę tutoriale dla rodzin i tak pozostanie.

Inspiracją do tego jest czerpanie niewiarygodnie dużego wpływu z The Coding Train: Coding Challenge # 29. Link do tego tutaj. Zainspirował go Smart Rockets, więc chociaż nie robię nic nowego ani oryginalnego, mam nadzieję, że posłuży jako przykład algorytmu ewolucji genetycznej. Korzystam z biblioteki P5.JS, którą podsumowałbym jako wizualną bibliotekę JavaScript.

Zanim będę mógł stworzyć jakikolwiek algorytm genetyczny, najpierw muszę skonfigurować rzeczywiste ustawienie. Najpierw tworzę bardzo prostą stronę HTML.

Mam dwie biblioteki dla P5. Główny obsługuje rysowanie na ekranie, tworzenie instancji zmiennych itp. Kij to linia, która będzie się ewoluować, populacja to zbiór patyków, a DNA uważam za rdzeń algorytmu genetycznego. Rzućmy okiem na kod Stick:

Więc kij ma kilka podstawowych funkcji. Musi być w stanie się poruszać, więc ma „silnik” ruchu (z braku lepszego terminu) w zmiennych prędkości, przyspieszenia i położenia. W tej chwili cały ruch jest kontrolowany przez tajemniczą funkcję DNA. Zanim przejdziemy do DNA, spójrzmy na populację:

Ludność naprawdę nie jest tak interesująca. Tworzy 25 patyków, które moim zdaniem są wystarczające dla populacji, a następnie przesuwa je na ekranie. Nie przekraczaj barier dzięki tej funkcji! DNA:

W tym momencie DNA w zasadzie nic nie robi. Jeden kij otrzymuje jedno DNA, a jedno DNA ma zestaw 200 genów, co stanowi długość życia mojego małego kija. Nie martw się, więcej zostanie dodane w odpowiednim czasie. Główny plik:

Więc Main robi tutaj całkiem sporo rzeczy. Po pierwsze, musimy stworzyć nową generację kijów, która jest instancją populacji, a następnie tworzymy nasze koło, do którego kij będzie dążył później. Następnie rysujemy wszystko na ekranie, z dodatkową możliwością zabijania i tworzenia nowej generacji, za każdym razem, gdy kończy się ich cykl życia.

Jeśli więc uruchomimy to w obecnej postaci, otrzymamy:

Zdezorientowane małe laski

W tym momencie nie jest to wcale algorytm genetyczny. Zamiast tego jest to zestaw drążków poruszających się w losowo wybranych wektorach, z kropką narysowaną na ekranie. Dodajmy więc część genetyczną.

Dlatego chcemy, aby kij, który czyni go najdalej, najbliżej kręgu, był kijem, który przekazuje swoje geny swoim dzieciom. Zasadniczo jest to przetrwanie najsilniejszych: kto przeżyje najdłużej, jest tym, który przekazuje swoje geny.

Możemy więc zacząć wdrażać to, nadając każdemu kijowi nową zmienną: fitness.

var fitness = 0

Sprawność zostanie obliczona na podstawie aktualnej pozycji drążka w stosunku do pozycji koła (celu). Możemy zaimplementować to jako funkcję, aby obliczyć Fititness na każdym drążku.

this.calculateFitness = function () {
var distance = dist (this.pos.x, this.pos.y, target.x, target.y)
this.fitness = 1 / dystans
}

Teraz mamy kije, które mają ocenę sprawności - tj. Mają lepsze geny, ponieważ przetrwały dłużej. Więc teraz potrzebujemy sposobu na odtworzenie tych patyczków z genami najwyższego poziomu. Wejdź do puli:

Zatem pula ta jest stosunkowo prosta w koncepcji. Ustaliliśmy już powyżej, że najbardziej skuteczne geny to te, które są najbliżej kręgu. Im bliżej jest laski, tym więcej razy genom zostanie wprowadzony do puli i tym bardziej prawdopodobne jest, że się rozmnaży. Kij, który sprawił, że 5% drogi, będzie miał 5% szansy na rozmnażanie, podczas gdy kij, który sprawił, że będzie to 70% drogi, będzie miał 70% szansy na reprodukcję. Mam nadzieję, że wyjaśniłem to wystarczająco dobrze. Bardziej skuteczny kij = większa szansa na odrodzenie się w ramach nowego kija.

Powyżej są dwie nowe funkcje. Selekcja, jak sama nazwa wskazuje, polega na wybraniu genów macierzystych z puli genów. Geny te są następnie łączone, tworząc nowe DNA w krzyżówce, które z kolei jest następnie przypisywane do nowego kija! To wszystko, ponieważ chcemy zachować to stosunkowo proste i szczątkowe.

Całkiem fajnie, nasze kije są teraz w stanie wykorzystać najlepsze umiejętności poprzedników i użyć ich do znalezienia kręgu! Jeśli teraz spojrzymy na to w akcji:

Wciąż zdezorientowane, ale nieco mądrzejsze kije.

Po kilkudziesięciu iteracjach zaczyna wyglądać, jakby wymarły, ponieważ widać tylko kilka linii. Ale tak nie jest: im lżejszy drążek, oznacza to, że wiele drążków podąża dokładnie tą samą ścieżką. Tego należy się spodziewać, ponieważ mamy stosunkowo ograniczoną pulę genów.

Bardzo sprytne kije alfa.

Im dłużej działa, tym bardziej na ekranie pojawi się tylko jeden drążek. Ten kij reprezentuje optymalny kij! Wybrany kij. Oto one, kulminacja naszego algorytmu genetycznego:

Genialny kij (ki)!

To jest algorytm ewolucji genetycznej, napisany całkowicie w przeglądarce! Oczywiście nie jest to doskonały przykład ewolucji genetycznej, ale jest to dobry przykład tego w pracy. Nasz mały kij może teraz przejść do kręgu, a co dalej, nie jest tematem na dziś.

Jak wspomniano na początku, jest to pod silnym wpływem The Coding Train. Link do ich repozytorium.

Mój pełny kod.