Języki

You are here

Algorytm ewolucyjny kukiełek

AE opiera się na selekcji, krzyżowaniu i mutacji. Należy również odpowiednio zakodować rozwiązanie w genotypie. Niniejsza sekcja zawiera opis rozwiązań przyjętych w prezentowanym programie.

Kodowanie rozwiązań

W przypadku naszego przykładowego problemu kodowanie jest proste: wszystkie współrzędne, kąty i promienie przechowywane są jako zmienne całkowitoliczbowe.

Krzyżowanie

Użyty operator krzyżowania pobiera wartości odpowiadających sobie zmiennych obojga rodziców (np. odcięte lewej dłoni, promienie poziome korpusu) oraz oblicza ich średnią arytmetyczną. Wartość ta staje się wartością odpowiedniej zmiennej potomka.

Mutacja

Mutacji podlegają jedynie kukiełki należące do potomstwa. Operacja mutacji dla każdej zmiennej z genotypu danej kukiełki losuje, czy mutować tę zmienną (z prawdopodobieństwem sukcesu równym parametrowi "Prawdopodobieństwo mutacji zmiennej". Jeśli nie, to rozważa następną zmienną, jeśli tak, to dodaje do niej lub odejmuje wartość losową z przedziału o szerokości 50% przedziału zmienności zmiennej. Wartość tego zaburzenia losowana jest z rozkładem normalnym, tak żeby częściej zdarzały się drobne kroki niż radykalne zmiany.

Selekcja

W programie użyto selekcji opartej na mechanizmie ruletki. Jego nazwa bierze się z możliwej obrazowej interpretacji: Każdemu osobnikowi populacji przydziela się na kole ruletki odcinek o długości proporcjonalnej do jego dopasowania, a potem kręci ruletką tyle razy, ile ma być osobników w nowej populacji. Osobniki lepiej dopasowane mają zatem większą szansę bycia wybieranymi. Kontrolę nad tym mechanizmem zapewnia parametr "Napór selekcyjny". Służy on do przekształcenia oryginalnych ocen kukiełek do takiej postaci, w której stosunek wartości oceny kukiełki najlepiej dopasowanej do oceny kukiełki "średniej" jest równy temu właśnie parametrowi. Dzięki temu możemy ustalić, że kukiełka najlepsza ma mieć np. dwa razy większe szanse na znalezienie się w nowej populacji niż kukiełka średnia (bo jeśli będzie miała dwa razy lepszą wartość funkcji oceny niż kukiełka średnia, to będzie również miała dwa razy większe szanse na wylosowanie podczas kręcenia ruletką).
Duża wartość naporu selekcyjnego prowadzi do zbyt szybkiego ujednolicenia populacji, zbyt mała wartość tego parametru powoduje zanik własności preferencji kukiełek lepiej dopasowanych.

Wpływ parametrów regulujących działanie wymienionych wyżej mechanizmów na efektywność AE łatwo można zauważyć bawiąc się ich wartościami w załączonym programie.