Rozdział 2
Podstawy matematyczne algorytmów genetycznych

W rozdziale 1 nakreśliliśmy wierny, choć cokolwiek nie wykończony wizerunek algorytmu genetycznego. Być może jest to obraz apelujący do wyobrażeń Czytelnika o naturze odkrycia i procesu badawczego. To, żeby mechaniczna, choć zawierająca elementy losowe, procedura mogła osiągnąć coś z rozległości i zmysłu odkrywczego charakteryzujących proces badawczy wydaje się zbyt piękne, aby było prawdziwe. Stwierdzenie, że taka procedura odkrywania powinna być odbiciem naturalnych procesów doprowadzających do powstania gatunku, który ją posiadł, jest przykładem rekurencji godnym G6dla, Eschera i Bacha (Hofstadter, 1979). Mimo jednak ich intuicyjnej atrakcyjności i narzucającej się symetrii rozstrzygające znaczenie będzie miało uzasadnienie owych mglistych odczuć i spekulacji na podstawie chłodnej analizy za pomocą narzędzi matematycznych. W samej rzeczy, zdążyliśmy już przystąpić do ściślejszej oceny algorytmów genetycznych. Pod koniec poprzedniego rozdziału wprowadziliśmy podstawowe pojęcie schematu albo wzorca podobieństwa. Pod względem ilościowym stwierdziliśmy, że populacja ciągów kodowych zawiera istotnie wielką liczbę podobieństw nadających się do wykorzystania. Zrozumieliśmy też, na poziomie intuicyjnym, działający współbieżnie mechanizm, za pomocą którego algorytmy genetyczne wyzyskują liczne podobieństwa kryjące się w wąskich, dobrze przystosowanych schematach (cegiełkach). W tym rozdziale uściślimy nieco te obserwacje, zajmując się kilku zagadnieniami. Przede wszystkim wyznaczymy liczbę schematów reprezentowanych w danej populacji ciągów kodowych i rozważymy, które z nich rozprzestrzeniają się, a które zanikają w obrębie jednego pokolenia. W tym celu zbadamy wpływ reprodukcji, krzyżowania i mutacji na określony schemat. Analiza tego problemu doprowadzi nas do podstawowego twierdzenia algorytmów genetycznych, które określa owe prawa wzrostu i spadku w sposób ilościowy oraz wskazuje matematyczną postać procesu wzrostu. Postać tajest związana z ważnym problemem klasycznej teorii decyzji, tzw. zagadnieniem dwuramiennego bandyty (i jego uogólnioną wersją - zagadnieniem fc-ramiennego bandyty). Matematyczne podobieństwo
2.1. Kto przetrwa, a kto zginie? Podstawowe twierdzenie .
45
optymalnych (w sensie minimalnej straty) rozwiązań obu tych problemów i równania opisującego liczbę realizacji danego schematu w kolejnych populacjach generowanych za pomocą elementarnego algorytmu genetycznego jest uderzające. Policzenie schematów biorących efektywny udział w przetwarzaniu populacji ujawnia istnienie czynnika w istotny sposób potęgującego wyzyskiwanie cegiełek. Na koniec, rozważymy doniosłą kwestię: Skąd wiadomo, że składanie cegiełek jest efektywną metodą w przypadku dowolnych zagadnień? Pytanie to skieruje naszą uwagę na stosunkowo nowe narzędzie analizy algorytmów genetycznych, jakim są transformaty schematów, a także na tzw. minimalny problem zwodniczy.
2.1. Kto przetrwa, a kto zginie? _____Podstawowe twierdzenie
Działanie algorytmu genetycznego jest niezwykle proste. W końcu zaczynamy od losowej populacji n ciągów kodowych, dokonujemy ich replikacji uprzywilejowując nieco najlepsze, kojarzymy je, wymieniając fragmenty ciągów, i na dodatek mutujemy od czasu do czasu jakiś bit. Chociaż algorytmy genetyczne operują na populacji ciągów kodowych w taki właśnie prosty sposób, zdążyliśmy zauważyć już pod koniec rozdziału 1, że z tą bezpośrednio widoczną aktywnością wiąże się ukryte przetwarzanie wielkiej liczby schematów w jednym pokoleniu. Aby zanalizować w sposób ścisły zjawisko rozprzestrzeniania się i wymierania schematów obecnych w populacji, musimy wprowadzić pewne proste oznaczenia. Rozważmy zatem wpływ reprodukcji, krzyżowania i mutacji na schematy reprezentowane w populacji.
Nie tracąc ogólności zakładamy, że ciągi kodowe składają się z symboli alfabetu dwójkowego V={0, 1}. Umówimy się dla wygody oznaczać ciągi kodowe wielkimi, a ich elementy - odpowiednimi małymi literami z dolnymi indeksami określającymi pozycję w ciągu. Na przykład siedmiobitowy ciąg A = 0111000 można symbolicznie przedstawić następująco:
Każde a. reprezentuje tu pojedynczą cechę binarną (detektor) albo - w terminologii biologicznej - gen. Każda taka cecha może przyjmować wartość 1 lub 0 (nazywamy je niekiedy allelami). W konkretnym przypadku ciągu 0111000 a, jest równe 0, a^ jest równe 1, a3 jest równe 1, itd. Można także rozważać detektory, których elementy nie są uporządkowane zgodnie z numerami indeksów, jak w przypadku ciągu A. Na przykład ciąg A' mógłby być uporządkowany następująco:
W jednym z późniejszych rozdziałów zbadamy konsekwencje takiego rozszerzenia reprezentacji, aby poszczególne cechy nie były zależne od ich umiejscowienia; na razie przyjmijmy, że rodzaj cechy jest wyznaczony przez jej pozycję.
46
. 2. Podstawy matematyczne algorytmów genetycznych
Algorytmy genetyczne pracują na populacjach ciągów kodowych, będziemy więc rozważać populację A(f) złożoną z ciągów Aj,j= 1, 2,..., n, w chwili (pokoleniu) t (populacje będziemy oznaczać pogrubioną czcionką).
Oprócz oznaczeń dla populacji, ciągów kodowych, pozycji i alleli potrzeba nam jeszcze dogodnej notacji do opisu schematów reprezentowanych przez poszczególne ciągi. Rozważmy schemat H złożony z symboli alfabetu V+ = {0, 1, *}. Jak powiedziano w poprzednim rozdziale, dodatkowy symbol * (gwiazdka) to symbol uniwersalny, reprezentujący 0 lub 1 na określonej pozycji. Na przykład ciąg kodowy 0111000 jest reprezentantem schematu H=*\]*0** o długości 7, gdyż allele at pokrywają się z elementami schematu na pozycjach ustalonych 2, 3 i 5.
Przypomnijmy, że dla ciągów dwójkowych o długości / można określić 3' schematów. Ogólnie, dla alfabetu złożonego z k symboli istnieje (fc+1)' schematów. Stwierdziliśmy też, że populacja złożona z n elementów może reprezentować co najwyżej n * 2' schematów, gdyż każdy ciąg z osobna jest reprezentantem 2' schematów. Te proste obliczenia dają pewne wyobrażenie o ogromie informacji przetwarzanej przez algorytmy genetyczne; aby jednak zrozumieć do końca czym są schematy-cegiełki, z których powstają przyszłe rozwiązania, musimy wyodrębnić różne typy schematów.
Schematy nie "rodzą się równymi". Pewne schematy są bardziej określone niż inne. Na przykład schemat 011*1** jest bardziej szczegółowym wzorcem podobieństwa niż schemat 0******. Ponadto, jedne schematy (jak np. l****l*) "rozciągają się" na dłuższych odcinkach niż drugie (np. l*]****). Aby scharakteryzować liczbowo te własności, wprowadzimy dwa nowe pojęcia: rzędu i rozpiętości schematu.
Rządem schematu H, który oznaczamy przez o(H), będziemy nazywać liczbę ustalonych pozycji (w przypadku alfabetu dwójkowego jest to po prostu liczba zer i jedynek) we wzorcu. Dla podanych wyżej przykładów mamy o(011*l**) = 4 oraz
O(Q******)=1. IJ . i; ->' �..'.
Rozpiętością schematu H, którą oznaczamy przez 5(ff), nazywamy odległość między dwiema skrajnymi pozycjami ustalonymi. Tak więc, schemat 011*1** ma rozpiętość 8 = 4, gdyż jego ostatnia pozycja ustalona ma numer 5, a pierwsza - numer 1, zatem odległość między nimi wynosi 5-1=4. Dla drugiego przykładu (schemat 0******) rozpiętość wyznacza się szczególnie łatwo: ponieważ mamy tylko jedną pozycję ustaloną, pierwsza pokrywa się z ostatnią, a więc odległość wynosi 0.
Schematy stanowią interesujące narzędzie notacyjne do ścisłego badania i klasyfikowania podobieństw ciągów kodowych. Co więcej, są one podstawowym środkiem analizy wpływu reprodukcji i pozostałych operacji genetycznych na rozprzestrzenianie się "cegiełek" w danej populacji. Zbadamy teraz indywidualne i łączne skutki działania wspomnianych operacji na schematy reprezentowane w populacji ciągów kodowych.
Najłatwiej określić wpływ reprodukcji na oczekiwaną liczbę reprezentantów określonego schematu. Załóżmy, że w chwili t w populacji A(?) znajduje się m = m(H, t) reprezentantów danego schematu H (podkreślamy zależność tej liczby od schematu H i chwili t). Podczas reprodukcji ciągi podlegają replikacji z prawdopodobieństwem proporcjonalnym do wskaźnika przystosowania, dokładniej, z prawdopodobieństwem Pi=ft/^Lfj- Po skompletowaniu nowej populacji złożonej z n ciągów wybranych z populacji A(?), możemy oczekiwać obecności m(H, t+ 1) reprezentantów schematu H w chwi-
2.1. Kto przetrwa, a kto zginie? Podstawowe twierdzenie .
47
li t+ 1, przy czym zachodzi wzorm(f/, t+l) = m(H, t)-n-f(H}/^fj ". Liczba/(tf) określa średnie przystosowanie ciągów będących reprezentantami schematu W w chwili t. Jeśli uwzględnimy, że średnie przystosowanie całej populacji można wyrazić jako/= to powyższy związek możemy też zapisać w postaci
m(H, t+l)=m(H,t)
f(tf} f
Oznacza to, że liczebność reprezentacji danego schematu (w następnym pokoleniu) zmienia się proporcjonalnie do stosunku średniego przystosowania schematu i średniego przystosowania całej populacji. Mówiąc jeszcze inaczej, schematy o przystosowaniu wyższym niż średnie z populacji będą miały większą liczbę reprezentantów w następnym pokoleniu, podczas gdy schematy o przystosowaniu niższym niż średnie z populacji otrzymają mniej reprezentantów niż miały dotychczas. Warto zauważyć, że wniosek ten odnosi się w równym stopniu do każdego schematu H reprezentowanego w populacji A. Można zatem powiedzieć, że - biorąc pod uwagę samą tylko reprodukcję - wszystkie schematy w populacji rozprzestrzeniają się (lub zanikają) odpowiednio do swego średniego przystosowania. Wkrótce przekonamy się, dlaczego takie zachowanie wydaje się być pożądane. Chwilowo odnotujmy, że dzieje się tu wiele rzeczy równocześnie, choć wykonujemy tylko proste operacje na n ciągach kodowych.
Pod względem jakościowym wpływ reprodukcji na schematy jest oczywisty: schematy "lepsze" od przeciętnej rozprzestrzeniają się, a "gorsze" - zanikają. Czy możemy jednak z otrzymanej wyżej zależności rekurencyjnej wywnioskować coś na temat matematycznej postaci tego wzrostu (zaniku)? Załóżmy zatem, że pewien schemat H przewyższa średnią o wielkość cf, gdzie c jest stałą. Przy takim założeniu możemy zapisać równanie schematów następująco:
m(H,t+l)=m(H,f)tf+cf)/f=(\+c)-m(H,t) "'f;'-ri.- .,;, . *x' Startując od t = 0 i zakładając, że c nie zmienia się w czasie, otrzymujemy zależność m(H,t) = m(H,0)-(l+c)' :'.-;;^;.::;:., -,:,:
Czytelnicy obeznani z finansami rozpoznają w powyższym związku wzór na procent składany, natomiast czytelnicy zorientowani matematycznie - postęp geometryczny, dyskretny odpowiednik funkcji wykładniczej. Otrzymaliśmy zatem ocenę ilościową efektu
11 Autor pomija tu symbol wartości oczekiwanej po lewej stronie równania. Ścisłe sformułowanie omawianej zależności wygląda więc następująco ;.
E[m(H,t+\)] = m(H,t)-n-f(H)/^fj .-.. �
Wzór rekurencyjny podany w książce można uważać za aproksymację rzeczywistego procesu słuszną dla dużych populacji. Uwaga ta odnosi się również do dalszych wywodów na temat dynamiki populacji (pr?yp. llum.).
48
. 2. Podstawy matematyczne algorytmów genetycznych
reprodukcji: w procesie reprodukcji schematy lepsze (gorsze) od przeciętnej są wybierane w liczbie przypadków rosnącej (malejącej) wykładniczo w czasie. Wkrótce powiążemy ten wynik z problemem wieloramiennego bandyty, ale przedtem zbadajmy jeszcze, jaki wpływ na propagację schematów wywierają operacje krzyżowania i mutacji.
Fakt, że mechanizm reprodukcji może przekazywać do następnych pokoleń rosnące lub malejące wykładniczo liczby schematów jednocześnie, jest do pewnego stopnia niezwykły; dzięki n prostym replikacjom bardzo wiele różnych schematów zostaje wybranych równolegle według tej samej reguły. Jednakże sama reprodukcja nie przyczynia się w żaden sposób do eksploracji nowych obszarów przestrzeni rozwiązań, gdyż nie wprowadza żadnych nowych punktów; jeśli kopiujemy tylko stare struktury bez zmian, to w jaki sposób możemy kiedykolwiek wypróbować coś nowego? W tym właśnie miejscu ujawnia się rola krzyżowania. Operacja krzyżowania dokonuje uporządkowanej, choć zawierającej element przypadku wymiany informacji między dwomaciągami kodowymi. Za pomocą krzyżowania tworzy się nowe struktury w sposób minimalnie zaburzający wzorzec propagacji dyktowany przez samą reprodukcję. W efekcie końcowym frekwencje różnych schematów reprezentowanych w populacji rosną lub maleją wykładniczo w kolejnych pokoleniach.
Aby przekonać się, które schematy są wrażliwe na krzyżowanie, a które nie, rozważmy przykładowy ciąg kodowy o długości 1-1 oraz dwa reprezentatywne schematy, pasujące do tego ciągu:
A = 0111000 � >
fi^ = *l****o � � � H2 - ***10**
Ciąg A jest reprezentantem obydwu schematów Ht i H2 jednocześnie; chcąc zbadać skutek działania operacji krzyżowania na oba schematy, przypomnijmy sobie najpierw, że krzyżowanie proste obejmuje losowy wybór partnera, losowy wybór punktu krzyżowania oraz wymianę segmentu początkowego (od pierwszej pozycji do punktu krzyżowania włącznie) z odpowiednim segmentem wybranego partnera. Przypuśćmy, że ciąg A został wybrany do krzyżowania. Aby wybrać punkt krzyżowania, możemy rzucić kostką do gry (w ciągu o długości 7 jest 6 możliwych punktów krzyżowania). Przypuśćmy następnie, że w efekcie takiego rzutu wypadła nam liczba 3, co oznacza, że ciąg A zostanie rozcięty między pozycjami 3 a 4. Skutki takiego rozcięcia dla obu naszych schematów H\ i H2 są widoczne poniżej (miejsce podziału zaznaczone jest przy użyciu symbolu I):
A = 01111000
� � H} = *l*l***o vv :[i '-
H2 = ***|10**
Jeśli partner ciągu A nie jest identyczny z A na pozycjach ustalonych schematu (przypadek, który jesteśmy skłonni zaniedbać), to schemat Ht ulegnie zniszczeniu, ponieważ symbole 1 na pozycji 2 oraz 0 na pozycji 7 znajdą się w dwóch różnych ciągach potom-
2.1. Kto przetrwa, a kto zginie? Podstawowe twierdzenie .
49
nych (zajmują bowiem miejsca po przeciwnych stronach punktu krzyżowania). Jest również oczywiste, że przy tym samym miejscu podziału (między pozycjami 3 a 4) schemat H2 pozostanie nie naruszony, gdyż zarówno symbol 1 na pozycji 4, jak i 0 na pozycji 5 zostaną przeniesione bez zmian do jednego ciągu potomnego. Chociaż w tym przykładzie wybraliśmy arbitralnie punkt podziału, widać jasno, że schemat #, ma mniejsze szanse przeżycia operacji krzyżowania niż schemat H2, ponieważ, średnio biorąc, punkt krzyżowania będzie częściej wypadać między odległymi pozycjami ustalonymi.
Aby scharakteryzować tę obserwację liczbowo, zauważmy, że schemat H} ma rozpiętość równą 5. Jeżeli punkt krzyżowania zostaje wybrany losowo zjednakowym prawdopodobieństwem spośród /- 1 =7- 1 =6 możliwych położeń, to jest rzeczą oczywistą, że schemat H( będzie zniszczony z prawdopodobieństwemprf=8(ff|)/(/-ł) = 5/6 (przeżyje z prawdopodobieństwem p,= l-prf=l/6). Podobnie, schemat H2 ma rozpiętość 8(f/2)= 1 i będzie zniszczony tylko w jednym przypadku na sześć, gdy miejsce podziału zostanie wybrane między pozycjami 4 a 5; tak więc pd=l/6, a prawdopodobieństwo przeżycia jest równe ps= 1 -pd=5/6.
Ogólnie widzimy, że dla każdego schematu można podać dolne oszacowanie prawdopodobieństwa przeżycia podczas krzyżowania. Ponieważ w przypadku, gdy punkt krzyżowania wypada poza ,,wnetrzem'' schematu, schemat przeżywa krzyżowanie, więc prawdopodobieństwo przeżycia ps wynosi co najmniej 1 -8(ff)/(l- 1) (punkt krzyżowania wybieramy spośród /-1 możliwych położeń). Jeśli dla określonej pary ciągów sama operacja krzyżowania jest wykonywana z pewnym prawdopodobieństwem pc, to prawdopodobieństwo przeżycia schematu H spełnia nierówność
/-1
która sprowadza się do poprzedniego oszacowania, gdy pc= 1.
Możemy teraz zbadać łączny efekt reprodukcji i krzyżowania. Tak jak w przypadku samej reprodukcji, chcemy wyznaczyć średnią liczbę reprezentantów danego schematu H w następnym pokoleniu. Zakładając niezależność operacji reprodukcji i krzyżowania, otrzymujemy oszacowanie:
Porównując to ze wzorem wyprowadzonym dla samej reprodukcji, widzimy, że łączny efekt krzyżowania i reprodukcji otrzymuje się mnożąc oczekiwaną liczbę reprezentantów schematu przy samej reprodukcji przez prawdopodobieństwo przeżycia podczas krzyżowania pt. I znowu skutek obu operacji jest wyraźnie widoczny. Schemat H rozprzestrzenia się lub zanika zależnie od wartości współczynnika liczbowego. Gdy mamy do czynienia jednocześnie z reprodukcją i krzyżowaniem, czynnik ten zależy od dwóch okoliczności: czy przystosowanie schematu wypada powyżej, czy poniżej średniej oraz czy schemat ma stosunkowo małą, czy dużą rozpiętość. Oczywiście, te schematy, które mają przystosowanie wyższe od średniej i małą rozpiętość będą rozprzestrzeniać się zgodniezwykładniczymprawemwzrostu. �� tj;;;";:);:::;> ��:
50
2. Podstawy matematyczne algorytmów genetycznych
Ostatnią operacją, którą musimy zbadać, jest mutacja. Zgodnie z naszą wcześniejszą definicją, mutacja polega na losowej zmianie zawartości poszczególnych pozycji z prawdopodobieństwem pm. Aby schemat H przeżył mutację, muszą się zachować wszystkie jego pozycje ustalone. A zatem, ponieważ pojedynczy allel zachowuje się z prawdopodobieństwem (1 pm) i ponieważ mutacje na poszczególnych pozycjach są statystycznie niezależne, dany schemat H przeżyje mutację z prawdopodobieństwem (1 -pm)"(H) (o(H) jest liczbą pozycji ustalonych). Dla małych wartości pm Qjm� 1), prawdopodobieństwo przeżycia można aproksymować za pomocą wyrażenia 1 -o(H} -pm. Możemy więc ostatecznie stwierdzić, że oczekiwana liczba reprezentantów schematu H w następnym pokoleniu, otrzymanym w wyniku reprodukcji, krzyżowania i mutacji, spełnia następującą nierówność (zaniedbując składniki wyższego rzędu):
m(H, f+l) >m(H, t)
f
[l _ p<; ^L - o(H}p
Uwzględnienie mutacji zmienia nasze wcześniejsze wnioski w minimalnym stopniu. Wąskie, niskiego rzędu i dobrze przystosowane schematy rozprzestrzeniają się w kolejnych pokoleniach zgodnie z wykładniczym prawem wzrostu. Jest to ważna konkluzja, na tyle ważna, że otrzymała specjalne miano: Twierdzenie o schematach albo Podstawowe twierdzenie algorytmów genetycznych. Mimo że obliczenia prowadzące do dowodu twierdzenia o schematach nie były zbyt wymagające, jego implikacje są daleko idące i wyrafinowane. Aby się o tym przekonać, przeanalizujemy sposób oddziaływania algorytmu genetycznego na schematy reprezentowane w populacji, powracając do odręcznej symulacji algorytmu z rozdziału 1.
2.2. Przetwarzanie schematów na żywo: symulacja odręczna po raz wtóry _
W rozdziale 1 zademonstrowaliśmy mechanizm działania elementarnego algorytmu genetycznego na przykładzie odręcznej symulacji jednego cyklu. Powróćmy teraz do tego przykładu, obserwując tym razem przetwarzanie schematów - a nie indywidualnych ciągów kodowych - w obrębie danej populacji. W tablicy 2.1 zestawiliśmy ponownie wyniki odręcznych obliczeń wykonanych w rozdziale 1, uzupełniając je o dane dotyczące zachowania trzech schematów H}, H2 i H3, gdzie H} = \****, H2 = *10**, H^= l***0. Zwróćmy uwagę na wpływ reprodukcji, krzyżowania i mutacji na pierwszy schemat H|. W fazie reprodukcji wybrane losowo z prawdopodobieństwem proporcjonalnym do przystosowania ciągi kodowe podlegają replikacji. Jak odnotowano w tablicy, ciągi o numerach 2 i 4 są reprezentantami schematu 1****. Po zakończeniu reprodukcji sche-matjest reprezentowany przez trzy ciągi (o numerach 2, 3 i 4 w puli rodzicielskiej). Czy wynik ten jest zgodny z przewidywaniami twierdzenia o schematach? Na podstawie twierdzenia o schematach możemy oczekiwać m-/(H)//reprezentantow. Obliczając średnie przystosowanie schematu/(H,), otrzymujemy (576 + 361)/2 = 468,5. Dzieląc tę
Tablica 2.1. Przetwarzanie schematów w algorytmie genetycznym -symulacja odręczna
Ciągi kodowe
Nr Populacja Wartość x pselect, Oczekiwana Liczba kopii Pula rodzicielska Partner Punkt Nowa Wartość /W
ciągu początkowa (Liczba f (x) f, liczba kopii wylosowanych po reprodukcji (wybrany krzyżowania populacja * 1
(wygenerowana całkowita) x2 I/ fi (wg reguły (zaznaczono losowo) (wybrany
losowo) J ruletki) punkty losowo)
krzyżowania)
1 01101 13 169 0,14 0,58 �� 1 011011 2 ' 4 01100 12 144
2 11000 24 576 0,49 1,97 ... 2 110010 1 4 11001 25 625
3 01000 8 64 0,06 0,22 o .-v; 1 1 1 000 4 2 11011 27 729
4 10011 19 361 0,31 1,23 i 101011 3 2 '10000 16 256
Suma 1170 1,00 4,00 4,0 1754
Średnia 293 0,25 1,00 � 1,0 439
Maksimum 576 0,49 1,97 2,0 729
Schematy
Przed reprodukcją Po reprodukcji Stan końcowy
Reprezentanci Średnie przystoso- Oczekiwana Faktyczna Reprezen- Oczekiwana Faktyczna Re-
wanie schematu f (H) liczba liczba tanci liczba liczba pre-
reprezentantów reprezen- reprezentantów repre- zen-
tantów zentantów tanci
Hl 1**** 2, 4 469 3,20 3 2,3,4 3,20 3 2, 3,4
H2 *10** 2, 3 320 2,18 2 2, 3 1,64 2 2, 3
#3 i***o 2 576 1,97 2 2,3 0,0 1 4
52
2. Podstawy matematyczne algorytmów genetycznych
liczbę przez średnie przystosowanie populacji f- 293 i mnożąc przez liczbę reprezentantów schematu H} w chwili t, m(Ht, t) = 2, otrzymujemy oczekiwaną liczbę reprezentantów tegoż schematu w chwili t+\, m(Ht, ?+l) = 2-468,5/293 = 3,20. Porównując to z faktycznym wynikiem (trzy) stwierdzamy, że otrzymaliśmy prawidłową reprezentację. Idąc o jeden krok dalej, zauważmy, że krzyżowanie nie może wprowadzić tu żadnej zmiany, gdyż rozpiętość 5(H,) = 0 wyklucza rozerwanie schematu. Następnie, przy natężeniu mutacji pra = 0,001, możemy oczekiwać, że dotknie ona m-pm = 3-0,001=0,003 bitów, tj. zawartość pozycji ustalonej w żadnym z trzech reprezentantów schematu nie ulegnie zmianie. Tak więc dla schematu Hl obserwujemy oczekiwany wykładniczy wzrost liczby reprezentantów, zgodnie z przewidywaniami twierdzenia o schematach.
Jak dotąd wszystko się zgadza, ale schemat Ht ze swym pojedynczym bitem wydaje się jednak dość szczególnym przypadkiem. Co można więc powiedzieć o propagacji schematów o większej rozpiętości? Zbadajmy, na przykład, propagację dwóch schematów, H-, = *]Q** i f/j= l***0. Stan będący wynikiem reprodukcji i poprzedzający krzyżowanie jest zgodny z oczekiwaniami. W przypadku schematu H2 zaczynamy od dwóch reprezentantów w populacji początkowej i kończymy z dwoma otrzymanymi podczas reprodukcji. Zgadza się to z wartością oczekiwaną m(H2) = 2 � 320/293 = 2,18 (320 jest to średnie przystosowanie schematu, a 293 - średnie przystosowanie populacji). W przypadku #3 startujemy odjednego reprezentanta (ciąg 2) i kończymy z dwoma po reprodukcji (ciągi 2 i 3 w puli rodzicielskiej). Wynik ten jest zbliżony do wartości oczekiwanej m(H^) = \ -576/293 = 1,97 (576 jest to średnie przystosowanie schematu, 293 - średnie przystosowanie populacji). Sytuacja ukształtowana po operacji krzyżowania wygląda jednak w obu przypadkach zasadniczo odmiennie. W przypadku krótkiego schematu H2 zostaje zachowana liczba reprezentantów (2). Ponieważ rozpiętość schematu jest mała, spodziewamy się, że krzyżowanie naruszy schemat tylko w jednym przypadku na cztery (/- 1 =5- 1 =4). W efekcie, prawdopodobieństwo przeżycia schematu H2jest duże. Wartość oczekiwana liczby reprezentantów schematu wynosi m(H2, f+l) = 2,18-0,75=l,64 i nie odbiega wiele od rzeczywistego wyniku równego 2. Natomiast H3 jest schematem zupełnie innego typu. Wskutek dużej rozpiętości (S(H3) = 4), schemat ten najczęściej ulega zniszczeniu podczas krzyżowania.
Odręczne obliczenia potwierdzają przewidywania teoretyczne wyprowadzone w pierwszej części rozdziału. Wąskie schematy niskiego rzędu rozprzestrzeniają się lub zanikają w kolejnych pokoleniach wykładniczo, w zależności od średniego przystosowania schematu. Wkrótce spróbujemy oszacować liczbę schematów, które są w taki sposób przetwarzane, ale przedtem musimy zadać i znaleźć odpowiedź na rodzące się pytanie. Dlaczego powinniśmy wybierać najlepsze z obserwowanych schematów z rosnącą wykładniczo częstością? Inaczej mówiąc, dlaczego ta szczególna strategia wyboru jest warta zachodu? Szukając odpowiedzi na to pytanie, odbiegniemy pozornie od tematu, podążając tropem hazardzisty pędzącego życie wśród automatów do gry w Las Vegas.
2.3. Zagadnienia dwu- i fc-ramiennego bandyty
53
2.3. Zagadnienia dwu- i fr-ramiennego ________________________ bandyty
Wyjaśniliśmy więc, zarówno w aspekcie jakościowym, jak też ilościowym, skutki reprodukcji, krzyżowania i mutacji. Schematy o małej rozpiętości, niskim rzędzie i ponad-przeciętnym przystosowaniu (czyli cegiełki) propagują się w kolejnych pokoleniach w rosnących wykładniczo liczbach egzemplarzy. Jest to fakt poza dyskusją. Pozostaje nam jednak co najmniej jedno dręczące pytanie: dlaczego jest to korzystne? Mówiąc precyzyjniej, dlaczego najlepsze obserwowane schematy-cegiełki powinny być wybierane z rosnącą wykładniczo częstością? Pytanie to jest związane z ważnymi zagadnieniami z dziedziny statystycznej teorii podejmowania decyzji, mianowicie z problemem dwu-ramiennego bandyty i jego uogólnioną wersją - problemem fc-ramiennego bandyty. Chociaż może się wydawać, że odbiegamy w ten sposób od przedmiotu głównego zainteresowania (chodzi nam przecież o zrozumienie działania algorytmu genetycznego, a nie o minimalizację strat w grze hazardowej), wkrótce przekonamy się, że optymalne rozwiązanie zagadnienia bandyty ma postać bardzo podobną do omawianej własności nasze-gotrzyczęściowegoalgorytmu. "
Rys. 2.1. Zagadnienie dwuramiennego bandyty rodzi dylemat: jak poszukiwać prawidłowej odpowiedzi (eksploracja), wykorzystując jednocześnie zdobytą informację (eksploatacja)?
Wyobraźmy sobie dwuramienny automat do gry, jak na rys. 2.1, którego ramiona są oznaczone jako LEWE i PRAWE. Przypuśćmy następnie, że wiadomo, iż jedno z ramion zapewnia średnią wygraną ^ przy wariancji of, a drugie - średnią wygraną
54
. 2. Podstawy matematyczne algorytmów genetycznych
^2 przy wariancji <5\, przy czym ^t, >^,2. Które zatem ramię powinniśmy wybierać? Jasne, że wolelibyśmy grać przy użyciu ramienia dającego większą wypłatę (^i,), ale w tym właśnie sęk. Ponieważ nie wiemy z góry, z którym z ramion jest związana większa średnia wygrana, stajemy tu wobec ciekawego dylematu. Musimy nie tylko podejmować decyzję (a właściwie serię decyzji), którym ramieniem zagrać, ale jednocześnie zbierać informacje o tym, które ramię jest lepsze. Konieczność zachowania kompromisu między eksploracją w celu nabycia wiedzy a eksploatacją tej wiedzy jest stale powracającą, fundamentalną kwestią w teorii systemów adaptujących się. Sposób, w jaki odniesiemy się do tego dylematu, określi w znacznym stopniu szanse ostatecznego sukcesu zastosowanej metody.
Jednym z możliwych rozwiązań jest oddzielenie eksploracji od eksploatacji polegające na tym, że najpierw wykonamy eksperyment, a następnie podejmiemy nieodwracalną decyzję zależna, od wyniku tego eksperymentu. Takie podejście, znane w tradycyjnej teorii decyzji, można opisać formalnie w następujący sposób. Przypuśćmy, że mamy do wykonania łącznie N prób, które należy podzielić między oba ramiona. Na początek, w fazie eksperymentalnej, wykonujemy po � prób (2nL(N, n} = In, - ^| � [(N - n)q(n} + n(\ - q(n))]
gdzie q(ri} oznacza prawdopodobieństwo, że po wykonaniu n prób z każdym z urządzeń gorsze ramię dało empirycznie lepszy wynik. To prawdopodobieństwo daje się dobrze oszacować za pomocą ,,ogona'' rozkładu normalnego
q(n) =
1
gdzie
Z równań tych widać, że opisana procedurajest związana z dwoma rodzajami strat. Pierwszą stratę ponosimy, wykonując w fazie eksperymentalnej n prób ze złym ramieniem. Druga strata wynika z decyzji wyboru, po zakończeniu eksperymentu, ramienia dającego niższą średnią wygraną (fi2). Nie możemy mieć absolutnej pewności, że po wykonaniu eksperymentu wybierzemy właściwe ramię, musimy więc liczyć się z tym, że od czasu do czasu podejmiemy błędną decyzję, ponosząc w ten sposób stratę podczas pozostałych N-2n prób w fazie eksploatacji. Można wyznaczyć optymalną wielkość eksperymentu n*, obliczając pochodną funkcji strat i przyrównując ją do zera. Na rysunku 2.2 pokazano zależność optymalnej wielkości eksperymentu n* od łącznej liczby prób
2.3. Zagadnienia dwu- i fr-ramiennego bandyty
55
c2N
o,i
t.o
10,0
100,0
Rys. 2.2. Znormalizowana łączna liczba prób (c2N) rośnie szybciej niż wykładniczo w stosunku do znormalizowanej optymalnej wielkości eksperymentu (c2n*) przy jednoetapowym modelu decyzyjnym dla zagadnienia dwuramiennego bandyty
Analiza tej prostej procedury nie sprawia większych trudności, ale bez wątpienia istnieją lepsze, być może optymalne rozwiązania. Holland (1975) wykonał obliczenia, z których wynika, jak należy podzielić próby między oba ramiona, aby zminimalizować oczekiwaną stratę. Liczba prób przypadających na gorsze (empirycznie) ramię powinna wynieść n*, zaś na lepsze - N-n*, przy czym n* jest dane wzorem0
n =
N2
Przekształcając powyższą równość dochodzimy do następującego związku określającego liczbę prób dla empirycznie lepszego ramienia:
N-n* = N = ^8nb4\nN2-e""2b~ ;:
Innymi słowy, optymalny podział prób (w sensie minimalnej oczekiwanej straty) wymaga, aby liczba prób z lepszym empirycznie ramieniem rosła nieco szybciej niż wykładniczo. Niestety, strategia taka nie daje się praktycznie zrealizować, ponieważ wymaga znajomości wyników prób przed ich wykonaniem. Niemniej określa ona górną granicę
" W nowym (uzupełnionym) wydaniu Adaptation in Natural and Artifidal Systems (MIT Press, 1992) Holland przyznaje się do błędu w dowodzie i podaje poprawioną wersję cytowanego wyżej wzoru, wyprowadzoną przez D. Frantza; różnica dotyczy stałych występujących we wzorze (str. 183) (pnyp. ttum.).
56
2. Podstawy matematyczne algorytmów genetycznych
efektywności, do której osiągnięcia powinny zdążać strategie realistyczne. Z pewnością wiele strategii może zbliżyć się do tego ideału. Widzieliśmy, że w przypadku analizowanego uprzednio podejścia, liczba prób przypadających na gorsze ramię maleje wykładniczo wraz ze wzrostem liczby prób. Inną metodą zbliżającą się nawet bardziej do idealnego podziału prób jest rozważany wcześniej trzyczęściowy algorytm genetyczny. Twierdzenie o schematach zapewnia empirycznie najlepszym cegiełkom co najmniej wykładniczo rosnącą liczbę reprezentantów. W ten sposób algorytm genetyczny okazuje się realistyczną, a przy tym niemal optymalną procedurą poszukiwania w zbiorze konkurencyjnych rozwiązań (Holland, 1973a, 1975).
Jednak w przypadku algorytmu genetycznego nie mamy już do czynienia z prostym zagadnieniem dwuramiennego bandyty, ale rozpatrujemy w istocie jednoczesne rozwiązanie wielu zagadnień wieloramiennych bandytów. Aby się o tym upewnić, rozważymy najpierw postać rozwiązania pojedynczego zagadnienia A>ramiennego bandyty, a następnie wykażemy, że zwykły algorytm genetyczny można ujmować w kategoriach złożenia wielu takich A:-ramiennych bandytów.
Postać rozwiązania w przypadku zbliżonego zagadnienia &-ramiennego bandyty została podana również przez Hollanda (1973a). Reguła podziału prób między k konkurencyjnych ramion zapewniająca minimalną oczekiwaną stratę przypomina analogiczną regułę dla dwóch ramion, stanowi bowiem, że liczba prób przypadających na empirycznie najlepsze ramię powinna wzrastać szybciej niż wykładniczo. Wynik ten niejest zaskakujący, ale dobrze zgadza się z naszymi wyobrażeniami na temat przetwarzania schematów, jeśli potraktujemy zbiór konkurujących schematów jako określonego k-ra-miennego bandytę. Ten ostatni związek stanie się bardziej widoczny, gdy zdefiniujemy pojęcie zbioru konkurujących schematów, a następnie określimy liczbę i wymiary zagadnień "bandyckich", rozwiązywanych równocześnie w trakcie wykonywania algorytmu genetycznego dla danej długości ciągów kodowych.
Dwa schematy A i B o elementach odpowiednio a, i bt konkurują, jeżeli dla każdej pozycji i= 1, 2, ..., / albo a~&, = *, albo a,-#*, b^*, ai^bi - przy czym ostatni przypadek zachodzi przynajmniej dla jednego /. Rozważmy, na przykład, zbiór następujących ośmiu schematów długości 7, konkurujących na pozycjach 2, 3 i 5:
* 0 0 * 0 * * .< .-> �
* 0 0 * 1 * *
* 0 1 * 0 * * ' � ' '. ,,
* 0 1 * 1 * *
* 1 0 * 0 * *
* 1 0 * 1 * * .; .,=� ,-.-
* 1 ] * 0 * * , '~ .^"i ' " ''
Dla trzech pozycji ustalonych 2, 3 i 5 mamy osiem konkurujących schematów, gdyż każda z nich może zawierać albo 1 albo 0 (23 = 8).
Teraz nietrudno już dostrzec analogię do zagadnienia &-ramiennego bandyty. Ponieważ powyższe schematy mają ten sam zestaw ustalonych pozycji, konkurują one
2.4. Ile schematów bierze efektywny udział w przetwarzaniu? .
57
o "przydział" cennych miejsc w populacji. Prawidłowa strategia wymaga przydziału wykładniczo rosnącej liczby miejsc najlepszym spośród obserwowanych schematów, analogicznie jak w przypadku prób przypadających na empirycznie najlepsze ramię A>ramiennego bandyty. Istotną różnicę między interesującym nas przypadkiem algorytmu genetycznego a nieco egzotycznym zagadnieniem ł-ramiennego bandyty stanowi okoliczność, że mamy tu do czynienia z rozwiązywaniem wielu takich zagadnień równocześ-
/7\
nie. Na przykład dla trzech ustalonych pozycji w ciągu długości 7 mamy =35 zagadnień ośmioramiennych (23 = 8) bandytów. Ogólnie, dla schematów rzędu j i długości / istnieje . różnych zagadnień &-ramiennych bandytów, gdzie k,=2>. Nie wszystkie
\ i / J J
= 2' zagadnień są rozwiązywane zjednakową sprawnością, gdyż operacja krzyżo-
wania ma tendencję do niszczenia "bandytów" o dużej rozpiętości, jak już uprzednio wskazywaliśmy. W następnym punkcie zajmiemy się wyznaczeniem liczby schematów biorących efektywny udział w przetwarzaniu.
2.4. Ile schematów bierze efektywny udział ____________________w przetwarzaniu?
Nasze dotychczasowe oszacowania wskazywały, że w przetwarzaniu populacji n ciągów kodowych o długości / bierze udział od 2' do n � 2' schematów. Jak wiemy, nie wszystkie z nich mają dużą szansę na przetrwanie, gdyż operacja krzyżowania niszczy schematy o stosunkowo dużej rozpiętości. Obecnie zajmiemy się oszacowaniem z dołu liczby schematów biorących efektywny udział w przetwarzaniu - to jest tych, których reprezentacja zwiększa się w pożądany wykładniczy sposób.
Najczęściej cytowanym w literaturze wynikiem dotyczącym liczby efektywnie przetwarzanych schematów jest szeroko znane, choć błędnie interpretowane oszacowanie O(n3), podane przez Hollanda (Goldberg, 1985d). Ujmując rzecz najprościej, oszacowanie to mówi, że w algorytmie genetycznym działającym na n strukturach, w każdym pokoleniu ulega przetworzeniu jakieś n3 schematów. Jest to własność tak doniosła, że Holland nadał jej specjalne miano: ukryta równoległość [implicit parallelism\. Chociaż bowiem w każdym pokoleniu liczba wykonywanych działań jest proporcjonalna do wielkości populacji, liczba schematów biorących efektywny udział w przetwarzaniu jest rzędu n\ Nie potrzeba przy tym żadnych ubocznych działań ani miejsca w pamięci innego niż dla samej populacji. Aby zrozumieć przesłanki tego oszacowania i dojść do źródeł efektu potęgującego proces przetwarzania, spróbujmy ponownie wyprowadzić wspomniany wynik.
Rozważmy populację złożoną z n ciągów dwójkowych o długości /. Interesują nas jedynie schematy o prawdopodobieństwie przeżycia (przetrwania) nie mniejszym od stałej ps. W konsekwencji, zakładając krzyżowanie proste i niewielkie tempo mutacji,
58
2. Podstawy matematyczne algorytmów genetycznych
I
będziemy uwzględniać jedynie schematy o "współczynniku utraty" eJesteśmy w stanie, dla danego rozmiaru schematu, oszacować z dołu liczbę różnych schematów biorących udział w przetwarzaniu początkowo losowej populacji ciągów kodowych. Wyznaczymy najpierw liczbę pasujących do danego ciągu kodowego schematów o rozmiarze ls lub mniejszym. Przypuśćmy, że chcemy policzyć schematy o rozmiarze nie większym niż /v = 5 pasujące do następującego ciągu o długości /= 10:
1 0 1 1 1 000 1 0
\"\ , , > : .'�-. '��' . ��'' ' '' ;L�� - � � � - � � �
Znajdźmy najpierw liczbę takich schematów "zawartych" w początkowym segmencie o długości 5,
o ustalonej wartości na ostatniej pozycji w segmencie. To znaczy, interesują nas schematy postaci
gdzie gwiazdki (*) zachowują swoje zwykłe znaczenie, a znaki procentu (%) oznaczają pozycje mogące przyjmować wartość ustaloną (taką, jak odpowiednia pozycja w danym ciągu) albo nieustaloną (*)2). Takich schematów jest oczywiście 2('v~'', gdyż /vl=4 pozycji może przyjąć wartości ustalone lub nieustalone. Aby znaleźć łączną liczbę poszukiwanych schematów, będziemy przesuwać nasze "okienko" kolejno ojedną pozycję:
Powyższy chwyt można wykonać / /,+ 1 razy, co daje dolne oszacowanie łącznej liczby schematów o rozmiarze /y lub mniejszym równe 2<'*~0-(/-/,+ !). Obliczenia te dotyczą liczby schematów pasujących do określonego ciągu kodowego. Mnożąc to przez wielkość populacji �, otrzymalibyśmy wynik �� 2^^"" � (/-/,+ 1), dający nadmiernie optymistyczną ocenę łącznej liczby takich schematów dla całej populacji, gdyż z całą pewnością wiele schematów niskiego rzędu powtarza się w dużych populacjach. Aby poprawić to oszacowanie, wybierzmy wielkość populacji równą3) n = 2'�/2. Możemy wówczas oczekiwać, że dowolny schemat rzędu co najmniej /v/2 wystąpi co najwyżej raz. Pamiętając, że liczby schematów wyrażają się współczynnikami dwumianowymi4', wnioskujemy, że połowa z nich jest rzędu wyższego niż /v/2, a połowa - rzędu niższego lub równego tej wielkości. Jeśli uwzględnimy tylko schematy wyższego rzędu, możemy podać następujące dolne oszacowanie liczby różnych schematów:
" Przez rozmiar schematu będziemy tu rozumieć liczbę elementów między skrajnymi pozycjami ustalonymi, włączając oba "końce", czyli rozpigtość + 1 (przyp. ttum.).
2) Nie są to wszystkie schematy o rozmiarze nie większym niż /,. mieszczące się w danym segmencie (przyp. thim.).
3) Przyjmujac,ze/,jestliczbaparzysta^rzw.rfMm.). '
4) Chodzi o schematy danego rzędu "zawarte" w jednym "okienku" (pnyp. ttum.).
2.5. Hipoteza cegiełek
59
ns>n(l-ls+ 1)2
/,.-2
Wynik ten różni się od poprzedniego optymistycznego oszacowania czynnikiem 1/2. Uzwględniając wybraną szczególną wielkość populacji 2'>72 otrzymujemy zależność
n, =
(/-/,+ l)n3
Ponieważ ns = Cn3, stwierdzamy, że liczba schematów jest proporcjonalna do sześcianu wielkości populacji, a więc jest rzędu n3, 0(n3)0.
Widzimy więc, że pomimo niszczącego działania operacji krzyżowania i mutacji na schematy wysokiego rzędu i o dużej rozpiętości, algorytmy genetyczne wyzyskują w ukryty sposób wielką liczbę schematów podczas przetwarzania stosunkowo niewiel-kiejliczbyciągówkodowych.
2.5. Hipoteza cegiełek
Z perspektywy odsłoniętej dzięki schematom obraz zachowania się algorytmów genetycznych wygląda znacznie przejrzyściej. Dobrze przystosowane schematy niskiego rzędu i o małej rozpiętości są nieustannie wybierane, zestawiane i powielane, tworząc ciągi kodowe o potencjalnie wyższym przystosowaniu. Wyzyskując te specyficzne schematy, redukujemy w pewnym sensie złożoność problemu; zamiast bowiem próbować każdej możliwej kombinacji, budujemy coraz lepsze ciągi z najlepszych częściowych rozwiązań dotychczas znalezionych.
Ponieważ dobrze przystosowane schematy niskiego rzędu i o małej rozpiętości odgrywają tak ważną rolę w działaniu algorytmów genetycznych, nadaliśmy im miano cegielek. Tak jak dziecko buduje swoje imponujące fortece, układając i dopasowując drewniane klocki, algorytm genetyczny dochodzi do niemal optymalnej wydajności zestawiając schematy-cegiełki.
Jest tu jednak pewien problem. W rozdziale pierwszym powtarzaliśmy z uporem, że z kombinacji poglądów powstają lepsze idee. Przed chwilą wygłosiliśmy tezę, że schematy-cegiełki łączą się tworząc lepsze ciągi kodowe. Jakjednak możemy się przekonać, czy stwierdzenia te, choć wydają się w pełni uzasadnione, są w istocie prawdziwe czy też nie?
Coraz większa liczba dowodów empirycznych świadczy na rzecz powyższej tezy dla szerokiego zakresu problemów2'. Począwszy od dwóch pionierskich dysertacji (Bagley, 1967; Rosenberg, 1967) sprzed dwóch dziesięcioleci, aż po liczne zastosowania
" Sformułowanie to zakłada dowolność parametru n. Jest to zapewne przyczyna nieporozumień, o których wspomina autor (prz.yp. tlum.).
2) W ostatnich latach pojawiły się pewne wątpliwości co do słuszności hipotezy cegiełek ^>rzyp. tlum.).
60
2. Podstawy matematyczne algorytmów genetycznych
algorytmów genetycznych prezentowane na ostatnich konferencjach poświeconych tej tematyce (Grefenstette, 1985a, 1987a), hipoteza cegiełek znajdowała potwierdzenie w wielu różnych dziedzinach problemowych. Przy użyciu prawie takich samych algorytmów opartych na reprodukcji, krzyżowaniu i mutacji pomyślnie rozwiązywano zadania należące do takich klas, jak problemy gładkie jednomodalne, problemy wielomodalne z szumem oraz problemy optymalizacji kombinatorycznej. Chociaż ta ograniczona liczba dowodów empirycznych nie przesądza o słuszności teorii, to jednak zdaje się wskazywać, że algorytmy genetyczne nadają się do rozwiązywania wielu typów zadań, z którymi zazwyczaj można się spotkać.
Niedawno Bethke (1981) rzucił nieco światła na tę sprawę. Stosując funkcje Wal-sha i umiejętne transformacje schematów, opracował efektywną metodę analityczną do wyznaczania średniego przystosowania schematów za pomocą współczynników Walsha. To z kolei daje nam możliwość określenia, czy przy danej funkcji przystosowania i sposobie kodowania optymalne lub suboptymalne rozwiązania można otrzymać dzięki kombinacji schematów-cegiełek. Holland (1987b) uogólnił wynik Bethkego na przypadek populacji o niejednostajnym rozkładzie.
i
0 4 S 12 16 20 24 28 32
Rys. 2.3. Obszarodpowiadającyschematowi 1**** na wykresie funkcji f(x) = x2
Prace Bethkego i Holłanda na temat transformacji Walsha wykraczają poza zakres naszych rozważań, lecz zainteresowany Czytelnik może skorzystać z dodatku D, gdzie zwięźle przedstawiono kilka najważniejszych wyników. Tym niemniej, idee leżące u podłoża tych odkryć są na tyle istotne, że musimy postarać się zrozumieć regularność związaną z przetwarzaniem schematów-cegiełek przynajmniej na intuicyjnym, obrazowym poziomie. W tym celu powróćmy do przykładu z pięciobitowym kodem, który zaczęliśmy omawiać w rozdziale pierwszym. Jak pamiętamy, chodziło tam o maksymalizację funkcji/(*)=JE2, przy czym do zakodowania x był zastosowany pięciopozycyjny zapis dwójkowy. Chcemy zatem przekonać się, jak wyglądają w tym przypadku schema-ty-cegiełki i w jaki sposób mogą tworzyć lepsze rozwiązania mieszając się ze sobą?
2.5. Hipoteza cegiełek
61
Rozważmy prosty schemat, Ht = 1****. Jak taki schemat może "wyglądać"? Odpowiedź znajdziemy na rys. 2.3 w postaci zacienionej części wykresu. Wygląda na to, że schemat odpowiadający jedynce na najstarszej pozycji pokrywa prawą połowę rozpatrywanej dziedziny. Podobnie schemat H2 = 0**** pokrywa lewą połowę. Pouczające okazują się inne przykłady jednobitowe, na przykład schemat H3 = ****l z rys. 2.4. Schemat ten pokrywa połowę dziedziny odpowiadającą liczbom nieparzystym (00001 = 1, 00011 =3, 00101 =5 itd). Schemat HĄ = ***0* również pokrywa połowę dziedziny, ale w sposób pokazany na rys. 2.5. Wydaje się więc, że schematy jednobitowe pokrywają połowę dziedziny, choć częstość "oscylacji" zależy od pozycji zajmowanej przez ustalony bit.
1
0,8-0,8-
0,6^ g-T- 0,5 -.X.
0,4-
0,3-0,2-
0,1 -0
0 4 8 12 16
Rys. 2.4. Obszarodpowiadającyschematowi ****1
20
24
28
0,9 -
0,8-
0,7 -
0,6-
� 0,5-
^~^ 0,4 -
0,3-
0,2-
0,1 -
0
0 4 8 12
Rys. 2.5. Obszar odpowiadający schematowi
16 20
***o*
24
28
62
. 2. Podstawy matematyczne algorytmów genetycznych
1
0.9 0,8 0,7 0,6 0,5 0,4 0,3
I 12
0 4 8 12 16
Rys. 2.6. Obszarodpowiadającyschematowi 10***
24
I 28
Schematy wyższego rzędu są z pewnością również interesujące. Rozważmy schemat H$= 10*** z rys. 2.6. Schemat ten pokrywa lewą ćwiartkę w prawej połówce dziedziny. Podobnie można zobrazować inne schematy dwubitowe, jak np. schemat tf6 = **l*l pokazany na rys. 2.7. Takjak schemat H5 pokrywa on także jedną czwartą dziedziny (dlaczego?), ale w sposób bardziej rozproszony. Dla Czytelników znających szeregi Fouriera periodyczność rozmaitych schematów będzie ważną wskazówką. Istotnie, to właśnie ta periodyczność umożliwia przeprowadzenie analizy za pomocą funkcji Walsha. Tak jak za pomocą analizy harmonicznej można określić własności fizyczne, badając względne wielkości współczynników Fouriera, zastosowanie funkcji Walsha umożliwia określenie zachowania się algorytmu genetycznego ze "statycznego" punktu widzenia przez analizę względnych wielkości współczynników Walsha0.
Chociaż metoda transformacji Walsha stanowi skuteczne narzędzie matematyczne do analizy zachowania algorytmu genetycznego w szczególnych przypadkach, uogólnienie jej na przypadek dowolnych funkcji kodujących i funkcji przystosowania okazało się zadaniem niełatwym. Bethke podał pewną liczbę testowych kombinacji, o których można dowieść, że kierują elementarny algorytm genetyczny na fałszywe tory (takie przypadki nazywamy problemami zwodniczymi). Wyniki te wskazują, że w problemach zwodniczych zdają się występować izolowane optima: punkty najlepsze są otoczone przez najgorsze. W zadaniach praktycznych, z jakimi mamy na ogół do czynienia w rzeczywistym świecie, nie musimy poszukiwać takiej "igły w stogu siana"; zazwyczaj w kombinacji funkcji przystosowania i funkcji kodującej występuje pewnego rodzaju regularność, która może być wykorzystana podczas rekombinacji schematów-cegiełek. Poza tym każdy się chyba zgodzi, że znalezienie igły w stogu siana nie jest zadaniem łatwym, niezależnie od zastosowanej techniki poszukiwania. Niemniej warto pamię-
Porównaj dodatek D Qjriyp. tlum.).
2.6. Minimalny problem zwodniczy .
63
1 -0,9- /
0,8- /
0,7- /
ff- �'6" /
^ �'5" . /
0,4- /
0,3- y/
0,2 - j* > /"
0,1 -0 -Rys. 2.7. Obszar , ------- - ^* �**" ^
3 4- 8 12 odpowiadający schematowi 16 20 **1*1 24 28 3
tać, że skuteczność elementarnego algorytmu genetycznego zależy od wyników rekombinacji schematów-cegiełek. Jeśli cegiełki prowadzą na manowce z powodu zastosowanego kodu lub samej funkcji przystosowania, możemy potrzebować sporo czasu, zanim dojdziemy do rozwiązań zbliżonych do optymalnego.
2.6. Minimalny problem zwodniczy
Graficzne przedstawienie schematów i transformacje Walsha dają wgląd w działanie algorytmów genetycznych. Jednak z praktycznego punktu widzenia techniki te są co najmniej tak samo uciążliwe, jak przeglądanie dyskretnej przestrzeni rozwiązań. W konsekwencji nie są one szeroko stosowane do analizy zadań praktycznych. Niemniej jednak chcielibyśmy wciąż lepiej zrozumieć źródła trudności napotykanych przez elementarny algorytm genetyczny. W celu dokładniejszego zbadania tego problemu skonstruujemy najprostsze zadanie, dla którego algorytm genetyczny może rozminąć się z globalnym optimum (Goldberg, 1987b). Aby do tego doprowadzić, spróbujemy naruszyć w maksymalnym stopniu hipotezę cegiełek. Inaczej mówiąc, chcemy, aby małe cegiełki łączyły się w niewłaściwe (nieoptymalne) większe bloki. Najprostszym zadaniem, w którym może wystąpić podobne zjawisko, jest problem rzędu 2 (dwubitowy). W tym punkcie przeprowadzimy zwięzłą analizę takiego minimalnego problemu zwodniczego (MDP, minimal deceptive problem). Pewnym zaskoczeniem może być fakt, że mimo naszych największych wysiłków, aby wyprowadzić algorytm w pole, ten zwodniczy przypadek nie okazuje się na ogół AG-trudny (to znaczy, że algorytm genetyczny na ogól nie rozmija się z globalnym optimum).
Przypuśćmy, że dane są następujące cztery schematy rzędu 2, ze współczynnikami przystosowania: �. � . .. .,;...�:"�.�.<_<... '"^.v~.r;:.-.>-(;^..:.^-. ,'
64
2. Podstawy matematyczne algorytmów genetycznych
] # * # # * 0 *
l4- 8(fl) ^ I
,j(00 ^)l
/10 /U
Współczynniki przystosowania odpowiadają średnim dla schematów względem populacji. Zakładamy, że są one stałe, o zerowej wariancji �. Przyjmijmy, że/,, jest globalnym optimum:
/II -^*/(X)
/II ^/01
/II
Ponieważ problem jest niezmienniczy względem obrotów i odbić w dwuwymiarowej przestrzeni Hamminga2', taki szczególny wybór globalnego optimum nie zmniejsza ogólności naszych wniosków.
Wprowadźmy teraz element zwodniczości, który jest konieczny, aby problem mógł przedstawiać trudności dla naszego algorytmu. Z taką sytuacją będziemy mieli do czynienia, gdy jeden lub oba schematy rzędu 1 mające tylko suboptymalnych reprezentantów okażą się lepsze niż odpowiednie schematy rzędu 1 mające optymalnego reprezentanta. W sformułowaniu matematycznym chcemy, aby spełniona była co najmniej jedna z następujących nierówności:
/(0*)>/(1*); .
/(*0)>/(*1) i:
W powyższych wyrażeniach pominęliśmy wszystkie pozycje oryginalnych schematów prócz dwóch pierwotnie ustalonych, a wyrażenia określające przystosowanie odnoszą się do średnich po wszystkich reprezentantach w danej klasie podobieństwa3'. Tak więc chcielibyśmy, aby zachodziły nierówności:
/(00)+/(10) /(01)+/(11)
2 2 " � ;' '
Niestety, obie nierówności nie mogą być równocześnie spełnione (w przeciwnym przypadku punkt 11 nie mógłby być globalnym optimum). Nie zmniejszając ogólności, możemy założyć, że prawdziwa jest pierwsza z nich. A zatem problem zwodniczy rzędu 2jest wyznaczony przez warunek globalności (maksimum równe/n) orazjeden warunek zwodniczosci(wybralismytuprzypadek/(0*)>/(l*)).
" Tzn. takie, jak średnie względem całej przestrzeni Qir?yp. tłum.).
2) Przestrzeń te można utożsamiać z "przestrzenią" złożoną z wierzchołków kwadratu jednostkowego na płaszczyźnie Q>rzyp. tłum.).
31 Tj. względem całej przestrzeni tyrzyp. tlum.).
2.6. Minimalny problem zwodniczy
65
W celu uproszczenia dalszych rozważań, znormalizujmy wszystkie współczynniki przystosowania względem/^, (tj. współczynnika przystosowania "dopełnienia" globalnego optimum):
/II /01 / /10
r = ; c = ; c = � , ;
/00 /00 /00 '' '
Warunek globalności w znormalizowanej postaci zapisuje się jako:
r > c; r > 1 ; r > c'
/* Podobniemożemyzapisaćwarunekzwodniczości: ,* .... ��'�-'
r< 1 + c - c' Znierównościtychwynikająinteresującekonsekwencje: ' -=1 i:-. J?�fi
c'TypI:/o,>/on(c>l). . / , : . '
Na rysunkach 2.8 i 2.9 zamieszczono reprezentatywne szkice obu przypadków, przy czym przystosowanie przedstawione jest jako funkcja dwóch zmiennych boolowskich. Oba przypadki są zwodnicze i można wykazać, że w żadnym z nich funkcja przystosowania nie może być wyrażona jako kombinacja liniowa poszczególnych alleli, tj. w postaci:
Rys. 2.8. Ilustracja geometryczna minimalnego problemu zwodniczego typu I (fm > fx
66
2. Podstawy matematyczne algorytmów genetycznych
Rys. 2.9. Ilustracja geometryczna minimalnego problemu zwodniczego typu II (f00> fm)
Używając terminologii biologicznej, mamy tu do czynienia z epistazą. Ponieważ można podobnie dowieść, że żaden problem rzędu 1 nie może być zwodniczy, wiec problem zwodniczy rzędu 2 jest najmniejszym możliwym, czyli minimalnym problemem zwodniczym (MDP). Mając już zdefiniowany MDP, możemy teraz przystąpić do wyczerpującej analizy jego własności.
2.6.1. MDP: analiza
Można przypuszczać, że skonstruowany właśnie uogólniony problem rzędu 2 okaże się zdolny wyprowadzić w pole nasz algorytm genetyczny, jeżeli dwie ustalone pozycje w rozważanych schematach będą znacznie oddalone od siebie. Twierdzenie o schematach wydaje się wskazywać, że trudności pojawią się, gdy czynnik
/(H)
7
nie przekracza 1 (zakładając, żepm = 0). Dokładniejsza analiza wymaga, byśmy przyjrzeli się szczegółom operacji krzyżowania.
W jednym z wcześniejszych punktów stwierdziliśmy, że obliczając w zwykły sposób oczekiwaną liczbę reprezentantów schematu otrzymujemy w istocie dolne oszacowanie. Dzieje się tak, gdyż w wyprowadzeniu nie uwzględniono wyrazów odpowiadających kreacji schematów (zniszczenie jednego schematu pociąga za sobą powstanie innego), przyjmując, że skrzyżowanie w punkcie leżącym między skrajnymi pozycjami ustalonymi schematu zawsze powoduje jego utratę. Jest to w tym przypadku założenie zbyt pesymistyczne, gdyż kojarzenie i krzyżowanie par niekomplementarnych zachowuje ma-
2.6. Minimalny problem zwodniczy
67
teriał genetyczny rodziców. Na przykład 00 skrzyżowane z 01 daje w wyniku 01 i 00. Utrata materiału genetycznego następuje jedynie w przypadku skojarzenia i skrzyżowania par komplementarnych. Wówczas to 00 krzyżuje się z 11 dając 01 i 10 albo 01 krzyżuje się z 10 dając 11 i 00. Pełna tabela krzyżowania podanajest w tabl. 2.2, przy czym symbolu S użyto dla zaznaczenia, że potomstwo nie różni się od rodziców.
Tablica2.2.Tabelakrzyzowaniadlaproblemudwubitowego
X 00 01 10 11
00 S s s 01 : 10
01 S s 00 11 s
10 S 00 11 s s
11 01 11 10 s s , S '
Z tablicy tej widać, jak pary komplementarne gubią materiał genetyczny, choć strata ta stanowi jednocześnie zysk dla konkurencyjnych par komplementarnych. Na podstawie tych danych możemy wypisać dokładniejsze zależności dla oczekiwanych frekwencji P każdego z czterech współzawodniczących schematów. Musimy w tym celu uwzględnić w odpowiedni sposób oczekiwane straty i zyski schematów wynikające z krzyżowania. Zakładając reprodukcję proporcjonalną, krzyżowanie proste i losowe kojarzenie produktów reprodukcji otrzymujemy następujący rekurencyjny układ równań nieliniowych:
p'+\ = p ' . /j_l [ j _ "' /on p i 1 + / /OK/IO p r p r
p<+l_pr /'<>fl n'^0' P' 1 I n' ^00^" P' P' r II) 'll) ' ~7~ ! Pc ^T^ M)l ^r Fc- ~72 rno'll
pt pt
M)0 '11
t+i _ p r oi i "' f"> p , , > /no/ii , ,
- M)l ' ~=r\ ' ~ Pc ~r" ^
p<+l_p/
'/k[i -p'.^Lp'
, "' ^"^ "c
' /01/10 pt p! ^2 M" 'K'
W równaniach tych wskaźniki górne reprezentują czas, a dolne - schematy. Symbol /oznacza aktualne (w pokoleniu t) średnie przystosowanie populacji, które można ob-liczyćzewzoru: ...... , ,,,,.,
/= M)o/>o + fiofm + ffofio +
68
2. Podstawy matematyczne algorytmów genetycznych
Parametr p'c określa prawdopodobieństwo, że krzyżowanie nastąpi w punkcie leżącym miedzydwomaskrajnymipozycjamischematu: <
P'<=Pc-
8(fl)
/-1
Łącznie równania te wyznaczają oczekiwane frekwencje czterech schematów w następnym pokoleniu. Mając zadane początkowe frekwencje, możemy więc prześledzić przebieg trajektorii oczekiwanych frekwencji w kolejnych pokoleniach. Warunkiem koniecznym zbieżności algorytmu genetycznego jest, aby oczekiwany udział schematu optymalnego dążył w granicy do jedności:
limP/, = l
t~>DO
Aby poznać własności powyższych równań, przyjrzymy się kilku rozwiązaniom numerycznym dla problemów odpowiednio typu I i II. Przedstawione zostaną także - bez dowodu - pewne wyniki teoretyczne.
2.6.2. MDP: wyniki symulacyjne
Na rysunku 2.10 pokazano rezultaty obliczeń reprezentatywne dla zagadnień typu I. W fazie początkowej frekwencja schematu optymalnego (11) maleje; w miarę jednak, jak zmniejsza się również udział schematów 10 i 00, ostateczna "bitwa" rozgrywa się między dwoma schematami 11 i 01, i w końcu 11 wygrywa. Można pokazać, że wynik ten pozostaje słuszny dla dowolnego problemu typu I, przy założeniu o niezerowych
TYP I: F01>FOO
50
Pokolenie
Rys. 2.10. Rozwiązanie numeryczne dla minimalnegoproblemu zwodniczegotypu I: r = 1,1, c = 1,05, c' = 0,0
2.6. Minimalny problem zwodniczy
69
frekwencjach początkowych wszystkich czterech schematów. Jest to nieco zaskakujące, gdyż problem został pomyślany tak, aby spowodować rozminięcie się algorytmu z optimum globalnym. Krótko mówiąc, analiza dynamiczna wykazuje, że minimalny problem zwodniczy typu I nie jest problemem AG-trudnym.
Rysunki 2.11 i 2.12 obrazują rezultaty obliczeń dla MDP typu II. Na rysunku 2.11 widzimy reprezentatywne wyniki, odpowiadające Qak w przypadku typu I) zbieżności rozwiązania do optimum mimo występującej zwodniczości. Jednak nie wszystkie problemy typu II zachowują się w taki sposób; jeśli komplementarny schemat 00 występuje inicjalnie w nadmiernej proporcji, to schemat 11 może ulec przewadze, co kończy się zbieżnością do rozwiązania suboptymalnego. Reprezentatywne wyniki odpowiadające
TYP II: FOO>F01
Przypadek zbieżny
n) 'o^
J 0,5
0>
ul
BO Pokolenie
100
Rys. 2.11. Rozwiązanie numeryczne dla minimalnego problemu zwodniczego typu II (przypadek "zbieżny"): r=1,1, c = 0,9, c' = 0,5. Jednakowe frekwencje początkowe
TYPII:FOO>F01
Przypadek rozbieżny
JO,5
50
Pokolenie
100
Rys. 2.12. Rozwiązanie numeryczne dla minimalnego problemu zwodniczego typu II (przypadek ,,rozbiezny"): r = 1,1, c=0,9, c'=0,5. Niejednakowefrekwencje początkowe
''
70
. 2. Podstawy matematyczne algorytmów genetycznych
temu ostatniemu przypadkowi pokazano na rys. 2.12. Można podać proste warunki dostateczne na to, by problemy typu II miały rozwiązania zbieżne do optimum (Goldberg, 1987b); co dziwniejsze, wszystkie problemy typu II mają tę własność dla większości warunków początkowych.
W ostatnim czasie (Bridges, Goldberg, 1987; Goldberg, 1987a) przedstawioną tu metodę analizy udało się rozszerzyć na problemy wyższego rzędu. Dzięki innym pracom należącym do tego samego nurtu być może uda się podać konstruktywną definicję problemów AG-trudnych. Wszystko to odnosi się, oczywiście, do kodowania stałopozycyj-nego. Operacje rekonfiguracji, takie jak inwersja, są być może odpowiedzią przyrody na problemy zbyt trudne dla elementarnego AG. Omówienie podobnych operacji oraz ich analizę odłożymy do rozdziału 5.
2.7. Jeszcze o schematach: wzorce podobieństwa jako hiperpłaszczyzny___________________
W ostatnich dwóch punktach spoglądaliśmy na schematy z dwóch punktów widzenia: przedstawienie graficzne ukazało związek przetwarzania schematów z operacjami na funkcjach okresowych, natomiast minimalny problem zwodniczy pozwolił nam ujrzeć je w kontekście współzawodnictwa ekologicznego. Jeszcze inne dogodne ujęcie uzyskamy, przyjmując bardziej geometryczny sposób patrzenia na leżącą u podstaw przestrzeń ciągów kodowych.
W celu pobudzenia wyobraźni geometrycznej, rozważmy ciągi i schematy o długości / = 3. Przy tak krótkich ciągach nietrudno przedstawić naszą przestrzeń poszukiwań w postaci graficznej (rys. 2.13). Punktami tej przestrzeni są ciągi kodowe lub schematy rzędu 3. Linie proste, jak widać na d:agramie, odpowiadają schematom rzedu 2. Płaszczyzny są schematami rzędu 1, a całej przestrzeni odpowiada schemat rzędu 0, czyli ***.
1* Pteszczyzna
.11* Prosta
Pteszczyzna
Rys. 2.13. Schematyjako hiperpłaszczyznyw przestrzenitrójwymiarowej
2.8. Podsumowanie
71
Prawidłowości te przenoszą się na przypadek przestrzeni o większej liczbie wymiarów, musimy jednak porzucić przy tym proste wyobrażenia geometryczne ograniczone do przestrzeni trójwymiarowej. Punkty, proste i płaszczyzny odpowiadające schematom o długości 3 przechodzą w przestrzeni rc-wymiarowej w hiperpłaszczyzny o różnych wymiarach. Możemy więc uważać, że w poszukiwaniu lepszych rozwiązań algorytm genetyczny "przenika podziały" tworzone przez różne hiperpłaszczyzny.
2.8. Podsumowanie
W niniejszym rozdziale dokonaliśmy bardziej rygorystycznej oceny zachowania się algorytmu genetycznego za pomocą dokładnej analizy schematów (wzorców podobieństwa). Najważniejszy wynik, zawarty w podstawowym twierdzeniu algorytmów genetycznych, stwierdza, że dobrze przystosowane schematy o małej rozpiętości i niskim rzędzie rozprzestrzeniają się w kolejnych pokoleniach w rosnących co najmniej wykładniczo porcjach. Dzieje się tak, ponieważ wskutek reprodukcji lepsze schematy otrzymują większą liczbę reprezentantów, a krzyżowanie proste nie narusza zbyt często schematów o małej rozpiętości. Mutacje występują stosunkowo rzadko, nie wywierają więc wielkiego wpływu na te ważne schematy. Wykładniczy charakter propagacji znajduje swoje racjonalne uzasadnienie w związku z optymalnym rozwiązaniem zagadnienia dwura-miennego bandyty.
Dzięki takiemu sposobowi wyzyskiwania podobieństw, złożoność dowolnych problemów rozwiązywanych za pomocą algorytmu genetycznego ulega zmniejszeniu. Owe ponadprzeciętne, krótkie, niskiego rzędu schematy (zwane cegiełkami) stanowią w pewnym sensie rozwiązania częściowe, a algorytm genetyczny odkrywa nowe rozwiązania drogą rekombinacji najlepszych częściowych rozwiązań obecnych w bieżącej populacji.
U podstaw elementarnego algorytmu genetycznego leży założenie, zwane hipotezą cegiełek, zgodnie z którym składanie schematów-cegiełek prowadzi istotnie do ulepszania rozwiązań. Transformacje Walsha dostarczają ważnego narzędzia służącego do rozstrzygania, czy określony problem nadaje się do rozwiązania za pomocą elementarnego algorytmu genetycznego. Wyniki prac prowadzonych na tym polu zdają się wskazywać, że funkcje AG-trudne (tzn. takie, które nie dają się łatwo optymalizować za pomocą elementarnego algorytmu genetycznego) zawierają izolowane optima, na podobieństwo igły w stogu siana; takie przypadki sprawiają jednak kłopot również innym technikom otymalizacji, nie tylko algorytmom genetycznym.
Dzięki analizie minimalnego problemu zwodniczego (MDP) - najprostszego problemu, mogącego potencjalnie "zwieść na manowce" elementarny algorytm genetyczny - uzyskaliśmy dodatkowy wgląd w jego zachowanie. Wydaje się zaskakujące, że dla większości prawdopodobnych warunków początkowych MDP nie jest AG-trudny. Inaczej mówiąc, choć skonstruowaliśmy trudną i zwodniczą funkcję (z silną epistazą), algorytm genetyczny najczęściej nie pozwala wyprowadzić się w pole. Jest to okoliczność zachęcająca i bez wątpienia w znacznym stopniu odpowiedzialna za sukcesy empiryczne algorytmów genetycznych w rozwiązywaniu zagadnień, w których występuje epistaza.
72
. 2. Podstawy matematyczne algorytmów genetycznych
Rozumiejąc już lepiej działanie algorytmów genetycznych, w następnym rozdziale zaprogramujemy elementarny algorytm genetyczny w Pascalu i zbadamy jego zachowa-niedlaprzykładowegozadania. :.,,..>i-,
2.9. Zadania
2.1. Rozważmy trzy ciągi kodoweA, = 11101111, A2 = 00010100 i A3 = 01000011 oraz sześć schematów #, = !*******, ft, = 0*******, #3 = ******11, #4=***0*00*, H5 = l*****l* i Hf,= ll\Q**l*. Które schematy pasują do których ciągów? Podaj
��� rząd i rozpiętość dla każdego z powyższych schematów. Oszacuj prawdopodobieństwo przeżycia przy mutacji każdego z tych schematów dla prawdopodobieństwa pojedynczej mutacji pm = 0,OQl. Oszacuj prawdopodobieństwo przeżycia schematów przy krzyżowaniu dla prawdopodobieństwa krzyżowania^t. = 0,85.
2.2. Populacja składa się z następujących ciągów kodowych w pokoleniu 0:
Nr Ciąg Przystosowanie
1
2 3 4
10001 11100 00011 01000
20
10
5
15
Prawdopodobieństwo mutacji wynosipm = 0,01, a prawdopodobieństwo krzyżowania^.= 1,0. Wyznacz oczekiwaną liczbę reprezentantów schematów 1**** i ()#*1* w pokoleniu 1.
2.3. Obmyśl trzy metody dokonania reprodukcji i oszacuj oczekiwaną liczbę reprezentantów schematów w następnym pokoleniu dla każdej z tych metod.
2.4. Przypuśćmy, że wykonujemy operację typu krzyżowania, w której wybiera się dwa punkty krzyżowania i wymienia segmenty ciągów zawartych między tymi dwoma punktami:
x x x I x x I x x
yyy i yy i yy
x x x y y x x
yyy
Wyznacz dolne ograniczenie prawdopodobieństwa przeżycia schematu o rozpiętości 8 i rzędzie o dla tej operacji. Wykonaj analogiczne obliczenia dla przypadku, gdy traktujemy ciągi jak zamknięte pierścienie (tzn. zakładamy, że lewy koniec sąsiaduje z prawym).
2.5. Ile istnieje schematów dla ciągów kodowych o długości /= 10, 20, 30, jeśli używa-
�' my alfabetu dwójkowego? Ile istnieje takich schematów rzędu 3? Podaj rozsądne
ograniczenia dolne i górne dla liczby schematów biorących udział w przetwarzaniu
2.10. Ćwiczenia komputerowe
73
przy długości ciągów /=10, 20, 30 i wielkości populacji m = 50. Przyjmij, że rozmiar znaczących schematów-cegiełek wynosi 10% pełnej długości ciągu.
2.6. Przypuśćmy, że ciągi kodowe pasujące do schematu H mają wskaźnik przystosowania o 25% wyższy od średniej dla bieżącej populacji. Jeśli prawdopodobieństwa zniszczenia tego schematu podczas mutacji i krzyżowania są zaniedbywalne i jeśli w pokoleniu 0 występuje jeden reprezentant rozważanego schematu, to w którym pokoleniu schemat H zmonopolizuje populacje o wielkościach n = 20, 50, 100 i 200?
2.7. Przypuśćmy, że ciągi kodowe pasujące do schematu H mają wskaźnik przystosowania o 10% niższy od średniej dla bieżącej populacji. Jeśli prawdopodobieństwa zniszczenia tego schematu podczas mutacji i krzyżowania są zaniedbywalne i jeśli 60% ciągów kodowych w pokoleniu 0 pasuje do rozważanego schematu, to w którym pokoleniu schemat H zniknie z populacji o wielkościach n = 20, 50, 100 i 200?
2.8. Wyprowadź dokładniejszy wzór na liczbę schematów reprezentowanych w wygenerowanej losowo populacji o wielkości m, jeśli długość ciągów kodowych wynosi /. (Wskazówka: Wyznacz prawdopodobieństwo braku reprezentantów schematów danego rzędu i oblicz stąd prawdopodobieństwo wystąpienia schematów mających jednego lub więcej reprezentantów.)
2.9. Zaznaczobszaryodpowiadająceschematom 1******, ******o, 111111*, 10*****, *****01, **lH** w przestrzeni rozwiązań {0, 1, ..., 127} przy zastosowaniu dwójkowego zapisu pozycyjnego.
2.10. Ćwiczenia komputerowe
A. Funkcja przystosowania dlajednobitowych ciągów kodowych przyjmuje dwie warto-sci/,=const i/o = const. Wyprowadź związki rekurencyjne dla oczekiwanych frekwencji jedynek w procesie reprodukcji, zakładając nieskończoną wielkość populacji. Napisz odpowiedni program i wyznacz zajego pomocą oczekiwane frekwencje jedynek dla kolejnych pokoleń od 0 do 100, zakładając równe frekwencje początkowe zer i jedynek i przyjmując, że stosunek r=f\/f{} wynosi 1,1, 2, 10.
B. Wykonaj ćwiczenie A dla przypadku reprodukcji połączonej z mutacją, przy prawdopodobieństwach mutacjipm = 0,001, 0,01, 0,1.
C. Rozważmy następujące schematy rzędu 2 i odpowiadające im wskaźniki przysto-
sowania:
**]***i*# **l***0** **0***l**
**o***o**
/n /,o /o,
/00
Zakładając stałość wskaźników przystosowania, wypisz związki rekurencyjne dla frekwencji każdego z czterech powyższych schematów (11, 10, 01, 00) w procesie
74
2. Podstawy matematyczne algorytmów genetycznych
D.
E.
reprodukcji połączonej z krzyżowaniem i mutacją. Upewnij się, że uwzględniłeś we właściwy sposób wyrazy określające "zyski" i "straty" z tytułu krzyżowania. Napisz odpowiedni program i dokonaj symulacji zachowania się dużej populacji dla danych z rys. 2.10. Porównaj wyniki otrzymane d\apm = 0,OOl, 0,01 i 0,1 z wynikami przedstawionymi na rys. 2.10.
Oblicz średnie wskaźniki przystosowania dla wszystkich 35 schematów w przypadku funkcji przystosowania/(*)=*2 określonej dla liczb całkowitych z przedziału |0, 31] i kodowania przy użyciu pięciopozycyjnego zapisu dwójkowego. Stwierdź na podstawie otrzymanych wyników, czy masz do czynienia z problemem zwodniczym. Obmyśl funkcję przystosowania i trzybitowy kod określające problem AG-zwod-niczy. Dowiedź jego zwodniczości obliczając średnie wskaźniki przystosowania wszystkich 33 schematów.