Algorytmy Ewolucyjne

Radosław Winiczenko

Wydział Inżynierii Produkcji, SGGW

radosł[e-mail]

2

Literatura

1.

J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT,

Warszawa, 2001.

2.

D. E. Goldberg, Algorytmy genetyczne i ich zastosowania,
WNT, Warszawa, 1998.

3.

Melanie Mitchell, ,,An introduction to genetic algorithms”,

MIT press, 1999

4.

Z. Michalewicz, Algorytmy genetyczne + struktury danych =

programy ewolucyjne, WNT, Warszawa, 1996

5.

M. D. Vose, The simple genetic algorithm. Foundations and

theory, MIT Press, Cambridge, Massachusetts, 1999.

6.

D. Rutkowska, M.Piliński, L. Rutkowski, Sieci neuronowe,

algorytmy genetyczne i systemy rozmyte”, PWN, Warszawa

1997.

3

Definicja algorytmów ewolucyjnych

Algorytmy ewolucyjne (ang. Evolutionary
Algorithms EA) są algorytmami przetwarzania,
które rozwiązują zadania optymalizacyjne i
zadania poszukiwania wykorzystując darwinowską
strategię

przetrwania

osobników

najlepiej

przystosowanych.

Modele algorytmów ewolucyjnych opierają się na
zasadzie działania rzeczywistego mechanizmu
ewolucyjnego.

4

Podział algorytmów ewolucyjnych

W grupie algorytmów ewolucyjnych należy
wyróżnić trzy podstawowe metody
optymalizacyjne:



algorytmy genetyczne

,



programowanie ewolucyjne

 strategie ewolucyjne.

Każda z tych metod kładzie nacisk na inną cechę
naturalnej

ewolucji.

Algorytmy

genetyczne

uwypuklają

rolę

operatorów

genetycznych.

Programowanie ewolucyjne

kładzie nacisk na

zmiany behawioralne na poziomie gatunków. W

strategiach

ewolucyjnych

najistotniejsze

są

zmiany behawioralne na poziomie osobników.

5

Pomimo tych różnic każda z tych powyższych

metod realizuje, na abstrakcyjnym
poziomie algorytmu, zasady wynikające z
praw jakimi otacza nas natura, mianowicie:



poszukiwanie rozwiązań poprzez procesy
ewolucji,



dziedziczenie informacji poprzez
pojedyncze rozwiązania w kolejnych
pokoleniach



wymianie informacji w pojedynczym
rozwiązaniu poprzez ich krzyżowanie bądź
ich mutację



selekcjonowanie pojedynczych rozwiązań

6

Historia algorytmów genetycznych



Sieci neuronowe a algorytmy genetyczne –

cele i różnice

Idea powstania algorytmów genetycznych



Lata 60/70 –John Holland - ”ewolucja

zachodzi na chromosomach, a nie na żywych

istotach”



1985- Goldberg - doktorant Hollanda

zastosowanie-Optymalizacja pracy gazociągu

7

Zastosowanie algorytmów

ewolucyjnych



programowanie komputerów



sztuczna inteligencja



optymalizacja kosztów, konstrukcji, procesów
produkcyjnych, minimalizacja błędów,



planowaniu i harmonogramowaniu zadań



w sterowaniu procesów



sztuczne sieci neuronowe-współpraca



projektowanie obwodów elektrycznych



prognozowanie na giełdzie



prognozowanie właściwości mechanicznych stali

8



Algorytmy a tradycyjne metody optymalizacji   

Algorytm genetyczny stanowi wzorowana na naturalnej
ewolucji metodę rozwiązywania problemów, głównie
zagadnień optymalizacyjnych.

Od tradycyjnych metod optymalizacji różnią się kilkoma
zasadniczymi elementami. Otóż algorytmy genetyczne:

1) nie przetwarzają bezpośrednio parametrów zadania,

lecz ich zakodowana postać,

2) prowadza przeszukiwanie, wychodząc nie z

pojedynczego punktu, lecz z pewnej ich populacji,

3) korzystają tylko z funkcji celu, nie zaś z jej

pochodnych lub innych pomocniczych informacji,

4) stosują probabilistyczne, a nie deterministyczne

reguły wyboru.

9

Podstawowe pojęcia algorytmów ewolucyjnych:

Populacja

- zbiór osobników o określonej liczebności

Osobniki

-zakodowane w postaci chromosomów punkty

przestrzeni poszukiwań czyli rozwiązania

Chromosomy

-łańcuchy lub ciągi kodowe-uporządkowane

ciągi genów

Gen

- cecha, znak, detektor-pojedynczy element genotypu,

