Ewolucja węża

31.08.2011 - Tomasz Urbański i Tomasz Kupczyk
TrudnośćTrudność

Prezentujemy nową grę na portalu: snake.

Informatyka pełna jest problemów tak trudnych, że konwencjonalne metody zawodzą. Czy warto rezygnować, kiedy je napotykamy ? Nie ! Czas podpatrzyć naturę i przestać się bać wszelkich problemów. A wszystko na przykładzie kultowej gry Snake.

STARY, DOBRY WĄŻ

Niemal wszyscy znają grę Snake. Ta kultowa gra wymyślona w połowie lat siedemdziesiątych doczekała się setek różnych odsłon i zagościła na niemal każdej platformie zdolnej do uruchamiania gier. By uzyskać jak najlepszy wynik w grze, czyli skonsumować jak największą liczbę obiektów, najczęściej owoców, niezbędna jest dobra zręczność i odpowiednia strategia manewrowania ciągle wydłużającym się wężem. Dodatkowym utrudnieniem w grze są przeszkody, o które wąż może się rozbić. Pomimo tego, możliwe jest stworzenie takiego automatycznego sterowania wężem, które znacząco przybliży nas do optymalnego wyniku w grze. Rozwiązanie podsuwa nam tutaj sama natura.

NIEZASTĄPIONA NATURA

Ponad 150 lat temu w dziele „O powstawaniu gatunków” Karol Darwin stworzył podwaliny teorii ewolucji, która przez dziesięciolecia została podparta wieloma dowodami Dzięki opisanej przez niego teorii wiemy jak powstają nowe gatunki i w jaki sposób natura kieruje ich przetrwaniem. Wykorzystamy tę wiedzę w celu rozwiązania naszego problemu.

Jak jednak stworzyć super węża zdolnego do zjedzenia jak największej ilości pożywienia? Przypatrzmy się w jaki sposób natura wyostrza cechy niezbędne dla przetrwania. Dzięki selekcji osobników przy życiu utrzymują się tylko te o określonych, preferowanych w danych warunkach cechach. Dzięki mechanizmom takim jak mutacja czy krzyżowanie osobników, możliwe jest wyostrzenie danej cechy w kolejnym pokoleniu (krzyżowanie osobników) lub powstanie nowej (mutacja). Reguły te możemy wykorzystać w wirtualnym świecie naszego węża.

Jeżeli z danej grupy węży wybierzemy tylko te, które potrafią zjeść najwięcej pożywienia, to w kolejnej generacji otrzymamy potomstwo, które będzie zawierało preferowaną przez nas cechę łakomstwa. Proces możemy kontynuować tworząc coraz to lepsze generacje węży, aż stworzymy węża który spełni nasze oczekiwania. Część wyselekcjonowanych węży dodatkowo mutujemy w wyniku czego otrzymujemy węże o losowych cechach, tzn. takie, które będą zdolne zjeść ogromną, pośrednią lub znikomą ilość jedzenia.

By zapobiec zmniejszeniu liczby węży i utrzymać stały rozmiar populacji równy temu sprzed selekcji, po każdym etapie tworzymy dodatkowe, losowo wygenerowane, węże. Następnie będziemy wybierać tylko te węże, które są zdolne do zjedzenia jak największej liczby pożywienia. Opisany poniżej schemat postępowania, w pseudokodzie, nazywamy algorytmem ewolucyjnym.

1. Stworzenie populacji początkowej
2. Selekcja – wybranie osobników o najlepszych cechach w
   danej populacji
3. Krzyżowanie – i mutacja wyselekcjonowanych osobników 
4. Wygenerowanie dodatkowej – liczby węży w celu uzupełnienia
   wielkości populacji sprzed selekcji
5. Jeśli nie uzyskano satysfakcjonującego wyniku, wykonujemy
   operacje 2.
6. Wybór najlepszego osobnika.

Kolejnym krokiem na drodze do stworzenia naszego „super” węża, jest upodobnienie go, w bardzo ograniczonym stopniu, do żywej istoty, która czasem podejmuje decyzje dobre, a czasem złe.

5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com