Algorytmy genetyczne. Schematy. Część 2.

Schematy

Hej, w tym wpisie określimy czym są schematy, dlaczego odgrywają dużą rolę oraz jaki związek algorytmy genetyczne mają z matematyką. Dalej posługuję się książką Goldberga „Algorytmy genetyczne i ich zastosowania” ponieważ w jasny sposób opisuje te zagadnienia. Mam nadzieję, że potraktujecie moje posty jako inspirację do sięgnięcia po tę pozycję. W tym wpisie nadal będziemy opierać się na kodzie dwójkowym, gdyż będzie na nim łatwo pokazać zależności matematyczne.

Pamiętacie, jak w części pierwszej obliczaliśmy „na piechotę” jedną pętlę algorytmu? Mam nadzieję, że nie będzie dla Was niespodzianką, jak powiem, że to nie ciągi kodowe jako całość nas interesują. Co zatem? Jak w tytule – schematy jakie te ciągi przyjmują.

Schemat(Holland, 1968) jest to wzorzec opisujący podzbiór ciągów podobnych ze względu na ustalone pozycje.

Rozbijmy tę definicję na czynniki pierwsze. Dla naszego ciągu kodowego (chromosomu) alfabet wygląda następująco:

V=\left \{0,1  \right \}

Oznacza to, że możemy tworzyć  chromosomy z dwóch znaków: 1 oraz 0. Przypomnijmy sobie populację z poprzedniego wpisu.

Algorytmy genetyczne - selekcja

Weźmy teraz pewien schemat, taki że: H=**10. Osobniki, które mogłyby być reprezentantami takiego schematu mogą wyglądać następująco: 0010, 1110. Każda ustalona pozycja w schemacie (czyli taka, która jest zerem lub jedynką) pasuje również do osobników wymienionych wyżej. Gwiazdki, czyli symbol specjalny możemy zastąpić którymkolwiek znakiem z alfabetu, tworząc nowe osobniki. Możemy więc określić, że schemat H będzie się składał z alfabetu:

V^+=\left\{0,1,*\right\}

Jeśli porównamy nasz schemat z populacją początkową, możemy zauważyć, że odpowiednikami tego schematu są osobnik nr 1: 0110 oraz osobnik nr 4: 0010. Można dostrzec, że liczba schematów, które pasują do danego osobnika długości l wynosi 2^l (na każde miejsce możemy wstawić tę samą wartość lub symbol specjalny), za to liczba wszystkich możliwych schematów dla dowolnego ciągu długości l wynosi w naszym przykładzie 3^l dla naszego binarnego alfabetu (2+1), oraz  \left(\bar{V}+1\right)^l dla dowolnego alfabetu.

Przykład:

Dla ciągu A=0110 możemy stworzyć 2^l czyli 16 różnych schematów, np:

H_1=****,H_2=***0, H_3=**10, H_4=**1*, H_5=*110, H_6=*1**,H_7=0***, H_8=*11*

Dla jakiegoś ciągu o długości l=4 będą istniały (dla kodu dwójkowego): 3^4=27 schematy.

Ile schematów może istnieć w jednej populacji? Najmniejsza liczba to \bar{V}^l, ponieważ jeden schemat może obejmować wszystkie osobniki, największa t0 n*\2^l, gdyż liczba schematów równa jest wtedy ilości osobników. Dużo tych liczb, prawda? Do tego większość potęgowana, co może wskazywać na dużą liczbę obliczeń.

Pytanie ile tych schematów w rzeczywistości bierze udział w obliczeniach oraz jak są przekazywane z pokolenia na pokolenie oraz jak można je określać?

Schematy – czym je określić?

Zdefiniujmy sobie przykładowe schematy:

H_1=**1**0110 oraz H_2=*1*****0*

Możemy zauważyć, że:

  1. Schemat 1. jest o wiele bardziej precyzyjny niż schemat 2.
  2. Schemat 1. jest bardziej „zbity”, niż schemat 2., który jest „rozciągnięty” ( ma dużo symboli specjalnych pomiędzy znakami określonymi).

Te dwie zależności możemy określić jako rząd i rozpiętość schematu.

Rząd schematu.

Rząd schematu H będziemy oznaczać jako o(H) i będzie on równy liczbie pozycji ustalonych w schemacie. Dla naszych schematów:

H_1=**1**0110        o(H)=5

H_2=*1*****0*      o(H)=2

Rozpiętość schematu.

Rozpiętość schematu H będziemy oznaczać jako \delta(H) i będzie to odległość między dwoma skrajnymi pozycjami ustalonymi.

H_1=**1**0110        \delta(H)=9-3=6 – jego ostatnia pozycja ma numer 9, a pierwsza 3.

H_2=*1*****0*      \delta(H)=8-2 = 6 – ostatnia pozycja ma numer 8, a pierwsza numer 2.

H_2=*1*******      \delta(H)=0  – jest tylko jedna pozycja ustalona, a więc odległość wynosi 0.

Po co mi to wszystko?

W następnym wpisie o matematycznych podstawach oraz Podstawowym twierdzeniu algorytmów genetycznych wiedza ta przyda się do zrozumienia jak schematy zmieniają się, przeżywają lub umierają w procesie selekcji i krzyżowania, jaki wpływ ma na to prawdopodobieństwo i dlaczego pozycja genów jest ważna dla dobrych wyników algorytmów genetycznych.

Pamiętajcie by wpaść do Lubiedaka, który stworzył praktyczny wpis o AG, opisał go życiowym przykładem i zaimplementował 🙂


Sztuka na dziś

Nie wiem, czy lubicie subskrybować na youtubie ciekawe kanały. Ja mam swoich faworytów, jednym z nich jest Radosław Gajda z kanału Architecture is a good idea. Ucząc się do matury z historii sztuki, architektura była moją zmorą: style architektoniczne, plany, powiązania między mecenasami, artystami i mnóstwo dat. Zraziło mnie to na bardzo długo do wiedzy architektonicznej, skupiłam się na malarstwie i nowych mediach.

Mogę jednak śmiało zapewnić, że ten kanał sprawił, że z przyjemnością włączam kolejne filmy, pochłaniam wiedzę i zakochuję się na nowo w miejscach na świecie. Ostatnim takim filmikiem był ten o Wenecji zalinkowany wyżej – rozbudził moją chęć znalezienia taniego biletu lotniczego, by zobaczyć to miejsce na żywo 🙂 Dodatkowo w końcu udało mi się zapamiętać który Canaletto to „ten nasz” i dlaczego zawsze mi się mylili.

 

 

Podziel się!

1 komentarz

Odezwij się, będzie mi bardzo miło :)