Dokumentacja klasy NelderMead

#include <NelderMead.h>

Diagram dziedziczenia dla NelderMead

Method Observable Lista wszystkich składowych.

Opis szczegółowy

Algorytm optymalizacji metodą Neldera-Meada.

W metodzie Neldera-Meada po wykresie funkcji pełza sympleks złożony z N+1 punktów, gdzie N oznacza liczbę wymiarów problemu.

Algorytm metody:

Oznaczenia:
$ S^k $ - zbiór punktów sympleksu w k-tej iteracji
$ S_i $ - zbiór indeksów punktów należących do $ S^k $.
$ \check{S}^k = S^k \setminus \{x^k_w\} $
$ \check{S}_i $ - zbiór indeksów punktów należących do $ \check{S}^k $
$ x^k_b $ - najlepszy punkt sympleksu w k-tej iteracji
$ x^k_w $ - najgorszy punkt sympleksu w k-tej iteracji
$ x^k_v $ - prawie najgorszy punkt sympleksu w k-tej iteracji
$ \bar{x} $ - środek ciężkości zbioru $ \check{S}^k $
$ x_r $ - punkt powstały poprzez odbicie najgorszego punktu sympleksu względem punktu $ \bar{x} $
$ x_e $ - punkt przesunięty jeszcze dalej w tym samym kierunku, w którym nastąpiło odbicie najgorszego punktu sympleksu przy tworzeniu punktu $ x_r $
$ x_c $ - punkt znajdujący się pomiędzy najgorszym punktem sympleksu, a środkiem ciężkości pozostałych jego punktów lub tymże środkiem ciężkości, a punktem $ x_r $

Dane potrzebne do obliczeń:
$ f(x) $ - funkcja celu
$ r $ - współczynnik odbicia ($ r > 0 $, domyślnie 1)
$ e $ - współczynnik rozciągnięcia ($ e > r $, domyślnie 2)
$ c $ - współczynnik ściśnięcia ($ 0 < c < 1 $, domyślnie $ \frac{1}{2} $)
$ s $ - współczynnik skurczenia ($ 0 < s < 1 $, domyślnie $ \frac{1}{2} $)
$ x^0 $ - środek początkowego sympleksu
$ d $ - długość krawędzi początkowego sympleksu

Krok 0 (wstępny):
W tym kroku wyliczamy współrzędne wierzchołków początkowego sympleksu w ten sposób, by punkt $ x^0 $ znalazł się w jego środku.
Poniższe wzory potrzebne do utworzenia regularnego sympleksu zaczerpnięto z [1].
Wzór na wyliczenie j-tej współrzędnej i-tego wierzchołka sympleksu ma postać:

