Globalna maksymalizacja drogiej funkcji celu


12

Interesuje mnie globalne maksymalizowanie funkcji wielu ( ) rzeczywistych parametrów (w wyniku złożonej symulacji). Jednak funkcja, o której mowa, jest stosunkowo droga w ocenie, wymaga około 2 dni na każdy zestaw parametrów. Porównuję różne opcje i zastanawiałem się, czy ktoś miał jakieś sugestie.30

Wiem, że istnieje zestaw metod dla tego rodzaju procesu, który wymaga opracowania przybliżonych funkcji, a następnie ich maksymalizacji (np. Jones i in. „Skuteczna globalna optymalizacja drogich funkcji czarnej skrzynki” ). Wydaje się jednak, że jest to względnie związane z kodowaniem.

Mam możliwość prowadzenia dużej liczby symulacji równolegle (50+). Wydaje się to sugerować użycie algorytmów genetycznych do przeprowadzenia tej optymalizacji - ponieważ mogę stworzyć populację rozwiązań kandydujących tak szybko, jak to możliwe.

Oto moje pytania: 1) Czy ktoś ma doświadczenie z ogólnodostępnymi implementacjami tego rodzaju globalnych rozwiązań / rekomendacji? 2) Czy istnieją powody, by preferować lub unikać algorytmów genetycznych?

Jest to problem fizyczny, a moje wczesne eksperymenty pokazały liczbę zmian zasługi dość płynnie, gdy zmieniam parametry.

AKTUALIZACJA:

Dziękuję za pomoc! Kilka dodatkowych szczegółów: Nie potrzebuję żadnych informacji poza lokalizacją maksimum. Symulacja jest deterministyczna, a nie Monte Carlo, więc komplikacja nie jest wielkim problemem. Nie ma wyraźnych granic ani ograniczeń parametrów. Inną informacją, którą posiadam (a której wcześniej nie wspomniałem), jest ocena wielkości wymaganego maksimum. Podczas gdy szukam globalnego maksimum, byłbym również zadowolony z czegoś takiego lub większego - nie wiem, czy to by pomogło. Mam nadzieję, że jeśli przeprowadzę screening bardziej systematycznie (łacińskie hipersześci, jak sugeruje Brian Borchers), to się pojawi.


Kiedy oceniasz funkcję celu, czy generuje ona dodatkowe informacje, szczególnie. pochodne (lub przybliżenia) w odniesieniu do parametrów? Ponieważ sama funkcja celu jest kosztowna w obliczeniach, może być konieczne, że takie obliczenia należy wydoić, aby uzyskać dodatkowe informacje.
hardmath,

(Rok później), co skończyłeś - zmieniając kilka z 30 parametrów, model ...?
denis

denis: Byłem w stanie użyć intuicji fizycznej (i szczęścia), aby odgadnąć najważniejsze parametry, a następnie zmieniać je, aby uzyskać „wystarczająco dobry” wynik. (W tym przypadku znalezienie dokładnego optimum nie było tak ważne jak znalezienie wystarczająco dużej odpowiedzi.) Nie potrzebowałem pełnej mocy tych technik, ale dobrze jest mieć je pod ręką.
AJK

To prawda, że ​​było to 2 1/2 roku temu, ale czy masz wybór poziomu dokładności w ocenie funkcji celu (symulacja deterministyczna) i czy możesz kompromis między dokładnością a czasem działania?
Mark L. Stone

Odpowiedzi:


11

Algorytmy genetyczne są bardzo złym wyborem, gdy ocena funkcji celu jest niezwykle droga - metody te wymagają wielu ocen funkcji w każdym pokoleniu (w których równoległość może pomóc) i wielu pokoleniom (które są z natury sekwencyjne). Po dwóch dniach na pokolenie byłoby to bardzo wolne.

Nie wspominałeś, skąd wziął się ten problem. Czy analizujesz statystycznie powierzchnię prawdopodobieństwa (w takim przypadku będziesz potrzebować czegoś więcej niż tylko optymalnych parametrów i wartości celu) czy po prostu optymalizujesz funkcję celu?

Nie wspominałeś, czy obliczanie funkcji celu jest dokładne, czy niedokładne. Często zdarza się, że gdy funkcja celu jest obliczana przez symulację Monte Carlo, wartości są dość głośne. Może to wprowadzić w błąd wiele algorytmów optymalizacji. Metody powierzchni reakcji pomagają rozwiązać ten problem, wygładzając hałas.

