Dokumentacja klasy EvolutionaryMethod

#include <EvolutionaryMethod.h>

Diagram dziedziczenia dla EvolutionaryMethod

Opis szczegółowy

Metoda oparta o algorytmy ewolucyjne.

Algorytmy ewolucyjne dają się zastosować w każdym zadaniu polegającym na przeszukiwaniu przestrzeni alternatywnych rozwiązań w poszukiwaniu najlepszego z nich. Takim zadaniem jest poszukiwanie optimum funkcji w przestrzeni dowolnej liczby wymiarów. W tym zastosowaniu algorytmy genetyczne charakteryzują się największą odpornością na występowanie minimów lokalnych. Z uwagi jednak na spory narzut obliczeniowy związany z ich użyciem należy stosować je tylko w uzasadnionych przypadkach (np. gdy nieciągłość funkcji celu może stanowić problem dla klasycznych algorytmów).

W algorytmach genetycznych operujących w przestrzeni liczb rzeczywistych problemem jest wybór odpowiedniego kodowania chromosomów. Klasyczne metody krzyżowania polegające na wymianie genów (bitów) pomiędzy chromosomami w wersji z liczbami zmiennoprzecinkowymi stają się bardzo skomplikowane i nieprzejrzyste. W niniejszej implementacji chromosom kodowany jest w sposób intuicyjny, czyli za pomocą wektora liczb rzeczywistych. Kodowanie to zdeterminowało użyte metody mutacji i krzyżowania.

Schemat działania algorytmu:
Krok 0 (wstępny):
Inicializacja - W zadanym obszarze tworzona jest losowo populacja o określonej liczbie osobników (chromosmów).

Krok 1:
Selekcja - Z początkowej populacji wybierane są osobniki najlepiej przystosowane wg algorytmów zawartych w konkretnych metodach selekcji (Narzucające się od razu proste rozwiązanie, czyli wybranie określonej liczenie grupy najlepszych osobników nie sprzyjałoby zróżnicowaniu populacji.

Krok 2:
Mutacja - Losowo wybrane z populacji osobniki ulegają mutacji, czyli losowej modyfikacji współrzędnych.

Krok 3:
Krzyżowanie - Proces polegający na rozmnażaniu się osobników wg zasad zawartych w konkretnych metodach krzyżowania. Osobniki namnażane są do momentu gdy populacja osiągnie początkową liczebność.

Krok 4:
Sprawdź czy został spełniony warunek stopu. Jeśli nie, to przejdź do kroku 1, jeśli tak, to zakończ działanie algorytmu. Za miniumum funkcji brany jest najlepszy osobnik z ostatniej populacji.

We wszystkich zaimplementowanych metodach selekcji, mutacji i krzyżowania kierowano się zasada, że najlepszy osobnik nie może zginąć, ani zostać zmodyfikowany.

Zaimplementowano następujące metody manipulacji populacją:

Metody selekcji:
- Selekcja proporcjonalna
- Selekcja turniejowa
Metody mutacji:
- Mutacja ze zmienną losową o rozkładzie jednostajnym w przedziale .
- Mutacja ze zmienną losową o rozkładzie Cauchy'ego
Metody krzyżowania:
- Krzyżowanie proste z dzieckiem w połowie drogi pomiędzy rodzicami
- Krzyżowanie tworzący kopię trzeciego osobnika przesuniętą o odcinek łączący rodziców

Poszczególne metody opisane są w klasach je reprezentujących.

W metodzie można korzystać z nastepująych warunków stopu:

Warunek $\| x^k_b - x^{k-1}_b \| \leq \varepsilon$ .
Warunek $| F^k_b - F^{k-1}_b | \leq \varepsilon$ .
Warunek $\frac{| F^k_b - F^{k-1}_b |}{\| x^k_b - x^{k-1}_b \|} \leq \varepsilon$ .
Warunek $\sigma(x: x \in P) \leq \varepsilon$ , czyli odchylenie standardowe odległości chromosomoów od chromosomu centralnego (zwartość populacji).
Warunek $\sigma(f(x): x \in P) \leq \varepsilon$ , czyli odchylenie standardowe wartości funkcji w chromosomach względem średniej wartości funkcji.
Warunek $N \leq \varepsilon$ , gdzie N oznacza liczbę iteracji

Uwaga: Nie istnieje jedna wybrana nomenklatura dotycząca algorytmów genetycznych, można się więc spotkać z różnymi nazwami użytymi na określenie tych samych etapów "ewolucji". W polskiej literaturze (np. [1]) selekcja nazywana jest zwykle reprodukcją. W źródłach angielskich reprodukcją częściej określa się następujące po sobie zjawiska krzyżowania i mutacji. W niniejszej pracy zdecydowano sie na podejście zachodnie, gdyż zaimplementowane metody selekcji nie pozwalają na utworzenie więcej niż jednej kopii wybranego/wylosowanego chromosomu, dokonują więc w rzeczywistości selekcji (wyboru) rozwiązań, a nie ich namnożenia. Takie podejście w swoich konsekwencjach nie różni się niczym od podejścia z utworzeniem wielu kopii lepszych osobników z następującymi potem operacjami mutacji i krzyżowania.
Zaimplementowany algorytm zawdzięcza wiele algorytmowi SADE (Simplified Atavistic Differential Evolution), którego opis można znaleźć na stronie: http://klobouk.fsv.cvut.cz/~ondra/sade/sade.html

Przy implementacji algorytmu korzystano z:
[1] Arabas, Jarosław: Wykłady z algorytmów ewolucyjnych, Wydawnictwa Naukowo-Techniczne, Warszawa, 2004
[2] Goldberg, David E.: Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne, Warszawa, 2003

Niniejszy dokument został półautomatycznie wycięty z dokumentacji kodu źródłowego programu Eduoptim 2. Pełna dokumentacja dostępna jest wraz ze źródłami bądź osobno w dziale pliki.
Hierarchia klas w programie nie odpowiada klasyfikacji metod optymalizacji.