Podręcznik

Mutacja to podstawowy operator różnicowania genetycznego w algorytmach ewolucyjnych. Jej głównym zadaniem jest wprowadzanie losowych zmian w strukturze genotypu, co pozwala na eksplorację nowych rejonów przestrzeni rozwiązań. Mutacja uzupełnia działanie operatora krzyżowania – podczas gdy krzyżowanie miesza informacje już istniejące w populacji, mutacja wprowadza nowy materiał genetyczny.

Dobór odpowiedniej techniki mutacji zależy od typu kodowania rozwiązania – inne metody stosuje się dla chromosomów binarnych, inne dla rzeczywistych, permutacyjnych czy drzewiastych.

Mutacja w kodowaniu binarnym

Najprostszą i najczęściej stosowaną metodą jest tzw. mutacja bitowa (bit flip mutation). Polega na odwróceniu wartości bitu z 0 na 1 lub odwrotnie z pewnym prawdopodobieństwem $p_m$. Dla każdego bitu w chromosomie generowany jest losowy wynik, który decyduje o tym, czy dany bit zostanie odwrócony.

Z matematycznego punktu widzenia, dla chromosomu $g = (g_1, g_2, ..., g_n)$, po mutacji:

$g_i' = \begin{cases} 1 - g_i & \text{z prawdopodobieństwem } p_m \\ g_i & \text{w przeciwnym razie} \end{cases}$

Parametr $p_m$ (np. 0.01 lub 1/n) określa siłę mutacji. Zbyt wysoka wartość może prowadzić do losowej eksploracji (efekt "szumu"), zbyt niska – do stagnacji populacji.

Mutacja w kodowaniu rzeczywistoliczbowym

W tej klasie problemów mutacja polega na dodaniu niewielkiego zaburzenia do wartości genu. Najczęściej stosuje się mutację gaussowską (normalną), gdzie do każdego genu dodawana jest wartość losowa z rozkładu normalnego:

$g_i' = g_i + N(0, \sigma^2)$

gdzie $\sigma$ to parametr określający intensywność mutacji.

Wadą mutacji gaussowskiej może być ryzyko wyjścia poza dopuszczalny przedział. Aby tego uniknąć, wartości są zwykle przycinane lub odbijane od granic. Alternatywnie można stosować mutację Cauchy'ego (o grubych ogonach), która częściej generuje większe zmiany – sprzyja eksploracji globalnej.

Inną metodą jest tzw. unbounded mutation, gdzie nowe wartości są losowane z całego przedziału zmienności, np.:

$g_i' = U(a_i, b_i)$

Mutacja permutacyjna

W problemach, gdzie rozwiązania są reprezentowane jako permutacje (np. TSP), standardowe metody mutacji nie mają zastosowania. Zamiast tego stosuje się modyfikacje struktur permutacyjnych:

• Swap mutation – losowo wybierane są dwa indeksy i ich wartości są zamieniane: $g = (..., g_i, ..., g_j, ...) \Rightarrow (..., g_j, ..., g_i, ...)$
• Insertion mutation – jeden element jest usuwany i wstawiany w innym miejscu w permutacji.
• Inversion mutation – losowy fragment permutacji jest odwracany.

Mutacja w strukturach drzewiastych

W programowaniu genetycznym mutacja najczęściej dotyczy struktury drzewa – np. podmiany pojedynczego węzła, zastąpienia poddrzewa nowym lub modyfikacji terminali.

• Subtree mutation – losowy węzeł drzewa zostaje zastąpiony losowo wygenerowanym poddrzewem.
• Point mutation – zmiana wartości operatora lub terminala w wybranym węźle.

Inne techniki mutacji

• Mutacja ograniczona (boundary mutation) – gen może przyjąć wartość jednego z krańców dopuszczalnego zakresu.
• Non-uniform mutation – siła mutacji zmniejsza się w miarę upływu czasu, np.:$g_i' = g_i + \Delta(t, b_i - g_i)$
  gdzie 
  • $\Delta(t, d)$ to funkcja malejąca wraz z czasem (np. logarytmiczna),
  • $t$ – numer pokolenia.
• Adaptive mutation – parametr mutacji (np. $\sigma$) zmienia się w trakcie działania algorytmu w odpowiedzi na tempo poprawy rozwiązania.

Podsumowanie

Mutacja pełni niezwykle ważną rolę w utrzymywaniu różnorodności populacji. W zależności od typu kodowania, należy dobierać odpowiednie operatory:

• binarne – odwracanie bitów,
• rzeczywiste – zakłócenia losowe (np. gaussowskie),
• permutacyjne – przekształcenia pozycji,
• drzewiaste – manipulacje strukturą drzewa.

Dobór intensywności mutacji i jej rodzaju wpływa na zdolność algorytmu do eksploracji i unikania zbieżności do lokalnych minimów. W praktyce często stosuje się również mechanizmy adaptacyjne, które dynamicznie dostosowują siłę mutacji w trakcie działania algorytmu.