CZĘŚĆ II

Wykład 3.
Zarządzanie populacją

Algorytm ewolucyjny określa sposób przeszukiwania przestrzeni chromosomów. W tym wykładzie przedstawiono ramowy schemat algorytmu oraz różne metody selekcji i omówiono sposób sterowania naciskiem selektywnym w każdej z nich. Wykład zakończono informacją na temat kryteriów zatrzymania algorytmu ewolucyjnego.

3.1. Ogólny schemat algorytmu ewolucyjnego

Definiując algorytm ewolucyjny, należy określić:
1) schemat algorytmu ewolucyjnego,
2) sposób kodowania i operatory genetyczne.
Należy również zdefiniować środowisko działania algorytmu ewolucyjnego, czyli funkcję przystosowania, oceniającą genotypy osobników.
Rodzaj kodowania problemu i operatory genetyczne określają "sposób patrzenia" na dziedzinę rozwiązywanego problemu. Rzecz jasna, ten sam problem można zakodować na wiele sposobów, tworząc różne środowiska działania algorytmu ewolucyjnego; można także w ramach tego samego środowiska określić wiele różnych operatorów krzyżowania i mutacji. Dobrym tego przykładem może być problem komiwojażera, dla którego znanych jest wiele sposobów kodowania problemu oraz liczne, nieraz bardzo wymyślne operatory krzyżowania. Zagadnieniom specjalizowanych operatorów genetycznych poświęcono następny wykład, natomiast w tym zajmiemy się głównie reprezentacjami najpowszechr)isi używanymi rzeczywistoliczbową i binarną
3. Zarządzanie populacją
skupiając uwagę na operatorach mogących uchodzić za "standardowe".
Ogólny schemat algorytmu ewolucyjnego podano na rys. 3.1.
procedurę Algorytm ewolucyjny begin
t := 0
inicjacja P�
ocena P�
while (not warunek stopu) do
begin
TŁ := reprodukcja P* �*"*"�""* Of := operacje genetyczne ocena O* PL+1 := sukcesja (P*, O*)
t := t + 1 end
end ( . . f _, , . ,-" , /;,
RYSUNEK 3.1. Schemat ogólny algorytmu ewolucyjnego
Algorytmem ewolucyjnym przetwarza się populację P* osobników. W pętli głównej działają kolejno: reprodukcja, operatory genetyczne i sukcesja. Proces ten trwa dopóty, dopóki nie zostanie spełniony warunek zakończenia.
Operacje reprodukcji i sukcesji określa się często wspólnym terminem selekcja. Podczas reprodukcji, osobniki o lepszym przystosowaniu są powielane z większym prawdopodobieństwem niż osobniki gorzej przystosowane; w ten sposób, algorytm ewolucyjny jest ukierunkowany poprzez selekcję w stronę lepszych rozwiązań. Tendencję algorytmu do poprawiania średniej wartości przystosowania populacji bazowej nazywa się naciskiem selektywnym; algorytm ma tym większy nacisk selektywny, im większa jest wartość oczekiwana liczby kopii lepszego osobnika w porównaniu z wartością oczekiwaną liczby kopii gorszego osobnika. Różnica między reprodukcją a sukcesją polega na tym, że reprodukcja określa sposób tworzenia populacji tymczasowej Tf, która jest poddawana działaniu operacji genetycznych, dając populację potomną Os, sukcesja zaś określa, jak utworzyć nową populację bazową Pt+l (po zadziałaniu operacji genetycznych). Niekiedy rnówi się o preselekcji (reprodukcji) i postselekcji (sukcesji).
3.2. Eksploracja i eksploatacja
.107.
3.2. Eksploracja i eksploatacja
Opisując właściwości algorytmu ewolucyjnego, dość często używa się pojęć eksploracja i eksploatacja. Pojęcia te mają przede wszystkim intuicyjny charakter, dlatego posłużymy się analogią prześledzimy proces poszukiwania złóż ropy naftowej. Poszukiwanie polega na dokonywaniu odwiertów w miejscach, gdzie należy się spodziewać występowania tego surowca. Niektóre z tych prób kończą się sukcesem, wiele zaś porażką. Na tym polega eksploracja. Jeśli złoże zostanie zlokalizowane, wykonuje się wiele odwiertów, aby zwiększyć możliwości wydobywcze jest to eksploatacja zlokalizowanego złoża.
Spróbujmy teraz posłużyć się intuicją do przeszukiwań realizowanych przez algorytm ewolucyjny. Wyobraźmy sobie dziedzinę funkcji przystosowania zbiór wszystkich chromosomów G (rys. 3.2). Oznaczmy maksimum lokalne tej funkcji przez X. Załóżmy, że dla rozwiązywanego problemu maksymalizacji funkcji przystosowania dysponujemy pewnym idealnym algorytmem, dzielącyrn dziedzinę funkcji przystosowania na rodzinę wzajemnie rozłącznych zbiorów przyciągania maksimów lokalnych G(X).
*(X)
RYSUNEK 3.2. Wykres trójwymiarowy przykładowej funkcji przystosowania. Wyraźnie widoczne liczne maksima lokalne wraz z obszarami przyciągania
-': ' V , -j ? ." ;'T '
Przez eksploatację można rozumieć przeszukiwanie obszaru przyciągania G(X) w celu wyznaczenia maksimum lokalnego X. Jest to zatem zadanie optymalizacji lokalnej. Zarówno w przypadku zadań ciągłych, jak i dyskretnych, znane są liczne efektywne metody i istnieje dobrze ugruntowana teoria. Natomiast eksploracja polega na wybraniu zbioru G(X*), zawierającego maksimum globalne X*, z rodziny obszarów przyciągania ekstre-mów lokalnych.
Jeśli rodzina obszarów przyciągania i wartości funkcji przystosowania w maksimach lokalnych byłyby znane, to wówczas eksploracja sprowadziłaby się do ich przejrzenia i wskazania najlepszego. Niestety, najczęściej taka informacja nie jest dostępna, ajej pozyskanie jest bardzo trudne*. Stąd blisko już do wniosku,
maksimum
.108.
3. Zarządzanie populacją
że zadanie optymalizacji globalnejjest nierozwiązywalne*. Nie oznacza to jednak, że należy zaniechać poszukiwania metod optymalizacji prowadzących do uzyskania dobrych rozwiązań przybliżonych z akceptowalnym kosztem. Algorytmy ewolucyjne sąjedną z wielu takich technik.
3.2.1. Nacisk selektywny w prostej metodzie poszukiwań losowych
Równoważenie eksploracji i eksploatacji (nacisk selektywny) ma istotny wpływ na sposób działania algorytmu. Rozważmy prostą funkcję przystosowania daną wzorem (rys. 3.3)
X + 8 dla - 8 < X < -4
-X dla - 4 < X < 0
X dla 0 < X < 5
-X + 10 dla 5 < X < 10
(3.1)
*(X)
RvsuNEK 3.3. Funkcja przystosowania opisana w przykładzie rachunkowym
Rozważmy algorytm z rysunku 3.4. Algorytm przetwarza jeden punkt roboczy Xł. W każdym kroku jest generowany nowy punkt Yt poprzez perturbację Xł, polegającą na dodaniu wartości zmiennej losowej o rozkładzie jednostajnym na przedziale [1,1] (gęstość prawdopodobieństwa jest funkcją stałą o wartości 1/2). Punkt Yl staje się nowym punktem roboczym w następujących warunkach: jeśli jego przystosowanie jest większe, prawdopodobieństwo jego akceptacji wynosi p+, jeśli zaś przystosowanie jest mniejsze, akceptacja zachodzi z prawdopodobieństwem p-. Zba-*Oznacza to, że dia dowoi- dajmy zachowanie powyższego algorytmu dla dwóch różnych po-
nej funkcji nie sposób zna- i � , y-Q
leźć w skończonej liczbie lOZ6n A .
iteracji algorytmu optyma- '- =Ti . �' �<'=
iizacyjnego jej maksimum Opuszczenie obszaru przyciągania maksimum lokalnego.
globalnego z dowolnie ma- r r, r . cc* �
łym błędem. Rozważmy punkt X 1/2. Znajduje się on w obszarze przy-
3.2. Eksploracja i eksploatacja
.109.
procedurę Przykładowy algorytm begin
t := 0
inicjacja X�
while (not warunek stopu) do
begin
Ył := perturbacja Xł if ($(y4) > *(A^*)) then begin
if (%(o,i) < P+] then begin
Xt+l ._ yt
else
Xt+l := X' end else
if(&/(o,i) else
Xt+l := end
end
i := t+1
end
end
RvsuNEK 3.4. Algorytm z przykładu rachunkowego
ciągania maksimum lokalnego. W wyniku perturbacji, możemy otrzymać punkt Yl 6 (3/2, 1/2) z jednakową gęstością prawdopodobieństwa. Są możliwe trzy przypadki:
1) F1 jest w obszarze przyciągania ekstremum globalnego
i<&(yi)<<&(A(y!e(o,i/2)),
2) Yl jest w obszarze przyciągania ekstremum lokalnego
3) y1 jest w obszarze przyciągania ekstremum lokalnego i ^(y1) < $(X�), (Yl 6 (-l/2,0)).
Jeśli przyjmiemy p+ = 1 i p- = 0, otrzymamy algorytm wzrostu, akceptujący zawsze lepsze rozwiązania. Rzeczą oczywistą
.110.
3. Zarządzanie populacją
jest, że w omawianej sytuacji (startując z X� = 1/2) niemożliwe jest wygenerowanie za pomocą tej strategii punktu roboczego Xł znajdującego się w obszarze przyciągania maksimum globalnego*. Rozważmy teraz algorytm o dowolnych wartościach p+ i p_ i sprawdźmy, jakie jest prawdopodobieństwo, że po dwóch ite-racjach osobnik X2 będzie w obszarze przyciągania maksimum globalnego i 3>(X2) > 3>(X0), czyli X2 > 1/2: � ;
. dlaX0 = 1/2
pn = Prob{-3/2 < X1 < -l/2\X0 = -1/2} = 1/2 (3.2)
pi2 = Prob{-l/2 < X1 < 0\X� = -1/2} = 1/4 (3.3)
pi3 = Prob{0 < X1 < l/2\X0 = -1/2} = 1/4 (3.4)
� dla -3/2 < X1 < -1/2
P2i = Prob{X2 > l/2\ - 3/2 < X1 < -1/2} = 0 (3.5)
. dla -1/2 p22 = Prob{X2 > 1/2 - 1/2 < X1 < 0} = ; i,
= 1/2
l/2)dz = l/16
-1/2
. dla 0 < X1 < 1/2
p23 = Prob{X2 > 1/2|0 < X1 < 1/2} =
l/2)dx = l/16
(3.6)
l/2
(3.7)
Mamy więc: !*
> 1/2} = P12P^P22P++P13P-P23P+ = l/32p_p+ (3.8)
Wartość Prob{X2 > 1/2} osiąga maksimum dla p_ = p+ = 1, czyli dla procesu błądzenia przypadkowego. Wynika z tego, że akceptowanie najlepszego punktu już po dwóch iteracjach prowadzi do gorszej sytuacji, niż przyjęcie gorszego jako nowego punktu roboczego. Z punktu widzenia zdolności opuszczania obszarów przyciągania maksimów lokalnych, proces błądzenia przypadkowego jest rzeczywiście dobrym rozwiązaniem. Prześledźmy teraz, jak prawdopodobieństwa akceptacji lepszych i gorszych rozwiązań wpływają na szybkość zbieżności algorytmu do maksimum (lokalnego) funkcji przystosowania.
*Wynika to z faktu, że
osiągalne punkty z ob- Podążanie w strone maksimum. W tym celu załóżmy, że
szaru przyciągania maksi- ^
mum globalnego naieżą do X = 2. Podobnie jak w poprzednim przypadku, obliczmy praw-przedziatu [o, . . . , i/2], a dopodobieństwo zdarzenia, że $(X2) > $(X�) + 1/2 (co jest rów-
więc mają przystosowanie r . . r, ' v ' v ' ' v J
mniejszenlzpunktroboczy. nOWaŻnC, Ż6 X > 5/2): - .,,
3.2. Eksploracja i eksploatacja
.111.
. dla X� = 2
pn = Prob{l < X1 < 3/2\X0 = 2} = 1/4
pi2 - Pro6{3/2'< X1 < 2\X� = 2} = 1/4
p13 = Pro&{2 < X1 < 5/2\X0 = 2} = 1/4
pi4 = Pro6{5/2 < X1 < 3|X� = 2} = 1/4
� dla 1 < X1 < 3/2
P2! = Pro6{X2 > 5/2|l < X1 < 3/2} = 0
. dla 3/2 < X1 < 2
p22 = Proh{X2 > 5/2|l < X1 < 2} =
= 1/2 / (x - 3/2}dx = 1/16 ^3/2
� dla 2 < A'1 < 5/2
p23 = Pro6{X2 > 5/2|2 < X1 < 5/2} =
= 1/2 / (x - 3/2)rfx = 3/16
.2
dla 5/2 < X1 < 3 4 = Pro6{5/2 < X2 < X^5/2 < X1 < 3} =
r3
= 1/2/ (x-5/2)dx = l/16
./52
A zatem '�
Prob{X2 > 2} = pn
(3.9) (3.10) (3.11) (3.12)
(3.13)
(3.14)
(3.15)
(3.16) (3.17)
p2i + (1 - P-)puP+] +
+ Pl2 fr-P22P+ + (1 - p-)
+pi3 fr+p<23p+ + (1 - p
+ PU [P+(P24P- + P25P+) + (1 - p+)pup+] =
=l/64p+(16-7p_ + 3p+) (3.18)
Jak widać, zwiększanie wartości p+ zwiększa prawdopodobieństwo przybliżenia do maksimum globalnego, większa wartość P- zaś spowalnia ten proces. Największą wartość prawdopodobieństwo przybliżenia osiąga dla p+ = 1 i p- = 0, czyli dla algorytmu wzrostu.
Nacisk selektywny. Jak mogliśmy się przekonać, najsilniejszą tendencję do opuszczania obszarów przyciągania maksimum lokalnego ma algorytm błądzenia przypadkowego, w którym punkt
.112.
3. Zarządzanie populacją
będący wynikiem perturbacji jest akceptowany jako nowy punkt roboczy niezależnie od jego przystosowania. Niestety, algorytm ten ma równie silną zdolność opuszczania obszaru przyciągania maksimum globalnego. Z kolei jeśli chodzi o szybkość zdążania ku maksimum globalnemu, najlepiej byłoby wybrać algorytm wzrostu. Niestety metoda ta z równą skutecznością będzie zmierzać ku maksimum lokalnemu. Algorytm optymalizacji globalnej, równoważący eksplorację (opuszczanie obszarów przyciągania) i eksploatację (podążanie w kierunku maksimum lokalnego) jest rozwiązaniem kompromisowym między tymi dwoma i jako taki, łączy zarówno zalety, jak i wady błądzenia przypadkowego i algorytmu wzrostu. Proporcje eksploracji i eksploatacji zależą od wartości p-i p+ i są nazywane naciskiem selektywnym, który jest tym większy, im algorytm bardziej przypomina metodę wzrostu. Można by się na przykład umówić, że miarą nacisku selektywnego jest wartość (1 -p-)p+.
*Niezależne uruchomienia oznaczają, że populacje bazowe P są różne. Niekiedy można się spotkać z praktyką wykonywania wietu uruchomień algorytmu z taką samą populacją P�, lecz różnym ziarnem generatdra liczb pseu-dolosowych w takim przypadku można mówić o właściwościach tego algorytmu dla tej konkretnej populacji początkowej.
**Zdarza się niekiedy, że w celu zbadania możliwości opuszczania przez algorytm obszaru przyciągania maksimum lokalnego funkcji przystosowania, początkowa populacja jest wypełniana kopiami osobnika kodującego to maksimum.
3.3. Jak oceniać algorytmy ewolucyjne
3.3.1. Metoda testowania i sposób prezentacji wyników
Charakterystyczny dla algorytmów ewolucyjnych (jak i dla wszystkich metod niedeterministycznych) jest fakt, że przy jednakowych ustawieniach parametrów i identycznych populacjach początkowych można obserwować różne zachowanie algorytmu w niezależnych uruchomieniach. Powodem jest element losowo-ści obecny zarówno w selekcji, jak i w operacjach genetycznych. Dokonanie rzetelnej oceny algorytmu wymaga więc wykonania wielu niezależnych uruchomień* dla losowej próby różnych populacji bazowych P�. Jeśli porównywane są dwa algorytmy, wskazane jest, aby próba ta była taka sama (czyli aby dla każdej losowej populacji początkowej uruchamiane były dwa porównywane algorytmy)**.
Wyniki niezależnych uruchomień powinny być poddawane analizie statystycznej. Najprostszy sposób to ograniczenie się do analizy wartości oczekiwanej i odchylenia standardowego wartości przystosowania w populacji bazowej. W ten sposób dobrze można scharakteryzować jedynie rozkład symetryczny wokół wartości oczekiwanej (a najlepiej zbliżony do rozkładu normalnego). Dlatego warto brać pod uwagę na przykład informację o minimalnej i maksymalnej osiąganej wartości bądź też informację o liczbie przypadków niewiele różniących się od najlepszego. Dobrym sposobem przedstawienia wyników jest ich prezentacja w postaci histogramu, z którego można łatwo ocenić właściwości rozkładu, mogące umknąć uwadze przy analizie ograniczonej jedynie do statystyki liczbowej. ,
3.3. Jak oceniać algorytmy ewolucyjne
.113.
Kryteria oceny i sposób testowania algorytmów ewolucyjnych niewiele odbiegają od ogólnych zasad naszkicowanych w wykładzie 1. Poniżej podano kilka szczegółowych kwestii, na które warto zwrócić szczególną uwagę.
v
Wynik działania algorytmu ewolucyjnego. Sposób działania algorytmów optymalizacji często jest charakteryzowany za pomocą krzywych zbieżności, będących wykresem zmian rozwiązania roboczego w czasie. W przypadku algorytmu ewolucyjnego, w każdej generacji zmiany dotyczą całej populacji chromosomów, w związku z tym krzywe zbieżności mogą ilustrować zmiany w czasie wartości liczbowej świadczącej o przystosowaniu populacji, na przykład średniej lub maksymalnej. Krzywe zbieżności kreśli się albo dla pojedynczego uruchomienia algorytmu, albo uśrednione dla wielu niezależnych uruchomień*. Pewną szczególną krzywą zbieżności jest wykres zmian w kolejnych generacjach wartości przystosowania najlepszego osobnika znalezionego począwszy od zerowej generacji. Po zakończeniu działania algorytmu ewolucyjnego, osobnik ten jest rozwiązaniem wyznaczonym przez pojedyncze uruchomienie algorytmu ewolucyjnego.
Koszt symulacji a liczba generacji. W wielu metodach optymalizacji koszt jest utożsamiany z liczbą iteracji metody. Jest to dosyć wygodna konwencja, gdyż w pojedynczej iteracji wykonuje się nie tylko obliczenie wartości funkcji celu, lecz również wiele czynności wymagających absorbujących obliczeń, na przykład wyznaczenie nowego kierunku poszukiwań. Obliczeń podczas czynności pomocniczych algorytmu w niektórych przypadkach może być nawet więcej niż związanych z wyznaczeniem wartości funkcji celu.
W przypadku algorytmów ewolucyjnych bazowanie na liczbie iteracji (czyli liczbie wygenerowanych populacji bazowych P*) nie jest właściwym pomysłem, gdyż liczba obliczeń wartości funkcji przystosowania w pojedynczej iteracji algorytmu ewolucyjnego jest zależna od liczności populacji potomnej. Porównywanie więc dwu różnych algorytmów ewolucyjnych, lub algorytmu ewolucyjnego z inną metodą optymalizacji, może prowadzić do fałszywych wniosków, jeśli bierze się pod uwagę wyłącznie liczbę iteracji, a pomija liczność populacji bazowej i potomnej.
Zdolność opuszczania obszarów przyciągania maksimum
i , i X , -, , , T ji ,, � *Usrednione krzywe zbiez-
lokalnego. Udpornosc algorytmu, czyn zdomosc opuszczania "ości są "bardziej repre-
obszaru przyciągania maksimum lokalnego funkcji przystosowa- zentatywne", choć naieży
. , . . , , , , to , . J r, ^o Pamiętać, że uśrednianie
ma, mozna rowmez testować, tworząc populację początkową f moze iiZgubić" istotne in-
tak, aby nie zawierała żadnego chromosomu pochodzącego z ob- f��acje o zachowaniu ai-
. , , , n ,, gorytmu w pojedynczych
szaru przyciągania maksimum globalnego. Szczególnym przy- uruchomieniach.
.114.
3. Zarządzanie populacją
padkiem jest użycie populacji początkowej, której wszystkie elementy są kopiami tego samego chromosomu, odpowiadającego maksimum lokalnemu*.
3.4. Metody selekcji
3.4.1. Reprodukcja i sukcesja
Jak już wcześniej wspomniano, selekcja (wykonywana w fazach reprodukcji i sukcesji) skutkuje ukierunkowaniem algorytmu w stronę rozwiązań poprawiających dotychczasowe. Zadaniem reprodukcji jest wybranie rodziców dla operacji genetycznych, czego wynikiem jest utworzenie populacji tymczasowej T4, która jest następnie poddawana operacjom genetycznym prowadzącym do utworzenia populacji potomnej O*. Sukcesja polega na utworzeniu nowej populacji bazowej na podstawie osobników znajdujących się w populacji potomnej i starej populacji bazowej.
Znane są dwie odmiany selekcji. W pierwszej z nich zakłada się, że nowa populacja bazowa Pi+1 powstaje wyłącznie z populacji potomnej O*. Schemat taki może prowadzić do sytuacji, w której nie zawsze najlepsze rozwiązania z populacji P* znajdą się w P4+1. Właściwość tę mają natomiast metody selekcji elitarnej, w której populacja P4+1 powstaje jako wynik złączenia populacji O* oraz najlepszych osobników z P* i odrzucenia najgorszych osobników.
3.4.2. Reprodukcja proporcjonalna (ruletkowa) :
W reprodukcji proporcjonalnej definiuje się zmienną losową, określając dla każdego osobnika w populacji P4 prawdopodobieństwo jego reprodukcji według wzoru
Pr(X) =
(3.19)
Prawdopodobieństwo wylosowania osobnika jest więc wprost proporcjonalne do jego wartości funkcji przystosowania (stąd nazwa metody). Zauważmy, że stosunek oczekiwanej liczby kopii w populacji T4 dwóch osobników z P4 jest równy stosunkowi wartości ich przystosowania
*Takie postępowanie wymaga jednak dość wiedzy o zadaniu opty lizacji, co ogranicza zakres zastosowań.
tdvr E(n(X))
<&(X)
E(n(Y}) pr(Y) <&(Y)
(3.20)
r; 3.4. Metody selekcji
.115.
Zastanówmy się teraz nad konsekwencjami takiej reprodukcji. Załóżmy, że niezależnie od siebie uruchomiono dwa algorytmy ewolucyjne o identycznych parametrach i jednakowych populacjach początkowych. Jedyna różnica polega na tym, że pierwszy algorytm działa z funkcją przystosowania <&(X), drugi zaś z funkcją przystosowania $'(X), będącą wynikiem dodania do pierwszej pewnej stałej
*'(X) = 3>(X) + A A > 0
(3.21)
Załóżmy, że w obu algorytmach w pewnej chwili populacja bazowa P* zawiera osobnika X i osobnika Y
s>(X)><&(Y) ���;�
Wówczas, w pierwszym algorytmie
S(n(X))
E(n(Y)) "1
w drugim zaś
Jak łatwo zauważyć, zachodzi
(3.22)
(3.23)
(3.24)
(3.25)
Oznacza to, że mimo jednakowej różnicy wartości funkcji przystosowania osobników, proporcje liczby potomków są różne dla funkcji przystosowania różniących się o stałą. Jest to i wadą, i zaletą. Z jednej strony, istnieje możliwość korygowania nacisku selektywnego poprzez dodanie lub odjęcie stałej. Z drugiej strony, jeśli nie wiadomo nic o funkcji przystosowania, nie sposób stwierdzić czy należy dokonać takiego zabiegu korekcyjnego, a także, jakiej wartości użyć do korekcji.
Ponadto można zauważyć, że intensywność nacisku selektywnego zmniejsza się wraz z kolejnymi generacjami, gdyż coraz więcej osobników potomnych uzyskuje zbliżone wartości przystosowania, co utrudnia zbieżność takiego algorytmu. Z kolei na początku działania, przy dużym zróżnicowaniu wartości przystosowania, należy oczekiwać silnego nacisku selektywnego, mogącego powodować tendencję do przedwczesnej zbieżności.
PRZYKŁAD. Powróćmy do przykładu z problemem plecakowym (p. 2.1.3). Rozważmy trzy rodzajefunkcjiprzystosowania
*i(X) =
i=l
i=l
.116.
3. Zarządzanie populacją
19
18
17
16
s
a
>6-
15
14
13
12
21 20
19
>e<
16
15
14
200
200
400
600 t
(a)
400
600 t
(b)
*i(X) *o(X) - 13 *:,(X) - 130
800
1000
*,(X) 800
1000
1200
1200
RYSUNEK 3.5. Krzywe zbieżności: a) zmiany średniej wartości przystosowania populacji dla metody reprodukcji proporcjonalnej, b) zmiany wartości przystosowania najlepszego znalezionego osobnika
3.4. Metody selekcji
.117.
$3(X) =
Przeprowadźmy trzykrotną symulację algorytmu genetycznego dla każdej zfunkcji przystosowania. Metoda reprodukcjijest w pełni zgodna z definicją (3.19). Sukcesja przebiega wg schematu pt+l = Q*.
Dla porównania przyjmijmy, że w każdym uruchomieniu algorytmu genetycznego populacja początkowa P� będzie jednakowa*. Przeanalizujmy krzywe zbieżności dla poszczególnych uruchomień (rys. 3.5).
Łatwo zauważyć, że dodanie stałej do wartości funkcji przystosowania ma negatywny wpływ na szybkość zbieżności, gdyż prowadzi do osłabienia nacisku selektywnego. Osłabienie to jest tym większe, im większa jest wartość dodawanej stałej.
W tabeli 3.1 zamieszczono wyniki 100 niezależnych uruchomień algorytmu. Podano wartość średnią wyniku, także jego odchylenie standardowe. Dodatkowo, zamieszczono liczbę uruchomień, których wynik różnił się o 1% od wartości maksimum globalnego. O koszcie metody świadczą wartość średnia i odchylenie standardowe kosztu brutto mierzonego liczbą wywołań wartości funkcji przystosowania.
Z tabeli 3.1 wynika, że zwiększanie dodawanej stałej prowadzi do coraz gorszych wyników algorytmu zmniejsza się średnia wartość przystosowania znalezionych rozwiązań. Algorytm zatrzymuje się po coraz mniejszej liczbie kroków, co świadczy o tym, że zmniejsza się szybkość zbieżności. Nie jest to zjawisko zaskakujące dodanie wartości stałej zmniejsza nacisk selektywny, co upodabnia algorytm ewolucyjny do błądzenia przypadkowego.
TABELA 3.1. Wyniki reprodukcji proporcjonalnej dla funkcji przystosowania przesuniętych o stałą. Wartości funkcji $2 i ^?3 pomniejszono odpowiednio o 13 i 130 w celu uzyskania porównywalnych wyników
Wynik Koszt
$ średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
*1 19.65 0.20 7 637.69 177.61
$2 18.85 0.45 0 596.14 207.85
*3 16.75 0.88 0 581.30 190.91
3.4.3. Zmodyfikowana reprodukcja proporcjonalna
Jak łatwo było stwierdzić analitycznie, reprodukcja ruletkowajest
"wrażliwa" na dodanie wartości stałej do funkcji przystosowania. *Można to łatwo uzyskać,
Może się również zdarzyć, że funkcja przystosowania przyjmuje '"Jei"doiosow^h^
wartości ujemne, co przeczy założeniom, jakie poczyniliśmy, de- wartością.
gdzie
T 1 fl 3.Zarzadzaniepopulacja :
finiując ruletkową metodę reprodukcji. Powyższym niedogodnościom można zapobiec w stosunkowo prosty sposób należy podać wartość 4?o spełniającą dla każdego X � D właściwość
$o < *(X) (3.26)
Wartość tę zastosujemy do utworzenia zmodyfikowanej funkcji przystosowania zdefiniowanej następująco:
$'(X) = $(X)-$0 :",Wartości funkcji 3>'(X) są wykorzystywane podczas selekcji.
Może się jednak zdarzyć, że nie jesteśmy w stanie podać wartości $o lub też jest ona bardzo zgrubnym oszacowaniem wartości infxer> 3>(X). Dlatego dość często jest stosowany taki schemat modyfikacji funkcji przystosowania, w którym określa się ją następująco:
$t (3.28)
(3.29)
Takie "dynamiczne szacowanie" ma dodatkową zaletę pod koniec działania algorytmu, gdy przeważają osobniki niewiele różniące się wartością przystosowania, przyjęcie modyfikacji (3.27) prowadzi do osłabienia nacisku selektywnego, podczas gdy modyfikacja (3.28) utrzymuje go dopóty, dopóki istnieje choć nie-znacznezróżnicowanie. �
PRZYKŁAD. Powróćmy do przykładu z problemem plecakowym i funkcjami celu powiększonymi o stalą. Opisywana modyfikacja metody reprodukcji prowadzi do uzyskania algorytmu niewrażliwego na dodanie stałej. Co więcej algorytm ten cechuje się szybszą zbieżnością, co można łatwo stwierdzić, analizując rys. 3.6.
Zmodyfikowana reprodukcja proporcjonalna, również w ocenie statystycznej, okazuje się lepsza od wariantu definicyjnego (tab. 3.2). Wynik stu niezależnych uruchomień algorytmu świadczy o tym, że zarówno koszt uzyskania rozwiązań (szybkość zbieżności), jak i ich jakość (odporność algorytmu) są znacznie lepsze niż otrzymane metodą standardową.
TABELA 3.2. Wyniki zmodyfikowanej reprodukcji proporcjonalnej. Ta metoda reprodukcji jest niewrażliwa na przesunięcie o stałą
$ Wynik Koszt
średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
$1, $2, $3 19.96 0.038 93 385.13 87.05
3.4. Metody selekcji
.119.
(inod)
'I>l(X) (8td) 2(X) - 13 (std) -
- 130 {std) -
(a)
1200
,(X) (mod) *i(X) (stcl) *z(X) - 13 (std)
1200
(b)
RYSUNEK 3.6. Krzywe zbieżności algorytmu ewolucyjnego ze zmodyfikowaną (mod) i standardową (std) wersją reprodukcji proporcjonalnej: a) zmiany w kolejnych generacjach średniego przystosowania populacji, b) rozwiązania znalezionego przez algorytm
.120.
3. Zarządzanie populacją
3.4.4. Reprodukcja rangowa
Reprodukcja rangowa (rankingowa) pozwala na znacznie swobodniejsze kształtowanie nacisku selektywnego. W metodzie tej prawdopodobieństwo reprodukcji każdego osobnikajest podane w sposób jawny na podstawie jego rangi liczby charakteryzującej jakość tego osobnika na tle populacji bazowej. Liczbę tę można nadawać dwoma sposobami. W pierwszym populacja jest sortowana według nierosnących wartości przystosowania osobników; ranga jest tożsama z numerem osobnika w tym uszeregowaniu. Takie postępowanie prowadzi do sytuacji, w której dwa osobniki o jednakowej wartości przystosowania otrzymają inne wartości rangi. Drugi sposób gwarantuje, że taka sytuacja nie będzie miała miejsca; osobniki o jednakowym przystosowaniu otrzymają jednakowe wartości rangi; wartości te są kolejnymi liczbami całkowitymi począwszy od zera.
Po określeniu rang, definiuje się zmienną losową, przypisując każdemu osobnikowi prawdopodobieństwo reprodukcji na podstawie jego rangi. Wybór funkcji określającej prawdopodobieństwo reprodukcji jest dokonywany arbitralnie przez projektanta algorytmu. Należy jednak zadbać o to, aby funkcja ta była nierosnąca wraz z numerem rangi. W literaturze fachowej najczęściej spotyka się rozwiązanie z liniową funkcją, daną wzorem
gdzie*
ax = max r(X)
(3.30)
(3.31)
a i k zaś są parametrami dobieranymi w taki sposób, aby spełnione były warunki**
t=l
0 < pr(X) < l
oraz dodatkowo
jeśli r(X) > r(Y) to pr(X)(3.32) (3.33)
(3.34)
Reprodukcja rangowa z liniową funkcją prawdopodobieństwa �Zauważmy, że w pierw- reprodukcji jest często określana jako metoda mało efektywna.
szym sposobie nadawania _ . . . . ., . .. ,", . ,, . .
rangmamyzawszermnx = opotyka się takze inne postaci iunkcji pr(X); dosc popularna jest = i* ~ L funkcja potęgowa
**Z tego wynika, że wy-
bórwartościajednoznacz- /,,-, , , /~v\\b /o oc\
nie określa wartość fe. Pr(-^-) = a + ^ (rmax ~~ r(*-)) (Ó.Ó5)
3.4. Metody selekcji
.121.
V
gdzie a, b, k są parametrami, których wartości dobiera się w podobny sposób, jak w przypadku funkcji liniowej pr(X).
Prawdopodobieństwo reprodukcji "przynależne" poszczególnym rangom jest z góry ustalone przez projektanta algorytmu i może być stałe lub zmieniać się wraz z numerem generacji. Zwróćmy także uwagę, że liczba różnych wartości rang w populacji P* może ulegać zmianom w czasie działania algorytmu ewolucyjnego w przypadku ekstremalnym liczba osobników o różnych wartościach rang może być równa yU, lecz również może się zdarzyć, że wszystkie osobniki będą miały tę samą wartość rangi*.
Ze schematu metody wynika, że jest ona niewrażliwa na zwiększenie wartości funkcji przystosowania o stałą. Kluczowe znaczenie ma właściwy dobór sposobu wyznaczania liczby kopii na podstawie rang, co stanowi podstawową trudność w wykorzystaniu tej metody reprodukcji.
PRZYKŁAD. Powróćmy do problemu plecakowego i przebadajmy kilka różnych wariantów metody reprodukcji rangowej.
Załóżmy, że prawdopodobieństwo reprodukcji będzie określone wzorem (3.35). Będziemymanipulowaćwartościamia ib, dobierając k w taki sposób, aby wartościpr spełniały właściwości (3.32)--(3.3A)- Zwiększanie wartości a powoduje globalne osłabienie nacisku selektywnego. Wraz ze wzrostem b, zwiększa się różnicowanie prawdopodobieństw reprodukcji lepszych i gorszych osobników.
Będziemy badać funkcje określone wzorem dla wartości a 6 6 {0,0.05,0.1,0.25,0.5} i6e {0.25,0.5,l,2,4}. Wtabeli 3.3po-dano wyniki statystyczne ze stu niezależnych uruchomień algorytmu ewolucyjnego z reprodukcją rangową dla różnych wartości parametrów a, b.
Jak można się przekonać, w przypadku rozważanego problemu plecakowego lepsze wyniki daje reprodukcja rangowa z nieco osłabionym naciskiem selektywnym (a > 0.l). Daje się również zauważyć, że wartość b w badanym zakresie ma niewielki wplyw na właściwości algorytmu ewolucyjnego. Warto odnotować znaczną wariancję uzyskiwanych wyników i kosztów symulacji, co przy dość dużym odsetku rozwiązań z marginesem 1% i przy niewielkiej wartości średniej wyników świadczy o tym, że algorytm kończył działanie albo z dość dobrym rozwiązaniem, albo też ze zdecydowanie niezadowalającym. Na rysunku 3.7 przedstawiono histogramy kosztu i uzyskiwanych rozwiązań dla reprodukcji rangowej przy ustawieniach parametrów a = 0.05, b = 2.
*Uwaga ta dotyczy oczywiście drugiego sposobu nadawania rang.
.122.
3. Zarządzanie populacją
1 5 � ------------------------------- 1 --------------------------- n -
4 - ' '.
-o
f 3 ' n n rn n
O
2 - fH flfl (T n n n n n m
1 -Q r lill.llM
17 17.5 18 18.5 19 19.5 a
Wynik
20 rr 15 � (a) ''''"'.'..',=
' '.',
>o '8 '
& 10 N O ' ,, '. -i
5 1 t
20( i J ....... n fruń * \ \ * . ' .n n n .L H n m n, n n
liiiiin ,n
) 250 300 350 400 450 500 550 60
Koszt
(b)
RYSUNEK 3.7. Histogram rozwiązań (a) i kosztu symulacji (b) dla reprodukcji rangowej, (wzór (3.35)), a = 0.05, b ~ 2
3.4. Metody selekcji
.123.
TABELA 3.3. Wyniki reprodukcji rangowej (wzór (3.35)) dla różnych wartości parametrów a, b
Wynik Koszt
a b średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
0 1/4 18.81 0.76 10 272.22 91.90
0 1/2 19.01 0.83 17 274.55 96.5
0 1 19.04 0.77 14 278.23 101.81
0 2 18.87 0.83 8 250.38 69.72
0 4 19.13 0.95 19 275.29 93.03
0.05 1/4 19.14 0.83 31 256.41 68.84
0.05 1/2 18.94 0.83 26 271.96 107.86
0.05 1 18.81 0.91 27 258.04 84.84
0.05 2 18.92 0.87 40 261.07 72.94
0.05 4 18.95 0.87 26 259.54 94.66
0.1 1/4 19.02 0.82 35 275.56 95.33
0.1 1/2 18.90 0.86 29 274.15 124.54
0.1 1 19.02 0.83 26 26&.58 97.03
0.1 2 18.83 0.81 28 248.66 82.70
0.1 4 18.91 0.78 29 254.12 75.12
0.25 1/4 18.84 0.98 36 268.87 95.07
0.25 1/2 18.98 0.86 27 271.99 104.59
0.25 1 19.09 0.74 29 276.91 97.24
0.25 2 19.06 0.76 21 277.23 91.91
0.25 4 19.06 0.76 27 277.64 110.29
0.5 1/4 18.88 0.77 27 275.85 96.53
0.5 1/2 19.06 0.81 34 267.32 95.62
0.5 1 18.85 0.83 35 267.16 86.66
0.5 2 18.93 0.81 37 272.82 95.94
0.5 4 19.07 0.79 33 283.67 97.89
3.4.5. Reprodukcja turniejowa
W reprodukcji turniejowej stosuje się dwustopniową selekcję , dydatów do skopiowania". W każdym kroku reprodukcji dokonuje się najpierw wyboru populacji Q C P*, zawierającej q osobników z populacji P*. Wszystkie g-elementowe kombinacje z P* są jednakowo prawdopodobne. Następnie przeprowadza się turniej między osobnikami z Q. Zwycięzcą turnieju zostaje osobnik X^ o największej wartości funkcji przystosowania, czyli
$(XQ) > $(Y) dla każdego Y � Q (3.36)
Osobnik ten jest kopiowany do populacji potomnej. Proces wyboru turnieju i wyłaniania zwycięzcy odbywa się wielokrotnie aż do wypełnienia populacji tymczasowej T**. *Pewien ktopot powstaje
Proces wyboru osobników do populacji Q może być realizo- wów�as.�dy ist"ie^ wi?-
J r r J ^ J cej niz jeden osobnik speł-
wany dwoma sposobami: poprzez losowanie ze zwracaniem i bez niający warunek zwycięzcy zwracania. Pierwszy wariant jest bardziej rozpowszechniony i tro- (3-36);wowczaswybierasię
J J J ^ J go losowo sposrod spełma-
chę łatwiejszy w implementacji komputerowej. jacych ten warunek.
.124.
3. Zarządzanie populacją
W zależności od przyjętego wariantu wyboru osobników do turnieju, wzór na stosunek wartości oczekiwanych liczby kopii osobników ma nieco odmienną postać. W obu przypadkach reprodukcja turniejowa da się sprowadzić do reprodukcji rangowej. Jeśli założymy, że dla każdego osobnika została wyznaczona jego ranga*, zwycięstwo zaś w turnieju odnosi osobnik o najmniejszej wartości rangi, to prawdopodobieństwa reprodukcji są następujące:
w taki
osobnik
rangę
sposób,
powinien
że każdy
mieć inna
w losowaniu bez zwracania

fc=l
- r(X) - k u k
w losowaniu ze zwracaniem
M
//
M ~
(3.37)
(3.38)
Parametrem sterującym intensywnością nacisku selektywnego jest liczność turnieju q. Dla q = 2, reprodukcja turniejowa jest szczególnym przypadkiem liniowej reprodukcji rangowej.
Warianty bez zwracania i ze zwracaniem dają różny nacisk selektywny. Drugi z nich jest mniej restrykcyjny, gdyż pozwala na reprodukcję dowolnego osobnika z niezerowym prawdopodobieństwem; z kolei w pierwszym, q 1 najgorszych osobników nie będzie w ogóle reprodukować.
PRZYKŁAD. Powróćmy do problemu plecakowego, znanego z poprzednich przykładów, i przeanalizujmy wphjw liczności turnieju na wyniki uzyskiwane przez algorytm oraz na nakład obliczeń. W tabeli 3.Ą zamieszczono wyniki dzialania algorytmu ewolucyjnego.
Wyniki symulacji ilustrują fakt, że manipulując wartością q, modyfikuje się intensywność nacisku selektywnego. Małe wartości q (2, 3, 5) prowadzą do najodporniejszego algorytmu. Uzyskiwane rozwiązania są niewiele oddalone od maksimum globalnego. Dalsze zwiększanie liczności turnieju sprawia, że algorytm nieznacznie traci odporność (świadczy o tym przede wszystkim zmniejszenie liczby wyników różnych o 1% od globalnie optymalnego), przy czym wzrasta odchylenie standardowe wyników.
Na rysunkach 3.8 i 3.9 zamieszczono histogramy rozwiązań i kosztów symulacji dla różnych wielkości turnieju: q = 2 duża odporność, na histogramie widoczna znaczna liczba uruchomień kończących się znalezieniem rozwiązania bardzo bliskiego global-nie optymalnemu, i q = 50 niewielka odporność, histogram
^ � ?
wyraźnie sptaszczony.
3.4. Metody selekcji
.125.
30
25
20
O
15
10
19
19.2
19.4 19.6
Wynik (a)
19.8
20
20
15
10
O
200 300
400
500
Koszt
600
(b)
700 800
RYSUNEK 3.8. Histogram rozwiązań (a) i kosztów symulacji (b) dla metody turniejowej,
.126.
3. Zarządzanie populacją
30
25
20
'8
15
10
19
20
15
N O
10
200
, n
mnrrrrnmn
mml
19.2
19.4
19.6
19.8
20
Wynik
(a)
300
400
500
Koszt
600
700
800
(b)
RYSUNEK 3.9. Histogram rozwiązań (a) i kosztów symulacji (b) dla metody turniejowej, q = 50
> 3.4. Metody selekcji
.127.
TABELA 3.4. Wyniki reprodukcji turniejowej dla różnych wartości q
q Wynik Koszt
średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
2 19.88 0.096 52 298.17 69.36
3 19.83 0.13 30 294.57 87.07
4 19.82 0.14 41 296.36 94.15
5 19.82 0.12 29 292.92 89.44
6 19.83 0.13 33 290.67 78.54
7 19.82 0.11 31 282.41 77.67
8 19.81 0.14 33 297.40 74.75
9 19.82 0.13 28 277.02 71.57
10 19.76 0.17 25 273.10 69.10
20 19.77 0.17 21 297.39 91.80
30 19.76 0.18 26 293.57 95.34
40 19.78 0.17 28 289.48 94.65
50 19.73 0.19 23 297.80 111.18
60 19.74 0.19 21 306.43 103.21
70 19.74 0.19 19 309.18 95.33
80 19.78 0.17 30 284.99 83.53
90 19.73 0.21 20 297.11 101.56
100 19.73 0.20 17 310.98 97.33
3.4.6. Reprodukcja progowa
Reprodukcja progowa jest szczególnym przypadkiem reprodukcji rangowej. Funkcja pr(X) ma postać progu prawdopodobieństwo reprodukcji jest określone wzorem
(3.39)
0 w przeciwnym przypadku
Wartość p jest wskaźnikiem nacisku selektywnego im jest ona mniejsza, tym mniej osobników będzie reprodukować, a zatem tym większa będzie liczność potomstwa jednego osobnika. Zmniejszanie p prowadzi więc do wzrostu nacisku selektywnego. W skrajnym przypadku, gdy p = \|^ (do reprodukcji wybierany jest dokładnie jeden osobnik), selekcja taka sprowadza się do algorytmu wzrostu.
PRZYKŁAD. Prześledźmy sposób dzialania metod reprodukcji progowej na przykładzie znanego już problemu plecakowego. W tabeli 3.5 przedstawiono wyniki i koszt ich uzyskania dla różnych wartości parametru p.
Jak nietrudno się przekonać, im większa jest wartość p, tym słabszy nacisk selektywny. Zbyt mała wartość p (0.05+0.1) powoduje przedwczesną zbieżność. Objawia się to niewielką liczbą rozwiązań mieszczących się w 1 % progu jakości przybliżenia mak-
m
.128.
3. Zarządzanie populacją
70
60
, 50
| 40
N
0 30 20
| 10
; 0
19.3 19.4
19.5
19.6 19.7
Wynik .....(a)
19.8 19.9
20
10
200
400
600
800
1000
1200
Koszt
(b)
RvsuNEK 3.10. Histogram rozwiązań (a) i kosztów symulacji (b) dla metody progowej, p = 0.15
3.4. Metody selekcji
.129.
TABELA 3.5. Wyniki reprodukcji progowej dla różnych wartości p
Wynik Koszt
P średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
0.05 19.88 0.085 62 367.75 110.27
0.10 19.94 0.053 85 414.06 131.15
0.15 19.95 0.047 89 432.05 137.02
0.20 19.95 0.050 87 431.41 115.22
0.50 19.96 0.032 95 484.00 121.30
0.75 19.90 0.10 70 542.42 143.49
simum globalnego. Zwiększanie wartości p (0.15+0.5) poprawia odporność i nieznacznie zwiększa nakład obliczeń, natomiast zbyt duża wartość (0.75) powoduje ponownie obniżenie odporności. Na rysunku 3.10 znajdują się histogramy rozwiązań i kosztów symulacji dla wartości p = 0.15.
Odpowiedniość reprodukcji progowej i selekcji w strategii
(H, A). W tym miejscu należy się kilka słów komentarza o odpo-wiedniości selekcji wykorzystywanej w strategii (^t, A) i metody reprodukcji progowej. W "tradycyjnym" ujęciu strategie reprodukcji ewolucyjne są przedstawiane w następujący sposób: populacja bazowa P* liczy n osobników, z których każdy reprodukuje z jednakowym prawdopodobieństwem. W wyniku reprodukcji i operacji genetycznych tworzonych jest A osobników potomnych, z których wybiera się ^ najlepszych do nowej populacji.
Ustawmy teraz etap wyboru p, najlepszych osobników nie na końcu pętli ewolucyjnej, lecz na jej początku, w jej miejsce stosując proste kopiowanie bez redukcji liczby osobników. W ten sposób populacja bazowa algorytmu z reprodukcją progową jest równoważna populacji potomnej strategii ewolucyjnej, a populacja bazowa strategii ewolucyjnej odpowiada osobnikom o rangach 1,..., pn w reprodukcji progowej*.
3.4.7. Sukcesja z całkowitym zastępowaniem
Sukcesja z całkowitym zastępowaniem (trywialna) jest podstawowym i najczęściej wykorzystywanym schematem. Polega na tym, że nową populacją bazową staje się populacja potomna, czyli Pi+1 ;= := O*. Sukcesja trywialna nie wprowadza nacisku selektywnego.
3.4.8. Sukcesja z częściowym zastępowaniem
*Kolejnym ważnym spostrzeżeniem, które możemy poczynić, obserwując tę od-powiedniość, jest fakt, że strategia ewolucyjna (//, A)
Nieco bardziej wyrafinowanym algorytmem sukcesji jest metoda z częściowym zastępowaniem (overlapping populations). Polega na tym, że nowa populacja bazowa może zawierać osobniki zarówno szego osobnika.
.130.
3. Zarządzanie populacją
z populacji potomnej, jak i ze starej populacji bazowej. W najprostszym wariancie zakłada się, że nowa populacja bazowa będzie się składać z r\^, osobników znajdujących się w populacji potomnej, gdzie j] jest współczynnikiem wymiany i przyjmuje wartości 0 < 77 < 1*. Część osobników starej populacji bazowej należy więc usunąć, aby zrobić miejsce dla potomstwa. Mechanizm usuwania może mieć wiele wariantów, na przykład:
� usuwanie najgorzej przystosowanych osobników (pomysł rozwinięty w sukcesji elitarnej, patrz p. 3.4.9),
� usuwanie osobników najbardziej "podobnych" do potomnych metoda ze ściskiem (miarą podobieństwa może być np. odległość chromosomów patrz wykład 5),
� usuwanielosowowybranychosobników. > VT
Sukcesja z częściowym zastępowaniem prowadzi do stabilniejszej pracy algorytmu ewolucyjnego, jednakże może nieco zwiększyć tendencję do osiadania w maksimach lokalnych funkcji przystosowania. Najczęściej stosowanym przypadkiem szczególnym jest sukcesja elitarna, nieco mniej popularna jest metoda ze ściskiem. Usuwanie losowo wybranych osobników jest bardzo rzadko stosowane.
*Wartość rj �� sukcesję z ca stepowaniem.
0 oznacza tkowitym za-
3.4.9. Sukcesja elitarna
Sukcesja elitarna polega na tym, że część osobników ze starej populacji bazowej przechodzi do nowej populacji w taki sposób, aby zagwarantować przeżycie co najmniej najlepszego osobnika.
Sukcesja elitarna składa się z następujących kroków. Najpierw sortuje się populację P* i wybiera rj najlepszych osobników; oznaczmy ich populację przez P*. W drugim kroku tworzy się populację P*+1, wybierając fj, najlepszych osobników z P^ U O*.
Elitarny schemat sukcesji jest szczególnie pomocny przy dowodzeniu zbieżności algorytmu ewolucyjnego. Majednak poważną wadę sprawia, że algorytm ma tendencję do "osiadania" w obszarach przyciągania maksimów lokalnych (wpadania w pułapki ewolucyjne). Przy elitarnym schemacie sukcesji podstawowym mechanizmem pozwalającym na wydobycie się z pułapki ewolucyjnej jest makromutacja, czyli mutacja o bardzo dużym zasięgu, co pociąga za sobą konieczność zwiększenia eksploracyjności operatorów genetycznych (zwłaszcza mutacji).
Wielkość elity 77 jest parametrem wpływającym na to, jak bardzo stabilnie algorytm będzie "osiadać" w maksimach lokalnych funkcji przystosowania zwiększanie rj powoduje wzmaganie tej tendencji. Innym skrajnym przypadkiem sukcesji elitarnej jest metoda trywialna, gdy r\ = 0 najbardziej odporna na "osia-
3.4. Metody selekcji
.131.
danie" w maksimach lokalnych, lecz jednocześnie prowadząca do algorytmu najwolniej zbliżającego się do maksimów (lokalnych i globalnych).
PRZYKŁAD. Prześledźmy na przykładzie problemu plecakowego wpływ wielkości elity na zbieżność algorytmu. Jako metodę reprodukcji zastosujemy schemat proporcjonalny i będziemy badać wpływ wielkości elity na zachowanie się algorytmu (histogramy uzyskiwanych rozwiązań oraz nakładów obliczeń). Zbadane zostaną przypadki dla r\ = 0 (sukcesja trywialna) oraz r/ e {l,2,5,10, 20,50,100}. Wyniki eksperymentów zamieszczono w tab. 3.6.
Można zauważyć znaczną różnicę między nieelitarnym a elitarnym sposobem sukcesji w pierwszym przypadku, jakość przybliżenia maksimum globalnego jest znacznie gorsza niż przy zastosowaniu jakiejkolwiek wielkości elity. Również koszt uzyskania rozwiązania jest wyższy w przypadku schematu nieelitarnego. Zestawiając te dwa fakty, można stwierdzić, że schematy elitarne mają znacznie większą szybkość zbieżności.
Wśród elitarnych metod sukcesji, szczególnie godny polecenia wydaje się schemat z nieliczną elitą, ograniczającą się do jednego lub co najwyżej kilku osobników. Dalsze powiększanie elity jest niewskazane prowadzi do wyraźnej przedwczesnej zbieżności. Zauważmy też, że wyniki otrzymane za pomocą schematu elitarnego i reprodukcji proporcjonalnej standardowej są porównywalne z wynikami uzyskiwanymi w reprodukcji proporcjonalnej zmodyfikowanej lub progowej z nieelitarną sukcesją. Można z tego wyciągnąć wniosek, że zastosowanie sukcesji elitarnejjestjedną z metod zwiększenia nacisku selektywnego.
Na rysunkach 3.11, 3.12, 3.13przedstawiono histogramy rozwiązań i kosztów symulacji dla wybranych przypadków sukcesji brak elity, niewielka elita poprawiająca działanie selekcji, a także zbyt liczna elita, powodująca przedwczesną zbieżność.
TABELA 3.6. Wyniki sukcesji elitarnej dla różnej wielkości elity 77 prz zastosowaniu metody reprodukcji proporcjonalnej
ł? Wynik Koszt
średni odchylenie standardowe 1% dokładność średni odchylenie standardowe
0 19.59 0.30 11 606.07 183.87
1 19.98 0.020 98 418.02 68.58
2 19.98 0.017 98 371.88 58.11
5 19.97 0.030 95 348.91 56.54
10 19.94 0.060 83 323.22 68.84
20 19.87 0.10 46 293.22 54.86
50 19.85 0.10 42 300.12 65.65
100 19.86 0.10 41 302.86 74.14
.132.
3. Zarządzanie populacją
10
O
17.5
18
18.5 19
\Vynik (a) '
19.5
20
10
>O K 'C0 �
O
O
200
400
600
800
Koszt
1000 1200
1400
(b)
RYSUNEK 3.11. Histogram rozwiązań (a) i kosztów symulacji (b) dla sukcesji trywialnej (wielkość elity r] = 0) przy zastosowaniu metody reprodukcji proporcjonalnej
3.4. Metody selekcji
.133.
100
80
O
40
20
19 19.2 19.4 19.6 19.8
Wynik , , (a)
20
10
6
200 250 300 350 400 450 500 550 600 650 700
Koszt (b)
RYSUNEK 3.12. Histogram rozwiązań (a) i kosztów symulacji (b) dla sukcesji elitarnej (wielkość elity J] = 1) przy zastosowaniu metody reprodukcji proporcjonalnej
.134.
3. Zarządzanie populacją
100
80
O
40
20
19
19.2
n, nn~ riWlnll nJh
19.4
19.6
19.8
20
Wynik
(a)
10
ę &
S)
o
200 250 300 350 400 450 500 550 600 650 700
Koszt (b)
RvsuNEK 3.13. Histogram rozwiązań (a) i kosztów symulacji (b) dla sukcesji elitarnej (wielkość elity 77 = 50) przy zastosowaniu metody reprodukcji proporcjonalnej ;,.
3.5. Kryteria zatrzymania algorytmu
.135.
Selekcja w strategii (n + A). Polega ona na uzupełnieniu selekcji (p,, A) o szczególny przypadek elitarności. Elitę stanowią wszystkie reprodukujące osobniki. Możemy ją traktować jako odmianę selekcji z reprodukcją progową z progiem p i sukcesją elitarną, w której elita ma liczność pfj,.
3.5. Kryteria zatrzymania algorytmu
Sformułowanie odpowiedniego kryterium zatrzymania jest zadaniem bardzo trudnym, wręcz niewykonalnym, gdyż zbieżność algorytmów ewolucyjnych rna charakter asymptotyczny (gdy liczba generacji dąży do nieskończoności, prawdopodobieństwo osiągnięcia maksimum globalnego wzrasta). Znane są wprawdzie wyniki analityczne dla pewnych szczególnych przypadków funkcji przystosowania (takich jak funkcja kwadratowa), lecz przyjęte założenia sprawiają, że są one mało praktyczne*. Szczególnie trudno analizuje się zdolność eksploracyjną algorytmu, polegającą na możliwości opuszczania pułapek ewolucyjnych obszarów przyciągania maksimów lokalnych. Z tych powodów, rozpowszechnione obecnie kryteria zatrzymania można podzielić na dwie grupy.
Do pierwszej z nich zaliczyć można takie kryteria zatrzymania, które polegają na monitorowaniu wartości funkcji przystosowania osobników generowanych przez algorytm. Wynikają one z obserwowanego w eksperymentach zjawiska, polegającego na tym, że wskutek działania algorytmu ewolucyjnego początkowo często, a później coraz rzadziej powstają osobniki, których przystosowanie jest większe niż dotychczas najlepsze. Tak więc generowanie nowych osobników, co wiąże się z coraz większym nakładem obliczeniowym, prowadzi do coraz rzadszych i mniejszych zysków. Kryteria maksymalnego kosztu, zadowalającego poziomu funkcji przystosowania i minimalnej szybkości poprawy, które są najpowszechniej stosowane ze względu na swą prostotę, sprowadzają się do obserwowania wartości funkcji przystosowania najlepszego wygenerowanego dotychczas osobnika. Niedawno opublikowano także bayesowskie podejście do kryterium zatrzymania, które polega na modelowaniu zmian rozkładu wartości funkcji przystosowania w populacji bazowej i próbie przewidywania wartości oczekiwanych zarówno stopnia poprawy najlepszego rozwiązania, jak i szybkości uzyskania tej poprawy.
Drugą grupę kryteriów zatrzymania stanowią takie, które monitorują zdolność algorytmu do eksploracji przestrzeni genotypów, co jest czynnikiem warunkującym odporność algorytmu na maksima lokalne. Zdolność taka wynika z dwóch czynników: różnorodności populacji bazowej (szczególnie istotnej dla eksplo-
*Optymalne kryterium zatrzymania umożliwiałoby stwierdzenie, że chromosom wygenerowany przez algorytm ewolucyjny jest dostatecznie dobrym przybliżeniem maksimum globalnego funkcji celu. To z kolei implikuje znajomość tego maksimum jeszcze przed rozpoczęciem optymalizacji, co oczywiściejest postulatem niespełnialnym.
.136.
3. Zarządzanie populacją
racji za pomocą operatora krzyżowania), jak również z zasięgu operatora mutacji (jeśli podlega on samoczynnej adaptacji).
Poniżej omówiono podstawowe kryteria zatrzymania algorytmu. �*..�;
3.5.1. Monitorowanie rozwiązań generowanych przez algorytm
\ f �;' ''i 'v
PRZYKŁAD. Jako ilustrację sposobu zmian rozwiązań generowanych przez algorytm rozważmy poniższy przykład. Prześledźmy zmiany wartości funkcji przystosowania najlepszego osobnika w populacji bazowej. Jako funkcję testową przyjmijmy 30-wymia-rową funkcję kwadratową, w której każda zmienna niezależna przyjmuje wartości z przedziału [-32,...,32]. Na rysunku 3.1Ą przedstawiono krzywą zbieżności najlepszego osobnika, którą typowo uzyskuje się dla algorytmów ewolucyjnych.
Daje się zauważyć, że zmiany nie mają jednostajnego charakteru zdarzają się okresy stagnacji algorytmu poprzedzające kilka generacji gwałtownych zmian. Można by (nieco paradoksalnie) stwierdzić, że algorytm ewolucyjny w swej istocie objawia się zewnętrznemu obserwatorowi jako "rewolucyjny" okresy istotnych zmian są nagłe i krótkotrwałe. Zauważmy też, że w kolejnych generacjach szybkość zmian najlepszej wartości funkcji przystosowania ma generalnie tendencję malejącą. Powyżej pewnego numeru generacji zmiany są już nieznaczne i świadczą o zbieżności (niekoniecznie jednak do maksimum globalnego) algorytm traci zdolność eksploracji.
Kryterium maksymalnego kosztu. Kryterium to jest chyba najprostsze w implementacji. Przyjmuje się, że jeśli koszt algorytmu przekroczy założoną wartość maksymalną Kmax, to algorytm kończy działanie. Wartość Kmax wynika najczęściej ze specyfiki zastosowania algorytmu, na przykład w sterowaniu optymalizującym, gdzie wszystkie sterowania muszą być wyznaczone w nieprzekraczalnym terminie określonym przez moment rozpoczęcia kolejnego cyklu sterowania.
Często stosowaną odmianą tego kryterium jest taka, w której przyjmuje się pewną maksymalną dopuszczalną liczbę generacji algorytmu. Należy mieć na uwadze, że tak sformułowane kryterium zależy w niejawny sposób od liczby nowych osobników generowanych w każdej generacji algorytmu. Zwiększając na przykład liczność populacji potomnej w strategii (p, + A), zwiększamy liczbę obliczeń wartości funkcji przystosowania (oraz czas obliczeń) potrzebnych do spełnienia kryterium zatrzymania związanego z liczbą generacji. Podsumowując korzystając z tego kryterium, należy zdawać sobie sprawę z niewygody związanej z uzależnieniem od innych parametrów algorytmu.
3.5. Kryteria zatrzymania algorytmu
.137.
o -
200 400 600 800 1000
t
100 200 300 400 500 600 700 800 900 1000
(b)
RYSUNEK 3.14. Krzywa zbieżności algorytmu ewolucyjnego w skali liniowej (a) i liniowo--logarytmicznej (b). Łatwo zauważyć, że wraz z kolejnymi generacjami zmniejsza się zarówno częstość znajdowania lepszego rozwiązania, jak i stopień uzyskiwanej poprawy
.138.
3. Zarządzanie populacją
Kryterium zadowalającego poziomu funkcji przystosowania. Kryterium to jest spełnione, jeśli algorytrn znajdzie rozwiązanie o wartości funkcji przystosowania określonej przez użytkow-nikajako zadowalająca, czyli gdy zachodzi
*{X(t)) >
(3.40)
gdzie 3>s jest zadowalającym poziomem wartości funkcji przystosowania, X(i) najlepszym dotychczas znalezionym osobnikiem
X(t) = arg max maxr=0,...,t xepr
(3.41)
*(X(t))
*min
*(X(t))
I?nax
(a)
Minimalna
szybkość
poprawy
(b)
RYSUNEK 3.15. Ilustracja kryteriów zatrzymania algorytmu ewolucyjnego na tle jego przebiegu: a) kryterium zadowalającego poziomu funkcji przystosowania i maksymalnego kosztu, b) kryterium minimalnej szybkości poprawy
3.5. Kryteria zatrzymania algorytmu
.139.
! Korzystanie z tego kryterium jest utrudnione z dwóch powodów. Po pierwsze, często nie jest łatwo (bez dostatecznie dobrej znajomości funkcji przystosowania) określić wartość Kryterium minimalnej szybkości poprawy. Kryterium to bazuje na obserwacji szybkości zmian wyniku osiągniętego przez algorytm; jego parametrami są wartości r, e. Algorytm jest zatrzymywany, jeśli w kolejnych r generacjach nie uda się poprawić wyniku algorytmu o więcej niż e, czyli jeśli jest spełniony warunek
Często przyjmowane jest e = 0 wówczas algorytm jest zatrzymywany, jeśli nie uda mu się uzyskać lepszego rozwiązania w kolejnych r generacjach.
Na rysunku 3.15 przedstawiono interpretację graficzną omawianych kryteriów zatrzymania algorytmu ewolucyjnego.
3.5.2. Monitorowanie zdolności eksploracyjnych
Kryterium zaniku różnorodności populacji. Różnorodność populacji bazowej ma wpływ na odporność algorytmu ewolucyjnego na maksima lokalne. Dodatkowo, jeśli ewolucja wykorzystuje operator krzyżowania, to różnorodność populacji bazowej sprawia, że krzyżowanie ma duży zasięg. W rezultacie, dopóki utrzymana jest duża różnorodność, dopóty algorytm dość szybko generuje nowe rozwiązania. Zanik różnorodności powoduje, że przeszukiwania są ograniczone do niewielkiego obszaru, co jest najczęściej równoważne z eksploatacją obszaru przyciągania jednego ekstre-mum (niekoniecznie globalnego).
PRZYKŁAD. Prześledźmy teraz, w jaki sposób zmienia się różnorodność populacji w algorytmie ewolucyjnym. Wykonajmy eksperyment polegający na uruchomieniu algorytmu ewolucyjnego z reprodukcją progową (p = 0.15j z losową populacją początkową zawierającą f-i = 100 osobników. Ewolucja trwa 1000 pokoleń. Funkcją przystosowania jest funkcja Ackleya. Prześledźmy zmiany wartości przystosowania najlepszego osobnika, jak również norm wektora średnich wartości genotypów X(i), którego elementami są
= \|p
(3.43)
XeP'
.140.
3. Zarządzanie populacją
oraz wektora standardowych odchyleń wartości genotypów o^(t), zawierającego elementy
(3.44)
Standardowe odchylenie genotypów jest łatwą do obliczenia miarą różnorodności, lecz uproszczoną. Dlatego zamieszczone wyniki mają charakter raczej informacyjny i do posłużenia się taką miarą różnorodności jako kryterium zatrzymania zalecałbym pewną ostrożność. Na rysunku 3.16przedstawiono zmiany wymienionych wyżej wielkości w kolejnych generacjach algorytmu ewolucyjnego. Początkowo, przy dużej różnorodności populacji bazowej, generowane są często osobniki znacznie lepsze niż dotychczas znalezione; w konsekwencji, szybkość poprawy najlepszego rozwiązania jest dość duża. W miarę upływu czasu, różnorodność populacji zmniejsza się do pewnego niewielkiego poziomu. Towarzyszy temu znaczne zmniejszenie szybkości generowania nowych rozwiązań.
Stosując kryterium zatrzymania bazujące na różnorodności populacji, w którym wykorzystuje się powyższe obserwacje, można stwierdzić, że obniżenie różnorodności poniżej pewnego poziomu świadczy o przejściu do etapu eksploatacji obszaru przyciągania ekstremum. Algorytm należy wówczas zatrzymać i wykorzystać pewną metodę optymalizacji lokalnej do dokładnego wyznaczenia tego ekstremum. Do określenia różnorodności populacji można na przykład zastosować wartość dyskrepancji zbioru chromosomów lub rozkład macierzy kowariancji na wartości i wektory własne*.
Zanik samoczynnie adaptowanego zasięgu operatora mutacji. Omawiane kryterium opiera się na eksperymentalnie potwierdzonej hipotezie, że jeśli w algorytmie ewolucyjnym stosuje się adaptację zasięgu mutacji (np. odchyleń standardowych rozkładu normalnego lub prawdopodobieństw zamiany bitu), to od pewnego momentu zasięg ten ma trwałą tendencję do zmniejszania się (patrz rys. 2.15). Wiąże się to z faktem, że algorytm zaczyna eksploatację znalezionego obszaru przyciągania ekstremum. Szanse na to, że zasięg zwiększy się ponownie w takim stopniu, aby przywrócić eksplorację, są niewielkie musiałoby dojść do kończącej się sukcesem makromutacji.
Kryterium zatrzymania bazujące na zasięgu mutacji jest szczególne dla algorytmów ewolucyjnych z samoczynną adaptacją zasięgu mutacji, co więcej, mutacja powinna być operatorem pierwszoplanowym (jak np. w przypadku strategii ewolucyjnych), *o dyskrepancji zbioru Wówczaszasięgoperatoramutacjijest,obokmetodselekcji,głów-punktów i analizie koreia- nym źródłem równoważenia eksploracji i eksploatacji. Jego zanik
cji można przeczytać w do- , . , , , n , . , . * . , ,
datku Di. prowadzi do lokalnych jedynie przeszukiwań, co ma negatywny
3.5. Kryteria zatrzymania algorytmu
.141.
100 |
0.01
0.001
0.0001
0.00001
200
400 600
t
(a)
800
1000
O
I
100 10
1
b ~7 0.01
0.001
0.0001
0.00001
0.000001
10
-I>(X(t))-
20
30
40
50 t
60
70
80
90 100
(b)
RYSUNEK 3.16. Zmiany w czasie ewolucji: a) wartości przystosowania najlepszego osobnika, b) wartości średniej genotypów, ich zróżnicowania oraz wartości funkcji przystosowania najlepszego osobnika (w okresie ich największej dynamiki)
.142.
3. Zarządzanie populacją >
wpływ na odporność, ale przyspiesza zbieżność do maksimów lokalnych.
W tym kryterium oblicza się dla populacji bazowej średnią wartość odchyleń standardowych pamiętanych w genotypach osobników, które to odchylenia są wykorzystywane podczas mutacji. Zmniejszenie tej wartości średniej poniżej pewnego progu &min przyjmuje się jako moment zakończenia przeszukiwań ewolucyjnych.
3.6. Uwagi bibliograficzne
Eksploracja i eksploatacja są pojęciami intuicyjnymi. Próba określenia ich w kontekście obszarów przyciągania maksimów lokalnych jest wzorowana na książce [103]. Tam również można znaleźć stwierdzenie o praktycznej dokładnej nierozwiązywalności problemów optymalizacji globalnej. Rozważania o pułapce ewolucyjnej są inspirowane pracami Galara [26]. Pogłębioną analizę teoretyczną metod reprodukcji i sukcesji można znaleźć w [6], gdzie Back podał również odmienne szacowanie prawdopodobieństwa reprodukcji w metodzie turniejowej wzory (3.37) i (3.38) są zaczerpnięte z [9]. Goldberg [31] wiele uwagi poświęca technikom skalowania przystosowania, które są wykorzystywane w celu poprawienia zbieżności metody reprodukcji proporcjonalnej; o technikach tych można również przeczytać w [33]. Rangowa metoda reprodukcji z liniową funkcją pr(X) została wprowadzona przez Bakera (wyniki referowane przez Goldberga [31]). Metoda ta była poddawana krytyce, gdyż komplikuje ona relacje między przystosowaniem schematów a licznością ich reprezentacji. 0 zastosowaniach nieliniowej funkcji pr(X) donosi na przykład Michalewicz [54]. Sukcesję z częściowym zastępowaniem badał de Jong, nazywając ją planem reprodukcyjnym; jego wyniki referuje Gold-berg [31].
Trudno jest wskazać źródło, w którym wiele uwagi poświęcono by kryteriom zatrzymania. Przedstawiona w niniejszej książce próba klasyfikacji jest oparta na doświadczeniu autora i nie wydaje się być powszechnie uznawana. Hulin [36] wprowadził interesujące bayesowskie kryterium zatrzymania, w którym podczas monitorowania działania algorytmu ewolucyjnego tworzy się model probabilistyczny procesu generowania nowych rozwiązań. Zatrzymanie algorytmu następuje po stwierdzeniu, że prawdopodobieństwo wygenerowania rozwiązania poprawiającego najlepsze dotychczas znalezione zmalałoby poniżej pewnego minimalnego poziomu. Możliwość wykorzystania spadku wartości samoczynnie adaptowanego zasięgu mutacji poniżej minimalnego poziomu sugerują m.in. Back [6] i Schwefel [93].
3.7. Pytania i ćwiczenia
.143.
Metody wyznaczania macierzy kowariancji, rozkładu na wartości i wektory własne, definicję dyskrepancji i sekwencje o niskiej dyskrepancji można znaleźć w [68].
3.7. Pytania i ćwiczenia
1. Wyprowadź zależność określającą prawdopodobieństwo reprodukcji turniejowej.
2. Czy reprodukcja turniejowa z sukcesją z całkowitym zastępowaniem jest równoważna metodzie selekcji stosowanej w programowaniu ewolucyjnym? Uzasadnij odpowiedź.
3. Rozważmy różniczkowalną funkcję $(X). Wykonajmy A perturbacji pojedynczego punktu X� L Rn, zakładając, że perturbacja każdej zmiennej niezależnej odbywa się poprzez dodanie wartości, wygenerowanej z rozkładu normalnego o zerowej wartości oczekiwanej i odchyleniu standardowym 4. Niektórzy autorzy charakteryzują intensywność nacisku selektywnego przez tzw. czas dominacji (takeover time}. Jest to oczekiwana wartość liczby generacji, która jest potrzebna, aby kopie najlepszego rozwiązania w populacji P� wypełniły populację P* (zakładając nieobecność operatorów genetycznych oraz nieskończoną liczność populacji bazowej fj,). Wyprowadź równanie czasu dominacji dla podstawowych metod reprodukcji (przy założeniu sukcesji trywialnej). Czy dominacja zawsze będzie miała miejsce, jeśli populacja ma skończoną liczność?