автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эволюционные алгоритмы решения задач управления и идентификации для динамических систем

На правах рукописи

РЫЖИКОВ ИВАН СЕРГЕЕВИЧ

ЭВОЛЮЦИОННЫЕ АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ УПРАВЛЕНИЯ И ИДЕНТИФИКАЦИИ ДЛЯ ДИНАМИЧЕСКИХ

СИСТЕМ

05.13.01 - Системный анализ, управление и обработка информации (космические и информационные технологии)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

12 /Л 2013

Красноярск — 2013 005543282

005543282

Работа выполнена в ФГОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва», г. Красноярск

Научный руководитель: доктор технических наук, профессор

Семенкнн Евгений Станиславович

Официальные оппоненты: Комарцова Людмила Георгиевна

доктор технических наук, профессор, Калужский филиал Московского государственного технического университета им. Н.Э. Баумана, профессор кафедры «Компьютерные системы и сети»

Терсков Виталий Анатольевич

доктор технических наук, профессор, Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, профессор кафедры безопасности информационных технологий

Ведущая организация: ФГБОУ ВПО «Национальный

исследовательский Томский политехнический университет», г. Томск

Защита состоится 20 декабря 2013 г. в 14 часов на заседании диссертационного совета Д 212.249.02, созданного на базе ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева» по адресу 660014 г. Красноярск, проспект имени газеты «Красноярский рабочий», 31.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева.

Автореферат разослан « 20 » ноября 2013 г.

Ученый секретарь

диссертационного совета — Александр Алексеевич Кузнецов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Современные подходы к решению задач оптимизации становятся все более эффективными в нахождении решений, но при этом сложность задач тоже возрастает. Известные методы активно развиваются, совершенствуются и сравниваются между собой, разрабатываются и исследуются алгоритмы, основанные на вновь появляющихся парадигмах. Особый интерес продолжают вызывать эволюционные методы оптимизации и иные методы, суть которых заимствована из природы. Надежность подобных подходов и их модификаций в нахождении желаемого решения сложных задач поиска экстремума демонстрируется в различных работах, в которых решаются, приведенные к экстремальным задачи различной природы. До сих пор одним из наиболее известных и эффективных методов является метод эволюционных стратегий. Как показано в работах по исследованию методов оптимизации, разные алгоритмы могут по-разному проявлять себя при решении задач: определенный класс алгоритмов быстрей и точней находит решение некоторых задач, но для других задач данный класс менее эффективен. На настоящий момент существует большое множество модификаций алгоритма эволюционных стратегий, как для решения задач вещественной оптимизации, так и для комбинаторных задач. Тестирование эвристических алгоритмов происходит на различных наборах целевых функций и заключается в некоторой оценке эффективности нахождения решения. Более того, развиваются методы генерирования специальных тестовых целевых функций для проверки эвристических алгоритмов оптимизации, разрабатываются модификации поисковых алгоритмов или их операторов для повышения эффективности в решении задач определенного класса. Все это свидетельствует о широкой распространенности эвристических алгоритмов и растущему интересу к ним.

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

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

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

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

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

Поставленная цель определила следующие задачи:

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

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

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

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

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

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

Научная новизна результатов диссертационной работы состоит в следующем:

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

уравнения по зашумленным измерениям выхода системы, а так же в условиях малой выборки;

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

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

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

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

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

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

предназначена для решения задачи идентификации и позволяет искать модель в виде дифференциального уравнения с максимальным порядком равным 10 по данным наблюдений. Программная система апробировалась на решении задачи идентификации изменений концентрации гексадекана для реакции его распада. Вторая и третья системы предназначены для поиска программного управления в виде кусочно-постоянных функций, например, реле, что позволяет решать задачи терминального управления с закрепленным или свободным временем, соответственно. Третья система апробирована на решении задачи перевода космического аппарата с одной геостационарной орбиты на другую за конечное время. Четвертая система разработана для параллельной идентификации параметров дифференциальных уравнений различных порядков. Разработано множество программных модулей по решению задач терминального управления в различных постановках, оптимального управления и идентификации для вычислительной среды MATLAB.

Реализация результатов работы. Разработанный алгоритм решения задач оптимизации применялся для идентификации параметров системы сенсоров по их показаниям, что позволило определить ошибку каждого сенсора по фазе и амплитуде (Hochschule Ulm, Ульм, Германия, 2009). -Модифицированный гибридный алгоритм эволюционных стратегий применялся для настройки параметров системы управления в проекте по разработке системы автоматической парковки транспортного средства с прицепом (Hochschule Ulm, Ульм, Германия, 2009).

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

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

