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