chromosomu

Genotyp

- zespół chromosomów danego osobnika

Fenotyp

- zestaw wartości odpowiadającej danemu

genotypowi, zdekodowana strukturą, rozwiązaniem,
punktem przestrzeni poszukiwań

Allel

- wartość danego genu

Locus

- pozycja, wskazująca miejsce położenia danego

genu w łańcuchu, czyli chromosomie

10

Funkcja przystosowania

(ang. fitness function)

jest to funkcja dopasowania lub funkcja oceny.

Ma duży wpływa na działanie algorytmów
genetycznych. Musi być odpowiednio zdefiniowana.
Może to być funkcja maksymalizowana lub
minimalizowana



w teorii sterowania - funkcja przystosowania może

być

funkcja błędu



w teorii gier - funkcja przystosowania to

funkcja

kosztu

Kolejną iterację a algorytmie genetycznym nazywa
się

generacją

a nowa utworzona populacja

osobników to nowe pokolenie lub

pokolenie

potomków

11

Rys. Etapy działania klasycznego algorytmu genetycznego

Inicjacja

N

k

Obliczenie

funkcji

przystosowania

Sprawdzenie

warunku

zatrzymania

krzyżowania i

mutacja

Wyprowadzenie

najlepszego
rozwiązania

Utworzenie

nowego

pokolenia N

(k+1)

Selekcja

chromosomów

TAK

NIE

12

Etapy działania klasycznego algorytmu genetycznego

Etap 1. Inicjacja jest związana z uruchomieniem algorytmu
genetycznego poprzez utworzenie populacji początkowej.
Polega ona na losowym wyborze żądanej liczby
chromosomów o określonej długości. Długość poszczególnych
chromosomów

będzie

zależała

od

skali

trudności

rozwiązywanego problemu.

Etap 2. Ocena przystosowania. Polega na obliczeniu
wartości funkcji przystosowania (ang. fitness function) dla
każdego chromosomu. Im większa jest wartość tej funkcji,
tym lepsza „jakość” chromosomu. Zakłada się, że
rozwiązywany problem optymalizacji jest problemem
poszukiwania maksimum tej funkcji a funkcja przystosowania
przyjmuje zawsze wartości nieujemne.

13

Etapy działania klasycznego algorytmu genetycznego

Etap 3. Sprawdzenie warunku zatrzymania.

Jeśli w optymalizowanym zagadnieniu znana jest

wartość funkcji przystosowania to zatrzymanie algorytmu
genetycznego może nastąpić w następujący sposób:



po uzyskaniu żądanej wartości optymalnej (lub z określoną

dokładnością)



jeśli dalsze działanie nie poprawia uzyskanej najlepszej

wartości



po upływie określonego czasu



po określonej liczbie iteracji

Jeśli warunek zatrzymania jest spełniony to następuje
podanie „najlepszego” rozwiązania. Jeśli nie, to następnym
etapem jest selekcja chromosomów.

14

Etapy działania klasycznego algorytmu genetycznego

Etap 4. Selekcja chromosomów

Selekcja chromosomów polega na wybraniu, na

podstawie obliczonych wartości funkcji przystosowania
chromosomów, które będą brały udział w tworzeniu nowych
potomków.

Wybór ten odbywa się zgodnie z z zasadą naturalnej

selekcji, czyli największe szanse w tworzeniu nowych
potomków będą miały chromosomy o największej wartości
funkcji przystosowania.

Istnieje wiele metod wyboru chromosomów. Najbardziej
znane to metoda ruletki, rankingowa oraz metoda turniejowa.

W wyniku procesu selekcji zostaje utworzona populacja

rodzicielska, nazywana także pulą rodzicielską (ang. mating
pool) o liczebności równej N, tzn. takiej samej jak liczebność
bieżącej populacji.

15

Etapy działania klasycznego algorytmu genetycznego

Etap 5. Zastosowanie operatorów genetycznych.



Operator krzyżowania (ang. crossover) pozwala nam

utworzyć dwa zupełnie inne chromosomy potomków poprzez
kombinację materiału genetycznego pary rodziców. W
klasycznym algorytmie genetycznym wystepuję prawie
zawsze a jego prawdopodobieństwo przyjmuje się zwykle
duże w zakresie 0,5≤ pc≤1.

