Piotr Borowiec PREZENTACJA DZIAAANIA KLASYCZNEGO ALGORYTMU GENETYCZNEGO Spośród wielu metod sztucznej inteligencji obliczeniowej algorytmy genetyczne doczekały się wielu implementacji. Można je wykorzystywać do rozwiązywania rzeczywistych problemów z dowolnej dziedziny ludzkiej działalności. Najczęściej jednak dostępne na rynku programy są mało przydatne dla celów dydaktycznych, gdyż działanie ich realizuje się w ukryciu przed okiem operatora. Podjęte w ramach niniejszej pracy działanie ma na celu stworzenie aplikacji (wraz z jej opisem), która przy wykorzystaniu wizualizacji zrozumiałego dla wszystkich problemu, ukazałaby w przystępny sposób działanie klasycznego algorytmu genetycznego. Komentarz [P.B.1]: zmienione Jako główne cele przyjęto: a) stworzenie programu, który mógłby być wykorzystywany w celach edukacyjnych, b) ukazanie, w jaki sposób dziedziczone są cechy osobników populacji (na przykładzie populacji owadów) c) skupienie się na możliwościach optymalizacyjnych klasycznego algorytmu genetycznego (stworzenie jak najlepszego osobnika), d) skupienie się na wizualizacji całego zagadnienia. 1. Geneza algorytmów genetycznych Pojęcie algorytmów genetycznych nie zostało wymyślone zupełnie od podstaw przez matematyków i informatyków. Metoda wywodzi się wprost z doświadczeń darwinowskiej teorii ewolucji oraz inżynierii genetycznej. Podobnie jak w teorii ewolucji, klasyczny algorytm genetyczny oparty jest na procesie tzw. doboru naturalnego oraz na zasadzie dziedziczności. W procesie doboru naturalnego przeżywają i rozmnażają się tylko te osobniki, które są najlepiej przystosowane do panujących warunków środowiska. W procesie rozmnażania przekazują potomstwu jedną z możliwych kombinacji własnych cech. Najczęściej, co potwierdzają badania biologiczne jak również doświadczenia prowadzone na algorytmach genetycznych, wraz z kolejnymi pokoleniami rodzą się osobnicy coraz lepiej przystosowani do panujących warunków. Zadaniem klasycznych algorytmów genetycznych jest poszukiwanie optymalnego rozwiązania problemów, dla których nie znamy zasad jego rozwiązania. Musimy jednak znać i dobrze określić funkcję celu, która będzie odpowiednikiem miary przystosowania organizmów żywych do środowiska. 2. Podstawowe pojęcia 1. Geny są to podstawowe elementy, z których składają się chromosomy. W przypadku, gdy pojedyncze chromosomy reprezentują osobników - geny można uznać za ich cechy, 2. Chromosom jest to uporządkowany ciąg (zbiór) genów. W najprostszym przypadku, każdy pojedynczy gen będzie prezentowany poprzez bit informacji. Często jeden chromosom może prezentować indywidualnego osobnika populacji, jednak może też reprezentować tylko jedną z jego cech. 3. Populacja zbiór osobników tworzonych przez chromosomy. Populacja ma swoją stałą liczebność. W kolejnych cyklach ewolucji (pokoleniach) w wyniku zastosowania operatorów genetycznych pierwotny skład populacji ulega zmianie dzieje się tak, ponieważ wszystkie chromosomy podlegają wymianie na nowe. W ten sposób powstają nowe pokolenia. 4. Genotyp to inaczej struktura danego osobnika, zespół jego chromosomów. Można powiedzieć, że genotyp jest osobnikiem populacji. 5. Fenotyp jest tym, co reprezentuje genotyp. Można go określić jako wygląd zewnętrzny osobnika. 6. Allel jest to wartość danego genu, określana często jako wartość cechy lub wariant cechy. 7. Locus pozycja danego genu określająca miejsce danego genu w chromosomie. 8. Funkcja przystosowania (celu) funkcja, która określa jakość każdego z dopuszczalnych rozwiązań. Dzięki niej możemy wszystkie rozwiązania uporządkować wg jej wartości. 9. Operatory genetyczne operacje, które mogą być wykonywane na chromosomach, np. krzyżowanie, mutacja. 10. Operacja krzyżowania polega na losowym przecięciu dwóch chromosomów (ciągów bitów) w jednym punkcie i wymianie podzielonych części pomiędzy chromosomami. Powstają w ten sposób dwa nowe chromosomy. 11. Operacja mutacji polega na zamianie na przeciwny losowego bitu. 12. Operacja przejścia polega na losowym wyborze (w określonej proporcji) osobników spoza populacji,. 13. Selekcja osobników etap przed krzyżowaniem. Wybór na podstawie wcześniej określonych wartości funkcji oceny tych osobników, którzy wezmą udział w tworzeniu kolejnego pokolenia. W przypadku klasycznego algorytmu genetycznego najczęstszym sposobem selekcji jest metoda koła ruletki . Koło ruletki składa się z prawdopodobieństw wylosowania każdego osobnika. Prawdopodobieństwa ustalane są właśnie poprzez wykorzystanie funkcji przystosowania. 14. Rozwiązaniem problemu jest najlepiej przystosowany osobnik z ostatniej wygenerowanej populacji. W celu określenia takiego osobnika, należy z góry ustalić warunek zatrzymania tworzenia kolejnych populacji. Takimi warunkami mogą być: a) uzyskanie osobnika o odpowiednio dobrych parametrach cech, b) powtórzenie działania algorytmu genetycznego określoną ilość iteracji (nastąpienie po sobie ustalonej liczby nowych populacji). 15. Problem optymalizacyjny zadanie wyszukania najlepszego rozwiązania spośród puli dopuszczalnych. Jest to cel, do którego dążymy. 16. Zbiór dopuszczalnych rozwiązań czyli zbiór wszystkich ewentualnych rozwiązań zadania (niekoniecznie optymalnych). 3. Etapy w klasycznym algorytmie genetycznym Realizacja klasycznego algorytmu genetycznego składa się z kilku podstawowych Komentarz [P.B.2]: dodane etapów (Rys.1.). Pierwszym z nich jest inicjacja, czyli wybór lub stworzenie nowej populacji osobników. Następnie dla każdego z osobników obliczana jest funkcja przystosowania (ustalana w zależności od tego, jakie zadania ma spełniać algorytm). Na ogół im większa wartość tej funkcji tym lepszy jest osobnik. Po wyliczeniu wartości przystosowania (wartość funkcji) sprawdzany jest tzw. warunek zatrzymania, którego spełnienie oznacza, że można już z obecnej populacji wybrać odpowiedniego osobnika. Przykładowo warunkiem zatrzymania może być osiągnięcie jakiejś minimalnej wartości przystosowania lub rozpoczęcie konkretnej iteracji algorytmu (ustalony arbitralnie numer pokolenia). W przypadku nie spełnienia warunku zatrzymania następuje selekcja osobników, łączenie ich w pary, krzyżowanie i mutacja (w programie dla uproszczenia pominięta). W wyniku użycia tych operatorów powstaje nowe pokolenie osobników. START Inicjacja Ocena przystosowania Optymalny NIE TAK Warunek (najlepszy) Selekcja zatrzymania wynik Zastosowanie operatorów STOP Utworzenie nowej populacji Rys. 1. Etapy w klasycznym algorytmie genetycznym 4. Projekt programu 4.1. Wstęp Jednym z głównych celów projektu było ukazanie w jaki sposób dziedziczone są cechy osobników, a także zobrazowanie właściwości optymalizacyjnych klasycznego algorytmu genetycznego (stworzenie doskonałego osobnika). Do napisania programu wykorzystano język Delphi. Program zaprojektowano w taki sposób, aby użytkownik mógł w czasie korzystania z niego na bieżąco poznawać wszystkie etapy działania klasycznego algorytmu genetycznego począwszy od inicjacji, a skończywszy na wyborze najlepszego osobnika (Rys.2.). Rys. 2. Okno główne programu tuż przed zastosowaniem operatorów genetycznych Badania obrazujące pracę programu przeprowadzono na stworzonym na potrzeby doświadczenia nowym gatunku owadów: sztucznej osie. Określono dla niej 9 cech, które wydają się istotne z punktu widzenia jej funkcjonowania w środowisku. Każda cecha jest reprezentowana przez ciąg 8 bitów. Cechy te, to: wielkość i kształt głowy, wielkość i kształt tułowia, wielkość i kształt odwłoka, wielkość i kształt odnóży, wielkość i kształt skrzydeł, wielkość żądła, wielkość i kształt czułek, wielkość i kształt oczu, wielkość i kształt żuwaczek (ust). 4.2. Inicjacja Pierwszy etap to utworzenie losowej populacji 20 osobników. 4.3. Ocena przystosowania osobników Obliczana jest wartość funkcji przystosowania dla każdego osobnika z populacji. Im wyższa będzie wartość tej funkcji, tym lepszy jakościowo będzie osobnik. Obrano bardzo prostą funkcję oceny do określenia jakości osobnika. Wykorzystano skonwertowaną wartość binarną chromosomu określającego cechę na system dziesiętny. Celem przeskalowania przedziału wartości oceny wielkość tą podniesiono do kwadratu. System przyznawania punktów: 1. Na początek postawiono założenie, że cechy nie są równie ważne (przyznano wagi). Dla przykładu: ważność cechy wielkość i kształt głowy w odniesieniu do całego osobnika (cały osobnik to 100%) to 20%, a wartość cechy wielkość i kształt odnóży to 5%. Ta procentowa wartość to wskaznik ważności. 2. Wartości binarne każdej z cech są zamieniane (dekodowane) na wartości dziesiętne. 3. Otrzymane wartości dziesiętne są przemnażane przez ich wskazniki ważności. 4. Otrzymane wyniki (wynik = wartość cechy w systemie dziesiętnym * ważność cechy) dla każdej z cech są ze sobą sumowane. Otrzymana po zsumowaniu cech wartość to właśnie zmienna x, która po podniesieniu do kwadratu służy do określenia stopnia przystosowania osobnika. Wartość przystosowania osobnika przy takich założeniach może wahać się od 0 do 65025. 4.4. Sprawdzenie warunku zatrzymania Wykorzystany w programie algorytm jest algorytmem optymalizacyjnym, którego zadaniem jest stworzenie idealnego owada. Zatrzymanie algorytmu nastąpi gdy: 1) funkcja przystosowania przekroczy ustaloną wartość (tzw. maksimum). W programie tą wartością jest 35000. 2) Utworzona zostanie ustalona (w programie 4-ta) generacja osobników, a wartość przystosowania nie przekroczy ustalonej wcześniej wartości (35000). Jeśli warunek zatrzymania zostaje spełniony, to wybierany jest osobnik, dla którego funkcja przystosowania osiągnęła najwyższą wartość. 4.5. Selekcja osobników Aączenia osobników w pary dokonano za pomocą metody koła ruletki (na podstawie obliczonych wartości funkcji przystosowania tych osobników). Jeżeli: w(xi) wycinek okręgu dla danego osobnika (w %) p(xi) wartość przystosowania konkretnego osobnika podzielona przez sumę wartości przystosowania wszystkich osobników f(xi) wartość przystosowania dla danego osobnika Ł f(xi) suma wartości przystosowania wszystkich osobników Za pomocą wzoru w(xi)=p(xi)*100%, gdzie p(xi)=f(xi)/ Ł f(xi) wyliczane są wycinki okręgu jakie przypadną dla każdego z osobników. Wielkość wycinka okręgu oznacza po prostu szansę, z jaka dany osobnik może zostać wybrany do tworzenia następnej generacji (pokolenia). Po określeniu szansy na wybór każdego z osobników, należy połączyć ich w pary, poprzez tzw. obrót kołem ruletki . Losowanie osobników do par następuje 20 razy (taka samą ilość razy jak wielkość początkowej populacji). Przy czym jeden osobnik rodzicielskich może się znalezć jednocześnie w kilku parach. Szanse na to ma tym większe im większą ma wartość funkcji przystosowania. Dla uproszczenia przyjęto operator przejścia równy 1, a to oznacza, że reprodukcja odbywa się w obrębie osobników z tej samej populacji. 4.6. Operacja krzyżowania Każdy z chromosomów u jednego z rodziców jest krzyżowany z odpowiednim chromosomem u drugiego z rodziców (krzyżowane są chromosomy odpowiedzialne za tą samą cechę). Czyli np. krzyżowany jest chromosom odpowiedzialny za wielkość odwłoka u rodzica A z chromosomem odpowiedzialnym za wielkość odwłoka u rodzica B, itd. Punkt krzyżowania (miejsce rozcięcia chromosomu) jest obierany losowo. Na koniec operacji krzyżowania zostają wymienione ze sobą powstałe w ten sposób podciągi bitów. Powstają w ten sposób nowe pary potomków. Nowi osobnicy stają się populacją bieżącą dla kolejnej iteracji algorytmu genetycznego. Jeśli warunek zatrzymania zostanie spełniony to wybierany jest osobnik o największej wartości funkcji przystosowania jest to osobnik optymalny. Jest bardzo mała szansa, że powstanie osobnik idealny. Jednak metoda ta jest wykorzystywana, gdy inne metody optymalizacyjne zupełnie zawodzą, dlatego nawet jej skuteczność na poziomie 60-70% (oczywiście może to być nawet 100%) może być w wielu przypadkach jak najbardziej wystarczająca. Wartość przystosowania osobnika idealnego to 65025, a jego wszystkie cechy to binarne 1111111 (dziesiętne 255). Najlepszy osobnik (Rys.3.) wg przyjętych w programie założeń to taki, który posiada: - ostro zakończoną głowę z dodatkowymi wyrostkami, - duże, szeroko otwarte oczy, - ostro zakończone szczęki o odpowiednim kształcie, - długie poskręcane czułki, - skrzydła o dużej powierzchni, - długie żądło. Rys. 3. Wzór idealnego osobnika Osobnikiem najgorszym (Rys.4.) jest taki, u którego powyższe cechy nie są w ogóle spełnione. Jego wartość przystosowania to 0, a cechy wynoszą po 00000000 (czyli dziesiętne 0). Rys. 4. Najgorszy możliwy osobnik 2. Wnioski Należy stwierdzić, że pominięcie mutacji oraz możliwości ustawienia wartości operatora przejścia sprawiło, że po przekroczeniu pewnej liczby kolejnych pokoleń, algorytm zastosowany w programie stopniowo zatraca swoje optymalizacyjne właściwości. Podsumowując można uznać, że obecna wersja programu, pomimo swojego wciąż niezbyt dużego stopnia skomplikowania, spełnia przedstawione na początku założenia. Trzeba też zauważyć, że w przyszłych wersjach należałoby uzupełnić oprogramowanie o brakujące, omówione wyżej operatory. To powinno pozwolić na usunięcie występujących ograniczeń. Literatura: 1. D. E. Goldberg, Algorytmy genetyczne i ich zastosowania , Wydawnictwa Naukowo - Techniczne, Warszawa 1998 2. Z. Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne , Wydawnictwa Naukowo Techniczne, Warszawa 2003 3. Internet: http://panda.bg.univ.gda.pl/~sielim/genetic/gen_algol.htm 4. Internet: http://wombat.ict.pwr.wroc.pl/nauczanie/prezentacja/flash/ag/intro.swf