\[ x^{(j)}_i = \left\{ \begin{array}{ll} x^{(j)}_0 + \delta_1 \mbox{ gdy } i \not= j;\\ x^{(j)}_0 + \delta_2 \mbox{ gdy } i = j. \end{array} \right. \]

Wartości współczynnika $ \sigma_1 $ i $ \sigma_2 $ wyliczamy ze wzorów:

\[ \delta_1 = \left(\frac{\sqrt{N+1}+N-1}{N\sqrt{2}}\right)\frac{d}{2} \]

\[ \delta_2 = \left(\frac{\sqrt{N+1}-1}{N\sqrt{2}}\right)\frac{d}{2} \]

W powyższy sposób otwrzymujemy zbiór $ S^1 $.
W wierzchołkach aktualnego sympleksu wyliczamy wartości funkcji.
Wybieramy szczególne punkty sympleksu: $ x^1_b $, $ x^1_w $ i $ x^1_v $. Zapamiętujemy rownież wartości funkcji $ F_b = f(x^1_b) $, $ F_w = f(x^1_w) $ oraz $ F_v = f(x^1_v) $
Podstawiamy $ k = 1 $ i przechodzimy do kroku 1.

Krok 1:
Wyliczamy środek ciężkości punktów sympleksu z pominięciem punktu najgorszego wg wzoru:

\[ \bar{x} = \frac{ \sum_{i \in \check{S}_i} x_i }{N} \]

Przechodzimy do kroku 2.
Krok 2:
Wyznaczamy punkt $ x_r $ poprzez odbicie najgorszego punktu sympleksu względem środka ciężkości:

\[ x_r = \bar{x} + r(\bar{x}-x^k_w) \]

Wyliczamy wartość funkcji celu w tym punkcie.
Jeśli $ F_r < F_b $, to przechodzimy do kroku 3. W przeciwnym przypadku przechodzimy do kroku 5.

Krok 3:
Wyznaczamy punkt $ x_e $ zgodnie ze wzorem:

\[ x_e = \bar{x} + e(\bar{x}-x^k_w) \]

Wyliczamy wartość funkcji w tym punkcie.
Jeśli $ F_e < F_r $ to przechodzimy do kroku 4a. W przeciwnym wypadku przechodzimy do kroku 4b.

Krok 4a:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_e $ i przechodzimy do kroku 12.

Krok 4b:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_r $ i przechodzimy do kroku 12.

Krok 5:
Jeśli $ F_b \leq F_r < F_v $, to przechodzimy do kroku 6. W przeciwnym wypadku przechodzimy do kroku 7.

Krok 6:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_r $ i przechodzimy do kroku 12.

Krok 7:
Jeśli $ F_v \leq F_r < F_w $, to przechodzimy do kroku 8. W przeciwnym Wypadku przechodzimy do kroku 9.

Krok 8:
Wyznaczamy punkt $ x_c $ ze wzoru:

\[ x_c = x_r - c(x_r - \bar{x}) \]

Wyliczamy w tym punkcie wartość funkcji.
Jeśli $ F_c \leq F_r $, przechodzimy do kroku 10. W przeciwnym wypadku przechodzimy do kroku 11.

Krok 9:
Wyznaczamy punkt $ x_c $ ze wzoru:

\[ x_c = x^k_w + c(\bar{x} - x^k_w) \]

Wyliczamy w tym punkcie wartość funkcji.
Jeśli $ F_c \leq F^k_w $, przechodzimy do kroku 10. W przeciwnym wypadku przechodzimy do kroku 11.

Krok 10:
W sympleksie zastępujemy punkt $ x^k_w $ punktem $ x_c $ i przechodzimy do kroku 12.

Krok 11:
Dokonujemy skurczenia sympleksu w kierunku punktu najlepszego zgodnie z procedurą:

\[ x^{k+1}_i = x^k_i - s(x^k_i - x_b) \mbox{ dla } i \in S_i\]

Oczywiście w wyniku działania tej procedury punkt najlepszy nie zmieni swojego położenia.
W nowych punktach obliczamy wartości funkcji.

Krok 12:
Podstawiamy $ k = k+1 $.
Wybieramy szczególne punkty sympleksu: $ x^{k+1}_b $, $ x^{k+1}_w $ i $ x^{k+1}_v $. Zapamiętujemy rownież wartości funkcji $ F_b = f(x_b) $, $ F_w = f(x_w) $ oraz $ F_v = f(x_v) $
Przechodzimy do kroku 13.

Krok 13:
Jeśli spełniony jest warunek stopu, zakończ działanie algorytmu. Punktem wynikowym jest najlepszy punkt ostatniego sympleksu.
Jeśli warunek niejest spełniony przechodzimy do kroku 1.

Uwagi:
W metodzie można zastosować kilka rożnych warunków stopu


Postępując zgodnie z [2] do implementacji algorytmu wprowadzono usprawnienie dotyczące jest uznany za gorszy od wszystkich punktów o takiej samej wartości funkcji celu.

[1] Aleksander Ostanin - Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok 2003 oraz: [2] J. C. Lagarias, J. A. Reeds, M. H. Wright, P. E. Wright - Convergence Properties of the Nelder-Mead Simplex Function in low dimensions. (SIAM Journal on Optimization, Vol. 1, No. 1, pp 112-147).

W drugim źródle zaproponowano sposoby postępowania w przypadku gdy co najmniej w dwóch wierzchołkach sympleksu wartość funkcji jest taka sama.


Metody publiczne

 ~NelderMead (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () const
 Tworzy kopię obiektu.
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.
virtual wxString & rName ()

Statyczne metody publiczne

static MethodIdType ClassId ()
 Zwraca ID metody.

Metody chronione

 NelderMead ()
 Konstruktor domyślny.
 NelderMead (const NelderMead &from)
 Konstruktor kopiujący.

Atrybuty chronione

DoubleParameter mReflectionCoefficient
 Współczynnik odbicia.
DoubleParameter mExpansionCoefficient
 Wspóczynnik rozciągnięcia.
DoubleParameter mContractionCoefficient
 Współczynnik ściśnięcia.
DoubleParameter mShrinkageCoefficient
 Wspóczynnik skurczenia.
ColumnVector mStartingPoint
 Punkt startowy (środek pierwszego sympleksu).
ColumnVector mInitialStartingPoint
DoubleParameter mSideLength
 Długość boku początkowego sympleksu.
double mSimplexRange
 Promień sfery opisanej na sympleksie.
CountedPtr< const NMStopConditionmcpStopCondition
 Warunek stopu.

Przyjaciele

class NelderMeadPanel
class NelderMeadIteration

Komponenty

class  Simplex
 Klasa wewnętrzna, której obiekt reprezentuje sympleks złożony z obiektów klasy PointWithValue. Więcej...


Dokumentacja konstruktora i destruktora

NelderMead::NelderMead const NelderMead from  )  [protected]
 

Konstruktor kopiujący.

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


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