Алгоритмические методы оптимизации и адаптации

Лекция. Алгоритмические методы оптимизации и адаптации

В некоторых задачах оптимизации объектов требуется определить либо вектор оптимальных управлений U^o, либо вектор параметров оптимальной настройки регулятора К°. При этом критерий качества, характеризующий оптимальный режим работы объекта, представляет собой функцию многих переменных J©, где вектором обозначены векторы искомых управлений или параметров.

В задачах адаптивного управления также требуется определить либо вектор управлений U^o (T_i), либо вектор параметров самонастройки регулятора на интервалах .

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

J © = Q (X, С);(1).

J © = М_х {Q (X, С)},(2).

где X — вектор координат состояния; М_х — символ математического ожидания по множеству реализаций вектора X.

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

(3).

Если функционал J© допускает дифференцирование по вектору С, то он достигает экстремума при таких значениях вектора С°, для которых.

(4).

Решение задачи оптимизации аналитическими методами дает аналитические выражения для искомых векторов управлений или параметров. Однако эти методы пригодны для решения относительно простых задач.

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

Регулярные алгоритмы в задачах на безусловный экстремум. Основная идея решения уравнений (4) итеративными методами состоит в следующем. Уравнение (4) записывается в виде.

(5).

где — некоторый скаляр.

На основании (5) вектор С°, соответствующий минимуму J ©, ищется с помощью последовательных приближений или итераций вида.

(6).

Значение определяет величину очередного шага по градиенту и в общем случае зависит от номера шага k и векторов С (m), где.

т = k — 1, k — 2, …, 0.

Если выполняются условия сходимости, то для любого начального вектора С (0) получим.

(7).

Начальное значение С (0) однозначно предопределяет последовательности С(k) для детерминированных задач [см. критерий (1)], поэтому итеративные методы, определяемые рекуррентным соотношением (6), называют регулярными. Формы регулярных итеративных методов различны в зависимости от .

Беспоисковые алгоритмы. Если рекуррентное соотношение (6) используют для определения оптимального вектора С° в задачах оптимизации, то его называют — алгоритмом оптимизации в рекуррентной форме. Введем первую разность вектора С С (k — 1) = С (k) - С (k — 4),.

после чего вместо (6) запишем разностное уравнение.

(8).

которое называют алгоритмом оптимизации в разностной форме. Просуммируем обе части уравнения (8) от 0 до k, тогда получим уравнение.

(9).

называемое алгоритмом оптимизации в суммарной форме.

Для увеличения скорости сходимости алгоритмов оптимизации вместо скаляра вводят матрицу.

При этом уравнение (8) принимает вид.

(10).

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

Алгоритмы оптимизации (10) различают в зависимости от формы матрицы Г (k):

Если Г (k) = Г = const,.

то получаем алгоритм оптимизации с постоянным шагом, или стационарный алгоритм;

если Г (k) зависит от k, то получаем алгоритм оптимизации с переменным шагом, или нестационарный алгоритм;

если Г (k + k₀) = Г (k),

то матрица Г (k) периодична и алгоритм оптимизации является циклическим.

В общем случае Г (k) может зависеть от вектора С (т), где.

т = k — 1, k — 2, …, 0,.

тогда алгоритм оптимизации (10) имеет «нелинейный» шаг. В зависимости от формы матрицы Г (k, С) различают алгоритмы с нелинейным шагом:

Если Г (k, С) = I (k, С),.

где I — единичная матрица, (k, С) — скаляр, то алгоритм оптимизации называют градиентным;

если Г (k, С) = (k, С).

• -скаляр, выбираемый на каждом шаге из условия минимума функции
• (11)

то алгоритм оптимизации называют алгоритмом наискорейшего спуска.

Дискретному алгоритму в разностной форме (10) соответствует дискретная замкнутая система, блок-схема которой представлена на рис. 1, где МУ — матричный усилитель, определяемый выражением Г (k); ДИ — дискретный интегратор (дигратор); НП — нелинейный преобразователь, определяющий градиент критерия качества В соответствии с уравнением первой разности запишем Следовательно, структурная схема дигратора будет представлять собой элемент запаздывания (ЭЗ) с положительной обратной связью (рис. 2). Для улучшения сходимости алгоритмов оптимизации, обеспечения их устойчивости и уменьшения времени определения С в соответствии с указанной блок-схемой можно применить методы коррекции и оптимизации импульсных систем.

Алгоритмы оптимизации (6), (8), (9) и (10) относятся к одношаговым алгоритмам и являются алгоритмами первого порядка, так как представляются в виде векторного разностного уравнения первого порядка.

Если функционал J © имеет несколько экстремумов, то одношаговые алгоритмы позволяют определить только локальные экстремумы. Поэтому необходимо выполнить расчеты при различных начальных векторах С_i (0) и полученные J (C_i°) сравнить, чтобы определить вектор С°, соответствующий глобальному (абсолютному) экстремуму.

алгоритм оптимизация экстремум.

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

(12).

Где.

.

который при.

s = s₁ = 1.

вырождается в одно шаговый алгоритм (10).