Para rodziców (przed krzyżowaniem) Para potomków (po
krzyżowaniu

1 0 0 1 0 0 1

1 0 0 1 1 0 0

0 1 1 0 1 0 0

0 1 1 0 0 0 1

Rys. Przykład zastosowania operatora krzyżowania w
chromosomach składających się z siedmiu genów.
(Krzyżowanie jednopunktowe z miejscem krzyżowania lk=4).

16

Etapy działania klasycznego algorytmu genetycznego



Operator mutacji (ang. mutation).

Operator ten jest elementem reprodukcji, która może

powodować zmianę w pojedynczych chromosomach. W
klasycznym algorytmie genetycznym mutacja występuję dość
rzadko. Dlatego prawdopodobieństwo zaistnienia jej
przyjmuje się na ogół 0≤p

m

≤0,1. Wynika to przede

wszystkim z faktu, że mutacje w świecie organizmów żywych
zachodzą niezwykle rzadko.

Mutacja która dokonuje się z prawdopodobieństwem

pm polega na zamianie wartości genu w chromosomie na
przeciwną (tzn. z 0 na 1 lub z 1 na 0).

chromosom przed mutacją chromosom po mutacji

1 0 0 1

1

0 0

1 0 0 1

0

0 0

Rys. Przykład mutacji chromosomu o ośmiu genach. Mutacji
dokonano na genie na piątej pozycji.

17

Etapy działania klasycznego algorytmu genetycznego

Etap 6. Wyprowadzenie najlepszego chromosomu.

Jeśli warunek zatrzymania jest już spełniony

należy podać rozwiązanie problemu. Najlepszym
rozwiązaniem będzie chromosom o „najlepszej” wartości
funkcji przystosowania.

18

Przykład 1.

Dana jest funkcja f(x)=2*x

2

+1 z przedziału x €

(O;15).

Zadanie polega na przeszukaniu przestrzeni złożonej

z 16 pkt i znalezieniu spośród wartości 0,1,,,15 dla
której funkcja przyjmuje wartość maksymalną (lub
minimalną)

Wartość parametru x można zakodować następująco.

(Jest to kodowanie binarne czyli zapis liczb
dziesiętnych w systemie dwójkowym)

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

19

Przykład 1.

Przykład populacji o liczebności 6.

Jest to zbiór

Chromosomów: 0010 0101

0111 1001 1100

1110

Fenotypy:

2

5

7

9

12

14

Kodowanie binarne w systemie dwójkowym

Ciąg binarny [

1 0 0 1 1

] jest kodem liczby 19

ponieważ

1

*2

4

+

0

*2

3

+

0

*2

2

+

1

*2

1

+

1

*2

0

=19

20

Przykład 2.

Należy znaleźć chromosom o możliwie największej

liczbie jedynek.

[11111111111111]

Założenia: chromosomy składają się z 12 genów a

populacja liczy 8 chromosomów.

Rozwiązanie-najlepszy chromosom będzie składał się

z 12 jedynek.

21

Etap1. Inicjacja

Polega na losowym doborze chromosomów do

populccji np. rzut 96 razy monetą)

ch

1

=[111001100101]

ch

5

=[010001100100]

ch

2

=[001100111010]

ch

6

=[010011000101]

ch

3

=[011101110011]

ch

7

=[101011011011]

ch

4

=[001000101000]

ch

8

=[000010111100]

22

Etap 2.

Ocena przystosowania chromosomów w

populacji (ilość jedynek)

F(ch

1

)=7

F(ch

5

)=4

F(ch

2

)=6

F(ch

6

)=5

F(ch

3

)=8

F(ch

7

)=8

F(ch

4

)=3

F(ch

8

)=5

23

Etap 3. Selekcja chromosomów metodą ruletki

V(ch

i

)=p

s

(ch

i

)*100%

ps(ch

i

)=F(ch

i

)/suma F(ch

i

)

v(ch

1

)=15,22

v(Ch

5

)=8,70

v(ch

2

)=13,04

v(Ch

6

)=10,87

v(ch

3

)=17,39

v(Ch

7

)=17,39

v(ch

4

)=6,52

v(Ch

8

)=10,89

Losowanie sprowadza się do losowego wyboru liczby z

przedziału [0;100]

Założenie. Wylosowano 8 następujących liczb:

79 44 9

74

44

86

48

23

Oznacza to wybór następujących chromosomów:

ch

7

ch

3

ch

1

ch

7

ch

3

ch

7

ch

4

ch

2

Powyższe chromosomy wchodzą do puli rodzicielskiej

24

Etap 4. Zastosowanie operatorów

genetycznych

Założenia

Prawdopodobieństwo krzyżowania

p

c

=1

,

Prawdopodobieństwo mutacji

p

m

=0

losowy dobór rodziców:

ch

2

i ch

7

ch

1

i ch

7

ch

3

i ch

4

ch

3

i ch

7

;

losowy dobór punktów krzyżowania (locus):

