Wykład 10

Algorytmy ewolucyjne.

Streszczenie

Tematem wykładu są algorytmy ewolucyjne - zbiór metod optymalizacji inspirowanych analogiami biologicznymi (ewolucja naturalna). Oprócz ogólnego opisu metod ewolucyjnych i przedstawienia podstawowych pojęć zaprezentowany zostanie opis dwóch algorytmów szczegółowych: klasycznego algorytmu genetycznego (z kodowaniem binarnym) i metody strategii ewolucyjnych.


Algorytmy ewolucyjne - przegląd

Algorytmy ewolucyjne to nazwa ogólna, obejmująca takie metody szczegółowe, jak np.:

Ich cechą wspólną jest wykorzystanie schematu działania wzorowanego na teorii doboru naturalnego i ewolucji. Jest to więc kolejna - po sieciach neuronowych - technika inspirowana analogiami biologicznymi. Główne pole zastosowań algorytmów (metod) ewolucyjnych to problemy optymalizacji - jak wiemy, wiele problemów praktycznych można przedstawić w języku problemów optymalizacyjnych; większość z nich można w związku z tym próbować rozwiązywać ewolucyjnie.

Zasadę działania algorytmów ewolucyjnych można nieformalnie streścić następująco: zamiast szukać na oślep (lub konstruować z kawałków, jak w przypadku strategii zachłannej) właściwego rozwiązania problemu, postarajmy się je "wyhodować". Niech różne rozwiązania konkurują ze sobą, krzyżują się, rozmnażają, naśladując mechanizmy odpowiadające za coraz lepsze dostosowanie organizmów żywych do środowiska. Skoro ewolucja naturalna jest tak skuteczna w konstruowaniu złożonych, dobrze dostosowanych organizmów, to możemy liczyć na to, że ewolucja symulowana przyniesie nam dobre (zbliżone do optymalnych) rozwiązania problemu. Musimy tylko zadbać o to, by nasze symulowane "środowisko" promowało te osobniki (tzn. rozwiązania problemu), które lepiej spełniają nasze kryteria optymalizacyjne.

Zanim przejdziemy do konkretnych definicji i rozwiązań algorytmicznych, warto przypomnieć kilka podstawowych pojęć występujących w opisach zarówno naturalnej, jak i symulowanej ewolucji.

Podstawowe pojęcia

Osobnik - podstawowa jednostka podlegająca ewolucji. Zakładamy zwykle, że ów osobnik przebywa w pewnym środowisku, do którego może być lepiej lub gorzej przystosowany. “Celem” ewolucji jest stworzenie osobnika możliwie dobrze przystosowanego do danego środowiska. W przypadku algorytmów ewolucyjnych osobnikiem będzie przykładowe rozwiązanie zadania (punkt z przestrzeni stanów).
Populacja - zespół osobników zamieszkujących wspólne środowisko i konkurujących o jego zasoby.
Fenotyp - ujawniające się “na zewnątrz” cechy danego osobnika. W przypadku algorytmów ewolucyjnych są to te parametry (cechy) rozwiązania, które podlegają ocenie.
Genotyp - “plan konstrukcyjny”, kompletny i jednoznaczny opis osobnika zawarty w jego genach. W przypadku algorytmów ewolucyjnych cechy rozwiązania (punktu z przestrzeni stanów) kodowane są w określony sposób, np. za pomocą ciągów binarnych ustalonej długości (odpowiednikiem genotypu osobnika jest w tym przypadku ciąg bitów).
Chromosom - miejsce przechowywania genotypu osobnika.
Kodowanie rozwiązań - sposób zapisania dowolnego dopuszczalnego rozwiązania problemu w postaci genotypu osobnika (np. ciągu bitów). Kodowanie musi zapewniać jednoznaczność dekodowania - każdemu genotypowi (np. każdej kombinacji bitów) musi odpowiadać pewne rozwiązanie zadania, czyli punkt z przestrzeni stanów. Musimy też się postarać, by każde rozwiązanie dało się zapisać w postaci genotypu.
Funkcja przystosowania (fitness) - funkcja pozwalająca dla danego osobnika określić jego jakość (z punktu widzenia rozwiązywanego problemu). Zakładamy, że jej wartości są rzeczywiste nieujemne oraz że wyższa wartość funkcji oznacza zawsze, że dany osobnik jest lepszy. W przypadku ewolucji naturalnej odpowiednikiem takiej funkcji jest ogólna ocena przystosowania osobnika do danego środowiska. W praktyce funkcja ta jest zwykle niewielką modyfikacją funkcji celu rozwiązywanego problemu.

