Metoda Neldera-Meada - Nelder–Mead method

Szukaj w funkcji bananów Rosenbrocka

Przeszukaj funkcję Himmelblau

Nelder-Mead minimalne przeszukiwanie funkcji Simionescu . Wierzchołki simpleksowe są uporządkowane według ich wartości, przy czym 1 ma najniższą (najlepszą) wartość.

Sposób Neldera-Mead (również w dół zwykłej metody , ameby metoda lub sposób Polytope ) jest powszechnie stosowane metody numeryczne wykorzystane do znalezienia minimum lub maksimum w funkcji celu w przestrzeni wielowymiarowej. Jest to metoda wyszukiwania bezpośredniego (oparta na porównaniu funkcji) i jest często stosowana do nieliniowych problemów optymalizacji , dla których pochodne mogą nie być znane. Jednak technika Neldera-Meada jest heurystyczną metodą wyszukiwania, która może zbiegać się do niestacjonarnych punktów problemów, które można rozwiązać metodami alternatywnymi.

Technika Neldera-Meada została zaproponowana przez Johna Neldera i Rogera Meada w 1965 roku jako rozwinięcie metody Spendleya i in.

Przegląd

Metoda wykorzystuje pojęcie simpleksu , który jest specjalnym politopem składającym się z n  + 1 wierzchołków w n wymiarach. Przykłady uproszczeń obejmują odcinek na linii, trójkąt na płaszczyźnie, czworościan w przestrzeni trójwymiarowej i tak dalej.

Metoda aproksymuje lokalne optimum problemu z n zmiennymi, gdy funkcja celu zmienia się płynnie i jest unimodalna . Typowe implementacje minimalizują funkcje, a my maksymalizujemy poprzez minimalizowanie . ${\displaystyle f(\mathbf {x} )}$${\displaystyle -f(\mathbf {x} )}$

Na przykład inżynier mostu wiszącego musi wybrać grubość każdej rozpórki, kabla i pirsu. Te elementy są współzależne, ale nie jest łatwo zwizualizować wpływ zmiany jakiegokolwiek konkretnego elementu. Symulacja takich skomplikowanych struktur jest często niezwykle kosztowna obliczeniowo, a wykonanie może zająć nawet więcej godzin. Metoda Neldera-Meada wymaga, w oryginalnym wariancie, nie więcej niż dwóch ocen na iterację, z wyjątkiem operacji zmniejszania opisanej później, która jest atrakcyjna w porównaniu z niektórymi innymi metodami optymalizacji bezpośredniego przeszukiwania. Jednak ogólna liczba iteracji do proponowanego optimum może być wysoka.

Nelder-Mead w n wymiarach utrzymuje zbiór n  + 1 punktów testowych ułożonych w simpleks . Następnie ekstrapoluje zachowanie funkcji celu mierzonej w każdym punkcie testowym, aby znaleźć nowy punkt testowy i zastąpić jeden ze starych punktów testowych nowym, dzięki czemu technika postępuje. Najprostszym podejściem jest zastąpienie najgorszego punktu punktem odbitym przez środek ciężkości pozostałych n punktów. Jeśli ten punkt jest lepszy niż najlepszy bieżący punkt, możemy spróbować rozciągać się wykładniczo wzdłuż tej linii. Z drugiej strony, jeśli ten nowy punkt nie jest dużo lepszy niż poprzednia wartość, to przechodzimy przez dolinę, więc zmniejszamy simpleks w kierunku lepszego punktu. Intuicyjne wyjaśnienie algorytmu z „Przepisów numerycznych”:

Metoda simpleksowa zstępująca obejmuje teraz serię kroków, większość kroków polega na przeniesieniu punktu simpleksu, w którym funkcja jest największa („najwyższy punkt”), przez przeciwną ścianę simpleksu do niższego punktu. Kroki te nazywane są odbiciami i są skonstruowane w celu zachowania objętości simpleksu (a tym samym zachowania jego niezdegeneracji). Kiedy może to zrobić, metoda rozszerza simpleks w jednym lub drugim kierunku, aby wykonać większe kroki. Kiedy dociera do „dna doliny”, metoda kurczy się w kierunku poprzecznym i próbuje przesiąkać w dół doliny. Jeśli występuje sytuacja, w której simpleks próbuje „przejść przez ucho igły”, kurczy się we wszystkich kierunkach, wciągając się wokół swojego najniższego (najlepszego) punktu.

W przeciwieństwie do nowoczesnych metod optymalizacji, heurystyka Neldera-Meada może zbiegać się do punktu niestacjonarnego, chyba że problem spełnia silniejsze warunki niż jest to konieczne dla nowoczesnych metod. Nowoczesne ulepszenia heurystyki Nelder-Mead są znane od 1979 roku.

Istnieje wiele odmian w zależności od rzeczywistego charakteru rozwiązywanego problemu. Popularny wariant wykorzystuje mały simpleks o stałym rozmiarze, który z grubsza podąża za kierunkiem gradientu (co daje najbardziej strome zejście ). Wizualizuj mały trójkąt na mapie wzniesień, przeskakujący w dół doliny do lokalnego dna. Metoda ta znana jest również jako metoda elastycznego wielościanu . To jednak ma słabe wyniki w porównaniu z metodą opisaną w tym artykule, ponieważ wykonuje małe, niepotrzebne kroki w obszarach mało interesujących.

