Algorytmy ewolucyjne
Wprowadzenie
Algorytmy ewolucyjne - są to algorytmy, które opierają swoje działanie na genetyce (przekazywanie korzystnych cech potomstwu poprzez krzyżowanie i mutacje).
Są one wykorzystywane do rozwiązywania zagadnień optymalizacyjnych (czyli poszukiwania tych rozwiązań, które dziedziczą cechy po swoich rodzicach i „przeżywają”, ponieważ są najlepiej przystosowane).
Klasyczne metody optymalizacji
Klasyczne metody poszukiwania optymalnych rozwiązań dzielimy na : metody analityczne, przeglądowe, oraz losowe.
Metody analityczne - poszukiwane są lokalne ekstrema funkcji rozwiązując układy równań (zwykle
nieliniowych). Metody te mają swoje wady - są złożone i nie zawsze dadzą się zastosować.
Metody przeglądowe - polegają na obliczaniu wartości funkcji jakiegoś celu w całej przestrzeni po kolei.
Dla dużych przestrzeni jest to nieefektywne i niemożliwe.
Metody losowe - losowo przeszukują przestrzeń rozwiązań i zapamiętują wyniki, z których potem wybierane jest najlepsze. Metody te są również mało efektywne.
Idea algorytmów ewolucyjnych
Algorytmy te są oparte na zasadzie doboru naturalnego i dziedziczenia, gdzie wykorzystuje się ewolucyjną zasadę przeżycia osobników najlepiej przystosowanych.
Główne cechy algorytmów ewolucyjnych :
wyjściem do przeszukiwania nie jest punkt przestrzeni poszukiwań, ale pewna populacja
przetwarzane są nie parametry zadania, ale zakodowana postać tych parametrów
losowy wybór jest tu jedynie jednym narzędzi poszukiwań
Podstawowe pojęcia (słowniczek) :
Populacja - określony zbiór osobników
Osobnik - zakodowany w postaci chromosomu zbiór parametrów zadania
Chromosom - to uporządkowany ciągiem genów
Gen - jest cechą, pojedynczym elementem genotypu
Genotyp - zespół chromosomów danego osobnika (czasem pojedynczy chromosom)
Fenotyp - to zakodowana struktura, czyli zbiór parametrów zadania
Funkcja przystosowania (także funkcja dostosowania, oceny) - pozwala ocenić stopień dopasowania osobnika populacji i wybrać wszystkie te najlepiej przystosowane (o największej wartości funkcji dopasowania) zgodnie z zasadą „przetrwa najsilniejszy”. (Odpowiednio w teorii sterowania - funkcja błędu a w teorii gier - funkcja kosztu).
W każdej iteracji algorytmu ewolucyjnego ocenia się przystosowanie osobnika za pomocą funkcji przystosowania i na tej podstawie tworzy się nową populację, jako zbiór potencjalnych rozwiązań.
Klasyczny algorytm genetyczny
Inicjacja - polega na losowym wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.
Ocena przystosowania - polega na obliczeniu wartości funkcji przystosowania dla każdego chromosomu z populacji.
Sprawdzenie warunków zatrzymania - zależą one od zadania. Najczęściej jest to:
osiągnięcie wartości optymalnej
osiągnięcie wartości optymalnej z określoną dokładnością
przekroczenie czasu działania (timeout)
wykonanie obliczeń dla określonej liczby generacji.
Selekcja chromosomów - odbywa się na podstawie wartości funkcji przystosowania, tych chromosomów, które będą tworzyć następne pokolenia. Najbardziej popularna metoda to metoda ruletki.
W wyniku tego procesu zostaje utworzona populacja rodzicielska o liczebności podobnej do bieżącej populacji.
Operatory genetyczne
Zastosowanie operatorów genetycznych do chromosomów (w procesie selekcji) prowadzi do utworzenia
nowej populacji potomków. Stosuje się dwa podstawowe operatory genetyczne: operator krzyżowania i
operator mutacji.
W klasycznym algorytmie genetycznym krzyżowanie występuje prawie zawsze (prawdopodobieństwo <0,5-1> a mutacje bardzo rzadko (prawdopodobieństwo na poziomie 0,1).
Operację mutacji stosujemy na populacji rodziców przed operacją krzyżowania, oraz na populacji potomków, już po krzyżowaniu.
Przykładowe operacje krzyżowania i mutacji
Przykład krzyżówki:
Chromosomy ch1 i ch2 mają po 10 genów. Stanowią one parę rodzicielską. W celu przeprowadzenia krzyżowania losujemy liczbę z przedziału [1,9]. Wylosowano nr.5.
Przykład mutacji:
Losujemy 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 prawdopodobieństwo pm = 0,2. Do mutacji zostaną dopuszczone tylko te geny, gdzie
liczba jest pm<= 0,1 - tylko gen nr. 7 (czerwony).
Przykład wykorzystania algorytmu genetycznego
Zadanie :
Znaleźć maksimum funkcji y = 2*x +1 w przedziale liczb całkowitych [0,31]. Zbiorem potencjalnych rozwiązań (czyli przestrzenią poszukiwań) jest zbiór {0,1,2,…,32}. Każdy z elementów zbioru jest fenotypem. Fenotypy zakodujemy jako chromosom 5-bitowy (bo wartości 32 odpowiada [11111]).
Losowanie populacji początkowej :
Ustalono początkową populacja na N=8
Ocena funkcji dostosowania :
wartości funkcji dostosowania obliczono
wg. wagi wzoru F(chi)=2* chi+1
Selekcja chromosomów :
Selekcji dokonano metodą koła ruletki.
(diagram poniżej).
Pola wycinków koła ruletki obliczono wg wzoru
Selekcja chromosomów - za pomocą koła ruletki odbywa się przez losowym zakręceniem koła ruletki
(tutaj ośmiu) liczb z przedziału [0,100]. Suma wszystkich wartości ( chi) jest równa 100%.
Wylosowano liczby : 79 44 9 74 45 86 48 23, które odpowiadają chromosomom :
ch6 ch4 ch2 ch6 ch5 ch6 ch5 ch3
Piąty wylosowany chromosom to ch5 ponieważ jako piątą wylosowano liczbę 45 , która jest większa od sumy granicznej 44,34.