Ewolucja przebiega według następujących ogólnych zasad:

Istotą ewolucji jest połączenie zjawiska losowych (nieukierunkowanych) zmian genotypu ze ściśle ukierunkowaną presją środowiska na fenotyp.

Wykorzystanie wybranego algorytmu ewolucyjnego do konkretnego problemu polega na:

Klasyczny algorytm genetyczny

Niech dany będzie problem optymalizacyjny: znaleźć maksimum funkcji rzeczywistej f(x) na pewnym zbiorze (przestrzeni stanów X). Algorytm genetyczny (klasyczny, z kodowaniem binarnym) rozwiązujący ten problem składa się z następujących etapów:

Schemat algorytmu genetycznego

0. Etap wstępny: kodowanie problemu. W przypadku algorytmu genetycznego genotyp osobnika jest ciągiem binarnym stałej długości. Aby rozwiązać konkretne zadanie, musimy zakodować przestrzeń stanów (czyli wszystkie potencjalne rozwiązania) w języku binarnym, przy czym długość łańcuchów kodujących rozwiązania ustalamy z góry. Jeżeli zadanie polega na znalezieniu maksimum funkcji nieujemnej f(x), możemy owej funkcji użyć jako stopnia przystosowania osobnika do środowiska. W innych przypadkach musimy sami taką funkcję skonstruować; np. jeśli zadanie polega na minimalizacji kosztu c(x) przyjmującego wartości [0,20], wówczas możemy przyjąć funkcję przystosowania f(x) = 20 - c(x).

1. Konstruujemy populację początkową składającą się z N osobników całkowicie losowych. Liczbę N dobieramy w zależności od czasu, jakim dysponujemy, oraz stopnia złożoności problemu. Typowe wartości to 20-50 osobników.

2. Stosujemy operatory genetyczne, czyli pewne przekształcenia kodu genetycznego osobników. Wyróżniamy dwa podstawowe operatory: mutację i krzyżowanie. Mutacja działa następująco: losujemy osobnika, następnie jeden z jego bitów. Zamieniamy wartość tego bitu na przeciwną. Mutacja dotyka średnio 0.1% bitów w populacji.

Drugim operatorem genetycznym jest krzyżowanie (crossing-over):

Krzyżowanie

Łączymy osobniki losowo w pary. Dla każdej pary ustalamy (w drodze losowania, prawdopodobieństwo rzędu 20-50%), czy dojdzie do ich skrzyżowania. Jeśli tak, losujemy miejsce (bit) w chromosomie jednego z rodziców, po czym zamieniamy miejscami fragmenty chromosomów poczynając od wylosowanego miejsca.

3. Liczymy wartości funkcji celu osobników. W tym celu odczytujemy kod genetyczny każdego osobnika i odkodowujemy go (interpretujemy) jako element przestrzeni stanów, czyli przykładowe rozwiązanie zadania. Następnie oceniamy to rozwiązanie funkcją celu. (Uwaga: warto zauważyć, że to jedyny moment, gdy osobniki rozpatrujemy w kontekście naszego konkretnego problemu; pozostałe kroki to operacje na abstrakcyjnych ciągach bitów).

4. Dokonujemy selekcji: zamieniamy wartości policzonej wcześniej funkcji celu na wartości przystosowania (często jest to ta sama funkcja). Następnie, spośród N osobników populacji pośredniej losujemy N osobników populacji końcowej (z powtórzeniami), za pomocą algorytmu “koła ruletki”:

