Jak działają algorytmy genetyczne? Krok po kroku

Algorytmy genetyczne (AG) to metoda optymalizacji inspirowana darwinowską teorią ewolucji. Zamiast szukać idealnego rozwiązania analitycznie, AG hodują populację rozwiązań-kandydatów, pozwalając najlepszym przetrwać, łączyć się i mutować — pokolenie po pokoleniu — aż wyłoni się rozwiązanie bliskie optymalnemu.

Kiedy używać algorytmów genetycznych?

AG sprawdzają się, gdy:

• Przestrzeń rozwiązań jest zbyt duża do pełnego przeszukania (np. problem komiwojażera z 50 miastami: 50! ≈ 3×10⁶⁴ permutacji)
• Funkcja celu nie jest różniczkowalna — nie możesz użyć gradient descent, bo nie ma gradientów
• Krajobraz fitness jest multimodalny — wiele lokalnych optimów, potrzebna eksploracja
• Rozwiązanie nie musi być idealne — wystarczająco dobre rozwiązanie w rozsądnym czasie

Typowe zastosowania: planowanie tras, harmonogramowanie, projektowanie obwodów, optymalizacja hiperparametrów, projektowanie struktur (kratownice, anteny NASA), gry i sztuczne życie.

Terminologia biologiczna → obliczeniowa

Algorytm genetyczny krok po kroku

Krok 1: Inicjalizacja populacji

Utwórz początkową populację N losowych rozwiązań. Każde rozwiązanie jest zakodowane jako chromosom — najczęściej wektor bitów (binarny), ale może to być wektor liczb rzeczywistych, permutacja lub drzewo.

Przykład: szukamy maksimum funkcji f(x) = x² dla x ∈ [0, 31]. Kodujemy x binarnie na 5 bitach:

• Osobnik 1: 10110 (= 22, fitness = 484)
• Osobnik 2: 01001 (= 9, fitness = 81)
• Osobnik 3: 11000 (= 24, fitness = 576)
• Osobnik 4: 00101 (= 5, fitness = 25)

Krok 2: Ewaluacja (obliczenie fitness)

Oblicz wartość funkcji celu (fitness) dla każdego osobnika. To jedyny krok, w którym algorytm „wie", co optymalizuje — reszta mechaniki jest uniwersalna.

Krok 3: Selekcja

Wybierz osobniki, które staną się „rodzicami" nowego pokolenia. Lepiej przystosowane mają większą szansę na wybór, ale słabsze też mogą przetrwać (utrzymanie różnorodności).

Popularne metody selekcji: selekcja ruletkowa, turniejowa i rankingowa.

Krok 4: Krzyżowanie (crossover)

Para rodziców wymienia fragmenty chromosomów, tworząc potomków łączących cechy obu rodziców.

Krzyżowanie jednopunktowe:

• Rodzic 1: 10|110
• Rodzic 2: 01|001
• Potomek 1: 10|001
• Potomek 2: 01|110

Punkt krzyżowania wybierany jest losowo. Potomkowie dziedziczą fragmenty obu rodziców.

Prawdopodobieństwo krzyżowania (pₓ): typowo 0,7–0,9. Nie każda para się krzyżuje — część przechodzi do nowego pokolenia bez zmian.

Krok 5: Mutacja

Losowa zmiana pojedynczych genów z małym prawdopodobieństwem. Dla chromosomu binarnego: odwrócenie bitu (0→1 lub 1→0).

Przykład:

• Przed mutacją: 10001
• Po mutacji: 10101 (trzeci bit zmutowany)

Prawdopodobieństwo mutacji (pₘ): typowo 0,001–0,05. Mutacja jest rzadka, ale kluczowa — wprowadza nową informację genetyczną, zapobiegając przedwczesnej zbieżności.

Krok 6: Utworzenie nowego pokolenia

Potomkowie (po krzyżowaniu i mutacji) zastępują starą populację. Opcjonalnie: elityzm — najlepsze osobniki z poprzedniego pokolenia przechodzą bezpośrednio do nowego (chroni najlepsze dotychczasowe rozwiązanie).

Krok 7: Warunek stopu

Powtarzaj kroki 2–6, aż:

• Osiągnięto maksymalną liczbę pokoleń
• Fitness najlepszego osobnika nie poprawia się od N pokoleń (stagnacja)
• Osiągnięto wystarczająco dobre rozwiązanie (znany próg)

Reprezentacja problemu — klucz do sukcesu

Sposób kodowania rozwiązania jako chromosomu fundamentalnie wpływa na skuteczność AG:

Kodowanie binarne

Klasyczne, najprostsze. Rozwiązanie jako ciąg bitów. Dobre dla problemów dyskretnych.

Kodowanie rzeczywiste

Chromosom to wektor liczb zmiennoprzecinkowych. Naturalne dla optymalizacji ciągłych funkcji. Wymaga zmodyfikowanych operatorów krzyżowania (np. blend crossover: potomek = α·rodzic₁ + (1-α)·rodzic₂).

Kodowanie permutacyjne

Chromosom to permutacja (np. kolejność miast w TSP). Wymaga specjalnych operatorów krzyżowania zachowujących poprawność permutacji (np. Order Crossover, Partially Mapped Crossover).

Kodowanie drzewiaste

Chromosom to drzewo (np. wyrażenie matematyczne, program komputerowy). Używane w programowaniu genetycznym (GP).

Parametry algorytmu genetycznego

Zalety algorytmów genetycznych

1. Uniwersalność — działają na dowolnym problemie, o ile potrafisz zdefiniować fitness i reprezentację
2. Brak wymagań matematycznych — nie potrzebują gradientów, ciągłości ani różniczkowalności
3. Eksploracja globalna — populacja przeszukuje wiele regionów przestrzeni jednocześnie, zmniejszając ryzyko utknięcia w lokalnym minimum
4. Równoległość — osobniki można ewaluować niezależnie (idealnie do GPU/klastrów)
5. Elastyczność — łatwo dodać ograniczenia, zmieniać funkcję celu, łączyć z innymi metodami

Ograniczenia

1. Brak gwarancji optymalności — AG znajduje rozwiązanie „dobre", ale niekoniecznie najlepsze
2. Kosztowna ewaluacja — jeśli obliczenie fitness trwa długo (np. symulacja fizyczna), AG jest wolny
3. Trudność parametryzacji — rozmiar populacji, pₓ, pₘ wymagają eksperymentowania
4. Przedwczesna zbieżność — populacja może „utknąć" wokół nieoptymalnego rozwiązania, jeśli różnorodność genetyczna spada zbyt szybko

Algorytmy genetyczne vs. gradient descent

AG i gradient descent to komplementarne narzędzia. Sieci neuronowe uczą się gradient descentem, ale AG mogą optymalizować ich architekturę (Neural Architecture Search) lub hiperparametry.