Selekcja, krzyżowanie i mutacja — operatory genetyczne

Operatory genetyczne to mechanizmy napędzające ewolucję w algorytmach genetycznych. Trzy fundamentalne operatory — selekcja, krzyżowanie i mutacja — odpowiadają za eksplorację przestrzeni rozwiązań i eksploatację znalezionych dobrych regionów. Ich prawidłowy dobór decyduje o skuteczności algorytmu.

Selekcja — kto przetrwa?

Selekcja to proces wybierania osobników z bieżącej populacji, które staną się rodzicami następnego pokolenia. Kluczowa zasada: osobniki o wyższym fitness mają większą szansę na wybór, ale nie gwarantowaną — element losowości utrzymuje różnorodność genetyczną.

Selekcja ruletkowa (Roulette Wheel Selection)

Każdy osobnik otrzymuje „wycinek" ruletki proporcjonalny do swojego fitness. Im wyższy fitness, tym większy wycinek — i większa szansa na wybór.

Przykład:

Losujemy liczbę z [0, 1). Jeśli 0,35 → osobnik A (zakres 0,00–0,40). Jeśli 0,85 → osobnik C (zakres 0,70–0,90).

Zalety:

• Proporcjonalność — lepsze osobniki mają większą szansę
• Prostota implementacji

Wady:

• Dominacja super-osobnika — jeśli jeden osobnik ma fitness wielokrotnie wyższy niż reszta, dominuje populację, prowadząc do przedwczesnej zbieżności
• Słaba presja selekcyjna — gdy fitness jest zbliżony, selekcja jest prawie losowa
• Nie działa dla ujemnych wartości fitness

Selekcja turniejowa (Tournament Selection)

Losowo wybierz k osobników z populacji (turniejowa grupa). Najlepszy z nich wygrywa i zostaje rodzicem. Powtarzaj dla kolejnych rodziców.

Parametr: rozmiar turnieju k (typowo 2–7).

• k = 2 (turniej binarny) → słaba presja selekcyjna, duża różnorodność
• k = N (cała populacja) → deterministic — zawsze wygrywa najlepszy, minimalna różnorodność

Zalety:

• Łatwa kontrola presji selekcyjnej (przez k)
• Działa niezależnie od skali fitness (nie wymaga normalizacji)
• Równoległa (turnieje niezależne)
• Najczęściej stosowana w praktyce

Wady:

• Wybór k wpływa na zachowanie algorytmu

Selekcja rankingowa (Rank Selection)

Osobniki sortowane są według fitness. Prawdopodobieństwo wyboru zależy od rangi (pozycji w rankingu), nie od wartości fitness.

Zalety:

• Eliminuje problem dominacji super-osobnika
• Stabilna presja selekcyjna niezależna od rozkładu fitness

Wady:

• Wymaga sortowania (O(N log N))
• Ignoruje bezwzględne różnice fitness (osobnik z fitness 1000 i 999 mają bardzo różne rangi, ale niemal identyczny fitness)

Elityzm

Nie jest metodą selekcji per se, lecz strategią: najlepszych e osobników z bieżącej populacji przechodzi bezpośrednio do nowego pokolenia, bez krzyżowania ani mutacji. Chroni najlepsze znalezione dotychczas rozwiązanie.

Typowo e = 1–5. Elityzm jest standardową praktyką — AG bez elityzmu może „stracić" najlepsze rozwiązanie przez pechowe krzyżowanie/mutację.

Krzyżowanie (Crossover) — wymiana genów

Krzyżowanie to proces łączenia materiału genetycznego dwóch rodziców w celu utworzenia potomków. Cel: potomek dziedziczy dobre cechy obu rodziców, potencjalnie tworząc rozwiązanie lepsze od każdego z nich.

Krzyżowanie jednopunktowe (One-point Crossover)

Losowy punkt dzieli chromosom. Potomek 1 = lewa część rodzica 1 + prawa część rodzica 2 (i odwrotnie).

Rodzic 1: 11001|010
Rodzic 2: 00110|101
Potomek 1: 11001|101
Potomek 2: 00110|010

Krzyżowanie dwupunktowe (Two-point Crossover)

Dwa losowe punkty wyznaczają segment do wymiany:

Rodzic 1: 11|001|010
Rodzic 2: 00|110|101
Potomek 1: 11|110|010
Potomek 2: 00|001|101

Krzyżowanie jednorodne (Uniform Crossover)