Selekcja za pomocą 'koła ruletki'

- Liczymy sumę wartości funkcji celu: fsum = f(x1) + ... + f(xN).

- Liczymy wkład każdego osobnika w sumę: p(xi) = f(xi) / fsum.

- Traktujemy wartości p(xi) jako rozkład prawdopodobieństwa i dokonujemy N-krotnego losowania osobników zgodnie z tym rozkładem. Wylosowane w ten sposób osobniki dokładamy do populacji końcowej.

5. Populacja końcowa staje się populacją bieżącą. Wracamy do punktu 2.

Algorytm zatrzymuje się na żądanie użytkownika, po określonym czasie lub po osiągnięciu określonego progu jakości rozwiązania. Algorytm jet niedeterministyczny (losowe działanie mutacji, krzyżowania i selekcji), nie mamy gwarancji, że znalezione rozwiązanie jest optymalne.

Uwaga: przedstawiony powyżej schemat jest najbardziej powszechny, ale nie jedyny możliwy. Często wykorzystuje się np. inne metody selekcji osobników, dodatkowe techniki wspomagające itp. (wkrótce poznamy przykłady takich modyfikacji).

Wady i zalety algorytmów genetycznych

Zalety:

Wady:

Strategie ewolucyjne

Inna - obok algorytmów genetycznych - popularna metoda ewolucyjna. Główny obszar zastosowań to optymalizacja funkcji rzeczywistych wielowymiarowych. W przypadku algorytmów genetycznych zakodowanie parametrów liczbowych wymaga ustalenia liczby bitów, co ogranicza nam dokładność obliczeń. W przypadku strategii ewolucyjnych kod genetyczny składa się po prostu z liczb zmiennoprzecinkowych (o precyzji limitowanej tylko przez używany język programowania), co znacznie ułatwia kodowanie problemu i poprawia dokładność końcowego rozwiązania.

Przykład: znaleźć maksimum funkcji f : Rn -> R na danym przedziale [a1 , b1] x ... x [an , bn].

Przez x = (x1, ... xn) oznaczmy przykładowe rozwiązanie (punkt z przestrzeni stanów, przy czym xi należy do przedziału [ai , bi]). Każdemu wektorowi x przyporządkujmy ponadto pomocniczy wektor wartości rzeczywistych dodatnich: s=(s1, ... sn). Para (x,s) będzie stanowiła kod genetyczny osobnika.

Strategie ewolucyjne

Schemat działania strategii ewolucyjnych jest zbliżony do schematu algorytmu genetycznego - też składa się z etapów wykorzystania operatorów genetycznych, liczenia wartości funkcji celu i przeprowadzania selekcji. Główna różnica polega na innym działaniu i znaczeniu operatora mutacji, a także tradycyjnie innym schemacie selekcji:

1. Tworzymy losową populację złożoną z N osobników postaci (x,s).

2. Dopisujemy do niej M osobników potomnych, tworzonych na podstawie losowo wybranych osobników z poprzedniego pokolenia za pomocą mutacji i krzyżowania.

3. Dla każdego osobnika w populacji pośredniej liczymy wartość optymalizowanej funkcji.

4. Spośród N+M osobników wybieramy N najlepszych względem f(x). Te osobniki przeżyją i utworzą następne pokolenie.

5. Powtarzamy od punktu 2. z aktualną populacją N-osobnikową.

Selekcja w alg. strategii ewolucyjnych

Mutacji podlegają zwykle wszystkie osobniki dodawane do populacji pośredniej. Mutacja polega na zmianie parametrów (x,s) zgodnie ze wzorami:

Mutacja w alg. strategii ewolucyjnych

gdzie N(0,a) oznacza liczbę losową wygenerowaną zgodnie z rozkładem normalnym o wart. oczekiwanej 0 i odchyleniu standardowym a.

