Planeta Małp II – Zemsta Binarców

To nie jest notka o filmie “Planeta Małp 2″. Oficjalnym sequelem oryginalnej “Planety Małp” był film “W podziemiach planety małp”. Jeśli szukasz recenzji tego filmu, zajrzyj na IMDb, albo Filmweb. Jeśli szukasz napisów, idż na napisy.info. A jeśli torrentów, spróbuj isohunt.com. Tutaj piszę o algorytmach ewolucyjnych na przykładzie stu małp piszących Hamleta, losowo stukając w klawisze na maszynach do pisania. Wybrałem ten tytuł bo mi się spodobał.

Tym razem był mały obsuw, ponieważ pogoda zrobiła się ładniejsza i wróciłem do jeżdżenia do pracy na skuterze. Ale teraz znowu jest brzydko. Poniższy wpis to drugi odcinek opowiadania o algorytmach genetycznych z końca października. Pierwszą część możecie przeczytać tu.

Często terminów „algorytmy genetyczne” i „programowanie ewolucyjne” używamy zamiennie, zwłaszcza jeśli rozmowa ma miejsce na imprezie, w towarzystwie osób które coś tam jakoś tam wiedzą o informatyce, a cała dyskusja ma na celu zabicie czasu i polega na wzajemnym przerzucaniu się mało wiarygodnymi ciekawostkami. Również na tym blogu czasem będę przymykał oko na dość niewielkie różnice techniczne pomiędzy tym, o czym piszę, a tym jakiego terminu użyłem – zwłaszcza jeśli zamiast konkretnej nazwy użyję terminu bardziej ogólnego (co w gruncie rzeczy oznacza, że nie zrobiłem błędu). W rzeczywistości jednak terminy te, podobnie jak wiele innych używanych w programowaniu ewolucyjnym, mają bardzo dobrze określone definicje.

Algorytm ewolucyjny to taki, w którym chromosom opisuje dowolną abstrakcyjną strukturę danych, a mutacje polegają na zmianie znaków tej struktury na inne, ale wciąż należące do zbioru znaków mających sens w kontekście tej struktury. Dla przykładu, algorytm ewolucyjny może szukać funkcji o pewnym określonym kształcie, która będzie jak najlepiej pasować do zbioru uzyskanych próbek, co do których mamy podejrzenie, że nie są losowe i w efekcie być może, jeśli dopasujemy do nich jakiś rozsądny wielomian, będziemy mogli przewidywać, jakie wartości będą miały próbki pobrane w przyszłości. Próbki w naszym przykładzie to zbiór punktów (x,y). Założyliśmy, że dla naszych potrzeb wystarczy funkcja opisana wzorem y=ax^3 + bx^2+cx+d, Nasz algorytm ewolucyjny będzie miał więc za zadanie znaleźć takie współczynniki a, b, c i d, by wykres funkcji przechodził jak najbliżej punktów-próbek. Spójrzcie na wykres poniżej:

Niebieskie kwadraty to punkty-próbki. Pomarańczowe romby to wykres funkcji y=0.1*x^3+0.1*x^2+0.1*x-1. (Pomarańczowe romby powinny tak naprawdę być pomarańczową linią, ale OpenOffice mnie nie lubi i nie pozwala na wykresie mieć równocześnie punktów i linii).

Nie jest to najlepsza możliwa funkcja i algorytm ewolucyjny miałby tu jeszcze sporo do roboty, ale dość dobrze ilustruje, o co mi chodzi. Współczynniki, którymi algorytm może się bawić, to a=0.1 , b=0.1 , c=0.1 i d=-1. I tu właśnie ma miejsce różnica pomiędzy binarnym, a nie-binarnym trybem reprezentacji danych. W trybie nie-binarnym mutacje będą po prostu zmieniać współczynniki (mogą też wprowadzać nowe, dla większych wykładników, albo kasować stare ustawiając je na zero, ale to szczególne przypadki i nie chcę tu o nich mówić). W trybie binarnym współczynniki zamieniamy na ciąg bitów, a mutacje polegają na prostej zmianie wartości losowo wybranego bitu, z 0 na 1, lub z 1 na 0. Następnie, po przeprowadzeniu mutacji, odcyfrowujemy ciąg bitów z powrotem we współczynniki funkcji, i patrzymy co nam wyszło.

