Rozdział 4
Niektóre zastosowania algorytmów genetycznych

Parafrazując znany żart: "Jeśli algorytmy genetyczne są takie sprytne, to dlaczego nie są bogate?'' W istocie, algorytmy genetyczne są bogate - bogate w zastosowania w wielkiej i wziąż rosnącej liczbie dyscyplin. W tym rozdziale zaprezentujemy przekrój zastosowań algorytmów genetycznych od dawnych do najnowszych, od czystych do stosowanych - w dziedzinach tak różnorodnych, jak matematyka, medycyna, technika i politologia. Nasz cel jest trojaki. Po pierwsze, potrzebujemy perspektywy historycznej, aby lepiej zrozumieć, jakim sposobem "sztuka" algorytmów genetycznych rozwinęła się do obecnego poziomu. Po drugie, liznąwszy w poprzednim rozdziale nieco programowania, teraz musimy przekopać się przez prace innych, aby poznać praktyczną stronę zastosowań. I w końcu, studiując rozmaite zastosowania algorytmów genetycznych, kontynuujemy gromadzenie dowodów na rzecz sformułowanej wcześniej tezy o odporności tychże algorytmów; wśród porównywalnych metod nie mają one sobie równych pod względem różnorodności zastosowań i efektywności działania.
Przegląd zastosowań rozpoczynamy od zapoznania się z wczesnymi symulacjami komputerowymi naturalnych procesów genetycznych oraz innymi prehistorycznymi śladami algorytmów genetycznych. Po omówieniu kilku dawniejszych zastosowań, począwszy od pionierskiej rozprawy Bagleya, aż po przełomową pracę De Jonga z zakresu optymalizacji funkcji, czeka nas potpourri aktualnych zastosowań, zaczerpniętych z techniki, medycyny i nauk społecznych. ;
4.1. Powstanie algorytmów genetycznych
Zanim zaczęto stosować algorytmy genetyczne jako algorytmy wyszukiwania w dowolnego typu problemach, pewna liczba biologów używała komputerów do symulacji proce-
4.1. Powstanie algorytmów genetycznych .
105
sów genetycznych (Barricelli, 1957, 1962; Fraser, 1960, 1962; Martin i Cockerham, 1960). Chociaż celem tych badań było wyjaśnienie zjawisk naturalnych, praca Frasera nie była zbyt odległa od współczesnego rozumienia algorytmu genetycznego. W swej pracy rozpatrywał on funkcję fenotypową postaci
Fenotyp = a + qa \a\ + ca3
Z piętnastobitowego ciągu reprezentującego genotyp pięć bitów przeznaczone było na parametr a, pięć na parametr b i dalsze pięć na parametr c. Fraser wykazał za pomocą serii wykresów (zreprodukowanych tu na rys. 4.1) istnienie interakcji między różnymi
o=o,o
Q. f 0 Genotyp
Q=1,O.C = 0,0 = 0,0;C = 0,9
Q=0,0;C=1,0
0 Genotyp
Rys. 4.1. Funkcja epistatyczna Frasera dla różnych wartości parametrów. Przedruk za zezwoleniem z Journal of Theoretical Biology, vol. 2, 1962, Academic Press London Ltd.
parametrami. W przeprowadzonych przez niego symulacjach selekcja polegała na wyborze jako rodziców tych genotypów, dla których funkcja fenotypowa przybierała wartości w określonych granicach (od -1 do +1). Fraser symulował ewolucję populacji genotypów i wyznaczał dla kolejnych pokoleń stosunek procentowy osobników o akceptowalnych genotypach. Wyniki tych komputerowych symulacji pokazane są na rys. 4.2.
Chociaż wspomniane wyniki przypominają nieco optymalizację funkcji, w pracy Frasera nie ma wzmianki o możliwości zastosowania algorytmu wyszukiwania wybranego przez przyrodę w niebiologicznym kontekście. Dopiero Hollandowi i jego studentom przypadło w udziale po raz pierwszy użyć operacji gwas/-genetycznych w zagadnieniach sztucznej adaptacji. Holland położył podwaliny pod te zastosowania w swych pracach na temat teorii systemów adaptacyjnych (Holland, 1962a-c). Jak można się przekonać z następującego cytatu (Holland, 1962c, str. 298), stawiał on sobie dość rozległy cel:
Studium adaptacji obejmuje zarówno adaptujący się system, jak i jego środowisko. Mówiąc ogólnie, jest to studium dotyczące sposobów, dzięki którym systemy mogą wytwarzać proce-
. rV.
106
4. Niektóre zastosowania algorytmów genetycznych
100
i
I 100
%
>, c
i 0
8 100
o 100
g
o.
20 rodziców
40 rodziców
80 rodziców
10
160 rodziców
j______l
20
30 40
50
0 50
0 50
0 50
50

nr
T> O 0)
'c
^D
2 -co
10 20 30 40 50
Rys. 4.2. Wyniki symulacji genetycznych dla funkcji epistatycznej Frasera przy różnych wielkościach populacji. Przedruk za zezwoleniem z Journal of Theoretical Biology, vol. 2, 1962, Acade-mic Press London Ltd.
dury umożliwiające im skuteczne dopasowanie się do swych środowisk. Jeśli w punkcie wyjścia nie zawęzimy arbitralnie pojęcia adaptacji, system adaptacyjny musi być zdolny do wytworzenia dowolnej metody lub procedury dającej sie efektywnie zdefiniować.
Nie są to słowa człowieka, który najzwyczajniej w świecie szukajeszczejednej metody rozwiązania tego czy innego zadania optymalizacji. Celem Hollanda było i nadal pozostaje stworzenie teorii oraz reguł, według których można będzie tworzyć ogólne programy i maszyny o nieograniczonych zdolnościach adaptacji do dowolnych środowisk. Jednocześnie Holland dostrzega fundamentalne znaczenie sztucznej selekcji - mechanicznego odpowiednika zasady przetrwania najlepiej przystosowanych - we wszelkich możliwych do pomyślenia programach lub maszynach (str. 300):
A zatem adaptacja zasadza się na selekcji różnicującej programów zarządzających. To jest, im większe "powodzenie" odnosi program zarządzający w sensie zdolności kierowanych przez siebie programów wykonawczych do znajdowania rozwiązań, tym bardziej dominującą (w liczbie kopii) pozycję zdobywa on sobie w populacji programów zarządzających.
Holland nie tylko dostrzegł potrzebę selekcji, ale w sposób nie budzący wątpliwości poparł podejście populacyjne do zadań poszukiwania, wbrew panującemu podówczas w literaturze podejściu punkt-za-punktem. Warto zauważyć, że w tych najwcześniejszych pracach Holland wspomniał jedynie pośrednio o znaczeniu krzyżowania lub innych rekombinacyjnych operacji genetycznych. Pierwsza bezpośrednia uwaga na ten temat pojawia się trzy lata później (Holland, 1965, str. 216): . , :,
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
107
Istnieją jednak techniki próbkowania funkcji na zbiorze bazowym ogólniejsze od metody Samuela. Dla danego zbioru bazowego techniki te, blisko związane ze znanymi w genetyce współzależnymi zjawiskami crossing-over, sprzężenia [linkage] i dominowania, zapewniają osiągnięcie ścisłej suboptymalności [strict near optimality} w znacznie szerszej klasie środowisk.
W czasie, gdy jego idee dojrzewały, Holland wykładał systemy adaptacyjne na Uniwersytecie Michigan. Jego słuchacze dokonywali podówczas symulacji adaptacyjnych algorytmów genetycznych w odniesieniu tak do układów biologicznych, jak i pozabiologi-cznych; niestety świadectwa pisane większości tych usiłowań nie zachowały się. Wiemy z pewnością, że używano w tym czasie operacji reprodukcji, krzyżowania i mutacji niemal w tej samej postaci, jak czyni się to dzisiaj. Niebawem zapoznamy się z tą częścią dojrzewającego młodego pokolenia, której udało się dorosnąć do rozprawy doktorskiej. Sam Holland, kontynuując wcześniejsze prace o bardziej spekulatywnym charakterze, przeniósł teorię adaptacyjnych systemów genetycznych na twardy grunt matematyki (Holland, 1966, 1967, 1969a, 1969c). Mająca duże znaczenie teoria schematów była gotowa mniej więcej pod koniec dekady (Holland, 1968, 1971), a zaraz potem zostały opublikowane wyniki dotyczące związków między planami reprodukcji a zagadnieniem &-ramiennego bandyty (Holland, 1973a, 1975).
4.2. Przegląd historyczny ważniejszych zastosowań ____________________algorytmów genetycznych
4.2.1. Bagley i adaptacyjny program gry w sześć pionków
Pierwsza wzmianka o algorytmach genetycznych i pierwsze opublikowane doniesienie na temat zastosowania algorytmu genetycznego pojawiły się w pionierskiej rozprawie doktorskiej Bagleya (1967). Panowało wówczas wielkie zainteresowanie komputerami grającymi w gry strategiczne i w tym duchu Bagley opracował kontrolowane środowisko doświadczalne do badania programów grających, zaprojektowane dla gry w sześć pionków. Gra w sześć pionków jest rozgrywana na szachownicy zredukowanej do dziewięciu (3x3) pól (por. rys. 4.3). Każdy z graczy ma początkowo do dyspozycji trzy pionki i próbuje dostać się na stronę przeciwnika. Dostosowując odpowiednio poziom gry przeciwnika, Bagley był w stanie kontrolować stopień nieliniowości procesu (zwany przez niego "głębokością procesu").
Bagley zaprojektował algorytmy genetyczne służące do określania zbioru parametrów używanych w funkcjach oceniających i porównywał je z algorytmami korelacyjnymi - procedurami uczącymi się, opartymi na ówczesnych algorytmach zmiany wag (por. Friedberg, 1958; Samuel, 1959; Uhr i Vossler, 1961). Niejest zaskoczeniem, że Bagley stwierdził potrzebę daleko idącej zgodności między nieliniowością gry, a nieliniowością algorytmu korelacyjnego. Natomiast algorytm genetyczny Bagleya okazał się niewrażliwy na nieliniowość gry i dawał dobre wyniki dla całego zakresu środowisk (głębokościprocesów). ,.
4. Niektóre zastosowania algorytmów genetycznych
Rys. 4.3. Plansza gry w sześć pionków , ,
Algorytm genetyczny Bagleya wykazuje duże podobieństwo do algorytmów używanych dzisiaj. Zaprojektował on operacje reprodukcji, krzyżowania i mutacji zbliżone do tych, które opisaliśmy w poprzednim rozdziale; ponadto zastosował reprezentacje diploidalną, mechanizm dominowania oraz inwersje. (O tych ostatnich powiemy więcej w następnym rozdziale.) Bagley używał do kodowania alfabetów niedwójkowych. Jak wiemy z wcześniejszych rozważań na temat schematów, istnieją poważne przesłanki, by stosować alfabety minimalne. Bagley nie znał jednak teorii schematów Hollanda, nie mógł więc kierować się nią w swej pracy.
Na polu reprodukcji i selekcji praca Bagleya stanowiła zapowiedź przyszłych rozwiązań. Bagley miał jasną świadomość, że tempo selekcji musi być odpowiednio dobierane w początkowej i końcowej fazie wykonywania algorytmu. Wprowadził więc mechanizm skalowania, aby osiągnąć dwie rzeczy: zmniejszyć presję selekcyjną we wczesnej fazie przebiegu, zapobiegając w ten sposób zdominowaniu populacji przez jednego su-perosobnika oraz zwiększyć presję w późniejszej fazie, aby utrzymać odpowiedni poziom konkurencji wśród wysoko przystosowanych i podobnych do siebie osobników przed ujednoliceniem się populacji. W podobny sposób postępują dzisiejsi badacze.
Bagley przedstawił również jako pierwszy pomysł samoregulacji algorytmu genetycznego. Zaproponował mianowicie kodowanie prawdopodobieństw krzyżowania i mutacji w samych chromosomach; nie podał jednak żadnych wyników eksperymentalnych dotyczących tego mechanizmu.
4.2.2. Rosenberg i symulacja żywej komórki
W tym samym czasie co Bagley, również Rosenberg (1967) pracował nad rozprawą doktorską poświęconą algorytmom genetycznym. Jednak jego wkład w tę gałąź wiedzy bywa niekiedy niezauważany, gdyż podkreślał on głównie stronę biologiczną i stronę symulacyjną swej pracy. W rozprawie Rosenberg zajął się symulacją populacji jedno-
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych
109
komórkowych organizmów o nieskomplikowanej, ale dobrze określonej biochemii, wyposażonych w przepuszczalną błonę komórkową i klasyczną strukturę genetyczną ^eden gen, jeden enzym). Pomimo nacisku na stronę biologiczną, praca Rosenberga miała istotne znaczenie dla przyszłego rozwoju pozabiologicznych zastosowań algorytmów genetycznych, ze względu na podobieństwo do zagadnień optymalizacji i wyznaczania miejsc zerowych funkcji. Nie będziemy tu wchodzić w szczegóły jego modeli kinetyki chemicznej, jednak pewne aspekty modelu genetycznego są interesujące. Rosenberg posługiwał się dwuchromosomowym ciągiem kodowym (reprezentacja diploidalna). Długość ciągu była ograniczona do 20 genów, przy czym każdy gen mógł mieć do 16 alleli. Rosenberg rozważał stężenia składników chemicznych Xj oraz pożądane stężenia tychże składników xf. Układ pożądanych stężeń nazwał właściwością tyroperty]. Jako kryterium przy kojarzeniu par i selekcji brana była pod uwagę wartość funkcji "antyprzystosowa-nia" (dla /-tej właściwości):
gdzie sumowanie rozciąga się na wszystkie składniki chemiczne wchodzące do /-tej właściwości. Rosenberg obliczał odwrotności wielkości f-t i przeprowadzał kojarzenie, a następnie reprodukcję stosownie do tego odwrotnego antyprzystosowania. W eksperymentach symulacyjnych ograniczył się jednak tylko do jednej właściwości i w rezultacie przepuścił szansę wykonania pierwszej próby z wielokryterialnym algorytmem genetycznym, czego dokonał dopiero Schaffer (1984). Niemniej jednakjego eksperymenty były pierwszym przypadkiem zastosowania algorytmu genetycznego do wyznaczania pierwiastków równań; jeśli spojrzeć na to z odpowiedniego punktu widzenia, znalezienie komórek minimalizujących funkcję antyprzystosowania jest równoważne rozwiązaniu wysoce nieliniowego równania (wyznaczonego przez chromosomy i biochemię komórki), określającego daną właściwość.
Podobnie jak w przypadku Bagleya, praca Rosenberga poprzedziła teorię schematów Hollanda, wskutek czego zastosował on również alfabet niedwójkowy. Takjak Bag-ley, Rosenberg starał się wymyślić sposób na zapewnienie dostatecznie dużej presji w procesie selekcji. Użył w tym celu funkcji, którą nazweAfunkcją generacyjnąpotomst-wa (offspring generation function, OGF). Określił mianowicie wielkość s, związaną ze znormalizowanym antyprzystosowaniem osobników rodzicielskich tfJf}. Opierając się na tej wielkości, określał liczbę potomków zgodnie z funkcją OGF, której wykres pokazano na rys. 4.4.
Innym ciekawym aspektem jego pracy jest mechanizm krzyżowania adaptacyjnego. Każdemu genowi został przyporządkowany tzw. współczynnik sprzężenia xt, dziedziczony wraz z allelem. Współczynniki sprzężenia, przyjmujące wartości całkowite od 0 do 7, ulegały replikacji podczas selekcji, a następnie były poddawane krzyżowaniu wraz ze swymi allelami. Rosenberg nie stosował całkowicie losowego wyboru punktów krzyżowania, ale wybierał je zgodnie z rozkładem prawdopodobieństwa określonym przez współczynniki sprzężenia:
110
4. Niektóre zastosowania algorytmów genetycznych
� ' '' � �: 5 � Liczba 4 potomstwa 3' 2 1 ' 0 i �� '�<'


, ... � ��� ���
, ,:�' �-

