Применение гибридного меметического алгоритма в задачах оптимального управления нелинейными стохастическими системами с неполной обратной связью

Введение

Рассматривается проблема приближенного решения задачи поиска оптимального в среднем управления нелинейными стохастическими системами в условиях неполной текущей информации о координатах вектора состояния [1,2]. Задачи синтеза оптимальных стохастических систем и управления с обратной связью ранее изучались в [3-6], где были сформулированы и доказаны различные условия оптимальности, и разработаны градиентные методы их удовлетворения.

В работе предлагается искать приближенное решение в параметрическом виде путем подбора коэффициентов, входящих в функцию разложения компонент управления. Функция разложения представляет собой сумму произведений элементов систем ортонормированных базисных функций, применяемых в спектральном методе анализа и синтеза нелинейных систем [7], и искомых коэффициентов. Структура функции разложения определяется набором измеряемых координат вектора состояния, используемых в управлении. Ограничения на управление учитываются с помощью применения функции насыщения. Задача нахождения оптимального управления с неполной обратной связью сводится к решению параметрической задачи нелинейного программирования относительно коэффициентов разложения. Для ее решения предлагается применить гибридный меметический алгоритм [8] поиска глобального условного экстремума, относящийся к метаэвристическим [9]. Его применение приводит к получению решения, близкого к оптимальному, за приемлемое время. Эффективность предложенного подхода демонстрируется на задаче оптимальной стабилизации спутника [10].

Постановка задачи

Поведение модели объекта управления описывается стохастическим дифференциальным уравнением Ито:

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

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

Начально состояние определяется плотностью вероятности

где , , , - множество -раз непрерывно дифференцируемых на функций.

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

Число , , определяется условиями информированности. При имеется информация о всех координатах вектора Х, т.е. система будет системой с полной обратной связью, а при – системой, разомкнутой по состоянию. В последнем случае рассматривается так называемое программное управление .

Множество допустимых управлений с неполной обратной связью образуют функции такие, что для всех , функции , удовлетворяют условиям, при которых решение уравнения (1) существует, единственно и является непрерывным марковским процессом. Если плотность вероятности этого процесса , то она удовлетворяет уравнению Фоккера– Планка–Колмогорова

с начальным условием (2).

Здесь - дифференциальный оператор, а .

Обозначим через функционал качества управления

где , - заданные непрерывные функция и функционал, , при фиксированном .

Требуется найти такой элемент , что

Замечание. Если функционал (4) линеен по плотности вероятности, т.е. имеет вид

где непрерывные функции , удовлетворяют условию полиномиального роста [4], искомое управление называется оптимальным в среднем.

Стратегия поиска решения

Будем предполагать, что

  1. Известна оценка множества возможных состояний, которая представляется прямым произведением

  1. Компоненты закона управления ищутся в виде

где

  1. Функции предлагается искать в виде:

где - неизвестные коэффициенты; , , ..., - масштабы усечения по времени и координатам вектора состояния, используемым в управлении.

В качестве функций , , ..., могут использоваться:

  • полиному Лежандра
гдегде
  • косинусоиды:

Стратегия решения заключается в переходе от задачи (5) к задаче поиска минимума функционала с помощью подбора коэффициентов , образующих функцию (7). Для формализации задачи предлагается использовать вектор

который представляет собой гиперстолбцовую матрицу, состоящую из компонент, - векторов :

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

Для нахождения значения критерия (6) для некоторого вектора необходимо:

  1. С помощью начальной плотности вероятности генерировать начальное состояние .
  2. По вектору найти соответствующее управление .
  3. Найти решение уравнения модели (1) с управлением и начальным условием , используя один из численных методов решения стохастических дифференциальных уравнений, например, метод Эйлера-Иосиды:
  4. Повторить пп. 1-3 при , где N - число генерируемых траекторий, и вычислить значение функционала (4) или (6).

В качестве решения задачи выбирается наилучший вектор и соответствующее ему управление.

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

Алгоритм решения задачи

Шаг 1. Подготовительный этап:

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

Шаг 2. Составление целевой оптимизируемой функции. Зададим правило: , ставящее в соответствие вектору некоторое число .

Шаг 2.1. Найти решение уравнения модели (1) с управлением и начальным условием , где каждая компонента управления определяется по формуле: , . Получим пару . Шаг 2.3. Подсчитать значение функционала (4): , . Шаг 2.4. Найти значение критерия . Шаг 2.5. Положить .

Применяя модифицированный гибридный меметический алгоритм к функции : , получим требуемое управление.

Алгоритм модифицированного гибридного меметического алгоритма

Шаг 1. Задать область поиска , максимальное число итераций , размер популяции , параметр – некоторый порог расстояния между точками, – максимальное количество элементов множества , – количество удаляемых решений из множества на каждой итерации, количество итераций и процедур Path-Relinking и локального улучшения соответственно, параметры и , область определения коэффициентов , параметры метода муравьиных колоний или имитации отжига в зависимости от сделанного выбора. Положить – количество элементов в множестве ; – номер итерации.

Шаг 2. Формирование множества .

Шаг 2.1. Случайным образом сформировать популяцию . Для этого с помощью равномерного распределения раз сгенерировать последовательность из случайных точек , , на отрезке . Используя линейное преобразование, каждая точка отображается на соответствующий ей промежуток : . Составляя векторы из точек последовательности при фиксированном , получаем начальных векторов , , , координаты которых имеют равномерное распределение на отрезках , . Таким образом может быть сформирована начальная популяция .

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

Шаг 2.3. Лучшее решение поместить в множество . Положить . Если , то перейти к шагу 2.4. Иначе перейти к шагу 3.

Шаг 2.4. Решение , следующее за в упорядоченном списке и удовлетворяющее условию , поместить в множество . Положить . Положить . Если такого решения нет, то перейти к шагу 2.1.

Шаг 3. Решение задачи локального поиска.

Шаг 3.1. Решить задачу