§ 2.7. Поисковые алгоритмы оптимизации

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

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

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

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

                                        (2.18)

Здесь  — скаляр,  — базисные векторы.

В простейшем случае

; ; …; .                                (2.19)

Тогда градиент можно приближенно оценивать по формуле

,                                                   (2.20)

определяющей так называемую разделенную разность. Заменив в приведенном ранее общем алгоритме оптимизации (2.4) градиент функционала его приближенным значением (2.20), получим поисковый алгоритм оптимизации

.                                               (2.21)

Этот алгоритм оптимизации, который можно представить, помимо рекуррентной формы (2.21), также и в разностной или суммарной форме, соответствует экстремальным дискретным системам.

Рис. 2.5.

Приближенная оценка градиента (2.20), т. е. получение разделенной разности, может осуществляться, например, при помощи синхронного детектора (рис. 2.5), если в качестве поискового колебания принять прямоугольное периодическое воздействие достаточно высокой частоты и амплитуды .

Действительно, легко проверить, что

.             (2.22)

Поэтому структурную схему экстремальной дискретной системы можно представить в виде, показанном на рис. 2.6. Обычно .

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

В основу алгоритмов оптимизации могут быть положены и иные виды поиска, которые широко применяются в экстремальных системах. В частности, иногда может оказаться удобным осуществлять поиск, изменяя  не «в обе стороны», как ранее:  и , а только «в одну»:  либо . В этом случае взамен (2.20) определяются разделенные разности вида

                        (2.23)

где  — вектор, все компоненты которого одинаковы.

Рис. 2.6.

При вычислении  или  вместо двух шагов производится один шаг.