Algorytm genetyczny

Algorytmy genetyczne

Algorytm genetyczny to typ heurystyki, która przeszukuje przestrzeń alternatywnych rozwiązań problemu, aby znaleźć te najlepsze.

Mechanizm działania algorytmów genetycznych jest zbliżony do procesu ewolucji biologicznej, co nie jest przypadkowe, ponieważ ich twórca, John Henry Holland, czerpał inspirację z biologii. Obecnie algorytmy te klasyfikowane są jako algorytmy ewolucyjne.

Wstęp

Problem definiuje środowisko, w którym występuje pewna populacja osobników. Każdy z tych osobników zawiera zbiór informacji, które stanowią jego genotyp, a które są podstawą do utworzenia fenotypu. Fenotyp to zbiór cech ocenianych przez funkcję przystosowania, która modeluje środowisko. Mówiąc inaczej, genotyp opisuje proponowane rozwiązanie problemu, a funkcja przystosowania ocenia jego jakość.

Genotyp składa się z chromosomów, w których zakodowany jest fenotyp oraz ewentualnie dodatkowe informacje dla algorytmu genetycznego. Chromosom zbudowany jest z genów.

Algorytmy ewolucyjne wyróżniają się od tradycyjnych metod optymalizacji kilkoma wspólnymi cechami:

użycie operatorów genetycznych dostosowanych do formy rozwiązań,
przetwarzanie populacji rozwiązań, co prowadzi do równoległego przeszukiwania przestrzeni rozwiązań z różnych punktów,
ocena jakości aktualnych rozwiązań jako wystarczająca informacja do ukierunkowania procesu przeszukiwania,
celowe wprowadzenie elementów losowych.

Zapis algorytmu

Typowy przebieg działania algorytmu wygląda następująco:

Tworzenie pewnej populacji początkowej.
Ocena populacji (selekcja). Osobniki z najlepszym przystosowaniem uczestniczą w reprodukcji.
Genotypy wybranych osobników poddawane są operatorom ewolucyjnym, takim jak:

krzyżowanie – łączenie genotypów rodziców,
mutacja – wprowadzenie drobnych losowych zmian.

Powstaje następne pokolenie. Aby utrzymać stałą liczbę osobników w populacji, najlepiej przystosowane osobniki są powielane, a najsłabsze eliminowane. Jeśli nie znaleziono wystarczająco dobrego rozwiązania, algorytm wraca do kroku drugiego. W przeciwnym razie wybierany jest najlepszy osobnik z populacji, którego genotyp stanowi uzyskany wynik.

Działanie algorytmu genetycznego obejmuje kilka kluczowych kwestii do ustalenia:

ustalenie genomu jako reprezentanta wyniku,
ustalenie funkcji przystosowania/dopasowania,
ustalenie operatorów przeszukiwania.

Kodowanie

Kodowanie jest kluczowym etapem projektowania algorytmu. Sposób, w jaki informacje o proponowanym rozwiązaniu są zakodowane w chromosomie, ma istotny wpływ na szybkość i jakość uzyskiwanych wyników. Nieodpowiednie kodowanie może prowadzić do sytuacji, w której fragment przestrzeni, zawierający najlepsze rozwiązania, nigdy nie zostanie przeszukany.

Najczęściej stosowane metody kodowania chromosomu obejmują:

wektory genów, gdzie każdy gen może być jedno- lub wielobitową liczbą całkowitą lub liczbą rzeczywistą,
struktury drzewiaste.

Funkcja przystosowania

Selekcja osobników do oceny odbywa się według określonych kryteriów, które zapisywane są w formie funkcji oceny, zwanej również funkcją przystosowania. Algorytmy genetyczne dążą zazwyczaj do jej minimalizacji (lub maksymalizacji). Jako kryterium często stosuje się funkcję celu dla danego problemu optymalizacji.

Funkcja oceny