l

k

=4, l

k

=3,

l

k

=11 oraz l

k

=5,

25

Etap 4. Zastosowanie operatorów

genetycznych cd..

I para rodziców

I para potomków

ch

1

=[111001100101]

ch

5

=[010001100100]

ch

2

=[001100111010]

ch

6

=[010011000101]

l

k

=4

II para rodziców

II para potomków

ch

3

=[011101110011]

ch

7

=[101011011011]

ch

4

=[001000101000]

ch

8

=[000010111100]

l

k

=3

następnie dla ch

3

i ch

4

l

k

=11 oraz ch

3

i ch

7

l

k

=5

26

Etap 5. Utworzenie nowej populacji

ch

1

=[001111011011]

ch

5

=[011101110010]

ch

2

=[101000111010]

ch

6

=[001000101001]

ch

3

=[111011011011]

ch

7

=[011101011011]

ch

4

=[101001100101]

ch

8

=[101011110011]

i powrót do etapu 2, czyli ocena funkcji

przystosowania

potomkowie

rodzice

F(ch

1

)=8 F(ch

5

)=7

F(ch

1

)=7 F(ch

5

)=4

F(ch

2

)=6

F(ch

6

)=4

F(ch

2

)=6

F(ch

6

)=5

F(ch

3

)=9

F(ch

7

)=8

F(ch

3

)=8

F(ch

7

)=8

F(ch

4

)=6

F(ch

8

)=8

F(ch

4

)=3

F(ch

8

)=5

27

Szczególne procedury reprodukcji

Strategia elitarna – (ang. elitist strategy) polega
na ochronie najlepszych chromosomów w kolejnych
iteracjach.

W klasycznym algorytmie genetycznym najlepiej
przystosowane osobniki nie zawsze przechodzą do
następnej generacji. Nie zawsze nowa populacja
(Pk+1) zawiera chromosom o największej wartości
funkcji przystosowania z populacji P(k).

Strategia ta stosowana jest w celu zabezpieczenia
przed utratą takiego osobnika. Jest on zawsze
włączony do następnej populacji.

Przedstawicielem takiej strategii jest mikroalgorytm
genetyczny.

28

z ustalonym stanem – (ang. steady state)

Jest to algorytm genetyczny z częściową wymianą
populacji (z ustalonym stanem). Charakteryzuje się
tym, że część populacji przechodzi do następnej
generacji bez jakichkolwiek zmian. Oznacza to, że
część populacji nie podlega krzyżowaniu i mutacji.
Często w konkretnej implementacji tego typu
algorytmu tylko jeden lub dwa osobniki są
wymieniane w danej chwili zamiast zastosowania
operatorów: krzyżowania i mutacji w obrębie całej
populacji.

W niektórych programach do optymalizacji możemy
sami określić jaki procent całej populacji, który jest
wybierany na podstawie funkcji przystosowania
wchodzi bez jakichkolwiek zmian do następnej
populacji.

29

Mikroalgorytm genetyczny –

Jest

modyfikacją

klasycznego

algorytmu

genetycznego,

który

służy

do

rozwiązania

problemów nie wymagających dużych populacji i
długich chromosomów.

Zastosowanie - w przypadku ograniczenia czasu
obliczeniowego a rozwiązanie potrzebujemy szybko i
niekoniecznie musi to być optimum globalne.

Cechy

charakterystyczne

mikroalgorytmu

genetycznego:



rozmiar populacji jest bardzo mały i ustalony



stosuje się strategie elitarną (co zapobiega utracie

dobrego chromosomu)

30



populacja jest mała, czyli selekcja odbywa się w sposób

deterministyczny



krzyżowanie jest z prawdopodobieństwem 1



nie ma mutacji, ponieważ wystarczająca

różnorodność wprowadza się przez wybór nowej
populacji po każdym restarcie algorytmu w celu
uniknięcia przedwczesnej zbieżności

Głównym celem mikroalgorytmu genetycznego jest
znalezienie rozwiązania optymalnego lub prawie
optymalnego tak szybko jak to możliwe.

31

Metody selekcji



Selekcja koła ruletki –(ang. roulette wheel

selection)

Metoda ta swoją nazwę zawdzięcza

analogii do losowania za pomocą koła
ruletki. Metoda polega ta na przydzieleniu
dla każdego chromosomu wycinka koła
ruletki o wielkości proporcjonalnej do
wartości

funkcji

przystosowania

poszczególnego chromosomu.

Im większa jest wartość funkcji

przystosowania tym większy wycinek
(obszar) zajmuje na kole ruletki.

Całe koło ruletki jest sumą wartości

