Algorytmy ewolucyjne — strategie, programowanie, rojowe

Algorytmy genetyczne to najsłynniejszy, ale nie jedyny rodzaj algorytmów inspirowanych ewolucją biologiczną. Szersza rodzina — algorytmy ewolucyjne (Evolutionary Algorithms, EA) — obejmuje różne podejścia do optymalizacji opartej na populacji, selekcji, krzyżowaniu i mutacji. Do tej rodziny dołączają algorytmy inteligencji rojowej (Swarm Intelligence), inspirowane kolektywnymi zachowaniami zwierząt — mrówek, pszczół, ptaków, ryb.

Rodzina algorytmów ewolucyjnych

1. Algorytmy genetyczne (GA)

Omówione szczegółowo w osobnym artykule. Kluczowe cechy:

• Reprezentacja: ciągi binarne lub permutacje
• Nacisk na krzyżowanie jako główny operator
• Selekcja: ruletkowa, turniejowa, rankingowa
• Klasyczne podejście Hollanda (1975)

2. Strategie ewolucyjne (ES)

Strategie ewolucyjne (Evolution Strategies), opracowane w Niemczech w latach 60. przez Rechenberga i Schwefela, różnią się od GA w kilku kluczowych aspektach:

Reprezentacja: wektory rzeczywistoliczbowe (nie binarne). Naturalne dla optymalizacji ciągłej.

Nacisk na mutację: w ES mutacja jest głównym operatorem (w GA — krzyżowanie). Mutacja to dodanie szumu gaussowskiego do parametrów:

x' = x + σ · N(0, I)

Samoadaptacja: kluczowa innowacja — ES ewoluuje nie tylko rozwiązanie, ale też parametry mutacji (σ). Osobnik = (x, σ). Mutacja adaptuje się do krajobrazu fitness — w gładkich regionach σ rośnie (duże kroki), w trudnych maleje (małe kroki).

Notacja:

• (1+1)-ES: jeden rodzic, jedno potomstwo, lepszy przeżywa
• (μ+λ)-ES: μ rodziców, λ potomków, najlepszych μ z μ+λ przeżywa
• (μ,λ)-ES: μ rodziców, λ potomków (λ > μ), najlepszych μ z λ przeżywa (rodzice giną!)

CMA-ES (Covariance Matrix Adaptation)

CMA-ES (Hansen, 2001) to stan sztuki w optymalizacji ewolucyjnej ciągłej. Adaptuje nie tylko σ, ale pełną macierz kowariancji rozkładu mutacji — kierunki i korelacje między wymiarami.

Intuicja: zamiast symetrycznej kuli gaussowskiej, CMA-ES kształtuje elipsoidę dopasowaną do krajobrazu fitness — wydłużoną w kierunkach, gdzie fitness zmienia się wolno.

CMA-ES jest benchmarkowym algorytmem optymalizacji czarnoskrzynkowej (black-box optimization) — nie wymaga gradientu, działa na dowolnej funkcji.

OpenAI ES (2017)

OpenAI pokazał, że proste strategie ewolucyjne mogą trenować polityki uczenia ze wzmocnieniem — konkurencyjnie z PPO i DQN na Atari i MuJoCo. Zaletą: łatwa paralelizacja (tysiące workerów) i brak potrzeby propagacji gradientów.

3. Programowanie ewolucyjne (EP)

Programowanie ewolucyjne (Evolutionary Programming, Fogel, 1966) — pierwotnie ewoluowało automaty skończone (finite state machines) do przewidywania sekwencji symboli.

Kluczowe różnice od GA:

• Brak krzyżowania — tylko mutacja. Uzasadnienie: krzyżowanie dwóch dobrych rodziców niekoniecznie da dobrego potomka w złożonych przestrzeniach
• Selekcja turniejowa stochastyczna — każdy osobnik rywalizuje z q losowymi przeciwnikami
• Fenotypowa (behawioralna) ewolucja zamiast genotypowej

Współczesne EP zbliżyło się do ES — oba operują na wektorach ciągłych z mutacją gaussowską.

4. Programowanie genetyczne (GP)

Programowanie genetyczne (Genetic Programming, Koza, 1992) ewoluuje programy komputerowe — reprezentowane jako drzewa składniowe.

Przykład: ewolucja formuły matematycznej:

      +
     / 
    *   sin
   /     
  x   3    y

Reprezentuje: (x * 3) + sin(y)

Operatory:

• Krzyżowanie: zamiana poddrzew między dwoma programami
• Mutacja: losowa zmiana węzła (operator, terminal) lub poddrzewa
• Selekcja: turniejowa na fitness (np. MSE na zbiorze treningowych danych)

Zastosowania GP:

• Symbolic regression — odkrywanie formuł matematycznych z danych
• Automatyczne projektowanie obwodów
• Odkrywanie reguł (rule mining)
• Handel algorytmiczny — ewolucja strategii tradingowych

Algorytmy inteligencji rojowej

Inspirowane kolektywnymi zachowaniami zwierząt — proste jednostki (agenty) bez centralnego sterowania tworzą złożone, adaptacyjne zachowanie grupowe.