Funkcja oceny stanowi miarę jakości danego osobnika (fenotypu, rozwiązania) w populacji. Dla każdego osobnika jest ona obliczana na podstawie modelu rozwiązywanego problemu. Na przykład, w przypadku projektowania obwodu elektrycznego o określonej charakterystyce, funkcja oceny premiuje rozwiązania najbardziej zbliżone do tej charakterystyki, a także te zbudowane z jak najmniejszej liczby elementów. W procesie selekcji faworyzowane są najlepiej przystosowane osobniki, które stają się rodzicami dla nowej populacji.

Metody selekcji

Istnieje wiele metod selekcji. Przykładowo, można zastosować metodę ruletki. W tym przypadku tworzony jest wirtualny krąg, którego segmenty odpowiadają poszczególnym osobnikom. Im lepszy osobnik, tym większy segment koła mu przypada. Rozmiar segmentów może być uzależniony od wartości funkcji oceny, gdzie wysoka wartość oznacza wysokie przystosowanie. W takim układzie prawdopodobieństwo wyboru lepszego osobnika jako rodzica jest wyższe. Niestety, ewolucja w tym algorytmie z każdym krokiem może zwalniać, gdyż podobne osobniki otrzymują równą szansę i presja selekcyjna maleje, co sprawia, że algorytm słabiej rozróżnia osobniki dobre od słabszych.

Metoda rankingowa eliminuje ten problem. Obliczana jest funkcja oceny dla każdego osobnika, a następnie są one uszeregowane od najlepszego do najgorszego. Pierwsze osobniki uzyskują prawo do rozmnażania, a reszta jest eliminowana z populacji. Wadą tej metody jest brak wrażliwości na różnice między kolejnymi osobnikami w kolejce, co może prowadzić do sytuacji, w której sąsiadujące rozwiązania mają różne wartości funkcji oceny, ale otrzymują prawie równą ilość potomstwa.

Wprowadzenie metod selekcji wielokryterialnej pozwala na stworzenie kilku różnych funkcji oceny, które oceniają różne cechy osobników osobno. Na przykład, osobniki mogą być uporządkowane w kilku szeregach, co czyni proces selekcji bardziej złożonym.

Selekcja zwiększa prawdopodobieństwo reprodukcji osobników o wysokim przystosowaniu, co prowadzi do coraz lepiej przystosowanych pokoleń. Z drugiej strony, zmniejsza różnorodność genotypu w populacji, co może prowadzić do monopolizacji przez niewielkie różnice w osobnikach. Może to skutkować zbieżnością kolejnych najlepszych rozwiązań do pewnej granicy, a czasami przedwczesną zbieżnością, która blokuje ewolucję i prowadzi do lokalnych ekstremów, które mogą być dalekie od oczekiwanych globalnych rozwiązań. Częściowym rozwiązaniem tego problemu jest losowa mutacja genotypu osobników.

Operatory kodowania

Każde pokolenie poddawane jest operacjom za pomocą operatorów ewolucyjnych. Celem jest wygenerowanie nowego pokolenia, które być może będzie lepiej przystosowane do ustalonego środowiska.

Operator krzyżowania łączy cechy pochodzące z różnych osobników populacji, natomiast operator mutacji zwiększa różnorodność tych osobników.

Przynależność algorytmu do klasy algorytmów genetycznych zależy głównie od zastosowania operatora krzyżowania oraz pracy z całymi populacjami osobników. Równie ważny jest operator mutacji, który jest sposobem na eksplorację przestrzeni rozwiązań. Jednak w niektórych przypadkach jego zastosowanie nie jest kluczowe.

Krzyżowanie

Krzyżowanie polega na połączeniu losowo wybranych genotypów w jeden. Celem jest, aby potomek dwóch osobników rodzicielskich miał zestaw cech będący kombinacją ich cech (możliwe, że tych najlepszych).

Sposób krzyżowania zależy od kodowania chromosomów oraz specyfiki problemu, ale można wskazać kilka standardowych metod:

rozcięcie dwóch chromosomów i stworzenie nowego poprzez połączenie lewej części jednego rodzica z prawą częścią drugiego (dla chromosomów z kodowaniem binarnym i całkowitoliczbowym),
stosowanie operacji logicznych (w przypadku kodowania binarnego),
obliczenie wartości średniej genów (w przypadku kodowania liczbami rzeczywistymi).

