Algorytmy ewolucyjne.cz4

[ Pobierz całość w formacie PDF ]
1
Algorytmy ewolucyjne
Wprowadzenie
Inspiracją do podjęcia badań dotyczących algorytmów
ewolucyjnych
było
naśladowanie natury
w zakresie zjawisk
na gruncie genetyki (przekazywanie korzystnych cech
potomstwu poprzez krzyżowanie i mutacje).
Idea ta została wykorzystana do rozwiązywania
zagadnień
optymalizacyjnych
. Mówiąc najprościej – poszukiwanie
takich rozwiązań oparte jest o zasadę, że spośród rozwiązań,
które dziedziczą pewne cechy po swoich rodzicach,
„przeżywają” tylko te rozwiązania, które są najlepiej
przystosowane.
Klasyczne metody optymalizacji
Klasyczne metody poszukiwania optymalnych rozwiązań
dzielą się na: metody analityczne, przeglądowe, oraz losowe.
W
metodach analitycznych
poszukujemy lokalnych
ekstremów funkcji rozwiązując układy równań (zwykle
nieliniowych). Metody te maja liczne wady – są złożone, nie
zawsze dadzą się zastosować, często „utykają” w lokalnych
ekstermach funkcji.
Metody przeglądowe
polegają, mówiąc w uproszczeniu, na
obliczaniu wartości funkcji celu w całej przestrzeni
poszukiwań po kolei. Oczywiście dla dużych przestrzeni jest
to bardzo nieefektywne i często po prostu niemożliwe.
Metody losowe
polegają na losowym przeszukiwaniu
przestrzeni rozwiązań i zapamiętywaniu otrzymanych
wyników, z których potem wybiera się najlepsze. Są one
również mało efektywne.
2
Idea algorytmów ewolucyjnych
Są to algorytmy oparte na mechanizmach
doboru
naturalnego
i
dziedziczenia
. Korzystają z ewolucyjnej zasady
przeżycia osobników najlepiej dostosowanych.
Główne cechy algorytmów ewolucyjnych, to:

Wyjście do przeszukiwania nie z pojedynczego punktu
przestrzeni poszukiwań, lecz z pewnej ich populacji,

Przetwarzanie nie bezpośrednio parametrów zadania,
lecz pewnej zakodowanej postaci tych parametrów,

Losowy wybór jest tu tylko pewnym narzędziem, a nie
zasadniczą ideą przeszukiwania, jak w klasycznych
metodach losowych.
Podstawowe pojęcia:

Populacja
jest określonym zbiorem osobników,

Osobnikiem
jest zakodowany w postaci chromosomu
zbiór parametrów zadania,

Chromosom
to uporządkowany ciąg genów,

Gen
jest cechą, pojedynczym elementem genotypu,

Genotyp
to zespół chromosomów danego osobnika
(chociaż często jest to po prostu pojedynczy
chromosom),

Fenotyp
to zdekodowana struktura, czyli po prostu
zbiór parametrów zadania.
Bardzo ważnym pojęciem jest
funkcja przystosowania
,
zwana również
funkcją dopasowania
, lub
funkcją oceny
.
Pozwala ona ocenić
stopień dopasowania
danego osobnika w
populacji i w ten sposób wybrać osobniki najlepiej
przystosowane ( o największej wartości funkcji dopasowania)
zgodnie z ewolucyjną zasadą przetrwania „najsilniejszych”. W
teorii sterowania funkcją przystosowania może być
funkcja
3
błędu,
którą się minimalizuje. W teorii gier –
funkcja kosztu
,
podlegająca również minimalizacji.
W algorytmie ewolucyjnym w każdej jego iteracji, ocenia się
przystosowanie każdego osobnika danej populacji za pomocą
funkcji przystosowania i na tej podstawie tworzy nową
populację osobników, stanowiących zbiór potencjalnych
rozwiązań problemu.
Klasyczny algorytm genetyczny
START
INICJACJA – wybór początkowej
populacji chromosomów
OCENA przystosowania
chromosomów w populacji
Nie Tak
warunek
Wyprowadzenie „najlepszego
chromosomu
Zastosowanie operatorów
genetycznych
STOP
Utworzenie nowej populacji
SELEKCJA chromosomów
4
Rys. 16. Schemat blokowy klasycznego algorytmu
genetycznego
Inicjacja
(utworzenie populacji początkowej) polega na
losowym wyborze żądanej liczby chromosomów (osobników)
reprezentowanych przez ciągi binarne o określonej długości.
Ocena przystosowania
osobników z populacji polega na
obliczeniu wartości funkcji przystosowania dla każdego
chromosomu z populacji.
Sprawdzenie warunków zatrzymania
. Zależą one od
konkretnego zadania. Najczęściej jest to:
-
osiągnięcie żądanej wartości optymalnej,
-
osiągnięcie wartości optymalnej z określoną
dokładnością,
-
przekroczenie ustalonego czasu działania
algorytmu,
-
wykonanie obliczeń dla żądanej liczby generacji.
Selekcja chromosomów
polega na wybraniu na podstawie
wartości funkcji przystosowania, tych chromosomów, które
będą brały udział w tworzeniu następnego pokolenia.
Najbardziej popularną metodą selekcji jest
metoda ruletki
.
W wyniku procesu selekcji zostaje utworzona
populacja
(pula) rodzicielska
o liczebności zazwyczaj takiej, jak
liczebność bieżącej populacji.
Operatory genetyczne
Zastosowanie
operatorów genetycznych
do chromosomów
wybranych metodą selekcji prowadzi do utworzenia nowej
5
populacji, która jest populacją potomków, otrzymanej z
populacji rodziców.
W klasycznym algorytmie genetycznym stosuje się dwa
podstawowe operatory genetyczne:
operator krzyżowania
i
operator mutacji
. W klasycznym algorytmie genetycznym
krzyżowanie występuje prawie zawsze (z prawdopodo-
bieństwem
p
k
,
które zwykle zawiera się w przedziale [
0.5,1
]),
podczas, gdy mutacja zachodzi dość rzadko (z prawdo-
podobieństwem
p
m
zwykle nie większym niż
0.1
). Wynika to
także z analogii do świata organizmów żywych, gdzie mutacje
zachodzą niezwykle rzadko.
W algorytmach genetycznych mutacje stosuje się zarówno na
populacji rodziców przed operacją krzyżowania, jak i na
populacji potomków, utworzonych w wyniku krzyżowania.
Przykład operacji krzyżowania i mutacji
Weźmy dwa chromosomy
ch
1
i
ch
2
majce po
10
genów.
Stanowić one będą parę rodzicielską. W celu przeprowadzenia
krzyżowania
wylosujmy liczbę z przedziału
[1,9]
.
Wylosowano
5
.
para rodziców krzyżowanie para potomków
ch
1
=[
10010
|
01100
] Ch
1
=[
10010
|
11110]
ch
2
=[10011
|
11110] Ch
2
=[10011
|
01100
]
Omówmy teraz przykład rozwiązania problemu
mutacji
.
W tym celu losujmy liczbę rzeczywistą z przedziału
[0,1]
dla
każdego z dziesięciu genów. Wylosowano:
0.23 0.76 0.54 0.10 0.28 0.68
0.01
0.30 0.95 0.12
Przyjmijmy, że
p
m
=0.02
. Do mutacji zostaną wybrane tylko
te geny, dla których wylosowana liczba jest
<= p
m
– u nas gen
siódmy.
[ Pobierz całość w formacie PDF ]