Algorytmy Genetyczne


Praca na konkurs "Zobaczyć Matematykę".
Autor: Krzysztof Stasiowski kl. II MP
IV Liceum Ogólnokształcące im. Stanisława Staszica w Sosnowcu

Część I - Wprowadzenie


Czym tak właściwie jest algorytm genetyczny? Algorytm genetyczny, inaczej: ewolucyjny, to algorytm - czyli schematyczna metoda postępowania - służący do odnajdywania optymalnego rozwiązania danego problemu. Algorytm taki sprawdza wiele różnych rozwiązań, po czym wybiera te, które są na danym etapie najlepsze, i na ich podstawie tworzy dużą ilość nowych rozwiązań. I tak w kółko. W ten sposób, metodą małych kroczków, dąży w kierunku coraz lepszych rozwiązań.

Wyobraźmy sobie klasę, w której nauczyciel przeprowadził kartkówkę - w postaci testu wielokrotnego wyboru - z zupełnie nieznanego uczniom materiału, dając im możliwość jej poprawiania w nieskończoność. Uczniowie napisali test, strzelając odpowiedzi, i - jak można się było spodziewać - prawie wszyscy dostali jedynki, i tylko paru "szczęśliwców" przypadkiem trafiło dobre odpowiedzi i dostało dwóję.

Sprytni uczniowie zapamiętali jednak, jakie były odpowiedzi w pracach, które otrzymały najwięcej punktów, po czym na najbliższej poprawie testu skorzystali z tych właśnie odpowiedzi, wprowadzając jednak niewielkie zmiany. I znów - niektórzy uczniowie napisali gorzej, inni lepiej. Ponieważ jednak tym razem ich odpowiedzi na teście stanowiły niewielką modyfikację prac "dwójkowych", w całej klasie znalazło się parę osób, które dostało tróje! Na kolejnej poprawie uczniowie zrobili znów to samo. Skopiowali odpowiedzi z kilku najlepszych prac, wprowadzili niewielkie zmiany i oddali prace nauczycielowi. I tak dalej. W efekcie po pewnym czasie cała klasa napisała klasówkę na piątkę.

Na tym mniej więcej polega idea algorytmów ewolucyjnych. Można by teraz zadać pytanie, co to ma właściwie wspólnego z genetyką albo ewolucją? Otóż budowa tych algorytmów została zaczerpnięta z nauk przyrodniczych. Pojęcia "genetyki" i "ewolucji" są nam lepiej lub gorzej znane z lekcji biologii. Dla celów tej prezentacji zupełnie wystarczy proste, intuicyjne zrozumienie tych terminów; zacznijmy więc od ich wyjaśnienia.

Czemu algorytm "genetyczny"?


Genetyka (ze starożytnej greki: γένεσις genesis – "pochodzenie") – nauka o dziedziczności i zmienności organizmów, które są oparte na informacji zawartej w podstawowych jednostkach dziedziczności – genach.
Wikipedia

Przetłumaczę to może "na ludzki". Genetyka to nauka o genach zawierających w sobie informację o wszystkich cechach danego organizmu - kolorze skóry, kolorze oczu, ilości kończyn... wszystkim! Gdy dwa osobniki danego gatunku tworzą potomka, ich informacja genetyczna zostaje połączona: dziecko nosi więc geny obojga rodziców - czy natomiast zostanie wybrana "wersja" danego genu pochodząca od ojca czy od matki - ustalane jest losowo.

Przypuśćmy, że jeden rodzic ma niebieskie oczy, a drugi: zielone, zaś oboje mają brązowe włosy. Biorąc pod uwagę samo "mieszanie" genów rodzicielskich, dziecko będzie miało więc albo niebieskie, albo zielone oczy, zaś jego włosy będą na pewno brązowe.

Animacja obok pokazuje "dziedziczenie" różnych wersji tego samego genu - w sumie dla 7 genów - gdzie różne "wersje" symbolizowane są przez różną długość pionowych kresek. "Pajęczaki" obok służą zilustrowaniu, jak odziedziczenie jednej z kopii genu wpływa na "dziecko". Spróbuj odgadnąć, za jaką cechę odpowiada każdy z genów!

