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
źródło
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.
ź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 .
źródło