Schemat działania algorytmu genetycznego

Zanim przystąpimy do szczegółowego omówienia poszczególnych etapów algorytmu genetycznego, przypomnijmy sobie podstawowy schemat jego działania zaprezentowany na poprzedniej lekcji.

RBMJPo3biC4Gh

Ilustracja przedstawia schemat algorytmiczny. Start kieruje do obiektu "Wybór początkowej populacji rozwiązań" ten obiekt kieruje strzałką dalej do "Ocena przystosowania osobników", następnym obiektem jest "Warunek końca", jeśli "tak", wskazuje on na obiekt "Zapamiętanie najlepszego rozwiązania" oraz kolejno na element "STOP". Jeśli "Warunek końca" nie został spełniony, wskazuje on na "Selekcja osobników", następnie na "Operatory genetyczne", oraz na "Powstanie nowej populacji". Ostatnia opcja wraca do obiektu "Ocena przystosowania osobników" co kończy pętlę.

Algorytm zaczyna swoje działanie od wygenerowania pierwszej populacji. Najczęściej  jest to wykonywane w sposób losowy. Następnie za pomocą określonej funkcji przystosowania każdemu z osobników przypisywana jest wartość, która jest odwzorowaniem jego jakości z punktu widzenia rozwiązywanego problemu. Zależy nam, aby za pomocą odpowiedniej metody selekcji wybrać najbardziej interesujących nas osobników z danej populacji. Następnie są oni poddawani zmianom za pomocą operatorów genetycznych takich jak operator krzyżowania oraz operator mutacji. Następnie zgodnie z wybraną metodą sukcesji tworzymy nową populację, która ponownie może być poddana naszemu algorytmowi genetycznemu.

Metody selekcji

Wybór odpowiedniej metody selekcji podczas projektowania naszego algorytmu genetycznego ma bardzo duży wpływ na jego jakość. Oto najczęściej wykorzystywane metody:

• metoda koła ruletki - polega ona na przydzieleniu każdemu osobnikowi takiego wycinka koła ruletki, jaki odpowiada jego jakości przystosowania w stosunku do innych – im lepszy osobnik, tym większy wycinek koła zajmuje. Oznacza to, że rozkładamy prawdopodobieństwo wylosowania osobników w sposób proporcjonalny do ich jakości.

• selekcja rankingowa - polega na przydzieleniu każdemu osobnikowi pewnej rangi, bazując na wartości jego przystosowania. Dzięki temu porządkujemy danych osobników w kolejności od najlepszego do najgorszego. Następnie wybieramy pewną określoną liczbę najlepszych osobników, którzy wezmą udział w rozmnażaniu. Osobniki, które nie zostały wybrane, są usuwane z populacji.

• metoda turniejowa - metoda ta dzieli populację na grupy, a następnie pomiędzy osobnikami z danej grupy jest rozgrywany turniej. Polega on na wyborze najlepszego osobnika w sposób deterministyczny lub losowy. Kolejną populację tworzą zwycięzcy turnieju z każdej grupy. Rozmiar grup może być dowolny, jednak najczęściej składają się one z dwóch lub trzech osobników.

Krzyżowanie osobników

Załóżmy, że w naszym algorytmie genetycznym osobnik jest reprezentowany przez 8‑bitową liczbę całkowitą. Każdy z bitów to jego gen, czyli wartość odpowiadająca pewnej cesze.

Po wybraniu grupy interesujących nas osobników z danej populacji następuje ich krzyżowanie. Jest to proces wymiany części informacji genetycznej pomiędzy rodzicami. Chromosomy rodzicielskie rozcinane są na dwa lub więcej fragmentów, a następnie pewne dwa fragmenty są między nimi wymieniane. W ten sposób powstają nowe osobniki.

R7xfLVtvDS4P7

Ilustracja przedstawia 4 zestawy po 8 bitów - 4 bajty. 2 bajty po lewej stronie jeden nad drugim, tak samo po prawej stronie. Pomiędzy lewym a prawym zestawem znajduje się strzałka kierująca od lewej do prawej strony. Po prawej stronie oznaczono połowę bajtu zamienioną pomiędzy zestawami z lewej strony.

Krzyżowanie nie zachodzi zawsze. Zazwyczaj w programie ustalamy pewne prawdopodobieństwo jego zajścia. Dodatkowo ze względu na liczbę punktów przecięć chromosomu wyróżniamy dwa rodzaje krzyżowań:

• krzyżowanie jednopunktowe - dwa rodzicielskie chromosomy przecinamy w jednym konkretnym punkcie, najczęściej jest to środek;

• krzyżowanie wielopunktowe - dwa rodzicielskie chromosomy przecinamy w dwóch lub więcej punktach.

R1LPvEpKoSMK6

Ilustracja przedstwia 4 zestawy po 8 bitów - 4 bajty. 2 bajty po lewej i 2 po prawej stronie, pomiędzy którymi znajduje się strzałka wskazująca od lewej do prawej. Po prawej stronie zaznaczono zamianę 3 bitów pomiędzy pierwszym - górnym - a drugim - dolnym - zestawem.

Mutacja genów

Osobniki powstałe w wyniku krzyżowania są następnie poddawane procesowi mutacji. Polega on na losowej zmianie wartości genów danego osobnika. Tak samo jak w przypadku krzyżowania, mutacja ma pewne określone prawdopodobieństwo zajścia. Najczęściej jest ono bardzo małe (w okolicy 1%), ponieważ w przeciwnym razie w wynikach pojawiłoby się za dużo losowości, a ewentualne korzystne zmiany nie będą miały szans na utrwalenie się w populacji.