Jedna z możliwych odmian algorytmu NM

(To przybliża procedurę z oryginalnego artykułu Nelder-Mead.)

Metoda Neldera-Meada zastosowana do funkcji Rosenbrocka

Staramy się zminimalizować funkcję , gdzie . Nasze obecne punkty testowe to . ${\displaystyle f(\mathbf {x} )}$${\ Displaystyle \ mathbf {x} \ w \ mathbb {R} ^ {n}}$${\ Displaystyle \ mathbf {x} _ {1} \ ldots \ mathbf {x} _ {n + 1}}$

1. Uporządkuj według wartości na wierzchołkach:

${\ Displaystyle f (\ mathbf {x} _ {1}) \ leq f (\ mathbf {x} _ {2}) \ leq \ cdots \ leq f (\ mathbf {x} _ {n + 1}). }$

Sprawdź, czy metoda powinna się zatrzymać. Zobacz Wypowiedzenie poniżej. Czasami niewłaściwie nazywany „konwergencją”.

2. Oblicz , środek ciężkości wszystkich punktów z wyjątkiem . ${\ Displaystyle \ mathbf {x} _ {o}}$${\ Displaystyle \ mathbf {x} _ {n + 1}}$

3. Odbicie

Oblicz punkt odbity za pomocą .${\ Displaystyle \ mathbf {x} _ {R} = \ mathbf {x} _ {o} + \ alfa (\ mathbf {x} _ {o} - \ mathbf {x} _ {n + 1})}$${\ Displaystyle \ alfa > 0}$

Jeśli odbicie punkt jest lepszy niż drugi najgorszy, ale nie lepsze niż najlepsze, czyli , ${\ Displaystyle f (\ mathbf {x} _ {1}) \ leq f (\ mathbf {x} _ {r}) < f (\ mathbf {x} _ {n})}$

następnie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem odbitym i przejdź do kroku 1.${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {r}}$

4. Ekspansja

Jeśli odbity punkt jest dotychczas najlepszym punktem, , ${\ Displaystyle f (\ mathbf {x} _ {r}) < f (\ mathbf {x} _ {1})}$

następnie oblicz rozwinięty punkt za pomocą .${\ Displaystyle \ mathbf {x} _ {e} = \ mathbf {x} _ {o} + \ gamma (\ mathbf {x} _ {r} - \ mathbf {x} _ {o})}$${\ Displaystyle \ gamma > 1}$

Jeśli rozszerzony punkt jest lepszy niż punkt odbity, , ${\ Displaystyle f (\ mathbf {x} _ {e}) < f (\ mathbf {x} _ {r})}$

następnie uzyskaj nowy simpleks, zastępując najgorszy punkt rozwiniętym punktem i przejdź do kroku 1;${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {e}}$

w przeciwnym razie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem odbitym i przejdź do kroku 1.${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {r}}$

5. Skurcz

Tutaj jest pewne, że . (Zauważ, że jest to drugi lub „kolejny” od najwyższego).${\ Displaystyle f (\ mathbf {x} _ {r}) \ geq f (\ mathbf {x} _ {n})}$${\ Displaystyle \ mathbf {x} _ {n}}$

Oblicz skrócony punkt za pomocą .${\ Displaystyle \ mathbf {x} _ {c} = \ mathbf {x} _ {o} + \ rho (\ mathbf {x} _ {n + 1} - \ mathbf {x} _ {o})}$${\displaystyle 0<\rho \leq 0,5}$

Jeżeli zamówienia punkt jest lepszy niż w najgorszym momencie, to znaczy , ${\ Displaystyle f (\ mathbf {x} _ {c}) <f (\ mathbf {x} _ {n + 1})}$

następnie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem skurczonym i przejdź do kroku 1;${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {c}}$

6. Skurcz

Zamień wszystkie punkty z wyjątkiem najlepszego ( ) na${\ Displaystyle \ mathbf {x} _ {1}}$

${\ Displaystyle \ mathbf {x} _ {i} = \ mathbf {x} _ {1} + \ sigma (\ mathbf {x} _ {i}} - \ mathbf {x} _ {1})}$ i przejdź do kroku 1.

Uwaga : , , i są odpowiednio odbicie, rozszerzalności, skurcz i kurczyć współczynników. Wartości standardowe są , , i . ${\ Displaystyle \ alfa}$${\ Displaystyle \ gamma}$${\ Displaystyle \ rho}$${\displaystyle \sigma}$${\ Displaystyle \ alfa =1}$${\ Displaystyle \ gamma = 2}$${\ Displaystyle \ rho = 1/2}$${\ Displaystyle \ sigma = 1/2}$

