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

Размещено на http://www.allbest.ru/

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

В некоторых задачах оптимизации объектов требуется определить либо вектор оптимальных управлений 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°) сравнить, чтобы определить вектор С° , соответствующий глобальному (абсолютному) экстремуму.

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

Рис. 1

Рис. 2

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

(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)

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

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

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

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

g(С) = 0,

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

(20)

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

(21)

Где

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

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

(22)

Алгоритмам (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) и составлять соответствующие вероятностные алгоритмы в стохастических задачах оптимизации на условный экстремум. Регулярные и вероятностные алгоритмы оптимизации используют для поиска экстремума в экстремальных системах, для определения параметров настройки регуляторов, а также для идентификации объектов в самонастраивающихся системах.

Размещено на Allbest.ru