Stopniowa optymalizacja
Stopniowana optymalizacja to globalna technika optymalizacji , która próbuje rozwiązać trudny problem optymalizacji, początkowo rozwiązując znacznie uproszczony problem i stopniowo przekształcając ten problem (podczas optymalizacji), aż stanie się równoważny trudnemu problemowi optymalizacji.
Opis techniki
Stopniowa optymalizacja to ulepszenie wspinaczki górskiej , które umożliwia wspinaczowi uniknięcie osiadania w lokalnych optymach. Rozbija trudny problem optymalizacyjny na sekwencję problemów optymalizacyjnych w taki sposób, że pierwszy problem w sekwencji jest wypukły (lub prawie wypukły), rozwiązanie każdego problemu daje dobry punkt wyjścia do następnego problemu w sekwencji, a ostatni problemem w sekwencji jest trudny problem optymalizacyjny, który ostatecznie stara się rozwiązać. Często stopniowa optymalizacja daje lepsze rezultaty niż zwykła wspinaczka górska. Ponadto, gdy istnieją pewne warunki, można wykazać, że można znaleźć optymalne rozwiązanie końcowego problemu w sekwencji. Te warunki to:
- Pierwszy problem optymalizacyjny w sekwencji można rozwiązać, biorąc pod uwagę początkowy punkt początkowy.
- Lokalnie wypukły region wokół globalnego optimum każdego problemu w sekwencji zawiera punkt, który odpowiada globalnemu optimum poprzedniego problemu w sekwencji.
Można wykazać indukcyjnie, że jeśli te warunki są spełnione, to alpinista osiągnie globalne optimum dla trudnego problemu. Niestety znalezienie sekwencji problemów optymalizacyjnych spełniających te warunki może być trudne. Stopniowa optymalizacja często daje dobre wyniki, nawet jeśli nie można udowodnić, że sekwencja problemów ściśle spełnia wszystkie te warunki.
Kilka przykładów
Stopniowana optymalizacja jest powszechnie stosowana w przetwarzaniu obrazu do lokalizowania obiektów na większym obrazie. Problem ten można uczynić bardziej wypukłym , rozmywając obrazy. W ten sposób obiekty można znaleźć, najpierw przeszukując najbardziej rozmyty obraz, a następnie rozpoczynając od tego punktu i przeszukując mniej rozmyty obraz, i kontynuując w ten sposób, aż obiekt zostanie precyzyjnie zlokalizowany na oryginalnym ostrym obrazie. Właściwy wybór operatora rozmycia zależy od transformacji geometrycznej wiążącej obiekt na jednym obrazie z drugim.
Stopniowana optymalizacja może być wykorzystana w wielorakim uczeniu się. Na przykład algorytm Manifold Sculpting wykorzystuje stopniowaną optymalizację do poszukiwania osadzania rozmaitości w celu nieliniowej redukcji wymiarowości . Stopniowo skaluje wariancję z dodatkowych wymiarów w zbiorze danych, jednocześnie optymalizując pozostałe wymiary. Był również używany do obliczania warunków frakcjonowania z guzami, do śledzenia obiektów w wizji komputerowej i do innych celów.
Dokładny przegląd metody i jej zastosowań można znaleźć w.
Powiązane techniki optymalizacji
Symulowane wyżarzanie jest ściśle związane ze stopniowaną optymalizacją. Zamiast wygładzać funkcję, którą optymalizuje, symulowane wyżarzanie losowo zaburza bieżące rozwiązanie o zanikającą ilość, co może mieć podobny efekt. [ Potrzebne źródło ] Ponieważ symulowane wyżarzanie polega na losowym próbkowaniu w celu znalezienia ulepszeń, jego złożoność obliczeniowa jest wykładnicza w liczbie optymalizowanych wymiarów. [ potrzebne źródło ] Z kolei stopniowa optymalizacja wygładza optymalizowaną funkcję, więc nadal można stosować lokalne techniki optymalizacji, które są wydajne w przestrzeni wielowymiarowej (takie jak techniki oparte na gradiencie, pokonywanie wzniesień itp.).