Czym jest Algorytm genetyczny (Genetic algorithm)?
Algorytm genetyczny to metoda poszukiwania rozwiązań inspirowana biologiczną ewolucją, formalnie opisana przez Johna H. Hollanda z University of Michigan w połowie lat siedemdziesiątych XX w. Podejście to traktuje każdy potencjalny wynik problemu jako osobnika w populacji, a procedurę optymalizacji jako proces selekcji naturalnej. Złożone z krzyżowania, mutacji i oceny kondycji rozwiązania powoli udoskonalają się z pokolenia na pokolenie, aż spełnią wcześniej zdefiniowane kryteria jakości.
Geneza i rozwój koncepcji
Pierwsze prace Hollanda zostały zebrane w książce Adaptation in Natural and Artificial Systems z 1975 r., w której autor formalnie zestawił operator krzyżowania, mutacji oraz selekcji turniejowej. W Polsce zagadnienie przybliżali m.in. prof. Zbigniew Michalewicz oraz dr Zbigniew Szkopek, którzy rozszerzali teorię o praktyczne zastosowania w planowaniu produkcji i logistyce.
Jak dokładnie działa Algorytm genetyczny (Genetic algorithm)
Proces rozpoczyna się od losowego (lub heurystycznie zainicjowanego) zestawu rozwiązań zakodowanych w postaci genotypu, najczęściej ciągu bitów, liczb całkowitych bądź realnych. Funkcja przystosowania mierzy, jak dobrze dany osobnik radzi sobie z problemem. W każdej iteracji algorytm wybiera najbardziej obiecujące osobniki, łączy ich genotypy w procesie krzyżowania oraz wprowadza niewielkie, losowe zmiany zwane mutacjami. Nowo powstała populacja przechodzi ocenę i cykl się powtarza, aż do osiągnięcia zadanej dokładności bądź wyczerpania limitu obliczeń. W odróżnieniu od metod gradientowych, GA nie wymaga informacji o pochodnych, dzięki czemu pracuje również na problemach dyskretnych lub o nieciągłej, złożonej powierzchni kosztu.
Zastosowania w praktyce
Konstrukcja anten o nieregularnych kształtach dla NASA, harmonogramowanie zadań w fabrykach samochodowych, optymalizacja tras kurierów czy dobór hiperparametrów sieci neuronowych to tylko kilka przykładów obszarów, w których GA pomaga znaleźć dobre rozwiązania w akceptowalnym czasie. W porównaniu z klasycznymi metodami liniowymi algorytmy genetyczne lepiej radzą sobie z problemami wielomodalnymi, gdzie powierzchnia funkcji celu zawiera liczne ekstrema lokalne.
Zalety i ograniczenia
Największą zaletą jest odporność na pułapki gradientowe oraz elastyczność reprezentacji, co pozwala stosować GA do optymalizacji zarówno dyskretnej, jak i ciągłej. Droga ku optymalnemu wynikowi bywa jednak kosztowna obliczeniowo, a sukces zależy od prawidłowego doboru parametrów, takich jak wielkość populacji czy prawdopodobieństwo mutacji. Istnieje również ryzyko przedwczesnej konwergencji, gdy zbyt mała różnorodność genotypów ogranicza eksplorację przestrzeni rozwiązań.
Na co uważać?
Kluczowe jest dopasowanie sposobu kodowania danych do natury problemu, aby uniknąć utraty informacji podczas krzyżowania. Warto monitorować różnorodność populacji, np. poprzez wskaźniki entropii, i w razie potrzeby zwiększać współczynnik mutacji. Podejście stochastyczne sprzyja eksploracji, lecz rezultaty mogą różnić się między uruchomieniami — w projektach produkcyjnych zaleca się wielokrotne przebiegi i statystyczną ocenę stabilności rozwiązania.
Dodatkowe źródła
Szczegóły teoretyczne i praktyczne przykłady można znaleźć w artykule Algorytm genetyczny – Wikipedia oraz w klasycznym opracowaniu J. H. Holland, Adaptation in Natural and Artificial Systems. Zastosowania inżynierskie omawia strona Evolutionary Algorithms at NASA, a aktualny przegląd literatury można znaleźć w publikacji arXiv:2001.06434.
