Метод Монте-Карло

Рассмотрим многомерную задачу глобальной условной оптимизации

(1)

где множество допустимых значений

(2)

(3)

Метод Монте-Карло относится к классу прямых методов случайного поиска.

Схема метода Монте-Карло.

Задаем общее количество испытаний и полагаем счетчик числа итераций .
С помощью какого-либо программного генератора случайных чисел генерируем компонент вектора . .
Вычисляем и полагаем , .

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

Отметим, что в простейшем случае точки

генерируются равномерно распределенными в области

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

Для локализации с помощью метода Монте-Карло глобального минимума с высокой вероятностью и точностью, требуется очень большое количество испытаний

. Поэтому метод Монте-Карло обычно комбинируют с каким-либо детерминированным методом локальной оптимизации.

Комбинация метода Монте-Карло с детерминированным методом локальной оптимизации.

Задаем общее количество исходных случайных точек .
С помощью какого-либо программного генератора случайных чисел генерируем случайных точек , принадлежащие множеству .
Полагаем .
Исходя из точки , каким-либо многомерным методом условной оптимизации (см. главу 9) находим локальный минимум функции в окрестности этой точки и вычисляем .
Если полагаем и переходим на п.4, иначе – переходим к следующему пункту.
Находим минимальное из чисел . Пусть

Принимаем в качестве приближенного решения задачи

и заканчиваем вычисления