Metoda Neldera-Meada - Nelder–Mead method
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 .
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.)
Staramy się zminimalizować funkcję , gdzie . Nasze obecne punkty testowe to .
1. Uporządkuj według wartości na wierzchołkach:
- 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 .
3. Odbicie
- Oblicz punkt odbity za pomocą .
- Jeśli odbicie punkt jest lepszy niż drugi najgorszy, ale nie lepsze niż najlepsze, czyli ,
- następnie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem odbitym i przejdź do kroku 1.
4. Ekspansja
- Jeśli odbity punkt jest dotychczas najlepszym punktem, ,
- następnie oblicz rozwinięty punkt za pomocą .
- Jeśli rozszerzony punkt jest lepszy niż punkt odbity, ,
- następnie uzyskaj nowy simpleks, zastępując najgorszy punkt rozwiniętym punktem i przejdź do kroku 1;
- w przeciwnym razie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem odbitym i przejdź do kroku 1.
5. Skurcz
- Tutaj jest pewne, że . (Zauważ, że jest to drugi lub „kolejny” od najwyższego).
- Oblicz skrócony punkt za pomocą .
- Jeżeli zamówienia punkt jest lepszy niż w najgorszym momencie, to znaczy ,
- następnie uzyskaj nowy simpleks, zastępując najgorszy punkt punktem skurczonym i przejdź do kroku 1;
6. Skurcz
- Zamień wszystkie punkty z wyjątkiem najlepszego ( ) na
- i przejdź do kroku 1.
Uwaga : , , i są odpowiednio odbicie, rozszerzalności, skurcz i kurczyć współczynników. Wartości standardowe są , , i .
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 .
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 .
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 .
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.
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 .
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ż
- Optymalizacja bez pochodnych
- COBYLA
- NOWOŚĆ
- LINCOA
- Nieliniowa metoda gradientu sprzężonego
- Algorytm Levenberga-Marquardta
- Metoda Broydena-Fletchera-Goldfarba-Shanno lub BFGS
- Ewolucja różnicowa
- Wyszukiwanie wzorców (optymalizacja)
- CMA-ES
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.