Strona główna

8. Metody poszukiwania minimum funkcji celu. Metody optymalizacji


Pobieranie 16.16 Kb.
Data19.06.2016
Rozmiar16.16 Kb.

8.Metody poszukiwania minimum funkcji celu. Metody optymalizacji

Ogólny podział metod optymalizacji, uważanych za najbardziej reprezentatywne, przedstawia rysunek. Teoria i metody obliczeniowe optymalizacji są opisane w literaturze. Są tu konwencjonalne, klasyczne metody optymalizacji oraz, stosunkowo nowe, metody optymalizacji globalnej.


    1. Klasyczne metody optymalizacji


Wśród klasycznych metod optymalizacji bez ograniczeń, wyróżnia się:

  • metody bezgradientowe, które w każdej iteracji wykorzystują informacje tylko o wartościach funkcji celu FC,

  • metody gradientowe, które w każdej iteracji wykorzystują informacje o wartościach funkcji celu FC oraz o wartościach gradientu FC.

Metody z ograniczeniami muszą dodatkowo uwzględniać odpowiednio wartości funkcji celu FC i funkcji ograniczających G, oraz wartości ich gradientów FC i G.

Podziału metod optymalizacji można dokonać także ze względu na sposób rozwiązywania zadania i tu wyróżniamy: metody wymiany (ang. exchange algorithms), metody bezpośrednie (ang. direct search), metody aproksymacyjne (metoda funkcji kary, metoda aproksymacji kwadratowych).

Metody bezgradientowe są łatwiejsze w implementacji, ale wolniejsze. W metodach gradientowych wyznaczany jest kierunek poszukiwania minimum. Jednakże metody postępujące ścieżką największego spadku zawodzą w pobliżu minimum FC. Mają one tendencję do błądzenia. Z powyższego wynika zasadność stosowania algorytmów kombinowanych: dla punktów przestrzeni parametrów relatywnie dalekich od minimum FC stosuje się metodę największego spadku, a w pobliżu minimum zastępuje się ją metodą linearyzacji funkcji regresji, np. metodą Gaussa-Newtona. Tak właśnie przebiegają obliczenia według metody Marquardta-Levenberga. Jest ona metodą kombinowaną, wykorzystującą zalety zarówno metody gradientowej jak i bezgradientowej. W metodzie tej kierunek w przestrzeni parametrów dający najszybszy spadek wartości FC jest wyznaczany w oparciu o wartości współczynników czułości tej funkcji względem poszczególnych jej parametrów, oraz na podstawie wyniku obliczeń w poprzednim kroku. W pobliżu minimum FC, kiedy metoda najszybszego spadku traci efektywność, zastępuje się ją metodą Gaussa-Newtona. Funkcję rozwija się w szereg Taylora i ogranicza do jej składnika liniowego. Następnie, poszukiwanie minimum jest poprzedzone analitycznym określeniem jego położenia, tak jakby zagadnienie było liniowe. Dalsze ewentualne iteracje służą do precyzyjnego zlokalizowania minimum. Może to być konieczne ze względu na błąd związany z uproszczeniem zagadnienia do liniowego. Ta kombinowana metoda Marquardta-Levenberga jest często rekomendowana jako efektywna.

    1. Metody optymalizacji globalnej


Stosunkowo nową grupą metod optymalizacji są metody optymalizacji globalnej. Należą tu: metoda grupowania (ang. clustering method), metoda symulowanego wyżarzania (ang. simulated annealing) i algorytmy genetyczne. Metody te są stosowane do wyznaczania parametrów zapewniających minimum funkcji celu zdefiniowanej np. jako suma kwadratów odchyłek. Są one również stosowane do analizy danych pomiarowych, a także do rozwiązywania tzw. zagadnień źle uwarunkowanych.

Konwencjonalne metody poszukiwania minimum startują z obranego punktu początkowego i poszukując w jego pobliżu mniejszej (niż poprzednia) wartości funkcji celu, zmierzają do minimum. Poszukiwanie takie uzależnione jest od obranego punktu startowego i nie zawsze kończy się w minimum globalnym. Algorytmy globalnej optymalizacji ukierunkowane są na zwiększenie prawdopodobieństwa osiągnięcia minimum globalnego. Wykorzystywane są w tym celu różne metody stochastyczne. Metody globalne nie gwarantują uzyskania rozwiązania optymalnego, jednak prawdopodobieństwo błędu można uczynić bardzo małym.

W metodach optymalizacji globalnej obliczane są wartości funkcji celu dla pewnego zestawu stochastycznie wybranych punktów - różne metody to różne strategie doboru zestawu punktów. Skuteczność konkretnej metody zależy od właściwości danej funkcji celu, dlatego nie można mówić o metodach globalnej optymalizacji ogólnego zastosowania. Metoda i jej parametry muszą być dopasowane do specyfiki problemu.

Podstawowe metody optymalizacji

Metoda grupowania


