Losowe wyszukiwanie - Random search

Przeszukiwanie losowe (RS) to rodzina numerycznych metod optymalizacji , które nie wymagają optymalizacji gradientu problemu, a zatem RS może być stosowany do funkcji, które nie są ciągłe lub różniczkowalne . Takie metody optymalizacji są również znane jako metody wyszukiwania bezpośredniego, metody bez pochodnych lub metody czarnej skrzynki.

Nazwa „wyszukiwanie losowe” jest przypisywana Rastriginowi, który dokonał wczesnej prezentacji RS wraz z podstawową analizą matematyczną. RS działa poprzez iteracyjne przechodzenie do lepszych pozycji w przestrzeni wyszukiwania, które są próbkowane z hipersfery otaczającej bieżącą pozycję.

Algorytm tu opisany jest rodzajem lokalnego wyszukiwania losowego, w którym każda iteracja zależy od rozwiązania kandydata z poprzedniej iteracji. Istnieją alternatywne metody wyszukiwania losowego, które próbkują z całej przestrzeni wyszukiwania (na przykład czyste wyszukiwanie losowe lub jednolite globalne wyszukiwanie losowe), ale nie są one opisane w tym artykule.

Algorytm

Niech f : ℝ ⁿ  → ℝ będzie funkcją przydatności lub kosztu, którą należy zminimalizować. Niech x  ∈ ℝ ⁿ oznacza pozycję lub rozwiązanie kandydata w przestrzeni poszukiwań. Podstawowy algorytm RS można zatem opisać jako:

1. Zainicjuj x z losową pozycją w przestrzeni wyszukiwania.
2. Do momentu spełnienia kryterium zakończenia (np. Liczby wykonanych iteracji lub osiągnięcia odpowiedniej sprawności), powtarzaj następujące czynności:
   1. Wypróbuj nową pozycję y z hipersfery o podanym promieniu otaczającej bieżącą pozycję x (zobacz np . Technikę Marsaglii do pobierania próbek hipersfery).
   2. Jeśli f ( y ) <  f ( x ), przejdź do nowej pozycji, ustawiając x  =  y

Warianty

W literaturze wprowadzono szereg wariantów RS:

• Wyszukiwanie losowe o ustalonym rozmiarze kroku (FSSRS) to podstawowy algorytm Rastrigina, który pobiera próbki z hipersfery o stałym promieniu.
• Optimum Step Size Random Search (OSSRS) autorstwa Schumera i Steiglitza to przede wszystkim teoretyczne badanie, w jaki sposób optymalnie dostosować promień hipersfery, aby umożliwić szybką zbieżność do optimum. Rzeczywista implementacja OSSRS wymaga przybliżenia tego optymalnego promienia przez wielokrotne próbkowanie i dlatego jest kosztowna w wykonaniu.
• Adaptive Step Size Random Search (ASSRS) autorstwa Schumera i Steiglitza próbuje heurystycznie dostosować promień hipersfery: generowane są dwa nowe rozwiązania kandydatów, jedno z bieżącym nominalnym rozmiarem kroku i jedno z większym krokiem. Większy krok staje się nowym nominalnym rozmiarem kroku wtedy i tylko wtedy, gdy prowadzi do większej poprawy. Jeśli przez kilka iteracji żaden z kroków nie prowadzi do poprawy, nominalny rozmiar kroku jest zmniejszany.
• Zoptymalizowane wyszukiwanie losowe względnego rozmiaru kroku (ORSSRS) firmy Schrack i Choit przybliża optymalny rozmiar kroku prostym wykładniczym zmniejszeniem. Jednak wzór na obliczenie współczynnika spadku jest nieco skomplikowany.

Zobacz też

• Optymalizacja losowa to blisko spokrewniona rodzina metod optymalizacyjnych, które próbują z rozkładu normalnego zamiast hipersfery.
• Luus-Jaakola to ściśle powiązana metoda optymalizacji wykorzystująca równomierny rozkład w próbkowaniu i prosty wzór na wykładnicze zmniejszanie zakresu próbkowania.
• Wyszukiwanie wzorców wykonuje kroki wzdłuż osi przestrzeni wyszukiwania przy użyciu wykładniczo malejących rozmiarów kroków.

Bibliografia