#include <RosenbrockDiscrete.h>
Diagram dziedziczenia dla RosenbrockDiscrete
Metoda poszukiwań prostych.
Podobnie jak algorytm Hooke'a i Jeevesa, oparta jest na wykonywaniu w każdej iteracji kroków próbnych wzdłuż ortogonalnych kierunków. Kierunki te, inaczej niż w metodzie HJ, mogą się zmieniać - na końcu każdej iteracji baza kierunków
jest obracana w taki sposób, aby zawierała kierunek największej poprawy i pozostałych
wzajemnie ortonormalnych kierunków.
Informacje wejściowe:
- minimalizowana funkcja
zmiennych,
- dowolnie wybrany punkt startowy,
- n-wymiarowy wektor początkowych długości kroku,
- współczynnik wydłużania kroku (
),
- współczynnik skracania kroku (
),
- wstępny warunek stopu - minimalna długość kroku próbnego,
- dokładność właściwego warunku stopu,
warunek stopu - do wyboru:
Oznaczenia:
- indeks aktualnego kierunku,
- numer aktualnej iteracji,
- aktualna baza kierunków,
- wektor sum długości udanych kroków próbnych w poszczególnych kierunkach,
- aktualny punkt próbny,
- najlepszy punkt w k-tym etapie,
- wartość funkcji w punkcie
,
- najlepsza wartość funkcji przed rozpoczęciem przeszukiwania kierunków z bazy,
- wektory sum przesunięć wykorzystywane przy obrocie bazy,
- kwadraty norm wektorów
wykorzystywane przy normalizacji nowej bazy (
).
Procedura.
Krok wstępny:
Podstawiamy:
Krok 1:
Badamy wartość funkcji w nowym punkcie próbnym (wykonując krok w i-tym kierunku):
Jeśli krok był udany (), to dodajemy długość kroku do sumy
, wydłużamy krok w bieżącym kierunku i zapamiętujemy aktualny punkt jako najlepszy:
Jeśli krok był nieudany (), to skracamy krok w bieżącym kierunku i odwracamy jego zwrot:
Podstawiamy i sprawdzamy, czy
. Jeśli tak, ponownie wykonujemy krok 1. Jeśli nie, podstawiamy
i przechodzimy do kroku 2.
Krok 2:
Sprawdzamy, czy przy ostatnim przeszukiwaniu kierunków nastąpiła poprawa.
Jeśli tak (), to podstawiamy:
i przechodzimy do kroku 1. W przeciwnym wypadku przechodzimy do kroku 3.
Krok 3:
Sprawdzamy wstępny warunek stopu:
i zapamiętujemy jego wartość logiczną.
Następnie sprawdzamy, czy w całej iteracji nastąpiła poprawa - jeśli tak (), to przechodzimy do kroku 4.
W przeciwnym wypadku (), jeśli wstępny warunek stopu jest spełniony, to STOP. Jeśli nie jest, podstawiamy
i przechodzimy do kroku 1.
Krok 4:
Sprawdzamy główny warunek stopu. Jeśli ten oraz wstępny warunek stopu z kroku 2 są spełnione, to STOP. W przeciwnym razie przechodzimy do kroku 5.
Krok 5:
Dokonujemy obrotu bazy, według algorytmu Palmera:
1) Dla :
Wyliczamy wektory sum przesunięć:
oraz wektor :
2) Tworzymy nowe kierunki ortonormalne :
a) Dla :
b) Na koniec tworzymy kierunek największej poprawy .
W ten sposób otrzymujemy nową bazę kierunków .
Następnie podstawiamy:
i przechodzimy do kroku 1.
Uwagi.
Oryginalna metoda Rosenbrocka wykorzystywała przy ortonormalizacji nowej bazy metodę Grama-Schmidta. W tej implementacji użyto metody Palmera, bardziej wydajnej i tworzącej poprawną bazę również w przypadku, gdy w iteracji istnieją kierunki, w których nie wykonano żadnego udanego kroku.
Metoda zaimplementowana na podstawie programu Franka Vanden Berghena (http://iridia.ulb.ac.be/%7Efvandenb/download.php?id=33), który powstał na podstawie publikacji:
1) Rosenbrock, H. H., An Automatic Method for Finding the Greatest or Least Value of a Function (1960). (http://iridia.ulb.ac.be/~fvandenb/optimization/paper_rosenbrock.zip)
2) Palmer, J. R., An improved procedure for orthogonalising the search vectors in Rosenbrock's and Swann's direct search optimisation methods (1969). (http://iridia.ulb.ac.be/~fvandenb/optimization/paper_palmer.zip)
Metody publiczne | |
~RosenbrockDiscrete (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 |
Sprawdza, czy dany problem może być rozwiązany tą metodą. | |
virtual StopConditions | AllowedStopConditions () const |
Zwraca listę warunków stopu odpowiednich dla danej metody. | |
Statyczne metody publiczne | |
static MethodIdType | ClassId () |
Zwraca ID metody. | |
Metody chronione | |
RosenbrockDiscrete (void) | |
Konstruktor domyślny. | |
RosenbrockDiscrete (const RosenbrockDiscrete &from) | |
Konstruktor kopiujący. | |
void | SearchAllDirections (const FunctionBase &function, ColumnVector &rxBest, double &rMin, const SquareMatrix &D, ColumnVector &rTau, ColumnVector &rLambda, RosenbrockDiscreteIteration &rIterationData) const |
Przeszukuje kierunki. | |
void | RotateBase (SquareMatrix &rD, const ColumnVector &lambda, RosenbrockDiscreteIteration &rIterationData) const |
Dokonuje obrotu bazy kierunków. | |
virtual wxString & | rName () |
Atrybuty chronione | |
ColumnVector | mTau |
Początkowe (zadane przez użytkownika) długości kroku próbnego, mogą się różnić dla poszczególnych kierunków. | |
DoubleParameter | mAlpha |
Współczynnik wydłużania kroku (![]() | |
DoubleParameter | mBeta |
Współczynnik skracania kroku (![]() | |
DoubleParameter | mDelta |
Minimalna długość kroku próbnego (![]() | |
ColumnVector | mStartingPoint |
Punkt startowy (![]() | |
ColumnVector | mInitialStartingPoint |
CountedPtr< const StandardStopCondition > | mcpStopCondition |
Warunek stopu. | |
Przyjaciele | |
class | RosenbrockDiscretePanel |
|
Konstruktor kopiujący.
|
|
Dokonuje obrotu bazy kierunków.
Na podstawie sum długości udanych kroków
Metoda wykorzystuje ortogonalizację Palmera:
gdzie:
oraz wektor
Następnie wykonana zostaje procedura utworzenia nowych kierunków ortonormalnych
2.
|
|
Przeszukuje kierunki.
Dla każdego kierunku
gdzie:
gdzie: Punkt próbny zostaje również zapamiętany jako najlepszy:
Jeśli krok nie powiódł się (
gdzie: Przebieg jest powtarzany do momentu, kiedy w żadnym z kierunków nie wykonano udanego kroku.
|