funkcji

przystosowania

wszystkich

chromosomów w populacji. Oznacza to, że
każdemu chromosomowi chi dla i =1,2,
…,M, gdzie N jest liczebnością populacji,
odpowiada wycinek koła v(chi) stanowiący
część całego koła i wyrażony jest w
procentach zgodnie z poniższym wzorem

32

Metody selekcji



Selekcja koła ruletki –(ang. roulette

wheel selection)

v(ch

i

)=p

s

(ch

i

)*100% ;

p

s

(ch

i

)=

gdzie F(ch

i

) oznacza wartość funkcji

przystosowania chromosomu chi, p

s

(ch

i

)

jest

prawdopodobieństwem

selekcji

chromosomu ch

i

. Selekcja metodą ruletki

polega na obrocie koła ruletki, w wyniku
czego zostaje wybrany chromosom
należący do wylosowanego w ten sposób
pola koła ruletki.





N

i

chi

F

chi

F

1

)

(

)

(

33

Metoda

ruletki

–

prawdopodobieństwo

wyboru

osobnika

proporcjonalne

do

wartości

FP

FP

= funkcja przystosowania

Metody selekcji…

34



Selekcja

rankingowa

–

(ang.

ranking

selection)

Osobniki populacji są ustawione kolejno w

zależności od wartości ich funkcji przystosowania.
Jest to lista rankingowa osobników
uszeregowanych od najlepiej do najgorzej
przystosowanych (lub odwrotnie), gdzie każdemu
osobnikowi przypisana jest liczba określająca jego
kolejność na liście i nazwana jest rangą (ang.
rank).

Liczba kopii każdego osobnika, wprowadzanych
do puli rodzicielskiej M(k), jest ustalana zgodnie z
wcześniej zdefiniowaną funkcją.

35

Metoda rankingowa

ranga

ilość
kopii

Rys. Funkcja określająca zależność liczby kopii
osobnika w puli rodzicielskiej od jego rangi w
selekcji rankingowej

36

Metody selekcji

Metoda turniejowa – (ang. tournament
selection)

Zastosowanie - metoda turniejowa nadaje się
do problemów maksymalizacji jak i
minimalizacji. Szczególnie wykorzystuje się ją
do optymalizacji kilku funkcji jednocześnie.
Badania wykazały, iż metoda turniejowa
działa lepiej niż metoda ruletki.

W selekcji turniejowej dzieli się osobniki
populacji na podgrupy, następnie z nich
wybiera się osobnika o najlepszym
przystosowaniu. Wybór ten może być:



wyborem

deterministycznym,

który

dokonuje

się

z

prawdopodobieństwem

równym 1



wyborem stochastycznym (losowym), który

jest

wyborem

z

prawdopodobieństwem

mniejszym od 1.

37

Metoda turniejowa cd..

Podgrupy mogą być dowolnego rozmiaru
ale najczęściej dzieli się populacje na
podgrupy składające się z 2 lub 3
osobników.

N osobników

populacji P(k)

2 osobniki

2 osobniki

1

”najlepszy

” osobnik

1

”najlepszy

” osobnik

Pula

rodzicielska

M(k);

N osobników

Rys. Przykład metody turniejowej z dwoma podgrupami

38

1. Problem optymalizacji globalnej

– analityczne

– numeryczne (np. gradientowe)

– enumeracyjne

Metody klasyczne

Jak znaleźć

globalne maksimum

(globalne minimum)

– błądzenie przypadkowe

– symulowane wyżarzanie

– sieci neuronowe

– logika rozmyta

– algorytmy genetyczne

Nowe metody

f(x)

x

maksimum globalne

maksimum
lokalne

?

39

FP

maksimum globalne

1. pokolenie

2. pokolenie

itd.

Ewolucja – dążenie do optymalnego

40



Algorytmy a tradycyjne metody optymalizacji   

Algorytm genetyczny stanowi wzorowana na naturalnej
ewolucji metodę rozwiązywania problemów, głównie
zagadnień optymalizacyjnych.

Od tradycyjnych metod optymalizacji różnią się kilkoma
zasadniczymi elementami. Otóż algorytmy genetyczne:

1) nie przetwarzają bezpośrednio parametrów zadania,

lecz ich zakodowana postać,

2) prowadza przeszukiwanie, wychodząc nie z

pojedynczego punktu, lecz z pewnej ich populacji,

3) korzystają tylko z funkcji celu, nie zaś z jej

pochodnych lub innych pomocniczych informacji,

4) stosują probabilistyczne, a nie deterministyczne

reguły wyboru.

41

DZIĘKUJE ZA

UWAGĘ