Krzyżowaniu podlega część (np. 25%) osobników dodawanych do populacji pośredniej. Osobnik potomny składany jest z genów dwóch losowo wybranych osobników rodzicielskich. Każdy gen (tzn. każdą składową xi) wybieramy z losowego z dwójki rodziców, przy czym wartości te są dziedziczone zawsze razem z odpowiadającymi im wartościami pomocniczymi si.

Powyższy schemat wskazuje na znaczącą rolę mutacji (w porównaniu z klasycznym algorytmem genetycznym, gdzie mutacje są rzadkie, a za kierunek ewolucji bardziej odpowiada krzyżowanie). Przeszukiwanie przestrzeni stanów polega tu na losowym (gaussowskim) przechodzeniu z danego punktu przestrzeni do pewnego innego, zwykle niezbyt odległego. Wielkość kroków w każdym wymiarze regulują parametry si - im większe, tym (średnio) dalej osobnik się przeniesie wskutek mutacji.

Różnica w sposobie kodowania osobników wskazuje też na zakres zastosowania algorytmów genetycznych i strategii ewolucyjnych. Jeśli zadanie jest typu kombinatorycznego (np. "Znaleźć podzbiór..." albo "Wyznaczyć optymalną kolejność...") lub jest określone na liczbach całkowitych, lepiej się sprawdza algorytm genetyczny i binarne kodowanie rozwiązań. Natomiast zadania, w których wynik jest wartością zmiennoprzecinkową (np. wielowymiarową, jak w zadaniu: "Wyznaczyć optymalne wymiary turbiny samolotu..."), lepiej sprawdzają się strategie ewolucyjne.

Samoadaptacja - motor działania strategii ewolucyjnych

Terminem samoadaptacja określa się sytuację, w której ewolucji podlegają nie tylko parametry rozwiązania problemu, ale też parametry samego procesu ewolucji. Potencjalnie daje to możliwość sprawniejszej pracy metod ewolucyjnych: skoro nie zawsze łatwo jest dobrać właściwe parametry pracy algorytmu, to rozsądnym się wydaje poszukiwanie ich metodami ewolucyjnymi. Pozostaje pytanie, jak oceniać wybór konkretnych wartości parametrów (jaka ma być funkcja celu)? Na szczęście okazuje się, że nie jest potrzebna osobna funkcja celu, co zobaczymy na przykładzie strategii ewolucyjnych.

Typowy przebieg optymalizacji za pomocą metody strategii ewolucyjnych jest następujący: początkowo osobniki próbkują różne miejsca przestrzeni stanów, utrzymując jednocześnie stosunkowo wysoką wartość parametrów s (dzięki czemu mutacje sprzyjają szerokiej eksploracji przestrzeni). Kiedy jednak osobniki znajdą się w pobliżu maksimum (globalnego lub izolowanego lokalnego), wówczas ich parametry s gwałtownie maleją, niekiedy o wiele rzędów wielkości. Takie zachowanie parametrów powoduje, że mutacje stają się coraz subtelniejsze i coraz dokładniej przybliżają wartość maksimum. Okazuje się, że za takie "inteligentne" zachowanie się parametrów s odpowiada właśnie zjawisko samoadaptacji.

Aby ewolucja promowała pewne cechy, nie muszą być one bezpośrednio oceniane przez algorytm ewolucyjny. Zauważmy, że funkcja celu zależy wyłącznie od wektora wartości x, czyli parametrów rozwiązania. Z drugiej strony, określone wartości pomocniczych parametrów s też mogą być promowane, o ile prowadzą w kolejnych pokoleniach do znalezienia lepszych wartości ocenianych bezpośrednio parametrów x. Takie zjawisko obserwujemy w przypadku zbliżania się do lokalnego maksimum funkcji celu: niewielkie wartości s są ewolucyjnie korzystne, gdyż mutacja oparta o parametr s nie spowoduje zbyt odległej "ucieczki" od tego maksimum (a może spowodować jeszcze dokadniejsze zbliżenie się do maksimum). Z drugiej strony, jeśli eksplorujemy obszary przestrzeni stanów odległe od maksimum, wówczas odległe "skoki" (mutacje przy wysokim parametrze s) często bywają korzystne.

