Wykład 5.
Zapobieganie przedwczesnej zbieżności

O przedwczesnej zbieżności mówi się, gdy algorytm ewolucyjny traci zdolność przeszukiwania przestrzeni chromosomów przed osiągnięciem maksimum globalnego. Zjawisku temu nie sposób zapobiec całkowicie, gdyż wynika z nacisku selektywnego; możnajejednak ograniczać, stosując techniki przedstawione w wykładzie: połączenie algorytmu ewolucyjnego i przeszukiwań lokalnych, techniki związane z czasem życia osobników, metody deformujące funkcję przystosowania, mechanizmy uzależniające nacisk selektywny nie tylko od przystosowania osobnika, lecz także od jego genotypu. Przedstawiono różne aspekty równoległości w algorytmach ewolucyjnych. Wspomniano także dwa słabo poznane zagadnienia wpływ metody inicjacji populacji bazowej na odporność algorytmu ewolucyjnego oraz związek między odpornością a licznością populacji.

5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych

W wykładzie 3 zakładaliśmy, że istnieje idealny algorytm optymalizacji lokalnej, który każdemu chromosomowi znajdującemu się w obszarze przyciągania maksimum lokalnego funkcji przystosowania przyporządkowuje to maksimum. Jeśli dysponujemy takim algorytmem, to można go wykorzystać w prostej meto- *Poiega ona na wieiokrot-dzie wielostartowej*. Takie postępowanie jest jednak bardzo cza- nym8eneraw3niu]050weg�
j f Yf j J genotypu i uruchamianiu
SOChlOnne. dlań algorytmu optymaliza-
W praktyce nie zawsze dysponujemy idealnym algorytmem cJ'lokalneJ- R�związamem
r J J r J J J o j je5t najlepszy punkt znale-
optymalizacji lokalnej najczęściej jest on mało precyzyjny, ziony w serii uruchomień.
.196.
5. Zapobieganie przedwczesnej zbieżności
"Klasyczny" algorytm ewolucyjny również jest mało precyzyjny wprawdzie dość szybko lokalizuje "obiecujące" obszary zbioru dopuszczalnego, lecz wyznaczenie dobrego przybliżenia maksimów jest bardzo żmudne. Na podstawie powyższych obserwacji powstała idea połączenia nieprecyzyjnego algorytmu ewolucyjnego z nieodpornymi (i również nieidealnymi) metodami optymalizacji lokalnej. Jak wynika z różnych publikacji, takie połączenie prowadzi nierzadko do uzyskania algorytmu hybrydowego o właściwościach lepszych od właściwości metod wchodzących w jego skład.
Idea połączenia algorytmu ewolucyjnego z algorytmem optymalizacji lokalnej sprowadza się do tego, że punkty startowe tego ostatniego nie są generowane losowo, lecz ewolucyjnie. Powszechnie są stosowane dwa sposoby wykonania takiego algorytmu hybrydowego pierwszy polega na wprowadzeniu dodatkowego operatora genetycznego, który uruchamia algorytm optymalizacji lokalnej, w drugim zaś algorytm taki jest jednym z elementów odwzorowania genotypu w fenotyp.
Przeszukiwanie lokalne jako jeden z operatorów genetycznych. Przeszukiwanie lokalne jest chętnie traktowane jako jedna z metod mutacji. Chromosom mutowanego osobnikajest punktem startowym, wynikiem zaś jest modyfikacja chromosomu w taki sposób, że odpowiada on wyznaczonemu metodą optymalizacji lokalnej ekstremum lokalnemu. Można posłużyć się dowolną metodą, polegającą na przekształcaniu jednego punktu roboczego. Atutem takiego schematu hybrydowego jest możliwość skorzystania z informacji, którą pomija się, korzystając z klasycznego schematu ewolucyjnego, na przykład gradientu funkcji przystosowania. Dodatkową zaletę schematu hybrydowego stanowi fakt, że optymalizacja lokalna nie musi być dokładna wystarczy, że wykona się kilka pierwszych kroków algorytmu optymalizacji lokalnej, tak aby tylko przyspieszyć proces przybliżania do maksimum.
Znane są również próby wprowadzenia metod optymalizacji lokalnej jako uogólnienia operatorów krzyżowania. Przykładem może być krzyżowanie wieloosobnicze, w którym bierze udział n +1 osobników. Krzyżowanie przebiega jak pojedynczy krok metody pełzającego sympleksu Neldera-Meada.
Przeszukiwanie lokalne za pomocą operatorów genetycznych zastosowane w algorytmie ewolucyjnym niejest, niestety, wolne od wad. Zauważmy, że w odróżnieniu od omawianych wcześniej operatorów, polegających na losowym próbkowaniu (i najlepiej nie-obciążonych), przeszukiwanie lokalne wprowadza obciążenie operatora z tendencją do preferowania obszarów przyciągania maksimów lokalnych stanowi zatem w algorytmie ewolucyjnym dodatkowe źródło nacisku selektywnego. Takie zaburzenie równowagi
5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych
.197.
eksploracji i eksploatacji wymaga równoważenia poprzez, na przykład, wprowadzenie dodatkowych operatorów genetycznych powodujących znaczną różnorodność populacji losowej, a także wykorzystanie mechanizmów selekcji słabo ukierunkowujących algorytm. Można sobie także wyobrazić rozwiązanie, w którym prawdopodobieństwo mutacji (lub krzyżowania) wykonanej za pomocą metody przeszukiwań lokalnych zwiększa się w kolejnych generacjach*.
Przeszukiwanie lokalne wykonywane podczas obliczenia przystosowania osobnika. Druga możliwość wprowadzenia metody optymalizacji lokalnej polega na zmianie sposobu obliczania wartości funkcji przystosowania. Fenotyp x odpowiadający chromosomowi X, którego przystosowanie jest obliczane, stanowi punkt startowy takiej metody. Wynikiem jej wykonania jest najczęściej odmienny fenotyp y. Oceniając osobnika X, mamy do dyspozycji dwa fenotypy pierwotny i zmodyfikowany. Powstaje pytanie: czy jest możliwe wykorzystanie tej dodatkowej informacji w algorytmie ewolucyjnym i jaki wpływ będzie to miało na jego działanie? Możliwe są dwa podejścia, związane z dwoma różnymi koncepcjami ewolucji lamarkowską oraz darwinowską (z tym drugim jest związany tzw. efekt Baldwina); oba podejścia omówiono poniżej.
5.1.1. Efekt Baldwina i ewoiucja lamarkowska
Sposób tworzenia cech osobnika nabytych wskutek interakcji ze środowiskiem jest analogiczny do obliczania wartości funkcji przystosowania osobnika poprzedzonych uruchomieniem algorytmu optymalizacji lokalnej w algorytmie hybrydowym. Oprócz wyjściowego chromosomu X (dla którego możemy obliczyć wartość funkcji przystosowania $(X) na podstawie jego fenotypu x i wartości funkcji celu /(x)) dysponujemy nowym fenotypem y, utworzonym wskutek działania metody optymalizacji lokalnej. Przystosowanie osobnika jest wyznaczone na podstawie wartości funkcji celu "poprawionego" fenotypu. W literaturze najczęściej są przedstawiane trzy (z możliwych czterech) sposoby postępowania w takiej sytuacji:
1) wartości y i f(y) sa zapamiętywane przez procedurę monito- *Patrz tei metody stro-
' . . J l w ' \ . f J . ^ ^ , ^ , jenia prawdopodobieństw
rującą algorytm ewolucyjny, lecz nie są wprowadzane do popu- operatorów genetycznych.
laCJi baZOWej**, **Wartości y i /(y) są na-
2) wartość (/(y)) jest traktowana jako wartość przystosowania tomiast brane p�duwag?
' t \J w '* J J c J przyocenianiuwyniKowge-
OSObniKcl J^., nerowanych przez algorytm
3) znajduje się genotyp Y = F~l(y), odpowiadający zmodyfi- ��i"cyjnyimogąbyćwy-
/ j J Y o Jf W/> t- J~e J J korzystanewkryteriumza-
kowanemu fenotypowi, i nowym chromosomem osobnika staje trzymania.
.198.
5. Zapobieganie przedwczesnej zbieżności
się Y zamiast X; podobnie postępuje się z wartością funkcji przystosowania.
Pierwszy ze sposobów jest neutralny dla algorytmu ewolucyjnego może mieć co najwyżej wpływ na kryterium zatrzymania, drugi jest określany mianem efektu Baldwina, trzeci zaś to model ewolucji lamarkowskiej. .";,, < .,-� ,.
Efekt Baldwina. W algorytmach ewolucyjnych efekt Baldwina7 polega na przypisaniu osobnikowi wartości funkcji przystosowania, którajest wynikiem działania metody optymalizacji lokalnej, modelującej proces adaptacji fenotypowych cech osobnika do warunków środowiskowych. Oznacza to, że czynności związane z eksploatacją są w kompetencji metody optymalizacji lokalnej, działającej w przestrzeni fenotypu, przypisującej chromosomowi wartość funkcji przystosowania tego maksimum lokalnego (lub jego przybliżenia), w którego obszarze przyciągania znajduje się fenotyp ocenianego osobnika. W efekcie, z punktu widzenia ewoluujących osobników, funkcja przystosowania przybiera postać wielu płaskowyżów, z których każdy pokrywa się z obszarem przyciągania maksimum lokalnego (rys. 5.1)*. Dzięki temu wszystkie osobniki znajdujące się w obszarze przyciągania jednego maksimum lokal-
*(X)
Oryginalna funkcja przystosowania
Funkcja przystosowania powstała wskutek efektu Baldwina '
0
X
*Jest tak wówczas, gdy zachodzi zgodność przestrzeni fenotypu i genotypu. W przeciwnym przypadku, w obszarze przyciągania maksimum lokalnego może być wiele płaskowyżów, jak również jeden płaskowyż może obejmować obszary przyciągania wielu maksimów lokalnych.
RYSUNEK 5.1. Funkcja przystosowania wstandardowym modelu ewolucji i odpowiadająca jej funkcja przystosowania w podejściu baldwinowskim
7Baldwin byl jednym z amerykańskich ewolucjonistów, szczególnie zainteresowanym mechanizmami rządzącymi korelacją pożądanych cech rodziców i potomstwa. Doszedł do wniosku, że genotyp osobnika określa jego predyspozycje, które w wyniku doświadczeń, oddziaływań środowiska i uczenia prowadzą do modyfikacji fenotypu i zwiększenia przystosowania. Tak więc nie dziedziczenie cech nabytych, ale zaledwie predyspozycji, jest przyczyną występowania wspólnych cech rodziców i potomstwa.
5.1. Algorytm ewolucyjny i metoda przeszukiwań lokalnych
.199.
\ \
0 2 chromosomy 3 chromosomy X\
:< '" '"' " '' (b)
RYSUNEK 5.2. Stan populacji: a) po wykonaniu reprodukcji i operacji genetycznych (liniami przerywanymi wskazano maksima lokalne, do których chromosom zostanie "ściągnięty" w wyniku działania metody optymalizacji lokalnej), b) po dokonaniu ewolucji lamarkowskiej. Widoczny zanik różnorodności populacji
nego mają jednakową wartość funkcji przystosowania, a to z kolei oznacza, że mogą dość łatwo zbliżyć się do brzegu obszaru przyciągania tego maksimum i go opuścić*.
Ewolucja lamarkowska. W algorytmach ewolucyjnych lamar-kizm8 polega na tym, że dla znalezionego wskutek uruchomie-
8Lamarkizm jest hipotezą rozwoju gatunków polegającą na dziedziczeniu cech nabytych w trakcie życia osobniczego. Sformułował ją Lamarck, biolog francuski żyjący w XIX wieku. Współczesny ewolucjonizm odrzuca ten pogląd ze względu na brak dowodów przemawiających za istnieniem mechanizmów modyfikacji genotypów komórek rozrodczych na podstawie adaptacji całego organizmu. Niezależniejednak od wiedzy współczesnych biologów, nie ma podstaw odrzucać z góry tej teorii w przypadku sztucznej ewolucji, tym bardziej, że ma ona najczęściej co najwyżej luźne powiązania z rzeczywistością.
*Jeśli algorytm optymalizacji globalnej niejest idealny, to płaskowyże te nie są idealnie płaskie; niemniej jednak zróżnicowanie wartości funkcji przystosowania dla osobników z obszaru przyciągania tego samego maksimum lokalnegojest mniejsze dla funkcji zmodyfikowanej niż pierwotnej.
.200^____ 5.Zapobieganieprzedwczesnejzbieznosci ,-!!,.ij.;A l?.
nia metody optymalizacji lokalnej nowego fenotypu y wyznacza się genotyp Y, który zastępuje genotyp oryginalny. W wyniku tego, cała populacja jest ,^ciagana" do maksimów lokalnych, następuje znaczne zmniejszenie różnorodności, a co za tym idzie algorytm ma bardzo eksploatacyjny charakter.
Ocena, czy lamarkizm stanowi ułatwienie, czy przeszkodę dla algorytmu ewolucyjnego, pozostaje sprawą otwartą, gdyż śledząc różne publikacje można spotkać się ze znacznym zróżnicowaniem poglądów na ten temat. Mechanizm ten będzie z pewnością utrudniał powstawanie chromosomów będących "pośrednimi ogniwami" w ewolucji, zazwyczaj gorszymi niż chromosomy bliskie lokalnych maksimów funkcji przystosowania. Wydaje się więc, że podejście takie może działać wówczas, gdy istnieją mechanizmy wprowadzające zróżnicowanie w populacji bazowej. Można się spodziewać, że w dziedzinach ciągłych zaobserwujemy silniejszy negatywny wpływ na zdolność algorytmu do eksploracji.
Ze względu na niejednoznaczność oceny lamarkizmu, wielu autorów proponuje stosować go tylko dla pewnej części osobników. Znana jest na przykład reguła 5%, która mówi, że tylko 5% osobników podlega dziedziczeniu cech nabytych. Stanowi ona wniosek z eksperymentów przeprowadzonych dla kodowania binarnego, jednak nie wszystkie eksperymenty ją potwierdzają.
Niezaprzeczalną wadą ewolucji lamarkowskiej jest bardzo duża podatność takiego algorytmu na pułapki ewolucyjne, z których jedyną drogą ucieczki są (mało prawdopodobne) makromuta-cje. Przy stosowaniu takiej ewolucji, algorytm ewolucyjny będzie przypominał prostą metodę wielostartową, która polega na wielokrotnym uruchomieniu metody optymalizacji lokalnej z losowym punktem początkowym*.
5.2. Czas życia osobników w populacji bazowej
5.2.1. Limitowanie maksymalnegoczasu życia ,, ,, ,,
W wykładzie poświęconym selekcji poznaliśmy metody sukcesji elitarnej, gwarantujące przeżycie najlepszego osobnika. Zaletą takiego postępowania jest fakt, że daje ono gwarancję .... . . ,. zbieżności w sensie niedeterministycznym. Również szybkość
*W skrajnym przypadku, ..... . .. ^ J .. . J.
ewolucja często "nie m- zbieżności jest większa niz w przypadku sukcesji nieelitarnej. ro-szy" najlepsze zna- ważna wadą iest natomiast zwiększona podatność na pułapki ewo-
lezione rozwiązanie bę- ^ ^J *� . r L
dzie wyznaczane w pierw- lucyjn6. W przypadku gdy stosowana jest techmka samoczynnej szej generacji ibędzie to adaptacji zasięgu operatorów, przetrzymywanie najlepszego osob-
maksimum lokalne z tym r J ^0 r ' r J ^ J L �
większym prawdopodobień- nika (którego zasięg operatorów był ustalony byc moze wiele gene-stwem, im mniejsza jest ra(,:j WCześniej) może często wprowadzać zakłócenia w działaniu
miara zbioru przyciągania J . J/ ..
maksimum globalnego. samoczynnej adaptacji.
5.2. Czas życia osobników w populacji bazowej
.201.
procedurę Selekcja elitarna z ograniczaniem
maksymalnego czasu życia begin
t := 0
inicjacja P*
ocena P*
while (not warunek stopu) do
begin
O* := reprodukcja P*
operacje genetyczne O*
ocena O*
foreach (X e O*) do
begin
;,.,'.^' ., ., J(X) :=�
end
P* := P* \ {X : J(X) < 0} PL, := wybór najlepszych (P*, v] P*+1 ;= wybór najlepszych (Pj, U O*) ''' �/; t := t + 1
foreach (X � P*) do begin
Z(X) := /(X) - 1
end end end
RvsuNEK 5.3. Schemat elitarnego algorytmu ewolucyjnego z ograniczaniem maksymalnego czasu życia
Rozwiązaniem kompromisowym jest wprowadzenie dodatkowego parametru maksymalnego czasu życia osobnika (rys. 5.3).
W schemacie sukcesji, ze starej populacji bazowej usuwa się najpierw osobniki, których czas życia przekroczył limit, a elitę wyłania się z pozostałych osobników. Taki schemat wprowadzono w strategiach ewolucyjnych i nazwano (^t,K,A). Nie ma jednak jak dotąd jasnych wskazówek dotyczących doboru wartości K. Wydaje się, że zwiększając tę wartość, można spowodować bardziej "stabilne", zmniejszając zaś bardziej "adaptacyjne" zachowanie algorytmu ewolucyjnego.
.202.
5. Zapobieganie przedwczesne] zbieżności
5.2.2. Selekcja sterowana czasem życia
Powszechnie przyjętym założeniem jest, że liczność populacji bazowej p, nie ulega zmianom podczas działania algorytmu, a także, że nacisk selektywny jest realizowany poprzez różnicowanie prawdopodobieństw reprodukcji, względnie przeżycia sukcesji. Jeśli stosowana jest sukcesja elitarna, to czas życia osobników jest potencjalnie nieskończony i jest pochodną ich przystosowania. Można oczekiwać, że im lepszy osobnik, tym dłużej będzie przetrzymywany w populacji bazowej. Oczywiście, czas życia osobnika nie zależy tylko od jego przystosowania, łecz również od stanu całej populacji bazowej. Spróbujmy teraz odwrócić sytuację niech czas życia osobnika będzie ustalany od razu w momencie jego narodzin, liczność populacji bazowej niech będzie zmienna w taki sposób, aby pomieścić wszystkie osobniki o czasie życia większym niż zero, reprodukcja zaś niech zachodzi z jednakowym prawdopodobieństwem dla każdego osobnika z P4.
procedurę Ewolucja z selekcją sterowaną czasem życia begin
t := 0 ii.
inicjacja P* ;
ocena P4
while (not warunek stopu) do '
begin *
O* := reprodukcja P* operacje genetyczne O' ocena O*
""'''''-""'' foreach(XeO')do ^<^<';'"-1--''"'---' <';
begin
l(X) := /,(*(X)) � - . - ,-� < '
end
pt+i:=p*\{XeP*|/(X)<0}UO* ' '
t := t + l
foreach (X � P*) do
begin
Z(X) := J(X) - 1
end end end
RYSUNEK 5.4. Schemat algorytmu ewolucyjnego z selekcją sterowaną czasem życia osobnika
5.2. Czas życia osobników w populacji bazowej
.203.
W algorytmie uwzględniającym powyższe założenie (rys. 5.4) przyjmuje się, że z każdym osobnikiem X � P* związana jest pewna wartość Z(X) określającajego czas życia, czyli liczbę generacji, przez które będzie on przechowywany w populacji bazowej. Wartość /(X) określa się na podstawie przystosowania oraz stanu populacji. Z reguły, osobnik lepiej przystosowany powinien żyć nie krócej niż osobnik gorzej przystosowany. Sposób określania wartości Z(X) określa funkcja /;, zwana funkcją obliczania czasu życia.
Rolą funkcji // jest wywieranie nacisku selektywnego poprzez różnicowanie czasu życia lepiej przystosowane osobniki żyją
dłużej*. Przy tym, im większa jest wartość stosunku $|xi-$(Y)' tym większy jest nacisk selektywny.
Sposoby obliczania czasu życia. Rozważmy kilka różnych funkcji /;. W ich definicji wykorzystuje się dwa parametry, lmin i lmax, które są odpowiednio minimalną i maksymalną wartością czasu życia osobnika w populacji; dodatkowo dla uproszczenia zapisu przyjmijmy lav = \(lmax + lmin}- Oprócz powyższych parametrów, do obliczenia czasu życia wykorzystuje się wartości *&min, &av i 3>max, będące najmniejszą, średnią i największą wartością funkcji przystosowania w populacjach bazowych mieszczących się w oknie czasowym o pewnej założonej szerokości. Oto przykładowe funkcje obliczania czasu życia (rys. 5.5):
funkcja liniowa
ff~v\ 1 i
//(X) = lmin +
_ .
max lrmn
a./v\
$(X)
� funkcja proporcjonalna //(X) = rnin f lmax, lmin +
funkcja biliniowa
/KX) =
<-rnir.
^av "min
U + fc:fcfr(X)
dla dla
^av ^av
/t- i\
(5.1)
(5.2)
(5.3)
Wartości 3>mm, 3?<� i &max są wielkościami statystycznymi dla pewnej liczby pokoleń K, czyli
&min(t) = min mul r=ts,...,tXePT
=^- y fł F *(x)l
*-*�T_f^ AAX^ /
� Łs ,...,L A.fcJr
max
xeP1"
gdzie ts = max(0, t n + 1).
(5.4) (5.5) (5.6)
*Wobec faktu, że prawdopodobieństwo reprodukcji jest jednakowe, dłuższy czas życia oznacza większą liczbę kopii osobnika podczas reprodukcji.
"(X)
*max
>-av
lmin
0
(a
*mi
(d)
*min
K(X)
� 'min ~" ~
(b)
*min
*av
*min
o
NJ
O
(C)
RYSUNEK 5.5. Funkcje obliczania czasu życia (a,b) proporcjonalne, c,d) biliniowe, e) liniowa), gdy $at, Ki $mi" (pojawienie się superosobnika w początkowej fazie działania algorytmu - a, c)) oraz gdy $>av fa $mox ("czarna owca" pojawia się pod koniec działania algorytmu - b, d)). Im większe nachylenie wykresu, tym większe zróżnicowanie czasu życia i przystosowania i tym samym większy nacisk selektywny
T> N S.
5.2. Czas życia osobników w populacji bazowej
.205.
Wartość K, ma wpływ na nacisk selektywny zmniejszanie K powoduje zwiększanie nacisku. W skrajnym przypadku, gdy K = oo, jeśli lmax ma niewielką wartość, algorytm nie "rozróżnia" osobników o zbyt bliskich sobie wartościach funkcji przystosowania, co może uniemożliwić jego zbieżność. Dla K = l mówimy o lokalnych statystykach, natomiast K = 00 odpowiada statystykom globalnym.
Przeanalizujmy teraz podane powyżej przykładowe funkcje /;. Funkcja liniowa charakteryzuje się jednakowym naciskiem selektywnym dla całej populacji osobników. Odmiennie jest w przypadku funkcji proporcjonalnej i biliniowej. W przypadku tej pierwszej, osobniki o wartościach funkcji przystosowania spełniających warunek
$(X) > 2$>av - $min (5.7)
mają jednakowe wartości czasu życia a zatem w grupie najlepiej przystosowanych osobników, nacisk selektywny może nie wystąpić. W przypadku funkcji biliniowej //, w populacji wyodrębnione są dwie grupy osobników poniżej i powyżej przeciętnej dla których nacisk selektywny jest stały, podobnie jak dla funkcji liniowej. Zależność nacisku selektywnego od wielkości statystycznych funkcji przystosowania powoduje jego zmiany podczas działania algorytmu ewolucyjnego.
Zmniejszenie wartości $mj" (pojawienie się "czarnej owcy") powoduje w przypadku funkcji liniowej zwiększenie średnich wartości i(X) oraz osłabienie nacisku selektywnego. Jest to zjawisko niekorzystne, gdyż grozi dodatnim sprzężeniem zwrotnym osłabienie tego nacisku może bowiem powodować generowanie nowych, jeszcze gorszych osobników, które będą go jeszcze bardziej osłabiać. Efekt ten wystąpi również w przypadku funkcji proporcjonalnej. Będzie mujednocześnie towarzyszyć zmniejszenie liczby osobników, dla których /(X) = lmax- W funkcji biliniowej, efekt opisany dla liniowej będzie dotyczyć tylko osobników poniżej średniej, dzięki czemu mniejsze będzie ryzyko pojawienia się opisanego sprzężenia.
Zwiększenie wartości $max (pojawienie się "superosobnika") spowoduje w przypadku funkcji liniowej zmniejszenie średniego czasu życia i zmniejszenie nacisku selektywnego. Jest to efekt niekorzystny, gdyż prowadzi do osłabienia tempa zbieżności ze względu na mniejsze zróżnicowanie czasu życia osobników słabszych. Metoda proporcjonalna nie jest na to wrażliwa ze względu na ograniczenie /(X) < lmax- Dzięki temu tempo zbieżności nie osłabnie, a można przy tym uniknąć zbyt szybkiego zdominowania populacji przez najlepszego osobnika. Podobnie w przypadku metody biliniowej nastąpi zmniejszenie nacisku selektywnego wśród osobników powyżej przeciętnej przy utrzymaniu tego samego poziomu konkurencyjności w grupie osobników gorszych.
.206.
5. Zapobieganie przedwczesnej zbieżności
10
oS 0.1
0.01
0.001
0.0001
1
10
100
1000
(a)
10
0.1
0.01
0.001
0.0001
10
100
1000
(b)
RYSUNEK 5.6. Porównanie wyników działania selekcji sterowanej czasem życia (linia ciągła) oraz elitarnej sukcesji progowej (/i + A) (linia przerywana); zależność rozwiązań dla różnych kryteriów zatrzymania: a) zatrzymanie po 200 generacjach, b) zatrzymanie po 100 generacjach bez odnotowania poprawy najlepszego rozwiązania
5.2. Czas życia osobników w populacji bazowej
.207.
10000
� 1000
100
10
100
1000
M0
(a)
10000
1000
100
10
100
1000
(b)
RYSUNEK 5.7. Porównanie wyników działania selekcji sterowanej czasem życia (linia ciągła) oraz elitarnej sukcesji progowej (fJ, + \) (linia przerywana); zależność kosztu rozwiązania dla różnych kryteriów zatrzymania: a) zatrzymanie po osiągnięciu zadowalającego poziomu przystosowania, b) zatrzymanie po 100 generacjach bez odnotowania poprawy najlepszego rozwiązania
.208.
5. Zapobieganie przedwczesnej zbieżności
Zmiany wartości $av nie wpływają na funkcję liniową. W funkcji proporcjonalnej, wraz ze zmianą $>av następuje zmiana liczby osobników, dla których /(X) lmax, toteż zwiększanie av towarzyszy wzrost nacisku selektywnego wśród osobników lepszych i jego spadek wśród gorszych. Jest to zjawisko korzystne, gdyż pozwala na rozdzielenie osobników silnie eksploatujących (powyżej średniej), które jak można oczekiwać szybciej osiągną rnaksima (być może lokalne) funkcji przystosowania niż osobniki słabsze, których zadaniem jest eksploracja (tak, jakby były w odwodzie). Podobnie jest w przypadku zmniejszenia się wartości $av wzrost nacisku selektywnego w grupie osobników słabszych powoduje szybszą zbieżność, przy zabezpieczeniu się przed lokalną zbieżnością przez osłabienie eksploatacyjności wśród osobników lepszych.
Liczność populacji potomnej. Źródłem nacisku selektywnego jest różnicowanie czasu życia poszczególnych osobników, toteż nie ma potrzeby różnicowania prawdopodobieństw reprodukcji. Uzależnienie czasu życia osobników od ich przystosowania powoduje, że liczność populacji bazowej nie jest stała, lecz zmienna w czasie i zależy od zawartości populacji bazowej. Powstaje zatem pytanie jaka powinna być w generacji t liczność populacji potomnej \(t), jeśli populacja bazowa zawiera wtedy ^,(t} osobników? Można rozważyć dwie odpowiedzi ze stałą wartością A(i) = A oraz ze stałym stosunkiem X(t)/p(t). Pierwsza wydaje się prowadzić do stabilniejszego algorytmu, gdyż maksymalna liczność populacji bazowej nie może przekroczyć A(/max + 1), przy drugiej zaś populacja bazowa może zwiększać się do nieskończoności.
Wyniki symulacji komputerowych algorytmu z selekcją sterowaną czasem życia przedstawiono na rys. 5.6, 5.7.
Jak można się przekonać, właściwości algorytmu z selekcją sterowaną czasem życia osobników w bardzo niewielkim stopniu zależą od liczności początkowej populacji bazowej. Przy ustalonym A, nakład obliczeń i odporność na maksima lokalne są porównywalne z wynikami selekcji progowej z wartością progu dającą dużą odporność przy jak najmniejszym koszcie*.
5.3. Optymalizacja wielomodalna
W formułowaniu funkcji przystosowania dużą trudność sprawia *Oznacza to, że można niekiedy uwzględnienie wszystkich elementów mających wpływ uniknąć kłopotliwego do- na i^ość rozwiązania. Wynikać to może zarówno z ich niemie-
bierania "optymalnej licz- J ^ J . . . . .....
ności populacji bazowej, rzalnych cech (np. "elegancja rozwiązania), jak rowniez ze swia-
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
domych uproszczeń, poczynionych np. w celu przyspieszenia obliczania wartości funkcji celu. W wyniku tego, funkcja celu nie oddaje w pełni wszystkich wymagań stawianych rozwiązaniu. To ?� kolei może powodować, że wśród rozwiązań globalnie optymalnych mogą występować lepsze lub gorsze z punktu widzenia zadania; może się nawet zdarzyć, że lokalne maksimum funkcji przystosowania odpowiada najlepszemu rozwiązaniu zadania. Mając na względzie powyższe rozważania, warto jest niekiedy prowadzić poszukiwania rozwiązań optymalnych (lub suboptymalnych) równocześnie w wielu obszarach zbioru dopuszczalnego.
Zadanie optymalizacji wielomodalnej spróbujmy postawić w podobny sposób, w jaki były formułowane zadania eksploracji i eksploatacji. Załóżmy, że dokonaliśmy podziału zbioru dopuszczalnego na podzbiory rozłączne parami, będące zbiorami przyciągania maksimów lokalnych. Ponumerujmy maksima lokalne X1, X2, X3, X4 ... w kolejności malejącego (lub przynajmniej niero-snącego) przystosowania; rzecz jasna, pierwszy element tej listy jest maksimum globalnym.
Jeśli założymy, że wynikiem optymalizacji jest k punktów, to celem jest, aby ich zbiór był tożsamy ze zbiorem {X1, ...,Xfc}. Oznacza to, że optymalizacja wielomodalna sprowadza się do zna-lezieniajak największej liczbyjak najlepszych, różnych maksimów lokalnych.
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
Podstawową techniką stosowaną w ewolucyjnej optymalizacji wielomodalnej jest utrzymywanie różnorodności populacji bazowej. Rozproszenie populacji w przestrzeni genotypów pozwala na lepsze jej próbkowanie, mechanizm selekcji zaś prowadzący do poprawy przystosowania ma za zadanie doprowadzić w kolejnych generacjach do zlokalizowania jak najlepszych maksimów funkcji przystosowania. Poważną przeszkodę w osiągnięciu tego celu stanowi głobalność selekcji osobniki konkurują ze sobą podczas reprodukcji i sukcesji. W rezultacie, po upływie odpowiednio wielu generacji, w populacji bazowej pozostają jedynie najlepsze osobniki, które najczęściej znajdują się stosunkowo blisko siebie, w obszarze przyciągania jednego zaledwie maksimum funkcji przystosowania. Można zapobiec tej sytuacji albo przez dodanie czynnika losowego, niezależnego od stanu populacji, albo przez zmniejszenie zasięgu selekcji, tzn. ograniczenie konkurencji do osobników znajdujących się blisko siebie w przestrzeni genotypów. Mówi się czasem, że należy w populacji wyłonić nisze, w ramach których odbywa się konkurencja osobników.
.210.
5. Zapobieganie przedwczesnej zbieżności
Techniki wyłaniania nisz można podzielić na trzy podstawowe grupy:
1) wyróżnianie podpopulacji na podstawie odległości genotypów; podział odnawiany co jakiś czas,
2) koewolucyjna równoczesna ewolucja wielu autonomicznych populacji z częściową wymianą materiału genetycznego, ,,,
3) lokalna deformacja funkcji przystosowania.
W kolejnych podrozdziałach omówiono: techniki wprowadzania czynnika losowego oraz metody bazujące na niszach.
*Czyli makromutację.
5.4.1. Wprowadzanie dodatkowego czynnika losowego
Wprowadzanie osobników losowych. W tym podejściu, zwanym również techniką losowych imigrantów, część populacji potomnej jest tworzona poprzez reprodukcję i operacje genetyczne na osobnikach starej populacji bazowej, część zaś jest losowo generowana (podobniejak w początkowej populacji bazowej). Takie postępowanie ułatwia uniknięcie maksimów lokalnych, jednakże osłabia nacisk selektywny, co może się objawiać zmniejszeniem szybkości zbieżności.
Wprowadzanie osobników losowych można traktować jak operator genetyczny, analogiczny do mutacji. W odróżnieniu od ,^conwencjonalnej" mutacji, operator taki wykorzystuje zmienną losową o rozkładzie niezależnym od chromosomu rodzicielskiego. Najczęściej jest to rozkład wykorzystywany podczas inicjacji populacji bazowej.
Okresowa odnowa algorytmu. Podobny do poprzedniego pomysł, zwany algorytmem ewolucyjnym z odnową (lub z selektywnie destrukcyjnym restartem), polega na wykonaniu ciągu powiązanych ze sobą algorytmów ewolucyjnych. Na początku uruchamia się algorytm ewolucyjny z losową populacją początkową. Po spełnieniu kryterium zatrzymania rozpoczyna się działanie kolejnego algorytmu ewolucyjnego, którego populacja bazowa jest inicjowana w specjalny sposób, na podstawie rozwiązania znalezionego w poprzednim algorytmie.
Chromosom każdego osobnika populacji bazowej powstaje poprzez mutację o dużym zasięgu* chromosomu będącego rozwiązaniem znalezionym przez poprzedni algorytm. Zainicjowana w ten sposób populacja bazowa będzie miała z reguły postać "chmury" chromosomów rozłożonych wokół rozwiązania z poprzedniej generacji. Algorytm z tak wygenerowaną populacją bazową jest uruchamiany i działa aż do ponownego spełnienia kryterium zatrzymania. Rozwiązanie przez niego znalezione jest wykorzystywane w kolejnym algorytmie do utworzenia populacji bazowej.
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
.211.
Proces ten jest kończony wówczas, gdy uruchomienie kolejnego algorytmu ewolucyjnego nie spowoduje zmiany najlepszego znalezionego dotychczas rozwiązania.
Losowe zaburzanie funkcji przystosowania. Pomysł polega na dodaniu "szumu" do funkcji przystosowania, tak że jej wartość staje się zmienną losową
gdzie L jest pewną zmienną losową. Jej wybór jest do pewnego stopnia arbitralny, jednak najczęściej jest wykorzystywany rozkład normalny o zerowej wartości oczekiwanej, którego wariancja jest stała lub zmniejsza się wraz z kolejnymi generacjami. Wynikiem takiego postępowaniajest "stochastyczne wygładzenie" funkcji przystosowania, co pozwala unikać płytkich pułapek ewolucyjnych.
5.4.2. Osłabianie konkurencyjności w ramach selekcji
Lokalne modyfikacje konkurencyjności. Analiza technik selekcji prowadzi do wniosku, że algorytm ewolucyjny ma tendencję do skupiania populacji bazowej wokół pojedynczych maksimów funkcji przystosowania. Dzieje się tak dlatego, że mechanizm selekcji preferuje osobniki o większej wartości funkcji przystosowania, prowadząc do ich lepszego ,^ozmnozenia" w populacji bazowej, co wobec jej skończonej liczności oznacza, że po pewnym czasie będą się w niej znajdować osobniki bardzo podobne do siebie i bliskie jednemu z maksimów (miejmy nadzieję, że globalnemu) funkcji przystosowania. Zdominowanie populacji przez osobniki podobne do siebie, czyli zanik różnorodności, może prowadzić do utraty eksploracyjności, co może skutkować przedwczesną zbieżnością. Temu niepożądanemu zjawisku można próbować zapobiec poprzez obniżanie wartości funkcji przystosowania osobników zbyt licznie reprezentowanych w populacji (metoda podziału przystosowania) lub też poprzez ograniczanie zasięgu selekcji (omówione w kolejnym podrozdziale).
Metoda podziału przystosowania. Metoda podziału przystosowania (fitness sharing) polega na obniżaniu wartości funkcji przystosowania osobnika w stopniu proporcjonalnym do liczby osobników w jego otoczeniu. Zarówno pojęcie "otoczenia" osobnika, jak i sam sposób podziału, określa projektant algorytmu ewolucyjnego, definiując funkcję podziału fs. Zmodyfikowaną wartość funkcji przystosowania osobnika <&'(X) określa się na podstawie wartości funkcji przystosowania w całej populacji bazowej
.212.
5. Zapobieganie przedwczesnej zbieżności
<&'(X) =
gdzie |X Y| jest metryką w przestrzeni genotypów.
Funkcja fs(d) powinna spełniać następujące warunki:
(5.9)
lim fa(d} = 0
(5.10) (5.11) (5.12)
Populację osobników Y � P*, dla których /S(|X - Y|) > 0, nazywa się często niszą, algorytm ewolucyjny zaś wykorzystujący technikę podziału przystosowania nazywa się algorytmem niszowym (niching evolutionary algorithm).
Sposób działania metody podziału przystosowania. Oddziaływanie funkcji podziału na funkcję przystosowania polega na obniżaniu jej w tych miejscach, w których gęstość liczby osobników jest większa (rys. 5.8).
*(X)
Oryginalna
funkcja
przystosowania
Chromosomy w populacji bazowej
0 X
RYSUNEK 5.8. Oryginalna funkcja przystosowania i jej postać po zastosowaniu podziału przystosowania; zaznaczono chromosomy z populacji bazowej. Zilustrowano przypadek, w którym maksimum globalnemu funkcji oryginalnej odpowiada maksimum lokalne funkcji zmodyfikowanej , . . ... ,
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
.213.
Zmodyfikowana metoda podziału przystosowania. Nie
można wykluczyć takiej sytuacji, gdy w wyniku podziału przystosowania chromosomy znajdujące się w otoczeniu maksimum globalnego będą miały na tyle zmniejszoną wartość funkcji przystosowania, że tylko niewiele z nich (i to niekoniecznie najlepszych) zreprodukuje się do populacji potomnej (niebezpieczeństwo to wzrasta wraz z naciskiem selektywnym). W rezultacie, może dojść do "migotania" populacji, polegającego na tym, że chromosomy oscylują między obszarami przyciągania różnych maksimów lokalnych. Jest to efekt niepożądany i sprzeczny z założeniami metody niszowania, jednak dość często obserwowany.
Zjawiska migotania można uniknąć, modyfikując schemat niszowania w ten sposób, że mianownik z (5.9) związany z podziałem nie jest jednakowy, lecz różny dla różnych osobników z niszy. Efekt ten jest osiągany w następujący sposób. Chromosomy w populacji bazowej P* są ponumerowane X*,X^...,X^. Zmodyfikowana funkcja przystosowania jest określana jako
*(X*
(5.13)
Oznacza to, że dwa osobniki o identycznym genotypie uzyskają różne wartości zmodyfikowanej funkcji przystosowania większą wartość otrzyma ten, który jako pierwszy był brany pod uwagę podczas obliczania 3>'(X).
5.4.3. Ograniczanie zasięgu selekcji
Metody ograniczające zasięg selekcji wykorzystują podział populacji osobników na podpopulacje. Pomysł ten, zastosowany dla algorytmów optymalizacji globalnej, niejest niczym szczególnie oryginalnym znanych jest wiele metod bazujących na grupowaniu. U podstaw legło przekonanie, że jeśli w obszarze dopuszczalnym "posieje się" równomiernie populację punktów, i jeśli dla każdego jej elementu będzie się wykonywać kroki algorytmu optymalizacji lokalnej, to zaobserwuje się tendencję do zagęszczania punktów wokół maksimów lokalnych. Obserwując zbliżanie się punktów, można przypuszczać, że znajdują się one w obszarze przyciągania tego samego minimum lokalnego. Skoro tak, to da się uniknąć zbytecznych obliczeń, usuwając część punktów z każdego z tworzących się zgrupowań.
(Nieewolucyjny) algorytm optymalizacji wykorzystujący grupowanie i redukcję punktów (rys. 5.9). Początkowa populacja P� jest wypełniana wygenerowanymi losowo punktami. Następnie rozpoczyna się iterowanie pętli głównej algorytmu.
.214.
5. Zapobieganie przedwczesnej zbieżności
procedurę Algorytm wykorzystujący grupowanie begin
utwórz populację P* punktów
while (not warunek stopu) do '
begin
O* := krok lokalnej optymalizacji P*
podziel O* na rozłączne grupy O*, c 1,..., v
for ( c = 1,..., v} do
begin
usuń kc losowych punktów z O* end
t :=t + l end lokalna optymalizacja punktów z P*
end
RvsuNEK 5.9. Algorytm optymalizacji wykorzystujący grupowanie punktów
W tej pętli, dla każdego punktu X e P* wykonuje się najpierw kilka kroków algorytmu optymalizacji lokalnej, co prowadzi do nowego punktu Y, który staje się elementem populacji potomnej O'. Następnym krokiem jest podział O* na rozłączne grupy O*. Z każdej z grup usuwa się pewną liczbę najgorszych punktów; ich liczba jest różna w różnych implementacjach algorytmu i zazwyczaj stanowi pewien stały ułamek liczności grupy. W kolejnej iteracji grupy są z powrotem łączone, wykonywany jest kolejny krok metody optymalizacji lokalnej, a następnie ponawiany jest podział na grupyi redukcja punktów. Zauważmy, że fakt przynależności w iteracji t algorytmu pary punktów X, Y do tej samej grupy nie implikuje, że w kolejnych iteracjach będą one również elementami tej samej grupy. Może się również zdarzyć, że dwa punkty należące do różnych grup będą w kolejnej iteracji elementami tej samej grupy.
Warunkiem zatrzymania algorytmu jest występowanie wyłącznie grup zawierających dokładnie jeden element. Oznacza to, że zanikła już tendencja do zbliżania się punktów do siebie, co pozwala mieć nadzieję, że każdy punkt należy do obszaru przyciągania innego maksimum lokalnego. Wówczas uruchamia się optymalizację lokalną dla każdego elementu populacji P* i wybiera najlepsze znalezione rozwiązanie, które jest wynikiem działania algorytmu.
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
.215.
Jednym z najprostszych algorytmów grupowania może być taki, który prowadzi do spełnienia dla każdej podpopulacji O' następującego kryterium:
VX,YeO* |X-Y|(5.14)
gdzie S jest parametrem algorytmu grupowania.
Wadą takiego algorytmu grupowania jest konieczność podania parametru 6 ograniczającego od góry odległość między osobnikami z grupy. Zbyt mała wartość 6 może spowodować, że wyłonione grupy będą zawierać po jednym punkcie. Z kolei zbyt duża wartość S doprowadzi do utworzenia tylko jednej grupy tożsamej z populacją bazową. W związku z tym, chcąc posłużyć się powyższym algorytmem, należałoby albo dodatkowo zdefiniować pewien mechanizm modyfikowania 6, albo też określać S jako pewną "odległość odniesienia", charakterystyczną dlapopulacji. Pierwszy pomysł jest dość kłopotliwy w praktyce, natomiast w celu realizacji drugiego pomysłu potrzebny byłby jakiś w miarę "naturalny"* sposób określania 6.
Wykorzystanie grupowania w algorytmie ewolucyjnym.
Naszkicowana powyżej metoda optymalizacji bazująca na grupo-
procedure Algorytm ewolucyjny z grupowaniem begin
t := 0
inicjacja P*
ocena Pf
while (not warunek stopu) do
begin
podziel P* na v rozdzielnych podpopulacji ' for ( c 1, . . . , v ) do
begin
O* := reprodukcja P* operacje genetyczne O* : ocena O*
end
Pi+1 := sukcesja (P*, O*) t := t+l
end
end
RYSUNEK 5.10. Algorytm z ograniczaniem reprodukcji do podpopulacji
*W świetle przedstawionych powyżej wad, dość atrakcyjne wydaje się być wykorzystanie algorytmów grupowania bazujących na gęstości punktów. Jako kryterium wyodrębnienia grupy można przyjąć wzrost gęstości punktów powyżej pewnego progu, który może być wyznaczany na przykład jako gęstość całej populacji punktów w obszarze przez nią zajmowanym. Dokładne omówienie metod grupowania wymagałoby znacznie więcej miejsca i przekracza ramy tej książki.
.216.
5. Zapobieganie przedwczesnej zbieżności
waniu może być w naturalny sposób wykorzystana w algorytmie ewolucyjnym (rys. 5.10). Algorytm należy zmodyfikować w taki sposób, aby przed przystąpieniem do reprodukcji populację bazową P* podzielić na v rozłącznych podpopulacji P*. Liczba pod-populacji nie musi być założona z góry, wynika ona bowiem z przyjętego algorytmu grupowania. Jeśli chodzi o kryterium grupowania, panuje tu względna swoboda powinno ono jednak wykorzystywać albo informację o wzajemnych odległościach chromosomów, albo o ich gęstości w ramach grupy. Dla praktyków dobrą wiadomością jest to, że grupowanie nie musi być wykonywane szczególnie starannie.
Po wyodrębnieniu podpopulacji P*, dla każdej z nich przeprowadza się reprodukcję i operacje genetyczne. Powstaje wiele podpopulacji O*, które są łączone i tworzą populację potomną. Podlega ona następnie sukcesji według "zwykłego" schematu (bez podziału na podpopulacje). Podobnie jak w omawianym wcześniej algorytmie bazującym na grupowaniu, w tak zmodyfikowanym algorytmie ewolucyjnym podział na podpopulacje nie jest sztywny dwa osobniki należące do jednej grupy w generacji t\ nie muszą się znaleźć w tej samej grupie w generacji t%.
5.4.4. Preselekcja
Metody preselekcji są podobne do bazujących na grupowaniu. Modyfikacja dotyczy przede wszystkim sposobu sukcesji, podczas której uwzględnia się, oprócz wartości funkcji przystosowania, również relację między genotypami osobników.
Schemat metody. Zasada metody polega na tym, że każdorazowo po utworzeniu nowego osobnika w wyniku reprodukcji i operacji genetycznych usuwa się z populacji bazowej jednego osobnika. Po zakończeniu cyklu reprodukcji i operacji genetycznych, populacja potomna i pozostałości populacji bazowej tworzą po złączeniu nową populację bazową.
Najczęściej wykorzystuje się dwa sposoby wyboru osobników do wymiany jest to albo jeden z osobników rodzicielskich, albo też taki osobnik, którego chromosom jest w dziedzinie genotypu najbliższy potomnemu.
Usuwanie jednego z rodziców. Kandydatem do usunięcia jest osobnik rodzicielski o najmniejszej wartości funkcji przystosowania. Jeśli jego przystosowanie jest mniejsze niż osobnika potomnego, wówczas dochodzi do usunięcia; w przeciwnym przypadku osobnik potomny jest odrzucany i populacja bazowa pozostaje bez zmian.
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
.217.
procedurę Algorytm ewolucyjny z preselekcją begin
t : = 0
inicjacja P�
ewaluacja P�
while (not warunek stopu) do
begin
O* := 0
for (i = 1,..., G[t) do
begin
, , T* := reprodukcja k osobników z P* ,.. ;, Y := operacje genetyczne (T*)
X := wybór osobnika do wymiany z P*
P* :=P*\{X}
Ot := Ot U {Y}
end
pt+l ._ pt ^ Qt ......
t :=t + 1 end end
RYSUNEK 5.11. Algorytm ewolucyjny z preselekcją (G oznacza wartość współczynnika wymiany) /
Usuwanie najbardziej podobnego osobnika; ścisk. Z populacji bazowej jest usuwany osobnik, którego chromosom jest najbliższy chromosomowi nowo utworzonego osobnika potomnego, niezależnie od jego przystosowania.
Znalezienie takiego osobnika wymaga przejrzenia całej populacji bazowej i porównania każdego jej osobnika z potomnym; jest to więc czynność dość czasochłonna. W celu zmniejszenia liczby potrzebnych operacji wprowadzono schemat ze ściskiem. Polega on na tym, że najpierw wybiera się losową podpopulację zawierającą k osobników, a następnie wyłania się z niej osobnika, którego chromosom jest najbliższy potomnemu. Osobnika tego się usuwa. Prawdopodobieństwo zaliczenia osobnika do podpopulacji kandydatów do usunięcia jest wprost proporcjonalne do przystosowania osobników (można np. zastosować metodę bazującą na reprodukcji proporcjonalnej). Wartość k jest zwana współczynnikiem ścisku. Rzecz jasna, im większa wartość k, tym schemat ze ściskiem pozwala na dokładniejszą realizację idei usuwania najbardziej podobnego osobnika; jest to niestety okupione większą liczbą operacji porównania.
.218.
5. Zapobieganie przedwczesnej zbieżności
5.4.5. Deformacje funkcji przystosowania w otoczeniu maksimum lokalnego
Pomysł lokalnego deformowania funkcji przystosowania powstał pierwotnie dla algorytmów wielostartowych (minimalizacji funkcji celu), polegających na wielokrotnym uruchamianiu metody optymalizacji lokalnej z punktu generowanego w sposób losowy. Ponieważ przy takim postępowaniu zdarza się często, że wielokrotnie osiągany jest ten sam punkt, który może być maksimum lokalnym, to opłaca się tak deformować optymalizowaną funkcję, aby uniemożliwić ponowne dojście do tego punktu przy kolejnej optymalizacji lokalnej*. Postępowanie takie można przyrównać do niwelowania krajobrazu opisanego optymalizowaną funkcją.
Rozważmy algorytm realizujący tę ideę (rys. 5.12). Składa się on z trzech elementów algorytmu ewolucyjnego, metody modyfikacji funkcji przystosowania oraz kryterium zatrzymania algorytmu nadrzędnego.
procedurę Algorytm z deformacją funkcji przystosowania begin
k := 0
while (not koniec algorytmu nadrzędnego) do
begin
Xfc := wynik ewolucji z funkcją $fc+1(X) := deformacja k := k + l end end
RYSUNEK5.12.Algorytmzdeformacjafunkcjiprzystosowania ; f,
Modyfikacji funkcji przystosowania dokonuje się w sposób zależny od maksimum funkcji przystosowania znalezionego w ostatnim uruchomieniu algorytmu genetycznego. W literaturze fachowej można znaleźć opisy modyfikacji polegających na dodaniu do wartości dotychczasowej funkcji przystosowania wartości funkcji deformującej, naprzykład
(5.15)
*jest to postępowanie po- gdzie
dobne do metody poszukiwań z tabu.
jest standardowym odchyleniem wartości genu Xi
, ., , . , . , . , .. . . , , . .
osobmkow znajdujących się w populacji bazowej w ostatniej ge-
1
5.4. Techniki ewolucyjnej optymalizacji wielomodalnej
.219.
*(X)
Funkcja modyfikująca
Znalezione maksimum lokalne
X
(a)
*(X)
(b)
RYSUNEK 5.13. Ilustracja działania metody modyfikacji funkcji przystosowania wokół maksimum lokalnego: a) wyjściowy krajobraz i funkcja modyfikująca, b) wynik modyfikacji / ii, �� i .-.��
.220.
5. Zapobieganie przedwczesnej zbieżności
neracji algorytmu o numerze k. Deformacja może być również wprowadzona poprzez wymnożenie dotychczasowej funkcji przystosowania
Kfe) (5.16)
a funkcja modyfikująca G może być równa
(5.17)
gdzie a jest parametrem odpowiadającym za "stromość" funkcji deformującej, r zaś określa zasięg deformacji. Algorytm powstały w ten sposób nazwano algorytmem sekwencyjnego niszowa-nia ze względu na podobieństwo do algorytmu z zastosowaniem metody podziału przystosowania, omawianej już wcześniej. Na rysunku 5.13 przedstawiono wyjściowy krajobraz adaptacyjny i wynik modyfikacji po znalezieniu jednego z maksimów lokalnych.
Znaczenie zasięgu deformacji. Kluczowe znaczenie z punktu widzenia poprawności działania metody sekwencyjnego niszo-wania ma właściwy dobór zasięgu deformacji wprowadzanej przez funkcję modyfikującą. Zbyt mały promień zasięgu może powodować powstanie dodatkowych maksimów funkcji przystosowania (których może być znacznie więcej niż jedno!). Z kolei przesadnie duży zasięg może powodować przesunięcie położeń maksimów lokalnych, a nawet doprowadzić do zaniku części z nich. Po trzecie, po wielokrotnych modyfikacjach można uzyskać bardzo płaski krajobraz, niewygodny do prowadzenia poszukiwań.
Nie ma, niestety, uniwersalnej metody doboru promienia zasięgu, niemniej jednak dość dobre wyniki zanotowano, przyjmując r ze wzoru (5.17) równe w przybliżeniu
(5.18)
gdzie p jest oszacowaniem liczby maksimów lokalnych funkcji przystosowania. Powyższy wzór wyprowadzono przy założeniach, że obszar dopuszczalny jest jednostkowym hipersześcianem i maksima lokalne są w nim równomiernie rozłożone*.
n
5.5. Inicjacja populacji bazowej
Zagadnienie inicjacji populacji bazowej nie wzbudza, jak dotąd, *Przy innym obszarze do- większego zainteresowania ze strony zarówno teoretyków, jak puszczainymnaieżatobyza- [ praktyków. W znacznej mierze jest to konsekwencją przekona-
stosować odpowiednie ska- . . , , . . . , . . , . , . ,.
iowanie. ma, ze algorytm ewolucyjny jest w stame prowadzić optymali-
5.5. Inicjacja populacji bazowej __ 221 _____
zację funkcji przystosowania dla dowolnej populacji początkowej. Jest to uzasadnione teoretycznie, gdyż rozważając w sensie probabilistycznym zbieżność algorytmu, nie czyni się założeń co do populacji początkowej. W praktyce, inicjacja populacji bazowej może mieć znaczenie przede wszystkim ze względu na szybkość dochodzenia przez algorytm do zadowalających rozwiązań.
Zmiany różnorodności populacji w czasie ewolucji. Atrakcyjność algorytmu ewolucyjnego i jego możliwości optymalizacji globalnej wynikają zarówno z mechanizmu losowego przeszukiwania, wprowadzanego przez operatory genetyczne, jak też z utrzymywania różnorodności populacji. Gdy populacja bazowa zawiera podobne do siebie chromosomy, wówczas przeszukiwanie realizowane przez algorytm ma charakter lokalny, podczas gdy duże zróżnicowanie prowadzi do przeszukiwań bardziej globalnych. Specyfiką algorytmu ewolucyjnego jest wbudowany weń mechanizm selekcji, ukierunkowujący algorytm. Powoduje on stopniowe przejście od globalności przeszukiwań do ich lokalności.
PRZYKŁAD. Prześledźmy przebieg zmian dyskrepancji* populacji bazowej dla algorytmu ewolucyjnego z operatorem mutacji z rozkładem Cauchy 'ego, selekcją progową nieelitarną i włączonym bądź wyłączonym operatorem krzyżowania uśredniającego. Przebieg zmian dyskrepancji oraz błędu względnego przedstawiono na rys. 5.14.
Jak łatwo zauważyć, duże zmiany rozwiązania osiągane są przy dużej różnorodności populacji bazowej, nacisk selektywny zaś powoduje w kolejnych generacjach jej zmniejszenie, co z kolei jest przyczyną zaniku zdolności eksploracyjnych algorytmu i może prowadzić do przedwczesnej zbieżności. Zjawisko to występuje z większym nasileniem w algorytmie wykorzystującym krzyżowanie uśredniające.
Z tych rozważań wynika, że w celu zapewnienia algorytmowi jak najlepszych warunków początkowych należy zadbać ojak największe zróżnicowanie populacji P�. Z tego względu, a także w celu uproszczenia metody generowania chromosomów, przyjmuje się, że populacja bazowajest na początku wypełniana elementami losowymi. Najpowszechniej stosowaną metodąjest wykorzystanie do tego celu rozkładu jednostajnego na zbiorze genotypów. Jeżeli jednak potrafimy wskazać najbardziej obiecujące obszary tego zbioru, wówczas może się opłacić wykonanie nierównomiernego posiewu, gęstszego w tych właśnie obszarach. Omówimy w skrócie wspomniane metody.
Zbiór zainteresowania. Chromosomy należące do początkowej populacji bazowej są przeważnie generowane losowo w taki sposób, że odpowiadające im fenotypy znajdują się w zbiorze zwanym zbiorem zainteresowania J C U. Może on pozostawać w na- t" ,. . . , ,
r *Defmicja dyskrepancji
stepujących relacjach względem zbioru dopuszczalnego D. znajdujesięwdodatkuD.i.
.222.
5. Zapobieganie przedwczesnej zbieżności
,,--'"' \ i, Błąd względny -------
03 \ _/\ \ Dyskrepancja -------
o1 L=: cc ! \j\ 'l <->>il : . . '

"O
G -o O>J '{ 1 ;'| >
"M N ^ 0.01
S ^' 1 ^ ''l^^1fl
n nni _ /I( ,
10
100
1000
(a)
10
o cs
>> T3
0.1
C 0.01
T3
0.001
0.0001
0.00001
1
Bląd względny Dyskrepancja

10
100
1000
(b)
RYSUNEK 5.14. Krzywe zmian dyskrepancji oraz btędu względnego dla algorytmu z krzyżowaniem (a) i bez krzyżowania (b)
5.5. Inicjacja populacji bazowej
.223.
� Miara zbioru dopuszczalnego nieskończona
Z taką sytuacją możemy mieć do czynienia wówczas, gdy nie istnieją funkcje ograniczeń lub gdy ograniczenia przez nie wprowadzone nie są dostatecznie ,^zczegolowe" (np. ograniczenia
� Xi > 0 dla każdego i = 1,..., n). Wtedy nie można wygenerować dowolnego punktu zbioru dopuszczalnego* i należy poczy-
, nić arbitralne założenia odnośnie zbioru J: jego miara powinna być skończona i większa niż zero. Najczęściej przyjmuje się, że J jest kostką n-wymiarową i J C D.
m Miara zbioru dopuszczalnego skończona
W takiej sytuacji często przyjmuje się, że zbiór zainteresowa-; nia jest tożsamy ze zbiorem dopuszczalnym J = D. Niekiedy jednak kształt zbioru dopuszczalnego powoduje, że zmienne losowe wykorzystywane podczas mutacji i inicjacji powinny spełniać bardzo duże wymagania (nieraz niewykonalne). Może się wówczas zdarzyć, że wygodniej jest zwiększyć zbiór zainteresowania w zamian za prostotę wykorzystywanych w algorytmie mechanizmów i wówczas J D D. Ceną jest jednak konieczność zdefiniowania funkcji celu poza obszarem dopuszczalnym lub jej zmodyfikowania w taki sposób, aby nie wprowadzić dodatkowych minimów lokalnych położonych poza zbiorem dopuszczalnym. Innym sposobem postępowania jest taka transformacja zmiennych niezależnych, która prowadzi do uproszczenia kształtu zbioru dopuszczalnego**, albo przyjęcie jako J takiego zbioru wpisanego w D, którego elementy dadzą się łatwo losowo generować.
� Miara zbioru dopuszczalnego zerowa
Ostatni z rozważanych przypadków zdarza się najczęściej przy ograniczeniach równościowych. Rodzi to spore komplikacje, gdyż dysponując zmiennymi losowymi, których nośnik jest nie-zerowej miary, nie sposób wygenerować punktu należącego do D. W takiej sytuacji warto zmniejszyć wymiarowość zadania poprzez odpowiednią transformację zmiennych niezależnych i redukcję ich liczby, tak aby obraz D w wyniku tej transformacji był niezerowej miary***. Inne postępowanie może polegać na przyjęciu, że interesują nas nie tylko punkty ze zbioru D, ale również takie, które są dostatecznie blisko zbioru dopuszczalnego. Wówczas J będzie zbiorem tych punktów, co może niekiedy prowadzić dojego nieskończonej miary, lub będziejego podzbiorem właściwym. Jeśli prowadziłoby to do nieskończonej miary J, należałoby zastosować dodatkowo jedno z wymienionych wcześniej podejść ograniczania miary zbioru zainteresowania.
Ze względu na prostotę definicji zmiennych losowych, przyjmuje się najczęściej, że J jest kostką n-wymiarową zawierającą zbiór dopuszczalny.
*Wykorzystanie komputera uniemożliwia posługiwanie się dowolnie dużymi co do modułu liczbami rzeczywistymi.
**To z kolei może powodować zaburzenia proporcji miar obszarów przyciągania minimów lokalnych. Jest to zjawisko niepożądane, gdyż może wprowadzać zakłócenia w algorytmie ewolucyjnym.
***Pamiętajmy o możliwości, że w wyniku transformacji zbiór D będzie nieskończonej miary! (na przykład płaszczyzna po transformacji z R3 do Rł).
.224.
5. Zapobieganie przedwczesnej zbieżności
Zbiór dopuszczalny nieskończonej miary. W takiej sytuacji musimy arbitralnie zdefiniować zbiór zainteresowania. Decyzja ta w konsekwencji "uprzywilejowuje" pewne punkty, gdyż niektóre genotypy mogą zostać wygenerowane już w procesie inicjacji populacji bazowej, podczas gdy do innych można dojść jedynie poprzez proces ewolucji. Podejmując tę decyzję, musimy się więc posługiwać wiedzą lub intuicją określającą w przybliżeniu obszary zbioru genotypów, w których należy oczekiwać rozwiązania.
Zbiór dopuszczalny skończonej miary. Skończona miara zbioru dopuszczalnego jest częstym przypadkiem w zadaniach praktycznych. Wówczas naturalne jest utożsamienie zbioru zainteresowania ze zbiorem zdefiniowanym przez te ograniczenia. Możliwe są przy tym dwa przypadki zbiór dopuszczalny może być iloczynem kartezjańskim zbiorów skończonej miary lub też mieć trudniejszą postać. , , ..
Pierwszy z przypadków oznacza gwarancję, że generując wartości kolejnych zmiennych niezależnych z rozkładem równomiernym na zbiorze wartości dopuszczalnych dla tej zmiennej, otrzymamy dopuszczalny chromosom. Jest to bardzo duże ułatwienie, gdyż nie ma potrzeby definiowania skorelowanych wielowymiarowych zmiennych losowych. Oznacza to również istnienie ograniczeń kostkowych dla zmiennych ciągłych.
Przypadek drugi oznacza występowanie ograniczeń funkcyjnych. Postępowanie zależy od metody ich uwzględnienia. Jeśli dopuszcza się istnienie w populacji bazowej punktów niedopuszczalnych, to zbiór zainteresowania można rozszerzyć do kostki zawierającej zbiór dopuszczalny. W przeciwnym przypadku, zadanie wygenerowania populacji początkowej może się skomplikować, trzeba bowiem zdefiniować skorelowane wielowymiarowe zmienne losowe, z pomocą których generowane będą osobniki dopuszczalne. Trudności z tym związane można obejść, ograniczając zbiór zainteresowania np. do kostki wpisanej w zbiór dopuszczalny. Może to jednak pociągać za sobą konieczność zwiększania eksploracyjności algorytmu, aby zniwelować wprowadzone "nie-równouprawnienie" w obszarze dopuszczalnym.
*wówczas ograniczeniami
puter.
5.5.1. Posiew nierównomierny
Metoda posiewu nierównomiernego jest szczególnie godna polecenia w dwóch sytuacjach gdy zbiór dopuszczalny jest nieskończonej miary oraz gdy można wskazać miejsca bardziej prawdopodobnego występowania dobrych rozwiązań.
Jeśli zbiór dopuszczalny jest nieskończonej miary, to można mimo wszystko założyć, że zbiór zainteresowania jest równy do-
J . * ' . , . ,*~,T:r' � i
puszczalnemu,zamiastsztuczmegozenwydzielac. Wowczasjeu-
5.5. Inicjacja populacji bazowej
.225.
nak trzeba odstąpić od założenia o równomierności rozkładu, a to z kolei ponownie wymaga podjęcia arbitralnej decyzji o "uprzywilejowaniu" pewnego podzbioru.
Jeśli znamy orientacyjną lokalizację rozwiązań "dobrych", możemy wykonać gęstsze próbkowanie w rejonie ich występowania. Z sytuacją taką możemy mieć do czynienia, gdy wygenerowanie choćby jednego elementu zbioru dopuszczalnego jest trudne (np. z powodu niewielkiej miary tego zbioru) wówczas, mając już takie rozwiązanie, można dokonywać jego perturbacji, aby uzyskać inne rozwiązania dopuszczalne.
5.5.2. Znaczenie generatora liczb pseudolosowych
Implementując algorytm ewolucyjny na maszynie cyfrowej, stajemy przed koniecznością komputerowego generowania liczb "losowych". Jednak ze względu na fakt, że do wygenerowania takich liczb musi być wykorzystany pewien (deterministyczny) algorytm, można mówić jedynie o liczbach pseudolosowych. Liczby takie powinny "wyglądać jak losowe", tzn. spełniać warunki jak najmniejszej korelacji, równomiernej gęstości wypełnienia zbioru wartości i wiele innych. Obecnie znane są liczne generatory liczb pseudolosowych, o dobrze poznanych i zbadanych właściwościach, dzięki czemu istnieje możliwość dobrania właściwego generatora.
Jednym z pierwszych sposobów wykorzystania generatorów liczb pseudolosowych było szacowanie metodą Monte Carlo całki oznaczonej dowolnej mierzalnej funkcji. Zwrócono przy tym uwagę, że wykorzystanie niektórych generatorów prowadzi do szybszego zmniejszania się błędu oszacowania, natomiast inne zachowują się nie najlepiej pod tym względem. Okazało się, że jedną z podstawowych cech decydujących o użyteczności generatora w zakresie całkowania numerycznego jest zdolność do równomiernego pokrywania przestrzeni. W celu porównywania tej cechy różnych generatorów wprowadzono pojęcie dyskrepancji zbioru punktów*. - .���:-.
Generatory o małej dyskrepancji. Szczególne miejsce wśród generatorów liczb pseudolosowych zajmują sekwencje o małej dyskrepancji. Ich cechą szczególną jest to, że ciągi liczb przez nie generowanych są bardzo równomiernie rozłożone (mają małą dys-krepancję). Dokładniej mówiąc, dla sekwencji liczb o małej dyskrepancji można od góry ograniczyć jej wartość, znając długość sekwencji. Cecha ta jest szczególnie przydatna przy całkowaniu numerycznym, gdyż ich zastosowanie pozwala na ograniczenie od góry maksymalnej wartości błędu wyniku. Równomierne rozłożenie w przestrzeni jest bardzo istotne również w fazie inicjacji populacji bazowej w algorytmie ewolucyjnym. Jeśli bowiem dys-
*Do pojęcia waliśmy się zji omawiani trzymania lucyjnego.
tego odwoły-już przy oka-a kryteriów za-lgorytmu ewo-
.226.
5. Zapobieganie przedwczesnej zbieżności
ponujemy generatorem liczb gwarantującym, że największa miara wypukłego zbioru nie zawierającego żadnego punktu sekwencji pseudolosowej jest mniejsza niż pewna wartość progowa, to wówczas wiemy, że co najmniej jeden chromosom będzie znajdować się w każdym wypukłym obszarze przyciągania maksimum lokalnego, którego miara jest nie mniejsza niż wartość progowa. Fakt ten ma podstawowe znaczenie dla eksploracji i przyczynia się do znacznie większej (w porównaniu z sekwencjami pseudolosowymi nie gwarantującymi tej właściwości) odporności na maksima lo-kalne,atakzeszybkoscizbieznosci. .-;-. : .-,
PRZYKŁAD. Rozważmy dwie przyktadowe funkcje celu Ra-strigina i Shuberta i spróbujmy je zoptymalizować, wykorzystując algorytm ewolucyjny z reprodukcją progową p = 0.31, zawierający p, = 160 osobników w populacji bazowej, z sukcesją wg schematu strategii ewolucyjnej (p + A). Prawdopodobieństwo krzyżowania Pc 0.7 (krzyżowanie uśredniające), mutacja zaś jest wykonywana z rozkładem normalnym. Algorytm jest zatrzymywany po 300 generacjach, o ile wcześniej nie uzyska się rozwiązania o wartości funkcji celu 10~8 (w przypadku funkcji Rastrigina) i 186.6 (funkcja Shuberta). W tabeli 5.1 (funkcja Rastrigina) i 5.2 (funkcja Shuberta) przedstawiono wyniki z 50 niezależnych uruchomień algorytmu ewolucyjnego; podano wartości średnie i odchylenia standardowe kosztu (mierzonego liczbą generacji) i uzyskanego wyniku. Podano wyniki dla następujących metod inicjacjipopulacji bazowej: siatka prostokątna, punkty wygenerowane z rozkładu równomiernego*, punkty pochodzące z generatora o małej dyskrepancji (dla trzech różnych generatorów Haltona, Sobola i Faure'go).
TABELA 5.1. Wyniki działania algorytmu ewolucyjnego z populacją bazową inicjowaną w różny sposób; funkcja celu Rastrigina
Typ rozkładu Koszt Wynik
średni odchylenie standardowe średni odchylenie standardowe
Siatka 56.90 50.86 0.040 0.20
Równomierny 49.02 36.60 0.020 0.14
Halton 50.48 36.58 0.020 0.14
Soból 49.02 36.57 0.019 0.14
Faure 44.16 4.74 io-10 itr10
*Generator wzięty z biblioteki stdlib.
Na podstawie tych tabel można stwierdzić, że najgorsze wyniki uzyskuje się, wypełniając populację początkową punktami rozmieszczonymi na siatce prostokątnej. Wydaje się, że przyczyną jest nadmierna regularność siatki, która utrudnia działanie operatora krzyżowania. Nieco lepsze wyniki (jest to widoczne zwłaszcza przy funkcji Rastrigina) można uzyskać, inicjując populację bazową punktami wygenerowanymi z rozkładujednostajnego. Istotna
5.6. Znaczenie liczności populacji bazowej
.227.
TABELA 5.2. Wyniki działania algorytmu ewolucyjnego z populacją bazową inicjowaną w różny sposób; funkcja celu Shuberta
Typ rozkładu Koszt Wynik
średni odchylenie standardowe średni odchylenie standardowe
Siatka 251.14 82.91 176.10 8.32
Równomierny 257.08 79.27 176.49 6.75
Halton 266.62 76.08 186.34 0.29
Soból 219.76 110.86 186.45 0.28
Faure 239.16 87.38 186.47 0.29
poprawa jest jednak możliwa dopiero przy wykorzystaniu jednej z sekwencji o malej dyskrepancji; wśród nich, najlepsze wyniki uzyskuje się przy zastosowaniu sekwencji Faure'go, najgorsze zaś przy sekwencji Haltona.
5.6. Znaczenie liczności populacji bazowej
Podobnie jak metody inicjacji populacji bazowej, również jej licz-ność nie wzbudza zbyt dużego zainteresowania. Wynika to z faktu, że zbieżność asymptotyczna algorytmu ewolucyjnego nie zależy od wartości p, i wystarczy jeden osobnik w populacji bazowej, aby algorytm miał tę właściwość. Jako zalecane przyjmuje się często takie wartości ^t, przy których algorytm ewolucyjny działa zadowalająco dla wielu funkcji testowych.
Niektórzy badacze twierdzą, że niewielka liczność populacji bazowej zapewnia "elastyczność" algorytmu ewolucyjnego. Obserwuje się, że małe populacje bazowe wykazują silniejsze tendencje do opuszczania obszaru przyciągania maksimum lokalnego funkcji przystosowania, duże zaś populacje mają tendencję do "osiadania" w nim (zwłaszcza przy intensywnym nacisku selektywnym).
Istnieje również odmienny pogląd, szczególnie rozpowszechniony w środowisku osób zajmujących się programowaniem genetycznym. Uważają oni mianowicie, że lepsze wyniki można uzyskać za pomocą algorytmu ewolucyjnego przetwarzającego dużą liczbę osobników (rzędu tysięcy). Uzasadniają to twierdzeniem o schematach, którego wyniki otrzymuje się przy założeniu nieskończonej populacji bazowej.
Niekiedy wyrażany jest też pogląd, że odporność algorytmu ewolucyjnego wzrasta monotonicznie wraz z licznością populacji; wzrost ten ma charakter nasycający się i istnieje taka wartość optymalna ^t*, powyżej której nie uzyskuje się już zauważalnej poprawy. Ponieważ koszt symulacji algorytmu ewolucyjnego jest wprost proporcjonalny do liczności populacji bazowej, najbardziej
.228.
5. Zapobieganie przedwczesnej zbieżności
opłaca się przyjąć optymalną liczność, równą fj,*. Kłopot w tym, że (jak się uważa) wartość ^* zależy od rozwiązywanego problemu (i mogą mieć na nią wpływ liczba wymiarów i maksimów lokalnych funkcji przystosowania), jak również od innych parametrów algorytmu (takich jak zasięg mutacji czy intensywność krzyżowania).
PRZYKŁAD. Sprawdźmy na konkretnym przykładzie wpływ licz-ności populacji bazowej na działanie algorytmu z reprodukcją progową p 0.25, z dwoma wariantami sukcesji: (p, + A) oraz trywialną. Algorytm, wykorzystujący mutację z rozkładem normalnym (bez krzyżowania), będzie zatrzymywany po wykonaniu 1000 obliczeń wartości funkcji przystosowania.
Rozważymy prostą jednowymiarową funkcję przystosowania
= max
a\ exp
(5.19)
z parametrami: a\ = 1.1, �2 = 1.0, p,\ = 1, ^2 = 1, o^i = 0.2, 02 = 1. Funkcja ta ma dwa maksima: lokalne (x = l,<&(z) = 1) i globalne (x -l,3?(x) l.lJ.
Będziemy zapamiętywać najlepszego znalezionego osobnika w każdym uruchomieniu i uśredniać tę informację po niezależnych uruchomieniach. Obserwując wartość średnią przystosowania lub argumentów tych niezależnych uruchomień, będziemy w stanie ocenić, ile razy znaleziono maksimum globalne, a ile lokalne. Wartość średnia przystosowania bliska 1.1 i genotypu bliska 1 będzie oznaczać, że algorytm częściej osiąga maksimum globalne, a wartości bliskie 1 będą świadczyć o jego zwiększonej podatności na maksimum lokalne.
Na rysunku 5.15 przedstawiono wyniki uzyskane dla sukcesji trywialnej. Z analizy wykresu wynika, że zwiększanie liczno-ści populacji bazowej powoduje początkowo pogorszenie, później zaś poprawę odporności algorytmu ewolucyjnego. Podobne zjawisko można zaobserwować (rys. 5.16) wprzypadku sukcesji (fj, + X). Jest to algorytm o większym nacisku selektywnym, dlatego też wyraźniej występują w nim omówione efekty.
Kształt otrzymanej zależności można tłumaczyć w następujący sposób. Odporność algorytmu ewolucyjnego jest wynikiem złożenia dwóch zjawisk (rys. 5.17):
1) możliwości opuszczenia przez populację obszaru przyciągania maksimum lokalnego,
2) możliwości wygenerowania punktu w populacji początkowej, który znajduje się w obszarze przyciągania maksimum globalnego.
5.6. Znaczenie liczności populacji bazowej
.229.
0 50 100 150 200 250 300 350 400 450 500
-0.5
(a)
1.1
1.08
1.06
1.04
1.02
1
0 50 100 150 200 250 300 350 400 450 500
fJ,
(b)
RYSUNEK 5.15. Uśrednione wartości genotypu (a) i przystosowania (b) 100 niezależnych uruchomień algorytmu ewolucyjnego dla różnych liczności populacji bazowej; zastosowano reprodukcję progową i sukcesję trywialną
.230.
5. Zapobieganie przedwczesnej zbieżności
0.5
1.08 -
1.06 -
O
1.04 -
1.02
0 50 100 150 200 250 300 350 400 450 500
(a)
50 100 150 200 250 300 350 400 450 500
(b)
RYSUNEK 5.16. Uśrednione wartości genotypu (a) i przystosowania (b) 100 niezależnych uruchomień algorytmu ewolucyjnego dla różnych liczności populacji bazowej; zastosowano reprodukcję progową i sukcesje (^i + A)
5.7. Równoległość w algorytmach ewolucyjnych
.231,
o ^
RYSUNEK 5.17. Zależność odporności algorytmu od liczności populacji bazowej (O\ odporność wynikająca ze zdolności do przekraczania siodeł, O-i odporność wynikającą z prawdopodobieństwa uchwycenia punktów w obszarach przyciągania maksimów lokalnych, Os odporność wynikowa, będącą skutkiem nałożenia dwóch poprzednich)
Zwiększanie liczności populacji bazowej powoduje, że populacja coraz trudniej opuszcza obszar przyciągania maksimum lokalnego; tendencja ta jest tym silniejsza, im większy nacisk selektywny. Wynika to z dwóch faktów. Po pierwsze, przekroczenie siodta przez ciąg mutacji o niewielkim zasięgu, prowadzące do powstania serii gorzej przystosowanych osobników, jest tym mniej prawdopodobne, z im większą liczbą osobników trzeba konkurować podczas reprodukcji i sukcesji. Po drugie, wraz ze wzrostem liczności populacji coraz mniej jest prawdopodobna taka makromutacja, która doprowadzi do utworzenia osobnika będącego w stanie konkurować z najlepszymi osobnikami z otoczenia maksimum lokalnego.
Wiemy również, że jeśli populacja początkowa jest tak tworzona, że wygenerowanie punktu z dowolnego obszaru ma nieze-rowe prawdopodobieństwo, to zwiększanie liczności populacji bazowej zwiększa prawdopodobieństwo wygenerowania punktu z obszaru przyciągania maksimum globalnego. Wten sposób, zwiększanie liczności populacji bazowej prowadzi do zwiększenia odporności.
Omówione tendencje sumują się, w wyniku czego możemy obserwować niemonotoniczny wpływ liczności populacji bazowej na odporność algorytmu.
5.7. Równoległość w algorytmach ewolucyjnych
Algorytmy ewolucyjne są technikami, które w szczególny sposób nadają się do zrównoleglenia. Wynika to z faktu, że naraz przetwarzanych jest wiele wzajemnie niezależnych osobników.
.232.
5. Zapobieganie przedwczesnej zbieżności
0 równoległości w algorytmach ewolucyjnych możemy mówić na etapie implementacji oraz koncepcji. W tym pierwszym przypadku, schemat algorytmu pozostaje bez zmian w dalszym ciągu selekcjajest scentralizowana. Natomiast drugi wariant oznacza decentralizację selekcji algorytmy takie są nazywane koewolucyjnymi.
5.7.1. Implementacje równoległe
Zrównoleglenie algorytmu ewolucyjnego na etapie implementacji jest możliwe dzięki temu, że na algorytm sklada się wiele niezależnych od siebie podobnych elementów. Po pierwsze, w populacji bazowej jest przechowywanych jednocześnie wiele osobników, dzięki czemu możliwe jest obliczanie wartości funkcji celu niezależnie dla każdego z nich. Po drugie, proces generowania nowych osobników w wyniku działania operatorów genetycznych przebiega niezależnie dla każdego osobnika potomnego (lub pary sprzężonych osobników potomnych).
Na rysunku 5.18 przedstawiono szczegółowy schemat algorytmu ewolucyjnego. Kroki algorytmu dające się zrównoleglić umieszczono w ramkach.
Zrównoleglenie na poziomie obliczania funkcji przystosowania pojedynczego osobnika. Obliczenie wartości funkcji
procedurę Algorytm ewolucyjny begin
t := 0
inicjacja P�
ocena
while (not warunek stopu) do begin
T* := reprodukcja PJ
O := operacje genetyczne T
ocena O
Pm := sukcesja(P*, O*) t := t + 1
end
end
RYSUNEK 5.18. Schemat algorytmu ewolucyjnego z zaznaczonymi krokami dającymi się zrównoleglić
5.7. Równoległość w algorytmach ewolucyjnych
.233.
przystosowania jest często najbardziej czasochłonne w przypadku problemów optymalizacji zaczerpniętych z ,^ealnego świata".
Najbardziej "drobnoziarnistym" podejściem jest zrównolegle-nie obliczania przystosowania pojedynczego osobnika. Efektywność takiego postępowania zależy w dużym stopniu od możliwości zrównoleglenia tkwiących w samej procedurze obliczania funkcji przystosowania, a zatem zależny od rozwiązywanego zadania.
PRZYKŁAD. Weźmy jako przyklad zadanie projektowania filtru o określonych właściwościach w pewnym pasmie częstotliwości. Załóżmy, że zadanie polega na znalezieniu filtru, który w pasmie < fminifmax ~> ma współczynnik tłumienia nie większy niż zadana wartość progowa. Funkcję przystosowania można więc zdefiniować jako
(5.20)
gdzie 4> jest funkcją określającą współczynnik tłumienia filtru dla częstotliwości fi, g zaśjestfunkcją agregującą.
Zauważmy, że obliczenie wartościfunkcjiprzystosowania daje się zdekomponować na wiele zadań niezależnych, polegających na wyliczeniu współczynnika tłumienia dla konkretnej częstotliwości; wynika z tego możliwość zrównoleglenia.
Zrównoleglenie obliczania przystosowania populacji. Nieco bardziej "gruboziarniste" podejście polega na zrównolegleniu procesu obliczania funkcji przystosowania dla wszystkich osobników populacji bazowej i potomnej. Etap oceny można podzielić na wiele wzajemnie niezależnych zadań obliczenia przystosowania pojedynczego osobnika, wykonywanych równolegle.
Zrównoleglenie reprodukcji i operacji genetycznych. Reprodukcja osobnika jest powtarzana wielokrotnie: tyle razy, aby można było skompletować odpowiednią liczbę osobników rodzicielskich potrzebnych do wykonania operacji genetycznych. Ponieważ dodatkowo różne operatory genetyczne mogą prowadzić do powstania różnej liczby osobników potomnych, trzeba by znać zawczasu liczbę osobników potomnych generowanych przez każdy z operatorów, tak aby można było zapełnić populację potomną. To z kolei wymagałoby przejścia przez scentralizowany etap wielokrotnego wyboru operatora genetycznego. Załóżmy więc, że w wyniku każdej operacji genetycznej powstaje dokładnie jeden osobnik potomny. Uproszczenie takie pozwala efektywnie zrównoleglić reprodukcję i operacje genetyczne, gdyż proces tworzenia każdego osobnika potomnego jest niezależny od pozostałych i polega na dokonaniu wyboru operatora, reprodukcji osobników rodzicielskich i wykonaniu operacji genetycznych.
.234.
5. Zapobieganie przedwczesnej zbieżności
Jedną z możliwych wersji zrównoleglonego algorytmu ewolucyjnego przedstawiono na rys. 5.19. Należy podkreślić, że nie jest to jedyny wariant zrównoleglenia.
procedurę Zrównoleglony algorytm ewolucyjny begin
t--=o .^;1 ��;..
for (i = 1,... ,^t) do begin asynchronicznie
generuj X* � P� ocena Xi e P�
end
while (not warunek stopu) do
begin
for (i = 1,..., A) do begin asynchronicznie
if(decyzjaokrzyzowaniu)then begin
c := wybór operatora krzyżowania for (k = l,...,fc(c)) do begin asynchronicznie
reprodukcja osobnika do T*
end
Y := mutacja(krzyzowanie T*)
else
X := reprodukcja osobnika z PL
; Y:=mutacja(X)
end
ocena Y '-'
dodajYdoO* 4
end
Pt+1 := sukcesja (P*, O*) t:=t + l end end
RYSUNEK 5.19. Zrównoleglony algorytm ewolucyjny jeden z możliwych wariantów (/i(c) liczba osobników rodzicielskich operatora krzyżowania c)
5.7. Równoległość w algorytmach ewolucyjnych
.235.
Oczekiwane korzyści ze zrównoleglenia. Korzyści, jakie odniesiemy ze zrównoleglenia algorytmu, zależą przede wszystkim od stopnia skomplikowania i wzajemnej niezależności poszczególnych jego elementów, które są wykonywane równolegle.
Dokonajmy teraz zgrubnego oszacowania korzyści płynących ze zrównoleglenia. Przyjmijmy następujące założenia dla czasu wykonania poszczególnych kroków algorytmu:
t&(n} obliczenie wartości funkcji przystosowania osobnika,
i9(yu) wykonanie operatorów genetycznych wraz z reprodukcją,
t[ losowanie operatorów genetycznych,
ts([i + A) wykonanie sukcesji,
ti(n) generowanie osobnika w populacji P�.
Załóżmy, że czas wykonania każdej z wyżej wymienionych czynności jest identyczny. Jeśli założenie to nie byłoby spełnione, należałoby prowadzić obliczenia, biorąc pod uwagę albo maksymalny czas wykonania (otrzymując ograniczenie górne tego czasu), albo wartość oczekiwaną (otrzymując przybliżenie wartości oczekiwanej).
Czas wykonania N generacji algorytmu ewolucyjnego w wersji sekwencyjnej wynosi więc
ti = fj, (ti(n} + ta,(n}} + N [X (tg(fj,) + ti + t<;,(n)) + ts(p, + A)]
(5.21)
w wersji zrównoleglonej zaś jak na rys. 5.19, przy założeniu, że do dyspozycji jest k nieobciążonych, jednakowych procesorów, oraz że algorytm przydziału zadań do procesorów jest "sprawiedliwy"*
(5.22)
+ N
gdzie K\ i K? są kosztami zrównoleglenia; \z\ oznacza najmniejszą liczbę całkowitą nie mniejszą niż z.
Analizując wyrażenie (5.22), łatwo spostrzeżemy, że o koszcie wykonania algorytmu decydują przede wszystkim kroki wykonywane w pętli głównej (ze względu na wymnożenie przez N). A zatem, najbardziej opłacalne wydaje się zrównoleglanie reprodukcji, operacji genetycznych i obliczania wartości funkcji przystosowania.
Należy zwrócić uwagę, że wartości tg(p), ts([i + A) zależą od liczności populacji. Charakter tych zależności jest zwykle liniowy lub kwadratowy, tak więc nie powinien mieć istotnego wpływu
J ' x r � ^ J
na złożoność obliczeniową algorytmu. Z kolei wartość t$(n) za-
... ,.
*Czyli procesory są rowno-
.236.
5. Zapobieganie przedwczesnej zbieżności
leży od liczby wymiarów rozwiązywanego problemu, co najczęściej jest czynnikiem decydującym o złożoności obliczeniowej algorytmu ewolucyjnego.
5.7.2. Algorytmy koewolucyjne
Zasada koewolucji polega na tym, że globalne oddziaływania na poziomie selekcji i krzyżowania, znamienne dla standardowego algorytmu ewolucyjnego, stają się w pewnym stopniu lokalne. Zasadę koewolucji realizuje się dwoma sposobami: za pomocą algorytmu wyspowego.(zwanego podpopulacyjnym) oraz algorytmu komórkowego (zwanego masowo równoległym lub dyfuzyjnym).
Algorytm wyspowy (podpopulacyjny). Składa się on z wielu populacji, które ewoluują niezależnie od siebie, sporadycznie wymieniając między sobą informacje (na przykład część osobników). Koewoluujące populacje mogą się składać z osobników tego samego typu bądź też różnych typów. Może się także zdarzyć (zwłaszcza w drugim z wymienionych przypadków), że w każdej z nich obowiązuje inna funkcja przystosowania; wówczas występuje często pewnego rodzaju zależność między funkcjami przystosowania poszczególnych podpopulacji9. Koewolucja może być modelem nisz ekologicznych: w ramach każdej z nich występuje konkurencja osobników o ograniczone zasoby, migracja zaś i krzyżowanie osobników między niszami zdarza się dość rzadko.
W każdej z podpopulacji wykonywany jest algorytm ewolucyjny, którego schemat naszkicowano na rys. 5.20.
Wykonywany w podpopulacji algorytm ewolucyjny tym różni się od schematu z jedną populacją, że dopuszcza dopływ osobników z "zewnątrz"; podobnie, możliwe jest wysłanie osobnika na zewnątrz. Osobniki te oczywiście nie giną, lecz są wprowadzane do innych podpopulacji.
Wymiana osobników między podpopulacjami. Spotyka się dwa modele wymiany osobników między podpopulacjami. Pierwszy z nich, zwany emigracją, polega na tym, że osobnik wysyłany na zewnątrz jest usuwany z populacji bazowej. Z kolei podczas imigracji, na zewnątrz wysyłana jest tylko kopia osobnika, on sam pozostaje zaś w populacji bazowej. Przyjęcia osobnika z ze-
9Znane są podejścia, w których koewolucja dotyczy dekompozycji zadania. W wektorze zmiennych niezależnych wyróżnia się dla każdej z podpopulacji zmienne ustalone, których wartości nie są przedmiotem ewolucji. Każda z podpopulacji ma uzmien-nioną inną część wektora zmiennych niezależnych. Nad całością czuwa proces (nie-ewolucyjny) koordynujący poszukiwania. Inne przykładowe rozwiązanie polega na koewolucji populacji rozwiązań i populacji funkcji ograniczeń. ,
5.7. Równoległość w algorytmach ewolucyjnych
.237.
procedurę Algorytm ewolucyjny w podpopulacji begin
t := 0
inicjacja P*
ocena P*
while (not warunek stopu) do
begin
T4 := reprodukcja P* O* := operacje genetyczne T* ocena O*
Pt+l := sukcesja (P*,O*) wymiana osobników z innymi podpopulacjami . t := t + 1 end end
RvsuNEK 5.20. Algorytm ewolucyjny wykonywany w podpopulacji
wnątrz dokonuje się w sposób analogiczny do sukcesji można na przykład stosować schemat elitarny lub preselekcję.
Wymiany informacji między podpopulacjami można dokonywać różnymi sposobami zbiór podpopulacji może być nieuporządkowany albo też może być przyjęta relacja sąsiedztwa podpopulacji. W j5ierwszym przypadku wymiana osobników następuje między dowolnymi dwiema podpopulacjami, w drugim zaś jest ograniczona do sąsiadujących podpopulacji. Rzeczjasna, pierwszy z wymienionych sposób ma charakter bliższy scentralizowanemu algorytmowi ewolucyjnemu, można się więc spodziewać większego nacisku selektywnego (a więc szybszej zbieżności i mniejszej odporności na maksima lokalne).
Na rysunku 5.21 przedstawiono najczęściej spotykane w literaturze topologie. Jak dotychczas brak jest jednoznacznych informacji, które topologie są najbardziej godne polecenia. Wydaje się natomiast, że w przypadku implementacji algorytmu podpopu-lacyjnego na komputerze równoległym lub w sieci komputerów, powinno się przede wszystkim uwzględniać topologię właściwą dla środowiska implementacji ze względu na dobre wykorzystanie możliwości sprzętu. Chodzi przede wszystkim o wykluczenie niebezpieczeństwa, że algorytm większość czasu będzie poświęcał na komunikację między podpopulacjami (co może się zdarzyć przy słabej przepustowości połączeń między jednostkami obliczeniowymi i niewłaściwym ich wykorzystaniu). Warto na koniec podkreślić, że wybór topologii podpopulacji ma arbitralny charakter i nie jest związany z topologią przestrzeni genotypów.
.238.
5. Zapobieganie przedwczesnej zbieżności
A-.
(a)
(b)
(c)
(d)
RYSUNEK 5.21. Topologie podpopulacji najczęściej spotykane w literaturze: a) ,,czysty" model wyspowy, b) wielowymiarowy torus, c) hipersześcian, d) drabina. Węzły oznaczają podpopulacje, krawędzie zaś dopuszczalne kierunki migracji osobników
Algorytm komórkowy (masowo równoległy). Algorytm taki uznawany jest za stosunkowo skuteczną technikę optymalizacji wielomodalnej. W populacji osobników obowiązuje pewna arbitralnie wybrana topologia (nie związana z topologią przestrzeni genotypów). Dla każdego osobnika Xż jest zdefiniowane sąsiedztwo 7Vr(X*) (r jest jego promieniem). Każdy osobnik podlega niezależnej ewolucji. Polega ona na tym, że wchodzi on w interakcje (selekcja, krzyżowanie i mutacja) z osobnikami z ATr(X*) (rys. 5.22), co prowadzi do wygenerowania nowego osobnika Y*,
O O O O O O O O O O O
o o o ^o] o o o o o o o
O oR)OOJO O O O O O
o o
o o o o o
O ' ' | ' 0 O O O O O � O � >j oJ O O O
o o oo|o >^> ojO O O O � ^jJ � ' O O O O . '
o o o o o o o o o o o o o o o o o o o o o o
RvsuNEK 5.22. Wyróżnianie podpopulacji konkurujących osobników w komórkowym algorytmie ewolucyjnym. Jeden osobnik zwykle należy do wielu podpopulacjijednocześnie
który konkuruje z X* na etapie sukcesji. Schemat tego algorytmu przedstawiono na rys. 5.23; wykonuje się go asynchronicznie dla każdego osobnika z populacji bazowej.
Algorytm komórkowy jest niekiedy nazywany dyfuzyjnym. Powodem jest sposób rozprzestrzeniania się rozwiązania, któ-
5.8. Uwagi bibliograficzne
.239.
procedurę Komórkowy algorytm ewolucyjny begin
t := 0
inicjacja X*
ocena XL
while (not warunek stopu) do
begin
T4 := reprodukcja (X* U Nr(X*)) Y* := operacje genetyczne (T*) ocena Y*
X*+1:=sukcesja({X*,Y'}) t := t + 1 end end
RvsuNEK 5.23. Model komórkowy algorytm ewolucyjny na poziomie pojedynczego osobnika
re powstało w miejscujednego z osobników populacji. W kolejnych generacjach rozwiązanie to, wskutek działania selekcji, powiela się dla sąsiednich osobników*. Jeśli w populacji powstały różne rozwiązania o porównywalnym przystosowaniu, to obszary, w których dominują, oddziela "front" osobników granicznych. Front ten jest miejscem, gdzie najczęściej powstają nowe ciekawe osobniki.
Rola relacji sąsiedztwa. Kluczową rolę w algorytmie komórkowym odgrywa relacja sąsiedztwa, wykorzystywana do określania konkurujących ze sobą osobników. Im większa liczba osobników znajduje się w sąsiedztwie, tym większyjest zasięg selekcji. To z kolei sprawia, że algorytm ma mniejszą odporność na maksima lokalne, za to szybszą zbieżność (mniejszy koszt obliczeniowy). Dzięki temu, manipulując liczbą osobników w sąsiedztwie, można uzyskać algorytm ewolucyjny o pożądanych właściwościach.
5.8. Uwagi bibliograficzne
Istnieje pokusa opracowywania jak najbardziej uniwersalnych algorytmów genetycznych (wyraz jej dał np. Goldberg [31], przeciwstawiając sobie metody lokalne, Monte Carlo i algorytmy genetyczne). Jednak jest wiele prac ukazujących niewątpliwe korzyści z hybrydyzacji z metodami lokalnymi (np. [34, 541). Włą- 'w. sp05Ób Jied?sl??ałł*
J J J J J J >� * l ' >' <� zaburzony wskutek działa-
czenie metody optymalizacji lokalnej jako operatora mutacji zna- nia krzyżowania i mutacji.
5. Zapobieganie przedwczesnej zbieżności
leźć można np. w [48]. Z kolei operator krzyżowania jako metoda optymalizacji lokalnej był wykorzystywany m.in. w [98, 111].
Osłabienie odporności w ewolucji lamarkowskiej i jej poprawę dzięki istnieniu efektu Baldwina opisano w [109].
Reprodukcję z ograniczaniem maksymalnego czasu życia użytą do strategii ewolucyjnej opisano np. w [95]. Znane jest również wykorzystanie tego pomysłu w tzw. steady-state genetic algo-rithm, czyli algorytmie z reprodukcją proporcjonalną i ściskiem, A = 1 [29]. Z kolei selekcję sterowaną czasem życia wprowadzono w [4] i rozwinięto w [1] (stamtąd pochodzą cytowane wyniki).
Podziałowi przystosowania wiele miejsca poświęca Goldberg [31]; nieco nowszy przegląd można znaleźć również w [49]. Tam również omówiono sekwencyjne metody niszowania (patrz także [62]). Znane są również nieewolucyjne metody optymalizacji oparte na lokalnych deformacjach funkcji celu, opisane jako penalty methods w [103].
Aimo Tórn pod koniec lat 70. wprowadził w [103, 110] algorytm optymalizacji bazujący na grupowaniu. Preselekcja i ścisk należą do jednych z wcześniejszych pomysłów utrzymywania różnorodności populacji bazowej, obecnie mało popularnych. Ich omówienie można znaleźć w [31].
Zagadnienie inicjacji populacji bazowej jest bardzo słabo poznane. Pomysł wykorzystania sekwencji o małej dyskrepancji do inicjacji populacji powstał w kilku niezależnych od siebie ośrodkach [12, 97]. Wyniki eksperymentów pochodzą z pracy [97]. Algorytm z selektywnie destrukcyjnym restartem opisano w [50].
Hipotezę o istnieniu optymalnej liczności populacji bazowej sformułowano w [60]. W artykule [44] można zapoznać się ze stwierdzeniem, że mniejsze populacje mają tendencję do łatwiejszego opuszczania obszaru przyciągania maksimum lokalnego, a zatem prowadzą do utworzenia bardziej odpornego algorytmu. W pracy [65] wykazano, że najszybszą zbieżność dla funkcji z do-kładniejednym maksimum globalnym można uzyskać dla liczności populacji bazowej ^ = 1 (nie oznacza to jednak, że właściwość ta dotyczy funkcji o wielu maksimach lokalnych, ani że taki algorytm jest najodporniejszy). Tam również zaproponowano algorytm modyfikacji liczności populacji bazowej w sposób proporcjonalny do zasięgu mutacji.
Przegląd tematyki algorytmów koewolucyjnych opracowano na podstawie [64, 96]. Przykładowe algorytmy koewolucyjne z różnymi funkcjami przystosowania w poszczególnych populacjach można znaleźć w [67] (algorytm z dekompozycją i koordynacją zadania) i [63] (koewolucja ograniczeń i osobników). O wpływie struktury sąsiedztw na odporność komórkowych algorytmów ewolucyjnych można przeczytać w [17, 89].
'.-.�;��'. 5.9. Pytania i ćwiczenia
5.9. Pytania i ćwiczenia
1. Rozważmy algorytm przetwarzający jeden punkt, dokonujący jego perturbacji i akceptujący nowy punkt z prawdopodobieństwem p+, jeśli daje poprawę przystosowania, i z p-, jeśli pogarsza przystosowanie (patrz p. 3.2.1). Rozważmy funkcję przystosowania jak w p. 3.2.1. Załóżmy, że w pewnej chwili punkt roboczy znajduje się w obszarze przyciągania maksimum lokalnego (np. X� = 1/2). Jakie jest prawdopodobieństwo opuszczenia obszaru przyciągania maksimum lokalnego w ciągu dwóch generacji, jeśli schemat algorytmu wzbogacony zostanie o dostrajanie metodą lokalną z efektem Baldwina? Jaki będzie wpływ przyjęcia ewolucji lamarkowskiej na działanie algorytmu?
2. Czy prawdziwe jest twierdzenie, że ewolucja lamarkowska zawsze prowadzi do zmniejszania różnorodności populacji (jeśli tak, uzasadnij odpowiedź, w przeciwnym przypadku, podaj kontrprzykład) ?
3. Jaki jest i z czego wynika dodatkowy nakład obliczeń związany z określeniem zmodyfikowanej funkcji przystosowania przez funkcję podziału? Zaproponuj sposób zmniejszenia kosztu tej operacji analogiczny do algorytmu preselekcji ze ściskiem. Czy problem ten występuje w metodzie sekwencyjnego niszowania?
4. Rozważmy algorytm z losowym zaburzaniem funkcji przystosowania; zmodyfikowaną funkcję przystosowania oznaczmy <&'(X) = 3?(X) + L. Załóżmy, że dysponujemy algorytmem maksymalizacji przetwarzającymjeden punkt roboczy X4, który dokonuje losowej perturbacji tego punktu; wynik tej perturbacji Y* jest akceptowany jako nowy punkt roboczy Xt+1, jeśli <&'(Y') > <&'(X*) (patrz p. 3.2.1). Załóżmy, że perturbacja ma ograniczony zasięg, a zmienna losowa L przyjmuje wartości z przedziału [-o,..., a] z niezerowym prawdopodobieństwem. Jakie warunki powinny być spełnione, aby taki algorytm miał niezerowe prawdopodobieństwo osiągnięcia maksimum globalnego z dowolnego punktu startowego? (Wskazówka: rozważ różnicę między wartościami funkcji przystosowania w maksimum lokalnym i na brzegu jego obszaru przyciągania).
5. Jakajest różnica między sukcesją elitarną a mechanizmem preselekcji? Czy preselekcja gwarantuje pozostawienie najlepszego osobnika z populacji bazowej?
6. Załóżmy, że wykorzystujemy algorytm ewolucyjny, którego jedynym operatorem genetycznym jest krzyżowanie uśredniające, wieloosobnicze, h > n + 1. Który sposób inicjacji populacji bazowej daje większą szansę znalezienia maksimum global-
.241,
.242.
5. Zapobieganie przedwczesnej zbieżności
nego: rozmieszczenie chromosomów z rozkładem jednostajnym na brzegu zbioru dopuszczalnego czy w jego wnętrzu?
7. Rozważmy zadanie opisane w podrozdziale 3.2.1. Załóżmy, że dysponujemy algorytmem z selekcją (^i, 1) przetwarzającym populację P* zawierającą ^, osobników. W populacji P� wszystkie chromosomy znajdują się w obszarze przyciągania maksimum lokalnego. Jeden z nich X = 1/4, pozostałe zaś spełniają warunek X < 1/2. Jak zmienia się prawdopodobieństwo w zależności od wartości p, że w populacji Pt+1 znajdzie się chromosom należący do zbioru przyciągania maksimum globalnego?

Wyszukiwarka