Całe piękno i kreatywność ewolucji polega jednak na tym, że dziecko rodziców, którzy mają oczy niebieskie i zielone, może mieć oczy brązowe! Przyczyną tego jest mutacja, czyli uszkodzenie informacji genetycznej. Mutacje wprowadzają zmienność w genotypie dziecka, co na poniższej ilustracji symbolizowane jest przez niewielką zmianę długości kreski - w trzech, losowo wybranych miejscach. W rzeczywistości w świecie biologicznym mutacje zachodzą - całe szczęście! - znacznie rzadziej.

Przedstawiony tu opis genetyki jest oczywiście skrajnie uproszczony i wszyscy czytający to biolodzy z pewnością chcą mnie właśnie pogonić. Piękno algorytmów genetycznych polega jednak na tym, że dokładniejsze zrozumienie genetyki wcale nie jest potrzebne!

Czemu algorytm "ewolucyjny"?


Ewolucja (łac. evolutio – rozwinięcie, rozwój) – ciągły proces, polegający na stopniowych zmianach cech gatunkowych kolejnych pokoleń wskutek eliminacji przez dobór naturalny lub sztuczny części osobników (genotypów) z bieżącej populacji. Wraz z nowymi mutacjami wpływa to w sposób ciągły na bieżącą pulę genową populacji, a przez to w każdym momencie kształtuje jej przeciętny fenotyp.
Wikipedia

W kontekście algorytmów genetycznych ewolucję można rozumieć jako ciągłą zmianę populacji aż do osiągnięcia przez nią stanu optymalnego - który identyfikuje się z rozwiązaniem problemu.

Zarówno w świecie istot żywych, jak i w algorytmach genetycznych, zmiana cech populacji wynika z doboru naturalnego - eliminacji najgorzej zaadaptowanych osobników z puli genów populacji, oraz rozmnażania się osobników najlepiej zaadaptowanych.

Rozpowszechnianie się w populacji genomów tych najlepiej zaadaptowanych osobników - oraz ciągłe niewielkie modyfikacje tych genomów poprzez mutacje - pozwalają na osiągnięcie rozwiązania. (Warto zauważyć, że w świecie biologicznym nie ma czegoś takiego, jak jedno określone "rozwiązanie problemu przeżycia" - organizmy ciągle zmieniają się, dostosowując do coraz to nowych warunków, poza tym istnieje wiele różnych sposobów, w jaki można przeżyć!

W przypadku orłów ewolucja będzie prowadziła do coraz ostrzejszych pazurków zdolnych do wbijania się w ciało ofiary; w przypadku populacji kretów - do szerokich, tępych łopatowanych, pazurów nadających się do odgarniania ziemi.)

Część II - Jak to wszystko tak naprawdę działa?


Większość Algorytmów genetycznych postępuje według następującego schematu:



Te pojęcia mogą się na razie wydawać niejasne, ale zachowajmy spokój. Za chwilę schemat ten zostanie wyjaśniony krok po kroku na podstawie naszego, algorytmu demonstracyjnego. W dalszej części strony będzie więc okazja samodzielnie "pobawić się w ewolucję", jednak zacznijmy od wyjaśnienia, na czym dokładnie polegają kolejne kroki algorytmu genetycznego.

Modelem, na przykładzie którego będziemy opisywać kroki algorytmu, jest ewolucja kolorów. Każdy z osobników cechować się będzie innym kolorem, zaś poszukiwanym rozwiązaniem jest jeden, określony, wybrany początkowo kolor. Przez stopień dostosowania się danego osobnika będzie więc rozumiana odległość "jego" koloru od koloru poszukiwanego: im bardziej zbliżona jest jego barwa do koloru docelowego, tym lepiej jest on dostosowany.

Bardzo łatwo jest wyobrazić sobie biologiczny odpowiednik takiego modelu! Wyobraźmy sobie, że nasze osobniki to łagodne, roślinożerne stworzonka - o kolorowym futerku - poruszające się po terenie o ustalonym kolorze. W powietrzu nad nimi latają drapieżniki, którym jest tym trudniej dostrzec danego osobnika, im bardziej kolor jego futerka zbliżony jest do koloru podłoża. Osobniki o futerku wyraźnie odcinającym się od koloru tła zostaną więc zauważone i upolowane z większym prawdopodobieństwem. O całej poniższej symulacji można więc pomyśleć jako o ewolucji kamuflażu!

