Luus–Jaakola

W inżynierii obliczeniowej Luus – Jaakola (LJ) oznacza heurystykę globalnej optymalizacji funkcji o wartościach rzeczywistych. W zastosowaniach inżynierskich LJ nie jest algorytmem , który kończy się rozwiązaniem optymalnym; nie jest to też metoda iteracyjna który generuje sekwencję punktów, która zbiega się do rozwiązania optymalnego (jeśli takie istnieje). Jednak w przypadku zastosowania do funkcji różniczkowalnej dwukrotnie w sposób ciągły, heurystyka LJ jest właściwą metodą iteracyjną, która generuje sekwencję, która ma zbieżny podciąg; dla tej klasy problemów metoda Newtona, która charakteryzuje się kwadratowym współczynnikiem zbieżności, podczas gdy dla heurystyki LJ nie podano analizy współczynnika zbieżności. W praktyce heurystyka LJ była zalecana dla funkcji, które nie muszą być ani wypukłe , ani różniczkowalne , ani lokalnie Lipschitza : Heurystyka LJ nie wykorzystuje gradientu ani podgradientu , jeśli taki jest dostępny, co pozwala na jej zastosowanie do problemów nieróżniczkowalnych i niewypukłych.

Zaproponowany przez Luusa i Jaakolę, LJ generuje sekwencję iteracji. Następna iteracja jest wybierana z próbki z sąsiedztwa bieżącej pozycji przy użyciu rozkładu jednolitego . Z każdą iteracją sąsiedztwo maleje, co zmusza podsekwencję iteracji do zbieżności do punktu skupienia.

Luus zastosował LJ w optymalnym sterowaniu , projektowaniu transformatorów , procesach metalurgicznych i inżynierii chemicznej .

Motywacja

Gdy bieżąca pozycja x jest daleka od optymalnej, prawdopodobieństwo znalezienia poprawy przez równomierne losowanie wynosi 1/2.
Gdy zbliżamy się do optimum, prawdopodobieństwo znalezienia dalszych ulepszeń poprzez jednolite próbkowanie spada do zera, jeśli zakres próbkowania d jest stały.

Na każdym kroku heurystyka LJ utrzymuje pudełko, z którego losowo próbkuje punkty, stosując równomierny rozkład na pudełku. W przypadku funkcji unimodalnej prawdopodobieństwo redukcji funkcji celu maleje, gdy pudełko zbliża się do minimum. Obraz przedstawia jednowymiarowy przykład.

Heurystyczny

Niech f : ℝ n → ℝ będzie funkcją przydatności lub kosztu, którą należy zminimalizować. Niech x ∈ ℝ n oznacza pozycję lub rozwiązanie kandydujące w przestrzeni poszukiwań. Heurystyka LJ obejmuje następujące kroki:

  • Zainicjuj x ~ U ( b lo , b up ) losową jednolitą pozycją w przestrzeni poszukiwań, gdzie b lo i b up są odpowiednio dolną i górną granicą.
  • Ustaw początkowy zakres próbkowania tak, aby obejmował całą przestrzeń poszukiwań (lub jej część): d = b up − b lo
  • Dopóki nie zostanie spełnione kryterium zakończenia (np. liczba wykonanych iteracji lub osiągnięcie odpowiedniej sprawności), powtarzaj następujące czynności:
    • Wybierz losowy wektor a ~ U (− d , d )
    • Dodaj to do bieżącej pozycji x , aby utworzyć nową potencjalną pozycję y = x + a
    •   Jeśli ( f ( y ) < f ( x )) następnie przejdź do nowej pozycji, ustawiając x = y , w przeciwnym razie zmniejsz zakres próbkowania: d = 0,95 d
  • Teraz x zajmuje najlepiej znalezioną pozycję.

Wariacje

Luus zauważa, że ​​proponowane dotychczas algorytmy ARS (Adaptive Random Search) różnią się pod wieloma względami.

  • Procedura generowania losowych punktów próbnych.
  • Liczba pętli wewnętrznych (NIL, liczba losowych punktów wyszukiwania w każdym cyklu).
  • Liczba cykli (NEL, liczba pętli zewnętrznych).
  • Współczynnik skrócenia rozmiaru obszaru wyszukiwania. (Niektóre przykładowe wartości to od 0,95 do 0,60).
    • Czy współczynnik redukcji regionu jest taki sam dla wszystkich zmiennych, czy inny dla każdej zmiennej (nazywany algorytmem M-LJ).
    • Czy tempo redukcji obszaru jest stałe, czy ma inny rozkład (np. Gaussa).
  • Czy włączyć wyszukiwanie liniowe.
  • Czy rozważyć ograniczenia losowych punktów jako kryteria akceptacji, czy też uwzględnić karę kwadratową.

Konwergencja

Nair udowodnił analizę konwergencji. Dla funkcji dwukrotnie różniczkowalnych w sposób ciągły heurystyka LJ generuje sekwencję iteracji o zbieżnym podsekwencji. Dla tej klasy problemów metoda Newtona jest zwykłą metodą optymalizacji i ma zbieżność kwadratową ( niezależnie od wymiaru przestrzeni, która według analizy Kantorowicza może być przestrzenią Banacha ).

Według analizy Judina i Niemirowskiego złożoność minimalizacji w najgorszym przypadku w klasie funkcji unimodalnych rośnie wykładniczo w wymiarze problemu. Analiza Yudina-Nemirowskiego sugeruje, że żadna metoda nie może być szybka w przypadku problemów wielowymiarowych pozbawionych wypukłości:

„Katastrofalny wzrost [liczby iteracji potrzebnych do osiągnięcia przybliżonego rozwiązania o danej dokładności] wraz ze wzrostem [liczby wymiarów do nieskończoności] pokazuje, że nie ma sensu stawiać pytania o konstruowanie uniwersalnych metod rozwiązywania… problemów jakiejkolwiek znaczącej wymiarowości „ogólnie”. Warto zauważyć, że ten sam [wniosek] odnosi się do… problemów generowanych przez funkcje uni-extremal [to znaczy unimodalne] (ale nie wypukłe).

W przypadku zastosowania do problemów dwukrotnie różniczkowalnych w sposób ciągły, współczynnik zbieżności heurystyki LJ maleje wraz ze wzrostem liczby wymiarów.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Luus–Jaakola&oldid=1059575312 ”