Metoda optymalizacji uwzględniająca różne koszty czasowe funkcji celu dla różnych parametrów

Pracuję nad usprawnieniem procesu optymalizacji niektórych programów do modelowania demograficznego, aby lepiej pasowały modele demograficzne do danych. Chcielibyśmy skrócić czas optymalizacji.

Czas potrzebny na ocenę naszej funkcji celu jest bardzo różny, w zależności od wartości wejściowych. Związek między czasem oceny funkcji celu a danymi wejściowymi jest znany. Zastanawiam się, czy istnieją metody optymalizacji uwzględniające względny koszt czasu funkcji celu przy wyborze punktów do oceny.

Dzięki!

Aktualizacja:

Zgodnie z prośbą Pawła, oto kilka istotnych cech tej szczególnej funkcji celu:

Liczba parametrów jest umiarkowana (~ 12ish)
Nasz problem jest niewypukły, a przynajmniej są wąskie i płaskie „grzbiety” na powierzchni funkcji celu. Obecnie mamy do czynienia z tym przy użyciu wielu optymalizacji z różnych punktów, ale chcielibyśmy zrobić to lepiej.
Funkcja celu jest dość płynna, chociaż możemy obliczyć przybliżone różnice skończone dla pochodnych.
Koszt oceny jest również płynną funkcją wartości parametrów i jest dość przewidywalny. z grubsza mówiąc, dla każdego parametru koszt oceny jest wysoki na jednym końcu zakresu i niski na drugim końcu. Mamy więc duże regiony kosztownych do oceny zestawów parametrów, ale wiemy, gdzie one są.

optimization

— nowa
źródło

Cześć Kate i witaj w Scicomp! Czy możesz podzielić się niektórymi cechami swojej funkcji celu? To może pomóc w ustaleniu konkretnej metody dla twojego przypadku.

— Paweł

Nigdy nie słyszałem o żadnym algorytmie, który bierze pod uwagę koszt oceny funkcji celu (lub jakichkolwiek ograniczeń) wyraźnie przy wyborze punktów do oceny. Istnieją jednak algorytmy optymalizacji wolne od pochodnych, które próbują sprytnie wybrać następny punkt do oceny przez optymalizator. Założeniem jest, że liczba ocen funkcji powinna być zminimalizowana, jeśli oceny funkcji są drogie. Nie jestem jednak pewien, czy użycie algorytmów bez pochodnych pomoże w przypadku użycia.

— Geoff Oxberry

Cześć, Paul, dzięki za powitanie! Jestem podekscytowany, że znalazłem tę społeczność. Dodałem cechy. Daj mi znać, jeśli są inne funkcje, które są ważniejsze.

— nowa,

Czy mam rację wnioskować z twojego nr 2, że jesteś zainteresowany globalnym minimalizatorem? Czy jesteś zadowolony z „wystarczającego” spadku? Globalna optymalizacja jest dziedziną samą w sobie, a kwestia osiągnięcia globalnego rozwiązania (jeśli takie istnieje) może być całkowicie niezależna od unikania kosztownych prób.

— Dominique

Dominique, założyliśmy, że globalny optymalizator będzie zbyt wolny dla naszego problemu, więc byliśmy zadowoleni z lokalnych optymalizatorów. Globalni optymalizatorzy to coś, co planujemy zbadać w przyszłości.

— nowa

Odpowiedzi:

Jednym z powszechnych podejść do radzenia sobie z kosztownymi funkcjami celu jest zbudowanie (np. Modelowanie regresji) „modelu powierzchni odpowiedzi”, który aproksymuje pierwotną funkcję celu, a następnie optymalizacja na podstawie tej powierzchni odpowiedzi zamiast pracy z pierwotną funkcją. W praktyce powierzchnie odpowiedzi są zazwyczaj tylko modelami kwadratowymi dopasowanymi przez regresję, więc znalezienie minimum powierzchni odpowiedzi staje się bardzo łatwym problemem optymalizacji.

Nie powiedziałeś nic o gładkości lub wypukłości swojej funkcji celu. Jeśli funkcja nie jest gładka lub nie wypukła, wówczas staje się to znacznie, znacznie trudniejsze.

Nie powiedziałeś również nic o tym, gdzie są drogie punkty w przestrzeni parametrów. Jeśli są one losowo rozmieszczone w przestrzeni parametrów, możesz użyć projektu technik eksperymentów, aby zbudować model powierzchni odpowiedzi, unikając kosztownych punktów. Jeśli istnieją większe obszary przestrzeni parametrów, w których oceny są drogie, możesz spróbować zminimalizować liczbę punktów w tych obszarach, które wykorzystujesz do budowy modelu powierzchni odpowiedzi. Oczywiście, jeśli Twoje optymalne położenie znajduje się w środku takiego regionu, będziesz skazany na ocenę funkcji w drogim regionie.

— Brian Borchers
źródło

Nie znam metod, które konkretnie ważą względne koszty oceny celu w różnych punktach próbnych, ale jeśli jesteś w stanie stosunkowo wiarygodnie przewidzieć, czy kandydat będzie drogi do oceny, czy nie, to mógłbym zasugerować spróbowanie metoda bezpośrednia . Metody bezpośrednie mieszczą się w rodzinie metod wolnych od pochodnych. Korzystanie z nich niekoniecznie jest złe, nawet jeśli podejrzewasz, że Twój problem jest dość płynny, ponieważ zapewniają pewną elastyczność, której nie zapewniają metody płynnej optymalizacji.

Chodzi o to, że metody bezpośrednie definiują siatkę (zależną od iteracji) o bieżącym iteracie i „krok” siatki (zależnej od iteracji). Na podstawie tego kroku siatki metoda określa punkty próby na siatce, które są sąsiadami bieżącego iteratu (leżą na siatce i znajdują się w odległości określonej przez krok siatki). Następnie przystąpi do oceny celu u sąsiadów. Gdy tylko zostanie znaleziony lepszy kandydat, staje się on nową aktualną iteracją. Do twojej dyspozycji możesz także ocenić wszystkich sąsiadów i wybrać najlepszy.

W twoim przypadku dobrym pomysłem może być zamówienie sąsiadów na podstawie oszacowania kosztu oceny tamtego celu. Oceń je w tej kolejności i wybierz pierwszy sukces jako następną iterację. Intuicyjnie preferujesz tanich kandydatów. W metodach bezpośrednich takie uporządkowanie pasuje do kategorii modeli zastępczych , koncepcji, która uogólnia koncepcję modelu powierzchni odpowiedzi wspomnianą przez Briana.

Oto doskonała implementacja metody bezpośredniej (w C ++): http://www.gerad.ca/nomad/Project/Home.html

Jeśli wydaje się, że daje to obiecujące wyniki, proszę do mnie wrócić, a być może uda mi się zasugerować inne ulepszenia.

Wierzę, że NOMAD posiada również funkcje globalnej optymalizacji (takie jak wielostartowy program, który obecnie stosujesz) w oparciu o koncepcję wyszukiwania zmiennych okolic .

— Dominique
źródło