Algorytm genetyczny

Z Encyklopedia Zarządzania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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