Rozdział 5
Techniki i operacje zaawansowane
W kilku początkowych rozdziałach tej książki zajmowaliśmy się tylko elementarnymi wersjami algorytmu genetycznego, opierającymi się głównie na współdziałaniu trzech operacji: reprodukcji, krzyżowania i mutacji. Skupiając zainteresowanie na tych mechanizmach, byliśmy w stanie dostrzec, tak od strony teoretycznej jak i empirycznej, centralną rolę sztucznej selekcji i zrandomizowanej, uporządkowanej rekombinacji w niebiologicznych procesach poszukiwania genetycznego. Jednak w zapale do zachowania prostoty zaniedbaliśmy kilka interesujących zjawisk i mechanizmów, które występują w przyrodzie. W tym rozdziale spróbujemy wydobyć i rozważyć ich rolę, mając na uwadze umocnienie odporności przejawianej przez elementarne algorytmy genetyczne. Zakres i głębokość tych rozważań będą z konieczności ograniczone aktualnym stanem wiedzy na temat mechanizmów naturalnych oraz tym, co udało się dotąd wypraktykować. Mimo tych ograniczeń, rozpoznanie, analiza i implementacja zaawansowanych technik i operacji to najbardziej owocny kierunek dalszego udoskonalania algorytmów genetycznych.
Omówimy tu niskopoziomowe mechanizmy, takie jak dominowanie, inwersja, duplikacja wewnątrzchromosomowa, delecja, translokacja i segregacja. Poprzez mechanizmy działające na poziomie populacji, jak migracja, bariery reprodukcyjne i funkcje współudziału uzyskamy efekty podobne do zjawisk wypełniania nisz ekologicznych i specjacji. Omówimy także związane z tym prace z dziedziny optymalizacji wielokryte-rialnej. Prócz tego zajmiemy się operacjami genetycznymi wzbogaconymi wiedzą [knowledge-augmented] i innymi metodami wykorzystującymi informację specyficzną dla zadania. Na zakończenie wyliczymy niektóre spośród ostatnich usiłowań dostosowania algorytmów genetycznych do wyłaniającej się właśnie architektury równoległych systemów komputerowych.
162
. 5. Techniki i operacje zaawansowane
5.1. Diploidalnyaparat genetyczny. Dominowanie i maskowanie _
Czytelnicy oczytani nieco w genetyce głowią się zapewne, dlaczego do tej pory ignorowaliśmy kwestię diploidalności (podwójnego zestawu chromosomów) i dominowania (ważnego rodzaju zależności fenotypu od genotypu). Czyż bowiem najbardziej elementarne podręczniki genetyki nie rozpoczynają się od omówienia doświadczeń Mendla z grochem i jakiegoś objaśnienia zjawiska dominowania? Otóż pominięcie to miało na celu podkreślenie zasadniczego znaczenia selekcji i rekombinacji. Tym niemniej, fakt istnienia tylu odnoszących powodzenie diploidalnych i poliploidalnych organizmów stawia przed nami pytanie, czy mechanizmy te mogłyby być skutecznie zastosowane w nie-biologicznych zagadnieniach poszukiwania genetycznego. W tym punkcie zapoznamy się z zasadami funkcjonowania genotypu diploidalnego i dominowania, w celu wyjaśnienia ich roli w osłanianiu alternatywnych rozwiązań przed zbyt niszczącym działaniem selekcji.
Dotychczas rozważaliśmy jedynie najprostszy rodzaj genotypów spotykanych w przyrodzie - o haploidalnej liczbie chromosomów. W modelu tym pojedynczy ciąg kodowy zawiera całą informację istotną dla rozpatrywanego zagadnienia. Mimo że przyroda zna wiele organizmów haploidalnych, większość z nich reprezentuje raczej nieskomplikowane formy życia. Wydaje się, że ilekroć przyroda chciała wytworzyć wyższe postaci życia roślinnego lub zwierzęcego, musiała polegać na bardziej skomplikowanej strukturze genetycznej - genotypach o diploidalnej liczbie chromosomów. Genotyp w postaci diploi-dalnej składa się z jednej lub więcej par chromosomów (zwanych chromosomami homologicznymi], każdy z których przenosi informację służącą tym samym funkcjom. Na pozór taka redundancja może się wydawać zbędna i trudna do pojęcia. Po co przechowywać pary genów służących tej samej funkcji? A jeśli dwa geny z jednej pary wyznaczają różne „wartości" funkcji, to wjaki sposób przyroda decyduje, który z nich dopuścić do głosu? Aby udzielić odpowiedzi na te pytania, rozważmy diploidalną strukturę chromosomową, w której poszczególne litery alfabetu reprezentują różne allele (warianty genów):
AbCDe aBCde
Każda litera na danej pozycji (locus) reprezentuje jeden allel; dwie odmiany tej samej litery (wielka i mała) odpowiadają przeciwstawnym allelom (odmianom genu). W przyrodzie każdy z alleli mógłby warunkować odmienną charakterystykę fenotypową (lub mieć pewien cząstkowy wpływ na jedną lub więcej charakterystyk). Na przykład allel B mógłby warunkować brązową barwę oczu, a allel b - niebieską. Choć opisana zasada nie odbiega wiele od obowiązującej w przypadku haploidalnym, jedna różnica jest wyraźnie widoczna. Ponieważ mamy teraz parę genów warunkujących tę samą cechę, musi istnieć mechanizm decydujący, który z dwóch wariantów wybrać, gdyż fenotyp nie może mieć - na przykład -jednocześnie brązowych i niebieskich oczu ^esli nie dopuszczamy, jak to się niekiedy dzieje w naturze, możliwości występowania form pośrednich; tym jednak nie będziemy się tu zajmować).
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
163
Podstawowy mechanizm służący do rozstrzygania takich konfliktów genetycy nazywają dominowaniem. Zauważono, żejeden z alleli (allel dominujący) zajmujących ten sam locus ma pierwszeństwo przed odmianą alternatywną (allelem recesywnym). Dokładniej, dany allel jest dominujący, jeżeli ulega ekspresji (przejawia się w fenotypie), występując w parze z drugim allelem. Wracając do przykładu, jeżeli założymy, że wielkie litery są dominujące, a małe - recesywne, to ekspresję alleli można wyrazić następująco:
AbCDe
ABCde
ABCDe
Gen dominujący przejawia się w każdym przypadku, a gen recesywny - tylko gdy występuje w parze z drugim genem recesywnym. W języku genetyków mówi się, że gen dominujący przejawia się zarówno w stanie heterozygotycznym (mieszanym, Aa^A), jak i homozygotycznym (czystym, CC^C), natomiast allel recesywny przejawia się tylko w stanie homozygotycznym (ee^e).
Przedstawione reguły wydają się dość przejrzyste. Na bardziej abstrakcyjnym poziomie możemy myśleć o dominowaniujako odwzorowaniu genotyp-fenotyp lubjako operacji redukcji genotypu. Jeślijednak będziemy próbowali nadal zgłębiać sens tych rozwiązań, muszą się one wydać nader dziwaczne. W jakim celu przyroda najpierw dubluje informację przenoszoną za pośrednictwem genotypu, aby ją potem zredukować do połowy, gdy przychodzi do jej wykorzystania? Wygląda to pozornie na rozrzutność i niepotrzebną żmudę; jednak przyroda nie jest utracjuszem, ani nie ulega zachciankom czy kaprysom. Muszą więc istnieć istotne powody nadmiarowości wynikającej ze struktury diploidalnej genotypu oraz zjawiska maskowania czy osłony będącego rezultatem dominowania.
Diploidalność oraz dominowanie od dawna były przedmiotem studiów genetycznych; przedstawiono liczne teorie mające wyjaśnić ich rolę. Z naszego punktu widzenia najbardziej interesujące są hipotezy, według których podwójny zestaw chromosomów stanowi mechanizm do zapamiętywania tych alleli oraz ich kombinacji, które w przeszłości okazały się pożyteczne, a dominowanie osłaniaje przed szkodliwym oddziaływaniem selekcji w aktualnie niesprzyjającym środowisku. Z przyrodniczego punktu widzenia można zrozumieć potrzebę takiej rozproszonej, długoterminowej pamięci oraz środków chroniących tę pamięć przed nagłym zniszczeniem. W toku ewolucji życia na Ziemi planeta nasza podlegała wielu zmianom środowiskowym. Od wysokich do niskich, i znów umiarkowanych temperatur, od ciemności do pełni światła i jakiegoś pośredniego oświetlenia - zmiany dokonywały się dramatycznie i gwałtownie. Najbardziej efektywne okazały się organizmy, które były zdolne do szybkiej adaptacji do zmieniających się warunków. Zwierzęta i rośliny o strukturze diploidalnej lub poliploidalnej były najbardziej zdolne do przeżycia, gdyż ich aparat genetyczny nie zapominał łatwo lekcji odebranych przed poprzednimi zmianami środowiska. Nadmiarowa pamięć genetyczna organizmów diploidalnych umożliwia jednoczesne przechowywanie różnych rozwiązań tego samego problemu, podczas gdy ujawnia się tylko jedno określone rozwiązanie. Dzięki temu stare nauki nie ulegają na zawsze zapomnieniu, a dominowanie i jego przemiany umożliwiają okazjonalne przypomnienie i sprawdzenie przydatności dawno wyuczonych lekcji.
164
. 5. Techniki i operacje zaawansowane
Znakomitym przykładem tej długoterminowej pamięci genetycznej mogą być przemiany w równowadze populacyjnej zaobserwowane w Wielkiej Brytanii w okresie rewolucji przemysłowej u pewnego gatunku ćmy". Pierwotnie dominująca forma tego motyla miała białe skrzydła z małymi czarnymi plamkami. Przed rewolucją przemysłową ubarwienie takie zapewniało skuteczny kamuflaż wobec ptaków i innych naturalnych wrogów w występujących w siedlisku ćmy, tj. wśród drzew pokrytych porostami. W połowie dziewiętnastego stulecia w okolicach miast przemysłowych zaczęto chwytać osobniki należące do odmiany ciemno ubarwionej. Staranne doświadczenia przeprowadzone przez Kettlewella (Berry, 1965) wykazały, że nakrapiana wersja ubarwienia zapewniała korzyści w warunkach pierwotnych, podczas gdy odmiana melaniczna (ciemna) okazała się korzystna w środowisku przemysłowym, w którym porosty pokrywające pnie drzew wyginęły z powodu zanieczyszczeń. Okazało się, że ciemny kolor skrzydeł był warunkowany przez pojedynczy dominujący gen, co wskazuje, że nastąpiła zmiana w dominowaniu. Kiedy równowaga przesunęła się w stronę odmiany ciemno ubarwionej, stała się ona formą dominującą, natomiast odmiana nakrapiana „przeszła do rezerwy". Zwróćmy uwagę, że forma melaniczna nie była nowym wynalazkiem; nie nastąpiła tu żadna szczęśliwa mutacja, która w magiczny sposób wymyśliła potrzebną zmianę. Przeciwnie, forma ciemna powstałajuż wcześniej, być możejako odpowiedź biologiczna na lasy, w których porosty w sposób naturalny nie występowały. Gdy produkty uboczne przemysłu spowodowały zanik porostów, forma melaniczna uzyskała przewagę selekcyjną i stała się postacią dominującą. Mając w zanadrzu alternatywne rozwiązanie, ćma bez trudu zaadaptowała się w krótkim czasie do nowych warunków zmieniającego się środowiska.
Przykład ten pokazuje, w jaki sposób diploidalność i dominowanie stwarzają osłonę dla alternatywnych rozwiązań przed nadmierną selekcją. Widzimy także, że dominowanie nie jest stanem ustalonym raz na zawsze. Biolodzy wysunęli i udowodnili hipotezę, że samo dominowanie podlega ewolucji. Inaczej mówiąc, dominowanie lub niedo-minowanie określonego allelu jest również warunkowane genetycznie. Szczegółowe aspekty biologiczne tego zagadnienia można znaleźć w pracy Fishera (1958) na temat ewolucji dominowania. Tutaj omówimy niektóre modele tych mechanizmów używane do celów poszukiwania genetycznego, aby dowiedzieć się, jak rozwiązano tam problemy reprezentacji struktury genetycznej, operacji dominowania oraz ewolucji tej ostatniej.
5.1.1. Diploidalnośćidominowaniewalgorytmachgenetycznych.
Zarys historyczny__________________________________________________________
W niektórych najwcześniejszych zastosowaniach praktycznych algorytmów genetycznych używano już struktury diploidalnej i posługiwano się mechanizmem dominowania. W rozprawie Bagleya para chromosomów homologicznych zostaje odwzorowana na określony fenotyp za pośrednictwem zmiennego wzorca dominacji, zakodowanego jako część samego chromosomu (Bagley, 1967, str. 136):
'' Ćma krępaka, Biston betularia Q)rzyp. tlum.).
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie.
165
Każdy aktywny locus zawiera prócz informacji określającej parametr, z którym jest on związany i konkretnej wartości tego parametru, również stopień dominowania [dominance value\. Algorytm po prostu wybiera w każdym z loci allele o największym stopniu dominowania. W przeciwieństwie do sytuacji spotykanych w przyrodzie, która dopuszcza niecałkowite dominowanie (czego wynikiem mogą być np. plamiste oczy), wymagamy tu, aby został wybrany dokładnie jeden z homologicznych alleli. Proces podejmowania decyzji w sytuacjach remisowych jednakowe stopnie dominowania) uwzględnia efekty pozycyjne i jest cokolwiek złożony, trzeba go więc będzie naszkicować nieco dokładniej. Jeden z dwóch chromosomów zostaje arbitralnie wybranyjako „kluczowy", po czym prze- , gląda się jego zawartość w kierunku od lewa na prawo. Przy każdorazowym napotkaniu aktywnego locus bada się zawartość homologicznego locus w drugim chromosomie. Następuje porównanie stopni dominowania i wybór allelu odpowiadającemu wyższemu stopniowi dominowania. Jeżeli stopnie dominowania są jednakowe, rozstrzygnięcie zależy od chromosomu kluczowego. To znaczy, sprawdza się najbliższy aktywny locus położony na lewo od rozpatrywanej pozycji w chromosomie kluczowym. Jeżeli jest on dominujący, to bieżący locus w chromosomie kluczowym zostaje uznany za dominujący, w przeciwnym razie dominuje homolog. Jeżeli badany locus zajmuje pierwszą aktywną pozycję w chromosomie kluczowym, to dominuje locus kluczowy.
Wprowadzenie stopnia dominowania dIa każdego genu umożliwiło adaptację tego modelu w kolejnych pokoleniach. Niestety, jak stwierdził Bagley, stopnie dominowania okazywały tendencję do wczesnej fiksacji, pozostawiając w ten sposób określanie dominowania w rękach cokolwiek skomplikowanego i dowolnego mechanizmu rozstrzygania remisów. Co gorsza, Bagley wyjął stopnie dominowania spod działania mechanizmu mutacji, przyspieszając jeszcze w ten sposób ich przedwczesną zbieżność. W dodatku Bagley nie dokonał porównania wariantu haploidalnego z diploidalnym, a we wszystkich rozpatrywanych przez niego przypadkach środowisko pozostawało stacjonarne. W rezultacie fiksacja stopni dominowania na wszystkich pozycjach doprowadziła do ustalenia się arbitralnego, przypadkowego mechanizmu dominowania, uniemożliwiając wyciągnięcie przekonywujących wniosków.
Ukierunkowane biologicznie badania Rosenberga (1967) obejmowały diploidalny model aparatu genetycznego; jednak ze względu na szczegółowość, z jaką podszedł on do modelowania procesów biochemicznych, efekt dominowania nie był osobno rozpatrywany. Wszelkie efekty związane z dominowaniem wynikały u niego z obecności lub nieobecności określonego enzymu. Enzym mógł hamować lub ułatwiać zachodzenie reakcji biochemicznej, wpływając ten sposób na pewien wynik na poziomie fenotypu.
Studium Hollstiena (1971) objęło model diploidalny oraz ewoluujący mechanizm dominowania. W istocie Hollstien opisał dwa proste, ewoluujące mechanizmy dominowania, a następnie zastosował najprostszy z nich do badań nad optymalizacją funkcji. W pierwszym przypadku zamiast pojedynczego genu binarnego, używano dwóch: genu modyfikatora i genu funkcyjnego. Gen funkcyjny mógł przyjmować normalne wartości 0 i 1 i był używany w zwykły sposób do kodowania pewnego parametru. Gen modyfikator przyjmował wartości M lub m. Przy tym rozwiązaniu allel 0 dominował, jeżeli w przynajmniej jednym z homologicznych loci modyfikatorowych występował allel M.
166
5. Techniki i operacje zaawansowane
W efekcie otrzymywało się wzorzec dominacji taki, jak na rys. 5.1. Hollstien zorientował się, że cały mechanizm można uprościć, wprowadzając zamiast genów modyfikatorów trzy allele dla każdego z loci. W takim modelu triallelicznym alfabet genetyczny składał się z symboli 0, 1 i 2, przy czym 2 pełniło rolę „dominującego 1", a 1 - rolę „recesyw-nego 1". Odpowiedni wzorzec dominacji został pokazany na rys. 5.2. Cały mechanizm można podsumować stwierdzeniem, że zarówno 1 jak i 2 przejawiają się jako 1, ale 2 dominuje nad 0 i 0 dominuje nad 1. Holland (1975) przeanalizował później zachowanie takiego samego modelu triallelicznego w warunkach stacjonarnych, choć wprowadził nieco bardziej przejrzyste oznaczenia {0, 1„, 1} w miejsce Hollstienowskich {0, 1, 2}.
OM Om
1M 1 m
OM
Om
1 M
Rys. 5.1. Wzorzec dominacji z genem modyfikatorem. Za Hollstienem (1971)
o i
Rys. 5.2. Wzorzec dominacji w modelu triallelicznym. Za Hollstienem (1971)
Model trialleliczny Hollstiena-Hollanda łącząc oba rodzaje informacji (o dominowaniu i allelu) na pojedynczej pozycji jest najklarowniejszą i najprostszą z metod zaproponowanych do tej pory dla celów poszukiwania genetycznego. Przy tej metodzie allel o wyższej wartości przystosowawczej staje się dominujący, osłaniając w ten sposób wariant recesywny. Potrzeba do tego minimum dodatkowej pamięci (pół bitu na locus}, a co więcej zmiana dominowania może być bez trudu dokonywana za pośrednictwem operacji typu mutacyjnego, przekształcającej 2 w 1 (1 w 1„ według notacji Hollanda) i odwrotnie. Mimo przejrzystości tego modelu wyniki otrzymane przez Hollstiena w związku z wprowadzeniem diploidalności i dominowania były niejednoznaczne. Chociaż w symulacjach oznaczonych Breed Type III różnorodność populacji (mierzona wa-
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
167
riancją populacji) utrzymywała się na wyższym poziomie niż w przypadku symulacji haploidalnych, nie zaobserwowano jednak istotnej poprawy średniej czy końcowej efektywności. Może się to wydawać dziwne dopóty, dopóki nie zdamy sobie sprawy z faktu, że Hollstien posługiwał się jedynie funkcjami stacjonarnymi. Jeśli sens diploidalności--dominowania polega na osłonie, to istotnych różnic w zachowaniu haploidalnych i dip-loidalnych algorytmów genetycznych powinniśmy się spodziewać wtedy, kiedy środowisko ulega przemianom w czasie. W tym świetle jest rzeczą zastanawiającą, że nie przestudiowano takich zmian w związku z omawianym modelem.
Brindle (1981) przeprowadziła eksperymenty z pewną liczbą wariantów dominowania w kontekście optymalizacji funkcji. Niestety, funkcje i kody, których używała w badaniach, zostały później zakwestionowane. Co więcej, zignorowała ona poprzednie prace na temat modeli dominacji i diploidalności, a pewne opracowane przez nią modele nie miały podstaw teoretycznych ani precedensów biologicznych.
•• *|
Brindle rozważała sześć następujących wariantów dominowania:
1) dominowaniestałe,globalne,określonelosowo,
2) dominowaniezmienne,globalne; ;«,
3) dominowanie zmienne, globalne, określone deterministycznie;
4) wybór losowego chromosomu;
5) dominowanie lepszego chromosomu;
6) haploidaIna kontrola dominowania adaptacyjnego diploidów.
W przypadku dominowania stałego, globalnego, określonego losowo, dominowanie alleli zostaje określone na początku eksperymentu, raz na zawsze dla wszystkich loci. Wzorzec dominacji odpowiada serii rzutów rzetelną monetą. Allel dominujący przejawia się w stanie heterozygotycznym lub homozygotycznym, natomiast allel recesywny - tylko w stanie homozygotycznym.
W przypadku dominowania zmiennego, globalnego, określa się prawdopodobieństwo dominowania danego allelu (0 lub 1) w określonym locus. Jest ono równe frekwencji tego allelu w aktualnej populacji. Po obliczeniu frekwencji zer i jedynek w każdym z loci, o ekspresji allelu będącego w stanie heterozygotycznym decyduje wynik odpowiedniej próby Bernoulliego.
W następnym wariancie (dominowanie zmienne, globalne, określone deterministycznie) wyznacza się, tak jak poprzednio, frekwencje zer i jedynek dla każdego z loci; jednak tym razem o ekspresji decyduje większość i allel mający większą frekwencję w populacji zostaje uznany za dominujący.
W wariancie z wyborem losowego chromosomu tworzy się (drogą kolejnych rzutów beztendencyjną monetą) losowy genotyp, a wszystkie jego allele zostają uznane za dominujące.
W wariancie z dominowaniem lepszego chromosomu chromosom o wyższym wskaźniku przystosowania (w parze chromosomów homologicznych) zostaje uznany za dominujący.
W ostatnim modelu trzeci dodatkowy chromosom (haploid) przenosi adaptacyjny wzorzec dominacji, określający ekspresję alleli w normalnej parze diploidalnej (Brindle, 1981, str. 115):
!^HBMttMr*
""
168
5. Techniki i operacje zaawansowane
Model haploidalny Średnia dla pokolenia
wu -80 -70 - Jl ; F m i • • 1 H J , r , F • r p 1
ao -ff
o> TŁ
c P
a so-
0 1
U)
2 40 -
w
L 30-
20-
to -
0 - -• i — i P t—i m -ii • hH • *~ • ł— < P ł-H • -t • -H • — 1 • —i P -H •»-
100
200 Nr pokolenia
300
40P
Rys. 5.3. Niestacjonarna wersja zagadnienia plecakowego. Średnie wartości rozwiązań dla modelu haploidalnego. (Goldberg i Smith, 1987)
0)
o tÓ
e-
0_
70 -
.2 60 -
g
S 50 -
40 -30 -20 -10 -
Model haploidalny Najlepsze rozwiązanie w pokoleniu
100
300
400
200 Nr pokolenia
Rys. 5.4. Niestacjonarna wersja zagadnienia plecakowego. Najlepsze rozwiązania dla modelu haploidalnego. (Goldberg i Smith, 1987)
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
169
Najlepszą metodą uzyskania wzorca dominacji, który przynosiłby największe korzyści or-ganizmowi,jest pozostawienie algorytmowi genetycznemu zadania wytworzeniatego wzorca w sposób dynamiczny. Każdy osobnik w populacji jest wyposażony w trzeci chromosom, który w fazie ewaluacji służy jako wzorzec dominacji dla tego osobnika. Podczas cyklu reprodukcyjnego chromosom ten zachowuje się jak organizm haploidalny, rekombinując w fazie kojarzenia z analogicznym chromosomem drugiego z rodziców. Podlega on mutacji z taką samą częstością, jak chromosomy homologiczne. [...] Dobre wzorce dominacji powinny rozwijać się równolegle z dobrymi organizmami.
Jest to najbardziej naturalny spośród modeli przyjętych przez Brindle. Podobnie jak wcześniejsze propozycje Hollstiena (1971) i Bagleya (1967), metoda ta opiera się na adaptacyjnym wzorcu dominacji; jednak Brindle całkowicie oddzieliła wzorzec dominacji (geny modyfikatory) od normalnego chromosomu (genów funkcyjnych). Pod względem biologicznym jest to niezrozumiałe. Genotypy występujące w przyrodzie nie są w połowie diploidalne, a w połowie haploidalne. Ponadto wydaje się, że gen modyfikujący powinien być dość ściśle związany z genem funkcyjnym, tworząc trudny do rozbicia (na skutek krzyżowania) blok. Separacja, którą narzuciła Brindle, skutecznie likwiduje sprzężenia między wzorcem dominacji a genami funkcyjnymi.
Są także i inne zastrzeżenia do jej modeli. Dwa z nich wymagają użycia informacji globalnej do podejmowania decyzji na szczeblu lokalnym. Już wcześniej mieliśmy okazję kwestionować pomysł algorytmu genetycznego na metapoziomie, gdyż zakładał on posługiwanie się informacją globalną. Te same zastrzeżenia należy zgłosić wobec używania informacji globalnej do lokalnego decydowania o dominowaniu. Musimy jeszcze raz postawić pytanie, w jaki sposób informacja taka miałaby być dostępna w przyrodzie. Choć może się to wydawać puryzmem genetycznym, nie chodzi tu wcale o ślepe naśladownictwo przyrody dla samego siebie. Główny urok naturalnych i sztucznych mechanizmów genetycznych polega na tym, że osiągają one globalne skutki poprzez działania czysto lokalne. Jeśli choć raz wprowadzimy tę czy inną operację globalną, utracimy bezpowrotnie tę pociągającą właściwość. A nie jest to bez znaczenia, jeśli ostatecznie zależy nam na uzyskaniu efektywnych implementacji tych metod dla komputerów o architekturze równoległej.
W swej rozprawie Brindle porównała drogą symulacyjną sześć modeli; ponieważ jednak użyła niewłaściwego materiału do badań oraz rozpatrywała jedynie funkcje stacjonarne, zjawiska diploidalności i dominacji nie zostały przez nią skutecznie zbadane.
W nieco nowszych pracach (Goldberg i Smith, 1987; R. E. Smith, 1987, 1988), główną uwage poświęcono roli dominowania i diploidalności jako struktur i mechanizmów maskowania. Smłth i ja porównaliśmy haploidalny AG, diploidalny AG ze stałym wzorcem dominacji (1 dominuje nad 0) oraz diploidalny trialleliczny AG Hollstiena--Hollanda pod względem efektywności, na przykładzie tzw. ślepego zagadnienia plecakowego. W zwykłym zagadnieniu plecakowym chodzi o maksymalizację łącznej wartości przedmiotów załadowanych do plecaka, przy zachowaniu jednego lub więcej więzów wagowych. Matematycznie zadanie formułuje się w zwięzły sposób następująco:
v,*,, gdzie*,e{0,l} pod warunkiem, że Xw,x,
'c
0!
co O OT
Model diploidalny prosty Najlepsza rozwiązanie w pokoleniu
100
200
3OO
400
Nr pokolenia
Rys. 5.6. Niestacjonarna wersja zagadnienia plecakowego. Najlepsze rozwiązania dla modelu diploidalnego ze statym wzorcem dominacji. (Goldberg i Smith, 1987)
T
t
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
171
Model trialleliczny Średnia dla pokolenia
300
400
100 200
Nr pokolenia
Rys. 5.7. Niestacjonarna wersja zagadnienia plecakowego. Średnie wartości rozwiązań dla modelu diploidalnegotriallelicznego. (Goldberg i Smith, 1987)
.2
<0
v>
o v>
Model trialleliczny Najlepsze rozwiązanie w pokoleniu
1
100
3OO
400
2OO
Nr pokolenia
Rys. 5.8. Niestacjonarna wersja zagadnienia plecakowego. Najlepsze rozwiązania dla modelu diploidalnegotriallelicznego. (Goldberg i Smith, 1987)
172
5. Techniki i operacje zaawansowane
W wersji „ślepej" algorytm nie zna, oczywiście, struktury zadania, wartości v, czy wag Wj. W tym przypadku zadanie zostało dodatkowo utrudnione przez wprowadzenie więzów będących periodyczną funkcją czasu: W(t)e [W0, Wt}, przy czym co Tl>erirxi pokoleń wartość funkcji zmienia się na przeciwną. Na rysunkach 5.3-5.6 porównano haploidalny AG z prostym diploidalnym AG. Haploidalny AG nie był w stanie dostosować się do oscylacji, natomiast prosta wersja diploidalna potrafiła za nimi do pewnego stopnia nadążyć. Wykonano również eksperymenty z algorytmem triallelicznym Hollstiena-Hollanda. Jak można było się spodziewać, otrzymane wyniki przewyższyły w istotnym stopniu rezultaty osiągnięte przy użyciu stałego wzorca dominacji. Na rysunkach 5.7 i 5.8 pokazano średnie i najlepsze w pokoleniu rozwiązania omawianego zadania. Ponieważ model trialleliczny umożliwia ewolucję wzorca dominacji na każdej pozycji, populacja jest dzięki temu zdolna do szybszej i pełniejszej adaptacji niż w przypadku stałego wzorca dominacji lub struktury haploidalnej.
5.1.2. Analiza diploidalności i dominowania w algorytmach genetycznych ____
Dowody empiryczne na rzecz struktury diploidalnej i mechanizmu dominowania w algorytmach genetycznych zaczynają układać się w bardziej zrozumiałą całość. O ile dawniej uważano diploidalność i dominowanie za magiczne lekarstwo na wszystkie niedomagania algorytmów genetycznych, o tyle teraz główną uwagę kieruje się na ich rolę związaną z zabezpieczeniem niegdyś pożytecznych schematów przed niszczącym działaniem selekcji. Aktualnie zaczęto studiować te zagadnienia w kontekście zadań niestacjonarnych i można przypuszczać, że przyszłe badania potwierdzą tę rolę. Za dowodami empirycznymi powinna podążyć analiza teoretyczna. W tym punkcie pokażemy, jak działa mechanizm przedłużający życie aktualnie słabszych schematów, będący efektem współdziałania diploidalności i dominowania. Zobaczymy również, że dzięki takiemu rozwiązaniu można zapewnić określony poziom różnorodności populacji przy mniejszej częstości mutacji.
Chcąc zrozumieć działanie wspomnianego mechanizmu, rozważmy najpierw, jaki wpływ wywiera on na rozprzestrzenianie się schematów. W rozdziale drugim otrzymaliśmy następujący związek między liczbą reprezentantów schematu H w następnym pokoleniu (m(H, t+ 1)) a liczbą tychże w pokoleniu bieżącym (m(H, ?))•'
m(H, t+\) > m(H, t) SL ] _
_ o(H)pr
W powyższej nierówności pc i pm oznaczają, odpowiednio, prawdopodobieństwa krzyżowania i mutacji,f(ff) — średni wskaźnik przystosowania schematu,/- średni wskaźnik przystosowania populacji, d(ff) - rozpiętość schematu (odległość między skrajnymi pozycjami ustalonymi) i o(H} - rząd schematu (liczbę ustalonych pozycji). Nierówność ta pozostanie w mocy po dodaniu diploidalności i dominowania,jezeli uwzględnimy w niej wpływ dominowania i zjawiska ekspresji alleli na wielkość średniego przystosowania
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
173
schematu/(H). Różnica będzie najlepiej widoczna, jeżeli rozróżnimy pojęcia schematu rzeczywistego H i schematu ujawnionego He. Innymi słowy, rzeczywisty schemat H może się przejawiać Iub nie, w zależności od swego statusu dominacyjnego oraz od aktualnego partnera homologicznego. Wymaga to wprowadzenia następującej modyfikacji do naszej nierówności: ,Ł
m(H, t+ 1) > m(H, t) %» [l - Pe ^- - o(H}Pm\
f
Wszystko pozostało po staremu, z wyjątkiem tego, że średni wskaźnik przystosowania schematu H, f(H}, został zastąpiony przez średni wskaźnik przystosowania schematu ujawnionego He, f(He). W przypadku schematu całkowicie dominującego średni współczynnik przystosowania zawsze równa się średniemu współczynnikowi przystosowania schematu ujawnionego: < , i • •
/tfO=/(ff,) -V . , , -
: ' ^ ' . ! *f i «i
W przypadku schematu dominowanego chcielibyśmy, oczywiście, aby średni współczynnik schematu ujawnionego nie ustępował średniemu współczynnikowi schematu rzeczywistego:
f(He)>f(ff) •,. ..' -...- ,..-• • ..-...- .,•..,.,.;,:..'.
Sytuacja taka jest najbardziej prawdopodobna, kiedy wzorzec dominacji ma możliwość ewoluowania, jak sugerowaliśmy wcześniej. Jeśli to nastąpi, to aktualnie szkodliwy, zdominowany schemat nie będzie narażony na odsianie wskutek selekcji w takim stopniu, jak w analogicznym przypadku haploidalnym. W ten właśnie sposób diploidalność i dominowanie chronią schematy będące aktualnie w niełasce.
Aby nadać naszemu rozumowaniu bardziej wymierny charakter, rozważmy prosty przykład, w którym mamy do czynienia z dwoma alternatywnymi, konkurującymi schematami, jednym dominującym i jednym recesywnym. Odpowiada to realnie dwóm al-lelom na tej samej pozycji lub dwóm schematom wielopozycyjnym, które „zmonopolizowały" określony podzbiór pozycji. W obu przypadkach zakładamy, że konkurent dominujący przejawia się zarówno w stanie heterozygotycznym, jak i homozygotycznym, natomiast konkurent recesywny przejawia się tylko w stanie homozygotycznym. Przekształcając równanie propagacji schematów" możemy wyznaczyć frekwencje P' alleli recesywnych w kolejnych pokoleniach t. Jeśli założymy, że istnieją tylko dwa konkurujące schematy, przy czym forma dominująca charakteryzuje się stałym wskaźnikiem średniego przystosowania^,, a forma recesywna - odpowiednio/r, to wówczas oczekiwana frekwencja recesywów w następnym pokoleniu wyniesie (Goldberg i Smith, 1987):
11 W celu uproszczenia dalszej analizy autor zastępuje wyprowadzoną wcześniej nierówność równaniem (przyp. ttum.).
174
. 5. Techniki i operacje zaawansowane
Pt+] = P'K
P' + r(] ~P') (1 - r)P' • P' + r
gdzie r=ft//fr, a A"jest współczynnikiem strat związanych z krzyżowaniem i mutacją.
Analogiczny związek można wyprowadzić w przypadku haploidalnym, w którym szkodliwy wariant (recesyw) nie jest nigdy maskowany:
K • .....v ; ••. ' - ' '•'••'''" "!"';;"'
pi+[=p
P' + r(\ -P')
Na rysunku 5.9 wykreślono zależność stosunku frekwencji P'+I/P' od frekwencji P' dla wariantów haploidalnego i diploidalnego. Najważniejszym wnioskiem, jaki można wyciągnąć z tych wykresów, jest to, że przy porównywalnych frekwencjach alleli wariant haploidalny odsiewa zawsze mocniej (mniejszy jest stosunek frekwencji) aniżeli wariant diploidalny. Oczywiście, nie oznacza to, że wariant diploidalny działa mniej efektywnie. W istocie, w przypadku diploidalnym częstość wyboru recesywu podczas reprodukcji jest niewielka (proporcjonalna do P2) °. Dzięki temu przydatne niegdyś rozwiązania zostają zachowane, aby pewnego dnia podjąć walkę, bez nadmiernej propagacji i bez nadmiernego odsiewu. Podobne wnioski można wysnuć, badając historie frekwencji recesy-wów, zobrazowane na rys. 5.10. Analogiczne wyniki dla modelu triallelicznego podaje Smith (1988).
Przeprowadzona wyżej analiza dowodzi jasno istnienia długoterminowej pamięci, będącej skutkiem diploidalności i dominowania. Z uwagi na to możemy się spodziewać, że mutacja będzie odgrywać jeszcze mniejszą rolę w przypadku algorytmów genetycznych stosujących to rozwiązanie. Holland (1975) przedstawił analizę wymagań stawianych wobec mutacji w warunkach populacji stacjonarnej, porównując przypadki struktur diploidalnych i haploidalnych2'.
Można pokazać, że dla struktur haploidalnych związek między frekwencją ^'+l określonego allelu w następnym pokoleniu a jego frekwencją P' w bieżącym pokoleniu jest dany wzorem
3'+l _
(\-Z}P'+pm(\-P')-pmP>
Występuje tu suma trzech wyrazów - składnika wynikającego z reprodukcji, składnika reprezentującego zysk z tytułu mutacji oraz składnika reprezentującego stratę z tytułu mutacji. Wielkość e(/) reprezentuje względne straty będące skutkiem działania innych operacji. W populacji stacjonarnej mamy P'+l =P'=PSX. Wyznaczając stąd PM otrzymujemy
P.. =
Pm
11 Chodzi o formę homozygotyczną Q>nyp. tlum.).
2) Analiza ta dotyczy przypadku dwóch przeciwstawnych alleli rzyp. tłum.).
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
175
1,0000
0,9000
.2
I J
J2 o,aooo -
o
s
I
o. a>
0,7000 -
0,9000 -
0,6000
0,OODOOB+00
fi=2
6,OOOOOB-01 1,00000>+0
Frekwencja w populacji graniczny « haploidalny R=2
Rys. 5.9. Współczynnik zachowania p'+'/P' w zależności od frekwencji P' dla modelu haploidalnego (r = 2), diploidalnego (r = 2) \ granicznego diploidalnego (r=). Za Goldbergiem i Smithem (1987)
0,6000
o,oooo
haploidalny R=2
10
eo 30
Numer ookolenia diploidalny R=2
graniczny diploidalny
Rys. 5.10. Frekwencja Pw zależności od pokolenia /dla modelu haploidalnego (r = 2), diploidalnego (r = 2) i granicznego diploidalnego (r = oo). Za Goldbergiem i Smithem (1987)
176
5. Techniki i operacje zaawansowane
Z równości tej wynika (dla 8 dużego w stosunku do pm), że końcowa stacjonarna frekwencja allelu jest wprost proporcjonalna do tempa mutacji.
Z kolei dla struktur diploidalnych można pokazać, że zależność między frekwencją allelu recesywnego w następnym pokoleniuajego frekwencją w pokoleniu bieżącymjest określona wzorem
W warunkach stacjonarności otrzymujemy następujący związek miedzy wymaganym tempem mutacji a frekwencją allelu recesywnego:
Przy niewielkiej frekwencji recesywnego allelu (Pss« 1) z równości tej wynika, że tempo mutacji niezbędne do utrzymania tejże frekwecji na stałym poziomie jest proporcjonalne do kwadratu frekwencji. Oczywiście, występowanie tych samych frekwencji allelu w wariantach haploidalnym i diploidalnym nie oznacza, że jest on w obu przypadkach w równym stopniu wystawiony na selekcję. Mimo tych samych frekwencji, w przypadku diploidalnym jest on poddawany próbie ze znacznie mniejszą częstością (proporcjonalną do kwadratu frekwencji). Wskazuje to na konieczność dokonywania sporadycznych zmian wzorca dominacji, aby umożliwić tak zmagazynowanym allelom sprawdzenie swojej wartości przystosowawczej w aktualnych warunkach.
5.1.3.Jmplementacja modelu triallelicznego
Implementacja modelu triallelicznego Hollstiena-Hollanda wymaga wprowadzeniajedy-nie drobnych zmian w naszym programie SGA. Należy zmienić struktury danych, tak aby uwzględnić homologiczne pary chromosomów oraz trzy allele na locus. Zmodyfikowane definicje i deklaracje danych dla SGA z dominowaniem (SGADOM) są podane na wyd. 5.1. Zauważmy, że typ allele został teraz zdefiniowany jako okrojony typ integer o zakresie -1..1 (w poprzedniej wersji był zdefiniowany jako typ boolean). W nowej implementacji -1 odpowiada recesywnemu 1 (10 w notacji Hollanda), 0 odpowiada 0, a 1 - dominującemu 1 (1 w notacji Hollanda). Relacja dominowania sprowadza się przy takim sposobie kodowania do zwykłej relacji >. Okoliczność ta została wykorzystana w funkcji paskalowej mapdominance, zamieszczonej w wyd. 5.2. Wzorzec dominacji zostaje zastosowany do pary chromosomów homologicznych w procedurze dominance, która wywołuje mapdominance kolejno dla każdej pozycji w chromosomach (wyd. 5.3).
Mechanizm wytwarzania potomstwa w modelu diploidalnym jest cokolwiek inny ' niż w wersji haploidalnej. W procedurze gametogenesis homologiczna para chromosomów produkuje parę gamet, które z kolei zostają zapłodnione przez inną parę gamet w procedurze fertilization. Proces ten jest niezupełnie zgodny z rzeczywistością biologiczną, jednak uwzględnia on najważniejsze elementy, a istniejące różnice mają na celu zmniejszenie do minimum szkodliwych efektów wywołanych niewielkimi rozmiarami populacji, na których najczęściej pracują algorytmy genetyczne.
5.1. Diploidalny aparat genetyczny. Dominowanie i maskowanie .
177
const maxpop
maxstring version
type allele
chromosome
chrompack
parentid
' idpack
individual
population
= 100;
= 30; .,- •
= 'vl.0';
= -1..1; { triallelic scheme (-1, 0, 1) }
= array[l..maxstring] of allele; { trits }
= array[1..2] of chromosome;
= record xsite, parent:integer end;
= array[1..2] of parentid;
= record
chrom:chrompack; { pack of chroms }
echrom:chromosome; { expressed chrom }
x, objective, fitness:real;
parents:idpack; { parent info } end; = array[l..maxpop] of individual;
oldpop, newpop:population;
popsize, lchrom, gen, maxgen:integer;
pcross, pmutation, sumfitness:real;
nmutation, ncross:integer;
avg, max, min:real;
{ non-overlapping }
{ integer globals }
{ Real globals }
{ Integer stats }
{ Real stats }
Wyd. 5.1. Triaileliczny mechanizm dominowania w Pascalu (SGADOM): definicje i deklaracje struktur danych
Nowe pokolenie powstaje pod kontrolą procedury generation, zamieszczonej w wyd. 5.4. Różni się ona od wersji oryginalnej tym, że została przystosowana do procedur gametogenesis \fertilization. Podobniejak poprzednio, najpierw wybiera się tu, przy użyciu funkcji select, parę partnerów do skojarzenia. Następnie dwukrotnie zostaje wywołana procedura gametogenesis, raz dla każdego z partnerów. Procedura fertilization z dwóch par gamet tworzy dwóch diploidalnych potomków; o tym, które gamety połączą się, decyduje rzut monetą. Po zapłodnieniu przeprowadza się ewaluację wskaźników przystosowania, zapamiętując przy okazji informacje o genealogii oraz punktach krzyżowania - do późniejszego wykorzystania w szczegółowym raporcie.
functionmapdominance(allelel,allele2:allele):allele; { dominance map using > relation among (-1,0,1) } begin
if (allelel >= allele2) then mapdominance := abs(allelel) else mapdominance := abs(allele2) end;
procedurę dominance(var lchrom:integer;
var homologous:chrompack; var expressed:chromosome );
1 { express dominance - homologous pair --> single chrom } var j:integer; begin
for j:=l to lchrom do
expressed[j]:=mapdominance(homologous[l,j],homologous[2,j]) end;
Wyd. 5.2. Trialleliczny mechanizm dominowania w Pascalu (SGADOM): funkcja mapdominance i procedura dominance
1
178
. 5. Techniki i operacje zaawansowane
procedurę gametogenesis(var ancestor,gamete:individual; var lchrom, nmutation, ncross,
jparent:integer; var pmutation, pcross:real);
{ Create a pair of gametes from a single parent } var j,jcross:integer; begin
{ handle crossover and mutation }
-" crossover(ancestor.chromfl], ancestor.chrom[2], ' ' gamete.chrom[l], gamete.chrom[2], !,^'~- > lchrom, ncross, nmutation, jcross, pcross, pmutation); { set parent and crossing pointers } for j := 1 to 2 do with gamete do begin chromid[j].parent :=jparent; chromid[j].xsite := jcross; 7 end; end; .. -, •.',- ;• ,• • - .•• '• • • ' ~ ' " '' : '
procedurę fertilization(var chroml, chrom2:chromosome; var parentl, parent2:parentid; var newindividual:individual); begin with newindividual do begin
, . chrom[l] := chroml; ••:.••'•••". ' •' •
chrom[2] := chrom2; chromid[l] := parentl; chromid[2] := parent2; end; end;
Wyd. 5.3. Trialleliczny mechanizm dominowania w Pascalu (SGADOM): procedury gametogenesis \ fertilization • . . . .... , , ,.. , ,. ,.
Oprócz opisanych zmian niezbędne są niewielkie modyfikacje sposobu dokonywania mutacji, części inicjującej programu i podprogramu sporządzającego raport. Zmiany w treści funkcji mutation odzwierciedlają fakt występowania trzech alleli. Aby uzyskać w populacji początkowej przeciętnie jednakową frekwencję jedynek i zer ulegających ekspresji, recesywne jedynki, zera oraz dominujące jedynki powinny być generowane losowo z prawdopodobieństwami odpowiednio 0,25, 0,5 i 0,25. Procedura używana przy tworzeniu raportów writechrom, została zmodyfikowana tak, by wypisywać poprawnie wszystkie trzy allele. Recesywnajedynka (lJ jest tu reprezentowana przez znak procentu (%). Zmiany w writechrom i mutation zostały podane na wyd. 5.5.
5.2. Inwersja i inne operacje rekonfiguracji
Artykułem wiary, na którym opieraliśmy wcześniejsze rozumowania dotyczące siły algorytmów genetycznych, było przekonanie, że schematy o dużej wartości przystosowawczej, małej rozpiętości i niskim rzędzie, czyli tak zwane cegiełki, łączą się z innymi takimi cegiełkami, tworząc ciągi kodowe o ponadprzeciętnej wartości przystosowawczej. Jednak różne przykłady zastosowań, z którymi się zetknęliśmy, uświadomiły nam, jak wielka dowolność wiąże się z wyborem sposobu kodowania. Czy możemy więc mieć pewność, że schematy związane z kodem użytym w danym zadaniu będą rzeczywiście prowadzić do
5.2. Inwersja i inne operacje rekonfiguracji
179
function other(jl:integer):integer;
begin if (jl=l) then other := 2 else other := 1 end;
procedurę generation;
{ Create a new generation through select, crossover, and rautation }
var j, jl, j2, raatel, mate2, jcross:integer;
gametel, gamete2:individual; begin j := 1;
repeat { select, generate gametetes until newpop is filled } { pick 2 mates }
matel := select(popsize, sumfitness, oldpop); {pick pair of mates } mate2 := select(popsize, sumfitness, oldpop); { make 4 gametes to make 2 zygotes } •"
garaetogenesis(oldpop[matel], gametel,
lchrom, nmutation, ncross, matel, '-
pmutation, pcross); gametogenesis(oldpop[mate2], gamete2,
lchrom, nmutation, ncross, mate2, pmutation, pcross);
{ flip honest coin to decide arrangement } if flip(0.5) then begin jl := 1; j2 := 1 end
else begin jl := 1; j2 := 2 end; { fertilize without replacment } , '''" fertilization(gametel.chrom[jl],
gametel.chromid[jl], v newpopljJ>;
jl := other(jl); j2 := other(j2); fertilization(gametel.chrom[jl],
gametel.chromid[jl], newpop[j+l]);
{ express, decode, and evaluate objective function } with newpop[j ] do begin
dominance(lchrom, chrom, echrom); X := decode(echrom, lchrom); s objective := objfunc(x);
end; with newpop[j+l] do begin
dominance(lchrom, chrom, echrom); x := decode(echrom, lchrom); objective := objfunc(x); end;
{ Increment population index }
j := j + 2; -• '>••" -' •' -' •. "->' -:
until j>popsize ; -
end;
Wyd. 5.4. Trialleliczny mechanizm dominowania w Pascalu (SGADOM): zmodyfikowana procedura generation uwzględniająca dominowanie i diploidalność
gamete2.chrom[j2], gamete2.chromid[i2],
gamete2.chrom[j 2], gamete2.chromidLj2] ,
poprawy? Prawdę mówiąc, nie możemy. Nie mamy żadnej pewności, że dowolny kod zastosowany w dowolnym zadaniu umożliwi elementarnemu algorytmowi genetycznemu znajdowanie lepszych rozwiązań. W pierwszej chwili stwierdzenie to może wprawiać w zakłopotanie dopóty, dopóki nie uświadomimy sobie, że przyroda również nie może być pewna swoich kodów i w związku z tym wypracowała mechanizmy, dzięki którym możejednocześnie usprawniać kod i poszukiwać lepszych zestawów alleli. W tym punkcie zajmiemy się badaniem takich właśnie mechanizmów rekonfiguracji, aby zorientować się, czy możnaje efektywnie zastosować w algorytmach genetycznych. . -
180
5. Techniki i operacje zaawansowane
function mutation(alleleval:allele; pmutation:real;
var nmutation:integer):allele;
{ Mutate an allele w/ pmutation, count number of mutations } var mutate:boolean; temp:allele; begin
mutate := flip(pmutation); { Flip the biased coin } if mutate then begin ,
nmutation := nmutation + 1; temp := alleleval + rnd(l,2); case temp of
mutation mutation mutation
{ Add one or two }
-1: 0: 1: 2: 3:
= temp; = temp; = temp;
= -l;
= 0;
mutation mutation end {case} end else
mutation := alleleval; end;
{ No change }
procedurę writechrom(var out:text; chrom:chromosome; lchrom:integer); { Write a chromosome as a string of l's (true's) and O's (false's) } var j:integer; ch:char; .
begin
for j := lchrom downto 1 do . ,• ...
begin ; ,,,.
case chrom[j] of
-1: ch := '%'; ,<. .. .. V . '. . ,. 0: ch := '0'; . ,
1: ch := '1'; " '.
end;
write(out,ch); end; end;
Wyd. 5.5. Trialleliczny mechanizm dominowania w Pascalu (SGADOM): zmodyfikowana funkcja mutation \ procedura whtechrom, uwzględniające dominowanie i diploidalność
Głównym naturalnym mechanizmem odpowiedzialnym za rekonfigurację kodu jest operacja inwersji. Podczas inwersji chromosom ulega przecięciu w dwóch wybranych punktach, a następnie środkowy jego odcinek ulega odwróceniu i połączeniu z dwoma pozostałymi. Początkowo operacja taka może się wydać dość dziwaczna, jeśli rozpatrywać ją w kontekście naszych sztucznych chromosomów-ciągów. Rozważmy na przykład następujący ośmiopozycyjny ciąg, w którym wybieramy drogą losową dwa punkty inwersji (powiedzmy miejsca 2 i 6, zaznaczone niżej znakiem A):
i o i i i o i i
Gdybyśmy chcieli bezmyślnie wykonać operację inwersji, otrzymalibyśmy w rezultacie następujący ciąg: • •
i o o i 11 i i
Nie widać wcale, jak operacja inwersji miałaby nam pomóc w znalezieniu nowej reprezentacji. W istocie, wygląda na to, że po prostu zmienia ona częściowo porządek
5.2. Inwersja i inne operacje rekonfiguracji
181
ułożenia alleli w ciągu kodowym. Kłopot bierze się z zastosowania zbyt prostej reprezentacji. Począwszy od pierwszego rozdziału zakładaliśmy, że funkcja allelu jest związana z jego położeniem, z jego locus. W rzeczywistości porządek genów w chromosomie może zostać odwrócony, a mimo to będą one odpowiadać za produkcję tego samego enzymu. Inaczej mówiąc, w przyrodzie funkcje alleli nie zależą od ich umiejscowienia. Aby zapewnić sobie taką samą swobodę, oznaczmy allele numerami od 1 do 8 i zobaczmy, co się stanie, gdy wykonamy operację inwersji na tak rozszerzonej reprezentacji: - , . ..-. .,«
1 2 3 4 5 6 7 8
1 0 1 1 l 0 1 1 ;
Gdy teraz dokonujemy tej samej inwersji, odnosimy ją również do ciągu numerów:
1 2 6 5 4 3 7 8 1 0 0 1 1 1 1 1
Dzięki tej rozszerzonej reprezentacji poszczególne bity zachowują swoje zamierzone znaczenie, niezależnie od pozycji, na której się znalazły. W terminach biologicznych rozszerzona reprezentacja rozdziela gen i locus. Ciekawą konsekwencją takiego pociągnięcia jest to, że wykonanie jednej samodzielnej inwersji nie wpływa bezpośrednio na wskaźnik przystosowania ciągu. Ponieważ allele są teraz ponumerowane, zmiana ich pozycji w ciągu nie ma wpływu na wynik dekodowania całości, tak więc wskaźnik przystosowania pozostaje bez zmian.
Jakkolwiek jest już rzeczą jasną, dlaczego rozszerzona reprezentacja umożliwia dokonywanie inwersji bez obawy pomieszania funkcji różnych alleli, nie wiemy wciąż, co pozytywnego wnoszą oba te pomysły do sprawy poszukiwań genetycznych. Przed chwilą właśnie stwierdziliśmy, że pojedyncza inwersja nie ma bezpośredniego wpływu na wartość przystosowawczą ciągu kodowego, po cóż więc przyroda trudzi się (i czemu my mielibyśmy się trudzić) tą przypadkową zabawą w genetyczne „komórki do wynajęcia"? Teoretyczną stroną operacji inwersji zajmiemy się nieco bardziej szczegółowo w dalszej części tego punktu; na razie poprzestańmy na stwierdzeniu, że inwersja mogłaby być przydatna do poszukiwania korzystnych konfiguracji ciągów kodowych, podczas gdy w tym samym czasie inne operacje genetyczne służą poszukiwaniu korzystnych zestawów alleli. Jeśli aktualna populacja zawiera niekorzystne permutacje alleli (takie, przy których allele o silnych związkach epistatycznych czy też nieliniowych są położone w odległych od siebie miejscach chromosomu), to krzyżowanie rozbije z dużym prawdopodobieństwem bloki alleli o ważnym znaczeniu przystosowawczym. Z drugiej strony, jeżeli wskutek rekonfiguracji zmienimy ustawienie alleli, to istnieje pewna szansa, że otrzymamy korzystne uporządkowanie, które w następstwie umożliwi bardziej efektyw-nąpropagację schematów-cegiełek. :^ :, ,'?';,.-?;r v:
Już wkrótce poddamy to rozumowanie dokładniejszej analizie. Natomiast w następnym punkcie dokonamy przeglądu wcześniejszych badań na temat mechanizmów rekonfiguracji w algorytmach genetycznych.
182
5. Techniki i operacje zaawansowane
5.2.1. Operacje rekonfiguracji w algorytmach genetycznych. Zarys historyczny_____________________________
Eksperymenty symulacyjne Bagleya (1967) objęły także inwersję. Zaimplementował on prostą operację inwersji oraz rozszerzoną reprezentację ciągu kodowego, którą omówiliśmy powyżej i stanął przed decyzją, jak podejść do krzyżowania niehomologicznych par ciągów. Dlaczego jest to istotny problem, możemy się przekonać na przykładzie krzyżowania dwóch następujących ciągów A i B:
A =
B =
Gdybyśmy naiwnie skrzyżowali te ciągi według zasady krzyżowania prostego, powiedzmy od pozycji czwartej (w miejscu zaznaczonym znakiem I), to otrzymalibyśmy dwa potomne ciągi następującej postaci:
1234 5678
1011 1011
1265 4378 /;
1001 1111
A' =
B' =
1 2 3 4 4 3 7 8
1 0 1 1 | 1 1 1 1
I
1 2 6 5 | 5 6 7 8
1 0 0 1 I 1 0 1 1
Widać od razu, że żaden z potomnych ciągów nie zawiera pełnego garnituru genów - i w ogólności, to właśnie jest główny argument przeciwko dopuszczaniu do krzyżowania dowolnie uporządkowanych ciągów. Bagley zastosował proste rozwiązanie eliminujące tę trudność: zabronił mianowicie krzyżowania niehomologicznych ciągów. Niestety, skutki tego pociągnięcia nie były zachęcające (Bagley, 1967, str. 168):
Wyniki dotyczące inwersji [...] były cokolwiek rozczarowujące. Najbardziej oczywistym skutkiem inwersji jest wyraźne wydłużenie przebiegów. Pamiętajmy, że jedną z konsekwencji inwersji jest zmniejszenie efektywnej intensywności krzyżowań, gdyż krzyżowanie fragmentów chromosomów, które nie są pozycyjnie homologiczne, jest niedozwolone. Jak widzimy, mniejsza intensywność krzyżowań odbija się niekorzystnie na symulacji i ten efekt wywarł przemożny wpływ na nasze wyniki. Pożądane konsekwencje inwersji, polegające na pojawieniu się w populacji gamet, w których geograficzne związki genów odzwieciedlałyby kombinacje [...], nie zostały zaobserwowane.
To niepowodzenie z inwersją Bagley przypisał charakterowi zadania (poszukiwanie strategii gry). Wyciągnął mianowicie wniosek, że zadanie było nie dość trudne (epistatycz-ne) na to, by inwersja mogła wykazać swe zalety. Ujmując to inaczej, elementarny algorytm genetyczny bez inwersji działał zbyt dobrze, aby jego wersja uzupełniona o in-
5.2. Inwersja i inne operacje rekonfiguracji
183
wersję mogła wykazać się większym tempem zbieżności lub lepszym końcowym stopniem zbieżności. Ta prawda (że elementarny AG działa zbyt dobrze) nieraz już wyszła najaw od czasu studiów Bagleya, co znacznie utrudniło wykazanie, że efekty sprzężenia odgrywają rolę w procesie poszukiwania genetycznego. Były też inne przyczyny tego, że Bagley nie potrafił wykazać korzyści wynikających z inwersji. Pamiętajmy, że Bagley dopuszczał wymianę wyłącznie homologicznych podciągów podczas krzyżowania. Reguła ta w istotny sposób ogranicza zasięg krzyżowania w populacji. Przyroda stosuje bardziej liberalną politykę w tym zakresie; podobnie mniej restryktywne reguły wprowadzili później inni badacze zainteresowani inwersją.
W swych badaniach dotyczących rozpoznawania postaci za pomocą algorytmu genetycznego, Cavicchio (1970) zastosował nieograniczoną inwersję wraz z następującym po niej krzyżowaniem; jak wiemy jednak z rozdziału trzeciego, geny Cavicchia składały się z numerów identyfikacyjnych pikseli zgrupowanych w detektorach. Przy takiej reprezentacji dowolna inwersja daje w wyniku „żywotny" chromosom. Ponadto dalsze krzyżowanie par prowadzi do powstania sensownego potomstwa, niezależnie od uporządkowania ciągów. Chociaż więc te korzystne właściwości wynikają z ukierunkowanego problemowo sposobu kodowania, wyniki Cavicchia są zachęcające. W jednej z serii eksperymentów, przy stosunkowo dużych intensywnościach krzyżowań i inwersji, otrzymano dobre tempo zbieżności i wysoki stopień ostatecznej zbieżności.
Natomiast badania Frantza (1972), poświęcone epistazie w procesach poszukiwania genetycznego, nie potrafiły wykazać przydatności inwersji. Frantz wykonał próby z kilkoma wariantami inwersji i reguł kojarzenia dla funkcji o różnym stopniu kont-' rolowanej nieliniowości. Rozważał on dwa warianty inwersji:
1) inwersjeliniowa[//near];
2) inwersję liniowo-boczną [linear+end].
Inwersja liniowa to nazwa, którą Frantz nadał zwykłej inwersji opisanej wcześniej w tym rozdziale. W przypadku inwersji liniowo-bocznej wykonujemy z zadanym prawdopodobieństwem (0,75) inwersję liniową. W przeciwnym razie wykonujemy z jednakowym prawdopodobieństwem (0,125) inwersję boczną od jednego lub drugiego końca ciągu. W inwersji bocznej jednym z końców odwracanego segmentu jest lewy lub prawy koniec całego ciągu, natomiast drugi koniec segmentu zostaje wybrany losowo spośród punktów leżących nie dalej niż w połowie odległości do drugiego końca ciągu. Inwersja liniowo--boczna była pomysłem, za pomocą którego Frantz próbował zmniejszyć tendencję inwersji liniowej do nieproporcjonalnego faworyzowania alleli położonych blisko środka ciągu (na niekorzyść alleli położonych w pobliżu krańców ciągu).
Każdy z wariantów inwersji mógł być stosowany w jednym z dwóch trybów:
1) inwersji ciągłej;
2) inwersji masowej.
W trybie inwersji ciągłej operacja inwersji była wykonywana z ustalonym prawdopodobieństwem p( dla każdego nowego osobnika w chwili jego powstania. Natomiast w trybie inwersji masowej, najpierw formowano całą nową populację, a następnie połowa osobników tej populacji przechodziła identyczną operację inwersji (z tymi samymi punktami
184
5. Techniki i operacje zaawansowane
końcowymi). Inwersja masowa była pomyślanajako środek powstrzymujący rozrost pod-populacji nie wchodzących ze sobą w interakcje, co towarzyszy kojarzeniu na zasadach ścisłej homologiczności.
Frantz wypróbował cztery reguły kojarzenia, mające na celu zapobieżenie trudnościom powstającym przy „naiwnym" krzyżowaniu par niehomologicznych:
1) kojarzenie ściśle homologiczne; - ;
2) kojarzenienapodstawieżywotności;
3) kojarzeniewedługwzorca; , • '•:••
4) kojarzeniewedługlepszegowzorca. r •• ;
Kojarzenie ściśle homologiczne odpowiada wariantowi stosowanemu przez Bagleya (tylko ciągi homologiczne mogą się ze sobą kojarzyć). Kojarzenie na podstawie żywotności dopuszcza krzyżowanie partnerów niehomologicznych, ale jeśli wynikłe stąd „potomstwo" nie posiada pełnego garnituru genów, to nie zostaje włączone do nowej populacji. W kojarzeniu według wzorca jeden z dwóch losowo wybranych partnerów określa wzorcowy porządek ciągu. Drugi z partnerów podlega wówczas odpowiedniej rekonfiguracji przed wykonaniem krzyżowania. Rekonfiguracja gwarantuje żywotność otrzymanego potomstwa. Kojarzenie według lepszego wzorca różni się od poprzedniego tylko tym, że osobnikiem wyznaczającym wzorcowy porządek zostaje lepiej przystosowany partner.
Pomimo liczby i różnorodności wypróbowanych opcji Frantzowi nie udało się wykazać istnienia wyraźnego efektu pozycyjnego. W dodatku nie potrafił on również dowieść wyraźnej korzyści z zastosowania inwersji w jakiejkolwiek postaci, trybie czy kombinacji kojarzeniowej. U podłoża napotkanych przez niego trudności leżał wybór środowiska eksperymentalnego. Frantz używał kombinacji liniowych funkcji liniowych lub nieliniowych ze względu na sześć do siedmiu alleli w 25-pozycyjnym ciągu kodowym. Funkcje nieliniowe były zdefiniowane przy użyciu tablic zawierających 26 lub 27 różnych wartości odpowiadających poszczególnym kombinacjom sześciu lub siedmiu alleli w grupie. Niestety, funkcje wybrane przez Frantza nie okazały się wystarczająco trudne, by zastosowanie inwersji stało się opłacalne. Jak zauważył Bethke (1981), funkcja AG-trudna nie tylko musi być epistatyczna, ale jej epistaza musi mieć zwodniczy charakter. Czyli wąskie schematy o wysokiej wartości przystosowawczej muszą kierować algorytm do złych obszarów przestrzeni. Sprawa ta nie była przedmiotem studiów Frantza, tak więc elementarny algorytm genetyczny był w stanie szybko znajdować rozwiązania.
Po pracach Frantza nastąpiła długa przerwa w badaniach nad zagadnieniem inwersji i innych mechanizmów rekonfiguracji ciągów. Holland (1975) wspomina krótko o inwersji, prezentując modyfikację twierdzenia o schematach, uwzględniającą przybliżone efekty zwykłej inwersji. Później niewiele było słychać o mechanizmach rekonfiguracji, aż do międzynarodowej konferencji na temat algorytmów genetycznych i ich zastosowań z 1985 r. Na konferencji tej kilku autorów (Davis, 1985b; Goldberg i Lingle, 1985; Smith, 1985) opisali konstrukcję operacji łączących w sobie cechy inwersji i krzyżowania. Choć powstały one niezależnie, operacje te mają wiele podobieństwa. Omówimy tu każdą z tych trzech operacji: PMX fo>artially matched crossover}, OX [order crossover] oraz CX [cycle crossover\. -;^
r
5.2. Inwersja i inne operacje rekonfiguracji
185
Operacja PMX powstała w wyniku prób stawienia czoła tzw. ślepej wersji zagadnienia komiwojażera. W zwykłym zagadnieniu komiwojażera (TSP) hipotetyczny komiwojażer ma za zadanie objechać wszystkie miasta z określonego zbioru, tak by zminimalizować przebytą drogę. W ślepej wersji tego zagadnienia zadanie komiwojażera pozostaje nie zmienione, ale nie zna on długości przebytej drogi aż do chwili zakończenia objazdu. Zagadnienie komiwojażera jest samo przez się problemem trudnym (należy do klasy problemów, które - jak się sądzi - nie dają się rozwiązać w czasie wielomianowym), nawet bez nakładania dodatkowych ograniczeń. Rozpatrując sposoby kodowania możliwe do zastosowania w tym zadaniu, niełatwo wpaść na rozwiązanie, które zapewniłoby rozsądne działania na schematach-cegiełkach. Wydaje się dość naturalne, by w zagadnieniach uporządkowania takich jak TSP stosować kod permutacyjny. Na przykład, w przypadku ośmiu miast odwiedzanych w kolejności rosnących numerów, trasa podróży mogłaby być przedstawiona następująco:
1 2 3 4 5 6 7 8
Odwrotna kolejność odwiedzin odpowiadałaby permutacji:
8 7 6 5 4 3 2 1
Chociaż taka reprezentacja wygląda dość naturalnie, nie widać na pierwszy rzut oka, jak można by ją dopasować do ogólnego schematu reprezentacji przyjętego dla algorytmów genetycznych. Niedawno podjęliśmy poważne wysiłki, aby dokonać rozdziału między funkcją a położeniem genu w chromosomie. Ujmując to matematycznie, moglibyśmy powiedzieć, że przystosowanie/powinno być funkcją podzbioru alleli v^=/(v)); jednak w wielu zadaniach korzystna może być także zależność przystosowania od ustawienia alleli: przystosowanie byłoby wtedy funkcją podzbioru alleli v i uporządkowania o tf=/(v, o)).
W zagadnieniu komiwojażera z reprezentacją permutacyjną osiągnęliśmy drugie ekstremum: przystosowanie jest tu funkcją samego uporządkowania tf=f(o)). Można by spekulować na temat wersji tego zadania, w której komiwojażer musi podejmować decyzje podczas swych zabiegów; decyzje takie nietrudno wtedy dołączyć do informacji o kolejności odwiedzin, otrzymując zagadnienie mieszane,/=/(v, o): -f .
l 2 3 4 5 6 7 8
o o o o o o o o •''- '''''' ' •''"' ''"'" :""": ''
W powyższym przykładzie do porządku odwiedzin są dołączone allele reprezentujące informację o każdym mieście (zera). Chcemy w ten sposób zaznaczyć, że potencjalnie istnieje całe spektrum możliwych sposobów kodowania, które w mniejszym lub większym stopniu zależą i od porządku i od składu chromosomu.
Jeśli już raz zgodziliśmy się z taką możliwością, powinniśmy teraz poszukać operacji analogicznej do krzyżowania, umożliwiającej wymianę wzorców uporządkowania między rodzicami i przekazywanie ich dzieciom. Pamiętajmy, że siła metod genetycznych zasadza się na połączeniu efektów selekcji i rekombinacji; mutacja pełni rolę ubezpieczenia przeciw bezpowrotnej utracie materiału genetycznego. W przypadku
186
5. Techniki i operacje zaawansowane
reprezentacji por/ądkowej inwersja jest - podobnie jak mutacja - operacją jednoar-gumentową. Jeżeli zamierzamy stworzyć operację o sile porównywalnej z siłą krzyżowania, musi to być operacja dwuargumentowa (podobnie jak krzyżowanie) i musi ona łączyć wzorce porządkowe pochodzące od ponadprzeciętnych rodziców w jakiś sensowny sposób. Goldberg i Lingle (1985) zaproponowali taki mechanizm w postaci operacjiPMX. •• .-•-.••••.: ,";";--,vv-..^<;:.tf.r.i,--:;'.^.4>".".: * ;
function find_city(city_name,n_city:city; var tour:tourarray):city;
var jl:integer;
begin
jl:-0;
repeat
jl:=jl+l; .i. ' : .
until ( (jl>n_city) or (tour[jl]=city_name) ); find_city:=jl; end;
procedurę swap_city(city_posl,'city_pos2:integer; var1 tour:tourarray);
var temp:city;
begin
temp:=tour[city_posl];
tour[city_posl]:=tour[city_pos2]j
tour[city_pos2]:=temp; . ;y •:. ;,-_j . . :, ,
end;
procedurę tour_norm(city_name,n_city:city; var tour:tourarray); var temp_tour:tourarray;
jl,j2:city;
begin -•'. ...'•;• • , -,-;. .•' . '
jl := find_city(city_name,n_city,tour); if (jl <> 1) then begin (* normalization *) for j2 := 1 to n_city do begin temp_tour[j 2]:=tour[j 1]; jl:=jl+l; if (jl>n_city) then jl:=l; end; •• ,"<• •- • '
tour:=temp_tour; end end; '' ;'
procedurę cross_tour(n_city,lo_cross,hi_cross:city;
var tour l_o ld, tour2_o ld, tour l_new, tour2_new: tourarray ); var jl,hi_test:integer; begin
if traceison then writeln('lo_cross,hi_cross=',lo_cross,' ',hi_cross); hi_test := hi_cross + 1; if (hi_test>n_city) then hi_test:=l; tourl_new := tourl_old; tour2_new := tour2_old;
if ( (lo_cross <> hi_cross) and (lo_cross <> hi_test) ) then begin '' jl := lo_cross;
4 while (jl<>hi_test) do begin (* mapped crossover on both tours *)
swap_city(jl,find_city(tourl_old[jl],n_city,tour2_new),tour2_new); swap_city(jl,find city(tour2_old[jl],n_city,tourl_new),tourl_new); jl:=jl+l; if (jl>n_city) then jl:= 1; end; end; end;
Wyd. 5.6. Operacja PMX w Pascalu. Procedura cross_four implementująca PMX, używa funkcji fincLcity\ procedury swap^city. Za Goldbergiem i Linglem (1985)
5.2. Inwersja i inne operacje rekonfiguracji
187
Podczas wykonywania PMX dwie reprezentacje (uwzględniające uporządkowanie i skład alleli) zostają ustawione jedna pod drugą, po czym dokonuje się losowego wyboru dwóch punktów podziału. Te dwa punkty wyznaczają sekcję dopasowania [matching section], służącą do określenia przebiegu procesu krzyżowania, realizowanego za pomocą transpozycji par elementów.
Zobaczmy jak to działa na przykładzie dwóch następujących ciągów:
A = 9 8 4 B = 8 7 1
5 6 7 2 3 10
1 3 2 10 9 5 4 6
Wykonanie PMX odbywa się drogą kolejnych transpozycji. Dopasowując ciąg B do ciągu A, zamieniamy miejscami 2 i 5, 3 i 6 oraz 10 i 7. Podobnie, dopasowując ciąg A do ciągu B, zamieniamy miejscami 5 i 2, 6 i 3 oraz 7 i 10. Po zakończeniu tych działań otrzymujemy dwa ciągi potomne:
A' = 9 8 4 B' = 8 10 1
2 3 10 5 6 7
1 6 5 7 9 2 4 3
przy czym uporządkowanie każdego z nichjest wyznaczone po części przez obu rodziców. W wydruku 5.6 podano implementację PMX w postaci procedur paskalowych. Procedury te były użyte do znalezienia rozwiązań dwóch zadań podanych przez Karga i Thompsona (1964), dotyczących odpowiednio 10 i 33 miast. Na rysunku 5.11 przedstawiono wykres długości najkrótszej drogi znalezionej w danym pokoleniu w zależności od numeru pokolenia dla dwóch niezależnych przebiegów algorytmu genetycznego, opartego na selekcji wg reguły ruletki oraz operacji PMX.
W jednym z przebiegów znaleziono rozwiązanie optymalne, a w drugim - bardzo bliskie optymalnemu. Wyniki dla 33 miast, pokazane na rys. 5.12, umożliwiają porównanie najlepszych rozwiązań (w kolejnych pokoleniach) dla wariantów ruletka-PMX i ruletka-inwersja. Zdolność PMX do przestawiania parami daje tej operacji możliwość
450,Or
N
a> O
400,0
c 'n)
350,0
0
10
Pokolenie
15
20
Rys. 5.11. Algorytm genetyczny z operacją PMX w ślepej wersji zagadnienia komiwojażera dla 10 miast. W przebiegu 1 proces zbiega do optymalnego rozwiązania. Wielkość populacji n=200 przy pc = 0,6. Za Goldbergiem i Linglem (1985)
188
5. Techniki i operacje zaawansowane
„bliskiego podejścia" do rozwiązania optymalnego, podczas gdy inwersja zacina się na „fałszywym płaskowyżu". Choć wygląda to zachecajaco,jednak w świecie, który widział już optymalne rozwiązania zagadnień TSP z 500 i 1000 miast, podobne przybliżone wyniki mogłyby zostać skwitowane wzruszeniem ramion - póki nie uświadomimy sobie, że algorytm genetyczny z PMX nie korzysta z informacji o odległościach między miastami. Ograniczenie się do ślepych metod poszukiwania charakterystyczne dla ,,czystych'' algorytmów genetycznych jest bardzo poważnym ograniczeniem i pod koniec rozdziału omówimy metody umożliwiające algorytmowi genetycznemu korzystanie z informacji specyficznej dla zadania. Na razie pamiętajmy jednak, że korzystanie z informacji specyficznej jest zawsze wątpliwym dobrodziejstwem. Użycie takiej informacji może znacznie zwiększyć efektywność algorytmu, ale też zawsze ogranicza zakres jego zastosowań.
45
40-
35
T5 rzyp. tlum.).
5.2. Inwersja i inne operacje rekonfiguracji
191
Dla długich ciągów równość ta redukuje się do , ,,,
P(przemieszczenia) = 2 (x - x2)
gdzie x oznacza położenie względne: x=kll. To asymptotyczne wyrażenie osiąga wartość maksymalną równą 0,5 dla * = 0,5.
Nierównomierność tego rozkładu była przyczyną, dla której Frantz wymyślił inwersję liniowo-boczną, o której wspominaliśmy wcześniej. Istnieją też inne sposoby zmniejszenia tych efektów peryferyjnych. Jednym z nich (nie bez analogii przyrodniczych) jest potraktowanie chromosomu jako pierścienia. W pozbawionym początku i końca pierścieniu każdy locus ma jednakowe prawdopodobieństwo przemieszczenia pod wpływem inwersji. Z analogiczną sytuacją mieliśmy do czynienia w rozdziale czwartym w przypadku krzyżowania dwupunktowego. Jeszcze inna możliwość to pozostawienie rzeczy takimi, jakie są i zaakceptowanie zależności od pozycji. Niewykluczone, że efekty peryferyjne mogą odgrywać pewną rolę tak w naturalnych, jak i w sztucznych procesach genetycznych, działając jako probabilistyczna tarcza ułatwiająca tworzenie się wartościowych zgrupowań genów. Gdyby tak było, korzystne zgrupowania genów mogłyby migrować ku peryferiom łańcucha używając osłony owego „inwersyjnego cienia" w celu hamowania procesu destrukcji. Z drugiej strony nieustabilizowane zgrupowania genów mogłyby szukać centrum łańcucha, co zapewniałoby im większe prawdopodobieństwo przemieszczeń.
Troska Frantza z powodu zależności prawdopodobieństwa przemieszczeń od pozycji w łańcuchu wydaje się zupełnie zrozumiała. Być może należałoby wyrównywać prawdopodobieństwa, a może, jak zauważyliśmy wyżej, zależność taka jest dającym się wykorzystać efektem ubocznym inwersji. Jeżeli naszym celem jest tylko znajdowanie ściśle sprzężonych „cegiełek", to absolutne położenie w łańcuchu nie wydaje się sprawą o największym znaczeniu. Bardziej uzasadnioną miarą potencjału destrukcyjnego operacji jest wówczas raczej stopień zachowania względnego skupienia genów. Holland (1975) uwzględnił tę okoliczność, obliczając w następujący sposób prawdopodobieństwo zniszczenia schematu wskutek inwersji:
P(zmszczema) = 2p,
8(ff) F - — - 1 -
/ — 1 J
Ostatni czynnik bierze się stąd, że jeśli obydwa końce odwracanego segmentu wypadają „wewnątrz" schematu, to rozpiętość schematu nie ulegnie przy tym zwiększeniu. Ilustrują to poniższe przykłady:
Inwersja destruktywna
! ! 3 ! 2 6 ! ! ! ! ! 3 ! ! 2 6 ! ! ! ! •". '
* * 0 * 0 1 * * *
* 0 * * 0 1 * * * *
192
. 5. Techniki i operacje zaawansowane
Inwersja niedestruktywna
\ ! 3 ! 2 6 ! ! ! ! ! 3 ! ! 2 6 ! ! !
* * 0 * 0 1 * * * * * * 0 0 * 1 * * * *
Użyta tu notacja różni się nieco od tej, którą stosowaliśmy do tej pory. Alleliczny symbol uniwersalny (*) zachowuje tu zwykłe znaczenie, natomiast wykrzykniki (!) są używane w celu zaznaczenia, że pozostałe nieokreślone geny mogą wystąpić w dowolnym porządku. Hol!and w swej oryginalnej pracy nie posługiwał się tą notacją ani nie wprowadził pojęcia schematu lub wzorca porządkowego; brał jednak pod uwagę możliwość zwiększenia rozpiętości schematu pod wpływem inwersji.
Pierwszym krokiem w kierunku ogólniejszej teorii schematów obejmującej także ich porządkowy aspekt było zdefiniowanie przeze mnie schematów porządkowych w związku z operacją PMX (Goldberg i Lingle, 1985). W pracy tej określono przestrzeń wszystkich wzorców porządkowych, korzystając z „porządkowego" symbolu uniwersalnego - wykrzyknika (!). Tak samo jak gwiazdki (*) określają wzorce podobieństwa dla alleli (schematy „alleliczne" lub a-schematy), tak też schematy porządkowe (nazwijmy je o-schematami) określają podobieństwa w uporządkowaniu. Na przykład o-schemat
! ! 2 3 ! ! ! ! ! ! , -
określa podzbiór wszystkich uporządkowań, w których geny o numerach 2 i 3 występują na pozycjach 3 i 4 odpowiednio. Dany schemat rzędu o wyznacza zatem (l-o)\ porządków na l-o nieokreślonych pozycjach. Na przykład w przypadku o-schematu określonego powyżej istnieje (10-2)! = 8! uporządkowań symboli {1, 4, 5, 6, 7, 8, 9, 10} na ośmiu nieokreślonych pozycjach. Nietrudno znaleźć liczbę o-schematów. Ponieważ istnieje sposobów wyboru o ustalonych pozycji w ciągu /-elementowym i ponieważ \ o I _ . .
istnieje \o\ sposobów rozmieszczenia / symboli na o miejscach, zatem łączna liczba
\o /
o-schematów wynosi
Proste rozumowanie wykazuje, że każdy ciąg jest reprezentantem 2' schematów i że populacja złożona z n schematów reprezentuje od 2' do n • 2' takich o-schematów.
Podana definicja o-schematujest tylkojedną z całego zbioru możliwych. Gdybyśmy chcieli rozpatrywać względne położenia alleli zamiast bezwględnych, zdefiniowalibyśmy względne schematy porządkowe (o-schematy typu r). Możemy teraz użyć zapisu r'(-) dla oznaczenia określonej klasy schematów bezwględnych (o-schematów typu a) długości /; w „rozwinięciu" wyrażenia r'"(3!!28) otrzymamy wówczas następujące schematy:
5.2. Inwersja i inne operacje rekonfiguracji
193
3 ! ! 2 8 ! ! ! ! !
! 3 ! ! 2 8 ! ! ! !
! 1 3 ! ! 2 8 ! ! !
! ! ! 3 ! ! 2 8 ! !
! ! ! ! 3 ! ! 2 8 !
!, ! ! ! ! 3 ! ! 2 8
Jeśli potraktujemy ciąg jako strukturę kołową bez początku i końca, to z tego samego wyrażenia otrzymamy ponadto następujące o-schematy bezwględne:
8 ! ! ! ! ! 3 ! ! 2
2 8 ! ! ! ! ! 3 ! !
! 2 8 ! ! ! ! ! 3 !
! ! 2 8 ! ! ! ! ! 3
Koncepcja „ślizgających się" genów nasuwa pomysł rozważenia trzeciego typu o-schematów. Do tej pory mówiliśmy o o-schemataeh, w których liczyło się bezwzględne położenie genów (typ a) oraz takich, w których liczyło się względne położenie genów (typ r). Rozważmy teraz pewien łańcuch genów o określonej rozpiętości i pozwólmy całemu pakietowi przesuwać się (w sensie o-schematów typu r) przy zachowaniu rozpiętości. Możemy teraz zdefiniować nowy typ o-schematów, które mogłyby być przydatne do scharakteryzowania pewnego typu problemów; nazwijmy je względnymi o-sche-matami z poślizgiem (w skrócie o-schematami typu rs). W celu opisania o-schematów typu rs wprowadźmy zapis funkcyjny rs'&(-) dla oznaczenia określonej klasy o-schematów względnych o rozpiętości 8 i długości /. Argumentem tej funkcji jest uporządkowana lista numerów, którą „rozwijamy" na zbiór o-schematów typu r. Na przykład o-schemat rs"}(238) rozwija się na następujące o-schematy typu r.
r10 (2 3 ! ! 8) r10 (2 ! 3 ! 8) r10 (2 ! ! 3 8)
Te schematy można z kolei rozwinąć na o-schematy bezwględne.
W niektórych problemach nieistotne może być nawet względne uporządkowanie ponumerowanych obiektów. Dla takich przypadków wprowadzimy ostatnie już rozszerzenie zapisu schematów, dopuszczające zmianę kolejności numerów: względne o-schematy z poślizgiem i zamianą (typ rse). Tak więc wyrażenie rse'^{-) rozwija nieuporządkowaną listę numerów na zbiór o-schematów typu rs. Na przykład o-schemat typu rse rse1^ (2 3 8) rozwija się na zbiór 6 o-schematów typu rs, wyznaczonych przez sześć permutacji liczb 2, 3 i 8. Te mogą być z kolei rozwinięte na o-schematy typu r i a.
Łączne rozpatrywanie o-schematów i a-schematów daje możliwość pełniejszego zrozumienia zachowania się algorytmów genetycznych pod kątem współdziałania operacji ,,allelicznych'' i rekonfiguracyjnych. Perspektywa taka pogłębia się, jeśli zwrócimy uwagę na to, że twierdzenie o schematach rozciąga się na o-schematy, a-schematy, jak też na kombinacje obu typów schematów. Trzeba jednak pamiętać, że prawdopodobieństwo
sfjft^^^^^^^
194
. 5. Techniki i operacje zaawansowane
przeżycia schematu pod działaniem danej operacji zależy od typu tego schematu. Na przykład w pracy Goldberga i Lingle'a (1985) wyznaczono prawdopodobieństwo przeżycia dla o-schematów typu a (bezwględnych) pod działaniem operacji PMX. Podane przez Hollanda (1975) „prawdopodobieństwo zniszczenia schematów" dotyczy o-schematów typu rse (względnych z poślizgiem i zamianą). Pogłębiona analiza przetwarzania schematów w rodzaju tej, którą przeprowadziliśmy w rozdziale drugim dla problemu MDP, powinna przyczynić się do dalszego teoretycznego wyjaśnienia problemu współdziałania o-schematów i a-schematów w rozwiązywaniu konkretnych zadań.
5.3. Inne mikrooperacje
Zapoznamy się teraz pokrótce z kilkoma mechanizmami niskopoziomowymi, których użycie proponowano w modelach adaptacyjnego poszukiwania genetycznego. Są to: segregacja, translokacja, duplikacja wewnątrzchromosomowa, delecja i zróżnicowanie płciowe. W porównaniu z mechanizmem dominowania i operacji rekonfiguracyjnych mają one jednak dla algorytmów genetycznych drugorzędne znaczenie.
5.3.1. Segregacja, translokacja i struktury wielochromosomowe __________
Rozważaliśmy do tej pory genotypy złożone z pojedynczego chromosomu (haploidalne) oraz z pojedynczej pary chromosomów (diploidalne). W przyrodzie większość organizmów jest wyposażona w genotypy złożone z wieIu chromosomów. Na przykład aparat genetyczny człowieka składa się z 23 par chromosomów dipłoidalnych. Zastosowanie podobnego rozwiązania w zagadnieniach związanych z poszukiwaniem genetycznym wymagałoby kolejnego rozszerzenia reprezentacji genotypu, tak by stanowił on listę k par ciągów kodowych (zakładając diploidalność). Co jednak miałoby uzasadniać takie powiększenie złożoności reprezentacji? Holland (1975) sugerował, że genotypy wielochromosomowe mogłyby przyczynić się do zwiększenia mocy algorytmów genetycznych, gdyby zastosować je łącznie z operacjami segregacji i translokacji.
Aby zrozumieć mechanizm segregacji, wyobraźmy sobie proces tworzenia się gamet w sytuacji, gdy genotyp składa się z więcej niż jednej pary chromosomów. Krzyżowanie (crossing-over} przebiegajak dawniej; kiedyjednak przystępujemy do utworzenia gamety, wybieramy wówczas po jednym z chromosomów homologicznych. Ten proces losowej selekcji, zwany segregacją, skutecznie likwiduje wszelkie sprzężenia między genami ulokowanymi w różnych chromosomach. Oczywiście, geny ulokowane w tym samym chromosomie są w dalszym ciągu mniej lub bardziej ściśle sprzężone, zależnie od dzielącego je dystansu. Segregacjajest użyteczną operacją w sytuacji, gdy względnie niezależne geny rozmieściły się w różnych chromosomach. Niekorzystne allele nie mogą wówczas rozprzestrzeniać się wykorzystując sprzężenia z nie związanymi z nimi allela-mi o dużej wartości przystosowawczej.
5.3. Inne mikrooperacje .
195
Ostatnie stwierdzenie jest pewnego rodzaju wyznaniem wiary. Jeśli bowiem segregacja może czynić użytek z właściwej organizacji chromosomu, to w jaki sposób chromosom uzyskuje właściwą organizację? Holland sugerował, że dzieje się tak dzięki translokacji. Translokację można traktować jako swego rodzaju crossing-over z udziałem różnych chromosomów. Aby zaimplementować taką operację na użytek algorytmów genetycznych, musimy zaopatrzyć każdy allel w pewien rodzaj „etykiety", aby można go było zidentyfikować po przerzuceniu do innego chromosomu wskutek translokacji. W przyrodzie zdarza się, że w wyniku translokacji może powstać genotyp z niepełnym garniturem genów; wydaje się jednak, że w modelach poszukiwania genetycznego może-myipowinniśmytegounikać. -:x;;;<, &;uf'- r^; •;
Omówione operacje nie były, jak dotąd, przedmiotem zbyt wielu eksperymentów z modelami poszukiwania genetycznego. Hollstien (1971) zastosował operację zbliżoną do segregacji w badaniach dotyczących genotypów diploidalnych złożonych z jednej pary chromosomów. Przyjął on, że segregacja polega na losowej wymianie alleli między łańcuchami rodzicielskimi podczas mejozy. Przeprowadzone eksperymenty miały ograniczony zakres i Hollstien nie sformułował żadnych ogólnych wniosków dotyczących tej operacji. W późniejszych badaniach związanych z zastosowaniem algorytmów genetycznych w problematyce maszyn uczących się konieczne okazało się wprowadzenie genotypów rozszerzonych oraz operacji przypominających segregację i translokację (Schaffer, 1984; Smith, 1980).
5.3.2. Duplikacja i delecja
Duplikacja i delecja to kolejna para operacji niskopoziomowych, które proponowano zastosować w modelach poszukiwań genetycznych. Duplikacja wewnątrzchromosomowa działa na zasadzie podwojenia określonego genu i umieszczenia jednocześnie obu kopii w chromosomie. Delecja polega na usunięciu z chromosomu zduplikowanego egzemplarza genu. Holland (1975) sugerował, że operacje te mogą być skutecznie używane w celu adaptacyjnego regulowania intensywności mutacji. Jeśli podstawowa intensywność mutacji pozostaje stała, a w wyniku duplikacji otrzymamy k egzemplarzy danego genu, to efektywne prawdopodobieństwo mutacji (prawdopodobieństwo, że co najmniej jedna z k kopii ulegnie mutacji) tego genu wzrasta k razy]). I odwrotnie, skutkiem delecji jest zmniejszenie efektywnej intensywności mutacji. Zauważmy przy tym, że kiedy jeden z egzemplarzy takiego genu zostanie zmutowany, wtedy musimy jakoś zdecydować, która z kopii ujawni się. Z analogiczną sytuacją mieliśmy do czynienia w przypadku dominowania. Rzeczywiście możemy przyjąć, że pojawienie się wielokrotnych kopii genu wywołuje zjawisko dominowania wewnątrzchromosomowego, w przeciwieństwie do zwykłego dominowania międzychromosomowego, które występuje przy diploidalno-ści. Holland proponował zastosowanie metody arbitrażu zbliżonej do dominowania, ale do tej pory nie opublikowano żadnych wyników badań tego typu mechanizmów.
Gdy kpm« \ fynyp. tłum.).
196
. 5. Techniki i operacje zaawansowane
Moglibyśmy postawić pytanie, czy duplikacja wewnątrzchromosomowa oraz dele-cja służą tylko jako adaptacyjny mechanizm regulacji tempa mutacji. Być może po części tak jest, jednak mieliśmy już okazję spotkać się z przykładem zastosowania duplikacji do znacznie istotniejszych celów. W rozdziale czwartym wspomnieliśmy mianowicie, że Cavicchio (1970) użył tej operacji do wytwarzania nowych detektorów cech. Każdy z jego genów określał zbiór pikseli wchodzących w skład detektora. Duplikacje wewnątrzchromosomowe nie stwarzały w tym przypadku problemu arbitrażu, a następujące dalej mutacje lub krzyżowania z udziałem nowego detektora mogły doprowadzić do powstania lepszego, odpowiedniejszego detektora. Pod pewnymi względami naturalne struktury genetyczne przypominają „niechlujne kodowanie" Cavicchia; wzięcie pod uwagę metod kodowania dopuszczających nadmiarowość, zmienną długość i niepełną specyfikację przyniosłoby, być może, pewne korzyści1}.
5.3.3. Determinacja płci i zróżnicowanie płciowe
To dziwne, a przynajmniej zastanawiające, dlaczego w książce, w której konstruujemy algorytmy oparte na wzorach zaczerpniętych z naturalnych procesów reprodukcji i z genetyki, nie pojawił się do tej pory temat płci. Nie stało się tak z braku zainteresowania ani też dlatego, że płeć jest mało znaczącym wynalazkiem o zaniedbywalnych efektach ubocznych. W tym punkcie omówimy mechanizm determinacji płci i zbadamy jego przydatność w modelach poszukiwania genetycznego.
Przyroda nie funkcjonuje tak prosto, jak zakładaliśmy. W naszych naiwnych metodach kojarzenia pozwalaliśmy każdemu osobnikowi wchodzić w związki z dowolnym innym osobnikiem i zawsze dokonywaliśmy takiego podziału wynikłych stąd produktów genetycznych, aby uzyskać zdolny do przeżycia genotyp. W przyrodzie wieIe organizmów dzieli się na dwie (lub więcej) różnych płci i muszą one w jakiś sposób wejść ze sobą w kontakt, aby zapewnić przetrwanie gatunku. Szczegółowy obraz determinacji płci wygląda różnie u różnych gatunków; dla naszych celów wystarczająco reprezentatywny jest jednak przykład człowieka.
Jedna z 23 par chromosomów ludzkich determinuje płeć. Kobiety mają dwa identyczne chromosomy płci (chromosomy X), a mężczyźni - dwa różne ^eden chromosom X i jeden chromosom Y). Podczas gametogenezy mężczyźni wytwarzają plemniki, które przenoszą albo chromosom X albo chromosom Y (w jednakowych proporcjach), natomiast kobiety wytwarzają jajeczka, które przenoszą jedynie chromosom X. Gdy dojdzie do zapłodnienia, wówczas zestawienie (pewnego) chromosomu X pochodzącego od kobiety z (losowym) chromosomem X lub Y pochodzącym od mężczyzny prowadzi do oczekiwanego (i obserwowanego) stosunku liczbowego płci męskiej i żeńskiej 1:1.
" Istotnie, pomysł ten został później wykorzystany w postaci tzw. niechlujnych algorytmów genetycznych; por. D.E. Goldberg, B. Korb, K. Deb, Messy Genetic Algorithms: Motivation, Analysis, and First Results, TCGA Report No. 89003, May 1989, University of Alabama nyp. tłum.).
5.3. Inne mikrooperacje .
197
Jfc i
Mimo że mechanizm determinacji płci u człowieka jest dość przejrzysty, przyroda dorzuca tu kilka interesujących komplikacji. Pewna liczba cech nie związanych z płcią może dziedziczyć się za pośrednictwem chromosomów płci. Te tak zwane cechy sprzężone z płcią są związane najczęściej z chromosomem X. W dodatku, chociaż u większości organizmów chromosom X zawiera loci, których brak w chromosomie Y, u niektórych organizmów oba te chromosomy zawierają odcinki homologiczne. W takim przypadku crossing-over zachodzący w strefie homologicznej może powodować występowanie niepełnego sprzężenia z płcią, w porównaniu do organizmów, u których zupełny brak homologiczności wyklucza crossing-over.
Wszystko to jest bardzo ciekawe. Nie możemy jednak zrezygnować z naszego pragmatycznego podejścia w zamian za kilka tajemnych szczegółów procesu reprodukcji. Wracając do meritum, co może nam dać determinacja i zróżnicowanie płciowe z punktu widzenia algorytmów genetycznych? Niestety, w literaturze na temat algorytmów genetycznych brak na razie publikacji poświęconych teoretycznym lub empirycznym studiom tych mechanizmów. Niemniej jednak proste rozumowanie może doprowadzić do satysfakcjonującego wyjaśnienia ich użyteczności. Jest oczywiste, że uformowanie się różnic płciowych prowadzi do podziału gatunku na dwie (lub więcej) kooperujące grupy. Takie rozdwojenie umożliwia samcom i samicom nieco odmienną specjalizację, dzięki czemu mogą one „zagospodarować" większą przestrzeń zachowań służących przeżyciu, niż byłoby to możliwe w ramach jednej konkurującej populacji.
Aby nadać temu rozumowaniu bardziej wymierny charakter, rozważmy wyidealizowany przypadek demonstrujący korzyści płynące z kooperacji i specjalizacji będących konsekwencją naturalnych różnic płciowych. Przypuśćmy, że osobnik może wybierać między zdobywaniem pożywienia („polowanie") a opieką nad potomstwem („wychowywanie"). Niech h będzie ułamkiem czasu poświęconym na polowanie, a n - ułamkiem czasu poświęconym na wychowywanie. Będziemy przyjmować, że prawdopodobieństwo przeżycia potomstwa 5 jest proporcjonalne do iloczynu tych ułamków:
Każdy osobnik musi dokonać podziału swych zajęć na czynności związane z polowaniem i czynności związane z wychowywaniem. Jeżeli następnie założymy, że z wykonywaniem tych czynności wiąże się dodatkowa strata czasu proporcjonalna do iloczynu obu „współczynników aktywności" (spadek wydajności), to otrzymamy następujące równa-nieopisującepodziałczasuzużywanegoprzezosobnika: ;,.,;: :;•-, •
n + h + anh — 1 . -.< •.•.-, , ,- ..•;, : ••.• :,
gdzie a jest współczynnikiem spadku wydajności z powodu braku specjalizacji. Maksymalizując wartość s przy użyciu elementarnych metod, otrzymujemy następujące optymalne poziomy wychowywania n* i polowania h* dla poszczególnego osobnika:
n* = h* =
198
. 5. Techniki i operacje zaawansowane
które osiągają w granicy dla a = 0 wartość n* = h* = Q,5. Wyrażając to słowami, osobnik może w najlepszym razie wybrać kompromis między dwiema niezbędnymi czynnościami; przewaga czasu wydatkowanego na którąkolwiek z nich zostaje ukarana spadkiem przeżywalności potomstwa. Ilustruje to graficznie rys. 5.13, gdzie są pokazane wykresy zależności przeżywalności s od współczynnika aktywności wychowawczej n dla przypa-dkowa=l ia = 0. "'•" :••< ••••- •*.< •.••> ,<
0,50-
•o
•OT O
C
S 0,25-
a> t!
0.
0,00-
a-0
0,0
0,5
1,0
Opieka nad potomstwem - n
Rys. 5.13. Aby zmaksymalizować szanse przetrwania gatunku, samotny osobnik musi szukać kompromisu między opieką nad potomstwem a zdobywaniem pożywienia. Spadek wydajności związany z brakiem specjalizacji (a>0) dodatkowo zmniejsza możliwość ' osiągnięcia wysokiej przeżywalności
Jeśli dopuścimy kooperację dwóch osobników, pozwalając im działać w charakterze jednostki myśliwsko-wychowawczej, otrzymamy podobny model przeżywalności potomstwa. Oznaczając odpowiednie współczynniki aktywności osobników 1 i 2 przez ht, nt, h2 i «2, możemy wyrazić prawdopodobieństwo przeżycia 5 wzorem
gdzie czynnik 1/2 wprowadzono, by umożliwić bezpośrednie porównanie z przypadkiem pojedynczego osobnika (teraz jest dwa razy więcej głów do wykarmienia i wychowania). Podział czasu obu osobników opisuje się następującymi równaniami:
'""""• n{ + hi + anihl - 1, i = 1, 2
Maksymalizując przeżywalność s ze względu na współczynniki aktywności myśliwskiej i wychowawczej otrzymujemy dwa przypadki do rozpatrzenia. Bez spadku wydajności z powodu braku specjalizacji przeżywalność osiąga maksimum wzdłuż prostej określonej równaniem
5.3. Inne mikrooperacje.
199
M* + «* = 1 ., • ; ,:,. = :
jak pokazano na rys. 5.14a, przedstawiającym wykres przeżywalności jako funkcji współczynników aktywności wychowawczej. Gdy nie ma strat, wówczas istnieje bodziec do współpracy (przeżywalność wzrasta z 0,25 do 0,5), ale nie ma bodźca do specjalizacji; wystarczy, aby łączny czas poświęcany przez oba osobniki na polowanie (względnie wychowanie)wynositjeden. , ;'-^'>f
Jeśli jednak pojawiają się straty (a>0), sytuacja zmienia się zasadniczo, co pokazuje rys. 5.14b. Optymalne zachowanie wymaga teraz specjalizacji. Maksimum prze-
*)
s(ry^)
s(n
Rys. 5.14. Kooperacja osobników zwiększa szanse przetrwania; jeśli jednak nie następuje spadek wydajności z powodu braku specjalizacji, to nie ma też powodów do specjalizacji (a). Jeśli występuje spadek wydajności, maksymalną przeżywalność osiąga się przy maksymalnej specjalizacji (b)
200
5. Techniki i operacje zaawansowane
żywalności otrzymuje się, gdy («,, «2) = (1, 0) lub (nt, n2) = (Q, 1). Mamy tu nadal przewagę w stosunku do przypadku osobnika samowystarczalnego, straty zaś zostają zminimalizowane.
Chociaż powyższy model jest bardzo uproszczony, demonstruje on istotę kooperacji i specjalizacji, którym służy zróżnicowanie płciowe. Przyszłe próby z wykorzystaniem płciowości w modelach poszukiwania genetycznego wykażą zapewne przewagę tego typu mechanizmu w zagadnieniach wymagających, podobnie jak wyżej, połączenia kooperacji ze specjalizacją. . •
5.4. Nisze i specjacja
Zróżnicowanie płciowe otworzyło drogę specjalizacji, która w przyrodzie sięga jeszcze dalej poprzez specjację (powstawanie gatunków) i wypełnianie nisz ekologicznych. Intuicyjnie niszę możemy przyrównać do określonego „zawodu" lub funkcji pełnionej przez dany organizm w środowisku, natomiast przez gatunek możemy rozumieć klasę organizmów o wspólnej charakterystyce. Ten podział środowiska i organizmów wykorzystujących środowisko na odrębne podzbiory jest tak powszechny w przyrodzie, że rzadko poświęcamy mu specjalną uwagę. W świetle tego może wydać się niezrozumiałe, dlaczego jeszcze nie zaobserwowaliśmy stabilnych podpopulacji ciągów kodowych (czyli gatunków), związanych z różnymi poddziedzinami funkcji (niszami) w większości omawianych przykładów. W tym punkcie pokażemy, w jaki sposób wprowadzenie nisz i gatunków może dopomóc w procesie poszukiwania realizowanym za pomocą algorytmu genetycznego, przedstawimy wyniki teoretyczne dotyczące tego problemu oraz wskażemy metodę urzeczywistnienia podobnych mechanizmów w algorytmach genetycznych.
o,o
0,5 X
(a) Równe wierzchoN;. ;h: ,:,
202
5. Techniki i operacje zaawansowane
5.4.1. Teoria nisz i gatunków
Mimo że istnieje obszerna literatura biologiczna na temat nisz ekologicznych i specjacji, jak dotąd niewiele udało się z niej przenieść na grunt algorytmów genetycznych. Tak jak i w przypadku wielu innych pomysłów i operacji, pierwsze koncepcje teoretyczne mające bezpośrednie odniesienie do algorytmów genetycznych przypisuje się tu Hollandowi (1975). Aby zilustrować mechanizm nisz i specjacji, Holland posłużył się zmodyfikowaną wersją zagadnienia dwuramiennego bandyty z podziałem [sharing] wypłaty. Prześledźmy zatem jego rozumowanie dla konkretnego sformułowania tego problemu.
Lewa kolejka J— dzieli się 1 f
matąwygraną /\^
Prawa kolejka dzieli się dużą wygraną
Rys. 5.16. Dwuramienny bandyta z podziałem wygranych pomiędzy graczy w kolejkach
Wyobraźmy sobie dwuramiennego bandytę z rys. 5.16. Tak jak w zagadnieniu dwuramiennego bandyty, które rozważaliśmy w rozdziale drugim, mamy tu dwa ramiona - lewe i prawe - i z każdym z nich jest związana inna średnia wypłata. Przypuśćmy, że dla prawego ramienia wynosi ona 75 dolarów, a dla lewego - 25 dolarów; podobnie jak w oryginalnym sformułowaniu zagadnienia, początkowo nie wiemy, które z ramion zapewnia większą wygraną. Załóżmy następnie, że mamy populację złożoną ze 100 graczy i że każdy z nich otrzymuje pełną kwotę wygranej związaną z ramieniem, które wybrał w danej próbie. Jeśli poprzestaniemy na tym i pozwolimy graczom wybierać dowolne
5.4. Nisze i specjacja
203
ramię, to sytuacja będzie wyglądać podobnie jak w pierwotnej wersji zagadnienia. Jeśli gracze „reprodukują się" proporcjonalnie do przystosowania, to coraz większa liczba członków populacji powinna ustawiać się w kolejce do lepszego (prawego) ramienia, aż wres/xie cała populacja skupi się w jednej kolejce.
Na razie nie mieliśmy powodu oczekiwać tworzenia się nisz; wszystkie eksperymenty zostają w ostateczności skierowane do najlepszego empirycznie ramienia. Wprowadzimy teraz istotną modyfikację do zasad gry, która spowoduje tworzenie się stabilnych podpopulacji wokół każdego z ramion. Zamiast wypłacać pełną wygraną każdemu osobnikowi, będziemy ją dzielić pomiędzy graczy z danej kolejki. Na pierwszy rzut oka wygląda to na dość drobną zmianę. W rzeczywistości ta jedna modyfikacja pociąga za sobą dramatyczne i zaskakujące skutki.
Aby przekonać sięjak i dlaczego zmienia się zachowanie graczy, zwróćmy uwagę, że mimo nieco odmiennych reguł gry, członkowie populacji nadal reprodukują się proporcjonalnie do przystosowania. W zmodyfikowanej grze każdy osobnik otrzymuje wypłatę zależną od ramienia, które wybrał oraz od liczby osobników stojących w tej samej co on kolejce. W naszym konkretnym przykładzie osobnik ustawiony w kolejce do prawego ramienia otrzymuje - w przypadku gdy wszyscy pozostali gracze stoją w tej samej kolejce - kwotę $75/100 = $0,75. Z drugiej strony, gdyby wszyscy gracze ustawili się do lewego ramienia, każdy grający otrzymywałby kwotę $25/100 = $0,25. W obu przypadkach pewna liczba graczy ma motywację do zmiany kolejki. W pierwszym z nich pojedynczy gracz zmieniający kolejkę zarabia na tym kwotę $25,00 - $0,75 = $24,25. W drugim przypadku motywacja do zmiany kolejki jest jeszcze większa. Możemy więc spodziewać się, że gdzieś pośrodku leży punkt, w którym nikomu nie opłaca się już zmieniać kolejki. Dzieje się tak, gdy wypłaty dla poszczególnych graczy w obu kolejkach są jednakowe. Jeżeli M jest wielkością populacji i mk,we jest długością kolejki do lewego ramienia, ml>rawe - długością kolejki do prawego ramienia, flewf - średnią wypłatą dla lewego ramienia i fprawe - średnią wypłata dla prawego ramienia, to punkt równowagi określają równości
J\>rawe __ J]iruv*
m,,
Jltwe
m
W naszym przykładzie całkowite wyrównanie wypłat indywidualnych nastąpi, gdy 75 graczy wybierze prawe ramię, a 25 graczy - lewe ramię, ponieważ $75/75 = $25/25 = $l. Bezpośrednie uogólnienie tego modelu na przypadek &-ramienny nie zmienia zasadniczej konkluzji. Wprowadzenie przymusowego podziału pociąga za sobą formowanie się stabilnych podpopulacji (gatunków) związanych z różnymi ramionami (niszami). W dodatku liczba osobników zajmujących określoną niszę jest proporcjonalna do oczekiwanej wypłaty z niszy. Jest to dokładnie ten typ zachowania, którego oczekiwaliśmy, rozpatrując zagadnienia wielomodalne z rys. 5.15. Oczywiście, przeniesienie koncepcji podziału na grunt prawdziwych algorytmów genetycznych jest sprawą trudniejszą, niż sugeruje to powyższy wyidealizowany przykład. W rzeczywistym algorytmie genetycznym mamy do czynienia z wieloma ramionami i decyzja, kto i w jakim stopniu powinien korzystać z podziału, nie jest banalną kwestią. W następnym punkcie omawiamy
204
. 5. Techniki i operacje zaawansowane
sposoby wywołania zjawiska formowania się nisz za pomocą mechanizmu podziału lub czegoś w tym rodzaju. Przedtem jednak musimy zająć się jeszcze jednym teoretycznym aspektem specjacji.
Uznając znaczenie podziału dla formowania się nisz, mamy do dyspozycji prawie gotowy aparat teoretyczny, potrzebny do objaśnienia funkcjonowania tego mechanizmu w modelu poszukiwań genetycznych; jednak pewna dodatkowa obserwacja przyrodnicza pozwoli nam osiągnąć jeszcze więcej. Otóż w naszym elementarnym modelu pozwalaliśmy na losowe kojarzenie się osobników. Jest to niezgodne z większością przykładów biologicznych. Ludzie nie szukają partnerów wśród kotów, a żaby wśród uczonych (choć gdyby tak było, to może mielibyśmy naukowców chwytających w lot problemy). Spostrzeżenie, że przedstawiciele poszczególnych gatunków nie są skłonni kojarzyć się z osobnikami niepodobnymi do nich samych, stawia przed nami pytanie, dlaczego tak się dzieje. Mówiąc inaczej, jaką korzyść selekcyjną przynosi reguła stanowiąca, że podobne kojarzy się z podobnym (kojarzenie selektywne dodatnie), której zdaje się przestrzegać większość gatunków? Prosty przykład z dziedziny optymalizacji funkcji znów dopomoże nam w naświetleniu podstawowej idei. Przypuśćmy, że mamy do czynienia z funkcją przybierającą wartości maksymalne na przeciwległych końcach odcinka, na którym jest określona (rys. 5.17). Jeśli użyjemy zwykłego dwójkowego kodu pozycyjnego, to osobniki położone w pobliżu lewego maksimum będą miały w sobie dużo zer, podczas gdy osobniki położone w pobliżu prawego maksimum będą miały dużo jedynek (lewe maksimum funkcja osiąga dla ciągu 00000, a prawe - dla ciągu 11111). W miarę jak postępuje proces reprodukcji, krzyżowania i mutacji, osobniki potomne będą na ogół przypominać
f(x)
Skrzyżowanie dobrze przystosowanych rodziców
daje nieprzystosowane potomstwo
Rys. 5.17. Prosta funkcja dwumodalna ilustrująca potrzebę stosowania barier reprodukcyjnych. Krzyżowanie się dwóch niepodobnych niemaloptymalnych osobników prawie zawsze prowadzi do degeneracji
5.4. Nisze i specjacja
205
takie ciągi, jak 00111 lub 11000 (a więc stosunkowo bezużyteczne - w tym przypadku - zestawienia zer i jedynek). Kojarzenie międzygatunkowe prowadzi więc w ten sposób do tworzenia upośledzonego potomstwa (degeneratów). Jeżeli natomiast uda się wywrzeć presję w kierunku kojarzenia się osobników podobnych, to produkcja bezużytecznego potomstwa może zostać ograniczona. Wskazuje to na potrzebę znalezienia metod wspomagających bardziej owocne wzorce kojarzenia.
5.4.2. Metody niszowe w poszukiwaniach genetycznych
Realizowano już różne metody powodujące formowanie się nisz w algorytmach genetycznych. W niektórych z tych technik podział ujawnia się w sposób pośredni. Chociaż zagadnienie dwuramiennego bandyty z podziałem jest prostą abstrakcją formowania się i wypełniania nisz ekologicznych, przyroda nie dzieli się swymi dobrami w tak bezpośredni sposób. W naturalnych warunkach podział dochodzi do skutku poprzez konkurencję i konflikt. Kiedy siedlisko pewnego organizmu zostaje przepełnione, zamieszkujące je osobniki są zmuszone dzielić między siebie dostępne zasoby.
Cavicchio (1970) byłjednym z pierwszych, którzy podjęli próbę wywołania ,,ni-szopodobnego" zachowania algorytmu genetycznego. Wprowadził on mechanizm nazwany preselekcją. Była to metoda polegająca na zastępowaniu gorszego z rodziców przez jego potomka, o ile tylko potomek wykazywał lepsze od niego przystosowanie. Populacja była dzięki temu zdolna do zachowania różnorodności, gdyż ciągi kodowe miały tendencję do zastępowania podobnych do siebie jednego ze swych rodziców). Cavicchio twierdził, że udało mu się w ten sposób utrzymywać bardziej różnorodne populacje w szeregu przebiegów symulacyjnych, przy stosunkowo niedużych rozmarach populacji (« = 20).
De Jong (1970) uogólnił technikę preselekcji w postaci modelu ze ściskiem. W modelu tym używa się populacji mieszanych (wielopokoleniowych), przy czym nowe osobniki zastępują inne według kryterium podobieństwa. Nowy osobnik zostaje porównany z losową podpopulacją o rozmiarze równym czynnikowi ścisku CF. Osobnik o najwyższym stopniu podobieństwa (w sensie minimalnej liczby różnic na poszczególnych pozycjach) zostaje następnie zastąpiony przez nowoutworzony ciąg. Początkowo działanie tego mechanizmu nie odbiega od losowego wyboru elementów do usunięcia, gdyż wszystkie osobniki są na ogół w tym samym stopniu niepodobne do siebie. W miarę jak symulacja postępuje i coraz więcej osobników w populacji upodabnia się do siebie (zaczyna się wyłaniać jeden lub więcej gatunków), zastępowanie jednych osobników innymi, podobnymi do nich osobnikami, sprzyja utrzymaniu różnorodności i tworzy przestrzeń życiową dla dwóch lub więcej gatunków. De Jong odniósł sukces, stosując model ze ściskiem do funkcji wielomodalnych przy czynniku ścisku CF równym 2 lub 3. Podobna metoda była później użyta w zastosowaniach związanych z maszynami uczącymi się (Goldberg, 1983).
Zwróćmy uwagę na to, że ani preselekcja Cavicchia, ani ścisk De Jonga nie wydają się wykazywać analogii do omawianego wcześniej podziału zasobów. Oba mechanizmy wywołują jednak coś w rodzaju pośredniego podziału w następującym
206
. 5. Techniki i operacje zaawansowane
sensie. Pod nieobecność preselekcji lub ścisku osobnik w populacji mieszanej podlega wymianie losowej (zjednakowym prawdopodobieństwem wyboru dla wszystkich). Jeżeli osobnik jest wymieniany z większą intensywnością (niż przy wymianie losowej), jak to dzieje się przy ścisku lub preselekcji, gdy wyłania się gatunek, to traci część „dochodu" (potomstwa), ponieważ nie realizuje pełnego potencjału reprodukcyjnego. Mówiąc inaczej, chociaż ścisk i preselekcja koncentrują się na aspekcie zastępowania, to wymuszając wcześniejsze „odejście" przedstawicieli nazbyt licznych gatunków, redukują liczbę ich potomstwa, zwalniając w ten sposób miejsce dla innych.
Najbardziej bezpośrednie odniesienia do biologicznej teorii nisz w kontekście algorytmów genetycznych można znaleźć w rozprawie Perry'ego (1984). W pracy tej Perry określa odwzorowanie genotyp-fenotyp, definiuje środowisko wieloczynnikowe oraz specjalny obiekt zwany schematem zewnętrznym. Schematy zewnętrzne to specyficzne wzorce podobieństwa określone przez projektanta systemu, służące do scharakteryzowania przynależności gatunkowej. Niestety, konieczność odwołania się do interwencji czynnika zewnętrznego ogranicza możliwości praktycznego zastosowania tej techniki w modelach poszukiwania genetycznego. Niemniej jednak Czytelnik interesujący się związkami między biologiczną teorią nisz a algorytmami genetycznymi znajdzie w tej pracy ciekawy materiał.
Grosso (1985) również nadał orientację biologiczną swej pracy poświęconej mechanizmom formowania się podpopulacji oraz migracji między nimi. Ponieważ użył on do badań multyplikatywnych funkcji celu faworyzujących osobniki heterozygotyczne (efekt heterozji), otrzymane przezeń wyniki nie mają bezpośredniego zastosowania w większości modeli poszukiwań genetycznych; jednakże Grosso był w stanie wykazać wyższość umiarkowanej intensywności migracji nad izolacją podpopulacji (brakiem migracji) oraz panmi-ksją (całkowitą swobodą kojarzenia prowadzącą do wymieszania podpopulacji). Badania te sugerują, że uwzględnienie czynnika geograficznego w poszukiwaniach genetycznych może sprzyjać formowaniu się odrębnych podpopulacji. Konieczne są dalsze studia, aby wyjaśnić, jak można tego dokonać w typowych zagadnieniach poszukiwania.
Praktyczna metoda kreowania nisz i gatunków, oparta bezpośrednio na idei podziału zasobów, została opisana przez Goldberga i Richardsona (1987). Wprowadza się tamfunkcję wspótudziału [sharingfunction], która określa sąsiedztwo i stopień współudziału dla każdego ciągu kodowego w populacji. Aby zobaczyć, jak działa ten mechanizm, rozważmy znanejuż prostejednoargumentowe funkcje przystosowania z rys. 5.15 oraz liniową funkcję współudziału, pokazaną na rys. 5.18. Liczbę współudziałów dla danego osobnika0 oblicza się, sumując wszystkie wartości funkcji współudziału wnoszone przez inne ciągi w populacji. Ciągi znajdujące się w bliskim sąsiedztwie danego osobnika mają duże współudziały (bliskie jedności), natomiast ciągi odległe - bardzo małe współudziały (bliskie zeru). Ponieważ osobnik znajduje się bardzo blisko (najbliżej jak można) siebie, zatem wartość funkcji współudziału wynosi dla niego 1 (podobnie jak dla każdego identycznego z nim ciągu). Po zsumowaniu wszystkich obliczonych w ten
" Liczba współudziałówjest miarą zapotrzebowania na zasoby środowiska w sąsiedztwie danego osobnika tyrzyp. tlutn).
5.4. Nisze i specjacja
207
g
o. I
1,0-
0,0
Odległość d^ = |fc-^H Rys. 5.18. Liniowa funkcja współudziału. Za Goldbergitm i Richardsonem (1987)
sposób współudziałów, zdeprecjonowany wskaźnik przystosowania osobnika oblicza się, dzieląc jego potencjalny wskaźnik przystosowania przez łączną liczbę współudziałów:
/,(*i) = T: #10tt:1010
#01#:1100 ,. -
ttOO#:0000 . ... i,
* J
W powyższych ciągach wzorce kojarzeniowe (podciągi położone na lewo od dwukropka) zostały zbudowane z symboli trójelementowego alfabetu 0, 1, #. Symbol 0 we wzorcu pasuje do symbolu 0 w części funkcjonalnej, podobnie 1 pasuje do 1, a # pasuje do 0 lub 1. W celu stwierdzenia, które z ciągów kodowych mogą się ze sobą kojarzyć, wzorzec kojarzeniowy jednego ciągu zostaje porównany z częścią funkcjonalną drugiego ciągu. Można tu wprowadzić różne reguły:
1) pełną zgodność dwustronną;
2) pełnązgodnośćjednostronną; . ,, ^,.
3) najlepszą zgodność częściową.
Część funkcjonalna ciągu zostaje zdekodowana w zwykły sposób w celu określenia wartości parametrów i wskaźnika przystosowania.
Wracając do przykładu, dwa pierwsze ciągi są zdatne do kojarzenia przy regule zgodności dwustronnej, gdyż wzorzec kojarzeniowy każdego z nich pasuje do części funkcjonalnej drugiego (#10# pasuje do 1100 i #01# pasuje do 1010). Trzeci z ciągów nie jest kandydatem nadającym się do kojarzenia, gdyż jego wzorzec kojarzeniowy nie pasuje do części funkcjonalnej żadnego z pozostałych.
Taki mechanizm kojarzenia jest dość prosty, ale dlaczego właściwie powinniśmy komplikować istniejące operacje? Przede wszystkim chcielibyśmy, aby jednocześnie z selekcją genotypów pod względem przystosowania mogły ulegać adaptacji ich praktyki kojarzeniowe. Czyniąc wzorzec kojarzeniowy częścią genotypu, poddajemy go selekcji i działaniu operacji genetycznych Qak krzyżowanie, mutacja i inne). W ten sposób populacja wykształca drogą ewolucji preferencje reprodukcyjne, które sprzyjają wytwarzaniu lepszego potomstwa. Ów efekt drugiego rzędu może się początkowo wydać niezgodny z intuicją, ale przecież mieliśmy już okazję dyskutować podobny mechanizm, kiedy rozważaliśmy możliwość kontroli genetycznej nad parametrami algorytmu genetycznego, takimi jak prawdopodobieństwa krzyżowania i mutacji (Bowen, 1986). Ponieważ
212
5. Techniki i operacje zaawansowane
w aktualnie rozważanym przypadku „plakietki preferencyjne" nie wpływają bezpośrednio na wartość przystosowawczą (nie zmieniają parametrów rozwiązania), wiec mamy tu właściwie do czynienia ze sprawą wydajności: preferowanie dobrych partnerów zwiększa prawdopodobieństwo dalszej poprawy wyników (zmniejsza prawdopodobieństwo destrukcji), możemy zatem oczekiwać wzrostu tempa poprawy w stosunku do algorytmów bez adaptacyjnych barier reprodukcyjnych.
Proponowano liczne ulepszenia podstawowej wersji mechanizmu. Jedno z zastrzeżeń wysuwanych wobec metody Bookera dotyczy konieczności dołączenia do ciągu kodowego wzorca kojarzeniowego o tej samej długości, co część funkcjonalna. Ponieważ mechanizm barier reprodukcyjnych przynosi w najlepszym razie wtórne korzyści, należy wątpić, czy wartjest inwestycji w postaci co najmniej dwukrotnego zwiększenia pamięci (nie wspominając już o dodatkowym koszcie obliczeniowym związanym z porównywaniem pełnych ciągów). W odpowiedzi na te obiekcje Holland (doniesienie prywatne, 1985) zaproponował zastosowanie trzyczęściowych ciągów kodowych, składających się z krótkiego wzorca kojarzeniowego, krótkiego identyfikatora kojarzeniowego i części funkcjonalnej o pełnej długości. Krótkie wzorce kojarzeniowe byłyby tu porównywane z krótkimi identyfikatorami kojarzeniowymi, a części funkcjonalne nie brałyby udziału w tym rytuale godowym. Przykładowa para trzyczęściowych chromosomów mogłaby wyglądać następująco:
:: #10#:1010:10010011101010 #0##:1100:11111000010010
Zauważmy, że wzorzec pierwszego ciągu pasuje do identyfikatora drugiego ciągu i odwrotnie.
Istnieje wiele odmian mechanizmu barier reprodukcyjnych. Sprawą otwartą pozostaje, czy lepszajest zgodność dwustronna czyjednostronna, a Booker (1982) posunął się nawet do sugestii, aby rozpatrywać różne stopnie zgodności częściowej, kiedy nie ma mowy o pełnej zgodności. Chociaż te i podobne pomysły brzmią wiarogodnie, nie przedstawiono na razie wielu argumentów teoretycznych ani empirycznych na ich poparcie. W konsekwencji problem wzorców i identyfikatorów kojarzeniowych pozostaje wciąż płodnymtematembadawczym. •
5.5. Optymalizacja wielokryterialna
Wszystkie dotychczas prezentowane zadania optymalizacji i poszukiwania sprowadzały się do jednego kryterium. Kryterium to (reprezentowane przez funkcję celu) było następnie przekształcane do postaci funkcji przystosowania, po czym mogliśmy już przystępować do realizacji planu reprodukcyjnego z udziałem operacji genetycznych. Podejście takie zdaje egzamin w wielu zagadnieniach, ale zdarza się, że mamy do czynienia z wieloma kryteriami jednocześnie i nie jest rzeczą możliwą (ani rozsądną) wyrażać je w po-
5.5. Optymalizacja wielokryterialna
213
staci jednej liczby. Mówimy w takich przypadkach, że jest to problem optymalizacji wielokryterialnej lub polioptymalizacji. Zagadnienia te są od dawna przedmiotem zainteresowania badaczy stosujących tradycyjne techniki optymalizacji i poszukiwania. Niedawno (Schaffer, 1984) do rozwiązania zadania optymalizacji wielokryterialnej użyto algorytmów genetycznych.
W przypadku jednego kryterium pojęcie rozwiązania optymalnego nie wymaga specjalnych wyjaśnień. Poszukujemy najlepszej (największej lub najmniejszej) wartości pewnej, z założenia dobrze określonej funkcji celu (reprezentującej użyteczność lub koszl). Natomiast przy optymalizacji wielokryterialnej pojecie rozwiązania optymalnego nie jest tak oczywiste. Jeżeli z góry nie zgadzamy się porównywać ze sobą wartości różnych kryteriów (powiedzmy, jabłek i pomarańczy), to musimy zaproponować taką definicję optymalności, która respektuje integralność każdego z nich. Przychodzi nam tu z pomocą pojęcie optymalności w sensie Pareto. Najlepiej zilustrować je na prostym przykładzie.
Przypuśćmy, że producent „widgetów" chciałby zminimalizować jednocześnie wypadkowość przy pracy i koszty produkcji. Obydwa te kryteria mają istotne znaczenie dla powodzenia jego przedsięwzięcia, a w dodatku konsekwencje wypadku niełatwo przeliczyć na dolary. Tak więc przykład ten jest dobrym kandydatem do optymalizacji wielokryterialnej. Przypuśmy następnie, że istnieje pięć możliwych wariantów organizacji procesu produkcji (scenariusze A, B, C, D i E), o następujących charakterystykach pod względem kosztu i wypadkowości: - ...
A = (2, 10) (koszt produkcji, liczba wypadków przy pracy) # = (4,6) C=(8,4) D = (9,5)
E=(1, 8)
Dane te są przedstawione na rys. 5.22 (wypadkowość w zależności od kosztów). Na pierwszy rzut oka wykres ten nie wydaje się być specjalnie pouczający: widać po prostu pięć chaotycznie rozmieszczonych punktów. Po chwili zastanowienia odkrywamy jednak, że najlepsze punkty znajdują się w obszarze położonym w dolnej i lewej części prostokąta. W szczególności scenariusze A, B i C sprawiają wrażenie dobrych kandydatów do wyboru: wprawdzie żaden nie jest optymalny ze względu na każde z dwóch kryteriów jednocześnie, ale decyzja wyboru któregoś z nich jest kwestią kompromisu -jeśli zyskujemy coś najednej osi, to tracimy na drugiej. W żargonie optymalizacyjnym mówi się, że te trzy punkty reprezentują rozwiązania niezdominowane, ponieważ nie istnieją żadne punkty, które byłyby lepsze ze względu na wszystkie kryteria jednocześnie. Z drugiej strony scenariusze D i E nie przedstawiają się jako atrakcyjni kandydaci. Jest tak dlatego, że obydwa rozwiązania są zdominowane przez jakieś inne. Scenariusz E (7, 8) jest zdominowany przez scenariusz B (4, 6), gdyż 4<7 i 6<8. A scenariusz D (9, 5) jest zdominowany przez C (8, 4), bo 8<9 i 4<5. Tak więc w tym zadaniu (i w innych zadaniach z wieloma kryteriami) zamiast jednej odpowiedzi otrzymujemy cały zbiór rozwiązań, z których żadne nie jest zdominowane przez drugie.
214
5. Techniki i operacje zaawansowane
Są to rozwiązania optymalne w s'ensie Pareto (P-optymalne). W rozważanym przypadku zbiorem scenariuszy P-optymalnychjest zbiór {A, B, C}. Patrząc od strony praktycznej, koncepcja optymalności w sensie Pareto nie daje wskazówek co do wyboru ostatecznego rozwiązania spośród P-optymalnych. Decydent jest w końcu zmuszony samodzielnie ocenić wszystkie warianty przed wydaniem werdyktu.
•o •w o
o
10-
A-(2. 10)
D
E-c, e> D
Q
C-(8. 4)
a
D-<9. 5)
a
Koszty produkcji
Rys. 5.22. Ilustracja problemu optymalizacji wielokryterialnej. Porównanie pięciu scenariuszy ze względu na wypadkowość i koszty produkcji. Scenariusze A, B \ C są niezdominowane
Warunek optymalności w sensie Pareto można w ścisłej postaci matematycznej sformułować następująco: Powiemy, że wektor*jest mniejszy (częściowo) od wektoraj>, wtedy i tylko wtedy, gdy
Mówimy wtedy również, że punktjjest zdominowany przez punktjc0. Jeżeli dany punkt nie jest zdominowany przez żaden inny, to nazywamy go punktem niezdominowa-nym. Będziemy używać tych podstawowych definicji, omawiając zastosowanie algorytmów genetycznych w zagadnieniach wielokryterialnych.
Pomysł zastosowania poszukiwania genetycznego w problemach wielokryterialnych datuje się od najwcześniejszych eksperymentów z algorytmami genetycznymi. Praca Rosenberga (1967) zawiera sugestie, które musiałyby logicznie doprowadzić do optymalizacji wielokryterialnej, gdyby autor zdecydował sięje zrealizować. Proponował on użycie wielu właściwości (odpowiadających pewnym kompozycjom składników chemi-
Autor używa zamiennie terminów punkt i wektor Q)rz.yp. tlum.).
5.5. Optymalizacja wielokryterialna
215
cznych) w symulacjach procesów genetycznych i biochemicznych zachodzących w populacji organizmówjednokomórkowych. W faktycznej implementacji Rosenberg ograniczył się jednak do tylko jednej właściwości, przez co jego pomysł może być uznany zaledwie za zapowiedź nadchodzących zdarzeń.
Praktyczna metoda została rozwinięta 17 lat później przez Schaffera (1984) wjego programie VEGA (Vector Evaluated Genetic Algorithm). Schaffer rozszerzył program GENESIS Grefenstette'a (1984a, b), dostosowując go do zadań wielokryterialnych. Program tworzył podpopulacje jednakowej wielkości, wewnątrz których była przeprowadzana selekcja ze względu na oddzielne kryteria w wektorze ewaluacji. Mimo że selekcja odbywała się niezależnie dla każdego kryterium, kojarzenie i krzyżowanie przekraczało granice podpopulacji. Schaffer zdawał sobie sprawę, że choć metoda taka jest łatwa w implementacji, to selekcja według niezależnych kryteriów wykazuje tendencję na niekorzyść osobników „pośrednich" (takich jak scenariusz B - dobrych ze względu na każde kryterium, ale nie najlepszych ze względu na żadne z nich). Stosował on różne heurystyki włącznie z redystrybucją dóbr i krzyżowaniem linii, próbując przezwyciężyć tę trudność, ale w końcu poprzestał na zwykłej niezależnej selekcji.
Schaffer przetestował program VEGA na zestawie siedmiu funkcji. Poprawność programu została sprawdzona na przykładzie funkcji F1 De Jonga. Dwie proste funkcje zostały zaczerpnięte z literatury na temat optymalizacji wielokryterialnej (Vincent i Grantham, 1981), a cztery inne - z literatury dotyczącej technik regulacji (zagadnienia identyfikacji z obiektami sterowanymi od drugiego do siódmego rzędu). Chcąc poznać typowe wyniki działania programu, rozważmy drugą funkcję Schaffera F2.
Jest to funkcja wektorowa o dwóch składowych, zależna od jednego parametru. Oznaczmy przez F21 pierwszą składową, przez F22 - drugą, a przez t - parametr:
F22(t)
•-. •.. . .:, 10 - - , .' • :..• .. •:.
F2l(t)
Rys. 5.23. Rzut drugiej funkcji Schaffera (F2) na płaszczyznę rozwiązań. Zaznaczono front Pareto punktów niezdominowanych
216
5. Techniki i operacje zaawansowane
F2,(f) = t2 F22(ł) = (t-
2)2
Rzut tej funkcji na płaszczyznę Pareto został pokazany na rys. 5.23, z zaznaczeniem frontu Pareto punktów niezdominowanych. Wszystkie inne punkty są zdominowane przez front i VEGA powinna umieć wyszukać dobre rozwiązania. Na rysunku 5.24 przedstawiono wyniki otrzymane przez program w pokoleniach 0 i 3. VEGA wykryła front; jednak widać pewną tendencje do ignorowania punktów pośrednich.
Legenda
Legenda
Of21(X) of22(X)
^^ Znacznik zdominowania
-6,00 -4,00
-2,00 0,00 2,00
X
Pokolenie 0
6,00
—1-------
-4,00
-2,00
0,00 2,1
x Pokolenie 3
4,00
6,00
Rys. 5.24. Rozwiązania drugiego zadania Schaffera otrzymane za pomocą programu VEGA. Porównanie pokoleń 0 i 3 (Schaffer, 1984). Przedruk za zezwoleniem
Zjawisko dyskryminacji rozwiązań pośrednich jest poważnym problemem. W żadnym pokoleniu nie powinno być tendencji skierowanej przeciwko jakimkolwiek lokalnie niezdominowanym osobnikom. Jeżeli uznajemy koncepcję optymalności w sensie Pareto, to wszystkie takie osobniki powinny posiadać ten sam potencjał reprodukcyjny. Jednym ze sposobów osiągnięcia jednakowego potencjału reprodukcyjnego dla wszystkich punktów na tym samym poziomie jest użycie specjalnej procedury sortującej. Jest ona podobna do procedur nadawania rang stosowanych dla pojedynczego kryterium (Baker, l985); jednak w tym przypadku rangi są związane ze „stopniem niezdomi-nowania". Wszystkie niezdominowane osobniki w bieżącej populacji zostają oznaczone, umieszczone na szczycie listy i otrzymują rangę 1. W następnym kroku rozpatrujemy
5.6. Techniki oparte na wiedzy .
217
pozostałą część populacji i wyszukujemy następną partię osobników niezdominowanych, nadając im rangę 2. Proces ten jest kontynuowany aż do nadania rang wszystkim osobnikom. Możemy wówczas przyporządkować każdemu osobnikowi - według jego rangi - liczbę potomnych kopii lub prawdopodobieństwo reprodukcji. Aby zapewnić utrzymanie dostatecznego zróżnicowania populacji, procedura ta powinna być używana łącznie z technikami formowania nisz i gatunków. Obecność nisz i gatunków może być szczególnie pomocna w stabilizowaniu licznych podpopulacji, które tworzą się wzdłuż frontu Pareto, dzięki czemu można uniknąć nadmiernej konkurencji między odległymi członkami populacji.
5.6. Techniki oparte na wiedzy
W całym dotychczasowym wywodzie - przez prawie pięć rozdziałów tej książki - uporczywie lansowaliśmy tezę, że istota działania algorytmów genetycznych sprowadza się do współdziałania reprodukcji i krzyżowania. W rozdziale pierwszym wymianę schematów-cegiełek o dużej wartości przystosowawczej między ciągami kodowymi porównaliśmy niejasno do procesów twórczego myślenia u ludzi. Przeprowadziliśmy mianowicie paralelę między wymianą schematów, prowadzącą do formowania nowych ciągów, a wymianą poglądów, prowadzącą do formowania nowych idei. Argumentacja ta wydawała się wówczas pociągająca, gdyż istotnie my, ludzie, zestawiamy ze sobą wartościowe pomysły w poszukiwaniu nowych idei. Z drugiej jednak strony pogląd, że krzyżowanie losowe to istota mechanizmu twórczego myślenia u ludzi wydaje się zdecydowanie zbyt uproszczony. Szukając nowych pomysłów, ludzie z całą pewnością wybierają w sposób bardziej świadomy koncepcje, z których skrzyżowania rodzą się nowe idee. Ludzie posługują się zasobem posiadanej wiedzy rozstrzygając, które poglądy mogą ze sobą współgrać, i oceniając (bez dokonywania bezpośrednich prób lub eksperymentów), czy efekt ich zestawienia ma dla nich jakiś sens. Inaczej mówiąc, operacje twórczego myślenia kierują się (przynajmniej od czasu do czasu) wiedzą. Algorytmy genetyczne - przeciwnie - są w swej najprostszej postaci procedurami ślepego poszukiwania: decydując o tym, jakie próby będą zadowalające w następnej turze, opierają się wyłącznie na własnościach funkcji kodującej i wartościach funkcji celu. Okoliczność ta jest jednocześnie błogosławieństwem i przekleństwem. Z jednej strony niewrażliwość na informację specyficzną dla zadania jest źródłem ich szerokiego zakresu zastosowań (metoda, która daje dobre wyniki bez uwzględniania szczegółowej wiedzy o danym problemie, ma znaczne szanse odniesienia sukcesu w innej dziedzinie). Jednak z drugiej strony, ignorując dostępną wiedzę o zadaniu, algorytmy genetyczne ustawiają się na niekorzystnej pozycji w porównaniu z konkurencyjnymi metodami, które czynią użytek z tej informacji.
W tym punkcie omówimy różne sposoby połączenia wiedzy szczegółowej o zadaniu z mechanizmami algorytmu genetycznego. Zbadamy techniki hybrydyzacji, operacje wzbogacone wiedzą i metody aproksymowania funkcji celu.
218
. 5. Techniki i operacje zaawansowane
5.6.1. Hybrydyzacja
Jeśli dysponujemy szczegółową wiedzą o zadaniu, to warto rozważyć połączenie algorytmu genetycznego z jakąś wyspecjalizowaną techniką poszukiwania. Hybrydyzacja umożliwia wykorzystanie „globalnego spojrzenia" algorytmu genetycznego zjednej strony i zbieżności techniki wyspecjalizowanej z drugiej. Rozwiązania takie były sugerowane przez licznych autorów (Bethke, 1981; Bosworth, Foo i Zeigler, 1972; Goldberg, 1983) - nie ma jednak zbyt wielu publikacji na temat osiągniętych w ten sposób wyników. Niemniej jednak sama idea jest prosta, ma merytoryczne uzasadnienie i może być stosowana w celu poprawy efektywności końcowej procesu poszukiwań genetycznych.
Optymalizacja lokalna funkcji ciągłych jednej lub wielu zmiennych jest dobrze rozwiniętą dziedziną wiedzy. Znane są liczne techniki gradientowe i niegradientowe znajdowania ekstremów lokalnych w tego typu zadaniach (Avriel, 1976). Aby skonstruować algorytm hybrydowy dla funkcji gładkiej, wystarczy po prostu „skrzyżować" preferowaną technikę lokalnego poszukiwania z algorytmem genetycznym. Algorytm genetyczny znajduje „wzgórze", a technika lokalna występuje w roli wspinacza, wdrapującego się na „szczyt".
Metody hybrydowe mogą być używane nawet w zadaniach nie poddających się technikom analitycznym. Na przykład algorytmy zachłanne (Lawler, 1976; Sysło, Deo i Kowalik, 1983) stanowią odmianę technik lokalnych w zadaniach optymalizacji kom-binatorycznej, a dla wielu typowych zadań istnieją dobrze rozwinięte metody heurystycz-ne. Specyficzność technik poszukiwania lokalnego powoduje, że dla każdego problemu lub klasy problemów musimy tworzyć odrębny algorytm hybrydowy. Nie możemy uciec od dylematu: efektywność czy ogólność. Jeżeli pragniemy korzystać z wiedzy szczegółowej, musimy być gotowi poświęcić nieco ogólności; na szczęście możemy tu w znacznej mierze zastosować podejście modularne.
Algorytm genetyczny
• elementarny
- zmodyfikowany
Metoda lokalna
• analityczna
• zachtenna
• inna
Rys. 5.25. Hybrydyzacja algorytmu genetycznego, podejście wsadowe. Algorytm genetyczny wyszukuje rejon wierzchołka, a procedura lokalna ,,wdrapuje się" na szczyt
I
5.6. Techniki oparte na wiedzy .
219
Istnieje wiele sposobów hybrydyzacji algorytmu genetycznego przy jednoczesnym zachowaniu istotnego poziomu modularyzacji. Na rysunku 5.25 zostało pokazane podejście „wsadowe". Przy tym podejściu algorytm genetyczny pracuje aż do osiągnięcia znacznego stopnia zbieżności populacji, a następnie włącza się procedura optymalizacji lokalnej, startując zjakichś 5-lO% najlepszych punktów ostatniego pokolenia. Można wtedy stosować także techniki niszowe i specjacyjne, opisane w poprzednim punkcie, w celu zapewnienia zróżnicowania populacji i powstania stabilnych podpopulacji związanych z różnymi maksimami lokalnymi funkcji.
Podejście równoległe do hybrydyzacji zostało przedstawione na rys. 5.26. Zakładamy tu dostępność wielu pracujących równolegle procesorów o mocy obliczeniowej wystarczającej do współbieżnego wyznaczania wartości funkcji dla poszczególnych ciągów kodowych w danym pokoleniu. Procesory współbieżne mogą być w ten sposób użyte do obliczania wskaźników przystosowania ciągów kodowych. Można ich również używać do wykonywania sporadycznych iteracji procedury lokalnego poszukiwania w celu ulepszenia bieżącego ciągu kodowego. (Więcej na temat równoległości w algorytmach genetycznych powiemy w jednym z następnych punktów.) ;
Rys. 5.26. Hybrydyzacja algorytmu genetycznego, podejście równoległe
Bardziej „kanoniczną" metodą lokalną, nadającą się do hybrydyzacji z algorytmem genetycznym, jest metoda iterowanych ulepszeń pozycyjnych [gradientlike-bitwise improvement, G-bit improvement]. Wjednej ze swych prac (Goldberg, 1983) wskazałem na podobieństwa między wykorzystaniem informacji o gradientach a zmianą poszczególnych bitów. Opierając się na tej idei, można otrzymać ogólną procedurę lokalnego poszukiwania, niezależną od struktury konkretnego zadania ł od sposobu kodowania rozwiązań. Metoda iterowanych ulepszeń pozycyjnych składa się z następujących trzech kroków: -v •• • <:•• ,
1. Wybierz jeden lub kilka najlepszych ciągów kodowych z bieżącej populacji.
2. Zmieniaj wartości kolejnych bitów w wybranym ciągu lub ciągach, zachowując za każdym razem lepszy z dwóch ostatnich wariantów.
3. Po zakończeniu powyższych działań włącz najlepszy znaleziony ciąg (lub k najlepszych ciągów) do populacji i kontynuuj zwykłe poszukiwanie genetyczne.
220
5. Techniki i operacje zaawansowane
Można pokazać, że metoda iterowanych ulepszeń pozycyjnych jest zbieżna do optymalnego rozwiązania dla każdej funkcji liniowej alleli. Można ją dodatkowo wzmocnić, zapamiętując historię udanych modyfikacji i wykorzystując tę informację przy podejmowaniu decyzji, czy w danej sytuacji opłaca się prowadzić dalsze próby ulepszeń. Inne rozszerzenie metody mogłoby polegać na eksperymentowaniu z parami lub trójkami bitów; należy tu jednak zachować ostrożność, aby nie doprowadzić do kombinatorycznej eksplozji złożoności nawet w przypadku ciągów o umiarkowanej długości.
5.6.2. Operacje wzbogacone wiedzą
Techniki hybrydowe stanowiąjeden ze sposobów wprowadzenia dodatkowej informacji, dzięki której można przyspieszyć proces poszukiwania genetycznego. Dodatkowej informacji można także użyć w celu lepszego ukierunkowania operacji genetycznych. Możemy w pewnym sensie mówić o „wspomaganiu" wiedzą szczegółową losowego wyboru podczas operacji takich, jak mutacja i krzyżowanie.
Pierwsze prace z tego zakresu dotyczyły mutacji. Bosworth, Foo i Zeigler (1972) użyli zmiennoprzecinkowej reprezentacji parametrów w wielowymiarowym zadaniu optymalizacyjnym oraz zastosowali operację krzyżowania (na styku parametrów) i kilka wariantów mutacji uwzględniających specyfikę zadania. Jeden z tych wariantów obejmował metodę FIetchera-Reevesa (metodę gradientów sprzężonych) w połączeniu z metodą złotego podziału. Podejście to przypomina nieco techniki hybrydowe omawiane w poprzednim punkcie.
Możliwość uwzględnienia wiedzy szczegółowej w sposobie działania operacji genetycznej nie ogranicza się do mutacji. Grefenstette, Gopal, Rosmaita i Van Gucht (1985) zaprojektowali heurystyczną, „zachłanną" operację krzyżowania dla zagadnienia komiwojażera (TSP). Przyjrzyjmy się metodom reprezentacji rozwiązań i operacjom, które zaproponowali wymienieni autorzy.
Rozważane przez nich sposoby reprezentacji obejmowały m. in. reprezentację porządkową [ordinal], ścieżkową \path] i opartą na relacji sąsiedztwa [adjacency]. W przypadku reprezentacji porządkowej jest tworzony uporządkowany „stos" zawierający nazwy jeszcze nie odwiedzonych miast, a reprezentacją trasy podróży jest po prostu aktualny numer pozycji (na stosie) miasta, które ma być odwiedzone w pierwszej kolejności. Zaletą reprezentacji porządkowej jest to, że operacja krzyżowania zachowuje trasy0. Wadą tej reprezentacji jest natomiast fakt, że drobne zmiany kodu mogą powodować kompletną reorganizację trasy podróży. W konsekwencji reprezentacja porządkowa nie wytwarza sensownych „cegiełek", czyli dobrych kandydatów do poszukiwania genetycznego. Inne reprezentacje, takie jak reprezentacja ścieżkowa (kolejne miasta na trasie) lub oparta na relacji sąsiedztwa (wartośćy na pozycji / oznacza, że miastoy' następuje po mieście /), dostarczają bardziej sensownych „cegiełek", ale operacja krzyżowania prostego, działając na dowolnej z tych reprezentacji, wytwarza sekwencje nie odpowiadające trasom. Aby się o tym przekonać, rozważmy przykładowe trasy w obu reprezentacjach.
Tzn. wynik krzyżowania dwóch tras jest zawsze dobrze określoną trasą (przyp. tłum.).
5.6. Techniki oparte na wiedzy .
221
W reprezentacji ścieżkowej trasa (1 3 5 4 2) biegnie od miasta 1 kolejno przez miasta 3, 5, 4 i 2 z powrotem do miasta 1. Widać wyraźnie, że krzyżowanie nie gwarantuje w tym przypadku uzyskania poprawnych tras potomnych. Jeżeli skrzyżujemy trasy (5 4 3 2 1) i (1 2 3 4 5) w punkcie krzyżowania 3, to otrzymamy ciągi potomne (5 4 3 4 5) i (1 2 3 1 2). W reprezentacji opartej na relacji sąsiedztwa mamy do czynienia z tym samym problemem. W tej reprezentacji ciąg (5 4 1 3 2) opisuje trasę biegnącą z miasta 1 do miasta 5, następnie z miasta 5 do miasta 2, z miasta 2 do miasta 4, z miasta 4 do miasta 3 i z miasta 3 z powrotem do miasta 1. Skrzyżowanie dwóch tras (5 4 1 3 2) i (2 3 4 5 1) w punkcie 3 daje w wyniku dwa ciągi (5 4 1 5 1) i (2 3 4 3 2), nie będące trasami. \
W obliczu tego problemu autorzy pracy zdecydowali się na reprezentację opartą na relacji sąsiedztwa oraz wymyślili heurystyczną operację krzyżowania (krzyżowanie zachłanne), która konstruuje trasę potomną, wybierając lepszą z dwóch krawędzi rodziciel-skich(Grefenstetteiin.,1985,str.l64): , ,- : •
Operacja ta konstruuje potomka z dwóch tras rodzicielskich w następujący sposób: Wybierz losowe miasto jako początek trasy potomnej. Porównaj dwie krawędzie wychodzące z wybranego miasta w trasach rodzicielskich i wybierz krótszą z nich. Kontynuuj próby przedłużenia trasy cząstkowej, wybierając krótszą z dwóch nadających się do tego krawędzi rodzicielskich. Jeżeli krótsza krawędź powoduje powstanie cyklu w trasie cząstkowej, to przedłuż ją wybierając losową krawędź. Kontynuuj to postępowanie aż do uzyskania pełnej trasy.
200 miast
Odlegtosc=1475,68 •>*•'<•••'•'•' Populacja początkowa
Rys. 5.27. Typowa trasa początkowa w zagadnieniu komiwojażera dla 200 miast (Grefenstette i in., 1985). Przedruk za zezwoleniem
222
5. Techniki i operacje zaawansowane
200 miast
Odlegtosc = 203,46
Pokolenie 493 24596 prób
Rys. 5.28. Zagadnienie komiwojażera dla 200 miast, najlepsza trasa w populacji 493 (końcowej). Metoda krzyżowania zachłannego (Grefenstette i in., 1985). Przedruk za zezwoleniem
Zastosowanie tej operacji w połączeniu z reprodukcją przyniosło dobre wyniki dla zadań obejmujących do 200 miast; otrzymano rozwiązania prawie optymalne przy nakładzie obliczeniowym tego samego rzedu, co w przypadku procedur symulowanego wyżarzania (Bonomi i Lutton, 1984; Kirkpatrick, Gelatt i Vecchi, 1983). Na rysunkach 5.27 i 5.28 porównano reprezentatywną trasę w populacji początkowej z najlepszą trasą w ostatnim pokoleniu dla zadania obejmującego 200 miast. Podejście to nie daje się bezpośrednio porównać z „czystymi" metodami omawianymi wcześniej w związku z operacjami re-konfiguracji. Krzyżowanie zachłanne korzysta w istotnym stopniu z wiedzy o odległościach między miastami. W przeciwieństwie do tego operacje PMX, OX i CX nie zależą od dodatkowej wiedzy szczegółowej i nie należy ich porównywać z operacjami, które wykorzystują taką informację.
5.6.3. Metody aproksymacyjne
W wielu przypadkach dysponujemy wiedzą szczegółową, która umożliwia skonstruowanie przybliżonego modelu zadania. To z kolei daje możliwość lepszego lub gorszego aproksymowania funkcji celu. Stosując algorytmy genetyczne, możemy wykorzystać z pożytkiem tę wiedzę w celu zredukowania liczby kosztownych obliczeń dokładnych wartości funkcji. W różnych zadaniach optymalizacji lub poszukiwania jednorazowe obliczenie wartości funkcji celu bywa złożonym procesem, obejmującym wiele poziomów podprogramów, obliczenia numeryczne lub symboliczne oraz rozmaite funkcje
5.6. Techniki oparte na wiedzy .
223
kodujące i dekodujące. Jeśli więc aproksymacja wartości funkcji przynosi oszczędności, umożliwiając przez to wykonanie większej liczby ewaluacji w tym samym czasie, to takie podejście może być warte zastosowania. Uwaga ta odnosi się szczególnie do algorytmów genetycznych, jako że zgodnie z naszymi oczekiwaniami powinny one wykazywać odporność na błędy i zakłócenia.
Mieliśmy już wcześniej okazję omówić pewną technikę przybliżonej ewaluacji funkcji, zastosowaną przez Grefenstette'a i Fitzpatricka (1985) w pracy dotyczącej odtwarzania obrazów. Przypomnijmy, że ewaluacja funkcji polegała tam na obliczeniu łącznej różnicy pikseli tworzących dwa obrazy -jednego sprzed, a drugiego po wstrzyknięciu środka cieniującego do tętnicy. Algorytm genetyczny miał za zadanie znalezienie współczynników przekształcenia dwuliniowego, które minimalizuje różnicę między obrazami. Obliczenia przeprowadzane w badaniach pilotowych były dość kosztowne, gdyż każdy obraz składał się ze 100x 100= 10000 pikseli. Po serii eksperymentów Grefenstet-te i Fitzpatrick przekonali się, że przy ustalonej łącznej liczbie operacji odejmowania pikseli (200000), najlepsze wyniki dały przybliżone ewaluacje funkcji, dokonywane na podstawie losowej próby złożonej z zaledwie 10 (spośród 10000) pikseli. Pomysł ten może być bezpośrednio zastosowany w innych przypadkach, w których wchodzi w grę próbkowanie wartości funkcji. Możemy również wykorzystać ogólną ideę aproksymowa-nia wartości funkcji w zagadnieniach charakteryzujących się bardziej tradycyjną struk-turąmatematyczną. .,;:
W wielu zagadnieniach optymalizacji dysponujemy dość dokładną wiedzą na temat matematycznej postaci zarówno modelu systemu, jak i funkcji celu. Wiedza ta umożliwia skonstruowanie stosunkowo „tanich" przybliżonych modeli systemu. Przypuśćmy, że mamy zmaksymalizować następującą „idealną" funkcję celu:
max/(s, d}
gdzie s jest «-wymiarowym wektorem stanu, d zaś m-wymiarowym wektorem decyzji. Załóżmy następnie, że matematyczny model systemujest dany przez równanie wektorowe
g(s, d) - 0, gdzie g jest n-wymiarową funkcją wektorową. fMi ,,:-,; ,
Tradycyjny sposób rozwiązania powyższego układu równań wiąże się zazwyczaj z serią przekształceń, podczas których należy odgadnąć (przybliżone) wartości zmiennych stanu, dokonać linearyzacji nieliniowego modelu i wyznaczyć nowe wartości zmiennych stanu. Po znalezieniu rozwiązania taką metodą nłetrudnojuż przeprowadzić analizę wra-żliwościrozwiązanianamałezaburzenia: ,,,,, ,;
A
As = -
ds
dd
Zmiany wektora stanu zostały tu wyrażone w postaci funkcji liniowej zmian wektora decyzji. Daje to możliwość obliczania liniowych poprawek do wartości funkcji celu, zgodnieznastępującąrównością: ,it-
224
5. Techniki i operacje zaawansowane
Możemy także obliczać dokładne wartości funkcji celu dla przybliżonych wartości zmiennych stanu. Jakąkolwiek metodę aproksymacji wybierzemy, musimy pamiętać, że każdy potomny ciąg kodowy ma dwoje rodziców, a zatem w obliczeniach przybliżonej wartości funkcji celu dla potomka powinniśmy systematycznie uwzględniać dane pochodzące od obydwu ciągów rodzicielskich. Można przy tym oprzeć się na:
a) najbliższym z rodziców;
b) średniej ważonej obu rodziców;
c) ostatnio ewaIuowanym rodzicu.
Zgodnie z tym, ciągi rodzicielskie mogą przekazywać potomkom swojejakobiany w celu propagacji przybliżonego modelu i przybliżonych wskaźników przystosowania. Obliczając poprawki do jakobianów, można starać się wydłużyć okres przydatności modelu liniowego. Istnieją też możliwości otrzymania lepszego modelu przybliżonego na podstawie danych z całej populacji, a nie tylko samych ciągów rodzicielskich. Techniki te nie zostały zastosowane w praktyce; powinny onejednak otworzyć drogę do zwiększenia konkurencyjności metod poszukiwania genetycznego w sytuacji, kiedy naturalny proces modelowania prowadzi do konstrukcji modelu zlinearyzowanego.
5.7. Algorytmy genetyczne a architektura równoległa____________________
Jest wielkim paradoksem, że w świecie, w którym algorytmy sekwencyjne przekształca się w równoległe, zazwyczaj dzięki niezliczonym trikom i łamańcom, algorytmy genetyczne (z natury w wysokim stopniu równoległe) są realizowane sekwencyjnie za pomocą równie nienaturalnych chwytów. Musi więc dziwić fakt, że aż do niedawna bardzo niewiele wysiłku poświęcano implementacji algorytmów genetycznych w sposób wykorzystujący istniejące lub projektowane równoległe architektury sprzętowe. W tym punkcie zajmiemy się więc współbieżnymi implementacjami algorytmów genetycznych.
Holland w jednej z najwcześniejszych prac teoretycznych (1962c) rozpoznał współbieżną naturę paradygmatu reprodukcyjnego i inherentną efektywność przetwarzania równoległego. Posunął się on nawet do rozważań nad realizacją planów reprodukcyjnych za pomocą pewnego modelu komputera komórkowego (1959, 1962).
Inni dawniejsi badacze nie poświęcili wiele uwagi możliwościom, jakie niosły współbieżne implementacje algorytmów genetycznych. Bethke (1976) podał różne oszacowania złożoności dla określonych sposobów realizacji algorytmu genetycznego na maszynie równoległej. Doszedł on do wniosku, że podstawowe wąskie gardło ówczesnych realizacji będzie stanowić obliczenie średniego wskaźnika przystosowania populacji. Nie próbował jednak zasymulować ani zaimplementować współbieżnego algorytmu genetycznego.
5.7. Algorytmy genetyczne a architektura równoległa
225
Grefenstette (1981) rozważał kilka współbieżnych implementacji algorytmów genetycznych. Przedstawił on w szczególności w zarysie cztery następujące projekty organizacji algorytmu: . « , > < •
a) synchroniczna scentralizowana; '* s
b) półsynchroniczna scentralizowana; . • • • -.
c) asynchroniczna rozproszona; •> ^ •<
d) sieciowa. . -. , ' '
Organizacja synchroniczna scentralizowana została już wcześniej przedstawiona na rys. 5.26. Mamy tu do czynienia z jednym procesem nadrzędnym, który koordynuje k procesów podrzędnych. Proces nadrzędny odpowiada za selekcję, kojarzenie oraz wykonywanie operacji genetycznych. Procesy podrzędne obliczają natomiast wskaźniki przystosowania. Organizacja tajest przejrzysta i dość łatwa do realizacji, majednak dwie zasadnicze słabości. Po pierwsze duża wariancja czasu niezbędnego do obliczenia wskaźników przystosowania powoduje duże straty. Po drugie niezawodność algorytmu zależy bezpośrednio od niezawodności procesu nadrzędnego. Jeśli ten zawiedzie, cały system zatrzyma się. Odpowiedzią na pierwszą trudność jest drugi projekt Grefenstette'a, or-ganiz'dC)apolsynchroniczna scentralizowana. Wymóg synchroniczności został tu zniesiony - elementy populacji są wstawiane i selekcjonowane na bieżąco, gdy tylko odpowied-ne procesy podrzędne zakończą swoją pracę. Mechanizm ten działa podobnie do populacji mieszanych De Jonga ze współczynnikiem wymiany G (rozdział 4). Organizacja półsynchroniczna scentralizowana jest również zawodna ze względu na zależność od zachowania jednego wyróżnionego procesu.
W asynchronicznym rozproszonym algorytmie genetycznym (przedstawionym schematycznie na rys. 5.29) k identycznych procesorów wykonuje niezależnie od siebie zarówno operacje genetyczne, jak i obliczenia wskaźników przystosowania, korzystając
Proces współbieżny N Proces współbieżny / Proces współbieżny
•^ i k \ ' A
Proces współbieżny Pamięć dzielona Proces współbieżny
\
^ r , i ^ L
Proces współbieżny Proces współbieżny Proces współbieżny
Rys. 5.29. Organizacja współbieżnego asynchronicznego algorytmu genetycznego
226
5. Techniki i operacje zaawansowane
ze wspólnej pamięci dzielonej. Dostęp do pamięci dzielonej jest ograniczony jedynie warunkiem, aby procesy nie odwoływały się jednocześnie do tego samego miejsca w pamięci; poza tym nie ma tu innych wymagań synchronizacyjnych. Organizacja ta jest nieco bardziej skomplikowana niż dwie poprzednie, ale niezawodność systemu znacznie wzrasta. Dopóki bowiem działa choć jeden z procesów współbieżnych i jakaś część pamięci dzielonej, dopóty wykonywanie algorytmu posuwa się naprzód.
Organizacja sieciowa została pokazana na rys. 5.30. W tym przypadku k niezależnych algorytmów genetycznych (obejmujących operacje genetyczne i obliczanie wskaźników przystosowania) wykonuje się, korzystając z własnych, niezależnych pamięci. Owe k procesów działa autonomicznie z wyjątkiem tego, że najlepsze osobniki wykryte w danym pokoleniu są rozsyłane do innych podpopulacji poprzez sieciowy system komunikacyjny. Oznacza to znaczną redukcję potrzeb komunikacyjnych w stosunku do innych organizacji. System osiąga wysoką niezawodność dzięki autonomiczności niezależnych procesów.
Rys. 5.30. Organizacja sieciowego algorytmu genetycznego
Niedawno zasugerowałem podejście obiektowe do implementacji współbieżnego algorytmu genetycznego. Rozpatrujemy tu dwa modele implementacyjne: model wspólnotowy [community] oraz modelpylkowy fc>lantpollination]. Model wspólnotowy został naszkicowany na rys. 5.31. Algorytm genetyczny jest tam rozdystrybuowany pomiędzy zbiór połączonych ze sobą „wspólnot". W skład wspólnot wchodzą domy przyłączone do centralnych, połączonych wzajemnie miast. Rodzice produkują potomstwo w swoich domach i tam też wyznacza się wskaźniki przystosowania. Dzieci są następnie wysyłane do centralnego klubu młodzieżowego (w mieście), gdzie spotykają się ze swymi przyszłymi partnerami. Po zawarciu związku pary udają się do agencji handlu nieruchomościami, by znaleźć dla siebie dom. Domy są oferowane ubiegającym się o nie parom w drodze przetargu. Jeśli miasto jest aktualnie przeludnione, pary mogą się zwrócić do agencji o znalezienie domu w innych wspólnotach i w razie potrzeby udają się na dworzec autobusowy, aby przenieść się do innej wspólnoty.
5.7. Algorytmy genetyczne a architektura równoległa
227
Wspólnota
Rys. 5.31. Podejście obiektowe, model wspólnotowy algorytmu genetycznego
Model pyłkowy składa się z sieci „roślin" połączonych kanałami przenoszącymi „pyłek" (rys. 5.32). Ziarna kiełkują i rozwijają się w dojrzałe rośliny wytwarzające pyłek, który jest roznoszony po całej sieci. Z każdym kanałem sieci związane jest praw-
Kanaty pyłkowe
Rys. 5.32. Podejście obiektowe, model pyłkowy algorytmu genetycznego
228
5. Techniki i operacje zaawansowane
dopodobieństwo transmisji pyłku. Umożliwia to tworzenie podpopulacji roślin izolowanych w mniejszym lub większym stopniu od innych. Pyłek zapyla dojrzałe rośliny, powodując powstanie nowych ziaren. Najlepsze ziarna zostają lokalnie wyselekcjonowane (w sposób probabilistyczny) do kiełkowania, aby przekształcić się w dojrzałe rośliny.
Chociaż opisane modele obiektowe mogą wydać się zabawne, a nawet nieco fry-wolne, to zostały pomyślane jak najbardziej poważnie. Traktując każdą składową procesu jako obiekt łatwiej możemy określić ich zapotrzebowanie na moc obliczeniową, wielkość pamięci i przepustowość kanałów komunikacyjnych. Dzięki temu powinniśmy być zdolni do efektywniejszej implementacji algorytmu genetycznego we współbieżnych systemach komputerowych.
W ostatnim czasie pojawiło się kilka doniesień o symulacjach i implementacjach współbieżnych (Jog i Van Gucht, 1987; Pettey, Leuze i Grefenstette, 1987; Suh i Van Gucht, 1987b; Tanese, 1987). Należy się spodziewać dalszego rozkwitu tego kierunku badań, w miarę upowszechniania się sprzętu o architekturze równoległej i odpowiedniego oprogramowania wspomagającego.
5.8. Podsumowanie
W tym rozdziale omówiliśmy niektóre zaawansowane operacje i techniki służące usprawnieniu elementarnego algorytmu genetycznego. Na początek rozważyliśmy rozmaite mikrooperacje, tj. operacje genetyczne działające napoziomie chromosomu, obserwowane w przyrodzie. Omówiliśmy kolejno: mechanizm dominowania i diploidalność, operacje rekonfiguracji, segregację, translokację, duplikację i delecję.
Diploidalność w połączeniu z dominowaniem zostały rozpatrzone jako metoda implementacji pamięci długoterminowej. Zarówno teoria, jak i wyniki symulacji wskazują na przydatność takiego podejścia w przypadku niestacjonarnych, a szczególnie periodycznych funkcji przystosowania.
Omówiliśmy również teorię i realizacje operacji rekonfigurujących. Zastosowanie tych operacji wymaga wprowadzenia numeracji alleli (rozszerzonej reprezentacji). Omówiliśmy operacje jednoargumentowe, takie jak inwersja, oraz dwuargumentowe, jak PMX, OX i CX. Teoria schematów daje się uogólnić na przypadek schematów porządkowych, związanych z operacjami rekonfiguracji. Zaproponowaliśmy klasyfikację schematów porządkowych (o-schematów), obejmującą schematy bezwzględne, względne, z poślizgiem i zamianą.
Rozważyliśmy także inne operacje niskopoziomowe, jak segregacja i translokacja. Wymagają one rozszerzenia genotypu do postaci struktury wielochromosomowej. Ponadto duplikacja i delecja pociągają za sobą konieczność wprowadzenia reprezentacji o zmiennej długości. Omówiliśmy też proces zróżnicowania płciowego i rolę, jaką może on odgrywać (umożliwienie kooperacji i specjalizacji wewnątrzgatunkowej).
Makrooperacje - operacje działające na poziomie populacji - umożliwiają z kolei różnicowanie prowadzące do tworzenia się nisz i powstawania gatunków. Podstawowe koncepcje teoretyczne, koncentrujące się wokół idei podziału zasobów i barier reproduk-
5.9. Zadania
229
cyjnych, doprowadziły nas do rozważenia pewnych rozwiązań praktycznych. Zjawisko formowania się nisz można wywołać dzięki zastosowaniu technik tworzenia ścisku lub użyciu funkcji współudziału. Natomiast specjację można uzyskać w wyniku wprowadzenia barier reprodukcyjnych (sztywnych lub adaptacyjnych).
Omówiliśmy następnie pokrewny temat optymalizacji wielokryterialnej. Przedstawiliśmy w zarysie koncepcję optymalności w sensie Pareto (rozwiązań niezdominowa-nych). Rozważyliśmy także metody selekcji opartej na wielu kryteriach. Selekcja według niezależnych kryteriów prowadzi do dyskryminacji rozwiązań „pośrednich". Użycie procedury sortującej populację według stopnia niezdominowania osobników powinno złagodzić tę trudność, ale jak dotąd nie wypróbowano praktycznie tej metody. v ;;
Przedyskutowaliśmy trzy nurty technik opartych na wiedzy: hybrydyzację, operacje wzbogacone wiedzą i metody aproksymowania funkcji celu. Techniki te umożliwiają wykorzystanie wiedzy szczegółowej, dostępnej w wielu zadaniach poszukiwania i optymalizacji.
Na koniec omówiliśmy zagadnienie implementacji algorytmów genetycznych w sprzęcie o architekturze równoległej. Zakrawa na ironię fakt, że pomimo współbieżnego charakteru naturalnych procesów genetycznych, w literaturze na temat przetwarzania współbieżnego nie poświęcono dotąd większej uwagi algorytmom genetycznym . Dopiero teraz teoretyczne i praktyczne badania w tym kierunku zaczynają wzbudzać większe zainteresowanie.
Pod wieloma względami udało nam się zaledwie musnąć problematykę stosowanego poszukiwania genetycznego. Opisane tu zaawansowane techniki i operacje powinny w praktyce doprowadzić do dalszego usprawnienia i rozszerzenia zakresu zastosowań algorytmów genetycznych. ,;..« ,, . >
5.9. Zadania
5.1. Chromosom haploidalny składa się z jednego genu o dwóch allelach, 1 i 0. Wartość oczekiwana przystosowania wynosi/, = 1,5 dla allelu 1, af0= 1,2 dla allelu 0. Zakładając, że nie występują straty z tytułu mutacji oraz że populacja zawiera początkowo równą liczbę obu rodzajów alleli, oblicz następujące wielkości:
a) oczekiwaną frekwencję allelu 1 w pokoleniu 1,
b) oczekiwaną liczbę pokoleń potrzebnych do osiągnięcia co najmniej 99-procen-towej frekwencji jedynek.
5.2. Wykonaj te same obliczenia, co w zadaniu 5.1 dla populacji diploidalnej, zakładając, że allel 1 jest dominujący, a dane dotyczące przystosowania odnoszą się do alleli ujawnionych.
5.3. Załóżmy, że współczynnik strat dla pewnego allelu wynosi 50%. Wyznacz tempo mutacji niezbędne do utrzymania l-procentowej frekwencji tego allelu w populacji haploidalnej i w populacji diploidalnej. Oblicz oczekiwaną częstość wyboru postaci recesywnej podczas reprodukcji.
230
5. Techniki i operacje zaawansowane
5.4. Pewna trasa ma reprezentację ścieżkową (2 1 4 3 7 6 5 9 8 0). Wykonaj dla niej operację inwersji z punktami podziału 3 i 5. Wyznacz dolne ograniczenie prawdopodobieństwa przeżycia przy inwersji dla schematu [5!8] traktowanego jako: bezwzględny o-schemat, względny o-schemat, względny o-schemat z poślizgiem oraz względny o-schemat z poślizgiem i zamianą.
5.5. Oblicz całkowitą liczbę o-schematów (bezwzględnych) dla ciągów kodowych długości /=10, 20,50i 100.
5.6. Rozwiń o-schemat r12(2!18) na bezwzględne o-schematy, przy założeniu struktury kołowej.
5.7. Rozwiń względny o-schemat z poślizgiem ry^(2134) na o-schematy względne.
5.8. Zakładając, że w wyniku duplikacji wewnątrzchmosomowej w danym genotypie pojawiło się sześć egzemplarzy danego allelu, a prawdopodobieństwo mutacji dla pojedynczego allelu wynosi 0,05, oblicz prawdopodobieństwo, że mutacja dotknie 0, 1, 2, 3, 4, 5 i 6 egzemplarzy tego allelu. Podaj wyniki dokładne oraz przybliżone (korzystając z rozkładu Poissona).
5.9. Operacja translokacji polega na podziale chromosomu w losowo wybranym punkcie (z jednakowym prawdopodobieństwem) i dołączeniu odciętego odcinka do innego chromosomu w obrębie tego samego genotypu. Oszacuj prawdopodobieństwo rozdzielenia dwóch alleli odległych od siebie o pięć pozycji w ciągu o długości 25. Prawdopodobieństwo zajścia translokacji wynosi 0,3.
5.10. Obmyśl mechanizm reprodukcji płciowej (z użyciem genu płci), który wytwarza trzy płci: męską, żeńską i nijaką w stosunku 2:1:5. Podaj naturalne przykłady gatunków różnicujących się więcej niż o dwie płci.
5.11. Dla dwójkowego problemu decyzyjnego z wypłatami/, = 10 przy decyzji 1 i^o = 5 przy decyzji 0, oblicz oczekiwaną liczbę decyzji 1 w następnym pokoleniu, jeśli zastosowano zwykłą metodę reprodukcji: a) bez podziału wypłat, b) z (równym) podziałem wypłat. Przyjmij, źe bieżąca populacja zawiera 70 jedynek i 30 zer.
5.12. W pewnej metodzie kojarzenia opartej na wzorcach kojarzeniowych dopuszcza się częściowe dopasowanie, jeśli brak pełnego dopasowania. Obmyśl miarę dopasowania, przy której pełne dopasowanie otrzymuje wyższą ocenę niż jakiekolwiek częściowe dopasowanie.
5.13. Metoda selekcji wielokryterialnej Schaffera (1984) faworyzuje rekordzistów ze względu na jedno kryterium. Czy w przypadku zadania minimalizacji rodzi to większe problemy dla wklęsłego czy dla wypukłego frontu Pareto? Uzasadnij krótko swoją odpowiedź.
5.14. Rozważmy zadanie maksymalizacji funkcji celu f(x, y)=x2+y2 na krzywej y=x* + 3x + 6 (model systemu). Znajdź przybliżenia liniowe obu funkcji w punkcie (x(), y0). Rozważ dwie metody kombinacji modeli przybliżonych umożliwiające propagację modelu przybliżonego bez konieczności dokonywania dodatkowych ewaluacji funkcji. ,
i
5.10. Ćwiczenia komputerowe
231
5.10. Ćwiczenia komputerowe
A. Zaimplementuj elementarny algorytm genetyczny z diploidalnością i triallelłcznym mechanizmem dominowania.
B. Zaprogramuj i przetestuj operację CX dla reprezentacji permutacyjnej.
C. Zaprogramuj i przetestuj operację inwersji traktującą permutacje jako struktury kołowe.
D. Opracuj metodę kodowania niechlujnego dla zagadnienia komiwojażera, w której dopuszcza się nadmiarowe wystąpienia miast w reprezentacji ścieżkowej. Obmyśl i przetestuj procedurę dekodowania takiej niechlujnej reprezentacji.
E. Zaprogramuj i przetestuj operację OX dla reprezentacji permutacyjnej.
F. Zaprogramuj algorytm genetyczny z dwoma mechanizmami tworzenia nisz: metodą ścisku De Jonga i metodą funkcji współudziału Goldberga-Richardsona. Porównaj i omów wyniki uzyskane przy zastosowaniu obu mechanizmów dla wybranej funkcji wielomodalnej.
G. Zaprogramuj metodę wzorców kojarzeniowych Bookera i Hollanda. Zaimplementuj reguły zgodności dwustronnej i jednostronnej w postaci przełączalnych opcji programu.
H. Zastosuj wielokryterialny algorytm genetyczny do optymalizacji drugiej funkcji Schaffera (rys. 5.23 i 5.24). Posłuż się dwiema metodami selekcji: metodą niezależnych kryteriów Schaffera i metodą sortowania wg stopnia niezdominowania Goldber-ga. Porównaj i omów otrzymane wyniki.
I. Zaimplementuj metodę iterowanych ulepszeń pozycyjnych. Porównaj i omów efektywność on-line \ off-line uzyskane dla funkcji De Jonga F\ \ F5 w eksperymentach bez użycia i z użyciem tej metody.
J. Użyj elementarnego algorytmu genetycznego do rozwiązania problemu optymalizacji postawionego w zadaniu 5.14. Zaprogramuj metodę przybliżonej ewaluacji funkcji i rozwiąż ponownie ten sam problem. Porównaj wyniki otrzymane dla dokładnej i przybliżonej ewaluacji funkcji.
Wyszukiwarka
Podobne podstrony:
05 Wykonywanie operacji obrĂłbki skrawaniem
05 Wykonywanie operacji obrĂłbki skrawaniemidX76
05 Techniki projekcyjne
Debugowanie NET Zaawansowane techniki diagnostyczne?bnet
Techniki negocjacji i mediacji w administracji wykłady 05 11 2013
technik rolnik21[05] o1 02 n
05 SporzÄ…dzanie rysunku technicznego odzieĹĽowegoidX36
technik rolnik21[05] z3 02 n
technik rolnik21[05] o2 04 n
technik rolnik21[05] z2 01 n
Technik mechatronik11[50] Z1 05 u
05 Posługiwanie się dokumentacją techniczną (2)
MS Access 2000 PL Zaawansowane techniki programowania
więcej podobnych podstron