Wyszukiwanie wzorców (optymalizacja)

Przykład zbieżności metody przeszukiwania bezpośredniego na funkcji Broydena. W każdej iteracji wzorzec albo przesuwa się do punktu, który najlepiej minimalizuje jego funkcję celu, albo zmniejsza się, jeśli żaden punkt nie jest lepszy niż bieżący punkt, aż do osiągnięcia pożądanej dokładności lub osiągnięcia przez algorytm określonej liczby iteracji.

Wyszukiwanie wzorców (znane również jako wyszukiwanie bezpośrednie, wyszukiwanie bez pochodnych lub wyszukiwanie metodą czarnej skrzynki) to rodzina numerycznych metod optymalizacji , które nie wymagają gradientu . W rezultacie można go używać w przypadku funkcji, które nie są ciągłe ani różniczkowalne . Jedną z takich metod wyszukiwania wzorców jest „zbieżność” (patrz poniżej), która opiera się na teorii dodatnich baz. Optymalizacja próbuje znaleźć najlepsze dopasowanie (rozwiązanie, które ma najniższą wartość błędu) w wielowymiarowej przestrzeni analizy możliwości.

Historia

Nazwa „wyszukiwanie wzorców” została wymyślona przez Hooke'a i Jeevesa. Wczesny i prosty wariant przypisuje się Fermiemu i Metropolisowi , kiedy pracowali w Los Alamos National Laboratory . Jest to opisane przez Davidona w następujący sposób:

Zmieniali jeden teoretyczny parametr na raz krokami o tej samej wielkości, a kiedy żaden taki wzrost lub spadek żadnego parametru nie poprawił dalej dopasowania do danych eksperymentalnych, zmniejszyli o połowę wielkość kroku i powtarzali proces, aż kroki zostały uznane za wystarczające mały.

Konwergencja

Konwergencja to metoda wyszukiwania wzorców zaproponowana przez Yu, który udowodnił, że jest ona zbieżna za pomocą teorii dodatnich baz. Później Torczon , Lagarias i współautorzy wykorzystali techniki pozytywnej podstawy, aby udowodnić zbieżność innej metody wyszukiwania wzorców na określonych klasach funkcji. Poza takimi klasami wyszukiwanie wzorców jest heurystyką , która może zapewnić przydatne przybliżone rozwiązania niektórych problemów, ale może zawieść w przypadku innych. Poza takimi klasami wyszukiwanie wzorców nie jest metodą iteracyjną która zbiega się do rozwiązania; w rzeczywistości metody wyszukiwania wzorców mogą zbiegać się do niestacjonarnych punktów w przypadku niektórych stosunkowo oswojonych problemów.

Zobacz też

Wyszukiwanie według złotego podziału koncepcyjnie przypomina PS w zawężaniu zakresu wyszukiwania, tylko dla jednowymiarowych przestrzeni wyszukiwania.
metoda Neldera-Meada . metoda simplex koncepcyjnie przypomina PS w zawężeniu zakresu poszukiwań dla wielowymiarowych przestrzeni poszukiwań, ale robi to przez zachowanie n + 1 punktów dla n -wymiarowych przestrzeni poszukiwań, podczas gdy metody PS obliczają 2 n + 1 punkty (punkt centralny i 2 punktów w każdym wymiarze).
Luus-Jaakola pobiera próbki z jednolitego rozkładu otaczającego bieżącą pozycję i używa prostej formuły do wykładniczego zmniejszania zakresu próbkowania.
Wyszukiwanie losowe to pokrewna rodzina metod optymalizacyjnych pobierających próbki z hipersfery otaczającej bieżącą pozycję.
Optymalizacja losowa to pokrewna rodzina metod optymalizacyjnych, które próbkują z rozkładu normalnego otaczającego bieżącą pozycję.