Nie wspomniałeś o żadnych ograniczeniach parametrów. Czy są ograniczone? Czy między parametrami istnieją ograniczenia liniowe lub nieliniowe?

Istnieje prawdopodobieństwo, że większość z 30 parametrów nie jest tak ważna dla problemu. Sugerowałbym zastosowanie eksperymentalnej metody sprawdzania projektu, aby najpierw ustalić, który z 30 parametrów jest naprawdę ważny w optymalizacji, a następnie po ustaleniu rozsądnych wartości dla nieistotnych parametrów zoptymalizować w stosunku do ważnych parametrów. Metody takie jak próbkowanie Latin Hypercube mogą być bardzo pomocne w eliminowaniu stosunkowo nieistotnych parametrów. Na tym etapie kontroli można łatwo korzystać z setek procesorów.

Po zmniejszeniu liczby parametrów do bardziej rozsądnego rozmiaru zastosowałbym metodę powierzchni odpowiedzi, aby zoptymalizować pozostałe parametry. Jeśli powierzchnia odpowiedzi jest naprawdę multimodalna i używasz zbyt prostego modelu powierzchni odpowiedzi (zazwyczaj ludzie pasują do modelu kwadratowego), możesz łatwo wprowadzić Cię w błąd i przegapić globalne maksimum. Bądź ostrożny! Na tym etapie możesz ponownie skorzystać z wielu procesorów, stosując eksperymentalną konstrukcję, która zapewnia bardzo dobre pokrycie przestrzeni parametrów. Poszukaj punktów projektowych, w których dopasowany model jest daleki od obliczonych wartości - jest to wskazanie, że powierzchnia odpowiedzi nie działa dobrze w tym obszarze. Konieczne może być zbudowanie powierzchni odpowiedzi w oddzielnych obszarach przestrzeni parametrów.

W ostatnim kroku możesz zacząć od parametrów z optymalizacji powierzchni odpowiedzi i spróbować poprawić wartości parametrów ekranowanych, dostosowując je pojedynczo (opadanie współrzędnych).

Popieram zalecenie DAKOTA jako ramy dla tego rodzaju optymalizacji. Jeśli zamierzasz przeprowadzić tę optymalizację tylko raz, może być łatwiej zorganizować obliczenia ręcznie, ale jeśli zamierzasz to robić wielokrotnie, wówczas DAKOTA byłaby bardzo pomocna.


4
  1. Nie mam żadnego doświadczenia z tego rodzaju rozwiązaniami; niektórzy z moich współpracowników z nich skorzystali. DAKOTA wydaje się być pakietem oprogramowania zalecanym do tego rodzaju zadań. Zawiera interfejs, który pozwala użytkownikowi wielokrotnie przesyłać zadania do kolejki przesyłania i wykorzystywać dane wyjściowe do badań parametrów, analizy wrażliwości itp. Nie znam go wystarczająco dobrze, aby wiedzieć, czy skorzysta z uruchomienia wielu symulacji równocześnie.

  2. Zakładając, że twoje parametry są ciągłe, jeśli liczba zasług zmienia się płynnie wraz ze zmianą parametrów, wówczas model zastępczy powinien wykonać rozsądną pracę, dopasowując liczbę zasług, a informacje o pochodnej pochodnej powinny być pomocne w dopracowaniu konwergencji. W przypadku 30 parametrów przydatne powinny być również deterministyczne metody optymalizacji bez pochodnych; tam znowu gładkość powinna pomóc. W przeciwieństwie do tego algorytmy genetyczne w ogóle nie wykorzystują informacji pochodnych i często wymagają dostrajania parametrów, takich jak częstotliwość mutacji, częstotliwość rekombinacji i parametry selekcji, aby osiągnąć dobrą wydajność. Jako algorytm wybrałbym algorytmy genetyczne jako awarię, ponieważ spodziewałbym się, że dobrze zaprojektowana optymalizacja zastępcza lub deterministyczna metoda optymalizacji bez pochodnych będzie mieć lepsze zachowanie zbieżności.


Kilka powodów, dla których stosowanie deterministycznej metody optymalizacji bez pochodnych może nie być rozsądne. Po pierwsze, są to lokalne metody wyszukiwania, które mogą w końcu znaleźć lokalne maksimum i utracić znacznie lepszy punkt w innym miejscu w obszarze parametrów. Po drugie, metody te zazwyczaj wymagają dużej liczby iteracji ze stosunkowo niewielką liczbą ocen funkcji na iterację, więc nie są one dobrze równoległe.
Brian Borchers,

