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)

Single point crossover

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)

Two point crossover

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)

uniform

Kolejne geny dziecka pochodzą losowo od pierwszego, albo drugiego rodzica.

11011100 + 10001011 = 10011111

  • Arytmetyczne (eng. arithmetic)

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:

mutation

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 🙂