Mamy już za sobą implementację selekcji chromosomów, z których stworzymy kolejne pokolenie. Teraz chcielibyśmy, żeby było ono w jakiś sposób lepsze, a przede wszystkim inne od poprzedniego. Do tego celu przyda nam się krzyżowanie i mutacja w algorytmach genetycznych.
Temat wydaje się być bardzo bliski życia codziennego, prawda? Przecież na co dzień widzimy jego efekty wszędzie dookoła. To właśnie dzięki krzyżowaniu i mutacji genów mamy w przyrodzie taką różnorodność. Kolejne rasy piesełów tworzone na przestrzeni wieków nie są niczym innym, jak krzyżowaniem tych już istniejących. Nikt przecież nie jest w stanie od zera „wygenerować” inaczej wyglądającego zwierzaka (chyba). Doskonałym przykładem mutacji z kolei, jest każda niebieskooka osoba. Już kilka lat temu ogłoszono, że ludzie o tym kolorze oczu pochodzą najprawdopodobniej od jednego przodka, u którego nastąpiła właśnie mutacja w łańcuchu DNA. Jak widać ewolucja postanowiła podtrzymać taki efekt i teraz możemy spotkać jego efekty na co dzień 🙂
Krzyżowanie i mutacja w algorytmach genetycznych
Jaką rolę natomiast pełnią te mechanizmy w algorytmach genetycznych? Analogicznie jak w przyrodzie, uzyskujemy dzięki nim pewne mniej lub bardziej losowe zmiany w populacji, które mogą doprowadzić do tego, że otrzymamy chromosom będący lepszym rozwiązaniem naszego problemu. W tym właśnie miejscu wychodzi różnica pomiędzy klasycznym algorytmem, a genetycznym – w pierwszym z nich rządzimy dosłownie wszystkim i nie ma miejsca na losowość, gdyż mamy z góry określone ścieżki, którymi podążamy. W drugim przypadku natomiast mamy bardzo mało do powiedzenia, bo wskazujemy jedynie sposób na obliczenie wartości danego osobnika w rozwiązaniu problemu. Reszta to całkowity los na loterii w połączeniu z odpowiednim wybieraniem co raz lepszych chromosomów.
Rodzaje krzyżowania
Jak pewnie się domyślasz, krzyżowanie polega na tym żeby wziąć trochę od jednego i drugiego rodzica i to wszystko połączyć w całość. Dokładnie tak jest! Sposobów na to może być tyle, ile przyniesie nam wyobraźnia, jednak jest kilka stosowanych w algorytmach genetycznych najczęściej:
- Jednopunktowe (eng. single point)
W całym łańcuchu losowo wybieramy punkt przełamania i to co jest przed nim bierzemy od rodzica A, a to co za nim od rodzica B. Gdyby nasz chromosom był ciągiem bitów mogłoby się to odbyć tak:
11011100 + 10001011 = 11011|011
- Dwupunktowe (eng. two point)
Tym razem wybieramy dwa punkty i wszystko co jest przed pierwszym i po drugim pochodzi od rodzica A, natomiast przestrzeń pomiędzy nimi od rodzica B.
11011100 + 10001011 = 11|00101|0
- Jednorodne (eng. uniform)
Kolejne geny dziecka pochodzą losowo od pierwszego, albo drugiego rodzica.
11011100 + 10001011 = 10011111
- Arytmetyczne (eng. arithmetic)
Dokonujemy wybranej operacji arytmetycznej, aby uzyskać potomka. Najlepiej to pokazać na operacji bitowej, np. AND:
11011100 + 10001011 = 10001000
Oczywiście sama implementacja każdego rodzaju krzyżowania może być różna w zależności od postaci chromosomów. Często może się okazać, że na określonych genach nie możemy dokonać jakiegoś typu miksowania. Musimy więc to mieć na uwadze tworząc reprezentację rozwiązania naszego problemu w algorytmie genetycznym.
Mutacja
Mutacja, tak jak w przypadku DNA, polega na losowej zmianie jakiegoś genu:
Efekty takiej operacji są ciężkie do przewidzenia, jednak mogą doprowadzić to stworzenia chromosomu, który okaże się być doskonałym rozwiązaniem, które niekoniecznie pochodzi od połączenia osobników z poprzedniego pokolenia.
Omówiliśmy więc podstawowe operacje, dzięki którym w ogóle jesteśmy w stanie otrzymywać różne rozwiązania za pomocą algorytmów genetycznych. Jest to kolejny temat, który został zaadoptowany do informatyki z życia codziennego. W następnym poście zobaczysz jak wykorzystamy te zagadnienia w kodzie 🙂
Dodaj komentarz