Algorytmy Genetyczne
Wnioskowanie_Statystyczne_-_wykład
Algorytmy Genetyczne
Algorytmy genetyczne (Genetic Algorithms, GA ) lub populacyjne to stochastyczna metoda przeglądu przestrzeni rozwiązań, oparta na mechanizmach rządzących ewolucją organizmów żywych. Praktyczne zastosowanie w analizie sygnałów jest na razie dość ograniczone ze względu na wysoki koszt obliczeniowy. Pomimo tego, ze względu na potencjalnie ogromne możliwości metody i szereg spektakularnych zastosowań w dziedzinach pokrewnych, omówimy poniżej w skrócie klasyczny AG.
Za początek badań w tej dziedzinie można uznać klasyczną monografię Hollanda 'Adaptation in Natural and Artificial Systems'. Więcej informacji o teorii i zastosowaniach można znaleźć np. w książce Goldberga 'Algorytmy genetyczne i ich zastosowania'.
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ągów. 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
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[1] algorytmu MP, rozdział o Matching Pursuit). 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 [math]M[/math] 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ą[2], to rozwiązanie najprościej zakodować jako [math]4*2*8=64[/math]-bitowy ciąg. Pierwszych 16 bitów możemy interpretować jako zapis pozycji, kolejne 32 — częstości itd.[3] 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.
- ↑ Znacznie ciekawsze jest wykorzystanie GA do znajdowania zestawów [math]M[/math] funkcji wyjaśniających największy procent energii sygnału. Tu ograniczymy się do przypadku łatwiejszego w opisie.
- ↑ W praktyce stosujemy liczby zmiennoprzecinkowe.
- ↑ Jeśli na 16 bitach zapiszemy liczę z przedziału [math](0, MAXINT )[/math], gdzie [math]MAXINT =2^{16}-1=65535[/math], to dla sygnału długości [math]N[/math] punktów i wylosowanej czwórki liczb [math](u, \omega, s, \phi)[/math] można rozpatrywać funkcje Gabora postaci [math] g_{(u, \omega, s, \phi)}(t) = K(u, \omega, s, \phi) e^{-\pi\left( \frac{\frac {t*MAXINT }N-u} s \right)^2} \sin\left( 2 \pi \frac{\omega}{MAXINT } \left(t-\frac{u*N}{MAXINT }\right)+ 2\pi\frac{\phi}{MAXINT } \right) [/math] gdzie [math]K(u, f, \omega, \phi)[/math] — stała normalizująca energię do [math]1[/math](por. wzór na funkcję Gabora).
