Metody rozwiązywania zadao optymalizacji

Podstawowy schemat myślenia gdy natrafiamy na problem optymalizacji przebiega mniej więcej w
ten sposób: Sformułowanie problemu -> utworzenie funkcji celu -> dodanie ograniczeo ->
klasyfikacja zadania.

Istnieje wiele współczesnych metod optymalizacji, a dla różnych zadao jest wymyślane coraz więcej
wyspecjalizowanych algorytmów. Chciałbym jednak się skupid na bardziej ogólnych strategiach
projektowania algorytmów które potem są wykorzystywane do stworzenia algorytmów które
rozwiązują konkretne przykłady.



Algorytmy numeryczne - Obliczenie numeryczne są najważniejszym zastosowaniem
komputerów równoległych. Przykładem są symulacje zjawisk fizycznych, których
przeprowadzenie sprowadza się do rozwiązania układu równao różniczkowych cząstkowych.
Z kolei przybliżone rozwiązanie układu równao różniczkowych cząstkowych jest znajdywane
poprzez rozwiązanie układu równao liniowych. Konkretnymi algorytmami numerycznymi są
na przykład : metoda Newtona jest to algorytm numeryczny mający na celu
znalezienie minimum zadanej funkcji celu., lub Metoda Halleya – algorytm wyznaczania
przybliżonej wartości pierwiastka funkcji y = f(x) jednej zmiennej w zadanym przedziale [a,b].



Przeszukiwanie wyczerpujące - czyli sprawdzenie każdego rozwiązania z przestrzeni
rozwiązao zaletą jest to że na pewno znajdziemy rozwiązanie optymalne, natomiast wadą
jest najczęściej duża przestrzeo rozwiązao która powoduje znaczną czasochłonnośd



Przeszukiwanie lokalne – przeszukiwanie części przestrzeni rozwiązao w otoczeniu
konkretnego rozwiązania, dzięki temu mamy mniejszą czasochłonnośd szczególnie jeśli
rozmiar otoczenia jest niewielki wtedy możemy je bardzo szybko przeszukad minusem tego
sposobu jest „pułapka” lokalnego optimum



Programowanie liniowe- to klasa problemów programowania matematycznego, w której
wszystkie warunki ograniczające oraz funkcja celu mają postad liniową. np. Algorytm
Sympleksowy inaczej metoda sympleks(ów) to stosowana w matematyce iteracyjna metoda
rozwiązywania zadao programowania liniowego za pomocą kolejnego polepszania
(optymalizacji) rozwiązania. Nazwa metody pochodzi od sympleksu, figury wypukłej będącej
uogólnieniem trójkąta na więcej wymiarów.



Teoria programowania nieliniowego jest to przypadek programowania matematycznego, w
którym funkcja celu bądź ograniczenia są funkcjami nieliniowymi np. Zagadnienie wyboru
optymalnego portfela akcji



Programowanie dynamiczne jest alternatywą dla niektórych zagadnieo rozwiązywanych za
pomocą algorytmów zachłannych Programowanie dynamiczne opiera się na podziale
rozwiązywanego problemu na pod problemy względem kilku parametrów. W odróżnieniu od
techniki dziel i zwyciężaj pod problemy w programowaniu dynamicznym nie są na ogół
rozłączne, ale musi je cechowad własnośd optymalnej podstruktury. Programowanie

dynamiczne jest jedną z bardziej skutecznych technik rozwiązywania problemów NP-
trudnych. Niejednokrotnie może byd z sukcesem stosowana do względnie dużych
przypadków problemów wejściowych, o ile stałe występujące w problemie są stosunkowo
nieduże. Na przykład, w przypadku dyskretnego zagadnienia plecakowego jako parametry
dynamiczne w metodzie programowania dynamicznego należy przyjąd rozmiar kolejno
rozpatrywanych podzbiorów elementów oraz rozmiar plecaka, zmieniający się od 0 do
wartości B danej w problemie.



Algorytmy zachłanne- tworzą one pełne rozwiązanie za pomocą ciągu kroków, istotną zaletą
jest prostota tych algorytmów, wystarczy przypisywad wartości wszystkim zmiennym
problemu podejmując za każdym razem możliwie najlepszą decyzje, niestety podejmowanie
najlepszej decyzji w poszczególnych krokach nie zawsze prowadzi do decyzji najlepszej



Ogólnie metody działające na rozwiązaniach niepełnych w wąskim zakresie umożliwiają
szybki i wiarygodne znalezienie rozwiązania globalnego , natomiast metody operujące na
pełnych rozwiązaniach gwarantują osiągnięcie sukcesu w poszukiwaniach lecz najczęściej
odbywa się to kosztem zwiększonego czasu działania. Stąd też próby stworzenia takich
algorytmów które unikają pułapki minimum lokalnego . Przykładem takich algorytmów może
byd symulowane wyżarzanie lub poszukiwanie z tabu. Wyżarzanie jest podobne do
przeszukiwania lokalnego jednakże wprowadza się tam dodatkowy parametr zwany
temperaturą, który zmienia prawdopodobieostwo przejścia z jednego punktu do drugiego,
algorytm kooczy przeszukiwanie po spełnieniu warunku zakooczenia a nie znalezienia
ulepszenia ostatniego punktu. Poszukiwanie z tabu : algorytm o podobnej strukturze co
wyżarzanie jednakże korzysta z historii przeszukiwania w której ostatnie punkty są punktami
tabu i są pomijane przy podejmowaniu kolejnych decyzji.



Softcomputing metody „odporne” np. algorytmy ewolucyjne które przeszukują przestrzeo
alternatywnych rozwiązao problemu w celu odnalezienia rozwiązao najlepszych lub
potencjalnie najlepszych. Zalicza się je do klasy algorytmów heurystycznych. Przeszukiwanie
odbywa się za pomocą mechanizmów ewolucji oraz doboru naturalnego. W praktyce te
słowa oznaczają, że wykorzystujemy ewolucję, aby poprzez krzyżowanie i mutacje stworzyd z
grupy losowych zestawów danych to, co nas będzie satysfakcjonowad. Pierwszy algorytm
ewolucyjny został zaproponowany przez Johna Hollanda w 1975 roku, który bardzo
interesował się biologią i często czerpał z niej inspirację w swych pracach informatycznych.
Do metod odpornych zaliczamy także sieci neuronowe czyli struktury matematyczne i ich
programowe lub sprzętowe modele, realizujące obliczenia lub przetwarzanie
sygnałów poprzez rzędy elementów, zwanych sztucznymi neuronami, wykonujących pewną
podstawową operację na swoim wejściu. Oryginalną inspiracją takiej struktury była
budowa naturalnych neuronów oraz układów nerwowych, w szczególności mózgu.

Istnieje dużo dziedzin w których jest wykorzystywana optymalizacja:



Badania kosmiczne: optymalizacja konstrukcji rakiet, problemy sterowania lotem w
stratosferze i w kosmosie.



Optymalizacja procesów ekonomicznych: problemy alokacji produkcji, optymalny skład
portfela inwestycyjnego.



Problemy logistyki.



Optymalizacja wykorzystywania pamięci