Mutacja

Mutacja wprowadza losowe zmiany do genotypu. Jej celem jest wprowadzenie różnorodności w populacji, co zapobiega (przynajmniej częściowo) przedwczesnej zbieżności algorytmu. Mutacja zachodzi z określonym prawdopodobieństwem, zazwyczaj wynoszącym około 1%. To niskie prawdopodobieństwo, ponieważ zbyt silna mutacja może przynieść odwrotny efekt, niszcząc dobre rozwiązania. Dlatego w procesie ewolucji mutacja odgrywa drugorzędną rolę, szczególnie w przypadku długich chromosomów.

Dla chromosomów kodowanych binarnie, zazwyczaj losuje się dwa geny i zamienia je miejscami lub neguje jeden z genów. W przypadku genotypów zakodowanych liczbami całkowitymi stosuje się permutacje. Natomiast dla genotypów zakodowanych liczbami rzeczywistymi wprowadza się losowe zmiany do przypadkowych genów zgodnie z danym rozkładem, najczęściej normalnym.

Zastosowania algorytmów genetycznych

Rozwiązywanie problemów NP

Algorytmy genetyczne są używane tam, gdzie sposób rozwiązania problemu nie jest dobrze określony, ale istnieje metoda oceny jakości rozwiązania. Przykładem może być problem komiwojażera, gdzie należy znaleźć najkrótszą trasę łączącą wszystkie miasta, przechodząc przez każde tylko raz. Ocena jakości proponowanej trasy jest szybka, jednak znalezienie optymalnej trasy jest problemem NP-trudnym. Zastosowanie podejścia ewolucyjnego pozwala na szybkie znalezienie dobrego rozwiązania, ale można jedynie liczyć na uzyskanie suboptymalnych wyników, co wynika z formalnej trudności problemów NP. Algorytmy genetyczne dobrze radzą sobie również z przybliżaniem ekstremów funkcji, które nie mogą być obliczone analitycznie.

Projektowanie genetyczne

Algorytmy genetyczne są także wykorzystywane do zarządzania populacją sieci neuronowych. Projektowanie maszyn czy obwodów elektrycznych stanowi doskonałą okazję do zastosowania algorytmów genetycznych. Inżynierowie, tworząc nowe projekty, niekoniecznie muszą dążyć do znalezienia najlepszego rozwiązania, lecz wystarczy, że spełnią określone warunki oraz zoptymalizują projekt. Algorytmy genetyczne, w przeciwieństwie do ludzi, nie działają schematycznie, co czasami prowadzi do innowacyjnych rozwiązań. Dodatkowo, ludzie często opierają się na przybliżonych modelach, które mogą wprowadzać w błąd, podczas gdy algorytm genetyczny może przeanalizować złożony model i znaleźć rozwiązanie, które umknęłoby ludzkiemu umysłowi.

Projektowanie obwodów elektrycznych

Algorytmy genetyczne można zastosować w projektowaniu obwodów elektrycznych. Ocena każdego osobnika opiera się na liczbie elementów oraz ich właściwościach elektrycznych, które można łatwo obliczyć. Główna różnica polega na tym, że algorytm buduje osobnika na podstawie genomu, który jest instrukcją dla programu, który tworzy obwód elektryczny. Proces rozpoczyna się od prostego połączenia wejścia z wyjściem, a następnie program dodaje lub usuwa połączenia i elementy. Taki obwód jest oceniany na podstawie prostych zasad fizycznych. Podobny algorytm genetyczny został wykorzystany do samodzielnego zbudowania filtru drabinkowego. Analogiczne podejście można zastosować w projektowaniu anten, gdzie wirtualny budowniczy porusza się w trójwymiarowej przestrzeni, ustawiając metalowe elementy odbijające fale.

