Algorytmy
Genetyczne
Czym są 'algorytmy genetyczne'?...
Najprościej rzecz ujmując jest to próba zasymulowania w pamięci
komputera populacji jakiegoś gatunku. Na taką populację składają się
dziesiątki, setki, tysiące... pojedynczych osobników. Osobniki te między
sobą mogą się krzyżować, mogą również następować jakieś
samoistne zmiany w strukturze pojedynczego osobnika (tzw. mutacja). W
wyniku krzyżowania i mutacji powstają nowe osobniki. Ze względu na
fakt, że populacja ma swój z góry narzucony maksymalny rozmiar część
osobników należy z niej usunąć (ten krok nazywany jest selekcją).
Oczywiście usuwane są te najmniej przystosowane... Cały ten proces
(krzyżowanie, mutacja, selekcja) powtarzany jest w nieskończoność...
Powyższy opis dotyczył komputerowych algortymów, ale na pierwszy rzut
oka widać ogromną analogię do matki natury (krzyżowania chyba nie muszą
tłumaczyć, mutacja może być spowodowana np. Czarnobylem, a selekcji może
dokonywać wilk który szybciej dogoni słabszą sarenkę...). I to chyba
ona była wzorem dla twórców algorytmów genetycznych...
Cóż z algorytmów genetycznych jest dobrego dla kodera, a tym bardziej
dla sztucznej inteligencji?...
Przyjmnijmy, że mamy do rozwiązania 'problem komiwojażera' (krótka
definicja tego zagadnienia: komiwojażer ma do odwiedzenia n miast,
wszystkie są ze sobą połączone (oznacza to że z każdego komiwojażer
może dojechać do wszystkich pozostałych). Należy znaleźć najkrótszą
drogę jaką musi pokonać komiwojażer). W przypadku małej ilości miast
problem wydaje się być łatwy. Wystarczy zestawić wszystkie permutacje
miast, obliczyć otrzymane w ten sposób odległości i wybrać najkrótszą.
Jednak problem komiwojażera jest NP-trudny (oznacza to że przy wzroście
rozmiaru instancji (liczby miast) czas potrzeby na obliczenia rośnie wykładniczo
(w przypadku problemu komiwojażera dodanie jednego miasta powoduje
dwukrotne zwiększenie czasu obliczeń)) dlatego ten sposób rozwiązania
na dłuższą metę jest niefajny...
Zaprzągnijmy więc do roboty algorytmy genetyczne. Jako 'gatunek' możemy
przyjąć trasę komiwojażera. Każdy osobnik będzie pamiętał jedną
trasę. Takich osobników może być dowolna ilość (im więcej tym
bardziej zróżnicowana populacja jednak kosztem dłuższych obliczeń).
Na początku do każdego osobnika wpisujemy trasę zupełnie losową... I
rozpoczynamy algorytm genetyczny. Krzyżowanie polega na wymianie pomędzy
dwoma osobnikami pewnych elementów tras (czyli podtras), natomiast
mutacja może oznaczać wymianę w pojedynczym osobniku dwóch miast między
sobą. Jeśli dodamy do tego krok selekcji, czyli wybór do następnej
populacji osobników najlepiej przystosowanych (to znaczy takich które
reprezentują trasy o najmniejszym koszcie) otrzymamy algorytm, który po
pewnej liczbie kroków znajdzie nam całkiem niezłą trasę przez
wszystkie miasta...
Niestety algortymy genetyczne są tylko heurystyką. Oznacza to, że
otrzymane rozwiązania nie zawsze będą najlepszymi możliwymi. W zamian
za to otrzymujemy rozwiązania bardzo dobre w rozsądnym czasie.
Algorytmy genetyczne rozłożone na elementy pierwsze...
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 algorymie 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 poszegó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 pojednycze 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śleć 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ą wykożystywane 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 miejsu 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).
Czasmami 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 esensją 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 najprostrze 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 wzorś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śleć 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 odpoweidzialnych
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 pierwszeo 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 wyniu przez pewną ilość
iteracji lub inne w zależnośći 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.
Bibliografia...
- "Algorytmy genetyczne+struktury danych=programy
ewolucyjne"
Zbigniew Michalewicz
Wydawnictwa Naukowo-Techniczne, 1996
- "Algorytmy genetyczne i ich zastosowania"
David E. Goldberg
Wydawnictwa Naukowo-Techniczne, 1998
- "Sieci neuronowe, algorytmy genetyczne i systemy
rozmyte"
Danuta Rutkowska, Maciej Piliński i Leszek Rutkowski
Wydawnictwo Naukowe PWN, 1997
Kopper
kopper@box43.gnet.pl
www.republika.pl/k0pper |