Dokumentacja klasy EvolutionaryMethod

#include <EvolutionaryMethod.h>

Diagram dziedziczenia dla EvolutionaryMethod

Method Observable Lista wszystkich składowych.

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ą:

  1. Metody selekcji:
  2. Metody mutacji:
  3. Metody krzyżowania:
Poszczególne metody opisane są w klasach je reprezentujących.

W metodzie można korzystać z nastepująych warunków stopu:
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


Metody publiczne

 ~EvolutionaryMethod (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () 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 SelectionMethodmcpSelectionMethod
CountedPtr< const MutationMethodmcpMutationMethod
CountedPtr< const CrossoverMethodmcpCrossoverMethod
CountedPtr< const EMStopConditionmcpStopCondition
 Warunek stopu.

Przyjaciele

class EvolutionaryMethodPanel
class InitialRangeValidator


Dokumentacja konstruktora i destruktora

EvolutionaryMethod::EvolutionaryMethod const EvolutionaryMethod from  )  [protected]
 

Konstruktor kopiujący.

Parametry:
from Obiekt, którego wartość jest kopiowana.


Dokumentacja atrybutów składowych

DoubleParameter EvolutionaryMethod::mCrossoverRate [protected]
 

Współczynnik wykorzystywany w niektórych metodach krzyżowania (np.

ThreeParticipantsCrossover).


Dokumentacja dla tej klasy została wygenerowana z plików:
Wygenerowano Fri Sep 29 21:04:51 2006 dla EduOptim2 programem  doxygen 1.4.6