Tekst opowiada o poszczególnych elementach składowych typowego algorytmu genetycznego. Przedstawione są dokładnie takie elementy jak reprezentacja rozwiązań, sposoby krzyżowania, mutacji, selekcji. Całość oparta na przykładach. Jeśli chcesz zyskać pogłębioną widzę na temat całej rodziny algorytmów ewolucyjnych, znajdziesz uporządkowane wykłady na playliście Algorytmy ewolucyjne.
Szczegółowy opis elementów algorytmu genetycznego powinniśmy rozpocząć od opisu najmniejszego elementu algorytmu, czyli od opisu pojedynczego osobnika.
W zasadzie jest to jedyny element w algorytmie, który jest różny w przypadku różnego wykorzystania algorytmów. Dlatego projektowanie osobnika jest chyba najważniejszą częścią projektowania całego algorytmu genetycznego. Ze względu na niepowtarzalność gatunku trudno jest zdefiniować 'złotą zasadę' projektowania osobnika. W tym miejscu mogę podać jedynie kilka cech, które tworzony przez nas gatunek powinien spełniać.
Przede wszystkim należy pamiętać, że w algorytmie genetycznym bierze udział bardzo wiele osobników (kilkadziesiąt/set/tysięcy), dlatego ważną cechą osobnika jest długość jego reprezentacji. Wiadomo, że liczba osobników jest sztywno ograniczana liczbą dostępnej pamięci (komputera), dlatego im mniejsza będzie reprezentacja gatunku tym więcej osobników będzie mogło brać udział w ewolucji (a co za tym idzie większe będą szanse znalezienia globalnego optimum). Poza tym inne elementy algorytmu (krzyżowanie, mutacja...), będą działać dużo szybciej gdy poszczególne osobniki będą miały mniejszą wielkość.
I od razu mały przykładzik. Przyjmijmy, że naszym gatunkiem jest homo sapiens charakteryzujący się następującymi cechami:
- Płeć (kobieta / mężczyzna)
- Kolor oczu (mamy do wyboru: niebieskie, piwne, brązowe i czarne)
- Wzrost (poniżej 140, 140-150, 150-160, 160-170, 170-180, 180-190, 190-200, powyżej 200)
- Narodowość (mamy do wyboru: Polak, Niemiec, Czech, Rosjanin)
Najprostszą reprezentacją homo sapiensa wydaje się być struktura w której będą zapamiętywane wartości poszczególnych atrybutów. Jeśli na każdy atrybut przeznaczymy zmienną typu char* (string) to otrzymamy całkiem pokaźny rozmiar osobnika. Dodatkową wadą takiej reprezentacji jest dosyć duża niewygoda krzyżowania i mutacji (o której będzie mowa za chwilę). Niewątpliwą zaletą tej reprezentacji jest jest 'bezpośredniość', wszystkie pola struktury pamiętają konkretną wartość atrybutu. Celem zmniejszenia rozmiaru struktury można przyjąć, że dla przechowywania wartości atrybutów wykorzystane zostaną zmienne liczbowe (int, byte...) wtedy rozmiar naszej struktury opisującej człowieka zmniejszy się do 4 bajtów. W tym wypadku nie będziemy mieli w strukturze natychmiastowej informacji o wartościach atrybutów i w związku z tym należy stosować pewne oznaczenia. Np: dla płci 0 oznacza kobietę, 1 oznacza mężczyznę, dla koloru oczu 0 oznacza niebieskie, 1 oznacza piwne, 2 oznacza brązowe, 3 oznacza czarne. Reprezentacja ta jest już niewielka i całkiem wygodna w późniejszej obsłudze. Można się jednak w opisie homo sapiensa posunąć trochę dalej i wykorzystać reprezentację bitową. Proszę zauważyć, że do reprezentacji płci wystarczy jeden bit (wartość zero-kobieta, jeden-mężczyzna), do reprezentacji koloru oczu dwa bity (00-niebieskie, 01-piwne, 10-zielone, 11-czarne), do reprezentacji wzrostu też trzy bity, a do reprezentacji narodowości dwa bity. I w przypadku takiego kodowania wartości wszystkich atrybutów mieszczą się w 9 bitach. Te 9 bitów tworzą całkowity obraz pojedynczego osobnika. Przy tej reprezentacji należy na początku przyjąć w jakiej kolejności poszczególne atrybuty będą występowały w reprezentacji osobnika. W naszym przypadku przyjmijmy, że pierwszy bit będzie informował o płci następne o kolorze oczu, wzroście i narodowości. Dla przykładu chromosom: 00000000 reprezentuje niebieskooką Polkę o wzroście nieprzekraczającym 140cm, a chromosom 11011001 reprezentuje wysokiego (190-200) Niemca o brązowych oczach.
I jeszcze jeden przykładzik pokazujący jak można stworzyć binarną reprezentację liczb naturalnych. Przyjmijmy, że mamy do rozwiązania problem znalezienia takiego x'a dla którego funkcja postaci y=f(x) ma minimum (maksimum). Szukamy po prostu ekstremów funkcji. W tym przypadku pojedyncze rozwiązanie ma reprezentować pojedynczą wartości x'a. Można do tego celu użyć zmiennej typu float (real), jednak wtedy trudno jest wymyślić jakiś rozsądny sposób krzyżowania takich osobników. Innym wygodniejszym sposobem kodowania x'ów jest zastosowanie reprezentacji bitowej. W tym wypadku tracimy jednak na maksymalnej rozdzielczości. Dla przykładu jeśli badamy funkcję w przedziale 1-3 i reprezentujemy x'y na 4 bitach to otrzymujemy maksymalną rozdzielczość:
(max_x-min_x)/(2^(liczba_bitów)-1)=(3-1)/(2^4-1)=2/15=0.1333
Oznacza to, że najmniejsza możliwa różnica pomiędzy analizowanymi x'ami jest równa 0,13333. Następujące wartości bitów odpowiadają następującym wartościami x'a:
0000-1.0
0001-1.1333
0010-1.2666
0011-1.4 itd.
Jeśli mamy już zaprojektowany chromosom (krótki i wygodny w obsłudze) możemy zająć się samym algorytmem. W uproszczeniu wygląda on następująco:
1. Losowanie populacji
2. Ocena osobników
3. Selekcja
4. Krzyżowanie
5. Mutacja
6. Powrót do punktu 2
Poniżej opis poszczególnych jego elementów:
Losowanie populacji
W tym miejscu należy ustalić jak wielka będzie tworzona populacja. Jeśli populacja będzie zawierała zbyt mało osobników to algorytm może zatrzymać się w jakimś minimum lokalnym (gdy jakieś niezłe (ale nie najlepsze) rozwiązanie zdominuje całą populację). Z drugiej strony zbyt duża liczebność populacji zmniejsza szybkość działania algorytmu. Po ustaleniu wielkości populacji należy stworzyć wszystkie osobniki. Ze względu na fakt, że początkowa populacja powinna być jak najbardziej różnorodna każdy osobnik powinien być tworzony całkowicie losowo. W tym miejscu widać przewagę reprezentacji bitowej gdzie bez względu na rodzaj problemu nowo tworzony osobnik zawiera n losowo wygenerowanych bitów. W przypadku reprezentacji osobnika w strukturze należy każde jej pole wypełnić osobno. Na tym kroku należy pamiętać aby tworzone osobniki były poprawne to znaczy reprezentowały obiekty należące do dziedziny problemu. Np przy tworzeniu x'ów (problem znajdowania ekstremum) w przedziale 1-3 wygenerowany chromosom nie może reprezentować x'a o wartości np. 5. W przypadku reprezentacji bitowej ten problem pojawia się wtedy gdy do reprezentowania jakiegoś atrybutu nie są wykorzystywane wszystkie kombinacje bitów. Wracając do poprzedniego przykładu chromosomu opisującego homo sapiensa, jeśli nie uwzględnialibyśmy Rosjan to chromosom 000000011 nie byłby poprawny.
Ocena osobników
W tym kroku banana jest 'dobroć' poszczególnych osobników. W zależności od rodzaju problemu różne są funkcje sprawdzające przystosowanie osobników. W przypadku ekstremum funkcji 'dobrocią' jest po prostu wartość funkcji w zadanym x'ie. W przypadku rozwiązywania problemu komiwojażera jest to długość trasy jaka jest reprezentowana przez danego osobnika. W tym miejscu można wprowadzić tzw. funkcję kary za niedopuszczalne rozwiązanie. Wcześniej wspomniałem, że o poprawne osobniki należy zadbać podczas tworzenia populacji (niepoprawne osobniki mogą też powstawać w krokach krzyżowania i mutacji). Czasami jest to jednak trudne do wykonania dlatego przy losowaniu można te osobniki zaakceptować a w tym kroku dodać funkcję kary. Spowoduje ona dużo mniejsze prawdopodobieństwo przejścia przez danego osobnika kroku selekcji. W zależności od tego czy funkcję dopasowania ('dobroć') minimalizujemy czy maksymalizujemy wartość funkcji błędu należy do niej dodać bądź odjąć.
Selekcja
Krok ten jest esencją całej genetyki. W tym miejscu tworzona jest nowa populacja na podstawie już istniejącej. W zależności od wartości funkcji oceny (obliczanej w poprzednim kroku) dany osobnik ma większe (gdy jest 'dobry') lub mniejsze (gdy jest 'słaby') szanse na znalezienie się w kolejnym pokoleniu. Istnieje kilka sposobów obliczania 'szansy' poszczególnych osobników:
Koło ruletki – Polega na n krotnym losowaniu (n – liczba osobników w populacji) ze starej populacji osobników, które zostaną przepisane do nowej populacji. Oczywiście wszystkie osobniki mają różne prawdopodobieństwa wylosowania. Prawdopodobieństwo to jest liczone z następującego wzoru:
Wartość przystosowania danego osobnika/suma wartości przystosowania wszystkich osobników
Powyższy wzór jest poprawny tylko wtedy gdy maksymalizujemy funkcję oceny. Gdybyśmy ją minimalizowali można zastosować następujący wzór:
(Wartość najgorszego osobnika-Wartość danego osobnika+1)/(suma wartości wszystkich osobników+1)
Wzór ten odwraca minimalizację na maksymalizację.
I od razu mały przykład (przyjmijmy maksymalizację funkcji przystosowania). Mamy trzy osobniki o następujących wartościach przystosowania: 5,1,2. Odpowiadające im wartości prawdopodobieństwa są zatem równe:
- Pierwszy osobnik: 5/8, czyli 62,5%
- Drugi osobnik: 1/8, czyli 12,5%
- Trzeci osobnik: 2/8, czyli 25%
Ranking liniowy – Selekcja tą metodą jest bardzo podobna do selekcji metodą koła ruletki. Modyfikacja polega jedynie na zmianie funkcji określającej prawdopodobieństwo wyboru danego osobnika. Przed przystąpieniem do tej selekcji należy nadać każdemu z osobników pewną wartość (przystosowanie) zależną od jego położenia na liście posortowanej względem wartości funkcji oceny. Jeśli chcemy maksymalizować to wartości powinny być posortowane rosnąco, w przypadku minimalizacji wartości powinny być posortowane malejąco. Aby obliczyć prawdopodobieństwo wybrania każdego osobnika można skorzystać ze wzoru:
Prawdopodobieństwo=Przystosowanie/Suma przystosowania wszystkich osobników
Dla powyższego przykładu wartości prawdopodobieństw wyglądałyby następująco:
* Pierwszy osobnik: 3/6, czyli 50%
* Drugi osobnik: 1/6, czyli 16,7%
* Trzeci osobnik: 2/6, czyli 33,3%
Ten sposób wyliczania prawdopodobieństw zmniejsza przewagę jaką mają najlepsze rozwiązania, gdy ich przewaga jest b.duża i zwiększa przewagę gdy jest ona b.mała.
Turniej – Metoda jest zupełnie różna od powyższych i polega na losowym wyborze z całej populacji kilku osobników (jest to tzw. grupa turniejowa), a później z tej grupy wybierany jest osobnik najlepiej przystosowany i on przepisywany jest do nowo tworzonej populacji. Losowanie grup turniejowych oraz wybieranie z nich najlepszego osobnika należy powtórzyć aż do utworzenia całej nowej populacji.
Selekcja metodą turniejową jest pozbawiona niedogodności metody koła ruletki, gdzie wymagana jest maksymalizacja funkcji oceny, w turnieju ważna jest jedynie informacja o 'lepszości' jednego rozwiązania nad innym.
Krzyżowanie
Zadaniem kroku krzyżowania jest wymiana "materiału genetycznego" pomiędzy dwoma rozwiązaniami w populacji. W wyniku krzyżowania na podstawie dwóch rozwiązań (rodzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania muszą się ze sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości od 0 do 1), który pokazuje jaka liczba osobników powinna być w jednej iteracji skrzyżowana, bądź określa prawdopodobieństwo z jakim każde rozwiązanie może wziąć udział w krzyżowaniu.
W przypadku binarnej reprezentacji chromosomu najprostsze krzyżowanie polega na podziale dwóch chromosomów (rodzice) na dwie części (niekoniecznie równe) i z nich tworzone są dzieci: pierwsze dziecko składa się z początkowej części pierwszego rodzica i końcówki drugiego natomiast drugie dziecko odwrotnie – początek drugiego rodzica i koniec pierwszego.
Na przykładzie homo sapiensa może to wyglądać następująco:
Pierwszy rodzic: 00000000 – niebieskooka Polka o wzroście do 140cm
Drugi rodzic: 11011001 – wysoki (190-200) Niemiec o brązowych oczach.
Jeśli punkt podziału ustalimy pomiędzy czwartym a piątym bitem to dzieci będą wyglądać następująco:
00001001 – Niemka o niebieskich oczach i wzroście 150-160cm
11010000 – Polak o brązowych oczach i wzroście 160-170cm
Rozszerzeniem tego krzyżowania jest krzyżowanie wielopunktowe, gdzie chromosomy rodziców dzieli się na kilka części a później dzieci tworzy się na podstawie przeplatanych wycinków rodziców.
W przypadku niebinarnej reprezentacji gatunku należy wymyślić krzyżowanie stosowne do zastosowanej reprezentacji. Gdy np. dane trzymane są w strukturze to możne podmieniać pomiędzy rodzicami zawartości poszczególnych pól struktur. W tym wypadku jednak dzieci będą zawsze zawierały wartości występujące przynajmniej u jednego z rodziców. W powyższym przykładzie krzyżowania jednopunktowego wzrost dzieci jest różny od wzrostu rodziców. Stało się tak dlatego, że punkt podziału trafił w środku bitów odpowiedzialnych za wzrost. W przypadku kodowania niebinarnego takie coś byłoby niemożliwe.
Mutacja
Mutacja podobnie jak krzyżowanie zapewnia dodawanie do populacji nowych osobników. Jednak w odróżnieniu od krzyżowania w przypadku mutacji modyfikowany jest jeden a nie dwa osobniki. Podobnie jak w przypadku krzyżowania istnieje tzw. współczynnik mutacji, który określa ile osobników będzie w jednej iteracji ulegało mutacji.
W przypadku reprezentacji binarnej sprawa mutacji jest bardzo prosta wystarczy np. zanegować jeden bit w rozwiązaniu aby otrzymać zupełnie nowego osobnika. W przypadku homo sapiensa negacja pierwszego bitu powoduje zamianę kobiety na mężczyznę lub odwrotnie. Oczywiście mutacja może być bardziej urozmaicona (negacja losowej liczby bitów, odwracanie kolejności losowej liczby bitów, przesunięcie losowej liczby bitów i inne.), należy jednak pamiętać, że operować ona może tylko na jednym rozwiązaniu.
W przypadku niebinarnej reprezentacji rozwiązania mutacja może polegać np. na wpisaniu do losowego pola struktury losowej wartości (oczywiście przewidzianej przez gatunek).
Powrót do oceny osobników
W zasadzie algorytm genetyczny powinien działać w nieskończoność jednak dobrze jest zapewnić jakieś rozsądne wyjście z pętli. Może to być np. pewna liczba iteracji, wartość osiągniętego najlepszego rozwiązania, czas, brak poprawy wyniku przez pewną ilość iteracji lub inne w zależności od rodzaju zadania.
Powyżej zostały opisane podstawowe elementy algorytmu genetycznego, które w zupełności wystarczają do napisania programu rozwiązującego taki czy inny problem. Oczywiście istnieją jeszcze pewne techniki usprawniające algorytm, ale o nich może innym razem.