Jeżeli nasz osobnik jest reprezentowany przez 8‑bitową liczbę całkowitą, to mutacja polega na negacji konkretnego bitu. Przechodzimy po każdym genie każdego osobnika i losujemy zdarzenie zajścia mutacji.

RI3rBbQCaPFIc

Ilustracja przedstawia dwa zestawy bitów, które są identyczne poza jednym - środkowym - oznaczonym odmiennym kolorem, bit ten zmiena swoją wartość z 1 na 0. Pomiędzy zestawami znajduje się strzałka wskazująca kierunek z lewego na prawy zestaw.

Zastosowanie mutacji w naszym algorytmie genetycznym jest kluczowe. Dzięki niej dodawana jest pewna losowość, która gra istotną rolę w procesie przeszukiwania przestrzeni możliwych rozwiązań.

Metody sukcesji

Po wykonaniu operacji krzyżowania oraz mutacji należy przeprowadzić proces sukcesjisukcesjasukcesji. Wybór odpowiedniej metody sukcesji wpływa na szybkość znajdowania optymalnego rozwiązania, ale też może zwiększać ryzyko osiągania lokalnych ekstremów lub przedwczesnej zbieżności. Oto najczęściej wykorzystywane metody sukcesji:

• sukcesja z całkowitym zastępowaniem - nową populacją bazową staje się populacja potomna. Oznacza to, że żaden osobnik z poprzedniej populacji nie zostaje przeniesiony do nowej. Metoda ta najwolniej prowadzi do optymalnego rozwiązania, ale jest najbardziej odporna na tendencję osiągania ekstremów.

• sukcesja z częściowym zastępowaniem - w nowej populacji znajdują się osobniki z poprzedniej i potomnej populacji. Metoda ta prowadzi zwykle do stabilniejszej pracy algorytmu ewolucyjnego, ale może spowodować tendencję do osiągania ekstremów lokalnych.

• sukcesja elitarna - gwarantuje, że w nowej populacji znajduje się co najmniej jeden najlepszy osobnik z poprzedniej populacji. Może to przyspieszyć znalezienie optymalnego rozwiązania, ale tym samym zwiększa prawdopodobieństwo osiągania ekstremów lokalnych.

Przykład algorytmu genetycznego

Do lepszego wyjaśnienia mechanizmów działania populacji, prześledzimy działanie jednej iteracji algorytmu genetycznego na przykładowym problemie. Będziemy dążyć do minimalizacji wartości funkcji na zbiorze liczb całkowitych z przedziału $[0,31]$. Nasza funkcja jest dana następującym wzorem:

Ponieważ poszukujemy najmniejszej wartości funkcji w przedziale $[0,31]$, to osobnikiem w naszym algorytmie genetycznym będzie 5‑bitowa liczba całkowita. Będzie to argument naszej funkcji zapisany w systemie dwójkowym.

RHLeUea7wmcSZ

Ilustracja wykresu funkcji, której wzór został przedstawiony wcześniej, której dziedzina została ograniczona do wartości of 0 do 31 włącznie. Wykres rozpoczyna się od 0, następnie opada delikatnie, aby zacząć wzrastać w granicach x równego 18, funkcja przypomnia kształtem przewrócony znak zapytania, bądź też małżowinę uszną.

Parametry i metody naszego algorytmu genetycznego:

• metoda selekcji: metoda koła ruletki,

• krzyżowanie: jednopunktowe,

• prawdopodobieństwo krzyżowania: 1,

• prawdopodobieństwo mutacji: 0,02,

• metoda sukcesji: sukcesja z całkowitym zastępowaniem.

• rozmiar populacji: 6

Pozostaje jeszcze kwestia wyboru populacji startowej algorytmu genetycznego. W tym przypadku została ona wygenerowana w sposób losowy. Przy użyciu generatora liczb pseudolosowych wylosowano sześć liczb całkowitych z przedziału $[0,31]$.

Następnie po jednej iteracji algorytmu genetycznego otrzymujemy:

Po jednej iteracji algorytmu najmniejszą wartością funkcji $f$ jaką udało nam się uzyskać w nowym pokoleniu jest $f(20) = -5200$. Jest to wynik gorszy niż w poprzednim pokoleniu, który wynosił $f(19) = -5225$. Taka sytuacja może się wydarzyć ze względu na losowość naszego algorytmu genetycznego. Można temu zapobiec, stosując inną metodę selekcji lub sukcesji. Innym możliwym rozwiązaniem jest zwiększenie liczby iteracji i zapisywanie najlepszego wyniku spośród wszystkich dotychczasowych populacji.

Zastosowania algorytmów genetycznych

Algorytmy genetyczne są najczęściej wykorzystywane do rozwiązywania problemów optymalizacyjnych. Wykorzystując element losowości, są one w stanie lepiej przeszukiwać duże przestrzenie rozwiązań w porównaniu do standardowych algorytmów deterministycznych.

Natomiast problemy optymalizacyjne można znaleźć w wielu różnych dziedzinach. Może to być problem zaprojektowania skrzydła samolotu o pewnej powierzchni i jak najmniejszej wadze. Projektując układy bramek logicznych w układzie elektronicznym, warto optymalizować jego koszt budowy przy zachowaniu pewnej funkcjonalności. Algorytmy genetyczne można także zastosować przy doborze liczby neuronów w warstwach ukrytych sieci neuronowych. Wtedy parametrem poddawanym optymalizacji jest poprawność działania sieci.

Słownik