Algorytm genetyczny

Algorytm genetyczny
Polecane artykuły
Typizacja Permutacja System ekspercki Algorytm przetwarzania Komputery kwantowe Algorytm ewolucyjny Metoda Blocha-Schmigalli Projektowanie eksperymentów Backlog produktu

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.

TL;DR

Algorytm genetyczny to metoda sztucznej inteligencji, która naśladuje procesy dziedziczenia i doboru naturalnego. Polega na tworzeniu nowych sztucznych organizmów poprzez kombinację najlepiej przystosowanych cech poprzednich generacji. Algorytmy genetyczne mają wiele zastosowań, m.in. w planowaniu procesów produkcyjnych, przemyśle chemicznym i medycynie. Mają wiele zalet, takich jak uniwersalność i zdolność do poradzenia sobie z problemami o wysokiej złożoności. Jednak mają też wady, takie jak wolniejsza wydajność w porównaniu do innych metod optymalizacji.

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

• E. Goldberg D. (1989). Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne (przekład dr K. Grygiel, Warszawa 1995)
• Figielska E. - Algorytmy ewolucyjne i ich zastosowania' - Zeszyty naukowe 81-92
• Michalewicz Z. (1992, 1994, 1996). Algorytmy Genetyczne+Struktury Danych=Programy Ewolucyjne, Wydawnictwa Naukowo-Techniczne (przekład dr hab. inż. Z. Nahorski 1996)
• Różanowski K. - Sztuczna inteligencja: rozwój, szanse i zagrożenia - Zeszyty naukowe 109-135
• Wieleba R. - Inżynieria wiedzy w systemach ekspertowych - Zeszyty naukowe 195-216 s. 204

Autor: Julia Witana