Введение в информатику. Хамухин А.А. - 138 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

137
4.7.5. Метод Монте-Карло (случайного поиска)
Датой рождения метода Монте-Карло принято считать 1949 год, когда
американские ученые Н. Метрополис и С. Услам впервые опубликовали статью с
аналогичным названием «Метод Монте-Карло», в которой были изложены
принципы этого метода. Свое название метод получил в честь города Монте-Карло,
славящимся своими игорными заведениями, непременным атрибутом которых
является рулетка – одно из простейших средств получения случайных чисел с
хорошим равномерным распределением, на использовании которых и основан этот
метод.
Метод Монте-Карло – это статистический метод, его используют при
вычислении сложных интегралов, решении систем алгебраических уравнений
высокого порядка, моделировании поведения элементарных частиц, в теориях
передачи информации и массового обслуживания, при исследовании сложных
систем (экономических, биологических и т. д.).
Сущность метода состоит в том, что в решаемую задачу вводят случайную
величину , изменяющуюся по какому-то закону p(). Как правило, случайную
величину выбирают таким образом, чтобы искомая в задаче величина A стремилась
к математическому ожиданию от при достаточно большом количестве испытаний:
AM )(
. (4.49)
Таким образом, мы определяем искомую величину A лишь теоретически. А вот
чтобы найти ее численно, пользуются статистическими методами: берут выборку
случайной величины объемом N элементов. В результате получают N вариант
случайной величины
i
, для которых вычисляют их среднее арифметическое
(выборочное среднее), которое и принимают в качестве приближенного значения
(оценки) искомой величины A.
Для получения результата приемлемой точности по методу Монте-Карло
требуется большое число статистических испытаний. Именно поэтому этот метод
иногда так и называют: метод статистических испытаний.
При поиске экстремумов, часто возникает проблема «ловушки локального
экстремума», которую многие алгоритмы не могут преодолеть. Метод Монте-Карло
один из немногих, который позволяет находить глобальный экстремум. Существует
множество модификаций этого метода, в частности, – метод «моделируемого
отжига», который применяют для поиска глобальных экстремумов. Метод
«моделируемого отжига» строится на аналогии постепенного охлаждения нагретого
до температуры плавления металла, при которой атомы, первоначально
находящиеся в беспорядочном движении, последовательно занимают все более
низкоэнергетическое состояние, пока не будет достигнуто наименьшее из
возможных энергетических состояний – глобальный минимум.
Недостатком методов случайного поиска является необходимость большого
количества вычислений целевой функции и, если она слишком сложна, то время
расчетов, даже на мощных компьютерах, может оказаться неприемлемо большим.

Страницы