4
ALGORYTMY EWOLUCYJNE
Przetwarzanie ewolucyjne za pomocą algorytmów genetycznych (GA) [1, 11, 19, 20, 21 22,
24, 74, 92, 97, 100] stanowi najbardziej znaną metodę optymalizacji stochastycznej. Jedną z
cech charakterystycznych algorytmów genetycznych jest prowadzenie poszukiwań w wielu
punktach. W procesie przetwarzania ewolucyjnego parametry zadania optymalizacji posiadają
postać zakodowaną, a do wyboru i tworzenia nowych rozwiązań stosuje się reguły
ewolucyjno-probabilistyczne. Skuteczność metod ewolucyjnej optymalizacji związana jest z
wykorzystywaniem łatwo obliczalnych wartości funkcji celu. Metody te wolne są od
ograniczeń nakładanych na przestrzeń poszukiwań (np. ciągłość), istnienie pochodnych oraz
unimodalność funkcji celu itp. Wynikająca z tego uniwersalność i prostota implementacyjna
stanowią podstawę użyteczności algorytmów ewolucyjnych.
4.1.
Podstawowe pojęcia
Przy charakteryzowaniu algorytmów genetycznych stosuje się słownictwo zapożyczone z
genetyki [2]. Poszukiwane w postaci zbioru parametrów rozwiązanie zadania
wielowymiarowej optymalizacji nazywane jest osobnikiem. Algorytmy genetyczne operują
na zbiorze osobników zwanym populacją. Każdy osobnik posiada strukturę, którą opisuje
(omówiony dalej) genotyp zawierający stałą liczbę chromosomów. Odpowiednio
zakodowana informacja genetyczna zawarta w chromosomach wykorzystywana jest przez
procedury (ewolucyjne) realizowane w algorytmach genetycznych. Ponadto każdy osobnik
posiada fenotyp, będący wynikiem procesu dekodowania genotypu
− w celu wyznaczania
stopnia przystosowania osobnika do środowiska reprezentowanego zadaną wektorową
funkcją celu. W algorytmach genetycznych osobniki zwykle posiadają genotyp złożony z
jednego lub dwóch chromosomów. Osobnika, który posiada parę chromosomów, nazywa się
osobnikiem diploidalnym, zaś osobnik z pojedynczym chromosomem nazywa się
osobnikiem haploidalnym. Ten ostatni osobnik utożsamiany jest zatem z chromosomem.
Ogólną strukturę populacji złożonej z N osobników n-ploidalnych przedstawiono na rys. 4.1.
18
4. Algorytmy ewolucyjne
Rys. 4.1.
Ogólny model populacji osobników podlegających ewolucyjnej optymalizacji.
Rys. 4.2.
Model chromosomu stosowanego w algorytmach genetycznych.
W chromosomie parametry zadania optymalizacji reprezentowane są jako sekwencja
genów, będących wielkościami (symbolami) opisującymi w sposób zakodowany określony
parametr. Budowę takiego chromosomu przedstawia schematycznie rys. 4.2, gdzie gen jest
zdefiniowany jako podstawowy element chromosomu posiadający określoną pozycję (locus)
w sekwencji chromosomu oraz przybierający określone wartości, nazywane odmianami lub
allelami (symbolizowanymi różnymi kolorami wypełniającymi kwadraty).
W algorytmie genetycznym dana populacja osobników podlega symulowanej ewolucji.
Oznacza to, że w każdej iteracji algorytmu „dobre” rozwiązania reprodukują się (przenoszą
19
swój materiał genetyczny do nowego pokolenia), a „złe” nie (wymierają). Nowa populacja,
uzyskiwana po każdej iteracji GA nazywana jest pokoleniem. Ocena przydatności
poszczególnych osobników, obliczana według funkcji kryterialnej, nazywana jest stopniem
przystosowania. Do określenia argumentów funkcji kryterialnej służy fenotyp, stanowiący
zdekodowaną postać parametrów zadania optymalizacji.
Realizacja procedur ewolucji w algorytmach genetycznych opiera się na doborze do
każdorazowej reprodukcji osobników według stopnia przystosowania (jako potencjalnie
ostateczne rozwiązania zadania optymalizacji). Wyselekcjonowana grupa osobników zwana
pulą rodzicielską (rodzicami) uzyskuje szansę udziału w generowaniu nowych osobników
zwanych potomkami poprzez zastosowanie operacji genetycznych. Do podstawowych
operacji genetycznych zalicza się krzyżowanie i mutację. Potomkowie powstający w wyniku
tych operacji w danym cyklu tworzą nowe pokolenie. W ten sposób realizowany ewolucyjny
cykl algorytmu genetycznego powtarzany jest do chwili, kiedy spełnione zostaje ustalone
kryterium zakończenia poszukiwań. Takim kryterium może być osiągnięcie odpowiedniej
liczby wygenerowanych pokoleń. Kodowanie parametrów, ocena stopnia przystosowania,
selekcja osobników oraz operacje genetyczne zostaną omówione w dalszej części niniejszego
rozdziału.
4.1.1.
Genotyp, fenotyp oraz przystosowanie osobnika
Załóżmy, że przeciwdziedziny poszczególnych współrzędnych wektora kryterialnego (2.2)
określone są na zbiorze liczb rzeczywistych dodatnich
+
ℜ
0
)
(
≥
∀
ℜ
∈
x
x
j
f
n
(4.1)
W algorytmach genetycznych funkcję celu
)
( x
j
f
o takiej własności nazywa się funkcją
przystosowania (ang. fitness function) [1, 19, 74, 88] lub stopniem przystosowania.
Natomiast wektor kryteriów nazywany jest wektorową funkcją przystosowania lub
wektorem stopnia przystosowania.
Przyjmijmy, że osobniki haploidalne określone są wektorami o postaci
[
]
ℵ
∈
=
=
n
N
i
v
v
v
i
i
i
n
i
,
,
,
2
,
1
,
T
2
1
…
…
v
(4.2)
których współrzędne (będące odcinkami chromosomu)
i
k
v
)
,
,
2
,
1
(
n
k
…
=
kodują wartości
poszczególnych współrzędnych
k
x
poszukiwanego wektora parametrów (2.1) zadania
maksymalizacji (2.1)
−(2.3), natomiast N oznacza liczbę osobników haploidalnych
(chromosomów) w populacji V reprezentowanej macierzą
[
]
N
v
v
v
V
…
2
1
=
(4.3)
Natomiast osobniki diploidalne, z parą chromosomów będą oznaczane jako macierz
dwukolumnowa
[
]
N
i
i
i
di
,
,
2
,
1
,
T
2
1
…
=
=
v
v
v
(4.4)
której kolumny oznaczają poszczególne chromosomy
[
]
N
i
i
i
di
,
,
2
,
1
,
T
2
1
…
=
=
v
v
v
(4.5)
20
4. Algorytmy ewolucyjne
[
]
N
i
i
i
di
,
,
2
,
1
,
T
2
1
…
=
=
v
v
v
(4.6)
zaś N oznacza liczbę osobników w populacji diploidalnej
[
]
dN
d
d
d
v
v
v
V
…
2
1
=
(4.7)
Niech fenotyp osobnika
i
v haploidalnego lub
di
v diploidalnego, będący zdekodowaną
postacią jego genotypu, ma następującą postać:
[
]
n
n
i
i
i
i
x
x
x
ℜ
∈
=
T
2
1
…
x
(4.8)
Wówczas wektorowy stopień przystosowania osobnika haploidalnego
i
v lub diploidalnego
di
v oznaczany jest następująco:
m
i
ℜ
∈
)
( x
f
(4.9)
4.2.
Kodowanie i dekodowanie parametrów
Do reprezentacji poszukiwanych parametrów zadania maksymalizacji w algorytmach
genetycznych najczęściej używa się kodu [19]:
• biallelicznego (binarnego) lub
• triallelicznego.
4.2.1.
Kod bialleliczny
Najwygodniejszym i najpowszechniej stosowanym sposobem kodowania osobników
haploidalnych w algorytmach genetycznych jest kod bialleliczny (binarny), w którym odcinki
(współrzędne
i
k
v
) chromosomu osobnika
i
v są skończonymi sekwencjami genów o allelach z
dwuelementowego zbioru liczb
}
1
,
0
{
. W czterowymiarowej przestrzeni o elementach
[
]
4
T
4
3
2
1
ℜ
∈
=
i
i
i
i
x
x
x
x
i
x
(4.10)
chromosom może przybierać na przykład postać
[
]
T
10111
00011011
0100111
0100111101
=
i
v
(4.11)
Jak widać sekwencje kodowe
i
k
v
danego parametru
i
k
x
mogą mieć różną długość, która
zależeć może od rodzaju zadania maksymalizacji oraz od wymaganej dokładności obliczeń.
Chromosom (4.11) składa się sekwencji binarnych, z których każdy ma długość odpowiednio
10, 7, 8 i 5 bitów (genów), zatem długość chromosomu wynosi 30 bitów (genów).
21
4.2.2.
Kod trialleliczny
Kod trialleliczny zwykle stosowany jest dla osobników diploidalnych, tzn. z genotypem
złożonym z pary chromosomów. Przy takim kodzie odcinki chromosomu są sekwencją
genów, których allele należą do trójelementowego zbioru liczb
}
1
,
0
,
1
{
−
. Przykładowo
osobnik diploidalny dla pewnej trójwymiarowej przestrzeni poszukiwań może mieć postać
T
T
2
1
1
1
0
1
0
1
1
1
0
1
0
1
1
0
1
0
1
1
−
−
−
−
−
=
=
d
d
di
v
v
v
(4.12)
Sekwencje trialleliczne poszczególnych odcinków (współrzędnych) pary chromosomów
osobnika (4.12) składają się odpowiednio z 3, 4 i 2 genów, zaś długość każdego z
chromosomów wynosi 9 genów.
4.2.3.
Dekodowanie parametrów
W procesie dekodowania informacji genetycznej zawartej w chromosomie kodowanym
binarnie na odpowiedni fenotyp, czyli wektor parametrów, należący do rzeczywistej
dziedziny zadania optymalizacji stosuje się proste odwzorowanie liniowe następującej
postaci:
N
i
n
k
v
x
x
x
x
k
ij
k
i
m
j
j
k
m
k
k
k
k
,
,
2
,
1
,
,
,
2
,
1
,
2
1
2
0
…
…
=
=
−
−
+
=
∑
=
(4.13)
gdzie
i
k
x
jest k -tą współrzędną wektora parametrów (2.1) i -tego osobnika haploidalnego,
przedział
[
]
ℜ
⊂
k
k
x
x
,
stanowi dziedzinę współrzędnych
i
k
x
, zaś
k
m
oznacza długość
sekwencji
i
k
v
kodującej tę współrzędną.
W przypadku kodu triallelicznego chromosomów osobnika diploidalnego, proces
dekodowania składa się z dwóch etapów. W pierwszym etapie stosuje się mechanizm
dominacji genetycznej [19] pozwalający na jednoznaczne określenie, który z genów z danej
pary chromosomów będzie miał wpływ na fenotyp osobnika. Dominacja genetyczna polega
na porównywaniu kolejno genów, które zajmują tą samą pozycję w obu chromosomach
osobnika diploidalnego, a następnie wybraniu tego genu, który jest dominujący genetyczne.
Wybór taki dokonywany jest na podstawie następującego schematu: 1 dominuje nad 0, 1
dominuje nad –1 oraz 0 dominuje nad –1, co przedstawia rys. 4.3 [19].
Rys. 4.3.
Schemat dominacji genetycznej w diploidalnym chromosomie kodowanym
triallelicznie.
Przykładowo dla osobnika diploidalnego (4.12) uzyskamy chromosom o postaci
[
]
T
'
1
0
1
1
0
1
1
1
0
−
=
di
v
(4.14)
22
4. Algorytmy ewolucyjne
W drugim etapie dekodowania stosuje się odwzorowanie liniowe (4.13) nieco
zmodyfikowane
N
i
n
k
v
x
x
x
x
k
ij
k
i
m
j
j
k
m
k
k
k
k
,
,
2
,
1
,
,
,
2
,
1
,
2
1
2
0
…
…
=
=
−
−
+
=
∑
=
(4.15)
Obecnie coraz częściej stosuje się multialleliczną (zmiennopozycyjną) reprezentację
parametrów [74], która stanowi naturalny sposób kodowania parametrów należących do
dziedziny określonej w zbiorze liczb rzeczywistych. W takim przypadku nie ma potrzeby
odrębnego kodowania poszukiwanych parametrów, ponieważ genotyp optymalizowanego i -
tego osobnika składa się z pojedynczego chromosomu (
i
v ), który może być utożsamiany z
jego fenotypem
i
x
n
i
i
ℜ
∈
= x
v
(4.16)
4.3.
Ocena stopnia przystosowania
Funkcja celu jest głównym źródłem oceny stopnia przystosowania każdego osobnika. W
algorytmach genetycznych wymagane jest, aby funkcja celu była funkcją przystosowania
)
( x
f
z przeciwdziedziną określoną w zbiorze liczb rzeczywistych dodatnich. W wielu
zadaniach optymalizacji mamy do czynienia z funkcjami celu, które tego warunku nie
spełniają. Wówczas stosuje się, na przykład, następujące przekształcenia [1, 19, 74, 88]:
• dla funkcji kosztu
)
( x
u
, gdy jej przeciwdziedzina jest określona w zbiorze liczb
rzeczywistych dodatnich i ujemnych
)
(
)
(
max
x
x
u
C
f
−
=
(4.17)
gdzie współczynnik
max
C
jest nie mniejszy niż maksymalna wartość funkcji
)
( x
u
uzyskana na zbiorze osobników w aktualnej populacji
• dla funkcji zysku
)
( x
g
, gdy jej przeciwdziedzina jest określona w zbiorze liczb
rzeczywistych dodatnich i ujemnych
min
)
(
)
(
C
g
f
−
=
x
x
(4.18)
gdzie współczynnik
min
C
jest nie większy niż minimalna wartość funkcji
)
( x
g
w
aktualnej populacji.
4.4.
Selekcja osobników
W selekcji osobników naśladuje się mechanizm przeżycia w naturze. Wobec tego
oczekujemy, że osobnik o najwyższym stopniu przystosowaniu uzyska liczne potomstwo, tj.
pomnoży swój materiał genetyczny i podniesie w ten sposób prawdopodobieństwo swojego
przeniknięcia („przeżycia”) do następnego pokolenia. Natomiast osobniki o najniższym
23
stopniu przystosowania powinny być eliminowane z opisywanego procesu prokreacji. Do
najczęściej stosowanych metod selekcji [1, 19, 88] należą:
• metoda proporcjonalna
• metoda ze stochastycznym doborem resztowym oraz
• metoda turniejowa.
4.4.1.
Metoda proporcjonalna
Metoda proporcjonalna [1, 19, 74, 88], polega na skonstruowaniu tzw. ruletki, której sektory
kątowe są proporcjonalne do wartości funkcji przystosowania osobników. Wybór osobników
do puli rodzicielskiej polega na N
−krotnym ( N − założona liczba osobników w populacji)
ustaleniu pozycji zakręcanego koła ruletki. Lepiej przystosowane osobniki mają
proporcjonalnie większe sektory kątowe na tarczy ruletki, zatem mają również większą szansę
na wprowadzenie większej liczby potomków do następnego pokolenia populacji.
Poniżej zamieszczono procedurę selekcji metodą proporcjonalną.
Proc. 4.1. Metoda proporcjonalna.
1. wyznacz prawdopodobieństwa wyboru osobników z populacji w postaci względnego
przystosowania
N
i
f
f
p
N
i
i
i
i
s
,
,
2
,
1
,
)
(
)
(
)
(
1
…
=
=
∑
=
x
x
x
(4.19)
2. wyznacz dystrybuantę dla ustalonej sekwencji osobników
∑
=
=
i
j
j
s
i
p
q
1
)
(
)
(
x
x
(4.20)
3.
N
-krotnie ‘zakręć kołem ruletki’ poprzez
N
-krotne:
• wygenerowanie losowej liczby
[ ]
1
,
0
∈
r
• ustalenie pierwszego napotkanego osobnika w populacji, dla którego
spełniony jest warunek
)
(
i
q
r
x
≤
(4.21)
• skopiowanie wylosowanego osobnika do puli rodzicielskiej
Przykł. 4.1. Selekcja metodą proporcjonalną.
Niech dana jest funkcja przystosowania
2
3
2
2
2
1
3
2
1
1300
)
,
,
(
x
x
x
x
x
x
f
−
−
−
=
(4.22)
określona w dziedzinie
[
]
15
,
0
1
∈
x
,
[ ]
7
,
0
2
∈
x
,
[
]
31
,
0
3
∈
x
. Załóżmy, że populacja składa się z
4 osobników haploidalnych
[
]
4
3
2
1
v
v
v
v
V
=
(4.23)
gdzie
24
4. Algorytmy ewolucyjne
[
]
4
,
3
,
2
,
1
,
T
3
2
1
=
=
i
v
v
v
i
i
i
i
v
(4.24)
Ponadto niech odcinki (współrzędne) chromosomu tych osobników kodowane są binarnie,
odpowiednio:
1
x
na 4 bitach,
2
x
na 3, zaś
3
x na 5 bitach. tab. 4.1 przedstawia przykładową
sytuację dla losowo wygenerowanych punktów w rozważanej dziedzinie.
Każdemu osobnikowi przyporządkowany jest odpowiedni sektor kątowy koła ruletki,
przedstawionej na rys. 4.4 według ich (względnego przystosowania) prawdopodobieństwa
wyboru. Jak widać największą szansę wyboru do puli rodzicielskiej posiada osobnik
4
v
)
3934
.
0
)
(
(
4
=
x
s
p
, zaś osobnik
1
v
szansę znalezienia się puli rodzicielskiej ma najmniejszą
)
0864
.
0
)
(
(
1
=
x
s
p
.
Przykładowy wynik czterokrotnego zakręcenia kołem ruletki prowadzi do puli
rodzicielskiej
p
V złożonej z następujących osobników
[
]
3
4
3
4
v
v
v
v
V
=
p
(4.25)
Zgodnie z oczekiwaniami osobniki najlepiej przystosowane tworzą pulę rodzicielską, która
wyda w kolejnym kroku algorytmu genetycznego swoje potomstwo.
Tab. 4.1.
Genotyp, fenotyp i przystosowanie osobnika.
przystosowanie
Lp.
Genotyp
fenotyp
bezwzglę
dne
względne
dystrybuanta
i
i
v
i
x
)
(
i
f x
)
(
i
s
p x
)
(
i
q x
1
[
]
T
11110
110
0110
[
]
T
31
6
6
267
0.0864
0.0864
2
[
]
T
10101
101
1100
[
]
T
21
5
12
690
0.2232
0.3096
3
[
]
T
10010
011
0111
[
]
T
18
3
7
918
0.2970
0.6066
4
[
]
T
01000
010
0100
[
]
T
8
2
4
1216
0.3934
1.0000
∑
=
4
1
)
(
i
i
f x
= 3091
Rys. 4.4.
Koło ruletki dla rozważanego przykładu.
25
4.4.2.
Metoda ze stochastycznym doborem resztowym
Metoda ze stochastycznym doborem resztowym polega na obliczeniu oczekiwanej liczby
kopii dla każdego osobnika w populacji, w oparciu o którą do puli rodzicielskiej kopiuje się
osobniki na podstawie całkowitej części oczekiwanej liczby kopii. Z kolei część resztowa z
tej liczby służy do określenia sektorów kątowych ruletki (tak jak w metodzie
proporcjonalnej). Tak skonstruowana ruletka zostaje użyta do uzupełnienia puli rodzicielskiej
dodatkowymi osobnikami. Poniżej zamieszczono procedurę metody ze stochastycznym
doborem resztowym ([1, 19, 52, 74].
Proc. 4.2. Metoda ze stochastycznym doborem resztowym.
1. wyznacz oczekiwaną liczbę kopii osobników w populacji
N
i
N
f
f
e
N
i
i
i
i
,
,
2
,
1
,
)
(
)
(
)
(
1
…
=
⋅
=
∑
=
x
x
x
(4.26)
2. skopiuj
∑
=
=
N
i
i
e
N
1
int
)
( x
osobników do puli rodzicielskiej na podstawie ich
całkowitych częściach liczby
)
(
i
e x
, oraz określ liczbę ‘wakatów’
int
~
N
N
N
−
=
;
3. wyznacz ‘dystrybuantę’ osobników wg resztowej części
)
(
i
e x
{
}
∑
=
−
=
i
j
j
j
i
e
e
q
1
)
(
)
(
)
(
x
x
x
(4.27)
4.
N
~
-krotnie ‘zakręć kołem ruletki’ poprzez
N
~
-krotne:
• wygenerowanie losowej liczby
[ ]
1
,
0
∈
r
• ustalenie pierwszego napotkanego osobnika w populacji, dla którego
spełniony jest warunek
)
(
)
(
N
i
q
q
r
x
x
≤
(4.28)
• skopiowanie wylosowanego osobnika do puli rodzicielskiej
Przykł. 4.2. Selekcja metodą stochastycznego doboru resztowego.
Zastosujmy metodę stochastycznego doboru resztowego dla rozwiązań z
przykł. 4.1. Wartości
oczekiwanej liczby kopii i ‘dystrybuanty’ dla osobników z
przykł. 4.1 przedstawia .
Wykonując krok 2 proc. 4.2 do puli rodzicielskiej skopiowane zostają osobniki
3
v i
4
v
. Pula
rodzicielska po tym kroku posiada 2 ‘wakaty’, zatem należy zakręcić dwukrotnie kołem
ruletki, którą zilustrowano na rys. 4.5. Sektory kątowe ruletki są wyznaczone na podstawie
prawdopodobieństwa wyboru, które prezentuje pierwsza od prawej kolumna w tab. 4.2.
Przykładowy wynik dwukrotnego zakręcenia powyższego koła ruletki prowadzi do
wybrania osobników
4
v
i
2
v
. Zatem pula rodzicielska
p
V złożona jest z następujących
osobników:
26
4. Algorytmy ewolucyjne
[
]
2
4
4
3
v
v
v
v
V
=
p
(4.29)
Można, zauważyć, że metoda stochastycznego doboru resztowego daje większe szanse dla
osobników o większej (nieuwzględnionej) części resztowej. W związku z tym, osobniki
1
v
i
2
v
mają większe prawdopodobieństwa uzupełnienia puli rodzicielskiej swoimi kopiami.
Tab. 4.2.
Przystosowanie, oczekiwana liczba kopii oraz dystrybuanty (nieunormowana
i unormowana) osobnika.
i
v
)
(
i
f x
)
(
i
e x
)
(
)
(
i
i
e
e
x
x
−
)
(
i
q x
)
(
)
(
4
x
x
q
q
i
)
(
)
(
)
(
4
x
x
x
q
e
e
p
i
i
s
−
=
1
v
267
0
0.3456
0.3456
0.1728
0.1728
2
v
690
0
0.8928
1.2384
0.6192
0.4460
3
v
918
1
0.1880
1.4264
0.7132
0.0940
4
v
1216
1
0.5736
2.0000
1.0000
0.2868
∑
=
4
1
)
(
i
i
f x
=3091
Rys. 4.5.
Koło ruletki dla metody stochastycznego doboru resztowego.
4.4.3.
Metoda turniejowa
Metoda turniejowa jest kolejną metodą pozwalającą tworzyć pulę rodzicielską. Sposób
selekcji został skojarzony z procesem rywalizacji dwóch osobników, z których wygrywa
lepiej przystosowany. Liczba osobników uczestniczących w turnieju decyduje o tzw. nacisku
selekcyjnym (ang. selection pressure) [1, 19, 74, 88]. Przykładowo, jeżeli liczba uczestników
jest stosunkowo duża, wówczas słabsze osobniki maja mniejszą szansę na wybranie jako
osobników rodzicielskich.
27
4.5.
Operacje genetyczne
Do operacji genetycznych [1, 19, 74, 88], wykonywanych na osobnikach wytypowanych do
puli rodzicielskiej zalicza się:
• krzyżowanie oraz
• mutację.
Należy zaznaczyć, iż przy wykonywaniu operacji genetycznych chromosom osobnika
traktowany jest jako pojedyncza sekwencja kodowa złożona z poszczególnych odcinków
kodowych chromosomu (reprezentujących współrzędne optymalizowanego wektora).
Natomiast w przypadku kodowania zmiennopozycyjnego (multiallelicznego) operacje
genetyczne (w algorytmach często nazywanych wówczas ewolucyjnymi) wykonuje się
odrębnie dla poszczególnych współrzędnych (genów).
4.5.1.
Krzyżowanie
Operacja krzyżowania (ang. crossover) jest analogiczna do (opisanej w dodatku)
rekombinacji pomiędzy nićmi DNA chromosomów z par homologicznych. W algorytmach
genetycznych krzyżowanie polega na wymianie materiału genetycznego (części chromosomu)
między dwoma rodzicami. W wyniku tego uzyskuje się dwóch potomków stanowiących nowe
rozwiązania. Operacja ta przebiega w dwóch etapach: najpierw kojarzone są w sposób losowy
osobniki z puli rodzicielskiej w pary, a następnie każda para rodziców przechodzi proces
wymiany materiału genetycznego (tj. wymiany fragmentów sekwencji kodowych pomiędzy
chromosomami osobników rodzicielskich). Operacja ta zachodzi z określonym
prawdopodobieństwem nazywanym prawdopodobieństwem krzyżowania
c
p
(zwykle
]
1
,
6
.
0
[
∈
c
p
).
Najczęściej stosowanym sposobem krzyżowania jest:
• krzyżowanie jednopunktowe lub
• krzyżowanie wielopunktowe (zwykle dwu- lub trójpunktowe).
Przy krzyżowaniu jednopunktowym proces wymiany materiału genetycznego rozpoczyna
się od wylosowania z jednakowym prawdopodobieństwem punktu krzyżowania (tj. punktu
podziału chromosomu na dwie części) spośród
1
−
m
pozycji w chromosomie, gdzie m jest
długością chromosomu. Następnie wymienia się miejscami cały odcinek od punktu
krzyżowania do końca chromosomu
)
(m włącznie w obu osobnikach pary. W rezultacie tego,
jak pokazano na rys. 4.6a, powstają dwa nowe osobniki potomkowie, (ang. offsprings).
W przypadku krzyżowania wielopunktowego proces wymiany materiału genetycznego
zachodzi między częściami chromosomów znajdującymi się pomiędzy kolejnymi (również
wylosowanymi z jednakowym prawdopodobieństwem) punktami krzyżowań. Przykładową
ilustrację krzyżowania trójpunktowego przedstawia rys. 4.6b.
Przykł. 4.3. Krzyżowanie jednopunktowe dla osobników kodowanych binarnie.
Niech dane są dwa osobniki haploidalne
r
v
i
s
v
})
,
,
2
,
1
{
,
(
N
s
r
…
∈
wybrane do krzyżowania,
których chromosomy mają długość
16
=
m
bitów (genów). Przy czym każdy osobnik
traktowany jest jako pojedyncza sekwencja kodowa złożona z połączenia poszczególnych
odcinków (sekwencji binarnych)
28
4. Algorytmy ewolucyjne
[
]
T
0100111
11110
0100
=
r
v
(4.30)
[
]
T
0000000
00011
0100
=
s
v
(4.31)
[
]
[
]
T
T
100111
0100111100
0100111
11110
0100
=
⇒
=
r
r
v
v
(4.32)
[
]
[
]
T
T
000000
0100000110
0000000
00011
0100
=
⇒
=
s
s
v
v
(4.33)
Niech losowo wybranym punktem krzyżowania (spośród 15 punktów) jest punkt leżący między
bitem 10 a 11. Wówczas generowane są następujące osobniki potomne:
[
]
[
]
T
'
T
'
0000000
11011
0100
000000
0100110110
=
⇒
=
r
r
v
v
(4.34)
[
]
[
]
T
'
T
'
0100111
00110
0100
100111
0100001100
=
⇒
=
s
s
v
v
(4.35)
Rys. 4.6.
Schemat krzyżowania [72]: (a) jednopunktowego; (b) trójpunktowego.
Rys. 4.7.
Schemat krzyżowania jednopunktowego osobników diploidalnych.
29
W przypadku osobników diploidalnych kodowanych triallelicznie również może być
stosowane krzyżowanie jedno- lub wielopunktowe. Jednopunktowy proces wymiany
materiału genetycznego przebiega jak na rys. 4.7. Wybrani losowo rodzice analogicznie do
procesu mejozy (opisanej w dodatku) produkują gamety (komórki rozrodcze). Gamety są
tworzone poprzez skrzyżowanie pary chromosomów danego rodzica. Następnie losowo
paruje się gamety w celu utworzenia potomków.
Przy reprezentacji zmiennopozycyjnej najczęściej stosuje się [74]:
• krzyżowanie arytmetyczne lub
• krzyżowanie mieszane.
Istotną cechą obu typów krzyżowania jest zapewnienie, że nowo kreowani potomkowie
stanowią rozwiązania dopuszczalne, tzn. należą do dziedziny określonej na podstawie zakresu
parametrów i innych liniowych ograniczeń nałożonych na te parametry.
Krzyżowanie arytmetyczne polega na unormowanej liniowej kombinacji dwóch
wektorów reprezentujących multialleliczne chromosomy (które są jednocześnie fenotypem i
genotypem). Jeżeli do krzyżowania wybrano parę osobników rodzicielskich
r
v
i
s
v
})
,
,
2
,
1
{
,
(
N
s
r
…
∈
[
]
T
2
1
r
r
r
n
r
v
v
v
…
=
v
(4.36)
[
]
T
2
1
s
s
s
n
s
v
v
v
…
=
v
(4.37)
to potomkowie wyznaczani są z następujących wzorów:
s
r
r
a
a
v
v
v
)
1
(
'
−
+
=
(4.38)
r
s
s
a
a
v
v
v
)
1
(
'
−
+
=
(4.39)
gdzie
]
1
,
0
[
∈
a
jest wartością wybieraną losowo dla każdej pary rodziców.
Krzyżowanie mieszane (Michalewicz nazywa to prostym krzyżowaniem) jest
połączeniem krzyżowania jednopunktowego z krzyżowaniem arytmetycznym. Jeżeli
krzyżowaniu podlegałaby para rodziców (4.36) i (4.37) według losowo wybranej k -tej
współrzędnej wymiany genetycznej, wówczas jej osobniki potomne uzyskałyby następującą
postać:
[
]
T
)
1
(
)
1
(
1
'
)
1
(
)
1
(
r
s
r
s
r
r
n
n
k
k
k
r
v
a
av
v
a
av
v
v
−
+
−
+
=
+
+
…
…
v
(4.40)
[
]
T
)
1
(
)
1
(
1
'
)
1
(
)
1
(
s
r
s
r
s
s
n
n
k
k
k
s
v
a
av
v
a
av
v
v
−
+
−
+
=
+
+
…
…
v
(4.41)
gdzie
]
1
,
0
[
∈
a
jest inną wartością wybraną losowo dla każdej pary rodziców. Podobnie jak
dla krzyżowania arytmetycznego, krzyżowanie mieszane zapewnia, że wykreowani
potomkowie stanowią rozwiązania dopuszczalne (należące do dziedziny określonej zakresem
parametrów i nie naruszające liniowych ograniczeń nałożonych na te parametry).
4.5.2.
Mutacja
Operacja mutacji wprowadza przypadkowe ‘zaburzenia’ w nowo powstałych rozwiązaniach
(osobnikach potomnych). Ze względu na obiekt modyfikacji, mutacje można podzielić na
dwie grupy:
30
4. Algorytmy ewolucyjne
• mutacje genotypowe (genetyczne) oraz
• mutacje fenotypowe (parametryczne).
Mutacja dotyczy zmiany alleli genów całej populacji osobników. Zmiana ta może mieć zasięg
pełny lub ograniczony: każdy z genów (lub parametrów) może podlegać mutacji (zmianie bi-
lub multiallelicznej) z założonym prawdopodobieństwem mutacji
m
p
lub ograniczając liczbę
dokonywanych mutacji losuje się (wg założonego rozkładu prawdopodobieństwa - zwykle
równomiernego) pozycje w genotypie (lub fenotypie), które mają podlegać zmianie (allelu).
Mutacja genotypowa w przypadku kodowania binarnego, polega na wprowadzeniu
(z zasięgiem pełnym lub ograniczonym) przypadkowej zmiany allelu genu w chromosomie na
„przeciwny” (zanegowanie wybranego bitu kodu binarnego). Ilustrację przykładowej mutacji
osobnika haploidalnego przedstawiono na rys. 4.8 [72], gdzie chromosom jest
reprezentowany przez sekwencję binarną.
Rys. 4.8.
Przykład mutacji genotypowej dla kodowania binarnego.
Przy kodowaniu triallelicznym dla mutacji genotypowej o wybranym zasięgu, sposób
wprowadzania przypadkowych zmian allelu genów chromosomu opisuje graf przepływowy
przedstawiony na rys. 4.9. Węzły grafu reprezentują początkowe wartości (allele) genów w
chromosomie, zaś gałęzie tego grafu reprezentują możliwe zmiany na skutek wylosowania z
jednakowym prawdopodobieństwem (równym 0.5) liczb –1 lub 1.
Rys. 4.9.
Przykład mutacji genotypowej dla kodowania binarnego.
W przypadku reprezentacji zmiennopozycyjnej osobników, kiedy realizowana jest
mutacja fenotypowa, wprowadza się zmianę wybranych parametrów. Podobnie jak dla
krzyżowania arytmetycznego i mieszanego, mutacja fenotypowa zapewnia, że zmutowane
osobniki są rozwiązaniami dopuszczalnymi, tzn. należą do dziedziny określonej na podstawie
31
zakresu parametrów i liniowych ograniczeń na te parametry. W tego rodzaju mutacji można
wyróżnić dwa sposoby modyfikacji wartości parametru polegające na [43, 74]:
• zmianie wartościowo-równomiernej lub
• zmianie wartościowo-nierównomiernej.
Zmiana wartościowo-równomierna polega na nadawaniu (w każdym cyklu mutacji GA)
wybranemu parametrowi
q
k
v
osobnika
n
q
ℜ
∈
v
losowej wartości
'
q
k
v
z przedziału
określającego dziedzinę mutowanego k -tego parametru z równomiernym rozkładem
prawdopodobieństwa [74]. Uzyskuje się w ten sposób nowy fenotyp
'
q
v
o następującej
postaci:
[
]
T
'
1
1
'
n
k
q
v
v
v
v
…
…
=
v
(4.42)
W zadaniach z liniowymi ograniczeniami owa dziedzina parametru musi być określana
odpowiednio
− biorąc pod uwagę narzucone ograniczenia zadania optymalizacji z
uwzględnieniem niezmienionych, pozostałych wartości parametrów w fenotypie. Przymiotnik
„równomierna” nie odnosi się do równomierności rozkładu prawdopodobieństwa, ale
oznacza, że działanie mutacji jest niezależne od numeru iteracji t algorytmu (numeru
pokolenia w realizowanym procesie optymalizacji).
Zmiana wartościowo-nierównomierna pozwala na dokładne dostrojenie parametrów.
Operacja ta polega na stochastycznym zaburzeniu poprzednio ustalonej wartości wybranego
parametru z zastosowaniem zawężającego się
− wraz ze wzrostem numeru iteracji −
dopuszczalnego przedziału (równomiernych zmian parametrów). Wybrany parametr
q
k
v
osobnika
n
q
ℜ
∈
v
uzyskuje wówczas wartość [74]
−
∆
−
−
∆
+
=
)
B
(
)
,
(
)
A
(
)
,
(
'
k
k
k
k
k
k
k
v
v
t
v
v
v
t
v
v
q
q
q
q
q
,
b
t
t
v
r
v
t
−
∆
⋅
=
∆
∆
max
1
)
,
(
(4.43)
gdzie przedział
[
]
ℜ
⊂
k
k
v
v
,
określa zakres (dziedzinę) mutowanego parametru
q
k
v
, t
oznacza numer pokolenia,
max
t
jest zadaną ilością generowanych pokoleń (iteracji), b to
współczynniki niejednorodności (zwykle
2
=
b
), natomiast
[ ]
1
,
0
∈
r
jest losową liczbą.
Dodatkowo, wybór sposobu mutacji, (A lub B), dokonywany jest losowo z jednakowym
prawdopodobieństwem równym 0.5.
4.6.
Strategie podstawień
Według podstawowej zasady obowiązującej w algorytmach genetycznych, początkowa
populacja, wygenerowana losowo przy starcie algorytmu, po przejściu jednego cyklu ewolucji
(iteracji) zastępowana jest przez powstałą populację potomków. Ta nowo powstała populacja
osobników po ponownym cyklu GA zostaje zastąpiona przez kolejną populację potomków.
Proces ten powtarza się do chwili, gdy spełnione jest zadane kryterium zakończenia
algorytmu. Stosowanymi strategiami podstawień są [1, 19, 74]:
• reprodukcja pełna lub
• reprodukcja częściowa.
32
4. Algorytmy ewolucyjne
W strategii z reprodukcją pełną nowo powstała populacja o liczbie osobników N zastępuje
całą poprzednią populację. Jest to najprostsza ze strategii podstawień. Strategia z częściową
reprodukcją polega na zastąpieniu jedynie najgorszych osobników, o najniższych stopniach
przystosowania, przez nowo powstałych potomków (co może być interpretowane jako
możliwość posiadania wielopokoleniowego potomstwa).
4.7.
Skalowanie przystosowania
Liczne badania nad algorytmami genetycznymi wykazały, że często występuje zjawisko
przedwczesnej zbieżności (ang. premature convergance) do suboptymalnego rozwiązania [1,
19, 74]. Zjawisko to oznacza, że w kilku pierwszych cyklach algorytmów genetycznych w
populacji
występuje
kilku
ponadprzeciętnych
osobników
(o
wysokim
stopniu
przystosowania), natomiast reszta osobników zalicza się do niższej kategorii. W wyniku
selekcji takich osobników, szybko (już po jednym pokoleniu) uzyskują one znaczący udział w
całej populacji. Przez co, powstająca nowo populacja jest mało zróżnicowana, a algorytm
genetyczny zachowuje się tak, jakby zaprzestał poszukiwania dalszych lepszych rozwiązań.
W celu zapobieżenia wyżej opisanemu zjawisku stosuje się metodę skalowania liniowego
[1, 19,74]. Schemat tej metody przedstawia następująca proc. 4.3.
Proc. 4.3. Metoda skalowania liniowego.
1. znajdź w aktualnej populacji osobnika o maksymalnym i minimalnym stopniu
przystosowania
)
(
max
}
,
,
2
,
1
{
i
N
i
max
f
f
x
…
∈
=
(4.44)
)
(
min
}
,
,
2
,
1
{
i
N
i
min
f
f
x
…
∈
=
(4.45)
2. wyznacz średnie przystosowanie populacji
avg
f
według wzoru
∑
=
=
N
i
i
avg
f
N
f
1
)
(
1
x
(4.46)
3. przeskaluj stopnie przystosowania osobników według formuły
b
af
f
i
i
s
+
=
)
(
)
(
x
x
(4.47)
gdzie
a
i
b
oznaczają współczynniki skalowania liniowego, których wartości
wyznaczane są następująco:
• sprawdź warunek skalowania
1
−
−
>
c
f
cf
f
max
avg
min
(4.48)
gdzie
c
oznacza współczynnik zwielokrotnienia (pożądaną liczbę kopii),
• jeżeli warunek (4.48) jest spełniony to wyznacz współczynniki skalowania:
)
1
(
,
)
1
(
+
−
=
−
−
=
a
f
b
f
f
c
f
a
avg
avg
max
avg
(4.49)
w przeciwnym wypadku wyznacz współczynniki skalowania według wzorów:
33
min
min
avg
avg
af
b
f
f
f
a
−
=
−
=
,
(4.50)
Współczynnik zwielokrotnienia
c
dla populacji składającej się od 50 do 100 osobników
przyjmuje zwykle wartość równą 2. Jest on utożsamiany z pożądaną liczbą kopii. Skalowanie
liniowe ze współczynnikami
a
i b wyznaczonymi wg wzoru (4.50) powoduje, że stopień
przystosowania odpowiednio osobników ponadprzeciętnych zmniejsza się, zaś osobników
gorszych zwiększa się. W ten sposób w początkowych cyklach algorytmów genetycznych
generuje się populacje bardziej różnorodne, zapobiega się przedwczesnej zbieżności
algorytmów. Z kolei skalowanie z użyciem współczynników (4.49) powoduje wywołanie
zdrowej konkurencji między osobnikami o podobnym stopniu przystosowania w końcowych
cyklach algorytmów genetycznych.
4.8.
Mechanizm niszowania
Proces selekcji jest w przyrodzie głównym mechanizmem rywalizacji pomiędzy osobnikami.
Decyduje on o możliwości przeżycia danego osobnika, gatunku czy też całej populacji.
Wybrane najlepiej przystosowane osobniki posiadają większą szansę uzyskiwania potomków
o podobnych cechach. Nieustanny proces selekcji w tworzących się nowych populacjach
prowadzi do generowania osobników coraz to lepiej przystosowanych. Czasami przyroda
dopuszcza przetrwanie z małym prawdopodobieństwem osobników słabiej przystosowanych.
Takie osobniki stanowić mogą źródło różnorodności i adaptacyjności danej populacji
osobników do nowych warunków. Owe osobniki stając się bowiem rodzicami pozwalają na
zachowanie innowacyjności (nowości) w procesie przekazywania potomkom informacji
genetycznej. Można powiedzieć, że w procesie naturalnej selekcji bada się także inne
możliwości osiągania osobników lepiej przystosowanych. Jednak w naturalnych warunkach
taki okres „ochronny” gorszych osobników trwa krótko. W wyniku tego populacje osobników
należących do gatunków zagrożonych zwykle szybko zanikają. Jednym z możliwych
sposobów zapobieżenia takiej sytuacji jest hodowla ginących gatunków w „cieplarnianych
warunkach” pozwalających na ich przeżycie.
Poprzez analogię do przyrody, niszowanie w algorytmach ewolucyjnych [1, 19, 61, 39,
74] ma na celu zachowanie gorzej przystosowanych osobników, tak, aby populacja była
różnorodna, tj. zawierała nie tylko bardziej przystosowane, ale także i osobniki przeciętne
oraz mniej przystosowane. Niszowanie pozwala zatem na utrzymaniu stałej liczby
istniejących gatunków: zarówno tych bardziej licznych (lepiej przystosowanych), jak i tych
mniej licznych (słabiej przystosowanych).
Nisza, w algorytmach ewolucyjnych, jest pewnym obszarem, w którym znajdują się
osobniki o podobnych charakterystykach, tzn. osobniki bliskie parametrycznie (fenotypowo,
geometrycznie), które powinny mieć także podobne stopnie przystosowania. Zatem osobniki
znajdujące się w niszy mogą być uznane za pewien gatunek. Stopień pokrewieństwa między
osobnikami określany jest na podstawie odwzorowania zwanego funkcją bliskości lub
pokrewieństwa, której argumentem jest geometryczna odległość między rozważanymi
osobnikami. Funkcja bliskości przyjmuje wartości z przedziału [0,1]. Wartość zerowa funkcji
bliskości oznacza, że osobniki nie są spokrewnione i nie należą do tego samego gatunku, z
kolei wartość 1 oznacza najbliższe pokrewieństwo (identyczność).
Nisze w wielowymiarowej przestrzeni parametrów definiuje się jako hiperelipsoidę, w
której może znaleźć się zbiór osobników. Jak wyżej zauważono, bliskie fenotypowo osobniki
zalicza się do jednego gatunku. Stopień bliskości fenotypowej (pokrewieństwa) dwu
34
4. Algorytmy ewolucyjne
osobników
i
v oraz
j
v o fenotypach odpowiednio
)
,
,
2
,
1
,
(
,
N
j
i
n
j
i
…
=
ℜ
∈
x
x
wyrażany jest
funkcją bliskości
ij
δ (ang. sharing function) [19, 74], którą definiujemy następująco:
≥
−
<
−
≤
−
−
=
δ
1
0
1
0
1
P
j
i
P
j
i
P
j
i
ij
jeśeś
jeśeś
x
x
x
x
x
x
(4.51)
gdzie
)
(
)
(
2
T
j
i
j
i
P
j
i
x
x
P
x
x
x
x
−
−
=
−
−
(4.52)
{
}
n
diag
φ
φ
φ
=
…
2
1
P
(4.53)
natomiast
)
,...,
2
,
1
(
n
k
k
=
φ
jest k -tą średnicą hiperelipsoidy o środku w i -tym osobniku. W
szczególności k -tą średnicę hiperelipsoidy wyznaczać można na podstawie wzoru
n
k
k
k
,
,
2
,
1
,
…
=
ε
∆
=
φ
(4.54)
gdzie
k
∆ jest niezerowym zakresem poszukiwań k -tego parametru, zaś
ε
reprezentuje liczbę
części, na jaką dzieli się ten zakres.
W ogólności mechanizm niszowania polega na modyfikacji wektora stopnia
przystosowania lub skalarnej rangi (wyznaczonej metodą rangowania wg Pareto-
optymalności) każdego osobnika znajdującego się we ‘własnej’ niszy według następującego
przepisu [1, 19, 61, 39, 74]:
∑
=
δ
=
N
j
ij
i
i
1
)
(
)
(
~
x
f
x
f
,
∑
=
δ
=
N
j
ij
i
i
r
r
1
)
(
)
(
~
x
x
(4.55)
gdzie
)
(
i
x
f
jest wektorem stopnia przystosowania, a
)
(
i
r x
oznacza skalarną rangę i-tego
osobnika, natomiast
)
(
~
i
x
f
i
)
(
~
i
r x
reprezentują odpowiednio jego ‘niszowo-uwarunkowany’
wektor stopnia przystosowania i skalarną rangę. Suma w obu mianownikach (4.55) wyraża
efektywną liczbę osobników w niszy własnej o środku opisanym przez fenotyp rozważanego
i
-tego osobnika. Jeżeli osobnik sam zajmuje oddzielną niszę, wówczas jego wektor stopnia
przystosowania lub skalarnej rangi oczywiście nie zmniejsza się (jedyna niezerowa wartość to
1
=
δ
ii
). W innym przypadku stopień przystosowania lub ranga są zmniejszane stosownie do
zagęszczenia populacyjnego jego niszy.
Przykł. 4.4. Nisze w dwuwymiarowej przestrzeni.
Rozważmy dwuwymiarową przestrzeń poszukiwań. Na rys. 4.10 przedstawiono
dwuwymiarową kostkę poszukiwanych parametrów
[
]
1
1
1
, x
x
x
∈
i
[
]
2
2
2
, x
x
x
∈
. Zakresy
poszukiwań wynoszą zatem
1
1
1
x
x
−
=
∆
i
2
2
2
x
x
−
=
∆
. W ten sposób obszar poszukiwań
został podzielony na 9 równych części
)
3
(
=
ε
. W wyniku takiego podziału, jak to
zilustrowano na rys. 4.11 każdy osobnik uzyskuje własną niszę, którą jest elipsa o średnicach
odpowiednio
3
/
1
∆
i
3
/
2
∆
.
35
Przykł. 4.5. Niszowanie przystosowania.
Rozważmy
przykładowy
proces
niszowania
dwuwymiarowego
wektora
stopnia
przystosowania. Rozmieszczenie 12 osobników w dwuwymiarowej przestrzeni pokazano na
rys. 4.12a natomiast odpowiadające im wektory przystosowania przedstawiono na rys. 4.12b.
Zauważmy, iż w populacji tej znajduje się pojedyncze Pareto-optymalne rozwiązanie
oznaczone ‘gwiazdką’. Dla tego osobnika zaznaczono jego własną niszę o promieniach
odpowiednio 8/6 i 7/6. rys. 4.12c przedstawia niszowo-uwarunkowany wektorowy stopień
przystosowania osobników, będący podstawą prowadzonej selekcji metodą rankingu. Widać,
że w wyniku niszowania stopień przystosowania 10-ciu osobników (oznaczonych ‘kółkami’ i
‘gwiazdką’) został zmniejszony (pokazują to strzałki), natomiast stopnie przystosowania
dwóch osobników (‘krzyżyk’ i ‘kropka’) pozostały niezmienione.
Rys. 4.10. Podział dwuwymiarowej kostki poszukiwanych parametrów.
Rys. 4.11. Nisze jako elipsy.
36
4. Algorytmy ewolucyjne
1
x
2
x
0
2
4
6
8
0
1
2
3
4
5
6
7
1
f
2
f
0
1
2
3
4
5
6
0
1
2
3
4
5
6
7
1
~
f
2
~
f
0
1
2
3
4
5
6
0
1
2
3
4
5
6
7
Rys. 4.12. Mechanizm niszowania przystosowania: (a) populacja osobników i niszowa elipsa
dla optymalnego rozwiązania; (b) przystosowanie osobników; (c) niszowo-
uwarunkowane przystosowanie
Porównując oba rodzaje modyfikacji [39], tzn. niszowanie przystosowania i rang można
wnioskować, że niszowanie rang jest mechanizmem „silniejszym”. Jest to spowodowane tym,
ż
e rangi osobników są modyfikowane bezpośrednio. Zmiana rangi bezpośrednio oznacza
zmianę w strukturze dominacji (i stopnia zdominowania) w sensie Pareto, podczas gdy
niszowanie przystosowania stanowi jedynie źródło pośredniej modyfikacji rang. Ze zmianą
wektora przystosowania nie musi wynikać zmiana jego stopnia zdominowania.
Niszowanie poprzez odpowiednią modyfikację przystosowania lub rang osobników
pozwala zwiększyć szansę znalezienia się w następnym pokoleniu potomków z materiałem
genetycznym gatunków z rzadkich populacyjnie nisz oraz zmniejszyć ową szansę dla
gatunków z gęstych nisz. O niszowaniu można zatem powiedzieć, że jest rodzajem
równomiernej hodowli osobników (prowadzącym do bardziej równomiernego przeglądania
przestrzeni poszukiwań). Taki sposób konstrukcji algorytmu ewolucyjnego zapobiega zatem
występowaniu zjawiska przedwczesnej zbieżności.
4.9.
Interpretacja algorytmów genetycznych
Metodologię procesu poszukiwań GA można interpretować w kategoriach schematów [1, 19,
74]. Jest to wzorzec opisujący podzbiór sekwencji kodowych podobnych pod względem
pozycji o ustalonych wartościach zwanych pozycjami ustalonymi. Schemat definiuje się,
wprowadzając do kodu binarnego dodatkowy znak (symbol)
“#”, oznaczający nieustaloną
wartość pozycji. Schemat reprezentujący wszystkie sekwencje kodowe składa się tylko z
symboli “#”.
Przykł. 4.6. Schematy.
Niech dany będzie schemat
1
S
oraz
2
S
każdy o długości 11 bitów
[
]
T
1
1
1
0
#
0
1
1
#
1
0
0
=
S
(4.56)
[
]
T
2
#
#
#
#
#
#
#
#
#
#
#
=
S
(4.57)
Do schematu
1
S
pasują cztery chromosomy
[
]
T
1
1
1
0
0
0
1
1
0
1
0
0
=
v
(4.58)
[
]
T
2
1
1
0
1
0
1
1
0
1
0
0
=
v
(4.59)
37
[
]
T
3
1
1
0
0
0
1
1
1
1
0
0
=
v
(4.60)
[
]
T
4
1
1
0
1
0
1
1
1
1
0
0
=
v
(4.61)
Natomiast do schematu
2
S
pasują wszystkie chromosomy o długości 11 bitów, tzn.
reprezentuje dokładnie
11
2 możliwych sekwencji binarnych. Każdy schemat może zatem
reprezentować dokładnie
p
2 podobnych chromosomów (o określonej długości), gdzie p jest
liczbą symboli “#” w schemacie.
Schemat posiada następujące dwie istotne własności, tj. rząd
i rozpiętość [1, 19, 74].
Rzędem schematu S nazywa się liczbę ustalonych pozycji, tzn. liczbę 0 i 1 w schemacie.
Niech rząd schematu S jest oznaczony przez
)
(S
ρ
. Schematy
1
S
i
2
S
z przykł. 4.6, posiadają
rzędy odpowiednio
9
)
(
1
=
ρ S
oraz
0
)
(
2
=
ρ S
.
Rozpiętością schematu S nazywa się odległość między skrajnymi ustalonymi pozycjami,
tzn. genami o ustalonej wartości (allelu) 0 lub 1 w schemacie i wyraża się następująco:
k
l
S
−
=
δ
)
(
1
(4.62)
gdzie k jest numerem pozycji pierwszego napotkanego genu o ustalonej wartości w
schemacie S , zaś l jest numerem pozycji ostatniego napotkanego genu o ustalonej wartości
(licząc od dowolnej strony). Dla schematów z przykł. 4.6 rozpiętości wynoszą odpowiednio
10
)
(
1
=
δ S
oraz
0
)
(
2
=
δ S
.
4.9.1.
Efekt ewolucyjnej selekcji
Niech schemat S reprezentuje osobniki haploidalne o chromosomach kodowanych binarnie.
Jeżeli selekcja jest przeprowadzana metodą proporcjonalną (opisaną w punkcie 4.4.1),
wówczas można ocenić liczbę reprezentantów rozważanego schematu S w następnym
pokoleniu.
Załóżmy, że w chwili t w populacji
t
V znajduje się
)
(S
t
ξ
=
ξ
osobników pasujących do
schematu S . Po kroku selekcji (metoda proporcjonalna) w chwili
1
+
t
liczba osobników
)
(
1
S
t
+
ξ
pasujących do danego schematu S wyraża się następująco [1, 19 72, 74]
∑
=
+
⋅
⋅
ξ
=
ξ
N
i
i
t
t
t
t
f
S
F
N
S
S
1
1
)
(
)
(
)
(
)
(
x
(4.63)
gdzie
)
(
i
t
f x
jest stopniem przystosowania i-tego osobnika w chwili t , N jest liczbą
osobników w populacji, natomiast
)
(S
F
t
jest średnim stopniem przystosowania schematu S
(osobników pasujących do schematu S ) określanym następująco:
∑
=
=
j
i
i
t
t
f
j
S
F
1
)
(
1
)
(
x
(4.64)
gdzie j oznacza liczbę osobników pasujących do schematu S . Biorąc pod uwagę, że średni
stopień przystosowania całej populacji w chwili t wyraża się wzorem
38
4. Algorytmy ewolucyjne
∑
=
=
N
i
i
t
avg
f
N
t
f
1
)
(
1
)
(
x
(4.65)
równanie (4.63) można przekształcić do postaci
)
(
)
(
)
(
)
(
1
t
f
S
F
S
S
avg
t
t
t
⋅
ξ
=
ξ
+
(4.66)
Zatem liczba reprezentantów
)
(
1
S
t
+
ξ
schematu S po kroku selekcji zmienia się
proporcjonalnie do stosunku średniego stopnia przystosowania schematu
)
(S
F
t
i średniego
stopnia przystosowania całej populacji
)
(t
f
avg
. Mówiąc inaczej, schematy o przystosowaniu
wyższym niż średnie przystosowanie populacji będą miały większą liczbę reprezentantów
w następnym pokoleniu.
Jeżeli założymy, że schemat S ma stopień przystosowania większy od średniego stopnia
przystosowania całej populacji o pewna stałą
ε, tzn.
)
(
)
(
)
(
t
f
t
f
S
F
avg
avg
t
⋅
ε
+
=
(4.67)
wtedy równanie (4.66) można przekształcić do postaci
)
(
)
1
(
)
(
1
S
S
t
t
ξ
⋅
ε
+
=
ξ
+
(4.68)
Poczynając od
0
=
t
i zakładając, że
ε
nie zmienia się w czasie, uzyskujemy zależność
t
t
S
S
)
1
(
)
(
)
(
0
1
ε
+
⋅
ξ
=
ξ
+
(4.69)
Z równania (4.69) wynika zatem eksponencjonalny wzrost liczby reprezentantów schematu S
w następnych pokoleniach.
4.9.2.
Efekt krzyżowania
Rozważmy wpływ krzyżowania jednopunktowego na ewolucję realizowaną w algorytmach
genetycznych. Niech schemat S reprezentuje osobniki haploidalne o chromosomach
(długości
m
) kodowanych binarnie. Dla określenia własności schematu S przy
jednopunktowym krzyżowaniu wprowadza się pojęcia prawdopodobieństwa destrukcji oraz
przeżycia schematu.
Prawdopodobieństwo destrukcji (utraty) schematu S ma postać
1
)
(
)
(
−
δ
=
m
S
S
p
d
(4.70)
Natomiast prawdopodobieństwo przeżycia (zachowania) schematu S wyraża się następująco
1
)
(
1
)
(
−
δ
−
=
m
S
S
p
d
(4.71)
gdzie
)
(S
δ
jest rozpiętością schematu S , zaś
m
jest długością chromosomów pasujących do
schematu S .
39
Przykł. 4.7. Efekt krzyżowania jednopunktowego.
Załóżmy, że do krzyżowania jednopunktowego wybrano parę osobników rodzicielskich,
których chromosomy są kodowane binarnie
[
]
T
1
1
1
0
0
0
|
1
1
0
1
0
0
=
v
(4.72)
[
]
T
2
0
1
0
0
1
|
0
1
0
0
0
1
=
v
(4.73)
oraz rozważmy dwa schematy
[
]
T
1
1
1
#
#
#
|
#
#
#
1
#
#
=
S
(4.74)
[
]
T
2
#
#
#
#
#
|
#
1
0
#
#
#
=
S
(4.75)
gdzie pionowa kreska w chromosomach i schematach oznacza wybrany punkt krzyżowania
leżący między bitem 5 a 6. Osobnik
1
v
pasuje do schematu
1
S
, natomiast do schematu
2
S
pasują oba osobniki rodzicielskie. Schematy charakteryzują się następującymi rzędami i
rozpiętościami:
8
)
(
,
3
)
(
1
1
=
δ
=
ρ
S
S
(4.76)
1
)
(
,
2
)
(
1
1
=
δ
=
ρ
S
S
(4.77)
W rezultacie krzyżowania jednopunktowego generowane są następujące osobniki potomne
[
]
T
'
1
0
1
0
0
1
|
1
1
0
1
0
0
=
v
(4.78)
[
]
T
'
2
1
1
0
0
0
|
0
1
0
0
0
1
=
v
(4.79)
Jak widać, osobniki potomne pasują tylko do schematu
2
S
, inaczej mówiąc schemat
2
S
został
zachowany (przeżył). Z kolei do schematu
1
S
nie pasuje żaden potomek, tzn. został utracony
(zniszczony).
Dla wyżej wymienionych schematów
1
S
i
2
S
prawdopodobieństwa destrukcji i przeżycia
wynoszą odpowiednio
10
2
)
(
,
10
8
)
(
1
1
=
=
S
p
S
p
d
d
(4.80)
10
9
)
(
,
10
1
)
(
2
2
=
=
S
p
S
p
d
d
(4.81)
Uzyskane prawdopodobieństwa wskazują, że większą szansę przeżycia podczas operacji
krzyżowania posiada schemat
2
S
, a przyczyną tego jest jego mała rozpiętość.
Jeśli operacja krzyżowania jest wykonywana z prawdopodobieństwem krzyżowania
c
p
,
wówczas
wzory
(4.70)
i
(4.71)
wyrażające
prawdopodobieństwo
utraty
oraz
prawdopodobieństwo zachowania schematu S przybierają odpowiednio postać nierówności:
1
)
(
)
(
−
δ
⋅
≥
m
S
p
S
p
c
d
(4.82)
40
4. Algorytmy ewolucyjne
1
)
(
)
(
−
δ
⋅
≥
m
S
p
S
p
c
d
(4.83)
4.9.3.
Efekt mutacji
Operacja
mutacji
oznacza
losową
zmianę
wartości
poszczególnych
genów
z
prawdopodobieństwem mutacji
m
p
. Aby schemat S przeżył mutację, ustalone pozycje (geny
o wartościach 0 lub 1) muszą zostać zachowane. Zatem pojedynczy gen przeżywa z
prawdopodobieństwem równym
m
p
−
1
. Ponieważ mutacje na poszczególnych pozycjach są
statystycznie niezależnie, dany schemat S przeżyje mutację z prawdopodobieństwem
równym
)
(
)
1
(
)
(
S
m
s
p
S
p
m
ρ
−
=
(4.84)
Przyjmując małe wartości prawdopodobieństwa mutacji
m
p
(
1
<<
m
p
), określić można
prawdopodobieństwo przeżycia schematu S za pomocą następującego wyrażenia:
m
s
p
S
S
p
m
⋅
ρ
−
≈
)
(
1
)
(
(4.85)
gdzie
)
(S
ρ
jest rzędem schematu S . Prawdopodobieństwa przeżycia schematów z przykł. 4.7
wynoszą odpowiednio:
m
s
p
S
p
m
⋅
−
≈
3
1
)
(
(4.86)
m
s
p
S
p
m
⋅
−
≈
2
1
)
(
(4.87)
4.9.4.
Twierdzenie o schematach
Łącząc wpływ selekcji, krzyżowania i mutacji na oczekiwana liczbę reprezentantów uzyskuje
się następujące pełne równanie schematu [1, 19, 72, 74]
⋅
ρ
−
−
δ
⋅
−
⋅
⋅
ξ
≥
ξ
+
m
c
avg
t
t
t
p
S
m
S
p
t
f
S
F
S
S
)
(
1
)
(
1
)
(
)
(
)
(
)
(
1
(4.88)
Podstawową konkluzją wynikającą z powyższej nierówności jest to, że schematy o małej
rozpiętości, niskiego rzędu i z wyższym stopniem przystosowania uzyskują wykładniczo
rosnącą liczbę reprezentantów w następnych pokoleniach. Wynika stąd, iż osobniki
haploidalne z chromosomami kodowanymi binarnie, które pasują do tychże schematów, są
nieustannie wybierane (selekcja), zestawiane (krzyżowanie), mutowane na pozycjach
nieustalonych schematu oraz powielane, tworząc osobniki o potencjalnie wyższym stopniu
przystosowania. Wniosek ten otrzymał miano twierdzenia o schematach [1, 19, 72, 74]. Na
podstawie tego twierdzenia wysnuto hipotezę, iż algorytm genetyczny poszukuje rozwiązania
optymalnego poprzez „zachowywanie” krótkich schematów niskiego rzędu o wyższym
stopniu przystosowania, które nazwane są blokami budującymi. Dowód powyższej hipotezy
jest oparty głównie na wynikach empirycznych uzyskanych dla szerokiego spektrum
zastosowań GA [1, 19, 72, 74].
Oczywistym jest, iż w toku genetycznej ewolucji populacji, o liczbie osobników N i
długości chromosomów
m
kodowanych binarnie przetwarzaniu podlega co najmniej
m
2 i co
najwyżej
m
N
2
⋅
schematów. Jednak nie wszystkie z nich maja szansę na przetrwanie,
41
ponieważ operacja krzyżowania niszczy schematy o dużej rozpiętości, zaś mutacja niszczy
schematy o wyższym rzędzie. Wykazano, iż (przy względnie długich chromosomach:
2
2
N
m
>
) efektywna liczba schematów przetwarzana w każdym pokoleniu przez algorytm
genetyczny wynosi w przybliżeniu
3
N
. Własność tę nazwano ukrytą równoległością (ang.
implicit parallelism
), ponieważ algorytm genetyczny, mimo działania na zbiorze N
osobników dokonuje przetwarzania
3
N
schematów [1, 19, 72, 74]. Własność ta czyni
algorytmy genetyczne szczególnie atrakcyjnymi w klasie metod optymalizacji.
4.9.5.
Pełny cykl algorytmu genetycznego
Stosując oznaczenia i definicje przedstawione we wcześniejszych punktach, pełny cykl
algorytmu genetycznego w przypadku kodowania binarnego prezentuje proc. 4.4.
Proc. 4.4. GA.
1. wygeneruj losowo z rozkładem równomiernym początkową populację osobników
[
]
N
v
v
v
V
…
2
1
=
(4.89)
gdzie
[
]
T
2
1
i
i
i
N
i
v
v
v
v
…
=
])
100
,
50
[
,
,
,
2
,
1
(
∈
=
N
N
i
…
jest
i
-tym haploidalnym
osobnikiem (chromosomem) w populacji
V
, zaś
i
k
v
)
,
,
2
,
1
(
n
k
…
=
jest losową
sekwencją binarną (odcinkiem chromosomu) o ustalonej długości, kodującą wartość
k
-tego poszukiwanego parametru;
2. zdekoduj genotyp osobnika haploidalnego na odpowiedni jego fenotyp
[
]
T
2
1
i
i
i
N
i
x
x
x
x
…
=
(4.90)
gdzie
,
,
,
2
,
1
,
2
1
2
0
n
k
v
x
x
x
x
k
ij
k
i
m
j
j
k
m
k
k
k
k
…
=
−
−
+
=
∑
=
(4.91)
jest
k
-tą współrzędną fenotypu
i
x
, przedział
[
]
ℜ
∈
k
k
x
,
x
jest jej dziedziną, zaś
k
m
oznacza długość sekwencji
i
k
v
kodującej współrzędną
i
k
x
;
3. wyznacz stopień przystosowania
ℜ
∈
)
(
i
f x
każdego osobnika:
• w przypadku, gdy funkcja celu jest funkcją kosztu
)
( x
u
)
(
)
(
max
i
i
u
C
f
x
x
−
=
(4.92)
gdzie współczynnik
max
C
jest równy maksymalnej wartości
)
(
i
u x
w aktualnej
populacji,
• w przypadku funkcji zysku
)
( x
g
, gdy jej przeciwdziedzina jest określona na
zbiorze liczb rzeczywistych dodatnich i ujemnych,
42
4. Algorytmy ewolucyjne
min
)
(
)
(
C
g
f
i
i
−
=
x
x
(4.93)
gdzie współczynnik
min
C
jest równy minimalnej wartości
)
(
i
g x
w aktualnej
populacji;
4. jeżeli ustalona liczba pokoleń (iteracji) jest osiągnięta to zakończ algorytm i wyznacz
z aktualnej populacji najlepszego osobnika, tzn. osobnika o najwyższym stopniu
przystosowania. W przeciwnym wypadku przejdź do kroku 5);
5. przeskaluj stopnie przystosowania osobników według metody skalowania liniowego:
• znajdź w aktualnej populacji osobnika o maksymalnym i minimalnym stopniu
przystosowania
)
(
max
}
,
,
2
,
1
{
i
N
i
max
f
f
x
…
∈
=
(4.94)
)
(
min
}
,
,
2
,
1
{
i
N
i
min
f
f
x
…
∈
=
(4.95)
• wyznacz średnie przystosowanie populacji
∑
=
=
N
i
i
avg
f
N
f
1
)
(
1
x
(4.96)
• przeskaluj stopnie przystosowania osobników według formuły
b
af
f
i
i
s
+
=
)
(
)
(
x
x
(4.97)
gdzie
a
i
b
oznaczają współczynniki skalowania liniowego, których wartości
wyznaczane są następująco:
•• jeżeli warunek skalowania
1
−
−
>
c
f
cf
f
max
avg
min
(4.98)
•• jest spełniony to wyznacz współczynniki skalowania
)
2
(
=
c
)
1
(
,
)
1
(
+
−
=
−
−
=
a
f
b
f
f
c
f
a
avg
avg
max
avg
(4.99)
••
w przeciwnym przypadku wyznacz współczynniki skalowania według
wzorów
min
min
avg
avg
af
b
f
f
f
a
−
=
−
=
,
(4.100)
6. wyselekcjonuj pulę rodzicielską
p
V
z populacji osobników
V
według metody ze
stochastycznym doborem resztowym:
• wyznacz oczekiwaną liczbę kopii osobników z populacji
43
N
i
N
f
f
e
N
i
i
i
i
,
,
2
,
1
,
)
(
)
(
)
(
1
…
=
⋅
=
∑
=
x
x
x
(4.101)
• skopiuj
∑
=
=
N
i
i
e
N
1
int
)
( x
osobników do puli rodzicielskiej na podstawie ich
całkowitych częściach liczby
)
(
i
e x
, oraz określenie liczby ‘wakatów’
int
~
N
N
N
−
=
• wyznacz dystrybuanty osobników według resztowej części
)
(
i
e x
{
}
∑
=
−
=
i
j
j
j
i
e
e
q
1
)
(
)
(
)
(
x
x
x
(4.102)
•
N
~
-krotne ‘zakręć kołem ruletki’ poprzez
N
~
-krotne:
•• wygenerowanie losowej liczby
[ ]
1
,
0
∈
r
•• wyznaczenie pierwszego napotkanego osobnika w populacji, dla
którego spełniony jest warunek
)
(
)
(
N
i
q
q
r
x
x
≤
(4.103)
•• skopiowanie znalezionego osobnika do puli rodzicielskiej;
7. wyselekcjonuj pulę rodzicielską
p
V
z populacji osobników
V
według metody ze
stochastycznym doborem resztowym:
• wylosowanie pary rodziców, a następnie wykonanie na nich krzyżowania
jednopunktowego z prawdopodobieństwem krzyżowania
]
1
,
6
.
0
[
∈
c
p
przez:
•• wygenerowanie liczby
]
1
,
0
[
∈
r
z rozkładem równomiernym dla każdej
pary rodziców
•• skrzyżowanie pary jeżeli
c
p
r
≤
: tzn. wylosowanie punktu krzyżowania
c
j
należącego do dyskretnego przedziału
]
1
,
1
[
−
m
, gdzie
m
jest
długością chromosomu, i zamianę miejscami części chromosomów
wylosowanej pary rodzicielskiej począwszy od bitu
1
+
c
j
do bitu
m
włącznie,
• przeprowadzenie mutacji binarnej z ustalonym prawdopodobieństwem
mutacji:
•• wygenerowanie liczby
]
1
,
0
[
∈
r
z rozkładem równomiernym dla
każdego genu,
44
4. Algorytmy ewolucyjne
•• mutacja jeżeli
m
p
r
≤
: tzn. zanegowanie danego bitu (zwykle
m
p
równe jest odwrotności liczby osobników populacji);
8. zastąp ‘starą’ populację nowo powstałą populacją potomków
'
V
według strategii z
pełną reprodukcją, tzn.:
'
V
V
←
i powróć do kroku 2).
4.10.
Podsumowanie
W niniejszym rozdziale przedstawiono podstawy konstrukcji algorytmów genetycznych jako
narzędzi optymalizacji stochastycznej. Cechą charakterystyczną GA jest prowadzenie
poszukiwań w wielu punktach. W zaimplementowanym sztucznym procesie ewolucji
parametry zadania optymalizacji posiadają postać zakodowaną. Natomiast do wyboru i
tworzenia nowych rozwiązań stosuje się reguły probabilistyczne. Jak zauważono powyżej
metody ewolucyjnej optymalizacji korzystają jedynie z łatwo wyznaczalnej wartości funkcji
celu. Wolne są zatem od wielu ograniczeń nakładanych zwykle na funkcje kryterialne, tj:
ciągłość, istnienie pochodnych, unimodalność, itp. Te i inne udogodnienia realizacyjne czynią
algorytmy ewolucyjne szczególnie atrakcyjnymi implementacyjne.
Ponadto wyjaśniono terminologię genetyczną wraz ze stosowanymi oznaczeniami oraz
podany został opis podstawowych procedur GA z uwzględnieniem techniki tworzenia nisz
pomocnej
w
rozwiązywaniu
zadań
wielokryterialnej
optymalizacji.
Dodatkowo
zaprezentowano numeryczne algorytmy realizacji owych procedur.