Poniższe ilustracje są przykładem opisanych wyżej zjawisk. Załóżmy dla uproszczenia, że każdy z osobników ma dwóch potomków i że etap selekcji przeżyje tylko najlepszy osobnik (pogrubione kółko). Osobniki zielone mają wysoką wartość parametru s, osobniki czerwone - niską. Widzimy, że jeśli (wspólny) punkt startowy leży niedaleko maksimum lokalnego, wówczas przeżyje ten osobnik, który miał mniejszą wartość s. Natomiast na "zboczu" funkcji celu, tzn. z dala od maksimów lokalnych, presja selekcyjna wypromuje wysokie wartości s.

Samoadaptacja - jak wartości s zmieniają szansę przeżycia

Uwagi historyczne

Próby zaprzęgnięcia mechanizmów ewolucji do rozwiązywania złożonych zagadnień sięgają dość odległej przeszłości, jednak algorytmy genetyczne we współczesnym kształcie wykrystalizowały się w połowie lat 70-tych. Metoda strategii ewolucyjnych jest o ok. 10 lat wcześniejsza. Najważniejsze wydarzenia i etapy:

Przykłady

1. Maksimum funkcji rzeczywistej.

Weźmy funkcję f: R3 -> R daną wzorem: f(x,y,z) = xy + 2zx3 - 6 cos(4y + 12z). Znaleźć maksimum funkcji f dla x, y, z z przedziału [0,2] z dokładnością do 0,001.

Rozwiązanie zadania za pomocą metod ewolucyjnych polega na wybraniu właściwej metody, zakodowaniu rozwiązań w postaci osobników i wskazaniu funkcji celu. W tym przypadku właściwsza wydaje się metoda strategii ewolucyjnych, gdyż problem ma naturę numeryczną.

Przestrzeń stanów, a więc zbiór wszystkich potencjalnych rozwiązań zadania, to zbiór wszystkich możliwych trójek liczb (x,y,z) o wartościach z zadanego wyżej przedziału. W metodzie strategii ewolucyjnych osobnik składa się z oryginalnych wartości x, y i z, oraz z trzech dodatkowych parametrów s1, s2, s3. Chromosom ma więc postać (x,y,z,s1,s2,s3). Funkcja celu w tym przypadku może być identyczna z analizowaną funkcją f (gdyż szukamy maksimum). Musimy jeszcze uwzględnić, że rozwiązania mają należeć do zadanego przedziału - w tym celu będziemy ignorować te mutacje, które nas wyprowadzą na którejś współrzędnej poza zakres [0,2]. Po zastosowaniu standardowej (opisanej wyżej) metody strategii ewolucyjnych (np. dla N=20, M=20) w krótkim czasie powinniśmy otrzymać rozwiązanie o wymaganej, a nawet znacznie lepszej dokładności.

W przypadku klasycznych algorytmów genetycznych zadanie to wymaga trochę bardziej skomplikowanej procedury kodowania potencjalnych rozwiązań. Ponieważ chromosom składa się z bitów, musimy zakodować rozwiązania, czyli wektory (x,y,z), jako liczby całkowite. Zadana dokładność to 0,001; to oznacza, że w przedziale [0,2] powinniśmy uwzględnić 2000 różnych punktów. Z powodów praktycznych uwzględnimy ich 2048, dzięki czemu każdą zmienną będziemy mogli zapisać na 11 bitach, a nasz chromosom będzie miał postać bxbybz, czyli ciągu 33 bitów odpowiadających za wartości kolejnych zmiennych. Dowolny ciąg 33 bitów rozkodowujemy następująco: najpierw dzielimy go na odcinki 11-bitowe, następnie odczytujemy wartość x jako:

x = minx + (maxx - minx)* bx / (2k-1)