Inicjacja - czyli jak to się zaczęło?


Pierwszym krokiem naszego algorytmu jest inicjacja, czyli stworzenie całkowicie losowej populacji. Choć na razie jest to zbiorowisko zupełnie przypadkowych osobników, tylko dzięki populacji początkowej będziemy mogli dojść do rozwiązania.

Nasza "populacja początkowa" jest to więc określona liczba osobników (przez cały czas pracy algorytmu genetycznego liczebność populacji nie ulegnie już zmianie, czyli miejsce po każdym usuniętym osobniku będzie musiało zostać uzupełnione przez nowe "dziecko") z zupełnie losowym "kodem genetycznym".

Ponieważ cała niniejsza symulacja polega na zmianie kolorów osobników, nasz "kod genetyczny" składa się z trzech genów reprezentujących 3 podstawowe kolory (czerwony, niebieski i zielony). Wszystkie komputery świata składają kolory właśnie w ten sposób; jeśli nie natrafiłeś jeszcze na ten sposób opisywania barw, zagoogluj: "model RGB".

Ocena i sprawdzian - czyli zaczynamy nowe pokolenie


W następnym kroku sprawdzamy, czy osiągnięty został zadowalający nas stan końcowy, czy też jeszcze musimy popracować nad poszukiwaniem rozwiązania. W naszym przypadku jest to pytanie, czy osobniki w naszej populacji uzyskały już odpowiedni kolor. Warunek zatrzymania algorytmu można ustalić na kilka sposobów:

  • Można go zakończyć po określonej liczbie cykli (np. po 5000 pokoleniach). Jest to najprostszy sposób wyznaczania końca, jednak rozwiązanie może być odległe od zamierzonego - trudno jest czasem przewidzieć, czy w danym przypadku potrzebnych będzie 500, czy 500 tysięcy pokoleń!

  • Po osiągnięciu określonej wartości funkcji przystosowania (np. 99% wartości maksymalnej) - tak będzie w naszym przypadku. Ten sposób pozwala uzyskać rozwiązania o określonej jakości, ale nie sprawdzi się, jeśli nie wiemy, jaka jest maksymalna dająca się osiągnąć wartość funkcji przystosowania. Algorytmy genetyczne, choć są świetną metodą, nie czynią cudów i - zwłaszcza w trudnych, złożonych przypadkach - mogą doprowadzić do osiągnięcia rozwiązania tylko, przykładowo, w 90% zbliżonych do rozwiązania optymalnego. Bywa, że i to rozwiązanie jest zupełnie satysfakcjonujące! Ba, są przypadki, kiedy nie wiadomo, jakie rozwiązanie jest optymalne, a algorytm genetyczny poszukuje na przykład zawsze tylko najwyższych wartości jakiejś zmiennej, a jego autorzy nie mają pojęcia, jaka jest maksymalna dająca się osiągnąć wartość.

  • Gdy wartość funkcji przystosowania nie zmienia się już (w określonym stopniu) z każdym kolejnym pokoleniem. Ta metoda polega więc w praktyce na zatrzymaniu się w momencie, kiedy nie ma już postępu.

  • Można również łączyć warunki końcowe, np. zakończyć algorytm, gdy osiągniemy określoną wartość przystosowania lub gdy osiągniemy określoną generację.

Niezależnie od metody zakończenia działanie algorytmu, jeżeli uda nam się zatrzymać działanie algorytmu, to jako naszą odpowiedź uznajemy najlepiej dostosowanego osobnika z ostatniej populacji.

Wybór Rodziców - czyli wybieramy geny do przekazania


