728 x 90

O algorytmach genetycznych

O algorytmach genetycznych

Coraz częściej w informatyce spotykamy nawiązania do rzeczywistych, występujących w przyrodzie zjawisk. Przykładem tego są algorytmy genetyczne, których ideę przybliżymy w tym wpisie.

Algorytmy ewolucyjne

Algorytmy ewolucyjne są (zgodnie z informacjami przedstawionymi w [1]) jednym ze sposobów aproksymacji najlepszego rozwiązania. Wywodzą się z obserwacji świata i sposobu rozmnażania się organizmów, oraz w szczególności z teorii doboru naturalnego Darwina, mówiącej o tym, że przeżywają organizmy silniejsze i lepiej przystosowane do środowiska. Rozwiązania kandydujące do miana najlepszego rozwiązania tworzą populację. Środowisko jest zdefiniowane za pomocą specjalnej funkcji. Rozwiązania żyją i ewoluują wykorzystując reprodukcje, mutacje, rekombinacje i selekcje. Każde kolejne pokolenie rozwiązań prezentuje lepsze wyniki. Algorytmy te nadają się do rozwiązywania wszelkiego rodzaju problemów [2], ponieważ nie są ograniczone żadnymi założeniami dotyczącymi rodzaju środowiska czy rodzajów rozwiązań.

Algorytmy genetyczne

Algorytmy genetyczne są szczególnym przypadkiem algorytmów ewolucyjnych. Rozważane są bardzo często jako uzupełnienie uczenia się ze wzmocnieniem. Podstawowe elementy używane podczas projektowania algorytmów genetycznych to dobrze zdefiniowane środowisko, w którym żyje populacja elementów. Każdy element populacji posiada własny genotyp.

Podstawowe operacje, które mogą być wykonane na elementach populacji to:

  • mutacja – umożliwiająca zmianę genotypu w obrębie pojedynczego elementu,
  • krzyżowanie – umożliwiające powstawanie nowych elementów potomnych za pomocą wyboru fragmentów genotypu z każdego z elementów macierzystych,
  • selekcja – powodująca usuwanie elementów gorszych jakościowo, czyli nie przystosowanych do środowiska.

W podstawowej wersji genotyp jest ciągiem długości n składającym się z elementów zbioru 0, 1. Modyfikacja problemu dopuszcza wykorzystanie jako elementów ciągu liczb z dowolnego zakresu. Daje to większe możliwości podczas projektowania opartych na tym pomyśle algorytmów.

Algorytmy genetyczne są projektowane tak, aby kolejne pokolenia elementów przybliżały coraz lepsze rozwiązanie zadanego problemu. Elementy macierzyste, które najgorzej przybliżają to rozwiązanie, zostają usunięte (giną). W większości podejść populacje rozrastają się do bardzo dużych rozmiarów.

(a) Elementy populacji w algorytmie genetycznym oraz podstawowe operacje na nich (b) mutacja, (c) krzyżowanie.

Wspólnymi cechami algorytmów ewolucyjnych, są:

  1. stosowanie operatorów genetycznych, które dostosowane są do postaci rozwiązań,
  2. przetwarzanie populacji rozwiązań, prowadzące do równoległego przeszukiwania przestrzeni rozwiązań z różnych punktów,
  3. w celu ukierunkowania procesu przeszukiwania wystarczającą informacją jest jakość aktualnych rozwiązań,
  4. celowe wprowadzenie elementów losowych.

Znaczenie

Algorytmy genetyczne pozwalają na szukanie rozwiązań w stosunkowo łatwy sposób, z pewną dozą losowości. Dlatego dobrze działają w przypadku analizy i pracy z nieustrukturyzowanymi danymi.  Bardzo ciekawym przypadkiem jest też użycie koncepcji w tzw. Programowaniu genetycznym: “konwencjonalne programowanie genetyczne dziedziczy nowe programy z istniejących na trzy różne sposoby. Punktowa mutacja losowo zamienia funkcje albo znaki terminalne w wybranej części drzewa z innym w obrębie tego samego drzewa” [4].

“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ęść z nich migruje do innego komputera, aby polepszyć uzyskiwane wyniki.” [3]

Źródła

[1] Rojas, Raul . 1996. Neural networks: a systematic introduction. New York, NY, USA: Springer-Verlag New York, Inc

[2] Back, Thomas. 1996. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford, UK: Oxford University Press.

[3] https://pl.wikipedia.org/wiki/Algorytm_genetyczny

[4] http://marek.piasecki.staff.iiar.pwr.edu.pl/dydaktyka/isa/2007/Kowalczyk_Damian.pdf

Źródło obrazów: opracowanie własne i freeimages.com

1 comment

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

1 Comment

  • Czytelnik
    21 sierpnia 2017, 15:51

    Bardzo dobry wpis. Zainspirował mnie do dalszej lektury o alg genetycznych. 🙂

    REPLY

Inne artykuły