Masz rację co do lokalnych metod wyszukiwania. Istnieją globalne metody wyszukiwania (DIRECT, rozgałęzione i powiązane, wielopoziomowe wyszukiwanie współrzędnych), które nie konstruują modeli zastępczych i powinny działać lepiej niż lokalne metody wyszukiwania. Nie mogę mówić o skuteczności paralelizacji tych metod.
Geoff Oxberry

1

Spójrz na TOMLAB, DAKOTA i OpenMDAO w celu optymalizacji czarnej skrzynki.


Edycja # 3: Optymalizacja bayesowska jest bardzo podobna do EGO:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

licencje ograniczone:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint


Edytuj # 2:

Pierwszym podejściem jest zbudowanie metamodelu / surogatu (przy użyciu kriging / GP) wokół drogiej funkcji i wykorzystanie tych dodatkowych informacji do szybszego znalezienia globalnego optymalnego punktu przy mniejszej liczbie ocen (EGO).

Drugie podejście, jak w MDAS, polega na wyszukiwaniu bezpośrednim z kilkoma sprytnymi adaptacjami na wielu poziomach.

Podejścia heurystyczne mają charakter genetyczny / randomizowany i bez żadnych gwarancji.


Edycja nr 1:

TOMLAB to narzędzie oparte na MATLAB-ie, które ma najlepszą szybkość / jakość optymalizacji według papieru Sahinidis. Ale jest to narzędzie komercyjne o znaczącym zastosowaniu korporacyjnym. Nie używam tego.

DAKOTA jest bardziej dostosowana do obliczania niepewności, oprócz ogólnej optymalizacji. Oparty na c ++ i pewnym starszym kodzie Fortran. Chociaż na podstawie licencji LGPL i plików binarnych dostępnych do pobrania, bardzo trudna do ponownej kompilacji przynajmniej z mojego doświadczenia na Win7 z GCC lub MSVS / ifort. Ma zależności od wzmocnienia, okrążenia, cmake do kompilacji. Zasadniczo jest to opakowanie dla wielu rozwiązań typu open source i niewielu komercyjnych. Jest to produkt SNL i jest ściśle zintegrowany z innymi projektami Sandia NL. Udało mi się z powodzeniem zintegrować ten program zamiast niektórych procedur IMSL. W pracy Sahinidisa brakowało ogromnego paralelizmu możliwego w przypadku DAKOTA.

OpenMDAO to oparte na optymalizacji oprogramowanie do projektowania opracowane w Pythonie przez NASA na licencji APACHE. Próbuję tego obecnie.


Witamy w SciComp! Jak napisano obecnie, Twój post tak naprawdę nie wyjaśnia, dlaczego warto spojrzeć na TOMLAB lub OpenMDAO (inne odpowiedzi już omawiają DAKOTA). Szukamy odpowiedzi, które nie tylko dostarczyły rekomendacje, ale dyskutują, dlaczego te rekomendacje są przydatne, potencjalne pułapki i tak dalej.
Geoff Oxberry

Pośpieszyłem z moją odpowiedzią, a teraz dodałem wyjaśnienie.
denfromufa

0

Jeśli nie możesz sobie pozwolić na 30 przebiegów, z których każdy zmienia jeden parametr, różnicuj je w grupach:
na przykład 8 przebiegów, każdy różni się 4 parametrami razem, a następnie sprecyzuj najlepsze 2 przebiegi / 8 parametrów ...
(Nie mam pojęcia, jak wymienić zysk informacji a całkowity czas działania; wieloręki bandyta ?)


-3

Oto kod, który pozwala efektywnie zoptymalizować drogie funkcje czarnej skrzynki przy użyciu procesorów wielordzeniowych.

Opis matematyki stojącej za kodem znajduje się tutaj .


1
To jest ta sama odpowiedź, którą podałeś w tym poście . Wygląda też na to, że to twoja praca. Jeśli to prawda, proszę to wyraźnie zaznaczyć w swojej odpowiedzi.
nicoguaro

Czy możesz podać szczegółowe informacje na temat podejścia opisanego w dokumencie i wdrożonego w oprogramowaniu? Jaka jest zastosowana metoda? Dlaczego to jest dobre? Co zapewnia takie podejście, czego nie obejmują inne odpowiedzi?
nicoguaro

1
Pamiętaj również, że jesteś autorem tego oprogramowania , więc każdy, kto go przeczyta, będzie wiedział, że a) wiesz, o czym mówisz ib) może być nieco stronniczy.
Christian Clason
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.