Algorytm z natury genetyczny

Pierwsza fala wpisów w ramach Daj Się Poznać za nami, kurz opadł, czas zabrać się do roboty.

Dziewiczy wpis na blogu, z racji swojej mało technicznej natury, nie znalazł się w szerokiej dystrybucji (dotnetomaniak, feed konkursowy), dlatego zainteresowanych zapraszam tutaj.

BEGIN SPOILER

Wpis będzie teoretyczny i nieco przegadany. Dla wielu ten temat jest kompletną nowością, stąd decyzja o zdefiniowaniu kilku pojęć. Znawców tematu zapraszam do kolejnego wpisu w ramach DSP.

END SPOILER

Algorytmy genetyczne to wciąż pewnego rodzaju egzotyka na polskim rynku algorytmów. Mało kto o nich słyszał, a jeżeli już słyszał, to jakoś niechętnie chce się nimi zajmować. Bo zbyt skomplikowane, za dużo zachodu, „a po co mi to, ja tworzę aplikacje biznesowe w windows forms”.

Tak się składa, że samo zrozumienie zasad działania takiego algorytmu jest bardzo proste. Gorzej z mądrym i efektywnym jego wykorzystaniem, ale o tym później. Na razie skupmy się na podstawowych pojęciach związanych z Klasycznym Algorytmem Genetycznym (w skrócie, trochę ziomalsko, KAG czyt. kæeg).

GEN – pojedynczy element określający cechę lub zmienną odnoszącą się do rozwiązywanego problemu. Przyjęło się, że w KAG gen ma wartość 0 lub 1, jednak nic nie stoi na przeszkodzie, żeby była to na przykład liczba z przedziału <0,1>

CHROMOSOM – zbiór genów – kandydat do bycia najlepszym rozwiązaniem. Długość chromosomu nie jest ustalona i różni się w zależności od problemu i sposobu implementacji algorytmu.

FENOTYP – w biologii określany jako przystosowanie organizmu do środowiska, w którym się znajduje. W algorytmie genetycznym fenotyp realizuje funkcja przystosowania definiowana na etapie projektowania algorytmu.

POPULACJA – zbiór chromosomów o równej liczbie genów. Liczność zbioru określona jest na początku projektowania algorytmu i pozostaje niezmienna w czasie jego działania. Przyjęło się, że populację początkową generujemy w sposób losowy.

Definicje definicjami, ale z czym to się je? Posłużmy się rekwizytem.., eee przykładem:

Problem do rozwiązania: maksymalizacja sumy dziesięciu liczb. Żeby było prościej, każda z tych liczb może być zerem lub jedynką. „Do tego nie trzeba żadnych algorytmów, panie; średnio rozgarnięty uczeń podstawówki jest w stanie rozwiązać ten >problem<„. Prawda. Ale przykład ma być prosty i zrozumiały. Więc cicho tam 😀

Spróbujmy określić czym jest w tym przypadku nasz gen? Pojedynczą liczbą z przedziału <0,1>. Chromosom? Zbiorem 10 takich liczb. Populacja to zbiór takich dziesiątek. A fenotyp?

Fenotyp jest funkcją, która odpowie nam na pytanie: czy aktualnie przetwarzany chromosom jest lepszy czy gorszy od dowolnego innego chromosomu? W jaki sposób możemy to sprawdzić? A gdyby tak po prostu wyliczyć… sumę?

Często żeby ocenić przystosowanie chromosomu wystarczy spróbować rozwiązać nim problem. Nie zawsze jest tak łatwo, dlatego cieszymy się tym co mamy.

Jeszcze bardziej przykładny przykład

Wygenerujmy losowo populację początkową:
1. (1,1,0,1,0,1,1,0,1,0)
2. (0,1,0,1,0,0,1,0,1,1)
3. (0,0,1,0,1,1,0,0,1,1)
4. (1,1,1,0,1,1,0,0,1,0)
5. (0,0,0,1,0,1,1,0,0,1)
6. (1,0,0,0,0,0,0,0,1,0)

Funkcja przystosowania (suma cyfr w chromosomie) zwróci kolejno: 6, 5, 5, 6, 4, 2. Stąd wniosek, że najlepiej przystosowane są chromosomy pierwszy i czwarty, natomiast najgorzej przystosowanym okazał się chromosom numer sześć.

No dobrze, określiliśmy wartość każdego chromosomu, ale co dalej? 6 nas nie satysfakcjonuje, dobrze znamy dokładne rozwiązanie, które wynosi 10.

A może by tak uruchomić algorytm ponownie, na nieco innej populacji? Jednak w jaki sposób zdecydować, które osobniki powinny się w niej znaleźć? Skąd wiadomo, kiedy należy przestać? O tym w kolejnym odcinku 😀 Tam też zamieszczę zaczątek implementacji mojej wersji KAG.

Reklamy

Jedna myśl na temat “Algorytm z natury genetyczny

Dodaj własny

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Connecting to %s

Blog na WordPress.com. Autor motywu: Anders Noren.

Up ↑

%d blogerów lubi to: