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

Ответ 1

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

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

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

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

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

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

Конечно, мои реализации S.A. и P.S.O. вполне могут быть испорчены - это сложные алгоритмы с большим количеством возможностей для настройки параметров. Но я просто подумал, что упомянул, что в конечном итоге работает лучше всего для меня.

Ответ 2

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

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

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

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

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

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

Ответ 3

Ваша ситуация, похоже, похожа на ситуацию с плакатом Software to Tune/Calibrate Properties для эвристических алгоритмов, и я дам вам тот же совет Я дал там: рассмотрим Metropolis-Hastings, как подход с несколькими ходоками и имитированный отжиг размеры шага.

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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