Algorytmy Ewolucyjne
Radosław Winiczenko
Wydział Inżynierii Produkcji, SGGW
radosław_winiczenko@sggw.pl
Algorytmy Ewolucyjne
Radosław Winiczenko
Wydział Inżynierii Produkcji, SGGW
radosław_winiczenko@sggw.pl
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Ę