Przeczytaj
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.
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.
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.
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.
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 sukcesjisukcesji. 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 . Nasza funkcja jest dana następującym wzorem:
Ponieważ poszukujemy najmniejszej wartości funkcji w przedziale , to osobnikiem w naszym algorytmie genetycznym będzie 5‑bitowa liczba całkowita. Będzie to argument naszej funkcji zapisany w systemie dwójkowym.
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 .
Numer osobnika | Populacja początkowa | Wartość | Wartość | Prawdopodobieństwo wylosowania osobnika | Liczba wylosowanych kopii |
1 | 00101 | 5 | -1375 | 0,0856 | 0 |
2 | 10011 | 19 | -5225 | 0,3253 | 2 |
3 | 00111 | 7 | -2093 | 0,1304 | 1 |
4 | 01100 | 12 | -3888 | 0,2421 | 2 |
5 | 11101 | 29 | -1015 | 0,0632 | 0 |
6 | 01000 | 8 | -2464 | 0,1534 | 1 |
Następnie po jednej iteracji algorytmu genetycznego otrzymujemy:
Pula rodzicielska | Wylosowany punkt krzyżowania | Populacja po krzyżowaniu | Populacja po mutacji | Wartość | Wartość |
10011 | 2 | 10100 | 10100 | 20 | -5200 |
01100 | 2 | 01011 | 01011 | 11 | -3553 |
10011 | 3 | 10000 | 10010 | 18 | -5184 |
01000 | 3 | 01011 | 01011 | 11 | -3553 |
01100 | 2 | 01111 | 01111 | 15 | -4725 |
00111 | 2 | 00100 | 01100 | 12 | -3888 |
Po jednej iteracji algorytmu najmniejszą wartością funkcji jaką udało nam się uzyskać w nowym pokoleniu jest . Jest to wynik gorszy niż w poprzednim pokoleniu, który wynosił . 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
proces zastępowania osobników ze starej populacji
metoda wyboru populacji startowej algorytmu genetycznego polegająca na doborze konkretnej puli osobników, zazwyczaj mało różnorodnej