Модифицированный алгоритм эволюционных стратегий применялся при решении задачи идентификации параметров аппроксимирующей функции для поля скоростей текущей в сосуде жидкости (Hochshule Ulm, Ульм, Германия, 2013).

Основные защищаемые положения.

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

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

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

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

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

Публикации. По теме диссертационной работы опубликовано 19 работ, из них 6 в изданиях Перечня ВАК и 4 зарегистрированные программные системы.

Апробация работы. Результаты научно-исследовательской работы докладывались и обсуждались на XIV Международной научной конференции «Решетневские чтения» (Красноярск, 2010); IX Всероссийской конференции с международным участием «Молодежь. Общество. Современная наука, техника и инновации» (Красноярск, 2010); на Международной конференции "The 9th International Conference on Informatics in Control, Automation and Robotics (ICINCO), Рим, 2012; на Международной конференции "2nd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), Рим, 2012; на 1-й и 2-й Международных конференциях "International conference on Mathematical Modeling and its Applications", Иркутск, 2012, Красноярск, 2013; на Международной конференции "The 1 Ith International Conference on Adaptive and Natural Computing Algorithms (ICANNGA), Лозанна, 2013; на Международной конференции "10th International Conference on Informatics in Control, Automation and Robotics (ICINCO)", Рейкьявик, 2013; на Пятой международной конференции «Системный анализ и информационные технологии, САИТ-2013, Красноярск, 2013; на ряде молодежных научных конференций.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Рассматривался вариант алгоритма эволюционных стратегий (ц/р, А.) , при этом ц = А,.

Популяция представлена следующим кортежем:

Н = (ор1, яр', , / = 1, ,

где о// , ] = 1,и - набор объективных параметров, которые являются

переменными целевой функции; ^ еЯ.+, _/' = \,п - набор стратегических параметров; п - размерность задачи; N1 - объем популяции.

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

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

дискретную случайную величину ze{0, \},P{z = \) = рп, где рт -

вероятность мутации для каждой пары генов i = \,n. При этом рассматривалась также следующая операция мутации:

j = 1,« : opj = opj + z ■ N(0,spj),

spj=\spj+z-N(0,ï)\.

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

±™к-орГп,Л

0p°ffsprmg _

к-1

где rWj~U\0, l],y' = l,p - непрерывная случайная величина,

распределенная по равномерному закону; оррагет'к - один из выбранных родителей. Аналогично скрещивание осуществляется для стратегических параметров.

В данной работе исследуется гибридный алгоритм эволюционных стратегий, в котором реализована схема улучшения решений, основанная на вероятностном алгоритме покоординатного спуска. Для каждой популяции Nl раз случайным образом выбирается некоторое решение, в котором N2 раз выбирается координата, по которой производится N3 шагов h, в одном из случайно выбранных направлений до тех пор, пока это приводит к улучшению решения. Таким образом, локальное улучшение решения можно представить в следующем виде:

(1): /, : P(ix = 1) =... = Р{ц =Nj) = —,

(2): i2 : P{i2 = 1) =... = P(i2 = n) = -, s, : P(s, = 1) = P(s, = -1) = 0.5,

n

(3): ophc = J opJ'V 7 e J * *2'

