Я работаю над улучшением процесса оптимизации некоторых программ для демографического моделирования, чтобы они лучше подходили демографическим моделям к данным. Мы хотели бы сократить время оптимизации.
Время, необходимое для оценки нашей целевой функции, сильно варьируется в зависимости от входных значений. Связь между временем для оценки целевой функции и входных данных известна. Мне интересно, существуют ли какие-либо методы оптимизации, которые учитывают относительную временную стоимость целевой функции при выборе того, какие точки оценивать.
Спасибо!
Обновить:
Как просил Павел, вот некоторые существенные особенности этой конкретной целевой функции:
- Количество параметров умеренное (~ 12ish)
- Наша проблема невыпуклая, или, по крайней мере, на поверхности целевой функции имеются узкие и плоские «гребни». Прямо сейчас мы имеем дело с этим, используя несколько оптимизаций из разных точек, но мы хотели бы добиться большего.
- Целевая функция довольно гладкая, хотя мы можем вычислять только разностные приближения к производным.
- Стоимость оценки также является гладкой функцией значений параметров, и она вполне предсказуема. грубо говоря, для каждого параметра стоимость оценки высока на одном конце диапазона и низкая на другом конце. Таким образом, у нас есть большие области дорогих для оценки наборов параметров, но мы знаем, где они находятся.
optimization
новая звезда
источник
источник
Ответы:
Один из распространенных подходов к работе с дорогостоящими целевыми функциями состоит в том, чтобы создать (например, регрессионное моделирование) «модель поверхности отклика», которая приближается к исходной целевой функции, а затем оптимизировать по этой поверхности отклика, а не работать с исходной функцией. На практике поверхности отклика, как правило, представляют собой просто квадратичные модели, подходящие по регрессии, поэтому поиск минимума поверхности отклика становится очень простой задачей оптимизации.
Вы ничего не сказали о плавности или выпуклости вашей целевой функции. Если функция негладкая или невыпуклая, то это, очевидно, становится намного, намного сложнее.
Вы также ничего не сказали о том, где находятся дорогие точки в вашем пространстве параметров. Если они случайным образом распределены по пространству параметров, то вы можете использовать методы экспериментов для построения модели поверхности отклика, избегая при этом дорогостоящих точек. Если в области параметров есть большие области, где оценки стоят дорого, вы можете попытаться свести к минимуму количество точек в тех областях, которые вы используете при построении модели поверхности отклика. Конечно, если ваш оптимум находится в центре такого региона, вы будете обречены на оценку функций в дорогом регионе.
источник
Я не знаю методов, которые бы конкретно взвешивали относительные затраты на оценку цели в разных испытательных точках, но если вы в состоянии относительно надежно предсказать, будет ли кандидат оценивать дорогостоящую оценку или нет, то я мог бы предложить попробовать прямой метод . Прямые методы вписываются в семейство методов без производных. Использовать их не обязательно плохо, даже если вы подозреваете, что ваша проблема довольно гладкая, поскольку они могут обеспечить некоторый уровень гибкости, который не может обеспечить методы плавной оптимизации.
Идея состоит в том, что прямые методы определяют (зависящий от итерации) меш относительно текущей итерации и (зависящий от итерации) «шаг» сетки. На основе этого шага сетки метод определяет пробные точки на сетке, которые являются соседями текущей итерации (они лежат на сетке и находятся на расстоянии, определяемом шагом сетки). Затем он приступит к оценке цели у соседей. Как только найден лучший кандидат, он становится новой текущей итерацией. По вашему выбору вы также можете оценить всех соседей и выбрать лучшего.
В вашем случае, было бы неплохо заказать соседей на основе вашей оценки стоимости оценки цели там. Оцените их в этом порядке и выберите первый успех в качестве следующей итерации. Интуитивно вы предпочитаете дешевых кандидатов. В прямых методах такие упорядочения соответствуют категории суррогатных моделей - концепции, обобщающей концепцию модели поверхности отклика, упомянутой Брайаном.
Вот отличная реализация прямого метода (в C ++): http://www.gerad.ca/nomad/Project/Home.html
Если это дает многообещающие результаты, пожалуйста, не стесняйтесь обращаться ко мне, и я могу предложить другие улучшения.
Я полагаю, что NOMAD также имеет функции для глобальной оптимизации (например, мультистарт, который вы в настоящее время применяете) на основе концепции поиска переменных окрестностей .
источник