#include <EvolutionaryMethod.h>
Diagram dziedziczenia dla EvolutionaryMethod
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ą:
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
Metody publiczne | |
~EvolutionaryMethod (void) | |
Destruktor. | |
virtual std::auto_ptr< Method > | Clone () const |
Tworzy kopię metody. | |
virtual void | UpdateStartingConditions (const Result *result) const |
virtual void | ResetStartingConditions () const |
virtual const wxString & | Name () const |
Zwraca nazwę metody. | |
virtual MethodIdType | Id () const |
Zwraca ID metody. | |
virtual wxString | ToString (bool standalone=true) const |
Zwraca opis tekstowy metody (nazwa + parametry). | |
virtual bool | CanHandle (const ProblemBase *pProblem) const |
Czy metoda nadaje się do rozwiązania zadanego problemu. | |
virtual StopConditions | AllowedStopConditions () const |
Zwraca listę warunków stopu odpowiednich dla danej metody. | |
Statyczne metody publiczne | |
static MethodIdType | ClassId () |
Zwraca ID metody. | |
Metody chronione | |
EvolutionaryMethod (void) | |
Konstruktor domyślny. | |
EvolutionaryMethod (const EvolutionaryMethod &from) | |
Konstruktor kopiujący. | |
virtual wxString & | rName () |
Atrybuty chronione | |
ColumnVector | mInitialRangeMinBounds |
Punkt startowy. | |
ColumnVector | mInitialRangeMaxBounds |
ColumnVector | mRangeMinBounds |
ColumnVector | mRangeMaxBounds |
unsigned | mNumberOfChromosomes |
DoubleParameter | mSurvivalRate |
Relatywna wielkość populacji, która ma zostać po dokonaniu selekcji. | |
DoubleParameter | mRadioactivity |
Prawdopodobieństwo zajścia mutacji osobnika. | |
DoubleParameter | mMutationRate |
Współczynnik mutacji decydujący o tym jak bardzo zmienią się współrzędne mutowanego punktu. | |
DoubleParameter | mCrossoverRate |
Współczynnik wykorzystywany w niektórych metodach krzyżowania (np. | |
CountedPtr< const SelectionMethod > | mcpSelectionMethod |
CountedPtr< const MutationMethod > | mcpMutationMethod |
CountedPtr< const CrossoverMethod > | mcpCrossoverMethod |
CountedPtr< const EMStopCondition > | mcpStopCondition |
Warunek stopu. | |
Przyjaciele | |
class | EvolutionaryMethodPanel |
class | InitialRangeValidator |
|
Konstruktor kopiujący.
|
|
Współczynnik wykorzystywany w niektórych metodach krzyżowania (np. |