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.