Zaletą takiego podejścia jest fakt, że fragment algorytmu zajmujący się mutacjami nie musi nic wiedzieć o tym, co reprezentuje chromosom. Wcześniej co prawda również nie musiał wiedzieć, że zmieniane przez niego liczby to współczynniki wielomianu, ale musiał przynajmniej mieć pojęcie, że operuje na liczbach. Jeżeli więc w programie przeprowadzalibyśmy dwie różne ewolucje, np. jedną na współczynnikach wielomianu, drugą na linijkach tekstu, to nie moglibyśmy skorzystać w przypadku mutacji z tego samego kodu. Jeśli natomiast użylibyśmy trybu binarnego, to zarówno współczynniki jak i tekst traktowalibyśmy jak ciąg bitów i kod zajmujący się mutacji zadziałałby tak samo.

W szczególnych przypadkach tryb binarny może nam pomóc również w inny sposób. I tu nadszedł w końcu moment, by wrócić do przykładu z małpami piszącymi wiersze, poprzedniej notki o AG. Mam nadzieję, że po tym nudnym, teoretycznym wstępie o funkcjach, współczynnikach i przybliżaniu, zrozumienie o co chodzi w chromosomach reprezentujących poematy i małpach walących w klawiaturę będzie już czystą przyjemnością i spacerkiem. Przynajmniej dla tych, którzy jeszcze nie usnęli.

Na pewno pamiętacie Szymborską.

Szymborska w wyniku pozytywnej mutacji była w stanie prawidłowo napisać aż 0.2, czyli 20% przypisanej sobie linijki. Pozostałe małpy, wszystkie 749, były w stanie prawidłowo napisać tylko 10% (0.1). Jedna pozytywna mutacja na siedemset pięćdziesiąt to niewiele, ale w trybie tekstowym, gdy mutacja polega na zmianie jednej litery na inną i w związku z tym zdecydowana większość mutacji jest neutralna – czyli nieprawidłowy znak ulega zmianie na inny nieprawidłowy – to nic niezwykłego. I w zasadzie gdybyśmy użyli trybu binarnego wyłącznie do przeprowadzania mutacji, to również niewiele by zmieniło. Na szczęście dla nas w tym konkretnym przypadku trybu binarnego możemy użyć nie tylko w mutacjach, ale również w funkcji ewaluacyjnej.

W przykładzie z małpami, w trybie tekstowym, działanie funkcji ewaluacyjnej polegało na zliczaniu, ile liter w linijce napisanej przez małpę zgadza się z tekstem, do którego dążymy. Oznaczało to, że w linijce składającej się z 50 znaków, jeśli wszystkie te znaki są błędne, a możliwych liter jest 32 (26 liter alfabetu łacińskiego, plus spacja, przecinek, kropka, myślnik, znak zapytania i wykrzyknik), to tylko jedna na trzydzieści dwie mutacje będzie pozytywna (spowoduje zmianę litery na prawidłową), podczas gdy w pozostałych trzydziestu jeden przypadkach wynik będzie neutralny – dojdzie do zmiany nieprawidłowej litery na inną nieprawidłową. Jeżeli natomiast linijka jest już po pewnej ewolucyjnej obróbce i część liter jest prawidłowa, dochodzą nam jeszcze mutacje negatywne – przypadkowe zmiany liter prawidłowych na nieprawidłowe. Zastosowanie trybu binarnego w funkcji ewaluacyjnej oznacza, że zarówno chromosom, jak i docelową linijkę tekstu, konwertujemy na ciągi bitów i porównujemy je ze sobą bit po bicie. Koniec końców, chodzi nam o to, by linijka powstała na podstawie chromosomu była identyczna z tą, do której dążymy, a więc i reprezentujące je ciągi bitów powinny być identyczne.

Jeżeli możliwych liter jest 32 to potrzebujemy przynajmniej pięciu bitów do reprezentacji jednej litery. 2^5=32 to dokładnie tyle, ile nam potrzeba. Gdyby zdarzyło się, że istnieją kombinacje bitów nie reprezentujące żadnej litery, należałoby te wolne miejsca uzupełnić jakimiś znakami specjalnymi.

Następnie zamieniamy litery na bity według tabelki:

a	0 0 0 0 0	i	0 1 0 0 0	q	1 0 0 0 0	y	1 1 0 0 0
b	0 0 0 0 1	j	0 1 0 0 1	r	1 0 0 0 1	z	1 1 0 0 1
c	0 0 0 1 0	k	0 1 0 1 0	s	1 0 0 1 0		1 1 0 1 0
d	0 0 0 1 1	l	0 1 0 1 1	t	1 0 0 1 1	,	1 1 0 1 1
e	0 0 1 0 0	m	0 1 1 0 0	u	1 0 1 0 0	.	1 1 1 0 0
f	0 0 1 0 1	n	0 1 1 0 1	v	1 0 1 0 1	-	1 1 1 0 1
g	0 0 1 1 0	o	0 1 1 1 0	w	1 0 1 1 0	?	1 1 1 1 0
h	0 0 1 1 1	p	0 1 1 1 1	x	1 0 1 1 1	!	1 1 1 1 1

