Методы, использующие случайный поиск (Нелокальный метод)

Градиентный метод приводит к экстремальной точке, если эта точка является единственной в области определения функции S.

Обычно целевая функция многоэкстремальна. Нужны нелокальные методы.

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

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

С ростом числа проб вероятность достижения экстремума 1.

Недостаток: информация об уже проведённых опытах не используется для проведения последующих.

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

Рассмотрим два возможных варианта построения таких процедур.

Вариант 1. Пусть задача состоит в отыскании набора переменных Х*, минимизирующего целевую функцию f(X) , т.е.

В области S определения функции f(X) выбираем в соответствии с некоторым случайным механизмом совокупность точек

Используя каждую из этих точек в качестве начальной для организации градиентной процедуры, получаем в результате её реализации совокупность точек

- локальные минимумы.

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

Теперь в качестве приближения к глобальному экстремуму выберем такую точку из Z, для которой

С увеличением числа проб q вероятность достижения глобального экстремума монотонно возрастает.

Вариант 2. Выбираем в области определения функции f(X) совокупность точек

.

Далее вычисляем значения функции f(X) в каждой из этих точек, получая при этом совокупность чисел

Теперь, в отличие от варианта 1, осуществляем однократный градиентный спуск из той точки , для которой значение функции минимально, т.е.

В результате градиентного спуска получаем точку

которую и принимаем в качестве оценки для глобального экстремума X*.

С увеличением q вероятность достижения глобального экстремума возрастает.

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