Podręcznik

Kodowanie genomu w algorytmach genetycznych

Kodowanie genomu to sposób reprezentacji potencjalnych rozwiązań problemu optymalizacyjnego w postaci chromosomów – czyli łańcuchów danych, na których operują algorytmy genetyczne. Wybór odpowiedniego rodzaju kodowania ma kluczowe znaczenie dla efektywności działania algorytmu, ponieważ wpływa na to, jak łatwo można zastosować operatory genetyczne (krzyżowanie, mutację) oraz jak dobrze przestrzeń poszukiwań jest odwzorowywana.

Klasyfikacja metod kodowania

Najczęściej stosowane techniki kodowania genotypu dzielą się na:

Kodowanie klasyczne (wektorowe)

W tym podejściu genotyp reprezentowany jest jako wektor wartości – może być to wektor binarny, liczbowy, całkowity itp. Każdy gen odpowiada za jedną cechę rozwiązania. To najczęściej stosowane podejście, zwłaszcza w problemach optymalizacji ciągłej lub dyskretnej.

Kodowanie permutacyjne

Tutaj chromosom zawiera permutację elementów – typowe zastosowanie to problemy kombinatoryczne, takie jak problem komiwojażera (TSP), harmonogramowanie zadań, kolejki produkcyjne itp. Operatory krzyżowania muszą być specjalnie przystosowane, by nie generowały nieprawidłowych permutacji.

Kodowanie drzewiaste

Stosowane głównie w programowaniu genetycznym. Genotyp ma strukturę drzewa – węzły to funkcje lub operatory, a liście to argumenty lub dane wejściowe. Struktura ta umożliwia reprezentację złożonych wyrażeń matematycznych, reguł lub algorytmów. Przykład: $(x + y) * z$.

Kodowanie grafowe

Zamiast drzew czy wektorów, genotypem może być graf – używane np. w ewolucyjnej optymalizacji sieci (np. topologie połączeń neuronów w neuroewolucji). Pozwala to na reprezentowanie bardziej ogólnych struktur i zależności.

Kodowanie listy instrukcji (linearne kodowanie genów)

Popularne w ewolucyjnych algorytmach programujących. Genotyp zawiera liniową sekwencję poleceń lub instrukcji, podobnych do kodu asemblera. Taka reprezentacja ułatwia mutacje i krzyżowanie na poziomie składni.

Kodowanie symboliczne

Używane w problemach, gdzie rozwiązania mają strukturę symboliczną – np. ewolucja formuł logicznych, automaty, reguły IF-THEN. Genotyp zawiera symbole ze skończonego alfabetu, np. {A, B, C, ¬, ∧, ∨}.

Reprezentacja pojedynczych genów

Poza strukturą całego genotypu, istotne jest to, w jaki sposób kodowane są pojedyncze geny. Najczęściej stosuje się dwa podejścia: reprezentację binarną (w tym kod Graya) oraz reprezentację rzeczywistoliczbową.

Kodowanie binarne

W tym przypadku każda zmienna kodowana jest jako ciąg bitów. Długość ciągu określa precyzję odwzorowania. Na przykład, wartość z przedziału $[a, b]$$ reprezentujemy za pomocą $n$ bitów, co pozwala wyróżnić $2^n$ wartości dyskretnych. Zamiana bitów na wartość rzeczywistą wymaga przeskalowania:

$x = a + \frac{b - a}{2^n - 1} \cdot \text{wartość binarna}$

Zaletą tego podejścia jest prostota operacji krzyżowania i mutacji. Wadą – ograniczona rozdzielczość i nieliniowość odwzorowania, szczególnie w problemach ciągłych.

Kodowanie Graya

Kod Graya to wariant kodowania binarnego, w którym dwie kolejne wartości różnią się tylko jednym bitem. Redukuje to problem „skokowych” zmian wartości przy małych mutacjach. Przydatny zwłaszcza tam, gdzie zmiana jednego bitu nie powinna prowadzić do dużej zmiany w wartości odwzorowanej.

Kodowanie rzeczywistoliczbowe

Zamiast bitów, gen przyjmuje bezpośrednio wartość rzeczywistą z określonego przedziału. Przykład: gen $x_i \in [0, 10]$ może mieć wartość 7.35. Operatory genetyczne muszą być dostosowane do przestrzeni ciągłej – mutacja może np. polegać na dodaniu losowego zakłócenia $\sim N(0, \sigma)$, a krzyżowanie – na liniowej kombinacji rodziców.

Zaletą tego podejścia jest jego naturalność i brak potrzeby dekodowania. Dobrze sprawdza się w optymalizacji ciągłej. Wadą jest większe ryzyko wyjścia poza dopuszczalne zakresy oraz konieczność dostosowania operatorów.

Podsumowanie

Dobór odpowiedniego kodowania zależy od rodzaju rozważanego problemu:

• dla problemów ciągłych preferowane jest kodowanie rzeczywiste,
• dla problemów kombinatorycznych – kodowanie permutacyjne,
• dla problemów strukturalnych – kodowanie drzewiaste, grafowe lub instrukcyjne.

Dodatkowo należy pamiętać, że rodzaj kodowania wpływa na konstrukcję operatorów genetycznych oraz na efektywność przeszukiwania przestrzeni rozwiązań. W praktyce często konieczne jest eksperymentalne dobranie najbardziej efektywnej reprezentacji.