Tak więc nasze docelowe „Ala” zamieni się w „000000101100000”, a wystukane przez małpę „Alf” w „000000101100101”. W trybie tekstowym funkcja ewaluacyjna stwierdzi, że dwie litery na trzy są prawidłowe, czyli wynik wynosi 0,666…, a w trybie binarnym trzynaście bitów na piętnaście, czyli 0,8666… Inny wynik to jednak nie jedyna różnica. Załóżmy, że następuje kolejna mutacja, znowu na ostatniej literze i w rezultacie powstaje wyraz „Alb”. Wynik funkcji ewaluacyjnej wynosi więc nadal 0,666… – mutacja jest neutralna. Jednakże jeżeli analogiczną mutację przeprowadzimy w trybie binarnym, otrzymamy poprawę wyniku. Zamiana „Alf” na „Alb” odpowiada w trybie binarnym zamianie „000000101100101” na „000000101100001”, a więc teraz już czternaście na piętnaście bitów jest prawidłowych. Co więcej, w trybie binarnym funkcji ewaluacyjnej nie istnieją mutacje neutralne. Każda zmiana bitu powoduje zmianę wyniku funkcji ewaluacyjnej, ponieważ bit może mieć tylko jedną z dwóch wartości, czyli albo prawidłową, albo nieprawidłową. Nie ma takiej możliwości, by w trybie binarnym nastąpiła zmiana wartości z nieprawidłowego na inną nieprawidłową. Ta właściwość trybu binarnego przydaje się w dwóch sytuacjach:

1. Na początku procesu ewolucyjnego, gdy większość liter jest nieprawidłowa i w trybie innym niż binarny bardzo łatwo o mutacje neutralne, co spowalnia ewolucję.
2. I na końcu, gdy do zoptymalizowania pozostały tylko pojedyncze znaki, ale trudno „trafić” ich prawidłowe wartości przy pomocy losowych zmian. W takiej sytuacji tryb binarny, gdzie na każdy znak przypada co najmniej kilka bitów, daje na kilkakrotnie większą szansę.

Na obronę trybu tekstowego (i wielu innych trybów nie-binarnych) mogę powiedzieć, że jeśli już mutacja w takim trybie jest nie-neutralna, to zazwyczaj powoduje ona dużo większą zmianę w wyniku funkcji ewaluacyjnej, niż mutacja w trybie binarnym, co przekłada się na szybszą propagację mutacji pozytywnej i szybsze wyparcie mutacji negatywnej. No i, oczywiście, tryb binarny nie jest zbyt elastyczny. W wielu przypadkach nie można z niego skorzystać, a w innych przełożenie współczynników na ciąg bitów w fazie mutacji, oraz otrzymanego wyniku na ciąg bitów w funkcji ewaluacyjnej, jest trudne i nie daje dużej przewagi nad innymi trybami. To tylko nasz przykład z linijkami tekstu jest o tyle wyjątkowy, że zamiana ciągu liter na ciąg bitów jest bezproblemowa i w obydwu fazach wygląda tak samo.

Inną cechą trybu binarnego jest fakt, że ponieważ operuje on na bitach, a nie na zrozumiałych dla człowieka literach lub współczynnikach, często zdarza się tak, że dopiero pod koniec procesu ewolucyjnego jesteśmy w stanie zobaczyć podobieństwo wyników algorytmu genetycznego do pożądanego rezultatu. Spójrzcie na proces pracy mojego programu w trybie binarnym, a następnie porównajcie go z trybem tekstowym z poprzedniej notki:

mutations = 0.4
we use binary genomes
text size = 8
you look at trees and label them just so,
(for trees are "trees," and growing is "to grow")
you walk the earth and tread with solemn pace
one of the many minor globes of space:
a star's a star, some matter in a ball
compelled to courses mathematical
amid the regimented, cold, inane,
where destined atoms are each moment slain.
number of genomes = 6000

