Метод случайного поиска с направляющим конусом

 Как и раньше, из точки х ^k делается т проб  но на основе использования случайных векторов с равномерно распределенной плотностью внутри гиперконуса с вершиной в точке х ^k и осью, направленной вдоль вектора памяти w^k, и с углом полного раствора Y (см. рис.5.14).

Рис.	5.14	Метод случайного поиска с направляющим конусом

Направление рабочего смещения Dх ^k определим в соответствии с методом наилучшей пробы

В качестве обновленного вектора w^k+1 примем вектор наилучшей пробы  Таким образом, в данном алгоритме выбору подлежат не четыре, а три параметра Y, h_раб, m.

Характерной особенностью двух последних алгоритмов является их «инерционность». Действительно, направление поиска, задаваемое в среднем вектором памяти w^k, не может резко измениться за один шаг. Эта инерционность определяется в одном алгоритме параметрами h_раб и d, в другом — параметрами h_раб и Y. Наличие инерционности придает глобальный характер процессу поиска, позволяя преодолевать локальные минимумы и осуществлять поиск вдоль «оврагов» и «хребтов» целевой функции. С другой стороны, процесс поиска должен быть достаточно мобильным. Поэтому при выборе параметров алгоритмов приходится прибегать к компромиссному решению. При рациональном назначении этих параметров алгоритм стимулирует поиск вдоль «оврагов» целевой функции независимо от того, поднимаются они или опускаются, позволяя преодолевать «хребты» по «перевалам» и отыскивать новые районы ее локальных минимумов. Эти алгоритмы хотя и не находят самого глобального минимума, но позволяют выделить те области пространства, где этот минимум может находиться.

Комбинированные методы

Эти методы применяются для улучшения сходимости методов случайного поиска, а также для ликвидации ряда недостатков детерминированных методов.

Стохастический вариант метода Гаусса-Зейделя. Основной недостаток метода Гаусса-Зейделя состоит в слабой эффективности при оптимизации овражных функций и при наличии ограничений. Этот недостаток может быть устранён, если движение вдоль координатной оси заменить движением в случайном направлении.

Метод оврагов. В случае многомерных оврагов полезно в начале поиска взять несколько случайных точек x⁰¹, x⁰², …, x^{0 n} и произвести спуск на дно оврага в точки x¹¹, x¹², …, x^{1 n}. Далее по этим точкам выбрать направление оврага, например, с помощью метода статистического градиента.

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

Блуждающий глобальный поиск. Этот метод является статистическим обобщением метода градиентного спуска. Чтобы придать поиску глобальный характер, на траекторию градиентного спуска накладываются случайные отклонения x( t), которые создают режим случайного блуждания. Движение точки x(t) в процессе поиска описывается уравнением

где h – параметр, играющий роль шага поиска при численной реализации данного уравнения, а x( t) - n-мерный случайный процесс типа белого шума с нулевым математическим ожиданием и спектральной плотностью s². Процесс, описываемый этим выражением, является Марковским случайным процессом диффузионного типа. Плотность распределения вероятности p( x, t) удовлетворяет уравнению Фоккера-Планка-Колмогорова

У этого уравнения есть стационарное решение

, при t ® ¥ ,

где c – формирующий множитель.

Максимальное значение p( x) соответствует точке глобального минимума функции f( x), следовательно, наиболее вероятное положение точки x в результате достаточно длительного поиска – это положение глобального минимума.

Упражнение 1. Сравнить качественно траектории поиска минимума функции f( x)=4( x₁-5)² + ( x₂- s)²  различными методами случайного поиска. (Как это предполагается делать? )

Упражнение 2. Показать, каким образом происходит изменение траекторий поиска минимума функции f( x) = x₁² + x₂² – cos18 x₁ – cos18 x₂ методом случайного поиска с направляющим конусом при изменении параметров y, h_раб, считая, что m достаточно велико. ( Как это сделать? )

 

Похоже, разд.5.5 это запись конспекта лекций, прочитанного кем-то (Заниным? ). Нуждается в кардинальной редакции.

В, В,!! У нас же есть пособие «Решение задач матпрограммирования в среде Delphi», в котором приведены как реализации алгоритмов, так и сведения о вычислении производных, оценках точности и т.п. Этим пособием пользуются наши студенты при выполнении курсовых работ.

Как предплогается выполнять упраженеия по построению линий уровня? – Матлаб?

Как решить упражнение 2 выше? В Матлабе нет случайного поиска вообще, а из методов первого порядка – только многогранник. О методе конфигураций, похоже все давно забыли по причине налиния многогранника.

Недостатки вроде «больших» затрат машинного времени следует оставить в прошлом веке. – Все относительно. 

Изложение методов случайного поиска – полный отстой.

С уважением, А.В.Ф.

⇐ Предыдущая1234567

Поделиться: