Algorytmy genetyczne (genetic algorithms, GA) to metody optymalizacji inspirowane teorią ewolucji Karola Darwina. Zamiast szukać rozwiązania analitycznie, algorytm genetyczny symuluje proces doboru naturalnego — tworzy populację kandydackich rozwiązań, ocenia ich „przystosowanie" i pozwala najlepszym „rozmnażać się", tworząc kolejne pokolenia coraz lepszych rozwiązań. To jedno z najbardziej eleganckich podejść w sztucznej inteligencji.
Czym są algorytmy genetyczne?
Algorytm genetyczny to metaheurystyczna technika przeszukiwania przestrzeni rozwiązań, która naśladuje mechanizmy ewolucji biologicznej: selekcję naturalną, krzyżowanie (rekombinację genetyczną) i mutację. Należy do szerszej rodziny algorytmów ewolucyjnych (evolutionary algorithms), obok strategii ewolucyjnych, programowania genetycznego i ewolucji różnicowej.
GA rozwiązują problemy, w których:
- Przestrzeń rozwiązań jest zbyt duża do przeszukania wyczerpującego
- Brak analitycznej metody znalezienia optimum
- Funkcja celu jest nieciągła, nieliniowa lub zaszumiona
- Istnieje wiele lokalnych optimów (i chcemy znaleźć globalne)
Algorytmy genetyczne zaproponował John Holland w 1975 roku w książce „Adaptation in Natural and Artificial Systems". Jego student, David Goldberg, spopularyzował GA w zastosowaniach inżynierskich w książce „Genetic Algorithms in Search, Optimization, and Machine Learning" (1989).
Inspiracja biologiczna
Zrozumienie algorytmów genetycznych wymaga znajomości ich biologicznych odpowiedników:
Ewolucja darwinowska
Teoria ewolucji opiera się na trzech filarach:
- Zmienność — osobniki w populacji różnią się między sobą
- Dziedziczność — cechy rodziców są przekazywane potomstwu
- Selekcja — osobniki lepiej przystosowane do środowiska mają większe szanse na przetrwanie i rozmnożenie
Te trzy mechanizmy, działając przez miliony lat, doprowadziły do powstania niezwykłej różnorodności i złożoności życia na Ziemi — od bakterii po ludzki mózg.
Mapowanie biologia → informatyka
| Biologia | Algorytm genetyczny |
|---|---|
| Chromosom | Zakodowane rozwiązanie (wektor bitów, liczb) |
| Gen | Pojedynczy parametr rozwiązania |
| Allel | Konkretna wartość genu |
| Genotyp | Zakodowana reprezentacja rozwiązania |
| Fenotyp | Zdekodowane rozwiązanie (to, co oceniamy) |
| Populacja | Zbiór kandydackich rozwiązań |
| Pokolenie | Jedna iteracja algorytmu |
| Przystosowanie (fitness) | Jakość rozwiązania (wartość funkcji celu) |
Jak działa algorytm genetyczny — krok po kroku
Krok 1: Reprezentacja rozwiązania (kodowanie)
Każde potencjalne rozwiązanie musi być zakodowane jako chromosom — struktura danych, którą algorytm może manipulować. Najpopularniejsze kodowania:
Kodowanie binarne — rozwiązanie jako ciąg bitów (0 i 1). Przykład: optymalizacja 3 parametrów, każdy kodowany 8 bitami → chromosom ma 24 bity. Proste, uniwersalne, ale nie zawsze naturalne dla problemu.
Kodowanie rzeczywiste — rozwiązanie jako wektor liczb zmiennoprzecinkowych. Naturalniejsze dla problemów ciągłych (np. optymalizacja wag sieci neuronowej). Przykład: [0.42, -1.7, 3.14, 0.89].
Kodowanie permutacyjne — rozwiązanie jako permutacja elementów. Idealne dla problemu komiwojażera (TSP): [3, 1, 4, 2, 5] oznacza trasę: miasto 3 → 1 → 4 → 2 → 5.
Kodowanie drzewiaste — rozwiązanie jako drzewo wyrażeń. Używane w programowaniu genetycznym do ewolucji programów komputerowych i wyrażeń matematycznych.
Krok 2: Inicjalizacja populacji
Algorytm zaczyna od losowej populacji N rozwiązań. Rozmiar populacji to hiperparametr — typowo od 50 do 500 osobników. Zbyt mała populacja → ryzyko przedwczesnej zbieżności do lokalnego optimum. Zbyt duża → wolniejsze obliczenia bez proporcjonalnej poprawy.
Inicjalizacja jest zwykle losowa, ale może uwzględniać heurystyki dziedzinowe — np. w TSP można zacząć od kilku rozwiązań wygenerowanych algorytmem zachłannym.
Krok 3: Ocena przystosowania (fitness evaluation)
Każde rozwiązanie w populacji jest oceniane przez funkcję przystosowania (fitness function), która mierzy jakość rozwiązania. To jedyny element algorytmu specyficzny dla danego problemu — reszta jest uniwersalna.
Przykłady funkcji przystosowania:
- Optymalizacja trasy — odwrotność całkowitej długości trasy (krótsza = lepszy fitness)
- Projektowanie anteny — jakość sygnału mierzona eksperymentalnie
- Harmonogramowanie — minimalizacja konfliktów i opóźnień
- Optymalizacja portfela — stosunek zysku do ryzyka (Sharpe ratio)
Krok 4: Selekcja (selection)
Wybór osobników, które staną się „rodzicami" następnego pokolenia. Lepiej przystosowane osobniki mają większe szanse na reprodukcję, ale selekcja nie jest deterministyczna — słabsze osobniki też mogą się rozmnożyć (zachowanie różnorodności).
Selekcja turniejowa (tournament selection) — losowo wybieramy k osobników, najlepszy wygrywa. Prosta, efektywna, łatwa w implementacji. Parametr k kontroluje presję selekcyjną.
Selekcja ruletkowa (roulette wheel selection) — prawdopodobieństwo wyboru proporcjonalne do przystosowania. Osobnik o dwukrotnie wyższym fitness ma dwukrotnie większą szansę.
Selekcja rankingowa (rank selection) — prawdopodobieństwo oparte na pozycji w rankingu, nie na bezwzględnej wartości fitness. Zapobiega dominacji jednego super-osobnika.
Elityzm — bezpośrednie przeniesienie N najlepszych osobników do następnego pokolenia (bez zmian). Gwarantuje, że najlepsze znalezione rozwiązanie nigdy nie zostanie utracone.
Krok 5: Krzyżowanie (crossover / recombination)
Krzyżowanie łączy materiał genetyczny dwóch rodziców, tworząc potomstwo. To kluczowy operator eksploatacji — łączy dobre cechy z różnych rozwiązań.
Krzyżowanie jednopunktowe — losowy punkt podziału. Potomek 1 = lewa część rodzica A + prawa część rodzica B. Potomek 2 = odwrotnie. Przykład (binarne): Rodzic A: 11001|010, Rodzic B: 00110|101 → Potomek: 11001|101
Krzyżowanie dwupunktowe — dwa punkty podziału. Środkowy segment wymieniany między rodzicami.
Krzyżowanie równomierne (uniform crossover) — każdy gen losowo od jednego z rodziców (50/50).
Krzyżowanie PMX (Partially Mapped Crossover) — specjalne krzyżowanie dla permutacji. Zachowuje poprawność permutacji (każdy element dokładnie raz).
Prawdopodobieństwo krzyżowania (crossover rate) — typowo 0.6–0.9. Nie każda para rodziców jest krzyżowana — niektóre są kopiowane bez zmian.
Krok 6: Mutacja (mutation)
Mutacja wprowadza losowe zmiany w chromosomie. To operator eksploracji — pozwala algorytmowi odkrywać nowe regiony przestrzeni rozwiązań, zapobiegając zbieżności do lokalnego optimum.
Mutacja bitowa (bit flip) — losowa zamiana 0 na 1 lub odwrotnie. Dla kodowania binarnego.
Mutacja gaussowska — dodanie losowej wartości z rozkładu normalnego. Dla kodowania rzeczywistego. Przykład: gen 3.14 → 3.14 + N(0, σ) = 3.27.
Mutacja zamiany (swap mutation) — zamiana dwóch losowych genów miejscami. Dla permutacji.
Mutacja inwersji — odwrócenie kolejności segmentu chromosomu. Dla permutacji.
Prawdopodobieństwo mutacji (mutation rate) — typowo 0.001–0.05. Mutacja jest rzadka — zbyt częsta destabilizuje ewolucję, zamieniając ją w losowe przeszukiwanie.
Krok 7: Tworzenie nowego pokolenia
Potomstwo (po krzyżowaniu i mutacji) zastępuje starą populację. Strategie zastępowania:
- Generacyjne — cała populacja wymieniana na nową
- Stałe (steady-state) — wymieniane są tylko najgorsze osobniki
- Elitarne — najlepsze N osobników przeżywa, reszta wymieniana
Krok 8: Warunek zakończenia
Algorytm powtarza kroki 3–7, aż spełniony zostanie warunek zakończenia:
- Osiągnięcie maksymalnej liczby pokoleń
- Znalezienie rozwiązania o zadowalającym fitness
- Brak poprawy przez N kolejnych pokoleń (stagnacja)
- Wyczerpanie limitu czasu
Kluczowe hiperparametry
| Parametr | Typowy zakres | Wpływ |
|---|---|---|
| Rozmiar populacji | 50–500 | Większa → lepsza eksploracja, wolniejsza |
| P(krzyżowanie) | 0.6–0.9 | Wyższa → więcej eksploatacji |
| P(mutacja) | 0.001–0.05 | Wyższa → więcej eksploracji |
| Rozmiar turnieju | 2–7 | Większy → silniejsza presja selekcyjna |
| Elityzm | 1–5 osobników | Zapobiega utracie najlepszego rozwiązania |
Równowaga eksploracja vs eksploatacja to fundamentalny kompromis. Zbyt dużo eksploracji (wysoka mutacja) → algorytm błądzi losowo. Zbyt dużo eksploatacji (silna selekcja, niski P mutacji) → przedwczesna zbieżność do lokalnego optimum.
Zastosowania algorytmów genetycznych
Inżynieria i projektowanie
Optymalizacja kształtu — NASA użyła algorytmów genetycznych do zaprojektowania anteny satelitarnej ST5 (2006). Wyewoluowana antena miała nieregularny, „organiczny" kształt, jakiego żaden inżynier by nie zaproponował, ale osiągała lepsze parametry niż projekty ręczne.
Projektowanie obwodów — ewolucja topologii obwodów elektronicznych. Adrian Thompson wyewoluował obwód FPGA rozróżniający dwa tony — obwód wykorzystywał fizyczne właściwości chipów w sposób nieprzewidziany przez projektantów.
Optymalizacja konstrukcji — minimalizacja wagi przy zachowaniu wytrzymałości (topologia, materiały, grubości).
Logistyka i harmonogramowanie
Problem komiwojażera (TSP) — znalezienie najkrótszej trasy odwiedzającej N miast. Algorytmy genetyczne znajdują rozwiązania bliskie optymalnemu dla tysięcy miast.
Harmonogramowanie produkcji — optymalizacja kolejności zadań na maszynach (job-shop scheduling) minimalizująca czas realizacji.
Planowanie tras — optymalizacja tras floty pojazdów dostawczych (Vehicle Routing Problem).
Uczenie maszynowe
Optymalizacja hiperparametrów — dobór parametrów modeli uczenia maszynowego (np. liczba warstw, tempo uczenia, rozmiar batch).
Neuroewolucja — ewolucja architektury i/lub wag sieci neuronowych. NEAT (NeuroEvolution of Augmenting Topologies) ewoluuje zarówno strukturę, jak i wagi sieci.
Selekcja cech — wybór optymalnego podzbioru cech do modelu ML. Chromosom: wektor binarny (1 = cecha wybrana, 0 = pominięta).
Finanse
Optymalizacja portfela — dobór proporcji aktywów maksymalizujących zysk przy ograniczonym ryzyku.
Strategie tradingowe — ewolucja reguł handlowych na rynkach finansowych.
Bioinformatyka
Wyrównanie sekwencji — porównywanie sekwencji DNA lub białek.
Dokowanie molekularne — znajdowanie optymalnej orientacji leku względem białka docelowego.
Sztuka i kreatywność
Ewolucyjna sztuka — generowanie obrazów, muzyki i form 3D metodami ewolucyjnymi. Karl Sims w latach 90. ewoluował wirtualne stworzenia zdolne do chodzenia i pływania — ich „morfologia" i „mózg" powstawały wyłącznie w drodze sztucznej ewolucji.
Warianty i rozszerzenia
Programowanie genetyczne (GP) — ewolucja programów komputerowych (drzew wyrażeń). Zamiast optymalizować parametry, GP odkrywa strukturę rozwiązania.
Ewolucja różnicowa (Differential Evolution) — wariant dla problemów ciągłych. Zamiast klasycznego krzyżowania, używa różnic między losowymi osobnikami do generowania nowych kandydatów.
NSGA-II — algorytm genetyczny do optymalizacji wielokryterialnej. Szuka frontu Pareto — zbioru rozwiązań, z których żadne nie jest gorsze od innego we wszystkich kryteriach jednocześnie.
Algorytmy memetyczne — hybrydowe podejście łączące GA z lokalnym przeszukiwaniem. Każdy osobnik jest dodatkowo optymalizowany metodą lokalną (np. hill climbing) po krzyżowaniu i mutacji. Analogia: ewolucja (GA) + uczenie w ciągu życia (lokalne przeszukiwanie).
Algorytmy koewolucyjne — kilka populacji ewoluuje jednocześnie, wpływając na siebie nawzajem (jak drapieżniki i ofiary w naturze).
Algorytmy genetyczne a inne metody optymalizacji
| Metoda | Zalety | Wady |
|---|---|---|
| Gradient descent | Szybki, precyzyjny | Wymaga pochodnych, wpada w lokalne minima |
| Algorytmy genetyczne | Bez pochodnych, globalne przeszukiwanie | Wolne, wiele ewaluacji |
| Symulowane wyżarzanie | Proste, jeden osobnik | Mniej eksploracji niż GA |
| Optymalizacja bayesowska | Efektywna przy kosztownych ewaluacjach | Skaluje się słabo do wielu wymiarów |
GA są szczególnie wartościowe, gdy funkcja celu jest czarną skrzynką (brak pochodnych), ma wiele lokalnych optimów lub przestrzeń rozwiązań jest dyskretna/kombinatoryczna.
Najczęściej zadawane pytania (FAQ)
Czy algorytmy genetyczne zawsze znajdują optymalne rozwiązanie?
Nie. Algorytmy genetyczne to metaheurystyki — nie gwarantują znalezienia globalnego optimum. Znajdują rozwiązania bliskie optymalnemu w rozsądnym czasie. Dla problemów NP-trudnych (jak TSP) znalezienie gwarancji optymalności wymagałoby wykładniczego czasu. GA oferują dobry kompromis między jakością rozwiązania a czasem obliczeń.
Kiedy algorytm genetyczny jest lepszym wyborem niż gradient descent?
GA sprawdzają się, gdy: (1) funkcja celu nie jest różniczkowalna, (2) przestrzeń rozwiązań jest dyskretna lub kombinatoryczna, (3) istnieje wiele lokalnych optimów, (4) funkcja celu jest „szumna" lub kosztowna w obliczeniu. Gradient descent jest szybszy i precyzyjniejszy, gdy pochodne są dostępne i funkcja jest wypukła lub umiarkowanie złożona — dlatego dominuje w treningu sieci neuronowych.
Ile czasu zajmuje działanie algorytmu genetycznego?
Zależy od problemu i kosztu ewaluacji fitness. Proste problemy z szybką funkcją celu — sekundy do minut. Symulacje inżynierskie, gdzie jedna ewaluacja trwa minuty — godziny do dni. Kluczowe parametry wpływające na czas: rozmiar populacji × liczba pokoleń × koszt ewaluacji jednego osobnika.
Czy algorytmy genetyczne są nadal używane w erze deep learning?
Tak. GA znajdują zastosowanie w: (1) neuroewolucji — ewolucja architektur sieci neuronowych, (2) optymalizacji hiperparametrów uczenia maszynowego, (3) problemach kombinatorycznych, gdzie deep learning nie jest naturalnym podejściem, (4) optymalizacji wielokryterialnej. GA i deep learning są komplementarne, nie konkurencyjne.