Optymalizacja

Zdefiniuj algorytm genetyczny

Omawiając, w jaki sposób cBoty mogą być optymalizowane, wspomnieliśmy, że cBoty można udoskonalać za pomocą metody algorytmu genetycznego. W tym przewodniku wyjaśniamy dokładnie, czym jest i jak działa.

Metoda algorytmu genetycznego opiera się na teorii doboru naturalnego. Teoria ta głosi, że tylko najlepiej przystosowane osobniki przetrwają do kolejnej reprodukcji.

W optymalizacji cBotów każdy przebieg optymalizacyjny jest uważany za osobnika. Aby ocenić poszczególne przebiegi, algorytm genetyczny oblicza określoną ocenę dopasowania dla każdego przebiegu i porównuje tę ocenę ze wszystkimi innymi przebiegami.

Aby działał, algorytm genetyczny potrzebuje populacji początkowej. Aby ją wygenerować, optymalizator uruchomi kilka różnych przebiegów z losowymi parametrami. Po utworzeniu populacji początkowej algorytm rozpocznie proces znajdowania najlepiej dopasowanego przebiegu optymalizacyjnego. Proces ten trwa do momentu, gdy oceny dopasowania przebiegów potomnych zaczną stagnować i zbiegać się. W tym momencie algorytm jest zatrzymywany.

Etapy algorytmu genetycznego

Każdy algorytm genetyczny ma następujące etapy.

graph TB
  B([Selekcja]) ==> C([Krzyżowanie]);
  C ==> D([Mutacja]);
  D ==> B;

Etapy są wyjaśnione w następujący sposób.

Selekcja

Na tym etapie algorytm znajduje dwa najlepiej dopasowane przebiegi optymalizacyjne, używając ich odpowiednich ocen dopasowania.

Krzyżowanie

Po znalezieniu dwóch najlepiej dopasowanych przebiegów optymalizacyjnych algorytm wykorzystuje je do tworzenia nowych przebiegów potomnych (lub potomstwa) poprzez użycie kombinacji wartości parametrów obu przebiegów rodzicielskich.

Mutacja

Na tym etapie algorytm mutuje przebiegi potomne poprzez losową modyfikację jednej lub więcej wartości parametrów.

Po etapie mutacji optymalizator uruchomi nowy przebieg optymalizacyjny potomny. Następnie powtórzy wszystkie etapy, ale tylko wtedy, gdy ocena dopasowania przebiegu potomnego była wyższa niż ostatni najlepiej dopasowany przebieg optymalizacyjny. Taki wynik oznaczałby, że jest miejsce na poprawę, wskazując, że optymalizacja powinna być kontynuowana.

W przeciwnym razie algorytm zwiększy swój licznik stagnacji. Jeśli licznik stagnacji osiągnie wartość parametru okresu stagnacji algorytmu, proces optymalizacji zostanie automatycznie zatrzymany.

Parametry algorytmu genetycznego

Algorytm genetyczny ma kilka parametrów, których używa podczas swojego działania. Tych parametrów nie można zmienić.