J [ °Pl+srhnj = i2, (4): fitness(op'' ) > fitness(oploc) oph = ophc.

В предложенной выше схеме, шаг (3) выполняется раз пока выполняется условие (4). Шаги (1) и (2) представляют собой циклы, выполняющиеся А^ и раз, соответственно.

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

Пусть выход объекта представлен измерениями, формирующими выборку объема то есть {^г;,,/,}, г = , где у, еЯ - измерения выхода динамической системы в момент времени tj, - управляющее

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

ак ■ хт + • х{к'1) +... + а0 ■ х = Ь • м(7), х(0)=х0.

Необходимо по данным выборки определить параметры системы и порядок п дифференциального уравнения, который мы будем считать ограниченным, т.е. п-1<,М,М еЫ. Предполагается, что в канале измерения выхода системы действует аддитивная помеха \-.М{%) = О, О© < со, т.е.

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

Будем считать, что для системы любого порядка ее коэффициент при старшей степени равен 1, таким образом

или

ак ак ак

х(к) + ак-ха 4 +... + а1-х = Ь-и(г).

Тогда, решение задачи идентификации мы будем искать как дифференциальное уравнение порядка т < М, М е N, такое, что

х(т) +ат-х(т~1) +... + агх = а0-и(О, х(О) = х0,

с параметрами а = (0 ... О ат ... ах й0) еЯ", т.е. п=М +1, доставляют экстремум выбранной функции

-ПИП,

аеГ

11{а)=т«х\у,-х(?1)\

—> тш.

а=а аеЯ"

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

ор\ = гоипсОрр'] — \,п, I = 1, , где гоша?(-): Я -»2 - функция, округляющее число до его ближайшего целого.

Рассматривались несколько различных оптимизационных алгоритмов решения поставленной экстремальной задачи: эволюционных стратегий (Е8); гибридного алгоритма эволюционных стратегий (НЕ8); гибридного алгоритма эволюционных стратегий с модифицированными операциями селекции, мутации и рекомбинации (11Е8+гп.гпи1а(лоп); гибридного алгоритма эволюционных стратегий с операцией округления (НЕ8+гоипс1т£); гибридного модифицированного алгоритма эволюционных стратегий с округлением (НМЕ8). Каждый алгоритм был тестирован при различных настройках на 10 системах для каждого из порядков: от 1-го до 10-го, число запусков алгоритма для каждой задачи -20. Для каждой системы результаты усреднены, среднее значение функции пригодности для каждого порядка для каждого алгоритма представлены на рисунке 1.

—•— ЕБ -И-НЕБ

НЕБ+т. ттаНоп —НЕБ+гоипсИпя —«-ьНМЕБ

1 2 3 4 5 6 7

Порядок ОДУ объекта

Рисунок 1. График сравнения средней пригодности для различных алгоритмов решения

задачи идентификации ЛДС.

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

Предложенный подход был апробирован на задаче идентификации параметров и порядка ОДУ, описывающего изменение концентрации гексадекана в реакции его распада. Для этого было произведено 30 запусков алгоритма. Некоторые из найденных решений представлены в таблице 1.

Таблица 1. Примеры найденных моделей по выборочным данным изменения концентрации гексадекана.

Модели величина ошибки (/,)

4.05 • х' + 0.9-х = 1, 0.3022

1.05 • х'+ 0.4 • д; = 1, 0.2834

2.1 • х' + 0.55-х = 1, 0.1822

-1.05-х"-0.15-х"-6.85-х'-0.9-х = 1, 0.2270

-3.4 -х'- 0.45 -х = 0. 0.2020

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

Состояние модели и выборочные данные представлены на рисунке 2.

У>________

5

3

цо

Рисунок 2. Состояние модели изменения концентрации гексадекана и данные

наблюдений.

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

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

ск

— = /(*,И.О. (1)

м

где

/(•): Я" х Л х —» Я" - вектор-функция, непрерывная по своим аргументам;

х е Я" - вектор состояний системы;

кусочно-постоянная функция

управления;

п - размерность системы;

Необходимо найти функцию управления и(Г), которая переводит систему из известного начального состояния х(0) =х° в заданное конечное состояние х(Т) = х за конечное время Т.

Хотя функция управления такого вида характерна только для некоторых задач управления, часто решение задачи оптимального управления предполагает поиск управлений в виде реле, если Гамильтониан линеен по функции управления, т.е. Н(х,р,и) = (х,р) + <р2{х,р)-и, а функция управления имеет ограничения

по модулю |и(0| < А, или Д^ < и(0 < Атах, / є [О, Т].

Если управление задано в виде реле, то представим его в следующем виде:

Г-А, ¿є/,,

«('Н / (2)

[А, іеІ2,

где /¡, 12 представляют собой множества, задаваемые некоторыми точками переключений, в которых функция меняет свой знак, причем ^ и /2 = [О, Т], а А - амплитуда реле.

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

«(0 = | : (3)

> ^ ^ ^ М, '

где /,, г = 1, Ми - интервалы, порожденные точками переключений, причем

ЛГ„ Я, _

[_)/,=[(), Г], = 0; и = {иІ<=Я,і = 1,ІУН} - множество значений,

/=і 1=1

принимаемых функцией управления; Ии - число значений, которое может принимать функция управления.

Пусть Р = : г, < гм, г, е Я* V/ = 0, к, г0 = 0| есть множество точек переключений, а к - параметр, определяющий количество точек переключений. Множество /. = <!/,:/, е N \/г = \,к) является набором

индексов, который используется для описания множества интервалов. Каждый интервал I = 1,Л'Ц для функции управления (3) может быть

определен уравнением = {[^ (гу, гу+1]-//(г,/)>>} еРУ/'}, в котором

1=о

/;('>/) = "I л' . / " специальная функция. Для указанного идеального реле [О, г Ф

(2) может быть использована упрощенная схема представления множества интервалов. В этом же случае, мы можем потребовать изменения знака функции управления в каждой точке переключения, тогда все, что нам потребуется для описания функции управления — знак управления в точке 1 = 0, поскольку выполнение данных условий позволяет полностью описать функцию управления на всем интервале работы системы.

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

- определение точек переключений управления при фиксированном времени работы системы Т;

- определение точек переключения и время работы системы Т.

Постановка задачи может также включать подбор элементов

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

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

Р = |г,: г, < гм,г, 6 П\г, < Т V/ = ОА г0 = о|. (4)

Неявная настройка числа точек переключений обусловлена применением численной схемы интегрирования системы (1). Пусть шаг интегрирования Л , тогда при выполнении условия |т;.+1 - | < /?, интервал (гп >;+1] не повлияет на поведение системы, поэтому может быть исключен.

Пусть множество 5 включает в себя все параметры, определяющие структуру функции управления. Для многоуровневого реле 5 = {Р, а

для идеального 5 = {Р,м(0)}. В случае, если рассматриваемая задача такова, что значения, принимаемые управлением, известны и фиксированы, то множества в случае многоуровневого реле и идеального могут быть заданы, как 51 = {Р,Ь) и 5 = {Р}, соответственно.

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

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

= (5)

где - вектор координат системы (1) в конечный момент времени

Т, при управлении, определенном множеством 5. Если время не фиксировано, то критерий приобретает вид

= (6) Так же существуют ограничения в виде неравенств

|;<гж,#;еД+ VI = й, которые обеспечивают выполнение условия нахождения каждой точки переключения внутри интервала [О, Г]. В случае использования множества Р вместо Р, появляется еще одно ограничение: гк<Т.

Для решения задачи условной оптимизации введем функцию штрафа

Г|Ы| х>о

ср(х) = -Р 11' , и весовой коэффициент а>0. Таким образом, задача [ 0, д: < О

условной оптимизации может быть представлена как задача безусловной оптимизации. Прибавляя к обозначенным выше целевым функциям (5) и (6) функцию штрафа, находим целевые функции для задач управления, в которых все точки переключений лежат внутри интервала регулирования: = + (7)

= + а - ф^ - Г)-»щш, (8)

Чтобы ограничения г, < гм были соблюдены, может быть добавлена

к-1

функция штрафа вида Р-^ф(?;+1 -г,) для любого из критериев (5)-(8),

м

тогда получим целевые функции следующего вида:

(5) = II/ - х(Т)II + р • X ф(г(+1 - г,) ппп, (9)

'15=511 г -гч (+1 I/ ^ М

адг)=\\х -^пиЦ+Р-Еф^-I)-»1??1»

м к-1

вО,,, -гЛ-иг

Ё3(§) = ед + а- ф(г, - Т) + 3 • ЁфСъ, - г,) ш]п

м

Р4 (Ё, Т) = ^ (Б, г) + а • Ф{гкТ) + р • X ф(гм - гЛ тш.

м х

(10) (П) (12)

Таким образом, задача терминального управления была сведена к оптимизации на пространстве вещественных чисел или вещественных и натуральных чисел с целевыми функциями (4), (5), (7)-(12). Указанные функции многоэкстремальны и не являются аналитическими, могут быть вычислены только численно. Учитывая сложность решаемых задач, размерность и неоднородность входных переменных, а так же особенности целевых функций, в качестве основного алгоритма решения задачи был выбран обобщенный гибридный модифицированный метод эволюционных стратегий.

Чтобы уйти от задачи условной оптимизации с неравенствами вида (6), можно представлять точки переключения через объективные параметры следующим образом:

< _

м

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

неотрицательности каждого из параметров: ор1 £0, ¡ = 1,к. Очевидно, что это будет достигаться при выполнения двух условий:

- все объективные параметры стартовой популяции сгенерированы на пространстве Я*;

- операция мутации дополнительно модифицирована так, что объективный параметр не может быть отрицательным:

°Р] = \ор] + г • N(0, )|, у = ТД.

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

гг м \^а<ъ

]г\а'ь)= ^ а , случайную величину, распределенную по закону

Бернулли = 1) = т1р, равномерно распределенную случайную

величину Хг~и (0,1), дискретную случайную величину

Яи:Р{ги -их)-...-Р{ги = и,,) = —. Тогда, если выполняется условие

^и

/г(яр,г2) = 1, то выполняется операция мутации:

opj={\-zl)■opj ■ ги, V/: ор] еИ,

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

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

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

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

я*,о=

2 1 — w(f) — 2 • х2 • х3

X¡ X¡ у

Необходимо перевести объект из начального положения х(0) = (1, 0, 1, 0.785) в конечное х(Т) = ( 1, 0, 1, Г), за конечное время Т, которое необходимо определить. Для данной системы и терминальной задачи управления для случая, когда двигатель может работать в трех режимах, Uu = {-0.005,0,0.005}, решим задачу с критерием (5), выбрав Т — гк, что означает, что время является свободным. После 20 запусков алгоритма было выбрано лучшее решение: Г = 17.2, х(17.2) = (1.009, -0.0065, 1.0048, 17.21). При этом среднее значение целевой функции (5) составило 0.018. В ходе каждого решения целевая функция вычислялась не более 6.25-104 раз.

Функция управления представлена на рисунке 3-А, а состояние системы - на рисунке 3-Б.

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

управлению, можно применить непрямой метод, суть которого изложена ниже.

Д, «( -.---X-,-,-,-.-

-61-1-1_-1-1-1-1-I-1--

О 2 4 6 8 10 12 14 16 18

I

Рисунок 3. Функция управления и(7), реле с тремя уровнями (А). Состояние системы (Б).

Четвертая глава посвящена поиску экстремума в численно-аналитическом методе решения задачи оптимального управления. Рассмотрим метод определения управления через нахождение начальных условий для сопряженных переменных: численно-аналитический метод решения задач оптимального управления для нелинейных динамических систем. В данной главе представлен определенный класс задач: терминальные задачи с закрепленным временем и некоторым критерием оптимальности. Известно, что объект задан нелинейным дифференциальным уравнением, необходимо найти управление, переводящее систему из положения х° в положение хт за конечное время Т и приносящее экстремум функционалу

т

1{х,и) = —> ех1т .

о

Согласно принципу максимума Понтрягина, составим систему с сопряженными переменными р, определим Гамильтониан:

Н = -Г(х,и) + р■ /(х,и,?),

и систему

ГГ Л

— = /(х,м, О, ш

с1р _ —сЩ Л сЫ

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

^ = 0.

¿и

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

Таким образом, задача оптимального управления была приведена к безусловной экстремальной задаче в пространстве Я", где п = сНт(х) -размерность системы.

Пусть х(/)>.Р(0|£(0)=ро - решение системы, при условии, что начальные

условия для сопряженных переменных были рОпределим критерий оптимальности:

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

X, ^ „ (\

-х1 + зт(х0) + ■ соз(х0)

F(x,и) = м2 +Хд

, Т = 5, х =

Í0Л

0 , 1 , ,. V

с/Я „ , , р,' соб(Хл)

По условию стационарности находим -= 0 м(/) = —1-—,

с1и 2

тогда система с сопряженными переменными примет вид

—+5Іп(х0)+'Р' -СС^Хд)

-2 • х0 + р1 ■ соз(х0) - Рі С05(х°) . 8Іп(х0)

-Рі+Ро

Рисунок 4. Функция пригодности для задачи оптимального управления На рисунке 4 видно, что единственным допустимым решением для

рассматриваемой задачи, является область около точки р =

у-22Л;

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

Для решения экстремальной задачи рассматривались некоторые распространенные методы оптимизации: стандартный алгоритм эволюционных стратегий (ЕБ), гибридный модифицированный алгоритм эволюционных стратегий (НМЕв), метод дифференциальной эволюции (ВЕ), стайный алгоритм оптимизации (РвО) и алгоритм эволюционных стратегий с адаптацией ковариационной матрицы (СМА-ЕБ). Для представленной выше задачи приведем оценку вероятности нахождения глобального оптимума разными алгоритмами с их наиболее эффективными

Продемонстрируем многоэкстремальность целевой функции, с помощью графика функции принадлежности изображенного на рисунке 4.

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

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

0,8 т-------—---

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

алгоритмами.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

8. Разработагаше алгоритмы были реализованы в виде программ, исследованы, некоторые программы были зарегистрированы.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ В журналах, рекомендованных ВАК:

1. Рыжиков И.С., Семенкин Е.С. Система нахождения релейного программного управления для динамических объектов // Программные продукты и системы. -№1(Ю1). - 2013. - С. 167-171.

2. Рыжиков И.С., Семенкин Е.С. Об одном методе решения задачи идентификации для линейных динамических систем // Системы

управления и информационные технологии. - №2.1(52). - 2013. - С. 173177.

3. Ryzhikov I., About multiagent system applications for speech recognition problem // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. — Вып. 4 (44). — 2012. - С. 82-85.

4. Ryzhikov I., Automatic linear differential equation identification in analytical form// Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Вып. 4 (44). - 2012. - С. 85-89.

5. Рыжиков И.С. Решение терминальной задачи управления для нелинейных динамических систем// Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Вып. 5 (38).-2011. -С. 85-88.

6. Охорзин В.А., Рыжиков И.С. Гибридный модифицированный метод эволюционных стратегий для решения задач идентификации динамических систем // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - Вып. 4 (30).-2010. -С. 20-23.

В других изданиях:

7. Рыжиков И.С. Об одном методе решения терминальной задачи управления в виде реле // Системный анализ и информационные технологии: Труды конференции САИТ-2013. В 2-х т. - Т. 1. - С. 276-284.

8. Ryzhikov I., Semenkin Е., Okhorzin V. About optimization techniques in application to symbolic-numeric optimal control seeking approach // Informatics in Control, Automation and Robotics: Proceedings of the 10th International Conference ICINCO'2013. - Vol. 1. - P. 268-275.

9. Ryzhikov, I., Semenkin, E. Evolutionary Strategies Algorithm Based Approaches for the Linear Dynamic System Identification // Adaptive and Natural Computing Algorithms. Lecture Notes in Computer Science, Volume 7824. - Springer-Verlag, Berlin, Heidelberg, 2013. - Pp. 477-483.

10. Ryzhikov I., Semenkin E. Modified Hybrid Evolutionary Strategies Method for Termination Control Problem with Relay Actuator // Informatics in Control, Automation and Robotics: Proceedings of the 9th International Conference ICINCO'2012. - Vol. 1. - P. 333-337.

11. Ryzhikov L, Semenkin E. Modified Evolutionary Strategies Algorithm in Linear Dynamic System Identification // Informatics in Control, Automation and Robotics: Proceedings of the 10th International Conference ICINCO'2013. -Vol. 1.-P. 618-621.

12. Ryzhikov I., Semenkin E. The Application of Evolutionary Algorithm for the Linear Dynamic System Modelling // Proceedings of the International Conference SIMULTECH' 2012. - P. 234-237.

13. Охорзин В.А., Рыжиков И.С. Решение терминальной задачи управления в виде многоуровневого реле // Перспективные инновации в науке, образовании, производстве и транспорте '2012": Материалы Международной научно-практической конференции. - Вып. 2. — 2012. -Том 2.-С. 89-93.

14. Охорзин В.А., Рыжиков И.С. Решение экстремальной задачи в численно аналитическом методе решения задач оптимального управления // "Современные направления теоретических и прикладных исследований '2012": Материалы Международной научно-практической конференции. -Вып. 1.-2012.-Том 10.-С. 36-42.

15. Охорзин В.А., Рыжиков И.С. Решение экстремальной задачи в численно аналитическом методе нахождения оптимального управления нелинейными системами // Электронный журнал «Исследовано в России», 072, 2011.-С. 959-965.

Зарегистрированные программные системы:

16. Рыжиков И.С. Структурно-параметрическая идентификация линейного динамического объекта по данным наблюдений. - М.: Роспатент, 2011, № гос. per. 2012611800.

17. Рыжиков И.С. Расчет программного управления для динамических систем с многопозиционным релейным исполнительным механизмом для двухточечных терминальных задач со свободным временем. - М.: Роспатент, 2013, № гос. per. 2013616552.

18. Рыжиков И.С. Расчет программного управления для динамических систем с многопозиционным релейным исполнительным механизмом для двухточечных терминальных задач с фиксированным временем. - М.: Роспатент, 2013, № гос. per. 2013616777.

19. Рыжиков И.С. Программная система решения задачи идентификации линейных динамических систем по данным наблюдений с помощью параллельного алгоритма эволюционных стратегий. - М.: Роспатент, 2013, № гос. per. 2013619507.

Рыжиков Иван Сергеевич Эволюционные алгоритмы решения задач управления и идентификации для динамических систем

Автореферат

Подписано к печати 19.11.2013. Формат 60x84/16 Уч. изд. л. 1.0 Тираж 100 экз. Заказ №

Отпечатано в отделе копировальной и множительной техники СибГАУ 660014, г. Красноярск, пр. им. газ. «Красноярский рабочий», 31