Algorytmy Genetyczne: Różnice pomiędzy wersjami
| (Nie pokazano 8 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
| − | + | [[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. | 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 | Pomimo tego, ze względu na potencjalnie ogromne możliwości metody i szereg | ||
| Linia 17: | Linia 19: | ||
Najbardziej charakterystyczną cechą AG jest fakt, że dobór rozwiązań | Najbardziej charakterystyczną cechą AG jest fakt, że dobór rozwiązań | ||
przebiega właściwie bez związku ze znaczeniem kodowanych | 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 | funkcji kosztu w sieciach neuronowych (z przeciwnym znakiem). Dla | ||
działania algorytmu konieczne jest obliczanie "jakości" każdego z | działania algorytmu konieczne jest obliczanie "jakości" każdego z | ||
| Linia 35: | Linia 37: | ||
'''1010011000000111''',<br/> | '''1010011000000111''',<br/> | ||
skrzyżowane poniżej szóstej pozycji, dadzą:<br/> | skrzyżowane poniżej szóstej pozycji, dadzą:<br/> | ||
| − | '''0011011000000111''' | + | '''0011011000000111''' |
| + | <!-- | ||
'''1010010011101011''' | '''1010010011101011''' | ||
| + | --> | ||
'''mutacja''' polega na zamianie bitu na losowo wybranej pozycji ciągu; | '''mutacja''' polega na zamianie bitu na losowo wybranej pozycji ciągu; | ||
| Linia 42: | Linia 46: | ||
przyjąłby postać '''0001010011101011'''. | przyjąłby postać '''0001010011101011'''. | ||
| − | + | ||
| + | Najprostszy przykład — poszukiwanie minumum złożonej, wielowymianrowej funkcji. Jako kodowanie przyjmijmy binarną postać współrzędnych. | ||
| + | |||
| + | Bardziej złożony przykład: poszukujemy parametrów funkcji Gabora, wyjaśniającej największy procent energii danego sygnału (iteracja<ref> | ||
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.</ref> algorytmu MP, rozdział [[Reprezentacje_przybliżone#Przybli.C5.BCenia_adaptacyjne_.28adaptive_approximations.29|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ą<ref> | 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.</ref> algorytmu MP, rozdział [[Reprezentacje_przybliżone#Przybli.C5.BCenia_adaptacyjne_.28adaptive_approximations.29|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ą<ref> | ||
| Linia 62: | Linia 69: | ||
energii tłumaczonej przez opisywaną przez niego funkcję. | energii tłumaczonej przez opisywaną przez niego funkcję. | ||
| − | Tak więc w pierwszym kroku losujemy populację przypadkowych ciągów 128 | + | 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. |
| − | 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. | ||
Aktualna wersja na dzień 16:52, 1 cze 2023
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.
Najprostszy przykład — poszukiwanie minumum złożonej, wielowymianrowej funkcji. Jako kodowanie przyjmijmy binarną postać współrzędnych.
Bardziej złożony przykład: 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).
