Optymalizacja stochastyczna - Stochastic optimization
Metody optymalizacji stochastycznej ( SO ) to metody optymalizacji , które generują i wykorzystują zmienne losowe . W przypadku problemów stochastycznych zmienne losowe pojawiają się w sformułowaniu samego problemu optymalizacji, który obejmuje losowe funkcje celu lub losowe ograniczenia. Metody optymalizacji stochastycznej obejmują również metody z losowymi iteracjami. Niektóre metody optymalizacji stochastycznej wykorzystują losowe iteracje do rozwiązywania problemów stochastycznych, łącząc oba znaczenia optymalizacji stochastycznej. Stochastyczne metody optymalizacji uogólniać deterministycznych metod deterministycznych problemów.
Metody dla funkcji stochastycznych
Częściowo losowe dane wejściowe powstają w takich obszarach, jak estymacja i sterowanie w czasie rzeczywistym, optymalizacja oparta na symulacji, w której symulacje Monte Carlo są uruchamiane jako oszacowania rzeczywistego systemu, oraz problemy, w których występuje błąd eksperymentalny (losowy) w pomiarach kryterium. W takich przypadkach wiedza, że wartości funkcji są zanieczyszczone przez losowy „szum” prowadzi w naturalny sposób do algorytmów wykorzystujących narzędzia wnioskowania statystycznego do oszacowania „prawdziwych” wartości funkcji i/lub podejmowania statystycznie optymalnych decyzji dotyczących kolejnych kroków. Metody tej klasy obejmują:
- przybliżenie stochastyczne (SA), Robbins i Monro (1951)
- stochastyczne zejście gradientowe
- różnica skończona SA Kiefera i Wolfowitza (1952)
- równoczesna perturbacja SA Spalla (1992)
- optymalizacja scenariusza
Randomizowane metody wyszukiwania
Z drugiej strony, nawet jeśli zbiór danych składa się z precyzyjnych pomiarów, niektóre metody wprowadzają losowość do procesu wyszukiwania, aby przyspieszyć postęp. Taka losowość może również zmniejszyć wrażliwość metody na błędy modelowania. Co więcej, wstrzyknięta losowość może umożliwić metodzie uniknięcie lokalnego optimum i ostatecznie zbliżenie się do globalnego optimum. Rzeczywiście, wiadomo , że ta zasada randomizacji jest prostym i skutecznym sposobem uzyskania algorytmów z prawie pewną dobrą wydajnością jednolicie w wielu zestawach danych, dla wielu rodzajów problemów. Tego rodzaju stochastyczne metody optymalizacji obejmują:
- symulowane wyżarzanie S. Kirkpatrick, CD Gelatt i MP Vecchi (1983)
- wyżarzanie kwantowe
- Kolektywy prawdopodobieństwa DH Wolperta, SR Bieniawskiego i DG Rajnarayan (2011)
- reaktywny optymalizacja wyszukiwania (RSO) przez Roberto Battiti , G. Tecchiolli (1994), ostatnio przeglądowi w książce
- metoda entropii krzyżowej Rubinsteina i Kroese (2004)
- losowo wyszukiwania przez Anatolija Zhigljavsky (1991)
- Wyszukiwanie informacji
- tunelowanie stochastyczne
- hartowanie równoległe, czyli wymiana replik
- stochastyczna wspinaczka górska
- algorytmy roju
-
algorytmy ewolucyjne
- algorytmy genetyczne według Hollanda (1975)
- strategie ewolucji
- algorytm optymalizacji i modyfikacji obiektów kaskadowych (2016)
W przeciwieństwie do tego, niektórzy autorzy twierdzili, że randomizacja może poprawić algorytm deterministyczny tylko wtedy, gdy algorytm deterministyczny został na początku źle zaprojektowany. Fred W. Glover twierdzi, że poleganie na elementach losowych może uniemożliwić rozwój bardziej inteligentnych i lepiej deterministycznych komponentów. Sposób, w jaki zwykle przedstawiane są wyniki algorytmów optymalizacji stochastycznej (np. prezentowanie tylko średniej lub nawet najlepszej z N przebiegów bez wzmianki o rozkładzie), może również skutkować pozytywnym nastawieniem na losowość.
Zobacz też
- Optymalizacja globalna
- Nauczanie maszynowe
- Optymalizacja scenariusza
- Proces Gaussa
- Model przestrzeni stanów
- Modelowa kontrola predykcyjna
- Programowanie nieliniowe
- Wartość entropiczna zagrożona
Bibliografia
Dalsza lektura
- Michalewicz, Z. i Fogel, DB (2000), How to Solve It: Modern Heuristics , Springer-Verlag, New York.
- „ PSA: Nowatorski algorytm optymalizacji oparty na regułach przetrwania porcellio scaber ”, Y. Zhang i S. Li