Dokumentacja klasy FibonacciDivision

#include <FibonacciDivision.h>

Diagram dziedziczenia dla FibonacciDivision

SectionLineSearch LineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Fibonacciego.

Metoda Fibonacciego, opublikowana w 1953 roku przez Kiefera, jest szczególnie przydatna w sytuacjach gdy liczba obliczeń, które możemy wykonać jest ograniczona (np. w systemach czasu rzeczywistego). Metoda daje najmniejszy przedział nieokreśloności przy zadanej z góry liczbie wyliczeń funkcji.

Algorytm metody:

Oznaczenia:
$ a^k $ - lewy kraniec przedziału poszukiwań w k-tej iteracji
$ b^k $ - prawy kraniec przedziału poszukiwań w k-tej iteracji
$ \lambda^k $ - pierwszy punkt wyliczany w k-tej iteracji
$ \mu^k $ - drugi punkt wyliczany w k-tej iteracji
$ F_k $ - k-ty element ciągu Fibonacciego

Dane potrzebne do obliczeń:
$ f(x) $ - minimalizowana funkcja jednej zmiennej
$ a^1 $ - lewy kraniec przedziału poszukiwań
$ b^1 $ - prawy kraniec przedziału poszukiwań
$ \varepsilon $ - wymagana dokładność rozwiązania

W metodzie Fibonacciego dokładność rozumiana jest jako szerokość ostatniego przdziału nieokreśloności. Wymagamy by była ona mniejsza od $ \varepsilon $. Charakterystyczną cechą metody Fibonacciego jest to, że liczbę kroków optymalizacji ustalamy przed rozpoczęciem obliczeń. $ K $ musi spełniać warunek: $ (b^1 - a^1) / F_K \leq \varepsilon $.
Krok 1:
Tworzymy dwa nowe punkty ($ \lambda^k $ i $ \mu^k $) leżące pomiędzy a i b zgodnie ze wzorami:

\[ \lambda^k = a^k + \frac{F_{K-k-1}}{F_{K-k+1}}(b^k - a^k) \]

\[ \mu^k = a^k + \frac{F_{K-k}}{F_{K-k+1}}(b^k - a^k) \]

W nowoutworzonych punktach wyliczamy wartość funkcji.

Krok 2:
Jeśli $ f(\lambda^k) > f(\mu^k)$, to podstawiamy:

\[ \left\{ \begin{array}{llll} a^{k+1} = \lambda^k \\ b_{k+1} = b^k \\ \lambda^{k+1} = \mu^k \\ \mu^{k+1} = a^{k+1} + \frac{F_{K-i}}{F_{K-k+1}}(b^{k+1} - a^{k+1}) \end{array} \right. \]

oraz obliczamy wartość funkcji w punkcie $ \mu^{k+1} $. Następnie przechodzimy do punktu 4.
Jednak gdy $ f(\lambda^k) \leq f(\mu^k) $ przechodzimy do kroku 3.

Krok 3:
Podstawiamy

\[ \left\{ \begin{array}{llll} a^{k+1} = a^k \\ b^{k+1} = \mu^k \\ \mu^{k+1} = \lambda^k \\ \lambda^{k+1} = a^{k+1} + \frac{F_{K-k-1}}{F_{K-k+1}}(b^{k+1} - a^{k+1}) \end{array} \right. \]

i wyliczamy wartość funkcji w punkcie $ \lambda^{k+1} $. Następnie przechdzimy do punktu 4.

Krok 4:
Podstawiamy $ k=k+1 $. Jeśli $ i < K-1 $, to przejść do kroku 2. W przeciwnym wypadku przejść do kroku 5.

Krok 5:

\[ \left\{ \begin{array}{ll} \lambda^K = \lambda^{K-1} \\ \mu^K = \lambda^K + \varepsilon \end{array} \right. \]

Jeśli $ f(\lambda^K) > f(\mu^K) $, to podstawiamy:

\[ \left\{ \begin{array}{ll} a^K = \lambda^K \\ b^K = b^{K-1} \end{array} \right. \]

Jeśli natomiast $ f(\lambda^K) \leq f(\mu^K) $, to podstawiamy:

\[ \left\{ \begin{array}{ll} a^K = a^{K-1} \\ b^K = \lambda^K \end{array} \right. \]

Wynikiem działania metody jest punkt w środku odcinka $ [a, b] $.

Algotytm zaimplementowany na podstawie // TODO: tej rosyjskiej ksiażki.


Metody publiczne

 ~FibonacciDivision (void)
 Destruktor.
virtual std::auto_ptr< MethodClone () const
 Tworzy kopię metody.
virtual const wxString & Name () const
 Zwraca nazwę metody.
virtual MethodIdType Id () const
 Zwraca ID metody.
virtual bool CanHandle (const ProblemBase *pProblem) const
 Sprawdza, czy dany problem może być rozwiązany tą metodą.

Statyczne metody publiczne

static MethodIdType ClassId ()
 Zwraca ID metody.

Metody chronione

 FibonacciDivision (void)
 Konstruktor domyślny.
 FibonacciDivision (const FibonacciDivision &from)
 Konstruktor kopiujący.
std::vector< unsigned int > GenerateFibonacciSequence (double a, double b, double epsilon) const
 Wygeneruj ciąg Fibonacciego.
virtual wxString & rName ()

Przyjaciele

class SectionLineSearchPanel< FibonacciDivision >


Dokumentacja konstruktora i destruktora

FibonacciDivision::FibonacciDivision const FibonacciDivision from  )  [protected]
 

Konstruktor kopiujący.

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


Dokumentacja funkcji składowych

vector< unsigned int > FibonacciDivision::GenerateFibonacciSequence double  a,
double  b,
double  epsilon
const [protected]
 

Wygeneruj ciąg Fibonacciego.

Wygeneruj ciąg Fibonacciego wystarczająco długi by w wyniku działania metody można było otrzymać przedział nieokresloności o zadanej długości.

Parametry:
a lewy kraniec początkowego przedziału poszukiwań
b prawy kraniec początkowego przedziału poszukiwań
epsilon wymagana dokładność
Zwraca:
wygenerowany ciąg Fibonacciego


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