Algorytm genetyczny

Algorytm genetyczny
Polecane artykuły


Algorytm genetyczny - Algorytm oparty na mechanizmach dziedziczności i doboru naturalnego. Łączy w sobie zasadę przeżycia najlepiej przystosowanych jednostek i zasadę losowej wymiany informacji. Takie połączenie skutkuje metodą poszukiwania obdarzoną dozą pomysłowości właściwej dla umysłu człowieka. W każdym kolejnym pokoleniu powstaje nowy zespół sztucznych organizmów (ciągów bitowych), utworzonych z połączenia fragmentów najlepiej przystosowanych przedstawicieli poprzedniego pokolenia (David E. Goldberg 1995 s. 17). Mimo losowości, algorytmy genetyczne nie są przypadkowe, a wykorzystują doświadczenia z przeszłości do najlepszego określenia nowego obszaru poszukiwań o spodziewanej, wyższej wydajności.

Historia powstania algorytmu genetycznego

Podstawą powstania algorytmu genetycznego była chęć zrobienia tego samego, co robi natura. Naśladuje on krok po kroku proces mutacji genetycznych u zwierząt - przeżywają najsilniejsze osobniki, a u kolejnych pokoleń nasilają się mocne cechy przodków. W latach 1957 - 1962 Barricelli, Fraser, Martin, Cockerham rozpoczęli proces powstawania algorytmu genetycznego modelując procesy genetyczne. W roku 1960 profesor John Holland z Uniwersytetu w Michigan w swojej książce Adaptation in Natural and Artificial Systems wyjaśnił i opisał istoty procesów adaptacyjnych występujących w przyrodzie. Stworzył również oprogramowanie, które odtwarzało podstawowe mechanizmy rządzące systemami biologicznymi. Holland wraz ze współpracownikami z uniwersytetu mieli dwa cele badań:

  1. Opisanie i wyjaśnienie w ścisły sposób istoty procesów adaptacyjnych w świecie przyrody,
  2. Stworzenie oprogramowania, które mogłoby odtwarzać podstawowe mechanizmy rządzące systemami biologicznymi.

Postawienie problemu w ten sposób skutkowało ważnymi odkryciami w badaniach systemowych.

Podstawowe pojęcia związane z algorytmem genetycznym

Biologia (genetyka) Algorytm genetyczny
Gen Bit
Chromosom Ciąg bitów
Osobnik Punkt w przestrzeni rozwiązań
Populacja Zbiór punktów
Krzyżowanie Wymiana ciągu bitów
Mutacja Negacja bitów

Tabela 1 - Odpowiedniki biologiczne podstawowych pojęć algorytmu genetycznego.

Odpowiedniki biologiczne podstawowych pojęć algorytmu genetycznego

  • Gen - Najmniejsza część chromosomu. Decyduje o dziedziczności jednej lub kilku cech.
  • Chromosom - Inaczej łańcuch lub ciąg kodowy. Jest to uporządkowany ciąg genów.
  • Osobnik - Najprostsza jednostka podlegająca ewolucji.
  • Populacja - Zbiór osobników zamieszkujących jedno środowisko.
  • Krzyżowanie - Losowe przecięcie dwóch chromosomów w jednym punkcie i zamiana podzielonych części między chromosomami.
  • Mutacja - Nagła zmiana materiału genetycznego.

Klasyczny algorytm genetyczny

Rys. 1 - Model przebiegu klasycznego algorytmu genetycznego. Opracowanie własne.

