Оптимизация нескольких параметров с большим количеством локальных минимумов

Question

Я ищу алгоритмы, чтобы найти «лучший» набор значений параметров.Данная функция имеет много локальных минимумов и меняется очень быстро.Что еще хуже, тестирование набора параметров очень медленное - порядка 1 минуты - и я не могу вычислить градиент напрямую.

Существуют ли известные алгоритмы для такого рода оптимизации?

Я добился умеренного успеха, пытаясь использовать случайные значения.Мне интересно, смогу ли я улучшить производительность, сделав случайный выбор параметров с меньшей вероятностью выбора параметров, близких к тем, которые давали плохие результаты в прошлом.Есть ли название для этого подхода, чтобы я мог искать конкретный совет?

Дополнительная информация:

• Параметры непрерывны
• Есть порядка 5-10 параметров.Конечно, не более 10.

Answer 1

Сколько существует параметров - например, сколько измерений в пространстве поиска?Являются ли они непрерывными или дискретными - например, действительными числами или целыми числами, или только несколькими возможными значениями?

Подходы, которые я видел для решения подобных проблем, имеют схожую общую структуру - занимают большое количествовыборочные точки и приспособьте их все к областям, которые имеют "хорошие" ответы так или иначе.Поскольку у вас много точек, их относительные различия служат временным градиентом.

• Имитация отжига : классический подход.Возьмите несколько точек, вероятностно переместите некоторые в соседнюю точку, выбранную случайным образом, в зависимости от того, насколько она лучше.
• Оптимизация роя частиц : Возьмите «рой» частиц со скоростямив пространстве поиска вероятностно случайным образом перемещают частицу;если это улучшение, дайте знать всему рое.
• Генетические алгоритмы : Это немного другое.Вместо того, чтобы использовать информацию о соседях, как описано выше, вы каждый раз берете лучшие результаты и «скрещиваете» их, надеясь получить лучшие характеристики каждого.

Ссылки на Википедию имеют псевдокод для первых двух;Методы GA настолько разнообразны, что сложно перечислить только один алгоритм, но вы можете переходить по ссылкам оттуда.Обратите внимание, что существуют реализации для всего вышеперечисленного, которые вы можете использовать или использовать в качестве отправной точки.

Обратите внимание, что все они - и в действительности любой подход к этому алгоритму поиска в больших объемах - являются эвристическими.Это означает, что у них есть параметры, которые должны быть настроены на вашу конкретную проблему.Который может быть утомительным.

Кстати, тот факт, что оценка функции стоит так дорого, может заставить вас немного работать;поскольку все вышеперечисленные методы включают в себя множество независимых вычислений функций, этот фрагмент алгоритма можно тривиально распараллелить с OpenMP или чем-то подобным, чтобы использовать столько ядер, сколько у вас есть на вашем компьютере.

Answer 2

Я пробовал Имитация отжига и Оптимизация роя частиц .(Как напоминание, я не мог использовать градиентный спуск, потому что градиент не может быть вычислен).

Я также попробовал алгоритм, который делает следующее:

• Выберите случайныйточка и случайное направление
• Оцените функцию
• Продолжайте двигаться в случайном направлении до тех пор, пока результат будет улучшаться, ускоряя каждую успешную итерацию.
• Когдарезультат перестает улучшаться, отступите назад и вместо этого попытайтесь двигаться в ортогональном направлении на то же расстояние.

Это "ортогональное направление" было сгенерировано путем создания случайной ортогональной матрицы (адаптировано этот код ) с необходимым количеством измерений.

Если перемещение в ортогональном направлении улучшило результат, алгоритм просто продолжил в этом направлении.Если ни одно из направлений не улучшило результат, расстояние прыжка сократилось бы вдвое, и был бы предпринят новый набор ортогональных направлений.В конце концов алгоритм пришел к выводу, что он должен быть в локальном минимуме, запомнил его и перезапустил всю партию в новой случайной точке.

Этот подход работал значительно лучше, чем моделируемый отжиг и рой частиц: требовалось меньше оценок (очень медленная) функция для достижения результата того же качества.

Конечно, мои реализации SA и PSO вполне могут быть ошибочными - это хитрые алгоритмы с большим пространством для настройки параметров.Но я просто подумал, что упомяну, что сработало лучше для меня.

Answer 3

Ваша ситуация похожа на ситуацию с плакатом Программное обеспечение для настройки / калибровки свойств для эвристических алгоритмов , и я бы дал вам тот же совет , который я дал там : подумайте Метрополис-Гастингс подобный подход с несколькими ходунками и имитацией отжига размеров ступеней.

Сложность использования методов Монте-Карло в вашем случае - это дорогостоящая оценка каждого кандидата. Насколько дороже по сравнению с тем временем, которое у вас есть под рукой? Если вам нужен хороший ответ через несколько минут, это не будет достаточно быстро. Если вы можете оставить его работать на ночь, он будет работать достаточно хорошо.

Учитывая сложное пространство поиска, я бы порекомендовал случайное начальное распределение. Ваш окончательный ответ может быть просто лучшим индивидуальным результатом, записанным за весь пробег, или средней позицией ходунка с лучшим результатом.

Не откладывай на то, что я там обсуждал максимизацию, а ты хочешь минимизировать: показатель достоинства можно отрицать или инвертировать.

Answer 4

Я не могу помочь вам найти алгоритм для вашей конкретной проблемы.

Однако, что касается случайного выбора параметров, я думаю, что вы ищете генетические алгоритмы .Генетические алгоритмы, как правило, основаны на выборе некоторого случайного ввода, выборе тех, которые наилучшим образом (на данный момент) подходят для задачи, и случайном изменении / комбинировании их для генерации следующего поколения, для которого снова выбираются лучшие.

Если функция является более или менее непрерывной (то есть небольшие мутации хороших входных данных, как правило, не будут генерировать плохие входные данные (маленький является несколько общим)), это будет работать достаточно хорошо для вашей проблемы.

Answer 5

Не существует обобщенного способа ответить на ваш вопрос. Существует множество книг / статей по данной тематике, но вам придется выбирать свой путь в соответствии с вашими потребностями, о которых здесь четко не сказано.

Однако нужно кое-что знать - 1мин / тест - это слишком много для любого алгоритма. Я предполагаю, что в вашем случае вы действительно должны выполнить одно из следующих действий:

• получите 100 компьютеров, чтобы сократить время тестирования параметров до приемлемого времени
• действительно постарайтесь определить ваши параметры руками и умом. Должна быть некоторая избыточность и, по крайней мере, некоторая проверка работоспособности, чтобы вы могли проверить свой случай за <1мин </li>
• для возможных результирующих наборов, попробуйте выяснить некоторые «операции», которые слегка его изменяют, а не просто рандомизируют. Например, в TSP некоторым базовым оператором является лямбда, который переставляет два узла и таким образом создает новый маршрут. Вы можете сместить некоторое число вверх / вниз для некоторого значения.
• тогда, найдите себе хороший алгоритм, ваша отправная точка может быть где-то здесь . Книга является бесценным ресурсом для всех, кто начинает с решения проблем.