Tradycyjnie minimum globalne może być wyznaczone poprzez: 1) wybór wielkiej liczby lokalizacji punktów startowych i 2) rozpoczęcie poszukiwań dla każdego z punktów startowych. Jednak niektóre spośród punktów startowych mogą prowadzić do tego samego minimum lokalnego. Oznacza to, że te same obszary mogą być wielokrotnie przeszukiwane. Liczba oszacowań funkcji celu będzie wówczas bardzo duża.

Metoda grupowania identyfikuje zgrupowania punktów wokół minimów FC. Dla przypadkowo wybranych lokalizacji początkowych, poszukuje się minimów lokalnych. Po kilku iteracjach lokalizacje minimów zaznaczają się jako zgrupowania. Zgrupowania te zostają rozdzielone w taki sposób, że każdy ich punkt zostaje zaliczony do klasy reprezentowanej przez najbliższy punkt centralny. W ten sposób zostaje zredukowana liczba poszukiwań w tych samych obszarach. Następnie minima lokalne są klasyfikowane według odpowiednich algorytmów a ich punkty centralne są uaktualniane w kolejnym kroku optymalizacji.


Metoda symulowanego wyżarzania


Minimalizacja z zastosowaniem symulowanego wyżarzania jest często przeprowadzana przy użyciu symulacji Metropolis będącej narzędziem statystyki fizycznej. W każdym cyklu obliczana jest wartość funkcji celu w pewnym, przypadkowo wybranym punkcie. Jeśli otrzymana wartość jest mniejsza od poprzedniej, punkt zostaje bezwarunkowo zaakceptowany. Jeśli jednak nowa wartość jest większa od poprzedniej, badany punkt zostaje zaakceptowany z prawdopodobieństwem P zależnym od zmiany wielkości funkcji celu ER oraz zależnym od parametru T:

.

Im mniejsza jest wartość T, tym mniejsza jest szansa zaakceptowania nowego punktu. Podczas wykonywania algorytmu wartość parametru sterującego T jest stopniowo obniżana. Przy pewnej, małej wartości T, faktycznie nie są już akceptowane żadne zmiany i algorytm zatrzymuje się.



Algorytmy genetyczne

Idea algorytmów genetycznych polega na naśladowaniu ewolucji gatunków. Każda z potencjalnie możliwych lokalizacji jest przedstawiana w postaci binarnej sekwencji zwanej chromosomem. Chromosomy mogą podlegać mutacji, krzyżowaniu lub selekcji tworząc w ten sposób potomstwo.

Każdy chromosom reprezentuje potencjalne rozwiązanie zadania. Proces ewolucji rozwiązań odpowiada przeszukiwaniu przestrzeni potencjalnych rozwiązań. Takie przeszukiwanie wymaga pogodzenia dwóch celów. Z jednej strony należy możliwie gruntownie przebadać przestrzeń potencjalnych rozwiązań, z drugiej strony warto skorzystać z najlepszych rozwiązań dotychczasowych. Algorytmy genetyczne umożliwiają utrzymanie równowagi pomiędzy szerokim badaniem przestrzeni a wykorzystaniem wcześniejszych wyników. Polegają one na wielokierunkowym przeszukiwaniu przestrzeni przez przekształcanie populacji potencjalnych rozwiązań. W każdym następnym pokoleniu dobre rozwiązania są reprodukowane, a złe „wymierają”. Aby rozróżnić rozwiązania dobre od złych używa się funkcji celu. W każdej następnej populacji znajdą się osobniki lepsze, zgodnie z funkcją celu. Osobniki gorsze podlegają eliminacji.

Niektóre elementy tej nowej populacji podlegają zmianom za pomocą krzyżowania i mutacji, tworząc w ten sposób nowe rozwiązania. Krzyżowanie prowadzi do połączenia cech rodzicielskich chromosomów w chromosomach dwóch potomków przez wymianę odcinków.

Np.: jeśli rodzice reprezentowani są przez wektory i , to przykładowe krzyżowanie po trzecim genie da potomków: i . Mutacja polega na losowej zmianie genów wybranego chromosomu, z prawdopodobieństwem równym częstości mutacji. Operator mutacji wprowadza dodatkowy element zmienności w populacji. Algorytm genetyczny, dla każdego indywidualnego zadania, składa się z następujących elementów:


  • Podstawowa reprezentacja potencjalnych rozwiązań zadania.

  • Sposób tworzenia początkowej populacji potencjalnych rozwiązań.

  • Funkcja celu (funkcja oceniająca), która ocenia rozwiązania.

  • Podstawowe operatory genetyczne (mutacja, krzyżowanie eliminacja), które wpływają na skład populacji potomków.

Inne parametry niezbędne do działania algorytmów genetycznych, np.: rozmiar populacji, prawdopodobieństwo użycia poszczególnych operatorów genetycznych, inne.



2016-06-18




©snauka.pl 2016
wyślij wiadomość