Każdy gen jest niezależnie losowany od rodzica 1 lub rodzica 2 (z prawdopodobieństwem 0,5):

Maska:    0  1  1  0  1  0  1  0
Rodzic 1: 1  1  0  0  1  0  1  0
Rodzic 2: 0  0  1  1  0  1  0  1
Potomek:  0  1  1  0  0  0  0  0

Krzyżowanie dla permutacji — Order Crossover (OX)

Dla problemów permutacyjnych (np. TSP) zwykłe krzyżowanie tworzy niepoprawne rozwiązania (powtórzone miasta). OX zachowuje fragment permutacji rodzica 1, a pozostałe pozycje wypełnia elementami rodzica 2 w oryginalnej kolejności.

Przykład (TSP z 8 miastami):

Rodzic 1: 1 2 |3 4 5| 6 7 8
Rodzic 2: 3 7  2 8 1  4 6 5
Potomek:  8 1 |3 4 5| 2 6 7

Segment [3 4 5] skopiowany z rodzica 1. Pozostałe: z rodzica 2 w kolejności, pomijając już użyte (3, 4, 5).

Krzyżowanie dla kodowania rzeczywistego

• Blend Crossover (BLX-α): potomek losowany z rozszerzonego zakresu między rodzicami
• Simulated Binary Crossover (SBX): symuluje efekt jednopunktowego krzyżowania binarnego na liczbach rzeczywistych

Prawdopodobieństwo krzyżowania (pₓ)

Nie każda para rodziców jest krzyżowana. Typowo pₓ = 0,7–0,9. Nieskrzyżowani rodzice przechodzą do nowego pokolenia bez zmian.

Mutacja — przypadkowe zmiany

Mutacja wprowadza małe, losowe zmiany w chromosomie. Cel: eksploracja — szukanie nowych regionów przestrzeni rozwiązań, które nie byłyby osiągalne wyłącznie przez krzyżowanie.

Mutacja bitowa (Bit Flip)

Dla chromosomu binarnego: z prawdopodobieństwem pₘ każdy bit jest odwracany (0→1 lub 1→0).

Przed: 1 0 0 1 1 0 1 0
Po:    1 0 1 1 1 0 1 0  (bit 3 zmutowany)

Mutacja dla kodowania rzeczywistego

• Mutacja gaussowska: dodaj losowy szum z rozkładu normalnego N(0, σ)
• Mutacja jednorodna: zastąp gen losową wartością z dozwolonego zakresu

Mutacja dla permutacji

• Swap mutation: zamień dwa losowe elementy miejscami
• Inversion mutation: odwróć kolejność segmentu
• Insertion mutation: przenieś losowy element w nowe miejsce

Prawdopodobieństwo mutacji (pₘ)

Typowo pₘ = 0,001–0,05 (na gen, nie na osobnika). Reguła kciuka: pₘ ≈ 1/L, gdzie L = długość chromosomu (średnio 1 mutacja na chromosom).

Za niskie pₘ: algorytm traci różnorodność, wpada w przedwczesną zbieżność. Za wysokie pₘ: algorytm staje się losowym przeszukiwaniem, nie ewolucją.

Balans eksploracji i eksploatacji

Fundamentalne napięcie w algorytmach genetycznych:

• Eksploatacja — intensywne przeszukiwanie okolic najlepszych znalezionych rozwiązań (silna selekcja, krzyżowanie)
• Eksploracja — szukanie nowych, potencjalnie lepszych regionów (słaba selekcja, mutacja, duża populacja)

Za dużo eksploatacji → przedwczesna zbieżność. Za dużo eksploracji → wolna zbieżność. Dobry AG balansuje oba aspekty.

Rekomendacje praktyczne

1. Selekcja: turniejowa (k=2–3) — najczęstszy i najbezpieczniejszy wybór
2. Krzyżowanie: jednopunktowe lub dwupunktowe (binarne); OX (permutacje); BLX-α (rzeczywiste)
3. Mutacja: bitowa z pₘ ≈ 1/L (binarne); gaussowska (rzeczywiste); swap (permutacje)
4. Elityzm: zawsze — przynajmniej 1 osobnik
5. Rozmiar populacji: 50–200 dla prostych problemów, 200–500 dla złożonych

Operatory genetyczne to silnik ewolucji. Algorytm genetyczny bez dobrze dobranych operatorów to jak samochód bez silnika — ma strukturę, ale nie jedzie.