W przypadku odbicia , ponieważ jest wierzchołkiem z wyższą wartością skojarzoną wśród wierzchołków, możemy oczekiwać, że znajdziemy niższą wartość w odbiciu od przeciwnej ściany utworzonej przez wszystkie wierzchołki z wyjątkiem . ${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {n + 1}}$${\ Displaystyle \ mathbf {x} _ {i}}$${\ Displaystyle \ mathbf {x} _ {n + 1}}$

W przypadku rozwinięcia , jeśli punktem odbicia jest nowe minimum wzdłuż wierzchołków, możemy spodziewać się interesujących wartości wzdłuż kierunku od do . ${\ Displaystyle \ mathbf {x} _ {r}}$${\ Displaystyle \ mathbf {x} _ {o}}$${\ Displaystyle \ mathbf {x} _ {r}}$

Jeśli chodzi o skrócenie , jeśli , możemy oczekiwać , że lepsza wartość będzie znajdować się wewnątrz simpleksu utworzonego przez wszystkie wierzchołki . ${\ Displaystyle f (\ mathbf {x} _ {r})> f (\ mathbf {x} _ {n})}$${\ Displaystyle \ mathbf {x} _ {i}}$

Wreszcie kurczenie obsługuje rzadki przypadek, w którym zmniejszanie się od największego punktu zwiększa się , co nie może się zdarzyć wystarczająco blisko nieosobliwego minimum. W takim przypadku schodzimy do najniższego punktu w oczekiwaniu na znalezienie prostszego krajobrazu. Jednak Nash zauważa, że ​​arytmetyka o skończonej precyzji może czasami nie zmniejszać sympleksu i wdrożyła kontrolę, czy rozmiar jest rzeczywiście zmniejszony. ${\displaystyle f}$

Początkowy simpleks

Ważny jest początkowy simpleks. Rzeczywiście, zbyt mały początkowy simpleks może prowadzić do wyszukiwania lokalnego, w wyniku czego NM może łatwiej utknąć. Zatem ten simpleks powinien zależeć od natury problemu. Jednak oryginalny artykuł sugerował simpleks, w którym punkt początkowy jest podany jako , a pozostałe są generowane ze stałym krokiem wzdłuż każdego wymiaru po kolei. W ten sposób metoda jest wrażliwa na skalowanie zmiennych tworzących . ${\ Displaystyle \ mathbf {x} _ {1}}$${\displaystyle \mathbf {x}}$

Zakończenie

Aby przerwać cykl iteracyjny, potrzebne są kryteria. Nelder i Mead użyli przykładowego odchylenia standardowego wartości funkcji bieżącego simpleksu. Jeśli te wartości spadną poniżej pewnej tolerancji, cykl jest zatrzymywany, a najniższy punkt w simpleksie jest zwracany jako proponowane optimum. Zauważ, że bardzo „płaska” funkcja może mieć prawie takie same wartości funkcji w dużej domenie, więc rozwiązanie będzie wrażliwe na tolerancję. Nash dodaje test skurczu jako kolejne kryterium zakończenia. Zauważ, że programy kończą się, podczas gdy iteracje mogą się zbiegać.

Zobacz też

Bibliografia

Dalsza lektura

• Avriel, Mordechaj (2003). Programowanie nieliniowe: analiza i metody . Wydawnictwo Dover. Numer ISBN 978-0-486-43227-4.
• Coope, dowód osobisty; Cena, CJ (2002). „Pozytywne podstawy w optymalizacji numerycznej”. Optymalizacja obliczeniowa i aplikacje . 21 (2): 169–176. doi : 10.1023/A:1013760716801 . S2CID  15947440 .
• Gill, Filip E.; Murraya, Waltera; Wright, Margaret H. (1981). „Metody wielowymiarowych funkcji nie-gładkich”. Praktyczna Optymalizacja . Nowy Jork: prasa akademicka. str.  93 -96. Numer ISBN 978-0-12-283950-4.
• Kowalik J.; Osborne, MR (1968). Metody rozwiązywania problemów optymalizacji nieograniczonej . Nowy Jork: Elsevier. s.  24-27 . Numer ISBN 0-444-00041-0.
• Swann, WH (1972). „Bezpośrednie metody wyszukiwania”. W Murray, W. (red.). Metody numeryczne optymalizacji nieograniczonej . Nowy Jork: prasa akademicka. s. 13–28. Numer ISBN 978-0-12-512250-4.

Zewnętrzne linki

• Wyjaśnienie i wizualizacja Neldera-Meada (Downhill Simplex) za pomocą funkcji banana Rosenbrocka
• John Burkardt: Kod Nelder-Mead w Matlab – zauważ, że odmiana metody Nelder-Mead jest również zaimplementowana przez funkcję Matlaba fminsearch.
• Optymalizacja Nelder-Meada w Pythonie w bibliotece SciPy.
• nelder-mead - implementacja w Pythonie metody Nelder-Mead
• SOVA 1.0 (bezpłatny) - Optymalizacja Simplex dla różnych aplikacji
• [1] - HillStormer, praktyczne narzędzie do nieliniowej, wielowymiarowej i liniowo ograniczonej optymalizacji Simplex firmy Nelder Mead.