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.
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.
źródło
Odpowiedzi:
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.
źródło
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.
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.
źródło
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.
źródło
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 ?)
źródło
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 .
źródło