Czym jest Algorytm genetyczny (genetic algorithm, GA)?
Algorytm genetyczny to metoda optymalizacyjna należąca do szerszej rodziny algorytmów ewolucyjnych. Posługuje się metaforą dziedziczenia i doboru naturalnego, aby iteracyjnie ulepszać populację potencjalnych rozwiązań. Koncepcję ukształtował John H. Holland z University of Michigan, publikując w 1975 roku książkę Adaptation in Natural and Artificial Systems, w której przedstawił formalny opis operatorów selekcji, krzyżowania i mutacji. Od tamtej pory GA znalazły zastosowanie w inżynierii, ekonomii, bioinformatyce oraz w systemach wspomagających podejmowanie decyzji.
Jak dokładnie działa Algorytm genetyczny (genetic algorithm, GA)
Kodowanie rozwiązań i inicjalizacja populacji
Każde potencjalne rozwiązanie problemu reprezentowane jest jako ciąg symboli, zwany chromosomem. Najczęściej stosuje się kod binarny lub bezpośrednie wektory liczbowe, choć w praktyce możliwe jest również kodowanie symboliczne czy drzewiaste. Proces rozpoczyna się od losowej populacji takich chromosomów.
Selekcja
Wartość każdego osobnika mierzy się funkcją przystosowania, która odzwierciedla jakość rozwiązania. Wyższe przystosowanie zwiększa szansę osobnika na udział w reprodukcji. Popularnymi metodami selekcji są koło ruletki oraz turniejowa, ale wybór techniki zależy od charakterystyki zadania.
Krzyżowanie i mutacja
Wyselekcjonowane osobniki łączą się w pary i wymieniają fragmenty swoich chromosomów, tworząc potomstwo. Dzięki temu pojawiają się nowe kombinacje cech, które mogą przewyższać rodziców pod względem jakości. Mutacje natomiast losowo zmieniają niewielkie fragmenty potomnych chromosomów, co zapobiega zbyt wczesnej utracie różnorodności genetycznej.
Zastępowanie i kryteria zatrzymania
Nowo utworzona generacja zastępuje całość lub część populacji rodzicielskiej. Proces trwa do momentu spełnienia kryterium zatrzymania: osiągnięcia limitu iteracji, czasu lub stabilizacji wartości funkcji przystosowania.
Zastosowania w praktyce
GA są szczególnie cenione w sytuacjach, w których przestrzeń poszukiwań jest nieciągła, silnie nieliniowa lub pozbawiona pochodnych. W telekomunikacji umożliwiają optymalizację rozmieszczenia anten 5G, minimalizując zakłócenia i maksymalizując zasięg. W logistyce służą do planowania tras wielopoziomowych dostaw, łącząc poziomy magazynowania z harmonogramem dostaw. W bioinformatyce pomagają dopasować sekwencje białek do struktur trzeciorzędowych, gdy klasyczne metody gradientowe zawodzą.
Zalety i ograniczenia
Algorytmy genetyczne nie korzystają z informacji o gradientach, dzięki czemu bez trudu radzą sobie z funkcjami o wielu lokalnych minimach czy lukach w przestrzeni poszukiwań. Odporność na utknięcie w lokalnym optimum podnosi również stochastyczny charakter operatorów. Z drugiej strony GA wymagają znacznych zasobów obliczeniowych i bywają wolniejsze od metod deterministycznych, gdy problem ma dobrze uwarunkowaną, gładką strukturę – przykładem są modele regresji, gdzie proste algorytmy gradientowe prowadzą do celu szybciej i precyzyjniej. Największe korzyści GA przynoszą więc tam, gdzie klasyczne narzędzia nie mają zastosowania lub ich efektywność spada.
Na co uważać?
Nadmierne dobranie parametrów, takich jak zbyt wysoki współczynnik mutacji, może prowadzić do efektu dryfu losowego, w którym populacja traci pamięć o dotychczasowych ulepszeniach. Zbyt niska różnorodność początkowej populacji sprzyja natomiast zacięciu się algorytmu w suboptymalnych rozwiązaniach. Ważne jest także odpowiednie zdefiniowanie funkcji przystosowania – jeśli jest źle skalibrowana, algorytm może promować niepożądane cechy.
Dodatkowe źródła
Pełniejszy opis teorii ewolucyjnych można znaleźć w książce Johna Hollanda, dostępnej w domenie akademickiej. Streszczenie koncepcji prezentuje hasło Wikipedia, a najnowsze badania porównawcze publikowane są regularnie w serwisie arXiv. Poszukując implementacji, warto zajrzeć do repozytorium pagmo2, które zawiera wiele wariantów GA i przykładów zastosowań.
