Методы, использующие случайный поиск (Нелокальный метод)
Градиентный метод приводит к экстремальной точке, если эта точка является единственной в области определения функции S.
Обычно целевая функция многоэкстремальна. Нужны нелокальные методы.
Метод случайного поиска: в области определения функции в соответствии с некоторым случайным механизмом выбираются точки, значения функции в которых сравниваются между собой.
Наибольшее из них (если отыскивается максимум) соответствует точке, принимаемой в качестве оценки для искомой.
С ростом числа проб вероятность достижения экстремума 1.
Недостаток: информация об уже проведённых опытах не используется для проведения последующих.
Усовершенствовать эту процедуру можно, сочетая случайный поиск с каким-либо из локальных методов (например, градиентным).
Рассмотрим два возможных варианта построения таких процедур.
Вариант 1. Пусть задача состоит в отыскании набора переменных Х*, минимизирующего целевую функцию f(X) , т.е.
В области S определения функции f(X) выбираем в соответствии с некоторым случайным механизмом совокупность точек
Используя каждую из этих точек в качестве начальной для организации градиентной процедуры, получаем в результате её реализации совокупность точек
- локальные минимумы.
Каждая из этих точек - локальный минимум, полученный из соответствующей начальной точки, т.е. если через Т обозначить процедуру градиентного спуска, то
Теперь в качестве приближения к глобальному экстремуму выберем такую точку из Z, для которой
С увеличением числа проб q вероятность достижения глобального экстремума монотонно возрастает.
Вариант 2. Выбираем в области определения функции f(X) совокупность точек
.
Далее вычисляем значения функции f(X) в каждой из этих точек, получая при этом совокупность чисел
Теперь, в отличие от варианта 1, осуществляем однократный градиентный спуск из той точки , для которой значение функции минимально, т.е.
В результате градиентного спуска получаем точку
которую и принимаем в качестве оценки для глобального экстремума X*.
С увеличением q вероятность достижения глобального экстремума возрастает.
В большинстве практических случаев 2-я процедура более эффективна. Причём выигрыш становится тем более заметен, чем более существенно глобальный экстремум отличается от ближайшего по величине локального, и следовательно, чем более важным является его отыскание.
