W poprzednim odcinku cyklu przedstawiłem ogólnie jeden z aspektów sztucznej inteligencji, czyli sztuczne sieci neuronowe. Dzisiaj chciałbym się pochylić nad techniką nieco w działaniu odmienną, która jednak również zainspirowana została światem biologicznym. Mowa o algorytmach ewolucyjnych.
Ponownie zacznę od małego disclaimera – materiał ten będzie bazował na uproszczeniach. Nie będę zagłębiał się w techniczne szczegóły przedstawianej rodziny algorytmów, a zamiast tego skupię się na idei i samym pomyśle. Jak powstała koncepcja algorytmów ewolucyjnych? W jaki sposób działają? Czy prawa natury można z powodzeniem przenieść na grunt algorytmów? Pytań jest całkiem sporo, więc, aby nie przedłużać, zaczynajmy.
Czym jest ewolucja?
W połowie XIX wieku brytyjski przyrodnik i geolog Charles Darwin opublikował pracę zatytułowaną O powstawaniu gatunków, która traktowała o ewolucji poprzez dobór naturalny. Teoria zakładała, że kolejne pokolenia żywych organizmów ewoluują w kierunku lepszej adaptacji do warunków środowiskowych. Innymi słowy, przeżywają osobniki lepsze, silniejsze. Współcześnie teoria doboru naturalnego jest teorią naukową, czyli, cytując Wikipedię, „najbardziej rzetelną, rygorystyczną i kompletną formą wiedzy naukowej”. Krótko mówiąc, dobór naturalny jest faktem.
To jednak nie wszystko. Kolejnym elementem ewolucyjnej układanki okazały się wyniki eksperymentów przeprowadzanych przez niemiecko-czeskiego zakonnika i naukowca Grzegorza Mendla. Być może pamiętacie go z czasów szkolnych – to ten pan, który w drugiej połowie XIX wieku badał dziedziczenie genów na przykładzie populacji grochu. Udowodnił on, że cechy organizmów biologicznych są w jakiś sposób w tych organizmach zakodowane i mogą być dziedzicznie przekazywane następnym pokoleniom.
Wisienką na ewolucyjnym torcie stało się słowo (i idąca za nim nowa dziedzina nauki) wymyślone w 1905 roku przez Williama Batesona – genetyka. Mendel wykazał, że potomkowie w sposób losowy dziedziczą mieszankę cech obu rodziców, natomiast w 1910 roku Thomas Hunt Morgan udowodnił, że mechanizm ten ma związek z chromosomami. Już trzy lata później jego student Alfred Sturtevant potwierdził ten związek i wykazał, że geny są umieszczone w chromosomach w sposób liniowy. W kolejnych latach wiedza o genetyce była stale poszerzana, aż wreszcie dotarliśmy do momentu, w którym dysponujemy względnie kompletną i spójną teorią dotyczącą ewolucji.
Jak zaprogramować ewolucję?
Musicie wiedzieć, że w informatyce istnieje dziedzina problemów, których nie da się rozwiązać wprost. Uściślając – wymagane jest tak wiele obliczeń, że nie jesteśmy w stanie uzyskać wyniku w rozsądnym czasie. Szerzej tę sytuację opisywałem w drugiej części cyklu, więc, aby się nie powtarzać, dla przypomnienia odsyłam właśnie tam. Jednym z takich zagadnień jest optymalizacja; z tematem każdy z nas zetknął się w szkole, kiedy za pomocą pochodnych liczyliśmy ekstrema funkcji matematycznych. Zagadnienie optymalizacji jest dość szerokie, ale dla ułatwienia przez cały materiał będę posługiwał się prostym przykładem optymalizacji funkcji. Do rzeczy.
W 1975 roku John Henry Holland, amerykański naukowiec, profesor psychologii, elektrotechniki i informatyki na University of Michigan wydał książkę zatytułowaną Adaptation in Natural and Artificial Systems, w której po raz pierwszy sformułowane zostało pojęcie algorytmu genetycznego. Holland zainspirował się integracją teorii ewolucji z genetyką i postanowił sprawdzić, czy możliwe jest przeniesienie praw natury na grunt algorytmów. Ponieważ czytacie ten wpis, efektów możecie się domyślić sami. Algorytmy genetyczne okazały się zarówno proste w implementacji, jak i efektywne (w niektórych przypadkach), choć do prawdziwego odwzorowania ewolucji jeszcze bardzo, bardzo daleka droga. Mimo to znalazły zastosowanie przy rozwiązywaniu wielu nieefektywnych obliczeniowo problemów.
Algorytmy genetyczne z czasem ewoluowały (hehe) w algorytmy ewolucyjne, czyli pojęcie, pod którym współcześnie kryje się kilka różnych podejść; mamy strategie ewolucyjne, programowanie ewolucyjne, programowanie genetyczne i algorytmy genetyczne. Na potrzeby materiału potraktuję je jako jedność, to znaczy opisywał będę ogólnie algorytmy ewolucyjne. To wszystko, co przeczytaliście do tej pory, to tylko przydługi wstęp i czas przejść do prawdziwego mięska, czyli tego, co sprawia, że algorytmy ewolucyjne rzeczywiście działają.
O operatorach genetycznych
Holland w swojej pracy zdołał zalgorytmizować trzy aspekty ewolucji: dobór naturalny, reprodukcję (aspekt rekombinacji genów) oraz losowe mutacje. Mechanizmy te nazwane zostały właśnie operatorami genetycznymi, odpowiednio selekcją, krzyżowaniem i mutacją. Niektóre opracowania nie traktują selekcji jako operatora, ale jako… po prostu selekcję, nie ma co jednak wprowadzać niepotrzebnego zamieszania. To, co dla nas jest istotne, to fakt, że wszystkie operatory podlegają pewnej losowości; zupełnie tak, jak ma to miejsce w naturze.
Nadszedł czas na wprowadzenie pojęcia rozwiązania. Operatory genetyczne stosuje się właśnie na analizowanych przez algorytm ewolucyjny rozwiązaniach. W zależności od typu algorytmu analizowane jest albo rozwiązanie pojedyncze (jak w strategii ewolucyjnej), albo cała populacja bądź zbiór rozwiązań (jak w algorytmie genetycznym). W przypadku optymalizacji funkcji matematycznej (na przykład wszystkim znanej paraboli) rozwiązaniem jest argument, dla którego funkcja przyjmuje wartość najmniejszą albo największą, w zależności od problemu. Tłumacząc na ludzki – w przypadku optymalizacji funkcji argumentem jest wartość na osi X, dla której wartość na osi Y jest najmniejsza albo największa.
Istotne jest, że algorytmy ewolucyjne przetwarzają rozwiązania w postaci zakodowanej. W przypadku algorytmu genetycznego najczęściej koduje się je w sposób binarny, czyli za pomocą ciągu zer i jedynek; niezależnie od tego, jaki problem rozwiązujemy, koniecznością jest opracowanie metody zakodowania i odkodowania rozwiązań. W przypadku optymalizacji takiej funkcji matematycznej musimy po prostu zakodować argument x.
Dochodzimy wreszcie do sedna: działanie algorytmu ewolucyjnego polega na poddawaniu rozwiązania (lub rozwiązań) działaniu operatora (lub operatorów). W przypadku algorytmu genetycznego pierw oceniamy całą losowo wygenerowaną populację (pod kątem optymalności rozwiązań), następnie wybieramy osobniki najlepsze, krzyżujemy je między sobą i wprowadzamy losowe mutacje; proces ten powtarzamy w pętli. Do wszystkich operatorów opracowano różne metody, metody posiadają różne parametry, ale nie będę Was już zamęczał technicznymi szczegółami.
To jak z tą ewolucją?
Przyznam szczerze, że przy pierwszym zetknięciu się z algorytmem genetycznym nie sądziłem, że może on działać. No bo jak, losowo krzyżujemy między sobą ciągi bitów, losowo mutujemy niektóre z nich, potem (również z udziałem losowości) wybieramy osobniki najlepsze, i to niby wystarcza do tego, by z początkowej losowej wygenerowanej populacji uzyskać rozwiązanie optymalne? Okazuje się, że tak.
Wróćmy jednak do postawionego w tytule materiału pytania. Czy da się zaprogramować ewolucję? Po tym, co przeczytaliście powyżej, wydawać by się mogło, że owszem, jak najbardziej. Przecież odwzorowujemy procesy ewolucyjne i w sposób losowy, ale z wykorzystaniem zjawisk ewolucyjnych, odnajdujemy najlepsze rozwiązanie, prawda? Ugrzeczniając jeden z memów: niby tak, ale, kurczę, nie do końca.
Podstawowy zarzut skierowany do algorytmów ewolucyjnych brzmi – to nie jest odwzorowanie ewolucji, a co najwyżej adaptacja pewnych jej reguł. Adaptacja w dodatku nieproporcjonalna, a to ze względu na kilka właściwości. Przede wszystkim operatory genetyczne są bardzo uproszczone, a prawdopodobieństwo ich występowania nienaturalnie zawyżone. Ponadto populacja nie może wymrzeć, bo każda kolejna generacja (kolejne pokolenie) liczy sobie tyle samo osobników. Taki już urok poczynionych założeń.
Inny zarzut dotyczy rozmiarów genomu – najmniejszy genom świata rzeczywistego (genom pasożyta) zbudowany jest z pół miliona par zasad, które binarnie można by zakodować z wykorzystaniem ponad miliona bitów. Technologicznie to bardzo mała liczba, natomiast w przypadku algorytmu genetycznego operujemy zazwyczaj na maksymalnie kilkuset bitach; im więcej ich jest, tym mniej skuteczne są operatory genetyczne i tym trudniej dojść do optymalnego rozwiązania. Inną kwestią jest, że zazwyczaj nie potrzeba ich aż tyle.
Takich zarzutów jest znacznie więcej. Pytanie brzmi – czy rzeczywiście mają one znaczenie? Wiemy już, że nie da się perfekcyjnie zaprogramować ewolucji, ale czy musimy to zrobić jeden do jednego? Zważywszy na fakt, iż przytoczone powyżej informacje, pomimo kilkudziesięciu lat na karku nadal są aktualne – niekoniecznie. Algorytmy ewolucyjne po prostu działają; nie są uniwersalne, nie znajdują zastosowania w codziennych sprawach, ale są jedną z technik, którą można zastosować do przeprowadzania bardziej „inteligentnych” obliczeń. I tym miłym akcentem kończę dzisiejszy materiał. Do następnego!
źródła: Leszek Rutkowski Metody i techniki sztucznej inteligencji, David E. Goldberg Algorytmy genetyczne i ich zastosowania, wiki, creation / zdjęcie tytułowe z pexels
