Elementarny Algorytm Genetyczny

Pierwszym problemem, który musimy rowiązać przed zastosowaniem AG, jest wybór kodowania elementów przestrzeni rozwiązań -- zwykle w postaci ciągu bitów, reprezentujących liczby (lub litery) opisujące dopuszczalne rozwiązanie.

Najbardziej charakterystyczną cechą AG jest fakt, że dobór rozwiązań przebiega właściwie bez związku ze znaczeniem kodowanych ciąógw. Jedynym łączem jest tu funkcja przystosowania, odpowiednik funkcji kosztu w sieciach neuronowych (z przeciwnym znakiem). Dla działania algorytmu konieczne jest obliczanie ,,jakości'' każdego z zaproponowanych rozwiązań.

Po ustaleniu sposobu kodowania i liczenia wartości funkcji przystosowania, optymalizacja polega na powtarzaniu następujących kroków:

• reprodukcja
• krzyżowanie
• mutacja

reprodukcja

w każdej pętli (pokoleniu), ciągi kodowe o wyższych wartościach funkcji przystosowania mają większą szansę na przejście do następnego pokolenia. Można to zrealizować z pomocą losowania ciągów z prawdopodobieństwem proporcjonalnym do względnej wartości funkcji przystosowania. Wylosowane ciągi przechodzą do następnego pokolenia, w którym odpowiednikiem rozmnażania jest krzyżowanie

krzyżowanie

krzyżowane są losowo dobrane pary ciągów kodowych. Krzyżowanie polega na zamianie części ciągów poczynając od losowo wybranego punktu. Np. ciągi
0011010011101011 i
1010011000000111,
skrzyżowane poniżej szóstej pozycji, dadzą:
0011011000000111 i
1010010011101011

mutacja

polega na zamianie bitu na losowo wybranej pozycji ciągu; np. pierwszy ciąg z powyższego przykładu, zmutowany na trzeciej pozycji, przyjąłby postać 0001010011101011.

Dla przykładu przyjmijmy, że poszukujemy parametrów funkcji Gabora, wyjaśniającej największy procent energii danego sygnału (iteracja^5.3 algorytmu MP, rozdział 4.2). Jak w każdym zastosowaniu AG, pierwszym krokiem będzie wybór kodowania w przestrzeni rozwiązań. W tym przypadku przestrzeń rozwiązań to zbiór $M$ czwórek parametrów opisujących znormalizowane funkcje Gabora -- pozycja, częstość, skala i faza. Jeśli każdą z tych liczb zakodujemy jako 2-bajtową liczbę całkowitą^5.4, to rozwiązanie najprościej zakodować jako $4*2*8=64$-bitowy ciąg. Pierwszych 16 bitów możemy interpretować jako zapis pozycji, kolejne 32 -- częstości itd.^5.5

Skoro celem poszukiwania jest wyjaśnienie największej części energii sygnału, to za ,,przystosowanie'' ciągu kodowego przyjmiemy wartość energii tłumaczonej przez opisywaną przez niego funkcję.

Tak więc w pierwszym kroku losujemy populację przypadkowych ciągów 128 bitów, które interpretujemy jak zapis parametrów funkcji Gabora. Dla każdej z tak opisanych funkcji liczymy funkcję przystosowania. Wybieramy z nich najlepsze (np. metodą losowania proporcjonalnego), po czym z uzyskanego w ten sposób następnego pokolenia losowo dobieramy pary do krzyżowania. Następnie (oczywiście również losowo) wybieramy ,,osobniki'' do mutacji. Gdy spełnimy kryteria zatrzymania algorytmu (np. względny brak poprawy w kolejnych pokoleniach), z ostatniego pokolenia wybieramy ciąg o największej wartości funkcji przystosowania.

...