Klasyczny algorytm z kodowaniem binarnym składa się z następujących etapów:

  1. Etap wstępny - kodowanie problemu. Zakodowanie wszystkich możliwych rozwiązań w języku binarnym. Długość łańcuchów kodujących ustalamy z góry. Skonstruowanie funkcji.
  2. Konstrukcja populacji początkowej z całkowicie losowych N osobników. Liczba N zależy od czasu oraz stopnia złożoności problemu. Najczęściej wybierana wartość to 20-50 osobników.
  3. Zastosowanie operatorów genetycznych - mutacja (zamiana jednego bitu danego osobnika na przeciwną) lub krzyżowanie (zamiana fragmentów ciągu kodowego).
  4. Obliczenie wartości funkcji celu osobników. Ocena rozwiązania funkcją celu.
  5. Selekcja - Zamiana wartości obliczonej poprzednio funkcji na wartość przystosowania. Wybór spośród N osobników populacji pośredniej N osobników populacji końcowej za pomocą algorytmu "koło ruletki". Obliczenie sumy wartości funkcji celu, wkład każdego osobnika w sumę i potraktowanie obliczeń jako rozkład prawdopodobieństwa.
  6. Potraktowanie populacji końcowej jako populacji bieżącej. Powrót do punktu 3.

Algorytm można zatrzymać na żądanie użytkownika. Brak gwarancji na znalezienie optymalnego rozwiązania z powodu losowych działań mutacji, krzyżowania i selekcji.

Zalety i wady algorytmu genetycznego

Zalety

  • Uniwersalność. Możliwość użycia tego samego schematu przy zmianie jedynie funkcji celu.
  • Możliwość poradzenia sobie w warunkach, gdzie optymalizowana funkcja jest zaszumiona, zmienna w czasie lub ma wiele ekstremów lokalnych.
  • Brak wymaganej wiedzy na temat optymalizowanej funkcji.
  • Brak wymaganej funkcji celu - 'możemy wykorzystywać algorytmy genetyczne nawet wtedy, gdy jedyną rzeczą, jaką potrafimy powiedzieć o punktach przestrzeni stanów jest to, który z dwóch punktów jest lepszy (selekcja turniejowa).' (P. Rembelski, Wykład 10 - Algorytmy Ewolucyjne)
  • Szybkość metody.
  • Możliwość powtarzania obliczeń wielokrotnie.

Wady

  • Uniwersalność, metoda nie jest tak skuteczna jak metody specjalizowane.
  • Metoda jest wolniejsza niż proste heurystyki (na przykład: metoda zachłanna).
  • Możliwość osiągnięcia sukcesu wyłącznie przy prawidłowym zakodowaniu problemu i odpowiednim dobraniu fukcji celu.
  • Brak jednoznacznej metody kodowania problemu i dobrania funkcji celu. Potrzebne jest odpowiednie doświadczenie.
  • Brak pewności, czy znalezione rozwiązanie jest poprawne.

Zastosowanie algorytmu genetycznego

Występujące w realnym świecie problemy charakteryzują się zwykle bardzo dużą liczbą zmiennych (dyskretnych lub ciągłych), dużą złożonością przestrzeni poszukiwań (wiele ograniczeń i celów, które na dodatek mogą być ze sobą sprzeczne). Problemy te mogą się zmieniać w czasie (być dynamiczne), co pociąga za sobą konieczność szybkiego otrzymywania dobrych rozwiązań. (E. Figielska Algorytmy ewolucyjne i ich zastosowania s. 89-90). Planowanie i harmonogramowanie procesów produkcyjnych jest ważnym zastosowaniem algorytmów genetycznych. W większości zastosowania algorytmów genetycznych, harmonogram jest kodowany jako chromosom, który określa kolejność wykonywania poszczególnych czynności. To wymaga zastosowania operatorów genetycznych, które są odpowiednio zaprojektowane. Odpowiednie zakodowanie chromosomów i zaprojektowanie operatorów genetycznych reprezentują rozwiązania dopuszczalne. Kolejnym zastosowaniem algorytmu genetycznego jest przemysł chemiczny. Optymalizacja w zakładach chemicznych polega na modyfikacji struktury parametrów operacyjnych tak, aby znaleźć globalne optimum w celu wykonania pewnego zadania chemicznego (E. Figielska Algorytmy ewolucyjne i ich zastosowania s. 90). Algorytmy stosuje się także w medycynie, zwłaszcza jako pomoc przy leczeniu nowotworów. Pomaga podejmować decyzję o sposobie leczenia, jak również optymalizuje czas pacjenta i wykorzystanie aparatury.

Bibliografia

Autor: Julia Witana