3.3.2.2. Случайный поиск с нелинейной тактикой

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

Рис. 3.3.6. Граф алгоритма случайного поиска с нелинейной тактикой.

Граф алгоритма с нелинейной тактикой показан на рис. 3.3.6. Как видно, он проще алгоритма с линейной тактикой. Здесь успех происходит за счет того, что используются только те случайные шаги, которые удачны, а неудачные устраняются (исправляются) с помощью операции возврата.

Рекуррентная формула алгоритма имеет вид

Рассмотрим область целесообразного использования этого алгоритма. Элементарный анализ показывает, что его следует применять в ситуациях со значительной нелинейностью, когда нецелесообразно повторять удачные шаги, так как вероятность повторного успеха (3.3.13) мала Такой бывает ситуация в районе экстремума или на дне оврага минимизируемой функции. Именно в этих случаях нелинейная тактика имеет существенное преимущество перед линейной.

Сравним этот алгоритм с известным детерминированным методом поиска — градиентным алгоритмом:

где у — определенный коэффициент, — градиент функции в точке Будем сравнивать эти алгоритмы по удельным потерям на поиск, т. е. потерям «на единицу успеха». Потери обычно связаны с вычислением значения минимизируемой функции и их естественно измерять количеством вычислений этой функции. Так, для реализации одного шага случайного поиска необходимо вычислить т. е. дважды определить значение функции (3.3.11), следовательно, затраты будут равны двум единицам. Каждый шаг по методу градиента (3.3.21) требует вычислений значений функции Действительно, для оценки частных производных градиента (3.3.14) необходимо вычислить

где — база оценки, а орт. Очевидно, что успех одного этапа обоих

алгоритмов будет разным: успех случайного поиска,

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

Разделив потери на успех, получим удельные потери на поиск поведение которых в функции размерности задачи показано на рис. 3.3.7 для обоих алгоритмов. Хорошо видно, что при решении простых задач, т. е. при более целесообразно применять метод градиента (МГ), а для задач большой размерности лучше случайный доиск (СП), у которого потери на поиск пропорциональны Любопытно, что критическая сложность разграничивающая оба метода, невелика Для линейного объекта

Интересно рассмотреть влияние близости к экстремуму на сравнительную эффективность обоих алгоритмов. Пусть — расстояние до экстремума Тогда на плоскости параметров и имеет место разделение на зоны целесообразного использования алгоритмов по критерию удельных потерь на поиск, показанное на рис. 3.3.8. Из рисунка видно, что зона случайного поиска достаточно велика и его лучше использовать для приближенного решения сложных задач. Уточнять решение следует методом градиента. Процесс оптимизации заключается в движении по вертикали (см. рис. 3.3.8) с переходом из зоны случайного поиска (СП) в зону метода градиента (МГ).

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

Выше уже говорилось, что случайный поиск можно рассматривать как способ сбора информации о поведении минимизируемой

Рис. 3.3.7. Поведение потерь на поиск при изменении размерности оптимизируемого объекта. СП — случайный поиск (с нелинейной тактикой), МГ — метод градиента.

Рис. 3.3.8. Области целесообразного применения алгоритмов случайного поиска (СП) и метода градиента (МГ).

мой функции. Такой информацией облагает оценка градиента, указывающего направление наиболее интенсивного увеличения функции. Поэтому естественно рассмотреть алгоритмы случайного поиска, использующие стохастические оценки градиента. Рабочий шаг при этом организуется так же, как и у градиентного алгоритма (3.3.21):

где стохастическая оценка градиента. Способ такой оценки и отличает алгоритм поиска.