Сравнивать и контрастировать метод Монте-Карло и эволюционные алгоритмы

Ответ 1

"Монте-Карло", по моему опыту, сильно перегружен. Люди, похоже, используют его для любого метода, который использует генератор случайных чисел (глобальная оптимизация, анализ сценариев (Google "Excel Monte Carlo simulation" ), стохастическая интеграция (расчет Pi что все используют для демонстрации MC). Полагаю, потому что вы упомянули эволюционные алгоритмы в своем вопросе, что вы говорите о методах Монте-Карло для математической оптимизации: у вас есть какая-то функция фитнеса с несколькими входными параметрами, и вы хотите свести к минимуму ( или максимизировать) эту функцию.

Если ваша функция хорошо себя ведет (есть один, глобальный минимум, который вы прибудете независимо от того, с какими входами вы начнете), тогда вам лучше использовать метод детерминированной минимизации, такой как метод сопряженного градиента. Многие методы классификации машинного обучения включают в себя поиск параметров, которые минимизируют ошибку наименьших квадратов для гиперплоскости по отношению к учебному набору. Функция, которая в этом случае сводится к минимуму, является гладким, хорошо выполненным, парабалоидом в n-мерном пространстве. Вычислите градиент и скатывайте вниз. Легкий peasy.

Если, однако, ваши входные параметры дискретны (или если ваша фитнес-функция имеет прерывания), то уже невозможно точно рассчитать градиенты. Это может произойти, если ваша функция пригодности вычисляется с использованием табличных данных для одной или нескольких переменных (если переменная X меньше 0,5, используйте эту таблицу, используйте эту таблицу). Кроме того, у вас может быть программа, которую вы получили от НАСА, которая состоит из 20 модулей, написанных разными командами, которые вы запускаете как пакетное задание. Вы поставляете его с вводом, и он выплескивает число (думаю, черный ящик). В зависимости от входных параметров, которые вы начинаете с вас, вы можете оказаться в ложном минимуме. Глобальные методы оптимизации пытаются решить эти проблемы.

Эволюционные алгоритмы образуют один класс методов глобальной оптимизации. Глобальные методы оптимизации обычно включают какое-то "восхождение на холм" (принятие конфигурации с более высокой (худшей) функцией фитнеса). Это восхождение на холм обычно связано с некоторой случайностью/стохастикой/монте-карлосностью. В общем, эти методы с большей вероятностью будут принимать менее оптимальные конфигурации на раннем этапе и, по мере продвижения по оптимизации, они с меньшей вероятностью будут принимать низшие конфигурации.

Эволюционные алгоритмы свободно основаны на эволюционных аналогах. Имитированный отжиг основан на аналогии с отжигом в металлах. Методы роевых частиц также вдохновлены биологическими системами. Во всех случаях вам следует сравнить результаты с простой случайной (a.k.a. "monte carlo" ) выборкой конфигураций... это часто даст эквивалентные результаты.

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

Ответ 2

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

Другие методы Монте-Карло: метрополис, wang-landau, параллельный отпуск и т.д.

OTOH, Эволюционные методы используют "методы", заимствованные у природы, такие как мутации, перекрестки и т.д.