Transcript
Algorytmy ewolucyjne - algorytmy genetyczne I. Karcz-Dulęba Algorytmy klasyczne a algorytmy ewolucyjne Przeszukiwanie przestrzeni przez jeden punkt bazowy Przeszukiwanie przestrzeni przez zbiór punktów bazowych Kolejne rozwiązania generowane w oparciu o wyliczanie pewnych charakterystyk funkcji celu np. gradientu Kolejne rozwiązania generowane w oparciu o wykorzystanie mechanizmów analogicznych do reprodukcji biologicznej Terminologia Osobnik rozwiązanie, punkt bazowy Chromosom łańcuch cech (genów) osobnika Gen - pojedynczy element chromosomu Allel wartość genu (0,1) Locus pozycja (miejsce) genu w chromosomie) Genotyp zespół genów danego organizmu warunkujących dziedziczenie (w GA chromosom) Fenotyp zbiór cech organizmu uwarunkowany przez genotyp i środowisko, służący do wyliczania przystosowania osobnika Przystosowanie wartość liczbowa określająca jakość osobnika, wyliczana na podstawie nieujemnej funkcji przystosowania (celu) Populacja - zbiór punktów bazowych, osobników Selekcja (selection), krzyżowanie (crossover), mutacja (mutation) operacje genetyczne Algorytm genetyczny (klasyczny - SGA) Osobniki opisywane przez binarnie kodowane chromosomy o stałej długości Geny przyjmują wartości 0 lub 1 Selekcja proporcjonalna Krzyżowanie jednopunktowe Mutacja bitowa Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Dane początkowe Zadanie optymalizacyjne: znaleźć maksimum danej funkcji przystosowania np. f(x)=10x 2 -x, x Є [0,10] Parametry: rozmiar populacji m, długość łańcucha binarnego (chromosomu) l, Warunek zatrzymania algorytmu (np. liczba generacji lg) Prawdopodobieństwo krzyżowania p c Prawdopodobieństwo mutacji p m Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Populacja początkowa Osobnik x zakodowany w postaci ciągu binarnego o długości l x i = (l=10) Populacja m-elementowa P 0 ={x 0 1, x 0 2,, x 0 m} Losowa populacja początkowa (macierz [m, l], randint) Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Ocena przystosowania Ocena osobników na podstawie fenotypów wymaga zdekodowania binarnego chromosomu do przestrzeni fenotypów Zadanie wstępne: znaleźć osobnika o największej liczbie jedynek w łańcuchu f(x)= f(x)= f(x)=4 Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Selekcja proporcjonalna (ruletkowa) Wybór rodzica zależny od jego jakości, zgodnie z prawdopodobieństwem: f ( xi ) p( xi ) m f ( x ) j 1 Wykonanie m losowań ruletką, na której kole przydzielono sektory proporcjonalne do wartości przystosowanie j Koło ruletki f(x 1 )=3 r=25% f(x 2 )=6 r=50% f(x 3 )=2 r=16.6% f(x 4 )=1 r=8.4% Metoda odwrotnej dystrybuanty p( x) { p( x ), p( x2 ),..., p( x 1 m Budujemy funkcję odwrotnej dystrybuanty zliczając sumy cząstkowe z wektora i fp( xi ) p( xk ), i 1,..., m k 1 Znajdujemy numer osobnika, dla którego: )} 1 fp(x 3 ) fp(x 2 ) rand p(x 2 ) p(x 3 ) p(x 4 ) fp(x i ) = rand rand liczba losowa z przedziału [0,1] Wybrany osobnik zostawi potomka w kolejnej generacji fp(x 1 ) p(x 1 ) Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Krzyżowanie jednopunktowe Losowe kojarzenie w pary osobników wybranych w procesie selekcji Krzyżowanie z wybranym prawdopodobieństwem p c Losowo wybierany punkt krzyżowania k Wymiana odpowiednich części łańcucha pomiędzy rodzicami k=4, Algorytm genetyczny 1. Populacja początkowa 2. Ocena przystosowania 3. Selekcja proporcjonalna 4. Krzyżowanie jednopunktowe 5. Mutacja procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); } } Mutacja Losowa zmiana wartości genu (0 1) Mutacja z wybranym prawdopodobieństwem p m, które zwykle jest znacznie mniejsze niż prawdopodobieństwo krzyżowania p c k=5, Kryterium zatrzymania Osiągniecie optimum! Ograniczenia zasobów CPU: maksymalna liczba wyliczeń funkcji przystosowania Ograniczenie na cierpliwość użytkownika: po kilku (kilkunastu, kilkudziesięciu) generacjach bez poprawy Inne uwagi Wykorzystywać możliwości Matlaba, szczególnie do pracy z macierzami i wektorami Program główny + podprogramy Zwięzłość kodu inicjalizacja 1 linijka mutacja 1 linijka Algorytm genetyczny Literatura D. Goldberg, Algorytmy Genetyczne w zastosowaniach, WNT, W-wa,1995 Z. Michalewicz, Algorytmy genetyczne+ struktury danych =programy ewolucyjne, WNT, W-wa, 1996 J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, W-wa, 2001 Algorytm genetyczny - program Parametry: rozmiar populacji - m długość łańcucha binarnego - l warunek zatrzymania algorytmu lg 1. Losowa populacja początkowa - macierz [m, l], randint 2. Ocena przystosowania - znaleźć osobnika o największej liczbie jedynek w łańcuchu 3. Selekcja proporcjonalna metoda odwrotnej dystrybuanty 4. Krzyżowanie jednopunktowe 5. Mutacja jednobitowa procedure GA; { t = 0; initialize population P(t); until (done) { t = t + 1; parent_selection P(t); recombine P(t) mutate P(t); }}
