Algorytm genetyczny - odmiana algorytmu przeszukującego przestrzeń alternatywnych rozwiązań dylematu w celu wyszukania rozwiązań najlepszych.
Sposób działania algorytmów genetycznych nieprzypadkowo jest podobne zjawisko ewolucji biologicznej, albowiem ich twórca John Henry Holland właśnie z biologii czerpał inspiracje do swoich prac. Aktualnie zalicza się go do grupy algorytmów ewolucyjnych.
Wstęp
Problem definiuje środowisko, w którym istnieje pewna populacja osobników. Każdy z osobników ma przypisany pewien zbiór informacji stanowiących jego genotyp, a będących podstawą do utworzenia fenotypu. Fenotyp to zbiór cech podlegających ocenie funkcji przystosowania modelującej środowisko. Innymi słowy - genotyp opisuje proponowane rozwiązanie problemu, a funkcja przystosowania ocenia, jak dobre jest to rozwiązanie.
Genotyp składa się z chromosomów, gdzie zakodowany jest fenotyp oraz ewentualnie pewne informacje pomocnicze dla algorytmu genetycznego. Chromosom składa się z genów.
Wspólnymi cechami algorytmów ewolucyjnych, odróżniającymi je od innych, tradycyjnych metod optymalizacji, są:
- stosowanie operatorów genetycznych, które dostosowane są do postaci rozwiązań,
- przetwarzanie populacji rozwiązań, prowadzące do równoległego przeszukiwania przestrzeni rozwiązań z wielorakich punktów,
- w celu ukierunkowania procesu przeszukiwania wystarczającą informacją jest jakość aktualnych rozwiązań,
- celowe wprowadzenie elementów losowych.
Zapis algorytmu
Najczęściej działanie algorytmu przebiega następująco:
- Losowana jest pewna populacja początkowa.
- Populacja poddawana jest ocenie (selekcja). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji.
- Genotypy wybranych osobników poddawane są operatorom ewolucyjnym:
- są ze sobą kojarzone poprzez złączanie genotypów rodziców (krzyżowanie),
- przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian.
- Rodzi się drugie (kolejne) pokolenie. Aby utrzymać stałą liczbę osobników w populacji te najlepsze (wg. funkcji oceniającej fenotyp) są powielane, a najsłabsze usuwane. Jeżeli nie znaleziono dostatecznie dobrego rozwiązania, algorytm powraca do kroku drugiego. W przeciwnym wypadku wybieramy najlepszego osobnika z populacji - jego genotyp to uzyskany wynik.
Działanie algorytmu genetycznego zawiera w sobie parę zagadnień potrzebnych do ustalenia:
- ustalenie genomu jako reprezentanta wyniku
- ustalenie funkcji przystosowania/dopasowania
- ustalenie operatorów przeszukiwania
Kodowanie
Kodowanie jest bardzo istotnym etapem projektowania algorytmu. Sposób zakodowania w chromosomie informacji o proponowanym rozwiązaniu wydatnie wpływa na szybkość oraz jakość znajdowanych wyników. Przyczyną takiego zjawiska jest wpływ kodowania na sposób w jaki przeszukiwana jest przestrzeń rozwiązań. Złe kodowanie może spowodować, że wcale nie zostanie przeszukany fragment przestrzeni, w którym leżą najlepsze rozwiązania!
Najczęściej stosowane kodowania chromosomu:
- wektorem genów, z których każdy z nich bywa jedno- albo wielobitową liczbą całkowitą, bądź też liczbą rzeczywistą.
- za pomocą drzewiastych struktur danych.
Funkcja przystosowania
Proces wyboru osobników poddanych ocenie wedle określonych kryteriów. Kryteria te zapisuje się w postaci funkcji oceny albo inaczej funkcji przystosowania. Algorytm genetyczny dąży zwykle do jej minimalizacji (maksymalizacji). Jako kryterium wielokrotnie przyjmowana jest funkcja celu rozważanego dylematu optymalizacji.
Funkcja oceny
Funkcja oceny to miara jakości dowolnego osobnika (fenotypu, rozwiązania) w populacji. Dla każdego osobnika jest ona obliczana na podstawie pewnego modelu rozwiązywanego problemu. Załóżmy dla przykładu, że chcemy zaprojektować obwód elektryczny o pewnej charakterystyce. Funkcja oceny będzie premiowała rozwiązania najbardziej zbliżonej do tej charakterystyki, zbudowane z najmniejszej liczby elementów. W procesie selekcji faworyzowane będą najlepiej przystosowane osobniki. One staną się "rodzicami" dla populacji.
Metody selekcji
Istnieje wiele metod selekcji. Dla przykładu da się przedstawić tzw. metodę ruletki. Budujemy wirtualnie koło, którego wycinki odpowiadają poszczególnym osobnikom. Im lepszy osobnik, tym większy wycinek koła zajmuje. Rozmiar wycinków może zależeć od wartości funkcji oceny, jeśli wysoka wartość oceny oznacza wysokie przystosowanie. W takim układzie prawdopodobieństwo, że lepszy osobnik zostanie wybrany jako rodzic, jest większe. Niestety ewolucja przy takim algorytmie z każdym krokiem zwalnia. Jeżeli osobniki są podobne, to każdy dostaje równy wycinek koła fortuny oraz presja selekcyjna spada. Algorytm słabiej rozróżnia osobniki dobre od słabszych.
Pozbawiona tej wady jest metoda rankingowa. Obliczamy dla każdego osobnika funkcję oceny oraz ustawiamy je w szeregu najlepszy-najgorszy. Pierwsi na liście dostają prawo do rozmnażania, a reszta trafia do historii. Wadą metody jest niewrażliwość na różnice pomiędzy kolejnymi osobnikami w kolejce. Może się okazać, że sąsiadujące na liście rozwiązania posiadają zróżnicowane wartości funkcji oceny, ale dostają prawie taką samą ilość potomstwa.
Istnieją także metody selekcji wielokryterialnej. Tworzymy parę wielorakich funkcji oceny (oceniających pewne wybrane cechy osobników osobno). Dla przykładu osobniki bywają ułożone nie w jednym, ale w kilku szeregach najlepszy-najgorszy, a proces selekcji jest bardziej złożony.
Jak widać, selekcja daje większe prawdopodobieństwo reprodukcji osobnikom o dużym przystosowaniu, więc kolejne pokolenia są coraz lepiej przystosowane. Spada jednak różnorodność genotypu populacji - populacja z czasem zostaje zmonopolizowana przez nieznacznie różniące się (lub wręcz identyczne) odmiany tego samego osobnika. Objawia się to zbieżnością kolejnych, najlepszych rozwiązań do pewnej granicy. Czasami zbieżność jest przedwczesna, a ewolucja utyka oraz uzyskane rozwiązania powodują pewne ekstrema lokalne. Potrafią być one dalekie od oczekiwanych rozwiązań globalnych, czyli tych najlepszych w całej przeszukiwanej przestrzeni. Częściowym rozwiązaniem tego dylematu jest losowa mutacja genotypu osobników.
Operatory przeszukiwania
W każdym cyklu (każde pokolenie) poddawane są "obróbce" za pomocą operatorów ewolucyjnych. Celem tego etapu jest wygenerowanie nowego pokolenia, na podstawie poprzedniego, które być może będzie lepiej dopasowane do założonego środowiska.
Operator krzyżowania ma za zadanie łączyć w wielorakich kombinacjach cechy pochodzące z wielorakich osobników populacji, zaś operator mutacji ma za zadanie zwiększać różnorodność tych osobników. O przynależności dowolnego algorytmu do klasy algorytmów genetycznych decyduje z reguły zastosowanie operatora krzyżowania oraz praca z całymi populacjami osobników (idea łączenia w przypadkowy sposób genotypów nieprzypadkowo wybranych osobników). Równie ważny jest operator mutacji. Jeśli krzyżowanie traktować jako sposób eksploatacji przestrzeni rozwiązań, to mutacja jest sposobem na jej eksplorację. Może się jednak zdarzyć, że dla poniektórych zagadnień jej zastosowanie nie jest krytyczne.
Krzyżowanie
Przykładowe krzyżowanie chromosomów zakodowanych binarnie w algorytmach genetycznych
|
|
+ |
|
= |
|
Krzyżowanie opiera się na połączeniu poniektórych (wybierane losowo) genotypów w jeden. Kojarzenie ma sprawić, że potomek dwóch osobników rodzicielskich ma zespół cech, który jest kombinacją ich cech (może się zdarzyć, że tych najlepszych).
Sposób krzyżowania jest zależny od kodowania chromosomów oraz specyfiki problemu. Jednak da się wskazać parę standardowych metod krzyżowania:
- rozcięcie dwóch chromosomów oraz stworzenie nowego poprzez sklejenie lewej części jednego rodzica z prawą częścią drugiego rodzica (dla chromosomów z kodowaniem binarnym oraz całkowitoliczbowym),
- stosowanie operacji logicznych (kodowanie binarne),
- obliczenie wartości średniej genów (kodowanie liczbami rzeczywistymi).
Mutacja
Mutacja wprowadza do genotypu losowe zmiany. Jej zadaniem jest wprowadzanie różnorodności w populacji, czyli zapobieganie (przynajmniej częściowe) przedwczesnej zbieżności algorytmu. Mutacja zachodzi z pewnym przyjętym prawdopodobieństwem - zwykle rzędu 1%. Jest ono niskie, albowiem zbyt silna mutacja przynosi efekt przeciwny do zamierzonego: zamiast subtelnie różnicować dobre rozwiązania - niszczy je. Stąd w procesie ewolucji mutacja ma znaczenie drugorzędne, szczególnie w przypadku długich chromosomów.
W przypadku chromosomów kodowanych binarnie losuje się zwykle dwa geny oraz zamienia się je miejscami bądź np. neguje pewien wylosowany gen.
W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje.
W przypadku genotypów zakodowanych liczbami rzeczywistymi wprowadza się do przypadkowych genów losowe zmiany o danym rozkładzie - najczęściej normalnym.
Zastosowania algorytmów genetycznych
Rozwiązywanie problemów NP
Algorytmy genetyczne znajdują zastosowanie tam, gdzie nie jest dobrze określony albo poznany sposób rozwiązania problemu, ale znany jest sposób oceny jakości rozwiązania. Przykładem jest np. problem komiwojażera, gdzie trzeba znaleźć najkrótszą drogę łączącą wszystkie miasta, tak by przez każde miasto przejść tylko raz. Ocena jakości proponowanej trasy jest błyskawiczna, natomiast znalezienie optymalnej trasy kwalifikuje się do klasy problemów NP-trudnych. Przy zastosowaniu podejścia ewolucyjnego dobre rozwiązanie da się znaleźć bardzo szybko, ale bez wątpienia pewni możemy być zaledwie uzyskania rozwiązań sub-optymalnych, co wynika z formalnie opisanej trudności problemów klasy NP. Algorytmy genetyczne równie dobrze radzą sobie w znajdowaniu przybliżeń ekstremów funkcji, których nie da się obliczyć analitycznie.
Projektowanie genetyczne
Algorytmy genetyczne wykorzystywane są także do zarządzania populacją sieci neuronowych. Projektowanie maszyn bądź obwodów elektrycznych jest doskonałym polem dla wykazania się algorytmów genetycznych. Inżynierowi podczas tworzenia nowych pomysłów nie chodzi o znalezienie najlepszego możliwego rozwiązania. Wystarczy tylko przybliżone spełnienie granicznych warunków oraz optymalizacja projektu. Algorytmy genetyczne w przeciwieństwie od człowieka nie działają schematycznie. Program nie zna wcześniejszych projektów oraz dlatego czasami wykazuje się pewną inwencją. Co więcej człowiek wielokrotnie ma za podstawę na bardzo przybliżonych modelach, które dają fałszywy obraz problemu. Algorytm genetyczny może przeanalizować złożony model / zagadnienie oraz znaleźć rozwiązanie, na które człowiek by nie wpadł.
Projektowanie obwodów elektrycznych
Algorytmy genetyczne da się wykorzystać do projektowania obwodów elektrycznych. Ocena każdego osobnika ma za podstawę na ilości elementów oraz własnościach elektrycznych, które łatwo jest obliczyć. Główna różnica tkwi w algorytmie budowy osobnika na podstawie genomu. Ma on osoba instrukcji dla programu, który na jego podstawie buduje obwód elektryczny. Najpierw mamy proste połączenie wejścia z wyjściem. Następnie program dodaje oraz usuwa połączenia oraz elementy. Zbudowany tak obwód jest oceniany na podstawie prostych zależności fizycznych. Podobny algorytm genetyczny zbudował samodzielnie filtr drabinkowy. Analogiczne podejście da się zastosować przy projektowaniu anten. Różnica tkwi w tym, że wirtualny budowniczy porusza się w trójwymiarowej przestrzeni oraz ustawia metalowe elementy odbijające fale.
Jednym z nowszych pomysłów jest wykorzystanie algorytmów genetycznych w połączeniu z układami FPGA (field-programmable gate arrays). Posiadają one osoba chipów, które da się błyskawicznie zaprogramować, aby zmienić strukturę zawartego w nich obwodu elektrycznego. Algorytmy genetyczne badają zwykle zachowanie symulowanych pokoleń. Dzięki układom FPGA możliwe jest ewoluowanie prawdziwych obwodów elektrycznych. Są one wpisywane do chipa, a następnie ich właściwości elektryczne są mierzone rzeczywistym obwodem testowym. W wyniku tego ewolucja może wykorzystać wszystkie fizyczne własności rzeczywistego układu elektrycznego.
Okazało się, że regulatory stosowane w automatyce także da się udoskonalić dzięki zastosowaniu algorytmów genetycznych. Najpopularniejszy algorytm sterowania czyli PID, da się wyobrazić sobie jako pewien zestaw połączonych ze sobą członów różniczkujących oraz całkujących. Odpowiedni algorytm genetyczny może zbudować taki układ analogicznie do obwodu elektrycznego. Korzystając z tej metody John R. Koza opracował nowe wersje PID-a [1].
Stworzono ponadto eksperymentalny system, zbudowany na bazie algorytmów genetycznych, który sam produkuje roboty, poddaje ocenie fizycznego środowiska oraz optymalizuje pod kątem jak najlepszego poruszania się w tym środowisku. Projekt nosi nazwę Golem.
Niestety, aby ewolucja mogła zajść potrzeba bardzo dużo czasu. W praktyce oznacza to, konieczność badania populacji tysięcy układów, na przestrzeni setek pokoleń. Moc obliczeniowa dzisiejszych komputerów jest zbyt mała, aby sprostać takiemu zadaniu w rozsądnym czasie. Z tego powodu wykorzystuje się klastry komputerów. Na każdym przebywa pewna populacja układów. Co pewien czas, cząstka z nich migruje do innego komputera, aby polepszyć uzyskiwane wyniki. Jednak rozwój techniki komputerowej spowoduje, że za parę lat algorytmy genetyczne będą mogły trafić pod strzechy.
Przeszukiwanie
Algorytmy genetyczne zapewniają skuteczne mechanizmy przeszukiwania dużych przestrzeni rozwiązań. Gdyż grupowanie trzeba do tej kategorii zadań to oczywiste jest, że algorytmy genetyczne stosowane są w grupowaniu. Algorytmy genetyczne są bardziej niezależne od wstępnej inicjalizacji oraz mniej skłonne do znajdowania lokalnych rozwiązań w miejsce optymalnych. Przykładem bywa zagadnienie grupowania w którym w miejsce klasycznych algorytmów z powodzeniem stosuje się algorytmy genetyczne.
Sprawdź też
Bibliografia
- John R. Koza, A. Keane, Mattethew J. Streeter: O dokonywaniu wynalazków drogą ewolucji. (pol.)
- „Świat nauki”. Nr 4 (140), kwiecień 2003, s. 40-47 (pol.).
- D. E. Goldberg: Algorytmy genetyczne oraz ich zastosowania. Warszawa: WNT, 1998. (pol.)
- Z. Michalewicz: Algorytmy genetyczne + struktury danych = programy ewolucyjne. Warszawa: WNT, 1996. (pol.)
- J. Arabas: Wykłady z algorytmów ewolucyjnych. Warszawa: WNT, 2001. (pol.)
- R. Poli, W.B. Langdon, N.F. McPhee: A Field Guide to Genetic Programming. (ang.) (O książce)
- Alan M. Turing: Computing Machinery and Intelligence.
- „Mind”. Tom 59, nr 236, s. 433-460; X/1950 (ang.). (dostępny tekst)
- John R. Koza: Genetic Programming: On The Programming of Computers by Means of Natural Selection. MIT Press, 1992. (ang.)
- John R. Koza, James P. Rice: Genetic Programming: The Movie. MIT Press, 1992. (ang.)
- Randy L. Haupt, Sue Ellen Haupt: Practical Genetic Algorithms. John Wiley & Sons, 1998. (ang.)
- John R. Koza, Forest H. BennetII, David Andre, Martin A. Keane, Scott Brave: Genetic Programming III: Darwinian Invention and Problem. Solving. Morgan Kaufmann, 1999. (ang.)
- John R. Koza, Martin A. Keane, Matthew J. Streeter, William Mydlowec, Jessen Yu, Guido Lanza: Genetic Programming III: Videotape: Human-Competitive Machine Intelligence. Kluwer Academic Publishers, 2003. (ang.)
Linki zewnętrzne