PSO — Particle Swarm Optimization

Optymalizacja rojem cząstek (Kennedy & Eberhart, 1995) — inspirowana zachowaniem stad ptaków i ławic ryb.

Idea: Populacja „cząstek" porusza się po przestrzeni rozwiązań. Każda cząstka:

• Pamięta swoją najlepszą dotychczasową pozycję (pBest)
• Zna najlepszą pozycję w populacji (gBest)
• Aktualizuje prędkość na podstawie obu

Aktualizacja prędkości: vᵢ(t+1) = w·vᵢ(t) + c₁·r₁·(pBestᵢ - xᵢ) + c₂·r₂·(gBest - xᵢ)

Aktualizacja pozycji: xᵢ(t+1) = xᵢ(t) + vᵢ(t+1)

Gdzie:

• w — inercja (momentum)
• c₁ — składowa kognitywna (atrakcja do własnego najlepszego)
• c₂ — składowa społeczna (atrakcja do globalnego najlepszego)
• r₁, r₂ — losowe z [0,1]

Zalety PSO: prosty, szybki, mało hiperparametrów, dobry dla optymalizacji ciągłej. Wady: może utknąć w optimach lokalnych, brak gwarancji zbieżności.

ACO — Ant Colony Optimization

Optymalizacja kolonii mrówek (Dorigo, 1992) — inspirowana zachowaniem mrówek szukających pożywienia.

Idea: Mrówki komunikują się pośrednio przez feromony — substancje chemiczne zostawiane na ścieżkach. Ścieżki z większą ilością feromonów przyciągają więcej mrówek — powstaje pozytywne sprzężenie zwrotne. Dobre ścieżki wzmacniają się, złe zanikają (parowanie feromonów).

Algorytm (dla problemu komiwojażera TSP):

1. Każda mrówka buduje trasę, wybierając następne miasto z prawdopodobieństwem proporcjonalnym do feromonów i odwrotności odległości
2. Po zbudowaniu wszystkich tras → aktualizacja feromonów:

• Ścieżki w lepszych trasach dostają więcej feromonów
• Wszystkie feromony parują (evaporation) — zapobiega zbieżności do jednego rozwiązania

1. Powtarzaj

Zastosowania ACO:

• Routing (TSP, vehicle routing) — naturalne mapowanie na problem
• Scheduling — harmonogramowanie zadań
• Sieci komputerowe — routing pakietów
• Bioinformatyka — fałdowanie białek

ABC — Artificial Bee Colony

Sztuczna kolonia pszczół (Karaboga, 2005) — inspirowana zachowaniem pszczół szukających nektaru.

Trzy typy pszczół:

• Employed bees — eksploatują znane źródła nektaru
• Onlooker bees — wybierają źródła proporcjonalnie do jakości (fitness)
• Scout bees — losowo eksplorują nowe źródła

FA — Firefly Algorithm

Algorytm świetlików (Yang, 2008) — atrakcja między świetlikami zależy od jasności (fitness) i odległości.

Porównanie algorytmów ewolucyjnych

Kiedy stosować algorytmy ewolucyjne?

Idealne warunki

• Brak gradientu — funkcja celu nie jest różniczkowalna
• Czarnoskrzynkowa optymalizacja — nie znamy struktury problemu
• Przestrzeń wielomodalna — wiele optimów lokalnych
• Problemy kombinatoryczne — TSP, scheduling, knapsack
• Brak analitycznego rozwiązania — heurystyka jest jedyną opcją

Kiedy nie stosować

• Gradient dostępny — gradient descent jest szybszy i dokładniejszy
• Prosta struktura — metody analityczne są lepsze
• Bardzo dużo zmiennych (>1000) — EA skaluje się słabo (CMA-ES: ~100 zmiennych)
• Ograniczony budżet ewaluacji — EA wymaga tysięcy ewaluacji fitness

Zastosowania w praktyce

• Inżynieria — optymalizacja kształtu (samoloty, samochody, budynki), dobór materiałów
• Logistyka — planowanie tras, harmonogramowanie, rozmieszczenie magazynów
• Finanse — optymalizacja portfela, ewolucja strategii tradingowych
• Robotyka — ewolucja kontrolerów, projektowanie morfologii robotów
• Neural Architecture Search — ewolucja architektur sieci neuronowych
• Sztuka i muzyka — ewolucyjna sztuka generatywna, kompozycja algorytmiczna

Podsumowanie

Algorytmy ewolucyjne i rojowe to bogata rodzina metaheurystyk inspirowanych naturą. Od algorytmów genetycznych przez strategie ewolucyjne (CMA-ES) po inteligencję rojową (PSO, ACO) — każdy wariant ma swoje mocne strony i optymalne zastosowania. CMA-ES dominuje w optymalizacji ciągłej, ACO w routingu, GA w problemach kombinatorycznych. Łączy je wspólna idea: populacja rozwiązań ewoluująca przez selekcję, wariację i adaptację — paralelizm z ewolucją biologiczną, który okazuje się zaskakująco skuteczny w rozwiązywaniu problemów, do których nie istnieją algorytmy dokładne.