Главная > Математика > Численные методы Монте-Карло
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 2. Простейший случайный поиск

2.1. Случайный поиск.

Рассмотрим ограниченную кусочно непрерывную функцию , определенную в замкнутом единичном -мерном кубе так что это куб вместе с его границей. Обозначим через Р точку абсолютного максимума т. е. такую точку, что для всех

Простейший поиск точки Р состоит в том, что в кубе задается произвольная последовательность точек

называемых пробными точками; в каждой из этих точек вычисляется значение и находится точка в которой

Точка служит приближением к точке Р.

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

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

Очевидно,

Вероятность того, что хотя бы одна из N пробных точек окажется в В, равна и стремится к 1, когда

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

Если никакой предварительной информации о расположении Р нет, то естественно выбрать , т. е. использовать пробные точки равномерно распределенные в Такой поиск называют простейшим случайным поиском (или слепым поиском).

Ясно, что процесс поиска можно улучшить, если в ходе поиска менять плотность с учетом уже полученных значений. Например, точку выбирать по плотности которая строится с учетом значений На таких более совершенных (но и более сложных) алгоритмах поиска мы здесь останавливаться не будем [22, 66, 72, 184]. Отметим только некоторые ситуации, в которых простейший случайный поиск весьма полезен.

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление