называемых пробными точками; в каждой из этих точек вычисляется значение
и находится точка
в которой
Точка
служит приближением к точке Р.
Рассмотрим произвольную область
с положительным
-мерным объемом
содержащую точку Р. Если при
хотя бы одна пробная точка попадает в В, то говорят, что процесс поиска сходится.
Докажем, что если в качестве пробных точек выбирать независимые случайные точки с плотностью
внутри
, то процесс поиска сходится. Для доказательства фиксируем произвольную область В с
содержащую точку Р и обозначим через
вероятность того, что одна пробная точка попадет в В.
Очевидно,
Вероятность того, что хотя бы одна из N пробных точек окажется в В, равна
и стремится к 1, когда
Следовательно, какой бы коэффициент доверия
мы ни выбрали, при достаточно большом N с вероятностью, большей чем
хотя бы одна пробная точка попадет в В.
Если никакой предварительной информации о расположении Р нет, то естественно выбрать
, т. е. использовать пробные точки
равномерно распределенные в
Такой поиск называют простейшим случайным поиском (или слепым поиском).
Ясно, что процесс поиска можно улучшить, если в ходе поиска менять плотность
с учетом уже полученных значений. Например, точку
выбирать по плотности
которая строится с учетом значений
На таких более совершенных (но и более сложных) алгоритмах поиска мы здесь останавливаться не будем [22, 66, 72, 184]. Отметим только некоторые ситуации, в которых простейший случайный поиск весьма полезен.
а) Функция
достаточно гладкая, но многоэкстремальная. Простейший случайный поиск целесообразно использовать для отбора начальных точек, из которых можно локальными методами (метод градиентов, наискорейший спуск и др.) попасть в ближайший максимум. Чем тщательнее выбор начальных точек, тем меньше шансов пропустить абсолютный максимум.
б) Требуется найти максимумы нескольких функций
При простейшем случайном поиске можно одновременно (по одним и тем же пробным точкам
) искать максимумы (и минимумы) всех этих функций.
Такая ситуация довольно типична для задач оптимального конструирования: обычно качество конструкции можно оценивать по ряду весьма различных критериев, и выбор решающего (или компромиссного) критерия удается сделать лишь тогда, корда известно, чего можно добиться, оптимизируя тот или иной критерий в отдельности.