Wybieranie osobników, które dostaną się do tzw. populacji rodzicielskiej - czyli przekażą swoje geny dalej - odbywa się na zasadzie zgodnie z tym, co w świecie biologii określa się jako selekcję naturalną. Krótko mówiąc: najwięcej potomków ma ten, kto jest najlepiej dostosowany. Sama już konkretna metoda wyboru tych osobników różni się w różnych algorytmach. Jedną z popularniejszych metod jest tzw. "metoda ruletki". Każdemu osobnikowi w populacji przyporządkowany jest wycinek koła proporcjonalny do stopnia jego dostosowania. Lepiej dostosowane osobniki otrzymują większy wycinek koła, więc w momencie losowania - które polega na wyborze losowego miejsca na okręgu - jest większa szansa, że trafi właśnie na nie, niż na osobniki mniej przystosowane.

W wyniku kolejnych "obrotów koła" losujemy kolejne osobniki, aż osiągniemy zamierzony rozmiar populacji. Zauważ, że ten sam osobnik może zostać wylosowany wiele razy, więc w o populacji rodzicielskiej nie powinniśmy raczej myśleć jako o podzbiorze populacji wyjściowej! W populacji rodzicielskiej teoretycznie może pojawić się każdy osobnik z całej populacji, ale w praktyce zawsze jest tak, że kilkukrotnie pojawiają się osobniki najlepiej przystosowane, a osobniki najgorzej przystosowane nie występuję w niej wcale. Właśnie ta metoda będzie stosowana w naszej demonstracji!

Istnieją również inne metody wyboru populacji rodzicielskiej:

  • "Selekcja turniejowa" - polega ona na losowym wybraniu 2-3 osobników z populacji, wyznaczeniu najlepszego z nich (tego o najwyższym parametrze dostosowania) i dodaniu go do populacji rodzicielskiej. Cały ten proces powtarzamy aż do osiągnięcia określonej liczby osobników w populacji rodzicielskiej. Również i przy tej metodzie może dojść do kilkukrotnego wybrania tego samego osobnika. W przeciwieństwie do metody ruletki, w populacji rodzicielskiej na pewno nigdy jednak nie pojawi się osobnik najgorzej przystosowany - zastanów się, dlaczego!

  • "Selekcja rankingowa" - pierwszym krokiem jest uszeregowanie wszystkich osobników według wartości ich parametru przystosowania - najlepiej przystosowane osobniki jako pierwsze, najgorzej - na końcu. Następnie według ustalonej wcześniej funkcji (np. liniowej) przekazujemy pewną ilość kopii każdego osobnika do populacji rodzicielskiej. Przykładowo, pierwszy (najlepiej przystosowany) osobnik na liście będzie zawsze reprezentowany przez 10 kopii w populacji rodzicielskiej; drugi - przez 9, i tak dalej, zaś osobniki poniżej pewnego miejsca w rankingu nie są reprezentowane wcale. Istnieje mnóstwo szczegółowych funkcji, za pomocą których można przeprowadzić selekcję rankingową.

Z uzyskanymi "rodzicami" przechodzimy do kolejnego kroku - tworzenia następnego pokolenia.

Rozmnażanie i mutacja - czyli tworzymy kolejne pokolenie

Teraz, gdy mamy już populację rodziców, możemy utworzyć kolejne pokolenie. By to zrobić, wybieramy dowolne dwa osobniki z populacji rodzicielskiej i krzyżujemy je ze sobą. Krzyżowanie polega na utworzeniu nowego kodu genetycznego na podstawie kodów genetycznych rodziców: w przypadku każdego genu nowy osobnik ("dziecko") otrzymuje jego wersję pochodzącą od jednego z dwóch rodziców. Najprostszą i najczęściej stosowaną metodą jest po prostu losowanie tego, od którego rodzica będzie pochodziła wersja danego genu. Proces ten przebiega niemal identycznie w przyrodzie.

Gdy już otrzymamy nowego osobnika - będącego na razie "mieszaniną" dwóch rodziców - jego geny mają szansę na zmutowanie. Ten proces jest niezwykle ważny! Gdyby nie istniały mutacje, nasza "odpowiedź" mogłaby się opierać wyłącznie na genach, które mieściły się w początkowej, losowo wybranej populacji. W pewnym sensie w całym tym procesie nie pojawiłaby się żadna prawdziwa innowacja. Gdyby natomiast mutacje występowały zbyt często, nasz algorytm prowadziłby do losowego, chaotycznego zgadywania odpowiedzi. Dlatego wybór częstości zachodzenia mutacji należy do najważniejszych kroków przy konstruowaniu algorytmu genetycznego.

W tym momencie kolejna "tura" ewolucji dobiega końca - otrzymujemy zupełnie nową populację, reprezentującą nowe pokolenie. Algorytm wraca więc do początku cyklu i sprawdza, jak bardzo zbliżył się do rozwiązania.

Część III - Demonstracja


Jeżeli z jakiegoś powodu jeszcze nie przeczytałeś sekcji "Jak to Działa?", polecam przeczytanie jej przed próbą zrozumienia poniższej demonstracji.

Poniżej znajduje się nasz "algorytm demonstracyjny". Jak wcześniej wspominałem ilustruje on graficznie działanie algorytmu ewolucyjnego. Kolorowe kwadraty reprezentują osobników - członków populacji. Osobniki te są tym bardziej przystosowanie im bardziej podobne do wybranego przez użytkownika koloru.

Przycisk "Krok" - - pozwala na wykonanie kolejnego kroku algorytmu, każde kolejne naciśniecie wykona kolejny krok w sekwencji. Proponuję w pierwszej kolejności zapoznanie się z chociaż jednym cyklem kroków.

Przycisk "Play" - - pozwala na włączenie "trybu automatycznego", po kliknięciu w ten przycisk, program będzie symulował kolejne pokolenia automatyczne, nie będzie trzeba klikać przycisku "Krok". Ponowne jego kliknięcie powróci nas do trybu manualnego.

Przycisk "Reset" - - pozwala na ponowne przeprowadzenie symulacji z poprzednimi ustawieniami.

Przycisk "Ustawienia" - - pozwala na zmianę koloru i wielkości populacji. Jeżeli znudzi ci się domyślny kolor lub zdecydujesz się na sprawdzenie jak wpływa na symulację rozmiar populacji wystarczy go kliknąć.

Poniżej przycisków znajduje się panel informacyjny wyświetla on wszystkie najważniejsze informacje takie jak: procent przystosowania populacji i najlepiej przystosowanego osobnika, czy numer pokolenia.


strona korzysta z tagu canvas użyj Chrome bądź Firefox

Panel Informacyjny:


Część IV - Zastosowania

Być może przez myśl przechodzi Wam w tej chwili następująca wątpliwość: OK, istnieje coś takiego jak algorytmy genetyczne, wygląda to bardzo atrakcyjne... ale czy ma jakiekolwiek zastosowanie praktyczne? Odpowiedź brzmi: tak! Algorytmy genetyczne stosowane są we wszystkich przypadkach, które matematycznie określa się jako zagadnienie minimalizacji lub maksymalizacji funkcji wieloargumentowych, a które "po ludzku" można określić jako po prostu problem optymalizacyjny - znalezienie "najlepszego" pod jakimś względem rozwiązania.

Posłużmy się przykładem. Problemem do rozwiązania jest wyznaczenie najkrótszej drogi łączącej pewną liczbę punktów - jego zwyczajowa nazwa to "problem komiwojażera", czyli wędrującego sprzedawcy. Wyobraź sobie, że patrzysz na mapę Polski, na której kropkami zaznaczone masz miasta, które musisz odwiedzić. Kolejność jest nieistotna, istotne jest tylko to, abyś w sumie pokonał jak najkrótszą drogę. Jeśli mamy na liście tylko kilka miast, problem bywa banalny. Widać na przykład od razu, że trasa Gdańsk-Katowice-Gdynia-Gliwice jest wyjątkowo złym wyborem: pokonujemy olbrzymią odległość, przejeżdżając całą Polskę z północy na południe i z powrotem, a przecież moglibyśmy przyjąć trasę: Gliwice-Katowice-Gdańsk-Gdynia, prawda?

Rzecz w tym, że przy coraz większej liczbie punktów ("miast") problem zaczyna się robić potwornie skomplikowany! Jeśli mamy do odwiedzenia 68 punktów, istnieje około 2,48 x 1096 różnych kolejności ich odwiedzenia! To bardzo dużo, więcej niż przewidywana liczba atomów we wszechświecie! Gdybyśmy chcieli sprawdzić każdą z tych możliwości, to - przy użyciu 10 największych superkomputerów świata - zajęłoby to nam ok. 9,53 x 1077 lat. Ale od czego algorytmy genetyczne?