0,0
0,5
1,5
s. fi+fi
Rys. 4.4. Funkcja generacyjna potomstwa (OGF). Za Rosenbergiem (1967)
Wielkość Pj oznacza tu prawdopodobieństwo skrzyżowania w punkcie i. Rosenberg podał przykład demonstrujący, że krótkodystansowość sprzężeń wywiera znaczny wpływ na otrzymywanie dobrych wyników; istotnie, w trakcie symulacji współczynniki sprzęże-niaewoluowaływkierunku,,skracania"sprzeżeń. '
4.2.3. Cavicchio i rozpoznawanie postaci
Po przygotowaniu gruntu przez Bagleya i Rosenberga nie trzeba już było długo czekać na następne zastosowania algorytmów genetycznych. W swym studium z 1970 r. pt. ,,Adaptive Search Using Simulated Evolution" (Poszukiwanie adaptacyjne na drodze symulowanej ewolucji), Cavicchio użył algorytmu genetycznego do rozwiązania dwóch problemów poszukiwania: zadania wyboru podprogramu i zadania rozpoznawania postaci. Ze względu na złożoność i związek z aktualną problematyką zajmiemy się bliżej rozważanym przez niego problemem rozpoznawania postaci.
W rzeczywistości Cavicchio nie zmierzył się bezpośrednio z problemem rozpoznawania postaci. Zastosował zamiast tego algorytm genetyczny do zaprojektowania zestawu detektorów dla urządzenia rozpoznającego o znanej architekturze. Aby dobrze zrozumieć, co oznacza "zaprojektowanie zestawu detektorów", musimy wpierw zapoznać się z konstrukcją urządzenia rozpoznającego, o którym mowa.
Cavicchio przyjął metodę rozpoznawania postaci, podaną przez Bledsoe'a i Browninga (1959). W metodzie tej obraz zostaje przetworzony do postaci cyfrowej, tworząc siatkę o rozmiarach 25 x 25 złożoną z 625 elementów (pikseli), przy czym każdy piksel jest pikselem binarnym, zdolnym do odróżnienia tylko dwóch odcieni, jasnego i ciemnego. Wybiera się zestaw określonych "detektorów cech"; każdy detektorjest przy tym tożsamy z pewnym podzbiorem pikseli. Podczas fazy treningowej urządzeniu rozpoznającemu prezentuje się znane obrazy należące do zarejestrowanych klas, a listy stanów detektorów zostają skojarzone z nazwami klas i zapamiętane. W fazie roz-
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
111
poznawania urządzenie otrzymuje nieznany obraz i określa stopnie podobieństwa. Następnie urządzenie generuje listę klas uporządkowaną według stopnia podobieństwa do nieznanego obrazu. Chociaż mechanizm ten jest sam w sobie całkiem prosty, metoda daje dobre wyniki tylko pod warunkiem, że wybrano odpowiedni dla danego zadania (w danym przypadku chodzi o rozpoznawanie znaków graficznych) zestaw detektorów. Tak więc problem skutecznego działania maszyny Bledsoe'a i Browninga sprowadza się do znalezienia dobrego zestawu detektorów. Cavicchio zastosował algorytm genetyczny do tego właśnie zadania.
W tym celu Cavicchio dopuścił średnio 110 detektorów na urządzenie Qeden projekt) i od dwóch do sześciu pikseli na detektor. Chromosomy (ciągi kodowe) składały się z naprzemiennych grup dodatnich i ujemnych liczb całkowitych. Przykładowo, następujący fragment chromosomu
+5 +372 [phone] +44 +348 . . .
przy takim sposobie kodowania przyporządkowuje pierwszemu detektorowi piksele 5, 372 i 9, drugiemu - piksele 518, 213, 35 i 76, i tak dalej. Odnotujmy mimochodem użycie dużego alfabetu i nietypową strukturę chromosomu z genami zmiennej długości. Możemy także wywnioskować, że z rozważanym zadaniem jest związana bardzo wielka przestrzeń rozwiązań. Aby dokonać porównania z zadaniami kodowanymi dwójkowo, spróbujmy oszacować liczbę bitów niezbędnych do zakodowania jednego rozwiązania w alfabecie dwójkowym. Przyjmując średnio 110 detektorów i cztery piksele na detektor, wymagana liczba bitów będzie wynosić
/ = 110 �
Jest wciąż jedno z największych pod względem rozmiaru zadań, jakie kiedykolwiek próbowano rozwiązać przy użyciu algorytmu genetycznego.
W swoim algorytmie genetycznym Cavicchio posługiwał się reprodukcją i krzyżowaniem w sposób podobny do tego, jak to robimy dzisiaj. Wykonał on próby z kilkoma wariantami operacji selekcji (reprodukcji) i ostatecznie wybrał taki, który nagradzał wysoko przystosowane osobniki, nie pozwalając im jednak zawładnąć zbyt wielką częścią populacji. Zastosowana przezeń operacja krzyżowania prostego przypomina podobną operację opisaną we wcześniejszych rozdziałach, z tą różnicą, że punkt krzyżowania może tam wypadać jedynie na styku detektorów (tj. między naprzemiennymi grupami dodatnich i ujemnych liczb całkowitych). Z powodu zmiennej długości genu oraz dużego alfabetu Cavicchio był zmuszony wymyślić trzy warianty mutacji:
u, - -l
Mutacja 1 - zmiana jednego piksela w detektorze. Mutacja 2 - zmiana wszystkich pikseli w detektorze. Mutacja 3 - wymiana pikseli w sąsiadujących detektorach.
Dopuszczał on również inwersję, krzyżowanie dwupunktowe i duplikacje wewnątrzchro-mosomowe, ale o tych zaawansowanych mechanizmach opowiemy szerzej dopiero w następnym rozdziale.
112
4. Niektóre zastosowania algorytmów genetycznych
Jedną z innowacji, które Cavicchio wprowadził w swych badaniach, był mechanizm tzw. preselekcji. Polegał on na tym, że osobnik potomny o dobrym przystosowaniu zastępował jednego ze swoich rodziców w nadziei utrzymania różnorodności populacji. Zachowanie różnorodności stanowiło problem z powodu niewielkich populacji (zazwyczaj 12-20 osobników), którymi Cavicchio był zmuszony posługiwać się. Preselekcja zdawała się w tym pomagać. Podobne rozwiązanie przyjął później z dobrym skutkiem De Jong (1975) w swym studium na temat optymalizacji.
Cavicchio, podobnie jak Bagley, był zafascynowany ideą adaptacji parametrów swego adaptacyjnego algorytmu; zamiast jednak wkodować prawdopodobieństwa krzyżowania i mutacji do chromosomow,jak sugerował Bagley, wybrał on metodę centralnej regulacji parametrów na podstawie danych o globalnym tempie poprawy wyników. Nie odbiegała ona zbytnio od innych, popularnych w owym czasie algorytmów zmiany wag, i nie będziemy tu wchodzić w jej szczegóły.
Musimy natomiast zatrzymać się na chwilę w tym miejscu i postawić kwestię stosowności użycia scentralizowanych danych w jakimkolwiek algorytmie adaptacyjnym zapożyczonym z naturalnej genetyki. Gdzie mianowicie w populacji biologicznej znajdują się przewody, wszechwiedząca inteligencja czy bóstwo, niezbędne do centralnego manipulowania parametrami? Jeśli nawet uznamy istnienie władzy centralnej, to jaki algorytm reguluje parametry sterujące głównego sternika? Na obie te wątpliwości znajdujemy w świecie biologicznym elegancką odpowiedź w postaci wkodowania parametrów sterujących do samych chromosomów. Jeśli pójdziemy za przykładem przyrody i zrobimy to samo w naszych sztucznych modelach, za jednym pociągnięciem wyeliminujemy potrzebę centralnego sterowania, unikając jednocześnie dylematu regressus ad infinitum.
Mimo filozoficznej niespójności koncepcji procesu genetycznego z centralnym sterowaniem, Cavicchio był w stanie eksperymentalnie wykazać pewną przewagę scentralizowanej adaptacji parametrów adaptacyjnych nad wyborem stałych parametrów. Do-
----------Eksperyment kontrolny
Wstępny plan reprodukcyjny Ulepszony plan reprodukcyjny
300
Liczba przetestowanych urządzeń
600
Rys. 4.5. Porównanie trzech mechanizmów adaptacyjnych dla zadania selekcji detektorów obrazów. ZaCavicchi'em(1970)
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
113
konał on porównania efektywności swego podstawowego algorytmu ("Wstępny plan reprodukcyjny"), jego ulepszonej wersji z mechanizmem adaptacji parametrów i różnymi "wodotryskami" ("Ulepszony plan reprodukcyjny"), schematu adaptacyjnego opartego na metodzie Klopfa (1965) ("Eksperyment kontrolny") oraz poszukiwania losowego ("3 odchylenia standardowe"). Otrzymane wyniki zostały podsumowane na rys. 4.5. Na wykresie pokazano zależność wydajności (maksymalna wydajnosc=100) od liczby przetestowanych urządzeń (liczby wypróbowanych kombinacji detektorów). Obie wersje algorytmu genetycznego wyprzedziły niegenetyczną metodę adaptacyjną oraz metodę przeglądu losowego.
4.2.4. Weinberg, symulacja komórki i algorytm _________________________________________________________ genetyczny z metapoziomu
Współcześnie z Cavicchiem, Weinberg kończył swoją rozprawę (1970), zatytułowaną "Computer Simulation of a Living Cell" (Symulacja komputerowa żywej komórki). Tak jak i w przypadku wcześniejszej pracy Rosenberga, wkład Weinberga w rozwój algorytmów genetycznych jest często zapoznawany z powodu nacisku położonego na symulację biologiczną. Jednakże Weinberg postawił - choć nie zbadał symulacyjnie - ciekawy problem optymalizacji algorytmu genetycznego. W rozdziale szóstym, pod tytułem "Symulacja komputerowa ewolucji DNA", Weinberg zaproponował użycie wielowarstwowego algorytmu genetycznego w celu dobrania odpowiedniego zestawu 15 stałych wpływających na funkcjonowanie różnych symulowanych komórek bakterii Escherichia coli. Podobnie jak Rosenberg, Weinberg pragnął doprowadzić do takiej adaptacji chromosomów, aby skład chemiczny komórek odpowiadał dostępnym składnikom.
Weinberg zaproponował w tym celu zakodowanie 15 stałych w postaci jednego ciągu, przy czym każda ze stałych mogłaby przyjmować wartości z zakresu od 10^* do 106. Krzyżowanie i inwersja nie mogły naruszać "wnętrza" parametrów, a użycie dużego alfabetu kodowego - jak w innych ówczesnych pracach - spowodowało konieczność zaprojektowania złożonej operacji mutowania (Weinberg nazwał ją mutacją kierowaną).
Podobnie jak Bagley i Cavicchio, Weinberg nie potrafił się oprzeć pokusie samo-adaptacji parametrów algorytmu genetycznego. Jednak Weinberg zaproponował w tym celu metodę diametralnie różną od pomysłów zarówno Bagleya, jak i Cavicchia. W szczególności poddał on myśl, aby zastosować algorytm genetyczny w celu adaptacji parametrów algorytmu genetycznego niższego rzędu. Weinberg nazwał algorytm genetyczny wyższego poziomu nieadaptacyjnym programem genetycznym, a algorytm genetyczny niższego poziomu - adaptacyjnym programem genetycznym Qego parametry ulegają adaptacji). Związki między obydwoma algorytmami a procesem symulacji komórki są uwidocznione w postaci schematu blokowego na rys. 4.6. Zgodnie z tym populacja złożona z 10 ciągów kodowych reprezentujących prawdopodobieństwa krzyżowania, inwersji i mutacji podlega selekcji, krzyżowaniu i mutacji. Otrzymane w ten sposób parametry zostają przekazane do adaptacyjnego programu genetycznego, który z kolei generuje i ocenia populacje (40-elementowe) stałych używanych następnie do symulacji komórek. Z kolei dane o tempie poprawy wyników symulacji zostają zwrotnie przekazane
114
4. Niektóre zastosowania algorytmów genetycznych
Nieadaptacyjny
program genetyczny
(metapoziom)
n=10
Parametry AG
A
V
Przystosowanie AG
Adaptacyjny program genetyczny n=40
Parametry komórek
V
/\
Przystosowanie komórek
Środowiska komórek
Rys. 4.6. Schemat wielowarstwowego algorytmu genetycznego wg propozycji Weinberga (1970)
do algorytmu genetycznego wyższego poziomu w celu dokonania oceny populacji parametrów, co umożliwia dalszą ich adaptacje. Weinberg był świadom faktu, że wprowadzenie do jego metody scentralizowanej informacji jest równoważne z postulowaniem interwencji wszechwiedzącej, wszechpotężnej instancji (1970, str. 101):
Użyteczność adaptacyjnego programu genetycznego określamy w sposób pośredni, korzystając z pomocy "nadprzyrodzonego" sędziego - nieadaptacyjnego programu genetycznego. Nieadaptacyjny program genetyczny oblicza użyteczność adaptacyjnego programu genetycznego na podstawie oceny populacji, która wyewoluowała pod nadzorem adaptacyjnego programu genetycznego. Oblicza on użyteczność najlepszego ciągu kodowego w populacji adaptacyjnego programu genetycznego. Taka jest użyteczność przyznana adaptacyjnemu programowi genetycznemu. Gdy każdemu adaptacyjnemu programowi zostalajuż przyznana użyteczność, wtedy nieadaptacyjny program genetyczny kieruje ewolucją populacji adaptacyjnych programów genetycznych.
Jako biolog, Weinberg był prawdopodobnie zaniepokojony potrzebą "nadprzyrodzonej" interwencji w swojej metodzie. Chociaż opisał on procedurę symulacji ze wszystkimi szczegółami, to jednak nie przedstawił wyników symulacji tego modelu w swej rozprawie. Na implementacje algorytmu genetycznego z metapoziomu trzeba było poczekać aż do prac Mercera (1977) i Grefenstette'a (1986).
4.2.5. Hollstien i optymalizacja funkcji
Praca doktorska Hollstiena (1971) była pierwszą rozprawą poświęconą zastosowaniu algorytmów genetycznych w naukach czystych. Tytuł rozprawy, "Artificial Genetic Ada-ptation in Computer Control Systems" (Sztuczna adaptacja genetyczna w komputero-
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych
115
wych systemach sterowania) jest nieco mylący, gdyż sugeruje, że chodzi tu o zastosowanie algorytmów genetycznych do sterowania procesami technologicznymi w jakiejś fabryce. Chociaż Hollstien wspominał o takiej możliwości, przedmiotem pracy była optymalizacji funkcji dwóch zmiennych przy zastosowaniu mechanizmów dominowania, krzyżowania, mutacji oraz przeróżnych metod reprodukcji wzorowanych na tradycyjnych praktykach hodowlanych i ogrodniczych.
Hollstien zbadał pięć różnych metod selekcji:
Na podstawie potomstwa
Osobnicza
Rodzinowa
Wewnątrzrodzinowa
Mieszana
Przystosowanie potomstwa decyduje o użyciu rodziców do dalszej reprodukcji.
Przystosowanie osobnika decyduje o użyciu go do dalszej reprodukcji.
Przystosowanie rodziny decyduje o użyciu jej członków do reprodukcji.
Przystosowanie członków rodziny decyduje o ich użyciu do reprodukcji wewnątrz rodziny. Kombinacja dwóch lub więcej innych metod.
Oprócz tego rozważał on osiem typów preferencji przy kojarzeniu partnerów:
Kojarzenie losowe Kojarzenie krewniacze (endogamia) Kojarzenie wg linii '
Kojarzenie niekrewniacze
(egzogamia)
Samozapłodnienie
Klonowanie
Kojarzenie selektywne
dodatnie
Kojarzenie selektywne
ujemne
Jednakowe prawdopodobieństwo dla wszystkich par. Kojarzenie osobników pokrewnych.
Szczególnie wartościowy osobnik zostaje skojarzony ze wszystkimi członkami populacji podstawowej, ajego potomstwo użyte do dalszej reprodukcji. Kojarzenie osobników o istotnie różnych cechach genotypowych.
Osobnik kojarzy się sam ze sobą. Tworzenie dokładnej repliki osobnika. Kojarzenie podobnych z podobnymi.
Kojarzenie osobników niepodobnych.
Hollstien wykonał symulacje różnych kombinacji tych pięciu strategii selekcji i ośmiu typów preferencji w zastosowaniu do 14 funkcji dwóch zmiennych. We wszystkich eksperymentach używał on 16-bitowych ciągów kodowych, po osiem bitów na każdy z dwóch parametrów. Wartości parametrów były kodowane jako liczby całkowite w dwójkowym zapisie pozycyjnym bądź w kodzie Graya. Tabela czterobitowego kodu Graya podana została w tabl. 4.1; zauważmy, że sąsiednie liczby całkowite różnią się tam tylkojednym bitem (tj. ich odległość Hamminga wynosi 1). Ta własność sąsiadowania jest ogólną cechą kodów Graya. Hollstien rozważał także możliwość użycia kodów mieszających (chodzi o wybórjednej z (2')! możliwych permutacji kodu podstawowego),
116
4. Niektóre zastosowania algorytmów genetycznych
ale nie zademonstrował tego praktycznie. Niezależnie od rodzaju użytego kodu Hollstien odzworowywał otrzymane liczby całkowite w przedział liczb rzeczywistych [0, lOO].
Tablica 4.1. Dwójkowy zapis pozycyjny i kod Graya dla liczb całkowitych 0-15
Liczba
Zapis dwójkowy
Kod Graya
0 0000 0000
1 0001 0001
. . 2 .-�� � ��'-� 0010 001 1
3 0011 ;.. .< 0010 .
4 , " 0100 ..... 0110
' 5" 0101 0111
6 0110 0101
7 0111 ' 0100 .
8 1000 1100
9 1001 1101
10 1010 1111 ,'.. ..
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000
We wszystkich przebiegach algorytmu genetycznego Hollstien używał populacji złożonych z 16 ciągów kodowych. Po przebadaniu różnych kombinacji metod selekcji i kojarzenia, ostatecznie zdecydował się na kojarzenie krewniacze połączone ze sporadycznym przekrzyżowywaniem linii, gdyż metoda ta okazała się najbardziej odporna. Twierdził również, że kody Graya wykazują pewną przewagę nad zapisem pozycyjnym i przypisywał to ich własności sąsiadowania oraz małym zaburzeniom ze strony licznych pojedynczych mutacji. Wyciągając wnioski z przeprowadzonych badań przyznał on, że miał pewne problemy w związku z użyciem małych populacji (n= 16) i zalecał na przyszłość wybór większego rozmiaru populacji.
4.2.6. Frantz i efekt pozycyjny
Frantz (1972) skorzystał z tej rady i użył większych populacji (n=100) oraz dłuższych ciągów kodowych (/=25) w badaniach efektu pozycyjnej nieliniowości (epistazy) w optymalizacji za pomocą algorytmu genetycznego. Skonstruował on kombinacje funkcji liniowych i nieliniowych określonych dla binarnych chromosomów haploidalnych i badał efekty pozycyjne (sprzężenia) dla szeregu takich funkcji, zmieniając porządek genów wewnątrz chromosomów, aby wpłynąć na rozpiętość wybranych grup genów. W początkowej fazie badań zastosował on regułę ruletki, krzyżowanie proste i zwykłą mutację, porównując skutki dobrego i złego uporządkowania ciągów kodowych. Udało mu się wykazać istnienie korelacji między występowaniem krótkodystansowych sprzężeń a tempem poprawy wyników. W jego eksperymentach z dobrymi i złymi uporządkowaniami
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
117
nie dało się jednak zaobserwować istotniejszych różnic w wydajności od chwili ujednolicenia się populacji. Przyczyną tego był fakt, że wybrane przez niego funkcje nie były dostatecznie "trudne", aby móc skutecznie przetestować hipotezę sprzężeń - co było wynikiem zbyt małej długości ciągów i słabej nieliniowości tablicowo określonych funkcji. Rzecz w tym, że to nie hipoteza sprzężeń okazała się fałszywa, ale że funkcje Frantza nie były dostatecznie mocne, aby móc dostarczyć jej potwierdzenie. W świetle obecnej wiedzy na temat zwodniczości nie dziwi, że miał on trudności ze skonstruowaniem AG-trudnych funkcji. Jak wskazano w rozdziale drugim, nie wystarczy do tego występowanie długodystansowych nieliniowości będących łącznym efektem kombinacji funkcji i kodu; muszą oprócz nich występować zwodnicze schematy-cegiełki niskiego rzędu. Zarówno teoria, jak i matematyczne narzędzia niezbędne do konstrukcji takich zadań nie były jeszcze w tym czasie wypracowane.
Frantz kontynuuował badania, włączając dodatkowo inwersję - operację zmieniającą uporządkowanie chromosomu do swego algorytmu genetycznego, w nadziei wytworzenia lepszych, bardziej zwartych bloków. Nie powinno dziwić, że jego eksperymenty z inwersją nie przyniosły rozstrzygnięć ^operacją tą zajmiemy się w następnym rozdziale). Aby wykazać różnicującą przewagę inwersji, trzeba mieć do czynienia z zadaniem o cechach zwodniczej nieliniowości, a jego wcześniejsze próby bez inwersji pokazały, że to nie miało miejsca.
Frantz zastosował także analizę statystyczną w celu wykazania, że pewne kombinacje alleli pojawiały się w procesie przetwarzania znacznie częściej, niż można by oczekiwać w przypadku losowym. Wprowadził również dwie nowe operacje - operację dopetnienia częściowego oraz operację krzyżowania wielopunktowego. Dopełnienie częściowe (które nazywał migracją) polega na zastąpieniu w wybranych osobnikach około jednej trzeciej bitów wartościami przeciwnymi (dopełnieniami). Te osobniki, zwane imigrantami, mogły potem przechodzić do następnego pokolenia. Dopełnienie częściowe miało na celu zachowanie różnorodności populacji. Frantz stwierdził, że operacja ta istotnie zwiększa różnorodność, ale za wysoką cenę zmniejszenia wydajności. Krzyżowanie wielopunktowe w jego wydaniu polegało na wymianie podciągów utworzonych w wyniku losowego (z pewnym zadanym prawdopodobieństwem) wyboru punktów podziału (idąc z prawa na lewo). Mimo że autorstwo pomysłu należy do Frantza, dopiero De Jong w późniejszej pracy (1975) zbadał mocne i słabe punkty tej operacji.
4.2.7. Bosworth, Foo i Zeigler-geny "rzeczywiste"
Wezbrany potok działalności badawczej związanej z algorytmami genetycznymi zdaje się około 1972 r. dzielić na dwa nurty, różniące się wyborem strategii kodowania. Obóz "minimalistów" skłonny jest przyjąć teorię schematów Hollanda i wynikające z niej zalecenie stosowania małych alfabetów. Z kolei obóz alfabetycznych "maksymalistów" wydaje się preferować wzajemnie jednoznaczną odpowiedniość między genami a para-metrami, niezależnie od liczby alleli przypadających najeden gen. Z krańcowym przypadkiem tego ostatniego podejścia spotykamy się w pracy Boswortha, Foo i Zeiglera (1972). (Patrz także: Foo i Bosworth, 1972; Zeigler, Bosworth i Bethke, 1973). We
118
4. Niektóre zastosowania algorytmów genetycznych
wspomnianej pracy operacje noszące nazwy reprodukcji, krzyżowania, mutacji oraz inwersji zostały zastosowane do "ciągów kodowych" złożonych / 4-40 parametrów rzeczywistych. Podobnie jak w poprzednich badaniach z dużymi alfabetami, trudno było zaproponować naturalną postać mutacji i w rezultacie użyto pięć różnych operacji tego typu:
1) mutacja Fletchera-Reevesa (FR);
2) mutacja losowa jednostajna; ;
3) przybliżenie gaussowskie drugiego stopnia;
4) przybliżenie gaussowskie trzeciego stopnia;
5) mutacja zerowa.
Czytelnicy znający tradycyjne procedury optymalizacji rozpoznają w pierwszej z tych "mutacji" całkiem zaawansowany algorytm wspinaczki. W tej tak zwanej operacji mutacji używa się przybliżonej wartości gradientu (trzeba przy tym obliczyć 2r wartości innych funkcji, gdzie rjest liczbą parametrów rzeczywistych) w celu określenia kierunku wspinaczki, aby następnie zastosować metodę złotego podziału (dokonując dalszych wartościowań funkcji).
Daleko odbiegliśmy tu od zwykłej mutacji objaśnionej w pierwszych trzech rozdziałach książki. Co istotniejsze, trudno byłoby się tu oprzeć najakimkolwiek rozsądnym precedensie biologicznym. Gdyby taka operacja istniała w przyrodzie, skąd brałyby się te wszystkie dodatkowe wartościowania funkcji? Co więcej, gdyby nawet istotnie przyroda stosowała taką metodę poszukiwania, to jaką moglibyśmy mieć pewność, że wartości pochodnych zachowają jakiś sens w ziarnistych, nieciągłych środowiskach poszukiwań, z którymi sami mamy do czynienia? Nie chodzi tu o to, aby kwestionować użyteczność tego typu technik. Zastosowanie reprodukcji, równoległych poszukiwań w populacji i złożonych procedur lokalnego poszukiwania może stanowić mocne narzędzie optymalizacji dla ograniczonej klasy; jednak w ogólnym przypadku posługiwanie się dużymi alfabetami do tego stopnia redukuje ukrytą równoległość, że nie jest już rzeczą właściwą nazywać taką metodę algorytmem genetycznym w sensie, wjakim rozumiał to Holland.
4.2.8. Box i planowanie ewolucyjne
Nie pierwszy to raz różne techniki otrzymywały miano "genetycznych" lub "ewolucyjnych", chociaż ich rzeczywiste podobieństwo do naturalnych mechanizmów genetycznych było minimalne. Jedną z pierwszych tego typu propozycji była metodaplanowania ewolucyjnego [evolutionary operation\ Boxa (ł957). Był to nie tyle algorytm, co metoda zarządzania mająca umożliwić pracownikom przemysłowym o mniej technicznym nastawieniu realizację systematycznego planu eksperymentów decyzyjnych. Chodziło tu o wykorzystanie eksperymentów w celu poprawy pewnych parametrów procesu technologicznego. W celu zilustrowania metody Box przedstawił przykład procesu zależnego od trzech zmiennych: nawęglenia, wdmuchu powietrza i szybkości wzrostu temperatury. Wychodząc z bieżącego "punktu operacyjnego" tworzono hiperkostkę wariantów (rys. 4.7) i przyjmowano systematyczny harmonogram "wizyt" w poszczególnych
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
119
(a) Cykl operacyjny
(b) Średnie wyniki po 5 cyklach
Mawęglenie
Rys. 4.7. Hiperkostka wariantów w metodzie planowania ewolucyjnego Boxa (Box, 1957). Przedruk za zezwoleniem z Journal of the Royal Statistical Society, C.
wierzchołkach hiperkostki. Jeśli wizyta w jednym z sąsiednich wierzchołków przynosiła znaczącą poprawę, komitet planowania ewolucyjnego podejmował decyzję o zmianie punktu operacyjnego, tworzono nową hiperkostkę i eksperymentowanie biegło dalej. Chociaż pomysł wydaje się dość rozsądny, a późniejsze, bardziej automatyczne metody sympleksowe zdały egzamin w zagadnieniach lokalnego poszukiwania (Nelder i Mead, 1965; Spendley, Hext i Himsworth, 1962), czy można uznać tę metodę za w jakimś sensie ewolucyjną? Box (str. 83) ujmuje to w ten sposób: >
Istoty żywe rozwijają się na skutek działania dwóch mechanizmów: 0
(i) Zmienności genetycznej będącej skutkiem różnych czynników, takich jak mutacja, (ii) Doboru naturalnego.
Procesy chemiczne rozwijają się w podobny sposób. Odkrycie nowej ścieżki technologicznej odpowiada mutacji. Dostrojenie parametrów procesu do optymalnych wartości dla uprzednio wybranej ścieżki jest związane z procesem naturalnego doboru, w którym mało obiecujące kombinacje wartości parametrów procesu są odrzucane na rzecz bardziej obiecujących. - -.;.;.-
Możemy się spierać, czy istotnie zachodzi tu analogia z procesem doboru naturalnego, gdyż według tej definicji prawie wszystko, co zmienia w jakiś sposób istniejącą strukturę, kwalifikuje się jako mutacja. Jest to stanowczo zbyt pojemna definicja, i musimy bardzo uważać, czy zachowane są tu istotne elementy analogii. Sposób użycia przez Boxa hiperkostki ma charakter o tyle "biologiczny", że proces poszukiwania wychodzi z pewnej populacji punktów (chociaż przyroda nie ogranicza się do poszukiwań w lokalnym otoczeniu danej jednostki, a populacje biologiczne rzadko kiedy bywają tak uporządkowane czy regularne), jednak brak ustalonego sposobu kodowania wyklucza przetwarzanie schematów, które leży u podłoża genetycznych procesów poszukiwania;
120
4. Niektóre zastosowania algorytmów genetycznych
brak rekombinacji przekreśla natomiast innowacyjną wymianę informacji między strukturami, co uznaliśmy za tak pożyteczne we wcześniejszych rozdziałach. Musimy zatem uznać, że metoda ewolucyjnego planowania, choć wartościowa i będąca prekursorem innych lokalnych technik poszukiwania, nie stanowi algorytmu genetycznego w nowoczesnym znaczeniu.
4.2.9. Inne ewolucyjne techniki optymalizacji
Po propozycji Boxa pojawiło się kilka nowych technik optymalizacji inspirowanych ewolucją (Bledsoe, 1961; Bremermann, 1962; Friedman, 1959). Prace Bledsoe'a i Bre-mermanna są najbliższe nowoczesnemu pojmowaniu algorytmu genetycznego. Obydwaj wypowiedzieli się za użyciem kodu dwójkowego. Bledsoe przedstawił metodę łączącą sukcesywne tworzenie pojedynczych osobników, mutowanie i selekcję przez zachowanie najlepszego osobnika. Zaproponował również (ale bez przedstawienia wyników) metodę opartą na populacjach. Bremermann rozszerzył pracę Bledsoe'a o generowanie kolejnych populacji ciągów kodowych z zastosowaniem selekcji i mutacji. Zaproponował także wprowadzenie rekombinacji, ale nie przedstawił wyników eksperymentalnych, żadna z tych wczesnych prac nie miała podstaw teoretycznych analogicznych do twierdzenia o schematach.
Na Politechnice Berlińskiej (Rechenberg, 1965; Schwefel, 1981) niezależnie opracowano techniki pod nazwą Evolutionstrategie (strategia ewolucyjna). Pierwotne eksperymenty Rechenberga dotyczyły określenia profilu płatów lotniczych, przy użyciu urządzenia fizycznego do wytwarzania lokalnych zaburzeń geometrii płata. Później zaczęto dokonywać symulacji komputerowych podobnych procesów. Użycie parametrów rzeczywistych ogranicza zakres przetwarzania schematów, będącego nieodłączną cechą tych metod. Tym niemniej strategie ewolucyjne znalazły gorących zwolenników w pewnych kręgach naukowych i inżynierskich, szczególnie na terenie Niemiec (Rechenberg, 1986).
4.2.10. Fogel, Owens i Walsh - Programowanie ewolucyjne
Po planowaniu ewolucyjnym i ewolucyjnych technikach optymalizacji pojawiły się techniki programowania ewolucyjnego (Fogel, Owens i Walsh, 1966). Odrzucenie tej pracy przez środowisko naukowe zajmujące się sztuczną inteligencją bardziej niż cokolwiek innego wpłynęło na upowszechnienie się w końcu lat sześćdziesiątych i w pierwszej połowie siedemdziesiątych sceptycyzmu wobec algorytmów genetycznych bliskich idei schematów.
Omawiana praca dotyczyła zadania poszukiwania w przestrzeni automatów skończonych o niewielkiej liczbie stanów. Aby lepiej zrozumieć naturę tej przestrzeni, rozważmy diagram przejść trzystanowego automatu, pokazany na rys. 4.8. Literami greckimi oznaczono symbole wyjściowe, cyframi 0 i 1 - symbole wejściowe, a literami łacińskimi - stany automatu. Na przykład, jeżeli automat z rys. 4.8 znajduje się w stanie A i otrzyma na wejściu 1, to wypisze na wyjściu f5 i pozostanie w stanie A. Jeśli nato-
4.2. Przegląd historyczny ważniejszych zastosowań algorytmów genetycznych .
121
O/y
Rys. 4.8. Diagram przejść automatu skończonego trenowanego metodąprogramowania ewolucyjnego (Fogel, Owens i Walsh, 1966). Adaptacja za zezwoleniem wydawcy z Artificial Intelligence Through SimulatedEvolution, L.J. Fogel, A.J. Owens, *M.J. Walsh, copyright � 1966 John Wiley & Sons, Inc.
miast automat jest w stanie A i otrzyma 0 na wejściu, to wypisze f5 i przejdzie do stanu B. Pelny opis przejść i wyjść automatu podano w tabl. 4.2.
Tablica 4.2. Tablica przejść automatu skończonego (Fogel, Owens i Walsh, 1967)
Stan bieżący
Symbol na wejściu
Stan następny
Symbol na wyjściu
C 0 B P
B 1 C a
C 1 A Y
A 1 A P
A � .. ''i:;'.: ' 0 B P
B 1 C a
Adaptacja za zezwoleniem wydawcy na podstawie: L.J. Fogel, A.J. Owens, M.J. Walsh, Artificial Intelligence Through Simutated Evolution. Copyright � 1966 John Wiley & Sons, Inc.
Takie automaty były uczone przewidywania powtarzających się cykli symboli wyjściowych metodą programowania ewolucyjnego. Metoda ta polegała głównie na selekcji i mutacji. W najprostszej postaci operacja selekcji wybierałajeden z dwóch automatów: automat rodzicielski lub zmutowany automat potomny. W pracy rozważano także populacje o rozmiarze większym niż n = 2; niezależnie jednak od liczby zapamiętanych automatów rodzicielskich, jedynym mechanizmem modyfikacji strukturalnej były mutacje.
Dla Fogela, Owensa i Walsha mutacja polegała na pojedynczej modyfikacji diagramu stanów automatu w następującym sensie (str. 14-15): � ;.\;V:,, r ;;
Następnie tworzy sie potomka tego automatu w wyniku mutacji, tj. w wyniku pojedynczej modyfikacji automatu rodzicielskiego zgodnie z pewnym rozkładem szumu mutacyjnego.
122
4. Niektóre zastosowania algorytmów genetycznych
Tryb mutacji zależy od przedziału, do którego należy liczba wybrana z tablicy liczb losowych. Przedziały te zostały wybrane zgodnie z rozkładem prawdopodobieństwa określonym sv dla dozwolonych trybów mutacji. Następnie wybiera sie dodatkowe liczby w celu określenia szczegółów charakterystycznych dla danej mutacji. W ten sposób zostaje utworzony automat potomny, który różni sie od swojego przodka albo symbolem wyjściowym, albo przejściem międzystanowym, albo stanem początkowym.
Programowanie ewolucyjne Fogela, Owensa i Walsha, oparte na losowych modyfikacjach diagramu stanów automatu skończonego i wyborze najlepszego osobnika, okazało się narzędziem nie dość silnym na to, by dostarczać szybkich rozwiązań - prócz przypadku małych przestrzeni problemowych. Teraz odłożymy na bok te i podobne prace badawcze, w których nie zwrócono uwagi na zasadnicze znaczenie strukturalnej rekombinacji i zajmiemy się przełomowym studium algorytmów genetycznych, łączącym w sobie solidną analizę teoretyczną ze starannie zaplanowanymi eksperymentami obliczeniowymi.
4.3. De Jong i optymalizacja funkcji
Rok 1975 był szczególnie udany dla algorytmów genetycznych. Hołland opublikował znane dzieło Adaptation in Natural andArtificial Systems i w tym samym roku De Jong ukończył swą ważną i stanowiącą punkt zwrotny badań rozprawę doktorską pt. "An Analysis of the Behavior of a Class of Genetic Adaptive Systems" (Analiza zachowania pewnej klasy genetycznych systemów adaptacyjnych). Studium De Jonga do tej pory stanowi kamień milowy w rozwoju algorytmów genetycznych, a to dzięki połączeniu teorii schematów Hollanda z jego własnymi, starannie zaplanowanymi eksperymentami. Ze względu na wpływ tej pracy na późniejszy kierunek rozwoju algorytmów genetycznych oraz na dobrze przemyślare wnioski, poświęcimy jej tu więcej miejsca niż poprzedniczkom.
Podobniejak Hollstien (1971) De Jong zajął się algorytmami genetycznymi w kontekście optymalizacji funkcji, chociaż był całkowicie świadom potencjału, jaki przedstawiają one w innych dziedzinach; był on szczególnie zainteresowany zastosowaniem algorytmów genetycznych do projektowania struktur danych, algorytmów oraz adaptacyjnych systemów operacyjnych dla komputerów. Mimo że pociągały go te bardziej ezoteryczne tematy, De Jong zdał sobie sprawę z tego, jak ważną rzeczą jest przeprowadzenie starannie zaprojektowanych eksperymentów w przyzwoitej dziedzinie problemowej. Rozłożył zatem algorytm genetyczny, środowisko i kryteria oceny na czynniki pierwsze. Właśnie uproszczenia, które wprowadził, umożliwiły mu przeprowadzenie fundamentalnych eksperymentów, wyznaczających standardy dla wszystkich późniejszych studiów i zastosowań algorytmów genetycznych.
De Jong zaprojektował "środowisko pomiarowe" składające się z pięciu zadań z zakresu minimalizacji funkcji. Wziął on pod uwagę funkcje o następujących charakterystykach:
ciągłe/nieciągłe;
wypukłe/niewypukłe;
4.3. De Jong i optymalizacja funkcji
123
jednomodalne/wielomodalne; kwadratowe/niekwadratowe; niskiegowymiaru/wysokiegowymiaru; deterministyczne/stochastyczne.
Funkcje i ich dziedziny zostały przedstawione w tabl. 4.3. Odwrócone wykresy funkcji dla przypadku dwóch zmiennych są pokazane na rys. 4.9-4.11.
Tablica 4.3. Pięć funkcji testowych De Jonga
Nr funkcji
Funkcja
Zakresy
3
i /-w = i*2 -5,12 <*,. < 5,12
i '
2 /,(*) = 100(*2-^)2 + (!-*,)2 -2,048 <*, < 2,048
5
3 /3(*) = IŁ*,- J -5,12 <*,. < 5,12
!
30
4 /4(*) = 1/** + GoMw(0,l) -1,28 <*,. < 1,28
i
v 1
5 " 1 //s (*) = 0,002 + L 2 -65,536 <*, < 65,536
J"' y + I(*,.-o,/
" Macierz współczynników (afj) jest przy tym zdefiniowana następująco:
1)
-32 -16 0 16 32 -32 ... -32 -16 0 16 32\ -32 -32 -32 -32 -32 -16 ... 32 32 32 32 32j
(prz.yp. ttum.).
Rys. 4.9. DwuwymiarowewersjefunkcjitestowychF1 iF2DeJonga(wykresyodwrocone).Przedrukza zezwoleniem
124
4. Niektóre zastosowania algorytmów genetycznych
Rys. 4.10. Dwuwymiarowe wersje funkcji testowych F3 i F4 De Jonga (wykresy odwrócone). Przedruk za zezwoleniem
Aby móc scharakteryzować ilościowo efektywność różnych algorytmów genetycznych, De Jong zaproponował dwa mierniki, jeden do oceny poziomu zbieżności i drugi do oceny efektywności bieżącej. Używał on przy tym terminów off-line per-formance (dla poziomu zbieżności) i on-line performance (dla efektywności bieżącej). Nazwy on-line i off-line nawiązują do różnicy między zastosowaniami typu off-line (wsadowego) oraz on-line (interakcyjnego). W pierwszym przypadku możemy dokonywać wielu symulacji i zapamiętywać najlepszy wynik otrzymany po spełnieniu pewnego warunku stopu. W drugim nie możemy pozwolić sobie na taki luksus, gdyż wszystkie wyniki otrzymuje się na bieżąco; wobec tego premia należy się za szybkie dojście do akceptowalnego wyniku. Jakjuż kiedyś wspominaliśmy, spotykany zazwyczaj nacisk na osiągnięcie zbieżności stanowi główny niedostatek we współczesnym podejściu do procedur poszukiwania.
De Jong następująco zdefiniował efektywność on-line xe(s) strategii s dla środowiska e\
4.3. De Jong i optymalizacja funkcji
125
F5
Rys. 4.11. Funkcja testowa F5 De Jonga (wykres odwrócony). Przedruk za zezwoleniem
gdzie/e(?) jest wartością funkcji celu dla środowiska e w próbie t. Słowami: efektywność on-line jest to średnia wartość funkcji celu ze wszystkich prób włącznie z bieżącą. W rzeczywistości De Jong podał nieco ogólniejszą postać tego kryterium, dopuszczając przypadek niejednakowych wag w poszczególnych próbach, jednak w badaniach trzymał się wersji z jednakowymi wagami.
Efektywność off-line x*e(s) strategii s dla środowiska e De Jong zdefiniował następująco: \ ;
1 L '� :
XI(S) = Lfe(t} * 1
gdziefl(t) = opt{fe(\),fe(2), ...,fe(t)}. Słowami: efektywność off-line)e,st to średnia najlepszych aktualnych (tzn. do danej próby włącznie) wartości funkcji celu ze wszystkich prób. Także i w tym przypadku zaproponowano ogólną definicję (z niejednakowymi wagami), ale badania ograniczyły się do jednakowych wag.
Przygotowawszy zestaw pięciu funkcji testowych i określiwszy kryteria porównawcze, De Jong przystąpił do rozważenia wariantów tego, co nazwaliśmy tu elementarnym algorytmem genetycznym. Rozpoczął od wersji, którą nazwał Rl (plan reprodukcyjny 1), obejmującej trzy operacje omówione w rozdziale trzecim:
1) selekcja wg reguły ruletki;
2) krzyżowanieproste(zkojarzeniemlosowym); .*,,,>-.
3) mutacja prosta.
126
4. Niektóre zastosowania algorytmów genetycznych
Wszystkie operacje są tu wykonywane na kolejnych populacjach dwójkowych ciągów kodowych (kod blokowy ze standaryzacją parametrów, dwójkowy zapis pozycyjny w blokach).
De Jong zdał sobie sprawe, że plan #1 jest właściwie rodziną planów zależnych od czterech parametrów:
n wielkość populacji;
pf-prawdopodobieństwokrzyżowania; ;
pm- prawdopodobieństwo mutacji; G współczynnik wymiany [generation gap].
Pierwsze trzy parametry sąjuż nam dobrze znane. Współczynnik wymiany G został wprowadzony przez De Jonga, by umożliwić mieszanie pokoleń. Może on przybierać wartości z przedziału [0, 1], przy czym dla C=1 mamy do czynienia z populacjami rozłącznymi, a dla 0W populacjach mieszanych operacje genetyczne wykonuje się na n � G osobnikach. Otrzymane stąd potomstwo rozmieszcza się w istniejącej populacji na n � G wybranych losowo (bez powtórzeń) miejscach.
Początkowo De Jong zajął się funkcją F\ - gładką funkcją kwadratową trzech zmiennych - zmieniając najpierw indywidualnie poszczególne parametry, a potem roz-
800U,0 UOW,0 KX*,0 8CKK,0
Liczba prób
iRys. 4.12. Wpływwielkościpopulacjinautratęallelidlaplanuftl ifunkcjiFI (DeJong,1975).Przedruk za zezwoleniem
2000,0 U000,0 6000,0 8000,0 10000,0
Liczba prób
Rys. 4.13. Wpływ wielkości populacji na efektywność off-l/ned\a planu fl1 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem
S000,0 10000,0 lSOOO,0 20000,0 25000,0
Liczba prób
Rys. 4.14. Wpływwielkościpopulacjinaefektywnośćon-//nedlaplanufl1 ifunkcjiF1 (DeJong,1975). Przedruk za zezwoleniem
128
4. Niektóre zastosowania algorytmów genetycznych
patrując ograniczoną liczbę kombinacji. Następnie przeprowadził ograniczone badania parametryczne dla wszystkich pięciu funkcji.
Na rysunkach 4.12-4.14 przedstawiono wyniki eksperymentów z wielkością populacji dla funkcji F1. Jak można było przypuszczać, większe populacje prowadzą do większej końcowej efektywności off-line dzięki dysponowaniu większą pulą różnorodnych schematów. Bezwładność dużej populacji pozwala z kolei oczekiwać gorszej efektywności on-line na początku (por. rys. 4.14). Z drugiej strony niewielkie populacje mogą ulegać znacznie szybszym zmianom i dzięki temu wykazują lepszą inicjalną efektywność on-line.
Często sugerowano, że w celu zapobieżenia przedwczesnej utracie alleli i utrzymania dostatecznej różnorodności populacji należy zwiększać tempo mutacji. Badania De Jongajasno wykazały, że nie jest to panaceum, co wynika niezbicie z rys. 4.15-4.17. W rozważanych przebiegach (przy n = 50, pc=l,0, G=l,0) intensywniejsze mutacje zmniejszyły wprawdzie liczbę utraconych alleli, ale stało się to kosztem pogorszenia obu wskaźników efektywności. Gdy tempo mutacji zaczyna dochodzić do poziomu pm = 0,l, plan R\ przypomina coraz bardziej poszukiwanie losowe pod względem efektywności off-line. (Oczywiście, przypm=0,5 mamy do czynienia z poszukiwaniem losowym niezależnie od wartości pc i n.) Co więcej, zwiększenie prawdopodobieństwa mutacji zmniejsza również efektywność on-line.
De Jong eksperymentował także z prawdopodobieństwem krzyżowania i współczynnikiem wymiany. W wyniku tych badań zalecił on dobór prawdopodobieństwa krzy-
=58
o
ż8
|-
3
o 8
0,0 200,0 400,0 600,0 800,0
Liczba prób (X10^1)
1000,0
Rys. 4.15. Wptyw tempa mutacji na utratę alleli dla planu fl1 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem
s.
Poszukiwanie losowe
Pm - 0,01 Pm - 0,001
'0,0 U00,0 800,0 1200,0 1600,0 2000,0
Liczbaprób (X10^1)
Rys. 4.16. Wpływ tempa mutacji na efektywność off-line dla planu f?1 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem
8
t
Poszukiwanie losowe
Pm- 0>005 Pm - 0,001
0,0 500,0 1000,0 1500,0 2000,0 2500,0
Liczba prób (X10"1)
Rys. 4.17. Wpływ tempa mutacji na efektywność on-//nedla planu fl1 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem
130
4. Niektóre zastosowania algorytmów genetycznych
żowania na poziomie p<: = 0,6 jako rozsądny kompromis w celu osiągnięcia dobrej efektywności on-line i off-line. Późniejsze studia (Mercer, 1977; Grefenstette, 1986) sugerowały, że w przypadku zastosowania metod selekcji o mniejszym rozrzucie losowym lepiej jest przyjąć wyższe prawdopodobieństwo krzyżowania (pc= 1,0). Eksperymenty ze współczynnikiem wymiany wykazały, że model rozłącznych populacji był najwłaściwszy dla większości zadań optymalizacji, w których liczyła się efektywność off-line\ tym niemniej efektywność on-line nie ulegała dramatycznemu pogorszeniu dla mniejszych wartości współczynnika.
W celu ulepszenia podstawowej wersji algorytmu genetycznego De Jong przebadał pięć następujących wariantów planu R\\
R2 modelelitarystyczny
^3 model wartości oczekiwanej
#4 elitarystyczny model wartości oczekiwanej
R5 model ze ściskiem [crowding model] ",
R6 model uogólnionego krzyżowania
W modelu elitarystycznym szczególną wagę przywiązywało się do zachowania najlepszego dotychczasowego osobnika (De Jong, 1975, str. 102):
Niech a*(f) będzie najlepszym osobnikiem wygenerowanym do chwili t. Jeżeli po utworzeniu A(f+ 1) w zwykły sposób, a*(t) nie należy do A(t+ 1), to włącz a*(t) to A(f+ 1) jako element (N+ 1).
W eksperymentach z R2 De Jong stwierdził, że plan elitarystyczny w znaczący sposób zwiększa zarówno efektywność on-line, jak i off-line dla funkcji jednomodalnych; jednak w przypadku wielomodalnej funkcji F5 oba te wskaźniki spadły. Zdaniem De .Tonga, może to oznaczać, że elitaryzm poprawia efektywność lokalnego poszukiwania kosztem perspektywy globalnej.
Chcąc zredukować rozrzut losowy przy selekcji wg reguły ruletki, De Jong opracował model wartości oczekiwanej R3. Jak pamiętamy, naszym pragnieniem jest, aby schematy rozprzestrzeniały się w populacji zgodnie z wykładniczym prawem wzrostu. W przypadku planu ^1 dokonujemy tego, dobierając prawdopodobieństwa wyboru w sposób proporcjonalny do wskaźników przystosowania, a następnie wylosowując n osobników według tego rozkładu prawdopodobieństwa. Ta procedura, stwierdza De Jong, wprowadza dwa źródła odchyleń. Po pierwsze, ponieważ nie możemy praktycznie obliczyć rzeczywistych wskaźników przystosowania schematow'\jestesmy zmuszeni estymować je drogą losowania sekwencyjnego. Po drugie, sama selekcja (wg reguły ruletki) jest procesem charakteryzującym się dużą wariancją, a więc dającym spory rozrzut faktycznej liczby kopii wokół wartości oczekiwanej. W modelu #3 De Jong spróbował zmniejszyć wielkość odchyleń tego drugiego rodzaju. W tym celu obliczał oczeki-
" Chodzi tu o średnią ze wskaźników przystosowania wszystkich możliwych reprezentantów danego schematu (lj. "statyczną", por. dodatek D) (przyp. tlum.).
4.3. De Jong i optymalizacja funkcji
131
waną liczbę kopii///dla każdego ciągu kodowego / (przy założeniu, że w każdym pokoleniu reprodukcji podlega cała populacja). Następnie, za każdym razem, gdy pewien ciąg został wylosowany do kojarzenia i krzyzowania,jego "kredyt" ulegał zmniejszeniu o 0,5 (w modelu De Jonga - inaczej niż przyjęliśmy w rozdziale trzecim - zachowywano tylko jednego potomka uzyskanego z krzyżowania). Jeśli natomiast dany ciąg kodowy podlegał samej replikacji, bez krzyżowania, jego kredyt zostawał zmniejszony o 1,0. W obu przypadkach osobnik, którego kredyt spadł poniżej zera, nie mógł już dalej brać udziału w procesie reprodukcji. Dzięki temu mechanizmowi, faktyczna liczba potomków musiała być zawsze mniejsza odfi/f+ 1, a na ogół nie przekraczała.^/7+0,5. Na rysunku 4.18 porównano plan R3 z planami R2 i R] dla funkcji F1 pod względem utraty alleli. Dla planu R3 obserwuje się znacznie mniejszy stopień utraty, niż w przypadku planu podstawowego i elitarystycznego. Na rysunkach 4.19 i 4.20 porównano te same plany odpowiednio pod względem efektywności on-line i off-line. Plan ^3 wykazuje w obu przypadkach wyraźną przewagę nad planem podstawowym R\. Wreszcie, chociaż plan elitarystyczny fi2jest pod tym względem nieco lepszy niż R3 dlajednomodalnej funkcji niewielu zmiennych F1, plan ^3 przewyższa oba pozostałe, jeśli wziąć pod uwagę cały zestaw funkcji Fl-F5. Na podstawie dodatkowych, ograniczonych eksperymentów z prawdopodobieństwem krzyżowania pc, De Jong stwierdził, że przy swoim ograniczonym rozrzucie losowym plan R3 mógłby "wytrzymać" zwiększoną intensywność krzyżowania. Późniejsze badania z użyciem innych procedur losowania redukujących fluktuacje losowe (Booker, 1982; Brindle, 1981; Grefenstette, 1986) potwierdziły tę obserwację.
=i
o
>>
C o O �
R2(50, 0,001, 0,6, 1,0)
R3(50, 0,001, 0,6, 1,0)
0 1500,0 3000,0 USOO,0 6000,0 7SOO,0
Liczba prób Rys. 4.18. Stratyallelidlaplanowfl1, fl2 i fl3 ifunkcji F1 (DeJong, 1975). Przedrukzazezwoleniem

0,001, 0,6, 1,0)
0,6, 1,0) 0,6, 1,0)
0,0 1500,0 3000,0 MSOO,0 6000,0 7500,0
Liczba prób
Rys. 4.19. Efektywność off-line dla planów R\, R2 \ R3 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem
8
CV T-
PS
8
Rl(50, 0,001, 0,6, 1,0) R3(50, 0,001, 0,6, 1,0) R2(50, 0,001, 0,6, 1,0)
6000,0 7SOO,0
T),0 lSOO,0 3000,0 U500,0
Liczba prób
Rys. 4.20. Efektywność on-line dla planów fl1, fl2 i fl3 i funkcji F1 (De Jong, 1975). Przedruk za zezwoleniem �� ; ;^'
L
4.3. De Jong i optymalizacja funkcji
133
W planie #4 De Jong połączył cechy planów R2 i R3>, tworząc elitarystyczny model wartości oczekiwanej. Wyniki, które otrzymał, były zgodne z oczekiwaniami: dla funkcji jednomodalnych (Fl-F4) obserwowano istotną poprawę, podczas gdy w przypadku trudnej, pełnej "lisichjam" funkcji F5 efektywność, w porównaniu z planem opartym tylko na modelu wartości oczekiwanej, spadła. Niemniej z uwagi na wzrost efektywności dla pierwszych czterech funkcji, ogólny wskaźnik odporności podniósł się.
De Jonga niepokoił spadek efektywności dla funkcji wielomodalnej F5, w związku z czym podjął on kroki w celu zaradzenia tej sytuacji, kierując się przy tym pewnymi analogiami przyrodniczymi. Powstał w ten sposób plan reprodukcyjny R5. Idąc śladem Hollanda (1975), De Jong rozumował, że wypełnienie niszy ekologicznej przez podobne osobniki powoduje wzrost konkurencji o dostęp do ograniczonych zasobów, co w konsekwencji przyczynia się do spadku średniej długości życia oraz wskaźników rozrodczości. Mniej zatłoczone nisze odczuwają mniejszą presję i osiągają wskaźniki przeżywalno-ści i rozrodczości znacznie bliższe pełnemu potencjałowi. Aby wymusić podobną presję podczas działania sztucznego algorytmu genetycznego, De Jong postanowił zastępować nowo utworzonym potomstwem podobne do niego, starsze osobniki, w nadziei, że przyczyni się to do utrzymania większej różnorodności w populacji.
W tym celu De Jong zastosował model z populacją mieszaną, ustalając współczynnik wymiany na poziomie G = 0,1. Wprowadził prócz tego nowy parametr, który nazwał czynnikiem ścisku [crowdingfactor] (CF}. Według nowego planu ^5, zwanego modelem
ta
MN=bO
1500,0 3000.0 �500,0 6000,0
Liczba prób
7500,0
Rys. 4.21. Wptyw czynnika ścisku na efektywność off-lined\a planu R5 '\ funkcji F5 (De Jong, 1975). Przedruk za zezwoleniem
134
4. Niektóre zastosowania algorytmów genetycznych
ze ściskiem, za każdym razem, gdy powstawał nowy osobnik, wybierano innego do usunięcia. Osobnik przeznaczony do usunięcia był wybierany spośród podzbioru CF osobników wylosowanych z całej populacji. Kryterium tego wyboru było maksymalne podobieństwo do nowo powstałego osobnika (w sensie minimalnej liczby różnic na poszczególnych pozycjach ciągu). Procedura ta nie odbiega wiele od mechanizmu prese-lekcji Cavicchia (1970), o którym wspominaliśmy wcześniej.
Z rysunku 4.21 widać, że dla przypadku funkcji F5 czynnik ścisku CF=2 zapewnił prawie optymalną efektywność w przedziale obserwacyjnym. Koncepcje ścisku (stłoczenia) oraz nisz ekologicznych zostały wykorzystane przez innych badaczy (Goldberg i Richardson, 1987; Perry, 1984) w dalszych studiach. Są one istotne w zadaniach optymalizacji funkcji wielomodalnych oraz w problematyce maszyn uczących się, poświęcimy więc im więcej uwagi w następnych rozdziałach.
Ostatni z rozważanych przez De Jonga modeli to model uogólnionego krzyżowania R6. Wprowadzono w nim dodatkowy parametr CP, określający liczbę punktów krzyżowania. Dla CP=\ krzyżowanie uogólnione sprowadza się do krzyżowania prostego. Przy parzystych wartościach parametru CP ciąg kodowy traktuje się jak pierścień bez początku i końca, a CP punktów podziału wybiera się z jednakowym prawdopodobieństwem wzdłuż okręgu. Sposób wymiany podciągów między dwoma ciągami kodowymi (narysowanymi teraz w postaci pierścieni) dla CP=4 został zilustrowany na rys. 4.22. W przypadku nieparzystych wartości CP zakłada się, że dodatkowy punkt krzyżowania wypada zawsze na pozycji 0 (tj. na początku ciągu), jak zilustrowano na rys.4.23 dla CP = 3.
De Jong nie był pierwszym, który rozważał bardziej złożone warianty operacji krzyżowania. Już wcześniej Cavicchio (1970) wprowadził krzyżowanie dwupunktowe, a Frantz (1972) zdefiniował uogólnioną, jednoparametrową operację krzyżowania
Wybierz losowo cztery punkty krzyżowania
W wyniku krzyżowania czteropunktowego powstają dwa nowe pierścienie
Rys. 4.22. Krzyżowanie wielopunktowe przy parzystej liczbie punktów krzyżowania (CP = 4)
4.3. De Jong i optymalizacja funkcji
135
Wybierz losowo trzy punkty krzyżowania
W wyniku krzyżowania trzypunktowego powstają 2 nowe ciągi
Rys. 4.23. Krzyżowanie wielopunktowe przy nieparzystej liczbie punktów krzyżowania (CP = 3)
w związku z badaniami pozycyjnej nieliniowości. W badaniach De Jonga krzyżowanie wielopunktowe powodowało obniżenie obu wskaźników efektywności, tym większe im więcej punktów krzyżowania wchodziło w grę. De Jong objaśniał to zjawisko, obliczając prawdopodobieństwa przeżycia schematów rzędu 2. Bardziej intuicyjne wyjaśnienie można znaleźć, rozważając liczbę różnych operacji danego typu. W przypadku krzyżowania prostego mamy właściwie do czynienia nie zjedną operacją, ale ze zbiorem /- 1 operacji (gdzie / jest długością ciągu). Wybierając punkt krzyżowania, dokonujemy losowego wyboru jednej z tych /- 1 operacji. Przy krzyżowaniu dwupunktowym (CP = 2) liczba
sposobów wyboru dwóch punktów krzyżowania wynosi . W ogólnym przypadku mamy I operacji krzyżowania wielopunktowego z parametrem CP. W konsekwencji,
\ \*rLt
gdy CP wzrasta, prawdopodobieństwo wyboru każdej określonej operacji podczas danego krzyżowania maleje, przez co struktura ciągów w większym stopniu narażona jest na naruszenie. Złożone operacje krzyżowania upodabniają się więc do mieszania losowego i mniej znaczących schematów może się w ten sposób zachować. Tę degradację zaobserwował De Jong w swoich badaniach.
De Jong porównał też pod względem efektywności pewne algorytmy poszukiwania lokalnego z planem ^4, m.in. algorytm PRAXIS (Brent 1973) oraz DFP, będący ulepszoną wersję algorytmu Fletchera i Powella (Fletcher i Powell, 1963). W łącznej ocenie plan R4 wypadł lepiej zarówno od DFP, jak i PRAXIS, przy czym szczególnie głębokie różnice uwidoczniły się w przypadku wielomodalnej funkcji F5. Jak można było oczekiwać, algorytmy DFP i PRAXIS zachowywały się dobrze dla funkcji gładkich,
I
136
4. Niektóre zastosowania algorytmów genetycznych
jednomodalnych; natomiast nie wypadały dobrze w pozostałych przypadkach. Oczywiście, jeśli interesują nas gładkie funkcje jednomodalne, to nie ma sensu zaczynać od algorytmów genetycznych; jeżeli jednak zależy nam na efektywności w szerokim przekroju funkcji, to wówczas pójście drogą algorytmów genetycznych przedstawia się obiecująco.
4.4. Udoskonalenia techniczne
Prace De Jonga postawiły algorytmy genetyczne i ich zastosowania na solidniejszych podstawach. Od tego czasu wielu badaczy proponowało i poddawało testom rozmaite udoskonalenia podstawowego algorytmu. W tym punkcie omówimy udoskonalenia na polu selekcji, skalowania i metod rankingowych. W rodziale piątym zajmiemy się bardziej zaawansowanymi mechanizmami, takimi jak inwersja, dominowanie, bariery reprodukcyjne oraz nisze.
4.4.1. Alternatywne metody selekcji
Po sukcesie De Jonga z modelem wartości oczekiwanej różni badacze zajęli się poszukiwaniem alternatywnych metod selekcji, próbując zredukować fluktuacje losowe związane z regułą ruletki. Brindle zbadała w swej rozprawie doktorskiej (1981) sześć następujących metod:
1) wybórdeterministyczny;
2) wybór losowy wg reszt bez powtórzeń;
3) wybór losowy bez powtórzeń;
4) wybór losowy wg reszt z powtórzeniami;
5) wybór losowy z powtórzeniami;
6) turnieje losowe (metoda rang Wetzela).
Wybór losowy z powtórzeniami to wyszukana nazwa dobrze nam znanej reguły ruletki; natomiast wybór losowy bez powtórzeń to inna nazwa modelu wartości oczekiwanej R3 De Jonga. Wybór deterministyczny odbywa się następująco: najpierw obliczamy Qak zwykle) prawdopodobieństwa reprodukcji p>se/ecf,=^/Z/J, następnie - liczby oczekiwanych kopii dla każdego osobnika e^pselect^n. Każdy osobnik otrzymuje tyle kopii, ile wynosi część całkowita et, po czym populacja zostaje uporządkowana według części ułamkowych e" a pozostałe wolne miejsca w nowej populacji zostają zapełnione kopiami osobników wziętych z góry listy.
Obie metody wyboru losowego wg reszt (z powtórzeniami i bez powtórzeń) rozpoczynają się identycznie, jak wybór deterministyczny. Obliczamy oczekiwaną liczbę kopii dla każdego osobnika i przydzielamy mu na początek część całkowitą tej liczby. Od tej chwili drogi metod losowych i metody deterministycznej rozchodzą się. W wariancie
4.4. Udoskonalenia techniczne
137
z powtórzeniami, części ułamkowe oczekiwanych liczb kopii służą do wykalibrowania tarczy ruletki, która następnie zostaje użyta w znany sposób do wypełnienia pozostałych wolnych miejsc w nowej populacji. W wariancie bez powtórzeń części ułamkowe oczekiwanych liczb kopii zostają potraktowane jako prawdopodobieństwa. Następnie wykonujemy serię kolejnych prób Bernoulliego, w których wspomniane części ułamkowe odgrywają rolę prawdopodobieństw sukcesu. Na przykład ciąg kodowy, dla którego oczekiwana liczba kopii wynosi 1,5, otrzyma jedną kopię na pewno i jedną z prawdopodobieństwem 0,5. Proces ten jest kontynuowany dopóty, dopóki wszystkie miejsca w populacji nie zostaną zapełnione.
Użycie procedury turniejów losowych zostało zasugerowane Brindle przez Wetzela (Wetzel, 1983). W metodzie tej (którą Brindle nazywała metodą rang), oblicza się w zwykły sposób prawdopodobieństwa reprodukcji, po czym dokonuje się losowania par osobników wg reguły ruletki. Po wylosowaniu pary, osobnik o wyższym przystosowaniu zostaje ogłoszony zwycięzcą i umieszczony w nowej populacji. Proces jest kontynuowany aż do całkowitego wypełnienia populacji.
Brindle porównała opisane sześć metod selekcji używając zestawu siedmiu funkcji własnego pomysłu. Późniejsze analizy (K.A. De Jong i L.B. Booker, doniesienie prywatne, 1985) zakwestionowały jej odejście od standardowego zestawu testowego. Pewna łiczba wybranych przez nią funkcji charakteryzowała się liczbą maksimów tego samego rzędu, co rozmiar przestrzeni poszukiwań (230 punktów). Wynikł stąd tzw. problem alia-sów: wskutek zbyt ubogiej próby losowej na zbiorze równoodległych punktów, algorytm wykrywał fałszywe periodyczności i nie był zdolny do poprawnego rozróżniania wierzchołków na podstawie podobieństwa ciągów kodowych. Mimo tych trudności badania wykonane przez Brindle potwierdziły zasadniczą niższość selekcji wg reguły ruletki, zaobserwowaną wcześniej przez De Jonga (1975). Różnice w efektywności między pozostałymi pięcioma mechanizmami były nieznaczne i Brindle nie byla w stanie wykazać przewagi któregokolwiek z nich, chociaż w pozostałej części rozprawy ograniczyła się do metody deterministycznej.
Kolejne studia procesów poszukiwania genetycznego, wchodzące w skład badań nad maszynami uczącymi się prowadzonych przez Bookera (1982) wykazały wyższość wyboru losowego wg reszt bez powtórzeń nad modelem wartości oczekiwanej De Jonga (czyli wyboru losowego bez powtórzeń). Wynik ten doprowadził do szerokiego upowszechnienia pierwszej z tych metod w późniejszych zastosowaniach algorytmów genetycznych.
Ze względu na popularność tej metody, podajemy tu jedną z jej implementacji (wyd 4.1). Populacja pop zostaje tam poddana reprodukcji metodą wyboru losowego wg reszt bez powtórzeń, za pośrednictwem procedury preselect i funkcji select (w których występuje jako parametr formalny). Procedura preselect zajmuje się wyznaczeniem części całkowitych i ułamkowych oraz zapisuje indeksy wybranych ciągów kodowych w tablicy choices. Funkcja paskalowa select może być następnie użyta do sukcesywnego losowania po jednej kopii z tablicy choices. Włączenie tego fragmentu do programu SGApozostawiamyjakoćwiczenienazakończenierozdziału. ..... .,,... ;
138
4. Niektóre zastosowania algorytmów genetycznych
type choicearray - array[l..maxpop] of integer;
choices:choicearray; nremain:integer;
( Array of choices )
procedurę preselect(popsize:integer; avg:real;
var pop:population; var choices:choicearray); ( Selection by stochastic remainder method ) . ^ , ^ var j, jassign, k:integer;
expected:real; ' - winner:boolean; , , ,
fraction:array[l..maxpop] of real;
begin '' '
j :- 0; k :- 0; . ,
repeat ( Assign whole nurabers )
j :- j + 1;
expected : pop[j].fitness / avg; jassign :- trunc(expected); fraction[j] :- expected - jassign; ; while (jassign > 0) do begin
k :- k + 1; jassign :- jassign - 1; choices[k] :- j
/' �' �' ., end; :_>. ; .i �' ' � , -
until j - popsize; j :- 0;
while k < popsize do begin ( Assign fractional parts ) j :- j + 1; if j > popsize then j :- 1; if fraction[j] > 0.0 then begin
'�� '����-. winner :- flip(fraction[j]); ( A winner if true ) if winner then begin k :- k + 1; choices[k] : j;
fraction[j] :- fraction[j] - 1.0; end;
end; ,
end; , , ,
end;
function select(var popsize,nremain:integer;
var choices:choicearray; var pop:population):integer; ( select using remainder method )
var jpick:integer; /�'.-'. �
begin -, ,t ,:
jpick :- rnd(l,nremain);
select :- choices[jpick];
writeln('jpick-',jpick,' choices-',choices[jpick],' nremain-',nremain);
choices[jpick] : choices[nremain]; ; nremain :- nremain - 1; end;
Wyd. 4.1. Podprogramy wyboru losowego wg reszt w Pascalu. Procedury prese/ect i select
4.4.2. Mechanizmy skalowania
Od chwili, kiedy De Jong swoimi pracami wyznaczył ramy badań nad algorytmami genetycznymi, skalowanie funkcji celu stało się powszechnie przyjętą praktyką. Robi się to w celu zapewnienia odpowiedniego poziomu konkurencji podczas wykonywania al-
4.4. Udoskonalenia techniczne
139
gorytmu. Przy braku skalowania spotykamy się z tendencją do dominowania w procesie selekcji ze strony niewielkiej liczby superosobników. W takiej sytuacji wartości funkcji celu muszą zostać "pomniejszone", by zapobiec opanowaniu populacji przez te super-cłągi. W późniejszej fazie, gdy skład populacji jest bardziej jednorodny, poziom konkurencji między osobnikami spada i proces zaczyna bezładnie błądzić. Tym razem wartości funkcji celu muszą być "powiększone", by uwydatnić różnice między członkami populacji, dzięki czemu najlepsi z nich mogą zostać odpowiednio nagrodzeni. W rzeczywistości mechanizmy skalowania nie są niczym nowym, datują się od najwcześniejszych empirycznych studiów Bagleya (1967) i Rosenberga (1967). Przegląd aktualnych procedur skalowania można znaleźć u Forrest (1985a). Metody te obejmują:
1) skalowanie liniowe;
2) skalowanie a-obcinające [a-truncation];
3) skalowaniepotęgowe.
Skalowanie liniowe omówiliśmy już w rozdziale trzecim. Jak wskazuje sama nazwa, zmodyfikowaną funkcję przystosowania/' otrzymujemy tu z pierwotnej funkcji/ stosując przekształcenie liniowe postaci:
f = Współczynniki a i b tego przekształcenia są na ogół dobierane w ten sposób, żeby spełnić dwa warunki: zachować niezmienioną wartość średniego przystosowania oraz ustalić maksymalną wartość wyskalowanego przystosowania na poziomie określonej krotności (najczęściej dwu-) średniego przystosowania. Te dwa warunki łącznie zapewniają, że przeciętny członek populacji otrzymuje przeciętnie jednego potomka, a najlepszy - tylu, ile wynosi wspomniana krotność. Trzeba przy tym zachować ostrożność, aby skalowanie nie doprowadziło do pojawienia się ujemnych wskaźników przystosowania.
Skalowanie liniowe działa dobrze z wyjątkiem przypadków, gdy ujemne wartości zmodyfikowanej funkcji przystosowania przekreślają możliwośćjego użycia. Najczęściej zdarza się to w późnej fazie przebiegu, kiedy większość członków populacji charakteryzuje się wysokim przystosowaniem, lecz kilku degeneratów ma bardzo niskie wskaźniki. Aby obejść tę trudność, Forrest (1985a) zaproponowała wstępne przetworzenie pierwotnej funkcji przystosowania uwzględniającejej wariancję w populacji. Wprocedu-rze tej, którą nazywamy skalowaniem o-obcinającym ze względu na związek z odchyleniem standardowym funkcji przystosowania a, od pierwotnego przystosowania odejmuje się stałą, zgodnie ze wzorem
f=f-przy czym krotność c dobiera się jako liczbę między 1 a 3. Wszystkie wartości ujemne Of'<0) zostają arbitralnie zamienione na 0. Po takim obcięciu funkcji przystosowania możnajuż bezpiecznie wykonać skalowanie liniowe, nie narażając się na ujemne wyniki. Gillies (1985) zaproponował przekształcenie typu potęgowego, przy którym skalowanie polega na podniesieniu pierwotnej funkcji przystosowania do pewnej ustalonej potęgi:
140
4. Niektóre zastosowania algorytmów genetycznych
'=k
f'=f
W swych badaniach (o ograniczonym zakresie) dotyczących widzenia maszynowego Gillies wybrał &=1,005; ogólniejednak wartość k zależy od problemu i może wymagać zmiany podczas przebiegu - aby doprowadzić do "rozciągnięcia" lub "ściągnięcia" zakresu, zależnie od potrzeby. -- �
4.4.3. Nadawanie rang
Fakt, że wszystkie opisane tu procedury skalowania mają w jakimś stopniu charakter metod ad hoc, skłonił Bakera (1985) do rozważenia nieparametrycznej metody selekcji. Polega ona na uporządkowaniu populacji według wartości funkcji celu. Liczba kopii, jaką otrzymuje dany osobnik, zależy wyłącznie od jego rangiJ). Na rysunku 4.24 przedstawiono jeden ze stosowanych przez Bakera sposobów realizacji tego przyporządkowania. Przeprowadził on eksperymenty, porównując swoją metodę rang z innymi rodzajami selekcji. Wyniki były w ogólności niepewne, chociaż metoda Bakera wykazała tę samą odporność na tendencje do nadmiernej i niedostatecznej reprodukcji, co normalne procedury selekcji w połączeniu ze skalowaniem. Metoda nadawania rang była poddana krytyce, ponieważ osłabia ona w istotny sposób związek między przystosowaniem a funkcją celu. Bezpośredni związek funkcji przystosowania i funkcji celu nie ma jednak oparcia w teorii, a procedura nadawania rang dostarcza konsekwentnego sposobu regulacji liczby potomstwa. Potrzebujemy wciąż lepszej teorii reprodukcji, która określiłaby sposób przydziału liczby kopii elementom bieżącej populacji, bez szczegółowej wiedzy natemat funkcji ceIu i sposobu kodowania.
max --i
Liczba kopii
mm
Ranga Rys. 4.24. Liczba kopii w metodzie nadawania rang (Baker, 1985)
0 Tj. miejsca w tym uszeregowaniu Q>rzyp. tłum.).
4.5. Aktualne zastosowania algorytmów genetycznych
141
4.5. Aktualne zastosowania algorytmów _____________________genetycznych
W tablicy 4.4 podano zestawienie niektórych dawniejszych i obecnych zastosowań algorytmów genetycznych. Na resztę rozdziału składa się wybór aktualnych zastosowań AG w nauce, technice i przemyśle. W tej chwili skoncentrujemy się na tych zastosowaniach, w których posłużono się jakąś odmianą elementarnego algorytmu genetycznego. W następnym rozdziale rozszerzymy nasze pole widzenia na eksperymenty i doświadczenia związane z bardziej złożonymi mechanizmami genetycznymi.
Tablica 4.4. Zastosowania algorytmów genetycznych w zadaniach poszukiwania i optymalizacji
Rok Badacz(e) Opis
Biologia
1967 Rosenberg Symulowana ewolucja populacji organizmów jednokomór-
kowych
1970 Weinberg Projekt symulacji populacji komórek z zastosowaniem al-
gorytmu genetycznego z metapoziomu
1984 Perry Badania nad teorią nisz i specjacją przy użyciu algorytmów
genetycznych
1985 Grosso , : Symulacja diploidalnego AG z jawnymi podpopulacjami
� i migracją
1987 Sannier i Goodman Adaptacja mechanizmów reagowania na dostępność pokar-
mu w przestrzeni i czasie za pomocą AG
Informatyka
1967 Bagley
1979 Raghavan i Birchard
1982 Gerardy
1984 Gordon
1985 Rendell
1987 Raghavan i Agarwal
Technika i badania operacyjne
1981c Goldberg
1982 1983 1985a 1985b
Etter, Hicks i Cho
Goldberg
Davis
Davis
Adaptacyjny algorytm gry w sześć pionków z zastosowaniem AG
Algorytm grupowania oparty na algorytmie genetycznym Próba identyfikacji automatu probabilistycznego za pomocą AG
Adaptacyjna metoda opisu dokumentów przy użyciu AG Zastosowanie AG do poszukiwania funkcji oceny strategii gry
Adaptacyjna metoda grupowania dokumentów przy użyciu AG
Identyfikacja modelu amortyzatora za pomocą elementarnego AG
Projektowanie filtru adaptacyjnego za pomocą elementarnego AG
Optymalizacja pracy gazociągu w reżymach stacjonarnym i nieustalonym za pomocą AG
Zastosowanie algorytmu genetycznego w zadaniach upakowania i kolorowania grafu
Projekt zastosowania algorytmu genetycznego w zadaniach szeregowania typu job shop
142 4. Niektóre zastosowania algorytmów genetycznych
Tablica 4.4. (cd.) : ..... ,^ _ ,
Rok Badacz(c) Opis
1985 Davis i Smith Projektowanie układów VLSI za pomocą AG
1985 Fourman ' Kompaktyfikacja układów VSLI za pomocą AG
1985 Goldberg i Kuo Optymalizacja rurociągu do przesyłu ropy w reżimie stac-
jonarnym za pomocą AG
1986 Glover Projektowanie układu klawiatury za pomocą AG
1986 Goldberg i Samtani Optymalizacja konstrukcji (kratownica płaska) za pomocą
AG
1986 Goldberg i Smith Zastosowanie AG w ślepej wersji zagadnienia plecakowe-
go
1986 Minga �"' ' � " Optymalizacja elementów podwozia samolotów za pomocą
AG
1987 Davis i Coombs Optymalizacja wielkości łączy w sieci łącznościowej za
pomocą AG z operacjami zaawansowanymi
1987 Davis i Ritter Układanie planu lekcji metodą symulowanego wyżarzania
z algorytmem genetycznym na metapoziomie
Algorytmy genetyczne !
1962c Holland Projekt samoadaptującego się komputera komórkowego
1968 Holland Opracowanie teorii schematów
1971 Hollstien Optymalizacja funkcji dwóch zmiennych przy zastosowa-
niu reguł kojarzenia i selekcji
1972 Bosworth, Foo i Zeigler Operacje "AG-podobne" na genach "rzeczywistych" ze
skomplikowanymi wariantami mutacji
1972 Frantz : Badania efektów nieliniowości pozycyjnej i operacji inwer-
sji
1973a Holland Problem optymalnego wyboru w AG a zagadnienie dwu-
ramiennego bandyty
1973 Martin . Badania teoretyczne "AG-podobnych" algorytmów proba-
bilistycznych
1975 De Jong Fundamentalne badania parametryczne elementarnego al-
gorytmu genetycznego w środowisku pięciu funkcji testo-
wych
1975 Holland Publikacja ANAS
1977 Mercer Algorytm genetyczny sterowany algorytmem genetycznym
� z metapoziomu
1981 Bethke Zastosowanie funkcji Walsha do analizy wartości przysto-
sowawczej schematów
1981 Brindle Badania metod selekcji i dominowania w AG
1983 Pettit i Swigger Ogólne badania możliwości zastosowania AG w niestacjo-
narnych zadaniach poszukiwania
1983 Wetzel Zastosowanie AG w zagadnieniu komiwojażera (TSP)
1984 Mauldin Poszukiwanie metod heurystycznych zapewniających
utrzymanie różnorodności populacji w elementarnym AG
1985 Baker Eksperymenty z metodą selekcji przez nadawanie rang
1985 Booker ,, ,,.. , Koncepcje zgodności częściowej, podziału zasobów i ba-
j: i rier reprodukcyjnych
1985 Goldberg i Lingle Zastosowanie operacji PMX w zagadnieniu komiwojażera
i analiza o-schematów
*\ 4 R Aktnalnp 7astnsnwania algorytmów gpnfityn7nyr.h 143
Tablica 4.4. (cd.)
Rok Badacz(e) Opis
1 985 Grefenstette i Fitzpatrick Badania elementarnego algorytmu genetycznego w zasto-
sowaniu do funkcji przybliżonych
1 985 Schaffer Optymalizacja wielokryterialna za pomocą AG z podpopu-
lacjami
I985d Goldberg Oszacowanie optymalnej wielkości populacji ze względu
na liczbę efektywnie przetwarzanych schematów
1 986 Grefenstette Algorytm genetyczny sterowany algorytmem genetycznym
z metapoziomu
1 987 Baker Redukcja odchyleń losowych w procedurach selekcji
1 987 Bridges i Goldberg Pogłębiona analiza reprodukcji i krzyżowania w /-bitowym
AG
I987d Goldberg : Minimalny problem zwodniczy (MDP) przy reprodukcji
i krzyżowaniu
!987 Goldberg i Richardson Formowanie się nisz i powstawanie gatunków jako efekt
zastosowania funkcji współudziału
1 987 Goldberg i Segrest Analiza reprodukcji i mutacji za pomocą łańcuchów Mar-
kowa
1 987 Goldberg i Smith Optymalizacja funkcji niestacjonarnych za pomocą diploi-
dalnego AG
1 987 Oliver, Smith i Holland Symulacja i analiza permutacyjnych operacji rekombinacji
1 987 Schaffer Analiza wpływu procedur selekcji na propagację schema-
tów
1 987 Schaffer i Morishima Adaptacyjny mechanizm krzyżowania
1 987 Whitley Zastosowanie selekcji na podstawie potomstwa w AG
Techniki hybrydowe
1 985 Ackley Doniesienie o algorytmie konekcyjnym o własnościach
zbliżonych do AG
1 985 Brady Zastosowanie operacji quasi-genetycznych w zagadnieniu
komiwojażera
1 985 Grefenstette i in. Zastosowanie operacji genetycznych wspomaganych wie-
dzą w zagadnieniu komiwojażera
1 987 Dolan i Dyer Propozycja użycia AG do adaptacji topologii sieci konek-
cyjnej
I987b Grefenstette Zastosowanie informacji specyficznej dla zadania w poszu-
kiwaniu genetycznym
1 987 Liepins, Hilliard, Palmer i Morrow Porównanie ślepych i zachłannych metod poszukiwania dla
zagadnień kombinatorycznych
1987 Shaefer Technika globalnie modyfikowanej reprezentacji adapta-
cyjnej (ARGOT)
1987 Sirag i Weisser Sterowanie częstością operacji genetycznych w zagadnie-
niu komiwojażera za pomocą metody typu symulowanego
wyżarzania
1987a Suh i Van Gucht Operacje genetyczne wspomagane wiedzą w zagadnieniu
komiwojażera
Przetwarzanie obrazów i rozpoznawanie wzorców
1970
Cavicchio
Dobór detektorów w zadaniu rozpoznawania wzorców binarnych
*J
',r>''
144
4. Niektóre zastosowania algorytmów genetycznych
Tablica 4.4. (cd.)
Rok
Badacz(e)
Opis
1984 Fitzpatrick, Grefenstette i Van Gucht
1985 Englander 1985 Gillies
1987 Stadnyk '"'''''
Obróbka obrazów za pomocą AG w celu minimalizacji różnic
Dobór detektorów przy zadanej klasyfikacji obrazów Poszukiwanie detektorów cech obrazów za pomocą AG Rozpoznawanie klas wzorców przy użyciu częściowego dopasowania
Współbieżne implementacje algorytmów genetycznych
1976 Bethke
1981 Grefenstette
1987 Cohoon, Hegde, Martin i Richards
1987 Jog i Van Gucht , .-..,.,
1987 Pettey, Leuze i Grefenstette
1987b SuhiVanGucht
1987 Tanese
Nauki fizyczne
1985b Shaefer
Nauki spoteczne
1979 Reynolds
1981
1985a
1985b
Smith i De Jong
Axelrod
Axelrod
Wstępne rozważania teoretyczne na temat możliwych implementacji współbieżnych
Wstępne rozważania teoretyczne na temat różnych implementacji współbieżnych
Symulowana implementacja współbieżna optymalnego rozmieszczenia liniowego
Algorytm genetyczny wspomagany wiedzą, z elementami współbieżności
Implementacja współbieżna AG na sprzęcie firmy Intel Selekcja lokalna we współbieżnym algorytmie genetycznym dla zagadnienia komiwojażera Implementacja współbieżna algorytmu genetycznego w architekturze HyperCube
Zastosowanie AG do rozwiązywania równań nieliniowych związanych z powierzchniami potencjału
Zastosowanie metod adaptacyjnych typu AG do modelowania zachowań prehistorycznych myśliwych-zbieraczy Kalibracja modelu migracji populacyjnych za pomocą AG Symulacja ewolucji norm behawioralnych za pomocą AG Zastosowanie AG do poszukiwania rozwiązań iterowanego dylematu więźnia
4.5.1. Optymalizacja rurociągu gazowego
Moja własne prace koncentrowały się wokół inżynierskich zastosowań algorytmów genetycznych. Po wysłuchaniu wykładów Johna Hollanda z algorytmów genetycznych na Uniwersytecie Michigan, rozpocząłem studia doktoranckie, w czasie których użyłem algorytmów genetycznych do rozwiązania problemów optymalizacji i samoadaptacji związanych z regulacją pracy gazociągu (Goldberg, 1985).
W przypadku pierwszego problemu zastosowałem model Wonga i Larsona (1968) stacjonarnego przepływu w rurociągu złożonym z 10 kompresorów i 10 przewodów rurowych. Schemat tego systemu został pokazany na rys. 4.25. Zachowanie systemu jest
4.5. Aktualne zastosowania algorytmów genetycznych
145
Kompresor
Dostawa
Odbiór
Rys. 4.25. Schemat gazociągu. Za Goldbergiem (1983)
wyznaczone przez układ równań nieliniowych określających spadki ciśnienia w rurach i przyrosty ciśnienia w kompresorach. Różnica kwadratów ciśnień zmienia się tak jak kwadrat objętościowego natężenia przepływu:
PS*M-PD*, = K,Q,lQ,\ ~
gdzie PS - ciśnienie wlotowe, PD - ciśnienie wylotowe, Q - objętościowe natężenie przepływu, K - współczynnik oporu przewodów rurowych oraz i - numer rury/kom-presora. Ciśnienia wlotowe i wylotowe, objętościościowe natężenie przepływu oraz moc pobierana przez stację kompresorową są związane z kolei zależnością
HP, = Q,[A,(PD,/PSf>-Bj
gdzie HP - pobierana moc, A, B, C - stałe charakteryzujące stację kompresorową. Paliwo do zasilania kompresora jest pobierane bezpośrednio z rurociągu ze stałym natężeniem, co daje następujący związek:
QM = O - r,)Q,
gdzie r - współczynnik poboru paliwa.
Zadanie polega tu na zminimalizowaniu całkowitego poboru mocy przy zadanym minimalnym i maksymalnym ciśnieniu oraz stosunku ciśnień:
W moim modelu więzy zostały uwzględnione przez wprowadzenie kwadratowych funkcji kar, tak jak to opisano w poprzednim rozdziale. Współczynniki kar zostały dobrane w taki sposób, aby nakładać znaczące obciążenia w przypadku naruszenia ograniczeń nominalnych.
Wong i Larson zdecydowali się wybrać w charakterze parametru sterującego różnicę kwadratów ciśnień u wlotu i wylotu każdego kompresora, U^PD]-PS], chociaż z fizycznego punktu widzenia moc stacji czy też stosunek ciśnień wydawałyby się bardziej przekonujące. W celu zachowania zgodności przyjąłem ich rozwiązanie i zakodowałem standaryzowane wartości parametrów U, poszczególnych stacji przy użyciu
146
4. Niektóre zastosowania algorytmów genetycznych
czteropozycyjnego kodu dwójkowego. Pełny ciąg kodowy powstałjako konkatenacja 10 bloków, w porządku zgodnym z numeracją stacji. Parametry mogły się zmieniać w granicach od ^min = 0 psia2 do f/max = 7,5xl05 psia2 �.
Wyniki trzech eksperymentów numerycznych zostały przedstawione na rys. 4.26 i 4.27. We wszystkich tych eksperymentach przyjęto następujące wartości parametrów algorytmu genetycznego:
n = 50(wielkoscpopulacji); *> �
pc = ],0(prawdopodobienstwokrzyzowania);
pm = 0,001(prawdopodobieństwomutacji). -��-�<���>����
Jako metodę selekcji zastosowano wybór losowy wg reszt bez powtórzeń. Na rysunkach 4.26 i 4.27 pokazano odpowiednio najlepsze i średnie wyniki w kolejnych pokoleniach. Na rysunku 4.28 przedstawiono profil ciśnienia otrzymany w przebiegu 2 w porównaniu z optymalnym profilem, znalezionym przez Wonga i Larsona metodą programowania dynamicznego (1968). We wszystkich trzech przebiegach, po przeszukaniu nieznacznej części dyskretnej przestrzeni rozwiązań, otrzymano prawie optymalne wyniki.
W celu przetestowania elementarnego algorytmu genetycznego na przykładzie innego, zupełnie odmiennego zadania optymalizacji gazociągu, zaprogramowałem model
Klucz
D SS.1 & SS.2 X SS.3
20
30
Pokolenie
40
50
60
Rys. 4.26. Najlepsze znalezione wyniki dla zadania optymalizacji gazociągu. Za Goldbergiem (1983)
" psia: funt na cal kwadratowy ^edn. ciśnienia bezwględnego); zakres ten odpowiada mniej więcej 0-495 at2 (przyp. tlum.).
3 ^g
M
00
E 5
3 a
8 s=
^ o
a> ćń;
co 2
o co'
>5 2.
3 m
c 9-
cQ a)
5 N
^ a>
ż i-
N 3 a> g_
O R"
O B)
SL. cr
CD cQ
<3 ffi
JB
dffi co p 00 " ^D
o
T3
^?
0)
Ciśnienie (psia)
0,00 200,00 400,00 , 600,00 800.00^ 1000,00 1200,00
w
_�>
fO
cn-
Koszt (w koniach mechanicznych) (X10^2)
4000,00 6000,00 7999,99 9999,99
c SL
D CD
N 0) 2. O CO O
a>
CQ
o
CQ CD 3 CD
f

co
00
co
148
4. Niektóre zastosowania algorytmów genetycznych
Wonga i Larsona nieustalonego przepływu w pojedynczym przewodzie rurowym. W zadaniu tym chodzi o zminimalizowanie energii sprężania przy zadanych minimalnym i maksymalnym ciśnieniu oraz stosunku ciśnień. Szczegóły tego modelu wykraczają poza zakres książki; wystarczy powiedzieć, że uproszczone cząstkowe równania różniczkowe ruchu i ciągłości zostały przekształcone na układ zwykłych równań różniczkowych za pomocą metody charakterystyk, te zaś z kolei równania zostały rozwiązane numerycznie na regularnej siatce przestrzenno-czasowej przy użyciu metody różnicowej. Podobnie jak w przypadku stacjonarnym więzy zostały włączone do modelu za pośrednictwem kwadratowych funkcji kar. Dalsze szczegóły tego modelu, funkcji celu i więzów można znaleźć w oryginalnym opracowaniu (Goldberg, 1983). Tutaj poprzestaniemy na omówieniu metody kodowania i otrzymanych wyników.
Ze względu na ciągły (w czasie) charakter zadania o przepływie nieustalonym, było konieczne wprowadzenie dodatkowego etapu dyskretyzacji. W zadaniu stacjonarnym parametry sterujące stacji kompresorowych Uf mogły być zakodowane w postaci czterobitowych bloków i skonkatenowane wjeden ciąg kodowy. W zadaniu o przepływie nieustalonym sterowanie ma postać funkcji opisującej dopływ gazu w czasie u wlotu przewodu rurowego. Aby umożliwić rozwiązanie zadania przy użyciu algorytmu genetycznego, przeprowadziłem dyskretyzację funkcji natężenia przepływu na zbiorze 15 równoodległych punktów. Przyjęto, że między tymi punktami natężenie przepływu zmienia się liniowo (por. rys. 4.29). Taka metoda dyskretyzacji została dobrze rozwinięta w literaturze na temat teorii interpolacji i elementu skończonego. Można by użyć innych funkcji interpolacyjnych Qak funkcje schodkowe, wielomiany wyższego stopnia, gładkie splajny i inne), ale przybliżenie liniowe okazało się wystarczająco dokładne dla zakładanych celów.
ą
0,Q
-------Natężenie wylotowe (zadane)
D Natężenie wlotowe (obliczone)
50,00 100,00
Czas (w minutach)
150,00
Rys. 4.29. Optymalizacja gazociągu w warunkach przepływu nieustalonego. Natężenie przeptywu u wylotu (zadane zapotrzebowanie) i natężenie przeptywu u wlotu obliczone przez algorytm genetyczny(przebiegTR.1).ZaGoldbergiem(1983)
4.5. Aktualne zastosowania algorytmów genetycznych
149
Po przeprowadzeniu dyskretyzacji wartości natężenia przepływu w 15 równoodległych chwilach wyznaczyły harmonogram przepływu. Do zakodowania tych 15 parametrów użyłem opisanego w rozdziale trzecim blokowego zapisu pozycyjnego ze standaryzacją parametrów. Wartości <2,, zmieniające się od 2min = 100 MMCFD do Qm^ = 200 MMCFD" zostały zakodowane przy użyciu trzech pozycji binarnych każda. Sposób kodowania ilustruje poniższy przykład (dla podkreślenia poszczególne podciągi oddzielono odstępami):
ciąg kodowy: 000 111 000 000 111 . . . 111 000
parametr: C^ Q2 Q3 Q4 Q5 ... Q14 Q15 ;
wartość: 100 200 100 100 200 ... 200 100
Wyniki dwóch eksperymentów numerycznych są przedstawione na rys. 4.30 i 4.31 (odpowiednio najlepsze i średnie wyniki w poszczególnych pokoleniach). Podobnie jak w przypadku stacjonarnym, prawie optymalne rozwiązania zostały znalezione bardzo szybko, po przeszukaniu nieznacznego ułamka całej przestrzeni. Więcej mówiący wykres można zobaczyć na rys. 4.32. Porównano tam najlepszy harmonogram otrzymany w drugim przebiegu z wynikiem optymalnym ze względu na ciśnienie wylotowe. W swej
20 30 40
Pokolenie
so
Rys. 4.30. Najlepsze znalezione wyniki dla zadania optymalizacji gazociągu w warunkach przepływu nieustalonego. Za Goldbergiem (1983)
MMCFD = milion stóp sześciennych dziennie; zakres ten odpowiada ok. 2,8-5,7 mln m3
Rys. 4.31. Średnie wyniki dla zadania optymalizacji gazociągu w warunkach przepływu nieustalonego. Za Goldbergiem (1983)
o
c i o : 'c " -w
O
0,00
-------optymalne
D obliczone
150,00
50,00 100,00
; Czas (w minutach)
Rys. 4.32. Wykresy zmian ciśnienia dla zadania optymalizacji gazociągu w warunkach przeptywu nieustalonego. Porównanie wartości optymalnych i obliczonych przez algorytm genetyczny. ZaGoldbergiem(1983)
oryginalnej pracy Wang i Larson stwierdzili, że strategia optymalna polega na utrzymywaniu ciśnienia wylotowego na najniższym dopuszczalnym poziomie przez cały okres objęty harmonogramem. Jak pokazuje rys. 4.32, znaleziony za pomocą algorytmu genetycznego harmonogram przestrzega dość ściśle tej zasady.
4.5. Aktualne zastosowania algorytmów genetycznych
151
4.5.2. Optymalizacja strukturalna konstrukcji przy użyciu ________________________ algorytmu genetycznego
Rurociągi nie są jedynym przykładem systemów technicznych, w których z powodzeniem zastosowano algorytmy genetyczne. Obecnie jednym z obszarów cieszących się zainteresowaniem jest optymalizacja strukturalna konstrukcji [structural optimization\. W niedawnej pracy (Goldberg i Samtani, 1986), mój magistrant i ja użyliśmy algorytmu genetycznego do optymalizacji 10-czlonowej płaskiej kratownicy. Geometria kratownicy została pokazana na rys. 4.33. To samo zadanie optymalizacji rozwiązywano innymi metodami; chodziło nam jednak o zbadanie zachowania się algorytmu genetycznego w różnego typu sytuacjach. Obecnie przedmiotem badań jest możliwość zastosowania AG do trudniejszego zadania z zakresu optymalizacji strukturalnej, gdzie standardowe techniki nie są odpowiednie z racji rozmiaru zadania, wielomodalności i innego rodzaju trudności (Minga, 1986, 1987).
W omawianym zadaniu chodzi o zminimalizowanie ciężaru całkowitego struktury, przy zachowaniu więzów określających maksymalne i minimalne naprężenia każdego z elementów. Szczegóły modelu matetftatycznego można znaleźć w oryginalnej pracy. W naszych badaniach używaliśmy standardowego programu komputerowego do analizy każdego projektu kratownicy wygenerowanego za pomocą AG. Zastosowany algorytm opierał się na trzech operacjach: selekcji metodą ruletki, krzyżowaniu prostym i mutacji, a więzy zostały wprowadzone za pomocą kwadratowej funkcji kary. Parametrami było tu 10 pól elementów składowych A,, które zostały zakodowane za pomocą blokowego zapisu pozycyjnego ze standaryzacją parametrów, przy czym każdy z lO-bitowych podciągów reprezentował wartości z zakresu od Amin = 0,l do Amax=10 cali kwadratowych0.
(6)
ioo^
360"
100
Rys. 4.33. Schemat 10-członowej kratownicy płaskiej w zadaniu optymalizacji konstrukcji (Goldberg i Samtani, 1986). Przedruk za zezwoleniem (9th Conference on Electronic Computation ASCE, February, 1986)
" Ok. 0,6-57,6 cm2 (przyp. t(um.).
152
4. Niektóre zastosowania algorytmów genetycznych
Wyniki z kilku niezależnych przebiegów algorytmu genetycznego są pokazane na rys. 4.34 i 4.35 (odpowiednio najlepsze i średnie w kolejnych pokoleniach). Charakter zbieżności nie odbiega od zachowania obserwowanego w innych badaniach.
8,6
8,5 -8,4 -
i
8,3 -
8,8 -2,1 -
1,8 -1,8-1/' ^ 1,6-1,5-
D Przebieg 1
80
- Przebieg 2
Pokolenie
o Przebieg 3
Optymalny
Rys. 4.34. Najlepsze znalezione wyniki w zadaniu optymalizacji konstrukcji (Goldberg i Samtani, 1986). Przedruk za zezwoleniem (9th Conference on Electronic Computation ASCE, Feb-ruary, 1986)
860 840 880 � 800 � 180 180 �
100 -j n 11 ! ) r \ i ^ ' \
80 - K ...... ;
60 - n '�.', . , >
40 - L,
20 - r***_^Aj*V^_A^W^ ^5UL = __ B_
0 " , 80 40
Pokolenie
Przebieg 1 ł Przebieg 2 o Przebieg 3 i Optymalny
Rys. 4.35. Średnie (dla populacji) wyniki w zadaniu optymalizacji konstrukcji (Goldberg i Samtani, 1986). Przedruk za zezwoleniem (9th Conference on Electronic Computation ASCE, Feb-ruary, 1986)
4.5. Aktualne zastosowania algorytmów genetycznych
153
4.5.3. Obróbka medycznych obrazów rentgenowskich za pomocą _______________________________ algorytmu genetycznego
Dotychczasowe przykłady zastosowań algorytmów genetycznych pochodziły z obszaru techniki (projektowanie techniczne i regulacja). Następny przykład dotyczy medycznego systemu analizy obrazów (Fitzpatrick, Grefenstette i Van Gucht, 1984; Grefenstette i Fitzpatrick, 1985). Zadanie to nie tylko zostało zaczerpnięte z innej dyscypliny, ale, jak wkrótce się przekonamy, związana z nim funkcja przystosowania nie ma już dobrze określonej reprezentacji matematycznej.
Fitzpatrick, Grefenstette i Van Gucht zastosowali algorytm genetyczny do obróbki obrazów w metodzie zwanej cyfrową angiografią różnicową (DAS). W systemie DAS lekarz bada wnętrze tętnicy, porównując dwa obrazy rentgenowskie, jeden wykonany przed wstrzyknięciem do światła tętnicy środka cieniującego i drugi wykonany po tym zabiegu. Obydwa obrazy zostają przetworzone cyfrowo i "odjęte" piksel po pikselu jeden od drugiego - w nadziei, że otrzymany w rezultacie obraz różnicowy ukaże wyraźny kontur wewnętrzny badanej tętnicy. Gdyby obrazy różniły się wyłącznie obecnością środka cieniującego, w wyniku operacji "odejmowania" widoczne powinny by pozostać jedynie obszary pokryte tym środkiem. Niestety, jest to wielkie "gdyby". Drobne ruchy pacjenta wystarczą, by oba obrazy przestały się nakładać, zaburzając w ten sposób obraz óżnicowy. W konsekwencji przed wykonaniem operacji odejmowania trzeba dokonać obróbki umożliwiającej dokładne nałożenie obrazów. .{
W tym właśnie miejscu wspomniana trójka badaczy postanowiła zastosować algorytm genetyczny. Metoda ich polegała na przekształceniu pierwszego obrazu (sprzed wstrzyknięcia) przy użyciu odwzorowania dwuliniowego (x'(x, y) = ^+a^x+a^y + a^xy oraz y'(x, y) = b" + blx+b2y + b^xy), co ilustruje rys. 4.36. Chociaż matematyczna postać przekształcenia jest tu ustalona, jego współczynniki potraktowano jako nieznane. Algorytm genetyczny został użyty do wyznaczenia współczynników minimalizujących różnice między obrazami sprzed i po wprowadzeniu środka cieniującego, w sensie średniej różnicy bezwzględnej. W tym celu współrzędne x i y każdego z czterech wierzchołków (rogów) obrazu zakodowano w postaci ośmiobitowych podciągów, reprezentujących przesunięcia w granicach od -8 do 8 pikseli (pełny obraz tworzył
Po przekształceniu
Przed przeksztateeniem
Rys. 4.36. Cyfrowe obrazy rentgenowskie przed i po obróbce. Wektory zaznaczone na diagramie ukazują przemieszczenie wierzchołków (Grefenstette i Fitzpatrick, 1985). Przedruk za zezwoleniem
154
4. Niektóre zastosowania algorytmów genetycznych
siatkę 100x100 punktów). Współczynniki przekształcenia dwuliniowego (w liczbie ośmiu) są jednoznacznie wyznaczone przez wektory przesunięć czterech wierzchołków obrazu. Algorytm genetyczny działający na pełnych 64-bitowych ciągach kodowych poszukiwał następnie dobrych przekształceń. Eksperymenty numeryczne z użyciem zarówno sztucznych, jak i rzeczywistych obrazów rentgenowskich wypadły pomyślne.
Jednym z ważnych czynników wziętych pod uwagę w tych pracach był koszt jednokrotnego obliczenia wartości funkcji przystosowania. W przypadku siatki 100x100, aby wyznaczyć średnią bezwzględną różnicę obrazów, trzeba wykonać około 10000 przekształceń oraz operacji odejmowania dla poszczególnych punktów. Grefens-tette i Fitzpatrick (1985) uświadomili sobie, że przy ustalonej liczbie operacji odejmowania pikseli powinno być możliwe osiągnięcie lepszego ogólnego dopasowania obrazów na podstawie wyrywkowego obliczania różnic. W celu sprawdzenia tej hipotezy przeprowadzili oni eksperymenty numeryczne, w których wykonywano 200000 operacji odejmowania pikseli, zmieniając przy tym liczbę pikseli wybranych do obliczenia jednej wartości funkcji. Rezultaty tych eksperymentów zostały przedstawione na rys. 4.37. Ten godny uwagi wykres pokazuje, że optymalna liczba pikseli w próbie wyniosła około 10 (na 10000). Badania te wydają się wskazywać, że algorytmy genetyczne w pewnym sensie ,,wola" korzystać z niedokładnych i zakłóconych wartości funkcji przystosowania, jeśli tylko w zamian mogą dokonywać eksploracji (nawet przybliżonej) większej liczby punktów w przestrzeni rozwiązań. Nie jest to wynik nieoczekiwany, ponieważ zgodnie z teorią algorytmy genetyczne są w stanie tolerować wyjątkowo zaburzone wartościowania funkcji - dzięki temu, że to schematy, a nie indywidualne ciągi kodowe, propagują się i podlegają ocenie w przyszłych pokoleniach. Ta zdolność do tolerancji może przynosić wymierne korzyści w sytuacjach, gdzie musimy dokonywać wyboru między dokładnymi i kosztownymi obliczeniami a zgrubnymi i szy-bkimiszacunkami.
50 100 150
Wielkość próby
zoo
Rys. 4.37. Dokładność algorytmu w zależności od wielkości próby użytej do wyznaczenia funkcji przystosowania w zadaniu obróbki obrazów (Grefenstette i Fitzpatrick, 1985). Przedruk za zezwoleniem
4.5. Aktualne zastosowania algorytmów genetycznych
155
4.5.4. lterowany dylemat więźnia
Jako ostatni w tym rozdziale przykład zastosowania algorytmów genetycznych wybraliśmy zagadnienie zaczerpnięte z politologił i teorii gier - iterowany dylemat więźnia. Problem ten był studiowany przez Axelroda (1985b, 1987), a Forrest (1985a) napisała odpowiedni program symulacyjny. Iterowany dylemat więźnia przybliża nas do tematyki maszyn uczących się, którą będziemy się zajmować w rozdziałach szóstym i siódmym. Dylemat więźniajest klasycznym, można by rzec prototypowym przykładem problemu konfliktu i kooperacji. W najprostszym sformułowaniu każdy z dwóch uczestników może wybierać między "współpracą" a "zdradą". W zależności od decyzji obu graczy każdy z nich otrzymuje "wypłatę", zgodnie z macierzą wypłat w rodzaju pokazanej na rys. 4.38. Jeśli obydwaj gracze współpracują, każdy z nich otrzymuje taką samą, umiarkowaną nagrodę (R). Jeśli tylko jeden z nich zdradzi, otrzymuje wtedy najwyższą wypłatę (T), podczas gdy drugi dostaje to, co należy się naiwniakowi (5). Jeśli obydwaj zdradzą, każdy otrzymuje minimalną wypłatę (umiarkowaną "karę", P). Dylemat więźnia był często podawany jako prosty, ale realistyczny model istotnej trudności w uzyskaniu zachowań kooperatywnych w sytuacji, gdy niegodziwość może popłacać. Zagadnienie to otrzymało nazwę dylematu więźnia, gdyż stanowi abstrakcyjny odpowiednik sytuacji więźnia, który ma do wyboru albo pójść na ugodę z prokuratorem i w ten sposób wydać swego wspólnika (zdrada), albo zachować milczenie na temat przestępstwa (współpraca).
Gracz 2
Decyzja Współpraca Zdrada
G r 1 a c z Współpraca (fi-6, R-e) (s-O. T-10)
Zdrada (T=IO. s=o) (p-2, P-2 )
Rys. 4.38. Typowa macierz wypłat w zadaniu o dylemacie więźnia
Problem robi się ciekawszy, gdy grę będziemy wielokrotnie powtarzać z udziałem tego samego gracza lub graczy, dzięki czemu przy podejmowaniu decyzji o współpracy bądź zdradzie mogą się oni kierować historią przeszłych zachowań. Ten tak zwany iterowany dylemat więźnia przyciągał od lat uwagę badaczy zajmujących się teorią gier. Niedawno rozegrano nawet dwa turnieje, w których przeciwnikami były programy komputerowe (Axelrod, 1985b). W obydwu zawodach ogólnym zwycięzcą pośród 76 konkurentów okazała się bardzo prosta strategia, znana pod nazwą "wet-za-wet". Zgodnie ze swą nazwą, strategia ta nakazuje współpracować w pierwszym ruchu, a następnie naśladować ostatnie posunięcia przeciwnika. Stanowi więc ona w pewnym sensie sformułowaną na opak "złotą zasadę" postępowania wobec bliźniego, głosząc otwarcie "Odpłacaj pięknym za nadobne".
156
4. Niektóre zastosowania algorytmów genetycznych
Fakt, że tak prosta strategia okazała się zdolna do pokonania bardziej wyrafinowanych przeciwników (pod względem wielkości programu), wydawał się, mówiąc ostrożnie, dość niezwykły, i Axelrod podjął kroki w celu znalezienia innych prostych strategii deterministycznych o tej samej lub większej sile. Użył on w swych poszukiwaniach algorytmu genetycznego, stosując sprytny sposób kodowania. Axelrod przyjął, że reguły decyzyjne mogą opierać się na posunięciach obu stron w trzech ostatnich ruchach. Dla każdego ruchu istnieją, oczywiście, cztery możliwości: obaj gracze współpracują (CC lub inaczej R), drugi gracz zdradza (CD lub 5), pierwszy gracz zdradza (DC lub T), albo obydwaj zdradzają (DD lub P). W celu zakodowania określonej strategii Axelrod przyporządkował najpierw każdemu z możliwych zachowań ciąg złożony z trzech liter. Na przykład ciąg RRR reprezentuje sytuację, w której obie strony współpracowały w ostatnich trzech ruchach, a SSP - sytuację, w której pierwszy z uczestników grał naiwniaka w pierwszych dwóch ruchach, a ostatecznie zdecydował się na zdradę. Każdy taki ciąg był następnie zamieniany na liczbę całkowitą z zakresu 0-63 (kody poszczególnych ruchów można traktować jako cyfry w układzie czwórkowym: CC=R = 0, DC=T=\, CD=S = 2, DD = P = 3; zgodnie z tą zasadą trzy wzajemne zdrady, czyli PPP, odpowiadają liczbie 63). Axelrod mógł teraz zapisać określoną strategię (zależną od trzech ostatnich ruchów) za pomocą 64-bitowego słowa reprezentującego ciąg symboli C (współpraca) i D (zdrada), gdzie /-ta pozycja określa reakcję gracza na /-tą sytuację. I tak np. symbol D na pozycji nr Ojest zapisem reguły mającej postać RRR^>D, a symbol C na pozycji nr 3 określa regułę RRP^C.
W rzeczywistości sytuacja jest nieco bardziej złożona, niż to przedstawiliśmy. Ponieważ reguły określone przez słowo 64-bitowe wymagają znajomości posunięć w trzech ostatnich ruchach, zachowanie w początkowej fazie gry pozostaje nieokreślone. Axelrod dołączył więc jeszcze sześć bitów (sześć symboli C lub L>) w celu określenia przestanek strategii, czyli założeń o sytuacji początkowej. Te sześć bitów opisywało po prostu kolejne posunięcia graczy przed rozpoczęciem gry. Dzięki temu normalne reguły w połączeniu z przesłankami mogły być użyte zarówno w fazie otwarcia, jak i w dalszym toku gry. (We wcześniejszej wersji Axelrod zakładał wstępną wzajemną współpracę, ale przekonał się, że wstępne zachowania mają istotny wpływ na wypracowanie strategii zdolnych do pobicia reguły wet-za-wet.) Ostatecznie więc, każdy z 70-bitowych ciągów reprezentował określoną strategię (64 bity) i przesłanki gry (6 bitów).
Po rozwiązaniu problemu kodowania Axelrod przystąpił do poszukiwania lepszych strategii gry. Aby zapewnić każdej strategii reprezentatywny sprawdzian, Axelrod utworzył grupę złożoną z ośmiu "zawodników" wybranych zjego wcześniejszych turniejów komputerowych. Grupa ta reprezentowała łącznie 98% zachowań obserwowanych w rozgrywkach komputerowych. Następnie, każda ze strategii-ciągów kodowych w 2()-ele-mentowej populacji rozgrywała pojedynek złożony ze 151 ruchów z każdym z ośmiu przeciwników. Wskaźniki przystosowania obliczano, biorąc średnią ważoną punktów zdobytych w pojedynkach z przeciwnikami, przy czym wagi odzwierciedlały możliwie dokładnie warunki panujące podczas turnieju. Startując od losowej populacji, algorytm genetyczny odkrył strategie, które biły regułę wet-za-wet w ogólnej klasyfikacji. Cytując własne słowa Axelroda (1985b, str. 13):
4.6. Podsumowanie
157
Jest to godne uwagi osiągnięcie, bowiem aby zdobyć tę dodatkową efektywność, reguła musi posiąść trzy umiejętności. Po pierwsze, musi umieć rozróżniać jednego reprezentanta od drugiego wyłącznie na podstawie posunięć drugiego gracza, dokonywanych spontanicznie lub sprowokowanych. Po drugie, musi umieć dostosowywać własne zachowanie, aby wykorzystać reprezentanta, który został rozpoznany jako gracz podatny na wykorzystanie. Po trzecie, i to może najtrudniejsze, musi być zdolna do takiego rozróżniania i eksploatacji nie popadając w zbytnie kłopoty z innymi reprezentantami. Jest to coś, czego żadna z reguł biorących pierwotnie udział w turnieju nie była w stanie dokonać.
Te wysoce efektywne reguły rozwinęły się z pogwałceniem najważniejszej zasady obowiązującej w turniejach komputerowych, mianowicie, aby być sympatycznym, czyli nigdy nie zdradzać jako pierwszy. Wspomniane efektywne reguły zawsze dopuszczają się zdrady już w pierwszym posunięciu, a niekiedy także w drugim, następnie zaś biorą pod uwagę działania drugiego gracza, aby rozeznać się co do dalszego postępowania. Reguły te miały w swoim repertuarze reakcje odpowiadające "przeprosinom" i umożliwiające podjęcie wzajemnej współpracy z większością nie dających się wykorzystywać reprezentantów, a także inne reakcje, dzięki którym mogły eksploatować reprezentantów, którzy się do tego nadawali. , , . -.: . , , , , - >-.,,,
Zapewne powinniśmy wątpić, czy politycy na Zachodzie poświęcają uwagę tym wynikom. Bardziej do rzeczy, powinniśmy pewnie zauważyć, że algorytmy genetyczne potrafią bardzo wydajnie eksploatować wielkie, nieciągłe i niedeterministyczne przestrzenie. Powinniśmy następnie stanąć nieco na uboczu i spojrzeć na ten problem z bardziej abstrakcyjnego punktu widzenia. Chociaż został on przedstawiony jako zadanie optymalizacji, w istocie rzeczy jest to przecież zagadnienie z dziedziny maszyn uczących się, gdyż strukturami podlegającymi modyfikacji są tu reguły zachowania. W rozdziale szóstym poznamy inne sposoby wykorzystania algorytmów genetycznych do uczenia się reguł postępowania w złożonych środowiskach.
4.6. Podsumowanie
W tym rozdziale przestudiowaliśmy zagadnienie powstania algorytmów genetycznych oraz ich ukształtowania się jako żywotnej metody rozwiązywania zadań poszukiwania i optymalizacji. Zajęliśmy się szczegółowo najbliższą prehistorią algorytmów genetycznych, wczesnymi osiągnięciami teoretycznymi Hollanda, dawniejszymi zastosowaniami w programach grających, symulacji biologicznej i optymalizacji, jak również kilku nowszymi zastosowaniami.
Prehistoria algorytmów genetycznych pełnajest komputerowych symulacji naturalnych procesów genetycznych. Choć niektóre z nich miały posmak optymalizacji funkcji, trzeba było przebłysku intuicji widocznego w pracach Hollanda, by przenieść wzory zaczerpnięte z przyrody na grunt sztucznych zastosowań; zaraz za osiągnięciami Hollanda postępowały pierwsze praktyczne implementacje algorytmu genetycznego dokonane przez Bagleya i Rosenberga.
;-,fe';
158
4. Niektóre zastosowania algorytmów genetycznych
Te i inne wczesne wersje algorytmu genetycznego charakteryzowały się złożonością i powszechną obecnością zawiłych operacji. Zakres tematyczny ówczesnych badań bywał zmienny, obejmowałjednak tak różne zainteresowania, jak adaptacyjne strategie gry, symulacje biologiczne, rozpoznawanie postaci i optymalizacja funkcji. Jednym słowem, okres ten moglibyśmy scharakteryzować jako erę śrutówek w algorytmach genetycznych: symulacje były przeładowane rozmaitymi operacjami i złożonymi mechanizmami, w poszukiwaniu św. Graala efektywności. Staranne eksperymenty pomyślane w celu określenia wagi poszczególnych mechanizmów były wówczas rzadkością.
Jednak, w pewnym sensie, narzędzia teoretyczne i obliczeniowe nie były jeszcze dostępne owym pionierom. Rozwinięta przez Hollanda pod koniec dziesięciolecia teoria schematów po raz pierwszy uwypukliła fundamentalne znaczenie rekombinacji strukturalnej dla osiągnięcia ukrytej współbieżności. Do tego czasu nikt z badaczy nie zdawał sobie sprawy, co właściwie przetwarza jego algorytm genetyczny, tak więc wymyślano wciąż nowe operacje, nie troszcząc się o ich wpływ na wysokowydajne "cegiełki" . Rozwój teorii szybko doprowadził do przeprowadzenia starannie przemyślanych i zaplanowanych eksperymentów z zakresu optymalizacji funkcji, które rozpoczęły się rozprawą doktorską Hollstiena i osiągnęły punkt kulminacyjny w przełomowej pracy De Jonga. De Jong oczyścił w swojej rozprawie wcześniejsze algorytmy genetyczne z większości komplikujących je elementów i dzięki temu był w stanie udokumentować względne znaczenie reprodukcji i krzyżowania. Potrafił także wykazać drugorzędną rolę mutacji w zadaniach poszukiwania genetycznego.
Po pracach De Jonga zastosowania algorytmów genetycznych uległy upowszechnieniu. Mieliśmy tu przed chwilą do czynienia z powierzchownym przeglądem takich zastosowań, zaczerpniętych z tak różnych dyscyplin, jak inżynieria, medycyna i poli-tologia. Chociaż w dziedzinie teorii i zastosowań algorytmów genetycznych pozostaje wciąż wiele do poznania, różnorodność i skuteczność istniejących algorytmów genetycznych jest powodem do optymizmu. W następnym rozdziale zapoznamy się z pewnymi postępami w technice algorytmów genetycznych, które powinny doprowadzić do dalszego wzrostu ich efektywności.
4.7. Zadania
4.1. Opracuj kod dwójkowy dla zadania Cavicchia (projektowanie zespołu detektorów dla urządzenia rozpoznającego wzorce) dopuszczający 110 detektorów i sześć pikseli na detektor dla siatki o wymiarach 25x25 pikseli. Porównaj długość tego kodu ze średnią długością kodu Cavicchia i minimalną długością kodu dwójkowego obliczoną w tekście. Porównaj także liczbę schematów dla wszystkich wymienionych kodów.
4.2. Oszacuj prawdopodobieństwa przeżycia schematu o rozpiętości 8 i całkowitej długości / przy krzyżowaniu wielopunktowym De Jonga dla CP= 1, 2, 3 ...
4.3. Oblicz prawdopodobieństwo krzyżowania w punkcie 4 przy mechanizmie krzyżowania adaptacyjnego Rosenberga dla struktury o długości /=10 i dziewięciu
l
4.7. Zadania
159
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
współczynników sprzężenia *,.= 1, 5, 6, 3, 2, 6, 7, 4, 5. Porównaj szacunkowe prawdopodobieństwa przeżycia dla schematu ***011**** przy krzyżowaniu adaptacyjnym i krzyżowaniu prostym.
Rozważmy dużą populację złożoną z punktów wybranych losowo z przedziału [0, 2]. Oblicz średni wskaźnik przystosowania w populacji dla funkcji przy-stosowania/(*)=*2. Następnie oblicz średni wskaźnik przystosowania po wy-skalowaniu, zakładając, że zastosowano skalowanie potęgowe z wykładnikiem k=],QQ5. Wyznacz także oczekiwaną liczbę kopii przy zwykłej reprodukcji dla przeciętnego (ze względu na pierwotne przystosowanie) osobnika przed i po skalowaniu.
Załóżmy, że przy metodzie nadawania rang środkowy element populacji otrzymuje jedną kopię podczas reprodukcji. Przyjmując, że najwyżej usytuowany element otrzymuje MAX kopii, wyprowadź związek między wielkością populacji i para-metrem MAX a liczbą kopii przyznawaną najniżej usytuowanemu elementowi populacji (MIN). Zakładamy liniową zależność liczby kopii od rangi. Jakie ograniczenia muszą spełniać wielkości MAX i MIN ^eśli muszą)? Przyjmując 40-bitowy blokowy zapis pozycyjny ze standaryzacją parametrów zastosowany w zadaniu regulacji pracy gazociągu (Goldberg, 1983), podaj ciąg kodowy odpowiadający następującemu zestawowi 10 parametrów U,: 0, 7,5xl05, 2x 105, 105, 0, 0, 7,5xl05,5xl05, 0, 7,5xl05. (Wartości parametrów U, mogą się zmieniać w zakresie od Umln-0 do f/max = 7,5x 105 psia2; patrz przypis 1) str. 146). Rozważmy model gazociągu z przepływem nieustalonym (Goldberg, 1983). Przyjmując, że funkcja natężenia przepływu 2jest reprezentowana przez 15 wartości <2,. (zakodowanych za pomocą ciągów trzybitowych), podaj ciąg kodowy odpowiadający fali sinusoidalnej o średniej 150 MMCFD i amplitudzie 50 MMCFD oraz okresie 140 minut. Wartości Q,. zmieniają się w granicach od gmirl=100 do 2max = 200 MMCFD i są obliczane w lO-minutowych odstępach czasu począwszy od chwili 0.
W zadaniu obróbki obrazów rentgenowskich Grefenstette'a i Fitzpatricka obraz wykonany po wstrzyknięciu środka cieniującego (100x 100 pikseli) zostaje przekształcony za pomocą odwzorowania dwuliniowego o następującej postaci (x, y - współrzędne pierwotne, x', y' - współrzędne po przekształceniu):
x = an y' = bn
ax
a3xy b3xy
Przekształcone obrazy są reprezentowane przez wartości przesunięć x i y każdego z czterech rogów obrazu (wyrażone w pikselach). Zakładając, że prawy dolny róg jest przesunięty o +3 jednostki wzdłuż osi x, a prawy górny róg jest przesunięty o +5 jednostek wzdłuż osi x i +8 jednostek wzdłuż osi y oraz że są to wszystkie niezerowe przesunięcia, oblicz współczynniki a,. i b: przekształcenia dwuliniowego. Przyjmujemy, że początek pierwotnego układu współrzędnych pokrywa się z lewym dolnym rogiem obrazu.
Wyprowadź związek między miernikiem efektywności on-line xe(t) De Jonga a średnim wskaźnikiem przystosowania populacji/avg(f).
160
4. Niektóre zastosowania algorytmów genetycznych
4.10. Załóżmy, że w zadaniu o iterowanym dylemacie więźnia decyzje o współpracy lub zdradzie są podejmowane na podstawie historii ostatnich pięciu ruchów. Opracuj kod dla strategii gry analogiczny do 70-bitowego kodu Axelroda dla strategii opartych na trzech poprzednich ruchach.
4.8. Ćwiczenia komputerowe
A. Włącz metodę wyboru losowego wg reszt bez powtórzeń (wyd. 4.1) do programu SGA.
B. Opracuj metodę selekcji wg rang, przy której osobnik przeciętny otrzymuje jedną kopię, a osobnik najlepszy - MAX kopii, a poza tym liczba kopii zależy liniowo od rangi. Zastosuj metodę wyboru losowego wg reszt po nadaniu rang i określeniu liczby kopii.
C. Opracuj procedurę krzyżowania wielopunktowego wzorowaną na metodzie De Jon-ga, z parametrem CP (liczba punktów krzyżowania).
D. Opracuj podprogram statystyczny do śledzenia odchylenia standardowego przystosowania osobników w populacji, a następnie procedurę skalowania a-obcinającego.
E. Opracuj wariant elementarnego algorytmu genetycznego z populacją mieszaną, zależny od współczynnika wymiany G. Zaimplementuj metodę ścisku wzorując się na De Jongu. Przetestuj program na przykładzie funkcji wielomodalnej ^ak F5) i porównaj wyniki otrzymane w eksperymentach z metodą ścisku i bez niej.
F. Porównaj i omów alternatywne metody selekcji.
G. Porównaj i omów alternatywne metody skalowania.
H. Porównaj i omów alternatywne metody nadawania rang.