Powyższy wzór ogólny można stosować we wszystkich sytuacjach, gdy chcemy liczbę rzeczywistą z zakresu [minx,maxx] zakodować liczbą naturalną bx zapisaną jako ciąg k-bitowy. W naszym przypadku ten wzór ogólny sprowadza się do x = 2 * bx / 2047 i podobnie dla zmiennych y i z. Warto zauważyć, że dzięki takiemu kodowaniu żadna mutacja czy krzyżowanie nie spowoduje wyjścia rozwiązań poza zakładany przedział.

Drugim elementem wymagającym pewnej uwagi jest funkcja celu. Nasza maksymalizowana funkcja f nadawałaby się, podobnie jak w przypadku strategii ewolucyjnych, na funkcję przystosowania (fitness), gdyby nie to, że jej wartości mogą być ujemne. Algorytm koła ruletki nie dopuszcza ujemnych wartości funkcji celu. Aby zapewnić spełnienie tego warunku, przyjrzyjmy się postaci funkcji f i zauważmy, że jej wartości na pewno nie są mniejsze niż -6. Możemy więc jako funkcję przystosowania zastosować pomocniczą funkcję g(x,y,z) = 6 + f(x,y,z). Jeśli nie znamy postaci badanej funkcji i nie możemy określić jej minimum, pozostaje uniwersalna metoda zastąpienia wszystkich ujemnych wartości funkcji zerem lub zastosowanie funkcji pomocniczej g(x,y,z)=ef(x,y,z). Po zastosowaniu powyższego kodowania i przekształcenia funkcji celu można już użyć klasycznego algorytmu genetycznego, by znależć rozwiązanie z zadaną dokładnością.

2. Pokrycie kolumnowe macierzy zerojedynkowej.

Niech dana będzie macierz A=[aij] o wymiarach N x M, o wartościach 0 lub 1. Znaleźć taki najmniejszy zbiór kolumn B, by w każdym wierszu choć jedna kolumna ze zbioru B miała wartość 1.

Tym razem naturalniejszym sposobem rozwiązania problemu jest użycie klasycznego algorytmu genetycznego. Kodowanie jest łatwe, gdyż przestrzeń stanów (rozwiązań) bezpośrednio przenosi się na ciągi zerojedynkowe długości N: bit równy 1 oznacza, że odpowiadająca mu kolumna należy do zbioru B, bit równy 0 oznacza, ze kolumna ta nie należy do B. Każdy ciąg zerojedynkowy można więc utożsamić z pewnym (być może błędnym) rozwiązaniem zadania.

Większym problemem jest funkja celu, którą tym razem musimy sami ustalić. Jakość rozwiązania mierzy się wielkością (jak najmniejszą) zbioru B, dbając przy tym o spełnienie przez B warunków zadania, a więc o to, by było to pokrycie kolumnowe. Funkcja przystosowania powinna rosnąć, gdy rozwiązania są coraz lepsze; w naszym przypadku najprostszym rozwiązaniem jest przyjęcie f(B) = N-|B|+1 dla zbiorów będących pokryciami i f(B)=0 dla pozostałych zbiorów.

Powyższe rozwiązanie, choć proste, nie zapewnia dużej skuteczności działania. Nie ma zróżnicowania pomiędzy tymi zbiorami B, które nie są pokryciami (a niektórym może niewiele brakować), w związku z czym nie ma presji ewolucyjnej na stopniowe "stawanie się pokryciem". Rozważmy inne rozwiązanie, w którym przez CB oznaczamy liczbę wierszy pokrytych przez kolumny ze zbioru B, a funkcja celu ma postać f(B) = CB + (N-|B|+1) / N. Jest to funkcja, która powoduje przede wszystkim tworzenie się podzbiorów B będących pokryciami, a w drugiej kolejności - wybór wśród nich najmniejszego pokrycia. Łatwo sprawdzić, że maksimum takiej funkcji f stanowi rozwiązanie naszego zadania.

Pozostałe elementy algorytmu genetycznego są zgodne z ogólnym schematem przedstawionym powyżej.