Выбирая а_т (k), a_m (k) и Г (/г), можно добиться того, чтобы алгоритм (12) был малочувствительным к локальным экстремумам. Применение многошагового алгоритма (12) в задачах оптимизации, когда J © имеет единственный экстремум, позволяет повысить помехоустойчивость и ускорить сходимость при определении С⁰.

Дискретным алгоритмам оптимизации можно поставить в соответствие непрерывные алгоритмы. Если, например, в (10) заменить k на t, а разности на производные, то при предельном переходе получим непрырывный алгоритм оптимизации первого порядка в виде векторного дифференциального уравнения первого порядка относительно вектора С (t):

. (13).

Непрерывному алгоритму (13) соответствует непрерывная замкнутая система; ее условная схема аналогична схеме, изображенной на рис. 1, в которой следует заменить Г (k) на Г (t) и дигратор на непрерывный матричный интегратор. Непрерывный алгоритм (13) можно реализовать на АВМ.

Для определения глобального экстремума и улучшения процессово пределения С° в случае единственного экстремума функционала J © можно применить непрерывные алгоритмы высшего порядка в виде векторного дифференциального уравнения s-гo порядка относительно вектора С (t):1.

(14).

где — коэффициенты, которые выбирают так, чтобы обеспечить желаемое качество процесса определения С^o. Алгоритмы высшего порядка (14) могут быть реализованы на АВМ.

Поисковые алгоритмы. На практике встречаются случаи, когда градиент вычислить в явной форме невозможно: функционал J © либо имеет разрывы относительно вектора С, либо недиффиренцируем по С, либо его зависимость от С выражена в неявной форме. В этих случаях используют поисковые алгоритмы оптимизации, наиболее широко применяемые при построении адаптивныхсистем.

При поисковых алгоритмах измеряют функционал или какие-либо величины, косвенно оценивающие градиент. Введем векторы, компонентами которых являются значения функционала при измененных значениях вектора С (k) на величину «пробного шага» g:

(15).

где — базисные векторы:

е₁ = [1 0 … 0]^T; е₂ = [0 1 0… 0]^T; е_n = [00 …0 1]^T.

Введем также вектор, компонентами которого являются значения функционала при неизменных значениях вектора С (k):

.(16).

Тогда градиент можно оценить по формулам при поиске с односторонним «пробным шагом».

(17).

с двусторонними «пробными шагами».

(18).

где — символ оценки градиента по вектору С.

Поисковый алгоритм оптимизации на основании уравнения (18) с учетом (16) запишется как.

Алгоритму (19) соответствует дискретная система, схема которой отличается от схемы, изображенной на рис. 1, наличием генератора поисковых сигналов, формирующих g(k), и устройства оценки градиента. Если шаг g (k) однозначно определяется значением функционала или его градиента, то поиск является регулярным. Если шаг выбирается в произвольном направлении и не зависит от абсолютного значения функционала или его градиента, то поиск является случайным.

Поисковые алгоритмы широко используют в адаптивных системах, особенно в экстремальных. Методы случайного поиска особенно эффективны для многомерных объектов с многоэкстремальными характеристиками.

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

Если указанные ограничения представлены в виде равенств.

g© = 0,.

то в соответствии с методом множителей Лагранжа записывается функционал.

(20).

В этом случае условием минимума являются равенства.

Где.

матрица размерности; = 1, 2, …, n; = 1, 2, …, п.

Алгоритмы оптимизации в задачах на условный экстремум, определяющие С^o и °, на основании (21) запишутся как.

Алгоритмам (22) можно поставить в соответствие непрерывные алгоритмы, записать многошаговые алгоритмы типа (12) и поисковые алгоритмы типа (19).

Алгоритмам (22) соответствует дискретная замкнутая система, схема которой в отличие от схемы, изображенной на рис. 1, будет иметь дополнительный контур для определения вектора (k — 1), необходимого для вычисления .

Если ограничения представлены в виде неравенств.

g©? 0,.

то условия минимума (21) записывают в соответствии с теоремой Куна — Таккера, после чего составляют алгоритмы оптимизации.

Вероятностные алгоритмы. Для вероятностных задач оптимизации критерий качества является статистической оценкой функционала Q (X, С) в виде его среднего значения по множеству реализаций [см. (2)] или по времени [см. (3)]. Уравнения ограничений для таких объектов также представляют средними значениями.

h © = М_х {g (X, С)}? 0.(23).

Задача оптимизации в этом случае состоит в том, чтобы подобрать такой оптимальный вектор С⁰, при котором среднее значение функционала имеет минимум.

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

Рис. 3.

Условие оптимальности (4) для стохастических объектов записывается уравнением.

(24).

в котором неизвестен градиент, а известны лишь реализации .

Если выбрать надлежащим образом матрицу Г (k), то вероятностный алгоритм оптимизации можно представить подобно регулярным алгоритмам в рекуррентной, разностной и суммарной формах соответственно:

• (25)
• (26)

(27).

Вероятностные алгоритмы называют алгоритмами стохастической аппроксимации.

Существенным отличием вероятностных алгоритмов от регулярных является то, что при С = С^o

(28).

в то время как для регулярных алгоритмов.

.

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

(29).

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

.

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

(30).

Алгоритму (30) соответствует дискретная замкнутая система, блок-схема которой представлена на рис. 3.

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