Obok pokazany jest rezultat rozwiązywania problemu komiwojażera przez tego właśnie typu algorytm. "Genotypem" naszego osobnika jest tu kolejność przebywania przez kolejne punkty (po prostu ciąg liczb naturalnych), a wartość przystosowania wynika z przebytej odległości: im krótsza całkowita droga komiwojażera postępującego wedle określonego "genotypu", tym większe przystosowanie tego "osobnika". Jak widać, algorytm ten dość szybko znajduje bardzo rozsądną trasę. Jeżeli wierzyć Randalowi Olsonowi, twórcy tej animacji, jedna z krótszych dróg została odnaleziona w czasie około 5 min; biorąc pod uwagę że mamy tą odpowiedź jestem skłonny mu uwierzyć na słowo, mimo tego, że początkowy genotyp jest całkowicie losowy.

Jednym z ważniejszych obszarów zastosowań algorytmów genetycznych jest tworzenie harmonogramów i planowanie procesów przemysłowych. Przykładowo, zakłady chemiczne, zawierające różnego rodzaju pompy i reaktory chemiczne oraz posiadające wiele parametrów, które podlegają regulacji, stanowią bardzo trudny "poligon" dla technik optymalizacji. Jeżeli chcielibyśmy osiągnąć wynik w klasyczny sposób, niekiedy musielibyśmy czekać na niego latami, nawet przy użyciu niesamowitej mocy obliczeniowej. Natomiast wykorzystanie algorytmów ewolucyjnych pozwala na otrzymanie satysfakcjonującego wyniku w rozsądnym przedziale czasowym. Co istotne, w większości przypadków praktycznych nie jest konieczne, aby odnalezione rozwiązanie było "optymalne" w ścisłym tego słowa znaczeniu, tzn., aby nie istniało lepsze. Czasem wystarczy, aby było "wystarczająco dobre". Algorytmy genetyczne pozwalają na łatwe i elastyczne dopasowanie czasu poszukiwania rozwiązania do jakości spodziewanego rozwiązania, co stanowi ich wielką zaletę. Cóż nam po świetnej metodzie odnajdywania najlepszego rozwiązania, której zrealizowanie wymaga jednak oczekiwania wielu miesięcy na wynik?...

Innym polem do popisu dla algorytmów genetycznych jest tworzenie elementów elektrycznych i elektronicznych. Co niezwykłe, bywa tak, że "zaprojektowany" przez algorytm genetyczny elementy cechują się niespotykanym, nieprzewidzianym przez nikogo projektem, którego nie byłby w stanie wykoncypować żaden inżynier. Przykładem jest ta antena, "stworzona" przez program korzystający z algorytmów genetycznych. 22 marca 2006r. agencja NASA wysłała w przestrzeń kosmiczną trzy sztuczne satelity, w których wykorzystano ten projekt. Pojazdy te wykonały założony cel misji, zaś "wyewoluowana antena" stała się pierwszym obiektem w Kosmosie stworzonym przez algorytm genetyczny. Jej nietypowy kształt (typowe anteny stosowane przez NASA mają bardziej regularny, spiralny kształt) jest spowodowany bardzo wymagającym zestawem parametrów, jakie musiała spełnić.

Część V - O Stronie


Od strony technicznej:

Strona została stworzona w technologii HTML5/CSS3 oraz JavaScript.Algorytm Demonstracyjny to skrypt autorski (plik Algorytm1.js). Tworząc stronę wykorzystałem takie technologie jak:

  • Hover.css - kolekcja efektów najechania CSS3,
  • jQuery - biblioteka ułatwiająca korzystanie JavaScript,
  • Bootstrap 3 - framework CSS/JavaScript na którym opiera się strona,
  • Bootstrap-colorpicker - plugin pozwalający na wybór koloru.

Wykorzystane Oprogramowanie:

Przy budowie strony wykorzystałem darmowe czcionki ze strony google.com/fonts. Strona została przetestowana pod przeglądarkami Firefox, Chrome. Plik DNA.svg został stworzony przez autorski program napisany w Javie.

Bibliografia