----- generation = 0 -----
yq|)|?v4|| |%j ,21||&y|%w|mo|wb-,!?s1|@e-w)?zrm(b$ : 0.5674603
|5$g|"@||w|*|f|ob)vsw*')||0)|;2|b:2)!p|qt,:|y2?a;u : 0.53333336
!0re?fvaunpf;i!yl!|e(%r|y,|40r$r@-irqv-|%btp3mj3.y : 0.60507244
01$f||6|?h|51;||)l$u5| eeny"|| imz*dkjwx)jpc  "3zh : 0.5940171
not;-?%%;m6|s|,|*|r:!|i||u|y"|s||'?|j5wt(|vfjkjc|c : 0.6111111
vn|l!?|)b4(, yex0|j6y&||tjg;zs|h$zm2".*%le|-,xi|dc : 0.61764705
|m2)*rcr*|@4uuo'a|mbd4xnv4'wax,a1-,$p6pnf))eb1ih|| : 0.627451
 |4)5)0|)bojmy dmcl1.i3nyo*1|;6j|w4nyod1%.-w-mu,|| : 0.6098485
chromosomes = 6000
.........................
----- generation = 25 -----
t1|60|g6'|5|-ya,sg*2oy"-p$mk|wcf *|s0;so:|)?zrm(b( : 0.68650794
| mf-"s:ww|4|g?%f*vqw6%63|043)npc&3)(r|ptm:xsoq(;d : 0.67333335
t2rc?agiutpf;aasl4(einctye440p(rj-zkqv,|-bdro|j3.y : 0.70289856
n3,g|x61ih ,1lv)%ho3b|:emfwn | avzbbgbhx)j!c  "3z; : 0.6837607
h'ule!)';e |r|d|*w2$4|mi|tyy'3v||'q|hi|t$|vfjjjc|c : 0.7136752
so$ha||'b5ig aoq0||c@$||tbghrz|i$wm2".*%le|-,zi|dc : 0.6862745
aml"@pcf |sa2fg'q.mc:|zny4 ikqga||,$p6pn-))eb1ih|| : 0.7254902
s(dj5 0yz|mnepcddgm1-a3ljg6$|44o;|luvkly"f-|-lu,a| : 0.72727275
chromosomes = 6000
.........................
----- generation = 50 -----
you lko('te6-ya,s:6fo 04rel'|wg$ )|s0'so:|;?sro;b1 : 0.8492063
(fmu ts|tq||rf'"u*vqz $ of06oropi&g)(r@$|m uro|;;d : 0.83
tor5|aokguwe5mast|5a&dctse|dcw(tw6zkmyg%-p|co|j2"z : 0.8695652
on$ ko 0he exnv'"ioor|geobyf |-kcpbsef|x)jpc g"oyh : 0.8504273
i'q0a*)c6a @t,t|*r2$e mattyy kf'a'pahh||(|v-jkjc|c : 0.8717949
comwa"had 1o co3rqdc $xthheatk a"bm2".!nne|-5qm1fc : 0.8872549
amll t|d teal1gnyee:5c3lf5 ikqne,|,$p6t2-)'abxml|0 : 0.8872549
w;dre teztinet dtgmy aymbgbs| lom|ltgkla$%.|-lu,|| : 0.88257575
chromosomes = 6000
.........................
----- generation = 75 -----
you look'ad6trees cne libel'|hem just so,|)?zri(f( : 0.96825397
(for ts,eq |rg "urgys,$ ifd vropi%g is "tm vrow;)| : 0.9433333
yor walk:the marth aodctreadcwith zomeen pace|j3.| : 0.9673913
one of 0he@mqny min3r5globtr ob space:|x|jpa 5|3zj : 0.96153843
a star)s a stap, snme matter in'q ball|u;|tfy'yc|c : 0.97863245
compelled to coursds mqthdmatical|m2|.*%ne!-$xi|,b : 0.9852941
amid the reemmented, cold, inane,|,$p pb-;)ebxih|| : 0.99019605
w;ere destinet atoms aye6each loment slain.|-1fe|| : 0.9810606
chromosomes = 6000
......................you look at trees and label them just so, : 1.0
(for trees are "trees," and growing is "to grow") : 1.0
you walk the earth and tread with solemn pace : 1.0
one of the many minor globes of space: : 1.0
a star's a star, some matter in a ball : 1.0
compelled to courses mathematical : 1.0
amid the regimented, cold, inane, : 1.0
where destined atoms are each moment slain. : 1.0
--- finished after 122 turns.

A na koniec zagadka: Dlaczego w trybie binarnym wyniki funkcji ewaluacyjnej zaczęły się od wartości trochę powyżej 0,5 , a nie jak w przypadku trybu tekstowego, od okolic 0,1? Przecież pierwsze linie tekstu są losowane i w niczym nie przypominają „Mythopoei”.

Zwycięzca otrzyma jedną pozytywną mutację dla swoich przyszłych dzieci