Jednym z nowatorskich zastosowań algorytmów genetycznych jest ich integracja z układami FPGA (field-programmable gate arrays), które można szybko programować w celu zmiany struktury obwodu elektrycznego. Algorytmy genetyczne badają zwykle zachowanie symulowanych pokoleń. Dzięki układom FPGA możliwe jest ewoluowanie rzeczywistych obwodów elektrycznych, które są wprowadzane do chipa, a następnie ich właściwości elektryczne są testowane w rzeczywistym obwodzie. To pozwala ewolucji wykorzystać fizyczne właściwości realnego układu elektrycznego.

Okazało się, że także regulatory stosowane w automatyce mogą być udoskonalone przy pomocy algorytmów genetycznych. Najpopularniejszy algorytm sterowania, czyli PID, można opisać jako zestaw połączonych członów różniczkujących i całkujących. Odpowiedni algorytm genetyczny może stworzyć taki układ analogicznie do obwodu elektrycznego. Wykorzystując tę metodę, John R. Koza opracował nowe wersje PID.

Stworzono również eksperymentalny system oparty na algorytmach genetycznych, który samodzielnie produkuje roboty, ocenia ich fizyczne środowisko i optymalizuje ich ruch w tym środowisku. Projekt ten nosi nazwę Golem.

Jednakże, aby ewolucja mogła przebiegać, potrzeba znacznej ilości czasu. W praktyce oznacza to konieczność badania populacji tysięcy układów przez setki pokoleń. Moc obliczeniowa współczesnych komputerów bywa niewystarczająca, aby sprostać temu zadaniu w rozsądnym czasie. Dlatego wykorzystuje się klastry komputerów, na których przebywa pewna populacja układów. Co pewien czas część z nich migruje do innego komputera, co pozwala na poprawę wyników. W miarę postępu technologii komputerowej, za kilka lat algorytmy genetyczne mogą stać się bardziej powszechne.

Przeszukiwanie

Algorytmy genetyczne oferują skuteczne mechanizmy przeszukiwania dużych przestrzeni rozwiązań. Z racji tego, że grupowanie należy do tej kategorii zadań, algorytmy genetyczne znajdują zastosowanie w tej dziedzinie. Charakteryzują się one większą niezależnością od wstępnej inicjalizacji oraz mniejszą skłonnością do znajdowania lokalnych rozwiązań zamiast rozwiązań optymalnych. Przykładem może być zagadnienie grupowania, w którym algorytmy genetyczne z powodzeniem zastępują klasyczne metody.

Zobacz też

Bibliografia

John R. Koza, A. Keane, Matthew J. Streeter: O dokonywaniu wynalazków drogą ewolucji. (pol.). Brak numerów stron w książce.
„Świat nauki”. Nr 4 (140), kwiecień 2003, s. 40–47. (pol.). Brak numeru strony.
D. E. Goldberg: Algorytmy genetyczne i ich zastosowania. Warszawa: WNT, 1998. (pol.). Brak numerów stron w książce.
Z. Michalewicz: Algorytmy genetyczne + struktury danych = programy ewolucyjne. Warszawa: WNT, 1996. (pol.). Brak numerów stron w książce.
J. Arabas: Wykłady z algorytmów ewolucyjnych. Warszawa: WNT, 2001. (pol.). Brak numerów stron w książce.
R. Poli, W.B. Langdon, N.F. McPhee: A Field Guide to Genetic Programming. 2008. (ang.). Brak numerów stron w książce (O książce).
Alan M. Turing: Computing Machinery and Intelligence. Brak numerów stron w książce.
„Mind”. Tom 59, nr 236, s. 433–460; X/1950. (ang.). Brak numeru strony (dostępny tekst).
John R. Koza: Genetic Programming: On The Programming of Computers by Means of Natural Selection. MIT Press, 1992. (ang.). Brak numerów stron w książce.
John R. Koza, James P. Rice: Genetic Programming: The Movie. MIT Press, 1992. (ang.). Brak numerów stron w książce.
Randy L. Haupt, Sue Ellen Haupt: Practical Genetic Algorithms. John Wiley & Sons, 1998. (ang.). Brak numerów stron w książce.
John R. Koza, Forest H. Bennet II, David Andre, Martin A. Keane, Scott Brave: Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann, 1999. (ang.). Brak numerów stron w książce.
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.). Brak numerów stron w książce.