Wykład 2.
Podstawowe typy algorytmów ewolucyjnych

W tym wykładzie omówiono najbardziej znane typy algorytmów ewolucyjnych: algorytmy genetyczne, strategie ewolucyjne, programowanie ewolucyjne i genetyczne. Algorytmy, które zasadniczo różnią się metodami selekcji, opisano wmozliwienajbardziej,,typowym" wariancie, tzn. zkodowa-niem chromosomów i operatoramigenetycznymi używanymi najczęściej przez autorów pierwszych publikacji poświęconych wymienionym metodom.

2.1. Algorytmy genetyczne

2.1.1. Prosty algorytm genetyczny

W roku 1975 John Holland zaproponował algorytm, którego zadaniem było modelowanie procesu ewolucji. Schemat tego algorytmu, zwanego obecnie prostym algorytmem genetycznym (SGA), przedstawiono na rys. 2.1.
Algorytm przetwarza dwie populacje: P*, zwaną populacją bazową, oraz O*, zwaną populacją potomną. Posługujemy się też populacją tymczasową T*, w której przechowywane są kopie osobników z P*. W populacjach tych zawarta jest jednakowa liczba osobników. W kroku "inicjacja P�" populacja bazowa jest wypełniana losowo wygenerowanymi osobnikami. Dla każdego z nich obliczana jest na etapie oceny wartość funkcji przystosowania. Po przygotowaniu populacji bazowej P� przystępuje się do głównej pętli programu, w której zdefiniowany jest proces sztucznej ewolucji.
Na początku następuje reprodukcja, polegająca na skopiowaniu do populacji tymczasowej T* losowo wybranych osobników
.66.
2. Podstawowe typy algorytmów ewolucyjnych
z populacji bazowej. Prawdopodobieństwa wylosowania osobników nie są jednak sobie równe osobniki o większej wartości funkcji przystosowania mają większe szanse reprodukcji; ponadto stosuje się losowanie ze zwracaniem. W efekcie, można oczekiwać, że w wyniku reprodukcji w populacji tymczasowej znajdzie się większa liczba kopii lepiej przystosowanych osobników.
procedurę Prosty algorytm genetyczny begin
t := 0
inicjacja P�
ocena P�
while (not warunek stopu) do
begin
Tł := reprodukcja Pż
O' := krzyżowanie i mutacja T*
ocena O*
pt+i := Q* ' ł
t := t+1 end end
RYSUNEK 2.1. Schemat prostego algorytmu genetycznego według J. Hollanda
Następnie, osobniki z T* poddawane są operacjorn genetycznym krzyżowaniu i mutacji. Są one kojarzone w rozłączne pary i dla każdej pary podejmowana jest decyzja o krzyżowaniu. Jeśli jest ona pozytywna, to następuje krzyżowanie, a powstałe osobniki potomne zastępują swoich rodziców. W przypadku decyzji negatywnej, parajest pozostawiana bez zmian. Prawdopodobieństwo zajścia krzyżowania pc jest parametrem algorytmu. Następnie, dla każdego osobnika z Tf jest wykonywana mutacja, będąca perturbacją jego genotypu. Utworzone w ten sposób osobniki są poddawane ocenie poprzez obliczenie wartości funkcji przystosowania i stanowią populację potomną O*. Populacja ta staje się nową populacją bazową w kolejnym obiegu pętli.
Pętlę wykonuje się dopóty, dopóki nie jest spełniony warunek zatrzymania. Może nim być na przykład wykonanie określonej liczby generacji, bądź też odnalezienie osobnika o odpowiednio dużej wartości funkcji przystosowania. Każdy obieg głównej pętli algorytmu nazywa się często generacją i traktuje jako jedną jego iterację, a stan populacji P* w chwili t określa się mianem pokolenia.
-.il A. ', 2.1. Algorytmy genetyczne
.67.
Gen
0 1 0 0 0 1 0 '1\ 1 0
Chromosom
RvsuNEK 2.2. Chromosom z kodowaniem binarnym
Kodowanie osobników i operacje genetyczne. Schemat algorytmu zaproponowany przez Hollanda abstrahuje od przyjętego sposobu kodowania osobników i wykonywania operacji krzyżowania i mutacji, jednakże algorytm genetyczny najbardziej jest znany z kodowaniem binarnym. W tej wersji chromosom jest więc n-elementowym wektorem genów, z których każdy jest zerem lub jedynką (rys. 2.2).
Osobnik rodzicielski
OliO>00\ \ \ podczas mutacji �
Osobnik potomny
0 J 1 0 0 0 0 l 0
RYSUNEK 2.3. Mutacja w kodowaniu binarnym
\
Mutacja osobnika jest operatorem wykonywanym dla każdego genu osobno. Polega ona na tym, że z prawdopodobieństwem pm, którego wartość jest parametrem algorytmu, wartość genu zmienia się na przeciwną (rys. 2.3).
Z kolei w krzyżowaniu udział biorą dwa osobniki rodzicielskie; przebieg tej operacji jest wzorowany na obserwowanym w przyrodzie procesie przemian w DNA, zachodzących podczas rozmnażania generatywnego. Chromosomy rodzicielskie są rozci-
Osobniki rodzicielskie
Osobniki potomne
0 0 1 0 0 0 1 0 0
0 1 0 1 1 1 0 0 1
RYSUNEK 2.4. Krzyżowanie w kodowaniu binarnym
.68.
2. Podstawowe typy algorytmów ewolucyjnych
nane na dwa fragmenty. Następnie pierwszy fragment pierwszego chromosomujest sklejany z drugim fragmentem drugiego chromosomu; podobnie pierwszy fragment drugiego chromosomu z drugim fragmentem pierwszego. Powstałe w ten sposób łańcuchy tworzą chromosomy osobników potomnych (rys. 2.4).
Wszystkie chromosomy zawierają jednakową liczbę bitów, dlatego też rozcięcie musi być wykonane w tym samym miejscu dla obu chromosomów. Miejsce rozcięcia jest wybierane losowo z rozkładem równomiernym.
Sposób reprodukcji. Populacja tymczasowa T* jest tworzona w sposób, w którym "preferuje się" osobniki lepiej przystosowane. W tym celu J. Holland zaproponował schemat zwany reprodukcją proporcjonalną albo ruletkową4. Określa się zmienną losową na zbiorze dla elementów populacji P*, o rozkładzie danym wzorem
Pr(X) =
<&(X)
(2.1)
gdzie X oznacza osobnika, <5(X) zaś jego wartość przystosowania. Następnie dokonuje się wielokrotnego próbkowania tej zmiennej losowej, za każdym razem kopiując wylosowanego osobnika do populacji tymczasowej T*.
PRZYKŁAD. W celu ilustracji działania mechanizmów algorytmu genetycznego rozważmy następujący prosty przyktad. Załóżmy, że chromosomy są kodowane binarnie i skladają się z n = 10 genów bitów, funkcja celu zaś jest równa liczbie jedynek w chromosomie (dzięki temu można ją będzie łatwo obliczyć)
(2.2)
Przyjmijmy też, że krzyżowanie jednopunktowe jest wykonywane z prawdopodobieństwem pc = 0.7,, a prawdopodobieństwo mutacji pm = 0.1. Niech populacja bazowa P* zawiera fj, = 20 osobników, ponumerowanych kolejno: X*,X2,..., X'*.
Załóżmy, że w pewnej chwili t populacja bazowa P* składała się z osobników, których chromosomy i wartości funkcji przystosowania podano w tab. 2.1.
4Nazwa reprodukcji ruletkowej powstała dzięki podobieństwu do gry w ruletkę, z tym że ruletka selekcyjna, w przeciwieństwie do spotykanych w kasynach gry, jest "sfałszowana" wypadnięcie pewnych liczb jest bardziej prawdopodobne niż innych. W takiej ruletce fragment koła odpowiadający osobnikowi ma długość wprost proporcjonalną do jego przystosowania. Tworzenie populacji T( odbywa się poprzez wielokrotne zakręcenie kołem i skopiowanie do T' tego osobnika, na którego polu zatrzymała się kulka rzucona przez wyimaginowanego krupiera.
2.1. Algorytmy genetyczne
.69.
TABELA 2.1. Zawartość populacji P*. W kolejnych kolumnach znajdują się dane osobnika o numerze i: X1 jego chromosom, <3?(X*) wartość przystosowania, pr(Xl) prawdopodobieństwo reprodukcji, Pr(Xl) dystrybuanta rozkładu reprodukcji, "&(X) wartość średnia przystosowania osobników
ż Xi *(X1) Pr(X') Pr(X<)
1 1111110011 8 0.0824 0.0824
2 0110100100 4 0.0412 0.1237
3 0000110100 3 0.0309 0.1546
4 0110100111 6 0.0618 0.2164
5 1001111001 6 0.0618 0.2783
6 1001110011 6 0.0618 0.3402
7 0000100101 3 0.0309 0.3711
8 1000110100 4 0.0412 0.4123
9 0001011001 4 0.0412 0.4536
10 1011110000 5 0.0515 0.5051
11 0010111101 6 0.0618 0.5670
12 1100010010 4 0.0412 0.6082
13 0111110111 8 0.0824 0.6907
14 0100101100 4 0.0412 0.7319
15 0001100110 4 0.0412 0.7731
16 1001001101 5 0.0515 0.8247
17 1010000110 4 0.0412 0.8659
18 0010101100 4 0.0412 0.9072
19 1101000011 5 0.0515 0.9587
20 0010010011 4 0.0412 1.0000
<&(X) 4.85
Na podstawie wartości funkcji przystosowania można określić rozkład prawdopodobieństwa reprodukcji pr(X*) i jego dystrybu-antę P,.(X*). W celu wyznaczenia osobnika do reprodukcji, dokonujemy z rozkładem jednostajnym losowania liczby a z przedziału (0,1)*. Jeśli spełnia ona warunek
ato reprodukcji podlega osobnik X1, w przeciwnym przypadku re-produkowanyjest osobnik X1, dla którego zachodzi (rys. 2.5)
< a < Pr(X*)
(2.4)
W tabeli 2.2 przedstawiono kolejne kroki tworzenia populacji potomnej O* na podstawie populacji bazowej w wyniku reprodukcji, krzyżowania i mutacji. Pary zreprodukowanych osobników poddano krzyżowaniu z prawdopodobieństwem pc; te pary, dla których me zapadła decyzja o krzyżowaniu, przechodzą przez ten etap *^^"met^*"o niezmienione. Następnie, produkty krzyżowania (lub prostej repro- ności dystrybuanty.
.70.
2. Podstawowe typy algorytmów ewolucyjnych
"Pr(X<)
1.0-
a = 0.735
0.5-
Wylosowany osobnik
0 1
10
15
20
RvsuNEK 2.5. Sposób realizacji reprodukcji ruletkowej. Punktami zaznaczono wartości dystrybuanty P,-(X), linią poziomą wartość a (patrz (2.4))
*Analiza wektora wartości własnych macierzy kowariancji jest często wykorzystywana, np. w analizie sygnałów. Więcej informacji na ten temat można znaleźć w dodatku D.
dukcji) ulegają dodatkowo mutacji w taki sposób, że dla każdego genu podejmuje się losowo decyzję o jego mutacji.
Zauważmy, że średnia wartość przystosowania zreprodukowa-nych osobników w populacji T* jest większa niż średnie przystosowanie w populacji bazowej P*. Można było oczekiwać tego zjawiska, gdyż mechanizm reprodukcji tak skonstruowano, aby promować lepsze osobniki. Ceną, jaką przyjdzie za to zapłacić, jest zmniejszenie różnorodności Tł w stosunku do P*. Operatory genetyczne przywracają różnorodność w O*, nie gwarantując poprawy średniego przystosowania. W podanym przykładzie, ze względu na rodzaj funkcji przystosowania, operator krzyżowania nie wprowadza zmian wartości średniej, gdyż nie zmienia liczby jedynek w chromosomie. Podobnie mutacja, która z jednakowym prawdopodobieństwem zamienia jedynkę na zero i odwrotnie, ma z tych samych powodów neutralny (w sensie wartości oczekiwanej) wpływ na średnie przystosowanie. Nie musi tak być (i w większości praktycznych problemów nie jest) i wówczas za poprawę różnorodności przychodzi zapłacić zmniejszeniem średniej wartości funkcji przystosowania.
Spróbujmy teraz uściślić ocenę zmian różnorodności populacji poczynioną jedynie na podstawie obserwacji zawartości populacji. Dla potrzeb przykładu załóżmy, że o różnorodności populacji świadczy wektor wartości własnych macierzy kowariancji genotypów osobników w tejpopulacji*.
W przypadku idealnego zróżnicowania, wartości własne powinny być sobie równe. Im większe zależności między genotypami osobników, tym mniejsza różnorodność populacji i większe wartości własne wektora kowariancji oraz większe ich zróżnicowanie.
TABELA 2.2. Przebieg cyklu reprodukcji, krzyżowania i mutacji. W kolejnych kolumnach znajdują się: Ęr � wartość zmiennej losowej wykorzystywanej do określenia numeru reprodukowanego osobnika, i jego numer, X1 jego genotyp, <&(X1) jego przystosowanie, Lc wartość zmiennej losowej opisującej decyzję o krzyżowaniu, fc pozycja rozcięcia do skrzyżowania, Z' genotyp osobnika potomnego (czcionką półgrubą zaznaczono geny zamienione w wyniku krzyżowania), <&(Z1) jego przystosowanie, Lm wektor decyzji o mutacji poszczególnych genów osobników powstałych w wyniku krzyżowania, Y* genotyp powstały w wyniku mutacji (czcionką półgrubą zaznaczono geny, które uległy zmianie w wyniku mutacji), $(Yl) przystosowanie wynikowego osobnika
Lr i X4 $(X') k k Z1 <&(Z') Śm Y1 *(Y')
0.0267 1 1111110011 8 1 l 1111110011 8 000001000 1111111011 9
0.0428 1 1111110011 8 1 l 1111110011 8 000100000 1110110011 7
0.3426 7 0000100101 3 0 - 0000100101 3 000000100 0000100001 2
0.6351 13 0111110111 8 0 - 0111110111 8 010001100 0011111011 7
0.6975 14 0100101100 4 1 8 0100101100 4 000000001 0100101101 5
0.8737 18 0010101100 4 1 8 0010101100 4 001000000 0000101100 3
0.6515 13 0111110111 8 1 4 0111110000 5 000010000 0111100000 4
0.4964 10 1011110000 5 1 4 1011110111 8 000000000 1011110111 8
0.1706 4 0110100111 6 1 5 0110110111 7 100000000 1110110111 8
0.6526 13 0111110111 8 1 5 0111100111 7 000000000 0111100111 7
0.8075 16 1001001101 5 1 3 1001011001 5 000000001 1001011000 4
0.4402 9 0001011001 4 1 3 0001001101 4 100000100 1001001001 4
0.6374 13 0111110111 8 1 4 0111110011 7 000000000 0111110011 7
0.3319 6 1001110011 6 1 4 1001110111 7 000000000 1001110111 7
0.1149 2 0110100100 4 0 - 0110100100 4 000000000 0110100100 4
0.1312 3 0000110100 3 0 - 0000110100 3 000000000 0000110100 3
0.6967 14 0100101100 4 0 - 0100101100 4 000100000 0101101100 5
0.9837 20 0010010011 4 0 - 0010010011 4 000000100 0010010111 5
0.3618 7 0000100101 3 1 6 0000100000 1 000001100 0000101100 3
0.4661 10 1011110000 5 1 6 1011110101 7 000100000 1010110101 6
$(X>) 5.40 5.40 5.40
.72.
2. Podstawowe typy algorytmów ewolucyjnych
TABELA 2.3. Zmiany wektora wartości własnych macierzy kowariancji genotypów w kolejnych etapach cyklu algorytmu genetycznego
Przed reprodukcją Po reprodukcji Po krzyżowaniu Po mutacji
^0.6798^ "0.8701" r0.8954" "0.8121"
0.4677 0.5259 0.4417 0.4587
0.3087 0.2949 0.2476 0.3664
0.2859 0.2028 0.2092 0.2125
0.2127 0.1443 0.1772 0.1598
0.1661 0.1229 0.1174 0.1453
0.1630 0.0926 0.0924 0.1017
0.0991 0.0359 0.0785 0.0878
0.0636 0.0271 0.0415 0.0565
0.0508 0.0045 0.0200 0.0307
W tabeli 2.3 podano wartości własne macierzy kowariancji populacji wyjściowej, populacji potomnej po reprodukcji, po krzyżowaniu i po mutacji.
Jak nietrudno zauważyć, największa zmiana różnorodności następuje podczas reprodukcji. Jest to spowodowane faktem, że niektóre chromosomy zreprodukowano wielokrotnie, niektóre zaś pominięto w tym procesie, w zależności od wartości funkcji przystosowania. Krzyżowanie nie wprowadza nowego materiału genetycznego (wariancja poszczególnych genów pozostaje bez zmian), lecz powoduje jego "przetasowanie". Prowadzi to do zwiększenia różnorodności, czyli poprawy rozkładu wartości własnych macierzy kowariancji. Z kolei mutacja wprowadza modyfikacje materiału genetycznego, co, podobnie jak w krzyżowaniu, owocuje poprawą rozkładu wartości własnych. Stopień poprawy jest nieco mniejszy niż w przypadku krzyżowania wynika to z faktu, że mutacja jest operatorem oddziałującym na pojedyncze geny, podczas gdy krzyżowanie na ich całe bloki.
Kiedy zatrzymać algorytm genetyczny? Powyższe pytanie o warunek zatrzymania algorytmu jest bardzo kłopotliwe i nie doczekało się zadowalającej odpowiedzi. Najlepszą (chociaż niezbyt praktyczną) odpowiedzią jest ... nigdy, ponieważ algorytm genetyczny jest procesem losowym i nie sposób zagwarantować osiągnięcia wyniku w skończonej liczbie generacji. Warunki zatrzymania omówiono w p. 3.5.
2.1.2. Schematy
Pytanie, dlaczego algorytmy genetyczne działają, doczekało się wielu prób odpowiedzi. W tym podrozdziale przedstawiono historycznie pierwszą próbę wyjaśnienia sposobu działania algorytmu genetycznego, korzystającą z pojęcia schematu.
2.1. Algorytmy genetyczne
.73.
Schematem S jest zbiór chromosomów jednoznacznie zdefiniowany przez wzorzec podobieństwa Ps, określający cechy wspólne elementów. Wprowadza się dodatkowy symbol wartości dowolnej $. Wzorzec podobieństwa jest łańcuchem symboli należących do zbioru {0,1, #}. Do schematu S należą chromosomy o wartościach genów identycznych jak zapisane we wzorcu podobieństwa na tych pozycjach, na których nie ma symbolu #.
PRZYKŁAD. Rozważmy chromosomy będące siedmiobitowymi wektorami. Niech schemat Są będzie zdefiniowany wzorcem podobieństwa PSl = 0110##1, natomiast schemat 82 będzie zawierał osobniki pasujące do wzorca PS2 = 0#1#11#. Wówczas schematy te będą zawierać następujące chromosomy:
51 = {0110001,0110011,0110101,0110111}
52 = {0010110,0010111,0011110,0011111,0110110,0110111,
0111110,0111111}
Jak łatwo zauważyć, jeden chromosom może należeć jednocześnie do wielu schematów; przykładowo, chromosom 0110111 należy zarówno do schematu S\, jak i S^.
W dalszym ciągu będziemy utożsamiać schematy z wzorcami podobieństwa; zamiast o "schemacie S definiowanym wzorcem podobieństwa 01#1#01", będziemy mówić o ,^chemacie 01#1#01", pamiętając jednocześnie, że schemat nie jest wzorcem podobieństwa, lecz zbiorem chromosomów. Kolejnym skrótem myślowym jest stwierdzenie, że ,^chemat S jest reprezentowany w populacji P*" oznacza to tyle, że chromosom co najmniej jednego osobnika z populacji P* pasuje do wzorca podobieństwa schematu 5.
Za Hollandem wprowadzimy teraz kilka pożytecznych definicji dotyczących wzorców podobieństwa schematów.
Rzędem schematu o(S) jest liczba wartości wzorca Ps różnych od #
(2.5)
i=l
gdzie XA(X) jest funkcją charakterystyczną zbioru A.
Długością definiującą schematu d(S) jest (powiększona o 1) różnica indeksów między skrajnymi wartościami wzorca różnymi od #
= l}+l (2-6)
.74.
2. Podstawowe typy algorytmów ewolucyjnych
Wartością przystosowania schematu $(5) jest średnia wartość przystosowania wszystkich chromosomów schematu
.. (2-7)
xes
PRZYKŁAD. W ia6e/i #.^ podano przykładowe schematy, ich rząd oraz długość definiującą.
TABELA 2.4. Rząd oraz długość definiująca dla różnych schematów
S o(5) d(S)
0101001 7 7
#i##### : 1 1
#1###0# 2 5
####10# 2 2
#1#010# 4 5
Twierdzenie o schematach. Twierdzenie o schematach Hol-land sformułował jako próbę wyjaśnienia sposobu działania algorytmu ewolucyjnego. Przyjmuje się następujące założenia:
1) populacja bazowa zawiera nieskończenie wiele osobników,
2) w populacji bazowej znajdują się chromosomy należące do wszystkich możliwych schematów,
3) działa selekcja proporcjonalna,
4) problem ma binarną reprezentację, stosowany jest operator krzyżowania jednopunktowego i mutacji bitowej (której prawdopodobieństwo jest bliskie zeru).
Przy takich założeniach, twierdzi się, że wartość oczekiwana liczby chromosomów należących do schematu w kolejnej generacji E(\S\pt+i) jest szacowana w następujący sposób: ..,-, >� .:.�
E(\S\)Pt+, >
'$(5)
'n-\
< (2-8)
gdzie \S\ jest liczebnością schematu. Ze wzoru (2.8) wynika, że liczba osobników należących do krótkich schematów, których przystosowanie przewyższa średnią, będzie miała tendencję wzrostową.
Hipoteza bloków tworzących. Przytoczona powyżej obserwacja dała podstawy hipotezy bloków tworzących, charakteryzującej w przybliżony sposób działanie algorytmu ewolucyjnego. Uważa się, że w kolejnych generacjach chromosomy te będą "składane" z coraz to lepszych, krótkich schematów, zwanych blokami tworzącymi (building blocks}. O blokach tworzących można mó-
2.1. Algorytmy genetyczne
.75,
wić nie tylko w przypadku kodowania binarnego, chociaż hipoteza ta powstała właśnie na tym gruncie. Koncepcja bloków tworzących jest dość wygodnym sposobem myślenia pozwalającym na konstruowanie specjalizowanych operatorów genetycznych, dostosowanych do rozwiązywanego problemu. Skoro za pomocą algorytmu genetycznego (lub ogólniej ewolucyjnego) rozwiązania otrzymujemy w sposób przyrostowy, dopasowując bloki tworzące, to należy tak dobierać sposób kodowania i operatory genetyczne, aby wyodrębnić bloki tworzące poprzez kodowanie i nie tracić ich podczas operacji genetycznych. Przeświadczenie to stanowiło motywację do tworzenia specjalizowanych algorytmów ewolucyjnych, których kodowanie i operatory genetyczne uwzględniają specyfikę rozwiązywanego problemu*.
Wbudowana równoległość. Kolejnym wnioskiem wynikającym z analizy zmian liczności schematów w czasie jest wbudowana równoległość. Holland zauważył, że liczba schematów efektywnie przetwarzanych przez algorytm genetyczny z populacją bazową P*, zawierającą ^, osobników, jest proporcjonalna do ^3.
Uwagi. Wyniki otrzymane na podstawie analizy schematów (twierdzenie o schematach i wbudowana równoległość) są uzyskane przy dość niepraktycznych założeniach (nieskończona licz-ność populacji bazowej i jej bardzo dobre zróżnicowanie, binarne kodowanie problemu, szczególne operatory genetyczne), a także nie pozwalają na skonstruowanie kryterium zatrzymania czy przeprowadzenie dowodu zbieżności. Z tych powodów, użyteczność schematów jako narzędzia analizy działania algorytmu genetycznego jest niewielka.
Zamiast teorii schematów, do analizy działania algorytmu genetycznego wykorzystuje się obecnie teorię procesów Markowa. Pozwala ona między innymi na przeprowadzenie dowodu zbieżności algorytmu w niedeterministycznym sensie. Można ponadto stosunkowo nietrudno odejść od wielu założeń: o kodowaniu binarnym, o selekcji proporcjonalnej i o operatorach genetycznych. Podstawową wadą metod analizy algorytmu genetycznego prowadzących do asymptotycznych wyników jest pominięcie prawie wszystkich cech specyficznych tego algorytmu, których istotność jest obserwowana w eksperymentach numerycznych (wykonywanych z konieczności w skończonym czasie).
Hipoteza bloków tworzących, być może dzięki nieformalnemu sformułowaniu, wydaje się być stosunkowo najbardziej nośna, gdyż "elegancko" wyjaśnia sposób działania operatora krzyżowania oraz podkreśla istotność wykorzystania regularności problemu do zdefiniowania tego operatora. Wychodząc z hipotezy bloków *Zagadnieniu tworzących, wprowadzono wiele nowych operatorów, dostosowa- ^d'rlzdz^' nych do specyfiki problemu (np. operatory OX i PMX dla pro- książki.
temu zo-
Dny osobny
l!i części
.76.
2. Podstawowe typy algorytmów ewolucyjnych
blemukomiwojażera). Składanie optymalnego (globalnie) rozwiązania z wielu lokalnie optymalnych (lub przynajmniej subopty-malnych) fragmentów nie jest zresztą pomysłem oryginalnym podobną ideę można znaleźć między innymi w programowaniu dynamicznym, heurystycznych metodach przeszukiwania itp. O odmienności algorytmów ewolucyjnych decyduje przede wszystkim fakt, że rozwiązania cząstkowe są składane w sposób losowy (choć nie całkiem przypadkowy) i wiele z nich jest jednocześnie obec-nychwpopulacjibazowej. !
2.1.3. Symulacja działania algorytmu genetycznego
Podejmiemy próbę wyznaczenia rozwiązania problemu plecakowego za pomocą prostego algorytmu genetycznego. Problem plecakowy jest dokładniej opisany w dodatku B2. Zadanie polega na podjęciu decyzji o załadowaniu do plecaka przedmiotów z których każdy ma określoną wagę Wi, i przynosi korzyść pi w taki sposób, aby zmaksymalizować korzyść całkowitą, nie przekraczając dopuszczalnej wagi całkowitej.
Chromosom binarny stanowi dość wygodny sposób kodowania, gdyż można go wykorzystywać, bez konieczności dodatkowych zabiegów, do reprezentowania wektora zmiennych niezależnych x; tak więc chromosom X będzie utożsamiany z wektorem x. Do przekształcania chromosomów zastosujemy operatory genetyczne zdefiniowane w poprzednim podrozdziale, tzn. mutację zmieniającą wartość bitu z prawdopodobieństwem pm oraz krzyżowanie jednopunktowe.
Ograniczenie pojemności plecaka będziemy uwzględniać, stosując liniową zewnętrzną funkcję kary. Funkcja przystosowania osobnika X będzie zdefiniowana następująco:
i - K max
i=l
- W, 0
(2.9)
,i=l
gdzie K jest współczynnikiem wagowym, dobieranym w taki sposób, aby odpowiednio mocno karać rozwiązania niedopuszczalne i w ten sposób zmniejszać ich szanse reprodukcji. Przyjmijmy poniższe określenie wartości K
K = max
i=l,...,n
min
i=l,...,n
(2.10)
Wykorzystana zostanie metoda reprodukcji proporcjonalnej. Wymaga ona jednak, aby wartości funkcji przystosowania były dodatnie, co nie musi być prawdą w przypadku przyjętej metody uwzględniania ograniczenia. Aby temu zaradzić, zastosujemy metodę skalowania przystosowania (fitness scaling), w której
2.1. Algorytmy genetyczne
.77.
prawdopodobieństwo reprodukcji jest określone wzorem
Pr(X) =
(2.11)
gdzie &min jest wartością funkcji przystosowania najgorszego osobnika w populacji P*
= min<5(Y)
(2.12)
Dzięki temu unikniemy niebezpieczeństwa uzyskania "ujemnego prawdopodobieństwa".
Warunki eksperymentu. W eksperymencie omówionym poniżej pakowano plecak zawierający n = 50 elementów. Wartosci.#i^ Wi wygenerowano w sposób losowy, niezależnie od siebie, z rozkładu jednostajnego na przedziale [0.0001,1]. Limit wagi plecaka przyjęto W = 13, co stanowi około 25% sumy wag plecaka.
Algorytm genetyczny zawierał f.i 100 osobników w populacji bazowej Pł. W chwili t = 0, populacja bazowa wypełniana była losowo generowanymi osobnikami. Chromosom każdego z nich był tworzony poprzez 50-krotne próbkowanie zmiennej losowej o rozkładzie dwupunktowym z prawdopodobieństwem wylosowania jedynki równym 0.2 (czyli zawierał około 20% jedynek, a resztę zer). Ustalono prawdopodobieństwa operatorów genetycznych: pm = 0.02 (dla mutacji) i pc = 0.7 (dla krzyżowania). Algorytm był zatrzymywany, jeśli przez 100 kolejnych generacji nie następowała poprawa rozwiązania dotychczas najlepszego.
Jednorazowe uruchomienie algorytmu. Przyjrzyjmy się najpierw wynikom pojedynczego uruchomienia algorytmu genetycznego. Na rysunku 2.6a przedstawiono typowe krzywe zbieżności, jakie można uzyskać, uruchamiając jednorazowo algorytm genetyczny. Pokazano na nim zmienność w czasie wartości średniej, minimalnej i maksymalnej (obliczane dla bieżącej populacji bazowej) funkcji przystosowania.
Nietrudno zauważyć, że algorytm porusza się niejako "skokami" obserwując wyniki, można wyodrębnić fazy szybkiej poprawy i następujące po nich okresy stagnacji lub wręcz pogorszenia średniej. W okresach szybkiej poprawy przewagę uzyskuje zbieżność do maksimum lokalnego. Stagnacja ma w rzeczywistości charakter dynamiczny nie obserwuje się wprawdzie poprawy najlepszego rozwiązania, lecz stale są przeszukiwane nowe rozwiązania w otoczeniu istniejących. Wniosek taki można wyciągnąć na podstawie obserwacji, że mimo stagnacji, wartości minimalna i maksymalna nie przejawiają tendencji do wzajemnego przybliżania się. Świadczy to o różnorodności populacji, wprowadzanej przez stale działające operatory genetyczne.
.78.
2. Podstawowe typy algorytmów ewolucyjnych
22
20
1B 18
12
10
40 35 30
g25
>& *~b 20
5 o
�O1 15
10
5
0
100
100
200
300 t
400
(a)
200
300 t
400
500
600
500
600
(b)
RvsuNEK 2.6. Pojedyncze uruchomienie algorytmu genetycznego: a) krzywe zbieżności, b) wykres zmian wartości średniej i wariancji wartości przystosowania w populacji bazowej (pomnożonej przez 25 w celu zobrazowania na wspólnym wykresie)
2.1. Algorytmy genetyczne
.79.
Okres stagnacji kończy się charakterystycznym zmniejszeniem średniego przystosowania, co pozwala przypuszczać, że w wyniku działania mutacji i krzyżowania, zawartość populacji bazowej znacznie różni się od zawartości w momencie znalezienia rozwiązania dotychczas najlepszego. Jest to faza "chwytania przyczółków", po której często następuje kolejna faza szybkiej poprawy.
Powyższa interpretacja staje się bardziej wiarygodna, gdy weźmiemy pod uwagę miarę różnorodności populacji bazowej wariancję wartości przystosowania w populacji (rys. 2.6b)*. Łatwo dostrzeżemy, że w okresie szybkiej poprawy zróżnicowanie ma tendencje spadkowe. Typowy histogram przystosowania w populacji odpowiadający tej fazie znajdziemy na rys. 2.7. Zauważmy, że ma on kształt z grubsza symetryczny. Populacja jest zdominowana przez osobniki o przystosowaniu bliskim średniej wartości. Osobniki o wartościach zbliżonych zarówno do minimum, jak i maksimum, występują w niewielkiej liczbie.
20
15 -
10
O
_LLQ_
ffl
10
12
14
16
18
20
RYSUNEK 2.7. Stagnacja populacji. Histogram wartości przystosowania (dla populacji i=l)
Z ciekawszą sytuacją mamy do czynienia w czasie poprzedzającym nagły wzrost średniego przystosowania wariancja przystosowania zwiększa się wówczas znacząco, czemu towarzyszy nieznaczny spadek wartości średniej. Przyjrzyjmy się histogramom przystosowania w populacjach o numerach od 172 do 175, czyli w okresie "przełomu" (rys. 2.8 i 2.9). Już w generacji 172 daje się zauważyć istnienie dwóch maksimów liczności dla różnych warto- *Taka miara różnorodności funkcji przystosowania. W kolejnych generacjach rozwiązania chocfaVnie"swtdcz''"z"oz-bliskie maksimum o większej wartości funkcji przystosowania do- nicowaniu genotypów.
.80.
2. Podstawowe typy algorytmów ewolucyjnych
20
15
UJ * rt
o>^ 10
N O
20
15
10
O
6 8 10 12 14 16 18 20
(a)
10
12
14
16
18
20
(b)
RYSUNEK 2.8. Histograrny przystosowania w generacjach 172 (a) i 173 (b). Znaleziono nowe maksimum przystosowania, do którego "przelewa się" populacja. Widoczne dwa maksima częstości poniżej i powyżej wartości 16; maksimum dla wartości większych niż 16 zaczyna dominować (rys. b)
20
15
10
O
2.1. Algorytmy genetyczne _____ 81.
hm
6 8 10 12 14 16 18 20
*(X)
w '
20
15
N
O
10
8 10
12 14
*(X)
(b)
16 18 20
RYSUNEK 2.9. Histogramy przystosowania w generacjach 174 (a) i 175 (b). Ciąg dalszy "przelewania się" populacji do maksimum o wartości powyżej 16; maksimum poniżej 16 zanika
.82.
2. Podstawowe typy algorytmów ewolucyjnych
10
O
19
19.2 19.4 19.6
19.8
Wynik
20 20.2 20.4
(*)
1 w 8 � n
^O c
^co o
o
c/3
0>>
N
0
4
2 m i nnn
o - " n ii fi.n j
200 400 600 800 1000 1200
Koszt
(b)
RYSUNEK 2.10. Histogramy: a) wartości funkcji przystosowania rozwiązań uzyskiwanych przez algorytm, b) liczby obliczeń wartości funkcji przystosowania do osiągnięcia kryterium zatrzymania '
2.2. Strategieewolucyjne
.83.
prowadzają do wyrównania (generacja 173), a następnie uzyskują przewagę w generacjach 174 i 175.
Wielokrotna symulacja algorytmu. Algorytm genetyczny jest metodą niedeterministyczną, co oznacza, że nie ma gwarancji znalezienia za każdym razem identycznego rozwiązania, a także, że będzie ono znalezione kosztem takiego samego nakładu obliczeń.
Wykonajmy 100 niezależnych uruchomień algorytmu genetycznego, aby uzyskać statystyczną informację o właściwościach algorytmu. Zaobserwujmy liczbę generacji wykonanych w każdym uruchomieniu, jak również znalezione rozwiązanie. Histogramy liczby generacji algorytmu oraz wartości funkcji przystosowania znalezionych rozwiązań przedstawiono na rys. 2.10.
Wartości funkcji przystosowania rozkładają się między 19.6 a około 20.4; różnica między najgorszym a najlepszym uzyskanym wynikiem wynosi więc 1.2, czyli około 6% wartości maksymalnej. Wartość tę możemy traktować jako oszacowanie dokładności rozwiązania zadania.
Liczba generacji zmienia się od około 300 do około 1000, co daje od 30000 do 100000 punktów próbkowanych przez algorytm* (jest to górne oszacowanie, gdyż jeden punkt może być generowany wielokrotnie). Wobec faktu, że liczba różnych chromosomów wynosi 250 � 1.12 � 1015, koszt znalezienia rozwiązania wydaje się znikomo mały.
2.2. Strategie ewolucyjne
2.2.1. Strategia (1+1)
Podstawą strategii ewolucyjnych był algorytm, który przez twórców został nazwany strategią (1 + 1). W algorytmie tym wprowadzono interesujący mechanizm adaptacji zasięgu mutacji (zwany regułą 1/5 sukcesów), który stanowił motywację dla zaawansowanych mechanizmów samoczynnej adaptacji tego zasięgu we współczesnych strategiach ewolucyjnych i jest podstawowym wyróżnikiem tych metod spośród innych algorytmów ewolucyjnych.
Schemat strategii (1 +1) przedstawiono na rys. 2.11. W strategii (1 +1) przetwarzany jest tylko jeden chromosom bazowy X1. W każdym kroku generowany jest nowy chromosom Y*, będący wynikiem perturbacji (czyli mutacji) X*. Wartości funkcji przystosowania w obu chromosomach są porównywane, po czym w ko-
., " r J ' f J
lejnej iteracji chromosomem X+ staje się ten, w którym wartość funkcji przystosowania jest większa**. Kluczową rolę w działaniu
J r i/ J x T: x.
strategii (1 + 1) odgrywa sposób mutacji. Chromosom Y jest ge-
*W cel u uzyska n ia tego górnego oszacowania, licz-ność populacji ^t wymno-żono przez liczbę generacji algorytmu.
**Jak łatwo zauważyć, jest to algorytm podobny, lecz prostszy od symulowanego wyżarzania. Różnica polega na tym, że w symulowanym wyżarzaniu dopuszcza się akceptację punktu "gor-
.84.
2. Podstawowe typy algorytmów ewolucyjnych
procedurę Strategia ewolucyjna (1 + 1) begin
t := 0
inicjacja X*
ocena X*
while (not warunek stopu) do
begin
Y*:=mutacjaX*
ocena Y*
if ( (Y') > $(Xł) ) then
begm
X*
else
X*+1 :
end
t := t+l
end
end
RYSUNEK 2.11. Schemat strategii ewolucyjnej (1+1)
nerowany przez dodanie losowej modyfikacji rozkładem normalnym do każdego genu chromosomu X*
r/ = ^ + a^v(o,i),i ( , _ (2.13)
Wartość a określa zasięg mutacji; w miarę jej zwiększania, coraz większe stają się perturbacje chromosomu bazowego. Jeśli założyć, że funkcja przystosowania ma więcej niż jedno maksimum, to takie silne perturbacje są, rzecz jasna, pożądane w początkowej fazie działania algorytmu, aby zwiększyć szansę zlokalizowania obszaru przyciągania "najlepszego" maksimum, czyli maksimum globalnego. Natomiast wraz ze zbliżaniem się do maksimum, w którego obszarze przyciągania znalazł się chromosom bazowy, opłaca się zmniejszać zasięg mutacji w celu umożliwienia dokładnej zbieżności. Błędem byłoby jednak przyjęcie bardzo małej wartości a, gdyż wówczas szybkość zbieżności byłaby niezadowalająco mała. Mając na uwadze konieczność pogodzenia przeciwstawnych celów, o których była mowa, zaproponowano algorytm dobierania wartości a, zwany regułą 1/5 sukcesów. W myśl tej reguły:
1) jeśli przez kolejnych k generacji liczba mutacji zakończonych sukcesem (czyli $(YL) > (X*) ) jest większa niż 1/5 ogólnej liczby wykonanych mutacji, to należy zwiększyć zasięg mutacji, stosując regułę a' := ą&,
2.2. Strategie ewolucyjne
.85.
2) gdy dokładnie 1/5 mutacji kończy się sukcesem, wartość a nie wymaga modyfikacji,
3) w przeciwnym przypadku należy zawęzić zasięg mutacji według
wzoru a :=
Wartość 1/5 została zaproponowana na podstawie rozważań teoretycznych prowadzonych dla wielowymiarowych funkcji testowych funkcji kwadratowej (tzw. model sferyczny) i hiper-płaszczyzny (tzw. model korytarzowy). Z kolei eksperymentalnie dobrano odpowiednie ustawienia wartości parametrów modyfikujących: cd = 0.82, q = 1/0.82.
Strategia ewolucyjna (1 + 1) przejawia niewielką odporność na minima lokalne, co było motywacją do poszukiwania innych, lepszych schematów. Powstały więc modyfikacje podstawowego schematu strategie (l + A) (w której jest generowany więcej niż jeden osobnik potomny), (n + \} i (^,A) (w których wprowadzono mechanizm samoczynnej adaptacji). ~"
2.2.2. Strategia (^ + A)
Strategia (^i + A) jest najczęściej (obok strategii (M)A)) wykorzystywanym schematem strategii ewolucyjnej (rys. 2.12). Jest to algorytm będący nie tylko prostym uogólnieniem schematu (1 + 1), lecz jego twórczym rozwinięciem dzięki mechanizmowi samoczynnej adaptacji zasięgu mutacji, zastępującemu regułę 1/5 sukcesów. Wprowadzono także operator krzyżowania.
procedurę Strategia ewolucyjna (^ 4- A) begin
t := 0
inicjacja P*
ocena P*
while (not warunek stopu) do
begin
T* := reprodukcja P* O* := krzyżowanie i mutacja T4 ocena O*
P*+1 := fj, najlepszych osobników z P* U O* t := t + l end end
RYSUNEK 2.12. Schemat strategii ewolucyjnej (p. + A)
.86.
2. Podstawowe typy algorytmów ewolucyjnych
W strategii (fj, + A) przetwarzana jest bazowa populacja P* zawierająca fj, osobników o specjalnej strukturze (omówionej poniżej). Z populacji tej generuje się populację potomną O*, zawierającą A osobników. Proces generowania reprodukcja przebiega w następujący sposób: wielokrotnie powtarza się losowanie (ze zwracaniem) osobnika spośród fj, osobników z P*, a następnie umieszcza się jego kopię w populacji pomocniczej T*.
Utworzoną w ten sposób populację pomocniczą poddaje się operacjom genetycznym: krzyżowaniu i mutacji (więcej na ich temat poniżej). Utworzona w wyniku operacji genetycznych populacja O* zostaje połączona ze starą populacją bazową. Nową populację bazową tworzy fj, najlepszych osobników wybranych spośród fj, + X znajdujących się w złączeniu populacji PL U O' (stąd pochodzi nazwa strategii).
Kodowanie osobników i operacje genetyczne. Osobnik
w strategii (fj, + A) ma strukturę składającą się z dwóch chromosomów. Pierwszym z nich jest wektor X wartości zmiennych niezależnych, natomiast drugim jest najczęściej wektor a, zawierający wartości standardowych odchyleń wykorzystywanych podczas mutacji.
Mutacja przebiega trójetapowo. Na początku losowana jest wartość zmiennej losowej o jednowymiarowym standaryzowanym rozkładzie normalnym; oznaczmy ją ^jv(o,i)- Następnie, dla każdego elementu wektora cr dokonuje się realizacji zmiennej losowej o rozkładzie normalnym (oznaczmyją Lw(o,i),i) i wykonuje modyfikację wartości standardowych odchyleń osobnika
o := ai exp
Wartości
r i r
(2.14)
są parametrami algorytmu. Mają one wpływ na
szybkość zbieżności strategii ewolucyjnej; ich zalecane wartości
wynoszą* - ,. ., .
T ~~~
2n K
T =
(2.15) (2.16)
W trzecim kroku zmodyfikowane wartości standardowych odchyleń są wykorzystywane do mutacji wartości zmiennych niezależnych. W tym celu, dla każdego genu chromosomu X realizuje się ponownie zmienną losową o rozkładzie normalnym i dodaje *Te zaiecane wartości poprawkę pomnożoną przez odpowiednią wartość standardowego
wyprowadzonoanalitycznie j i i �
dlamodelu sferycznego i odchylenia
potwierdzono eksperymen-
tami dla innych funkcji te- v/ .= X + /L , (2.17)
5towych. * i^>jv^u,i;,i -, j, , \ i
2.2. Strategie ewolucyjne
.87.
Niezwykle istotny jest fakt, że podczas mutacji X wykorzystuje się już nowe wartości o^. Mechanizm ten, w powiązaniu ze schematem generowania nowej populacji bazowej, ma na celu umożliwienie samoczynnej adaptacji zasięgu mutacji, tak aby minimalizować wartość oczekiwaną czasu dojścia do maksimum globalnego funkcji przystosowania. Różnica między adaptacją, wprowadzoną w strategii (1 + 1), a samoczynną adaptacją polega na tym, że w pierwszym przypadku z góry znana jest pożądana wartość wielkości, charakteryzującej mutację (liczba sukcesów); odchylenie od tej wartości powoduje podjęcie znanych kroków korygujących*. W drugim przypadku, nie są narzucone żadne wymagania co do wartości cr, ich modyfikacjajest losowa, natomiast efekt adaptacji jest konsekwencją mechanizmu selekcji, premiującego lepsze osobniki, a zatem takie, które w wyniku mutacji stały się lepsze od rodziców.
W pierwszych strategiach ewolucyjnych nie wykorzystywano krzyżowania; we współczesnych strategiach operator ten jest obecny pod nazwą rekombinacja. Najczęściej używa się operatora polegającego na uśrednianiu lub na wymianie wartości wektorów X i o^ chromosomów macierzystych. Powstają w ten sposób dwa chromosomy potomne, zastępujące swoich rodziców. Przykładem może być schemat, w którym geny chromosomów X i a podlegają uśrednianiu ze współczynnikiem wylosowanym z rozkładu jednostajnego:
a = &7(0,1)
X'1 = oX* + (l-a)X2 X'2 = oX2 + (1 - a)X1 cr'1 = ao^ + (l-a)cr2 a'2 = acr2 + (1 - a)cr1
(2.18) (2.19) (2.20) (2.21) (2.22)
2.2.3. Strategia (^, A)
Strategia ewolucyjna (^i + A), mimo znaranej odporności ma minima lokalne i samoczynnej adaptacji zasięgu mutacji, nie jest wolna od wad. Samoczynna adaptacja zasięgu mutacji nie zawsze działa w sposób zgodny z oczekiwaniami. Problemy mogą powstawać wówczas, gdy w populacji znajdzie się przez przypadek osobnik o wyróżniającej się wartości funkcji przystosowania, lecz zdecydowanie nieodpowiednich (na przykład zbyt dużych lub zbyt małych) wartościach odchyleń standardowych. Osobnik ten nie zostanie usunięty z populacji dopóty, dopóki nie zostanie znaleziony inny, o większej wartości funkcji przystosowania. Jednakże,
� � u -i i l \ i u J u 'T- *Jesttoregutal/5sukce-
ponieważ osobnik ten wpływa na potomstwo, będąc osobnikiem Sów.
.88.
2. Podstawowe typy algorytmów ewolucyjnych
procedurę Strategia ewolucyjna (^, A) begin
t := 0 �>'���'
inicjacja P(
ocena P*
while (not warunek stopu) do
begin
T' := reprodukcja Pf O* := krzyżowanie i mutacja T* ocena O*
Pt+1 := p, najlepszych osobników z Of t := t + 1 end end
RYSUNEK2.13.Schematstrategiiewolucyjnej(^,A)
rodzicielskim, jego wartości odchyleń standardowych są w ten sposób powielane i utrwalane w populacji, to zaś utrudnia znalezienie osobników lepszych. Wytwarza się więc niepożądane sprzężenie zwrotne, które utrudnia działanie algorytmu.
Zapobieżenie powyższym problemom było motywacją wprowadzenia schematu strategii ewolucyjnej (p-,\) (rys. 2.13). Schemat ten różni się od (/^ + A) jedynie tym, że nowa populacja bazowa jest tworzona wyłącznie na podstawie A osobników potomnych z populacji Of osobniki rodzicielskie ulegają więc zapomnieniu. W ten sposób każdy osobnik "żyje" dokładnie jedną generację, podczas gdy schemat (p, + X) pozwalał na dowolnie długie przetrzymywanie osobnika w populacji bazowej.
2.2.4.Analizadziałaniastrategii ,O
Zbieżność asymptotyczna. Działanie strategii ewolucyjnych wynika przede wszystkim z istnienia mechanizmów mutacji i selekcji. Ponieważ zakłada się, że podczas mutacji wykorzystywany jest rozkład normalny o niezerowej wartości odchylenia standardowego i zerowej wartości oczekiwanej (charakteryzujący się tym, że wartość funkcji gęstości prawdopodobieństwa jest większa od zera dla dowolnego skończonego argumentu), dowolny punkt przestrzeni Rn może zostać osiągnięty w każdym kroku. Dzięki temu, dla strategii ewolucyjnej (1 + 1) (a co za tym idzie, również dla p, + A) można sformułować następujące twierdzenie o zbieżności prawie na pewno. j
2.2. Strategie ewolucyjne
.89.
Poszukiwane maksimum globalne funkcji przystosowania oznaczmy X*, a zbiór poziomicowy funkcji przystosowania L$(a) = = {X � L>|5>(X) > a}. Niech X(t) = argmaxXeP, $(X). Jeśli
1) istnieje a > 0 takie, że
V6 < a Ls>(<&(X*) 6) jest niezerowej miary
(2.23)
2) X* nie należy do brzegu zbioru D,
3) zachodzi |X*| < 00 i $(X*) < oo,
4) stosujemy strategię ewolucyjną (y, + A),
5) stosujemy mutację każdego genu według wzoru X[ = Xi +
6) istnieje amin > 0 takie, że a{ > amin,
to dla dowolnej populacji początkowej P� takiej, że
VX e P� |X| < 00
i dla każdego e > 0 zachodzi
(2.24)
(2.25)
Twierdzenie to można udowadniać różnymi sposobami. W literaturze przeważnie korzysta się z twierdzenia Borela-Cantellego o zbieżności ciągu zdarzeń losowych. Istnieje też dowód korzystający z dowodu zbieżności strategii (1 + 1), która z kolei jest szczególnym przypadkiem algorytmu symulowanego wyżarzania (z zerową temperaturą).
Strategia ewolucyjna (yn, A) nie ma dowodu zbieżności. Wynika to z faktu, że osobniki rodzicielskie są zawsze zapominane, niezależnie od tego, czy ich potomstwo jest lepiej przystosowane. Może się jednak zdarzyć, że zbiór poziomicowy, zawierający eks-tremum globalne, zostanie "odwiedzony"* przez algorytm (bez gwarancji pozostania). W stosunku do twierdzenia o zbieżności strategii (n+\) należałoby zmodyfikowaćjedynie konkluzję twierdzenia, która mogłaby brzmieć, że dla dowolnej populacji początkowej P� takiej, że
vxeP
0
|X|(2.26)
i dla każdego L > 0 zachodzi
lim Prob{3r � {0,1,..., t} X(r) � L$($(X*) - e)} =
/c\ f v "
......
t 00 *To znaczy, ze w wyniku
działania algorytmu zósta-nie wygenerowany chromosom zawarty w tym zbio-
czyli, że do jedności dąży prawdopodobieństwo odwiedzenia choć rze poziomicowym {chro-raz zbioru poziomicowego dowolnie bliskiego maksimum global- ^tte^u^nrVSL
nemu funkcji przystosowania.
bazowej).
.90.
2. Podstawowe typy algorytmów ewolucyjnych
Gdyby więc nad strategią ewolucyjną (p, A) "czuwał" monitor*, który zapamiętywałby najlepsze dotychczas znalezione rozwiązanie, to można by udowodnić zbieżność (prawie na pewno) takiego algorytmu hybrydowego.
Zauważmy, że zbieżność strategii ewolucyjnej ma charakter asymptotyczny i probabilistyczny. Właściwość taka, choć ważna, nie jest specjalnie pożyteczna, gdyż nie da się z niej wyprowadzić efektywnego kryterium zatrzymania ani np. zaleceń ustawienia wartości parametrów algorytmu. Wada ta jest wynikiem bardzo słabych założeń o funkcji przystosowania. Zaletą twierdzenia o zbieżności strategii ewolucyjnych, zwłaszcza w porównaniu z twierdzeniem o schematach, jest przede wszystkim konkretność wyniku, jak również brak założeń o nieskończonej liczności populacji bazowej. Zwróćmy też uwagę na fakt, że w twierdzeniu o zbieżności nie zakłada się istnienia operatora krzyżowania ani żadnego dolnego ograniczenia liczności populacji bazowej czy potomnej**.
2.2.5. Symulacja działania strategii
Prześledźmy działanie strategii (^,A) i (^i + A). Szczególną uwagę zwrócimy na zmiany w kolejnych generacjach wartości standardowych odchyleń wykorzystywanych podczas mutacji.
Do testów będzie służyć 30-wymiarowa funkcja Ackleya (patrz dodatek B1). Funkcja przystosowania będzie równa <&(X) = -/(x),ponadtox = X. .,,. - ,/
o
-10
-12
-14
-16
-18
-20
-22
10
*Jest to proces monitorujący działanie algo-rytmu ewolucyjnego (anali-zującywygenerowanechro-mosomy), lecz nie ingerujący w \eeo działanie.
zatezeniem^ze''T">'T dla bazowych strategii ewolucyjnych ^ > i ~
100
1000
_ � - , ~ , . .
RYSUNEK 2.14. Przebieg zmian w
dla bazowych strategii ewolucyjn mają identyczną populację bazową
. . . . ,
czasie maksimum przystosowania w populacji
(p + A) i (p,A); obie strategie w chwili t = 0
Hy/iij-,1 ...;!i>v -->~>i'i 2.2. Strategie ewolucyjne
.91.
100 200 300 400 500 600 700 800 900 1000
lb
(a)
100 200 300 400
500 t
600 700 800 900 1000
(b)
RvsuNEK 2.15. Przebieg zmian w czasie odległości wartości średniej genotypów populacji od genotypu będącego maksimum globalnym (a) oraz wartości średniej normy wektora standardowych odchyleń, używanych podczas mutacji (b); strategia ewolucyjna
.92.
2. Podstawowe typy algorytmów ewolucyjnych
Pojedynczy przebieg. Rozważmy pojedyncze uruchomienie strategii ewolucyjnej bez operatora krzyżowania (jedynym operatorem genetycznym jest mutacja). Pozwólmy także na długotrwale działanie algorytmu, aby móc zaobserwować charakter zbieżności. Będziemy badać strategię (/x+A) (dla // = 50, A = 200) oraz strategię (fj,, A) (dla ^ 50, A = 300)*. Oba algorytmy będą zatrzymywane wówczas, gdy numer generacji przekroczy 1000. Prześledzimy charakter zmienności wartości maksimum przystosowania w populacji bazowej (rys. 2.14).
Łatwo zauważyć odmienny charakter zmienności średniej wartości przystosowania dla obu odmian strategii ewolucyjnej. Dla strategii (^ + A) obserwuje się miarowy wzrost wartości maksymalnej, również średniej i minimalnej, strategia (^,A) zaś ma bardziej "gwałtowny" charakter zmian.
Przyjrzyjmy się zmianom wartości |\a\ =
1 L
* ^V \ ^-1
(X,cr)eP*
(2.28)
W czasie działania strategii ewolucyjnej obserwuje się zdecydowaną tendencję spadkową wartości |*Wartości /t, A są zbliżone dozalecanych
2.3. Programowanie ewolucyjne
Ewoluujące automaty. Twórca programowania ewolucyjnego, Lawrence Fogel, zamierzał modelować proces powstawania sztucznej inteligencji na drodze samoczynnej organizacji. W tym celu rozważał problem odkrywania gramatyki nieznanego języka, gdy znany jest zestaw jego symboli i dane są przykłady wyrażeń syn-taktycznie poprawnych. Gramatyka była modelowana za pomocą automatu skończonego (rys. 2.16), którego zbiór stanów, funkcja przejść i funkcja wyjść były przedmiotem poszukiwań.
Funkcja przystosowania osobnika automatu skończonego polega na określeniu liczby prawidłowych klasyfikacji (jako po-
r e> J f J J J VJ f
prawnych syntaktycznie) wyrazen poznawanego języka. Usobmk
ri~>v.>;K >;icws 2.3. Programowanie ewolucyjne
.93.
O/a
l/a
l/b
l/a
l/a
RYSUNEK 2.16. Automat skończony przedstawiony w postaci grafu. Stanami są węzły grafu, krawędzie zaś opisują przejścia między stanami. Każde przejściejest spowodowane wczytaniem symbolu wejściowego przez automat i powoduje wygenerowanie symbolu wyjściowego; oba symbole są podane w sąsiedztwie odpowiedniej krawędzi
ii .,�-: '.' (t :
automat skończony może podlegać ewolucji, która w przypadku programowania ewolucyjnego polega wyłącznie na dokonywaniu mutacji. Rozważane przez Fogela rodzaje mutacji były następujące:
dodanie stanu,
usunięcie stanu,
zmiana stanu początkowego,
zmiana funkcji wyjść,
zmiana funkcji przejść.
Wyniki prac byly wprawdzie zachęcające obserwowano uczenie się automatów, jednakże programowanie ewolucyjne w swojej pierwotnej formie nie stało się popularne.
W stronę strategii ewolucyjnych. Dopiero lata 80. przyniosły ponowne zainteresowanie programowaniem ewolucyjnym, które uległo znacznym zmianom upodabniającym je do strategii ewolucyjnych. Modyfikacje dotyczyły przede wszystkim dziedziny zastosowań schemat programowania ewolucyjnego został rozwinięty przez Davida Fogela w kierunku optymalizacji numerycznej. Jego wkład polegał na wprowadzeniu reprezentacji rzeczywistoliczbowej i dostosowanego do niej operatora mutacji, wykorzystującego nieskorelowany wielowymiarowy rozkład normalny o zerowej wartości oczekiwanej. Fogel wzbogacił genotyp osobnika o chromosom, zawierający wektor cr standardowych odchyleń (po jednej wartości dla każdej zmiennej niezależnej) i wprowadził mechanizmy modyfikacji tego zasięgu.
2. Podstawowe typy algorytmów ewolucyjnych
2.3.1. Schemat programowania
Algorytm programowania ewolucyjnego przedstawiono na rys. 2.17. Przetwarzana jest populacja Pf, zawierająca p, osobników. W jednym kroku algorytmu każdy osobnik tworzy jednego potomka, który jest poddawany mutacji. W ten sposób* powstaje populacja potomna O* o liczności A = fi. Po obliczeniu wartości
procedurę Programowanie ewolucyjne i
begin t := 0
inicjacja P* ' ,
ocena P* ; ,'
while (not warunekstopu) do '"*'-,
begin
O* := 0 x .....^
foreach (X e P*) do begin
Y := mutacja X
O* := O* U {Y}
end ,
ocena O*
foreach (X e P* U O*) do
begin
wyznacz r(X)
i
end
p4+1 := wybór najwyższych rangą z P* U O* end y !���:
end
RYSUNEK 2.17. Schemat programowania ewolucyjnego
*Zwróćmy uwagę na różnicę w stosunku do strategii ewolucyjnej. W programowaniu ewolucyjnym, każdy osobnik będzie miał dokładniejedną kopię, podczas gdy w strategii ewolucyjnej każdy reprodukujący osobnik będzie miałjedna-kową wartość oczekiwaną liczby kopii.
przystosowania osobników z populacji potomnej, tworzona jest nowa populacja bazowa w następujący sposób: dla każdego osobnika (zarówno populacji bazowej, jak i potomnej) określa się jego rangę, a następnie wybiera do nowej populacji bazowej te osob-niki,ktorychrangajestnajwyzsza. t_ ,
Metoda określania wartości rang. Wartość rangi wyznacza się w następujący sposób. Dla każdego osobnika X dokonuje się losowania podpopulacji Q C (P* U O* \ {X}), zawierającej q osobników. Ranga osobnika r(X) jest równa liczbie osobników z Q
2.3. Programowanie ewolucyjne
.95.
o przystosowaniu mniejszym od niego ||{YeQ|S(X)>*(Y)}||
(2.29)
Wyznaczone w ten sposób wartości rang decydują o przejściu osobnika do nowej populacji bazowej. Osobniki o największej wartości przystosowania w P* U O* otrzymują z definicji rangę równą q*.
2.3.2. Operatory mutacji
Mutacja osobnika polega na perturbacji wartości zmiennych niezależnych. Istnieją trzy wersje mutacji; różnica między nimi polega na sposobie modyfikacji zasięgu tej perturbacji.
Brak adaptacji. Mutacji dokonuje się poprzez dodanie do genotypu osobnika wartości zmiennej losowej o wielowymiarowym nieskorelowanym rozkładzie normalnym
Xi +
i),i ..' (2.30)
gdzie współczynniki o^j są parametrami algorytmu (dla n genów możemy mieć n różnych wartości Oi bądź też jedną wspólną wartość; wówczas cTj = a dla każdego i).
Adaptacja poprzez śledzenie wartości funkcji przystosowania. Kolejna wersja programowania ewolucyjnego, określana jako standardowa, polega na uzależnieniu stopnia mutacji osobnika od wartości funkcji przystosowania. Nowa wartość genu jest tworzona na podstawie starej w następujący sposób:
v'_ v
A-4 ^i
- <&(X))
(2.31)
gdzie 0 oraz 7 są arbitralnie wybieranymi parametrami algorytmu**, 3>max zaś jest oszacowaniem wartości funkcji przystosowania w maksimum globalnym. Mechanizm ten prowadzi do zmniejszania stopnia mutacji osobnika w miarę zbliżania się do szacowanej wartości maksimum globalnego. Parametr 7 pozwala na ograniczenie od dołu wartości wariancji zmiennej losowej wykorzystywanej podczas mutacji, f3 zaś wpływa na szybkość zmian tej wariancji wraz ze zbliżaniem się wartości przystosowania osob- *Zwróćmy uwage, że nika do oszacowania wartości funkcji przystosowania w maksimum ^ukcjHsTkces^progra^
globalnym. mowanie ewolucyjne można
zaliczyć do algorytmów � 1 , . . T~ T . . ewolucyjnych dzieki loso-
Samoczynna adaptacja zasięgu. Kolejna wersja programo- wości wyboru PodPoPuia-
wania ewolucyjnego (nieta-EP), zawiera mechanizm samoczyn- <=J'<3.
nej adaptacji zbliżony do znanego już ze strategii ewolucyjnych. *7''^Tostu'^=TT
Wartości odchyleń standardowych crj wykorzystywanych podczas 7 = o.
. 96 _____ 2. Podstawowe typy algorytmów ewolucyjnych
mutacji poszczególnych genów osobnika zostają zapisane w tym osobniku i podlegają wraz z nim ewolucji. Mutacja przebiega według następującego schematu: najpierw modyfikowane są wartości genów odpowiadających za przystosowanie osobnika
X'i = Xi +
a następnie wartości odchyleń standardowych
mn
(2.32)
(2.33)
gdzie C jest parametrem sterującym intensywnością zmian &{. Zauważmy, że (odmiennie niż w strategiach ewolucyjnych) modyfikacja standardowego odchylenia następuje przez dodanie wartości losowej, a nie wymnożenie przez nią5.
2.4. Programowanie genetyczne
2.4.1. Programy, które powstają samoczynnie
Programowanie genetyczne jest stosunkowo nowym kierunkiem rozwoju algorytmów ewolucyjnych. Powstało jako pewna szczególna gałąź algorytmów genetycznych o silnie rozwiniętych strukturach danych.
Pierwotnie, programowanie genetyczne było próbą znalezienia sposobu automatycznego generowania tekstów programów, gdy znane były kryteria oceny prawidłowości działania. Jako bazowego języka programowania użyto języka LISP, w którym program jest reprezentowany w identyczny sposób jak dane w postaci drzewa. W ten naturalny sposób kodowanie binarne (rozpowszechnione w algorytmach genetycznych) zastąpiono drzewiastym, przy czym w węzłach drzewa znajdują się wielkości niebi-narne symbole pewnego alfabetu lub wartości liczbowe, zarówno dyskretne, jak i ciągłe; dopuszczalne są wartości stałe, zmienne lub funkcje. Założenie takie pociągnęło za sobą konieczność zdefiniowania operatorów genetycznych, uwzględniających specyfikę wprowadzonej metody kodowania, modyfikujących zarówno wartości w węzłach drzewa, jak również jego strukturę.
5Badacze z kręgu programowania ewolucyjnego przyznają, że postępowanie wedlug takiego schematu mutacji, jak w strategiach ewolucyjnych, prowadzi do szybszej samoczynnej adaptacji. Jednakże nie należy pomijać faktu, że reprodukcja w strategiach ewolucyjnych jest bardziej "rozrzutna" (typowo jeden osobnik rodzicielski tworzy kilku potomków), a zatem można pozwolić na ,/marnowanie" (wskutek niefortunnej zmiany standardowego odchylenia) części szans na wygenerowanie dobrych osobników, licząc że strata ta zostanie wyrównana poprzez lepszą samoczynną adaptację zasięgu mutacji.
2.4. Programowanie genetyczne
.97.
Dosyć szybko zauważono, że automatyczne pisanie programów nie jest jedyną grupą problemów, w której znajduje zastosowanie drzewiasta reprezentacja danych. Problemami tymi mogą być zadania, w których oprócz wartości parametrów optymalizacji podlega struktura ich powiązań. Przykładem może być zadanie syntezy drzewa decyzyjnego, projektowanie układów elektronicznych, regresja symboliczna i wiele innych. Obecnie, termin "programowanie genetyczne" jest niekiedy używany do określenia algorytmów ewolucyjnych wykorzystujących drzewiastą reprezentację zadania i modyfikujących strukturę tej reprezentacji.
2.4.2. Kodowanie drzewiaste
Chromosom jest kodowany jak drzewo składające się z węzłów i krawędzi. Informacjajest zawarta w węzłach, krawędzie zaś określają wzajemne relacje między węzłami. Jeśli krawędź jest skierowana od węzła A do węzła B, wówczas A jest nazywany nadrzędnym, B zaś podrzędnym.
W zależności od położenia węzła w drzewie, mówimy o węzłach terminalnych (takich, które nie mają węzłów podrzędnych) oraz pośrednich (nieterminalnych). Istnieje dokładnie jeden węzeł nie mający nadrzędnego, nazywany korzeniem drzewa.
W węzłach terminalnych znajdują się elementy, które są atomiczne* z punktu widzenia programowania ewolucyjnego. Mogą być nimi wartości stałe, zmienne lub funkcje bezparame-trowe. Węzły pośrednie odpowiadają funkcjom lub operatorom, które zwracają dokładnie jedną wartość i mogą przyjmować jeden lub więcej argumentów. Argumenty te są, w zależności od struktury drzewa, albo wartościami węzłów terminalnych, albo wartościami zwracanymi przez inne funkcje określone przez odpowiednie poddrzewa.
setq
delta
_ ^,n n � i � *Elementyatomicznetota-
RYSUNEK 2.18. Reprezentacja drzew,a- kje któryych stmktur3 we_
stawyrażenia (setq (delta -( *(b b) wnętrzna nie jest modyfi-
*(4 * (a c))))) kowana.
.98.
2. Podstawowe typy algorytmów ewolucyjnych
PRZYKŁAD. Zapis wjęzyku LISPfunkcji obliczającejpierwiastki rzeczywiste równania kwadratowego ax2 + bx + c = 0 jest następujący:
(defun pierwiastki (a b c)
( (setq (delta -( *(b b) *(4 * (a c))))) (if<(delta 0)
(setq n 0) " ,,
) '. , � � >
(if=(delta 0) ;., , �. ; , .. �.
( (setq n 1)
(setq xl ( /(-b)(* (2 a))))
) ,...,- = ,' L<
(if>(delta 0) ( (setq n 2)
(setq xl ( /((-( -b sqrt(delta) )(* (2 a)))))) (setq x2 ( /((+( -b sqrt(delta) )(* (2 a))))))
Funkcji tej odpowiada dość rozbudowane drzewo, którego fragment (związany z określeniem wartości zmiennej deltaj przedstawiono na rys. 2.18. _ ,
2.4.3. Operatory genetyczne
Zarówno zestaw wartości stałych, zmiennych, jak i rodzajów dostępnych funkcji jest ustalany z góry. Zadaniem algorytmu genetycznego jest takie poskładanie z tych elementów drzewa chromosomu, które pozwala uzyskać jak najlepszy program. W tym celu należy określić operatory genetyczne, przekształcające drzewa.
W podstawowym wariancie algorytmu mutacja polega na zmianie zawartości wybranego losowo węzła, w wyniku czego (rys. 2.19):
zawartość węzła terminalnego zostanie zmieniona, węzeł zaś pozostanie nadal terminalny,
zamiast węzła terminalnego zostanie wstawiony węzeł pośredni 7, losowo wygenerowanym poddrzewem,
węzeł pośredni wraz z całym swoim poddrzewem zostanie zamieniony na terminalny,
węzeł pośredni ze swoim poddrzewem zostanie zamieniony na inny, z losowo wygenerowanym poddrzewem, nastąpi reorganizacja poddrzew węzła pośredniego.
T3 T3 O
CL
a
!
m
c
O
bO
L S
N >
^ !
� -s?
." o
E �-
O^ ra SP S?
H | u
O) N ftl
r c
II
nj ^o 5 o
05 Q.
|E
..
C ^
l.ą
.2 E
z E
ce u
.100.
2. Podstawowe typy algorytmów ewolucyjnych
Zauważmy, że w czterech z pięciu wymienionych przypadków ma miejsce zmiana strukturalna w chromosomie może się on rozrastać, kurczyć lub zmieniać kształt.
Krzyżowanie jest wykonywane dla pary chromosomów rodzicielskich i prowadzi do powstania pary chromosomów potomnych. Z każdego z chromosomów rodzicielskich wyodrębniany jest losowo wybrany węzeł pośredni (wraz ze swoim poddrzewem) lub terminalny. Chromosomy potomne powstają w wyniku zamiany powstałych poddrzew (rys. 2.20).
(b)
RYSUNEK 2.20. Krzyżowanie w kodowaniu drzewiastym zamiana wyciętych poddrzew: chromosomy rodzicielskie (a), chromosomy potomne (b)
Wykorzystanie powyższych operatorów daje dużą dowolność zarówno struktury powiązań w drzewie, jak też liczby węzłów. Często zdarza się, że perfekcyjne rozwiązanie jest nadmiernie skomplikowane, gdyż zawiera zbyt wiele węzłów lub ma nieodpowiednią strukturę. Aby temu przeciwdziałać, wprowadza się dodatkowe mechanizmy zabezpieczające. Sam problem, jak i wzmiankowane mechanizmy, omówiono dokładniej w podrozdziale poświęconym kodowaniu drzewiastemu (w III części książki).
2.5. Uwagi bibliograficzne
.101.
2.5. Uwagi bibliograficzne
Prosty algorytm genetyczny wprowadził Holland [35] i upowszechnił Goldberg [31]. Również Michalewicz [54] rozpoczął prezentację algorytmów ewolucyjnych od opisu działania prostego algorytmu genetycznego. W podręcznikach tych zakłada się, że chromosom jest łańcuchem binarnym kodującym (z precyzją zależną od liczby bitów) wektor liczb rzeczywistych, na podstawie którego oblicza się przystosowanie osobnika*. Kolejne uproszczenie dotyczy prezentacji działania operatorów genetycznych. Autorzy często dobierają przykłady w taki sposób, że wynikiem każdej operacji genetycznej (krzyżowania i mutacji) jest poprawa wartości średniej przystosowania osobników. W przypadku wielu funkcji (zwłaszcza tych trudniejszych) nie jest to prawdą: krzyżowanie i mutacja prowadzą najczęściej do pogorszenia średniej wartości przystosowania, w zamian wprowadzając zróżnicowanie do populacji bazowej ("przy okazji" może zostać znaleziony chromosom lspiej przystosowany niż wszystkie inne sprawdzone w poprzednich generacjach).
Teoria schematów pierwsza próba wyjaśnienia działania algorytmu genetycznego [31, 35] jest uważana bardziej za próbę uzasadnienia przydatności operatora krzyżowania niż pełnowartościową teorię. Obecnie powszechniejsze jest wykorzystanie modelu algorytmu jako procesów Markowa i dowodzenie jego zbieżności w oparciu o te procesy [107].
Strategie ewolucyjne są omówione dość szczegółowo w książkach Schwefela [93] i Backa [6]. W tej ostatniej można również znaleźć wyczerpujący opis programowania ewolucyjnego, a także porównanie tych trzech podstawowych typów algorytmów ewolucyjnych. Back poświęca również sporo miejsca teorii algorytmów ewolucyjnych. Programowaniu ewolucyjnemu w "nowoczesnej" wersji poświęcona jest w całości praca [23].
Interesująca może być też lektura książki [13]. Jest to kolekcja artykułów napisanych przez przedstawicieli różnych trendów w tworzeniu algorytmów ewolucyjnych: można się na przykład zapoznać z argumentacją zwolenników i przeciwników traktowania krzyżowania jako użytecznego operatora genetycznego.
W pracy [33] można znaleźć omówienie pierwszej wersji programowania ewolucyjnego (z osobnikami automatami skończonymi) wraz z przykładowymi zastosowaniami.
Czytelnik zainteresowany dokładniejszymi informacjami na temat programowania genetycznego powinien sięgnąć do pozycji [40] omówiono tam dokładnie zarówno podejście z ewoluującymi programami w iezyku LISP, iak również przykłady zastoso- " ,, ,.
^ *� � Jx J ' J * J J *Poprawnosc takiego po-
wania kodowania drzewiastego w połączeniu z algorytmami gene- stepowania jest wątpliwa tycznymi.
(patrz wykład 4).
, 102 _____ 2. Podstawowe typy algorytmów ewolucyjnych
2.6. Pytania i ćwiczenia
1. Czy algorytm genetyczny, posługujący się wyłącznie operatorem krzyżowania (bez mutacji), jest w stanie odnaleźć maksimum globalne funkcji przystosowania? Czy posługiwanie się samą mutacją (bez krzyżowania) może do tego doprowadzić?
2. Czy w strategii ewolucyjnej (^ + A) możliwejest zajście zdarzenia, w którym średnie przystosowanie osobników w populacji pt+i jeSL niższe niż w populacji P*? Czy to samo można powiedzieć o strategii (^,A)?
3. Ile obliczeń wartości funkcji przystosowania potrzeba do symulacji k pokoleń za pomocą: a) algorytmu genetycznego, którego populacja bazowa zawiera fj, osobników, b) strategii ewolucyj-
. nej ((j, + A) i (^, A), c) programowania ewolucyjnego przy licz-1 ności populacji bazowej ^?
4. Czy mechanizm selekcji w programowaniu ewolucyjnym jest ... tożsamy z wykorzystywanym w strategiach ewolucyjnych me-x: chanizmem (^t + ^i)? Czy selekcja w algorytmach genetycznych
da się zapisać jako (^i,/^)?
5. Jaki rozkład prawdopodobieństwa mają zmutowane wartości wektora standardowych odchyleń cr' w schemacie wykorzystywanym w strategii ewolucyjnej, a jaki w programowaniu ewolucyjnym? Czy w obu przypadkach wartością oczekiwaną wek-torao^'jestcr(wektorsprzedmutacji)? , .,, ,
6. Jaki wpływ na adaptację zasięgu mutacji w programowaniu ewolucyjnym będzie miało przyjęcie zbyt małej wartości