Losowe optymalizacja - Random optimization

Losowo optymalizacji (RO) to rodzina numerycznych optymalizacji metod, które nie wymagają gradientu od problemu, który ma być optymalizowane i RO może wówczas być używany w funkcji, które nie są ciągłe lub różniczkowalną . Takie metody optymalizacji są również znane jako metody bezpośredniego wyszukiwania, pochodnych wolnych lub czarnej skrzynki.

Nazwa optymalizacja losowo przypisuje się Matyas, która dokonała wcześniejszej prezentacji RO wraz z podstawowej analizy matematycznej. RO działa poprzez iteracyjne przeprowadzce do lepszych stanowisk w poszukiwaniu miejsca, które są próbą używając np rozkładu normalnego wokół aktualnej pozycji.

Algorytm

Niech f : ℝ ⁿ  → ℝ być funkcja fitness lub koszty, które muszą być zminimalizowane. Niech x  ∈ ℝ ⁿ wyznaczyć stanowiska lub rozwiązania kandydatem w wyszukiwarce przestrzeni. Podstawowy algorytm RO może być opisany jako:

• Zainicjować X z dowolnej pozycji w poszukiwaniu miejsca.
• Aż do zakończenia kryterium jest spełnione (np liczba iteracji wykonywana, lub odpowiednie fitness osiągnięta), powtórz czynności:
  • Próbki w nowe położenie Y przez dodanie zwykle rozproszony losowy wektor do aktualnego położenia X
  • Jeśli ( F ( r ) <  f ( x )), a następnie poruszać się w nowe położenie, ustawiając x  =  y
• Teraz x posiada najlepiej znaleźć pozycję.

Algorytm ten odpowiada (1 + 1) strategii wydzielania ze stałym kroku wielkości.

Konwergencja i warianty

Matyas wykazała, że podstawowa forma RO zbieżny do optimum prostej funkcji jednomodalnego przy użyciu graniczną odporne na co wskazuje konwergencję optymalna jest pewna czy potencjalnie nieskończonej liczby iteracji są wykonywane. Jednak ten dowód nie jest przydatna w praktyce, ponieważ skończona liczba iteracji może być wykonane tylko. W rzeczywistości takie teoretyczna granica odporne również wykazują, że jedynie próbkowanie losowe poszukiwanie przestrzeni pewnością uzyskać próbkę dowolnie blisko optimum.

Analiz matematycznych są prowadzone przez Baba i Solis zwilża się ustalić, że zbieżność do obszaru otaczającego optimum nieuniknione w niektórych łagodnych warunkach za pomocą innych wariantów RO rozkład prawdopodobieństwa dla próbek. Oszacowanie liczby iteracji potrzebne podejście do optimum mająca Dorea. Analizy te są krytykowane przez doświadczeniach empirycznych przez Sarma, którzy korzystali z wariantów optymalizatora Baba i Dorea na dwóch rzeczywistych problemów, pokazując optimum należy podchodzić bardzo powoli, a ponadto, że metody są rzeczywiście w stanie zlokalizować roztwór odpowiedniej sprawności, chyba proces rozpoczął się wystarczająco blisko optimum na początku.

Zobacz też

• Losowe wyszukiwania jest ściśle związane z metodami, które rodzina próbki z optymalizacji hypersphere zamiast rozkładu normalnego.
• Luus-Jaakola jest ściśle związane z użyciem metody optymalizacji równomiernego rozkładu w jej pobierania i prosty wzór na wykładniczo maleje zakres próbkowania.
• Szukaj wzór podejmuje kroki wzdłuż osi wyszukiwania z wykorzystaniem przestrzeni gwałtownie malejących rozmiarach kroku.
• Stochastic optymalizacja

Referencje