Podsumowanie i literatura

Celem wykładu było zaprezentowanie dwóch podstawowych algorytmów ewolucyjnych: klasycznego algorytmu genetycznego (z kodowaniem binarnym) i algorytmu strategii ewolucyjnych. Kolejne wykłady stanowią rozszerzenie tej tematyki zarówno od strony teoretycznej, jak i praktycznych technik dodatkowych. Zastosowanie opisanych algorytmów zaprezentowano na przykładzie dwóch problemów, które Czytelnik łatwo uogólni na inne zastosowania, zawierające parametry zarówno zmiennoprzecinkowe, jak i typu kombinatorycznego.

Zalecana literatura:


Słownik pojęć

Szczegółowe definicje znajdują się w treści wykładu (słowa kluczowe zaznaczone są na czerwono).

algorytm ewolucyjny - ogólna nazwa różnych metod wykorzystujących mechanizmy ewolucji
algorytm genetyczny - klasyczny algorytm ewolucyjny z kodowaniem binarnym
chromosom - miejsce przechowywania genotypu osobnika
fenotyp - cechy osobnika podlegające ocenie za pomocą funkcji przystosowania
funkcja celu - optymalizowana funkcja (zależna od problemu) oceniająca dane rozwiązanie, wykorzystywana po ew. modyfikacjach jako funkcja przystosowania osobnika
funkcja przystosowania (fitness) - funkcja określająca szansę przeżycia danego osobnika
genotyp - kompletny i jednoznaczny opis osobnika zawarty w jego genach, zakodowany (np. binarnie) opis punktu z przestrzeni stanów
kodowanie rozwiązań - sposób zapisania rozwiązania problemu w postaci genotypu osobnika
koło ruletki - metoda selekcji wykorzystywana w klasycznym algorytmie genetycznym
krzyżowanie - wymiana części genotypu między dwoma osobnikami
mutacja - niewielka, losowa zmiana genotypu danego osobnika
operatory genetyczne - operatory modyfikujące genotyp osobnika lub całą populację, np. mutacja, krzyżowanie, selekcja
osobnik - podstawowa jednostka podlegająca ewolucji, odpowiada przykładowemu rozwiązaniu problemu (punktowi z przestrzeni stanów)
populacja - zespół osobników zamieszkujących wspólne środowisko i konkurujących o jego zasoby
samoadaptacja - mechanizm ewolucyjny, w którym pewne parametry działania algorytmu (np. sposób kodowania albo intensywność mutacji) również są regulowane ewolucyjnie
selekcja - tworzenie kolejnego pokolenia osobników poprzez wybór i powielenie części z nich (zwykle lepiej przystosowanych)
strategie ewolucyjne - algorytm ewolucyjny, w którym osobnik zapisany jest jako wektor liczb rzeczywistych


Zadania

10.1. Czy możliwe jest, by po fazie reprodukcji całą populację opanował osobnik najgorzej przystosowany?

10.2. Jakie znaczenie ma dodatkowy parametr s w algorytmie strategii ewolucyjnych?

10.3. Danych jest n punktów z kwadratu jednostkowego [0,1]x[0,1]. Zaprojektować algorytm genetyczny znajdujący okrąg leżący najbliżej tych punktów. Użyć sumy kwadratów odległości punktów od okręgu jako wartości do zminimalizowania. Zakładana dokładność: 3 miejsca po przecinku.

10.4. Problem z zadania 11.3 rozwiązać metodą strategii ewolucyjnych. Porównać dokładność i czas działania obu algorytmów (uśredniony dla wielu eksperymentów z losowymi danymi).

10.5. Zaimplementować algorytm genetyczny z przykładową funkcją celu. Porównać skuteczność algorytmu (np. liczoną jako średnia z najlepszych wyników po 50 pokoleniach) dla różnych prawdopodobieństw mutacji i krzyżowania i dla różnych wielkości populacji.


Strona uaktualizowana przez Sinh Hoa Nguyen, 2009