1
|
|
|
|
|
0
|
|
|
0
|
|
| | | 0 | 1 | 2 | 3
|
|
Выражение (17) может быть задано следующим десятичным вектором:
Переход от чисел к правилам осуществляется последовательно с
учетом формулы: продукционное правило = элемент вектора длина правила.
Таким образом, преобразование вектора p в формулу выглядит так:
и так далее.
Данный метод был применен ко многим различным задачам, однако, в
задачах по нахождению управления систем динамическим объектом он еще не
использовался.
Метод сетевого (СО) оператора был создан в 2006 году профессором
А.И. Дивеевым [9-11] в том числе и для решения задачи синтеза управления. В нём
учтены специфические особенности этого класса задач, вследствие чего
пространство поиска было сужено. Поэтому его работа в рассматриваемом классе
задач требует меньшей вычислительной мощности по сравнению с другими способами
символьной регрессии.
Сетевой оператор - это ориентированный ацикличный граф с
определенными свойствами. Узлы-источники содержат значения переменных и
параметров упорядоченного множества терминальных символов . Каждому узлу, не являющемуся источником, соответствует бинарная
операция из упорядоченного множества бинарных операций . Элементы множества должны быть коммутативны и ассоциативны. На дугах указываются
унарные операции из упорядоченного множества .
Для построения СО необходимо представить математическое выражение
в виде последовательности бинарных и унарных операций. Внешняя операция должна
быть бинарная. Аргументом унарной операции может быть только бинарная операция
или элемент множества . Аргументами бинарной операции могут быть только унарные
операции, у которых аргументы в виде параметров или переменных различны.
Реализовать метод СО программным кодом можно, преобразовав граф в
целочисленную верхнетреугольную матрицу специального вида . На диагонали располагаются индексы
элементов множества , а над диагональю элементы или 0, которые обозначают отсутствие дуг.
Для поиска решения используется генетический алгоритм, работающий
на множестве вариаций базисного решения. Базисное решение представляет собой
математическое выражение, представленное в виде матрицы и описывающее систему управления, составленную инженером на
основе опыта и здравого смысла. Для описания вариации используется вектор из
четырех элементов , где - номер вариации, - номер строки, - номер столбца, - номер операции.
Параллельно с популяцией базисных решений операторы скрещивание и
мутация модифицируют также популяцию параметров, входящих во множество .
2.3 Принцип
действия метода аналитического программирования
Ещё один метод символьной регрессии - аналитическое
программирование (АП). Он был создан польским профессором И. Зелинкой [12-14] и
является развитием ГП и ГЭ.
Данный метод был протестирован на многочисленных
экспериментах различных направлений, что показало его способность решать те же
задачи, что и ГП и ГЭ, но также как и ГЭ он ещё не применялся к задаче синтеза
управления.
Главным преимуществом АП по сравнению с другими методами
является то, что для его реализации можно использовать не только различные
компьютерные языки, но также и различные эволюционные алгоритмы.
Для поиска подходящей формулы вводятся множества функций
различной арности, операторов и терминальных символов произвольной размерности.
Например:
Состав этих функций определяется согласно поставленной задаче
и выбранному языку программирования, а также может содержать не только
стандартные функции, но и пользовательские.
Все вместе элементы этих множеств объединяются в одно общее
множество, называемое обобщённое функциональное множество (ОФМ или GFS - general functional set). Оно является упорядоченным и имеет
вложенную структуру, т.е. состоит из упорядоченных подмножеств функций в
соответствии с числом их аргументов . Здесь индекс означает арность функций подмножества. Так,
например, будет содержать функции, требующие один аргумент, - два аргумента и так далее. составляют терминальные символы и константы.
В эволюционном алгоритме в качестве особи выступает целочисленный
вектор, составленный из порядковых номеров функций, входящих в обобщенное
функциональное множество. Этот вектор «переводится» в выражение путём
поэлементной замены числа на функцию, оператор или терминальный символ.
Может сложиться такая ситуация, что будут использованы все числа
из вектора хромосомы, а некоторые функции или операторы ещё не содержат
требуемого количества аргументов. Тогда алгоритм вернется к «местам пропусков»
и поочередно заполнит их элементами множества .
Для того чтобы избежать некорректных решений, программа содержит
процедуры, обрабатывающие исключительные ситуации.
К ним можно отнести:
1. патологические функции (без аргументов,
зацикливающиеся…)
. функции с мнимой или действительной частью (если их
не ожидалось)
. бесконечность в функциях (деление на 0, …)
. «замороженные» функции (требуют очень много времени,
чтобы получить конечный результат).
. и так далее.
Рис. 4. Преобразование методом АП
Пример преобразования целочисленного вектора в формулу приведён
на рисунке 4.
Для этого случая подмножества ОФМ имеют следующий вид:
На сегодняшний день существует три основные версии АП. Первая
и основная версия называется AP_basic. Она продемонстрирована на примере. Вторая
версия - AP_meta (АП с метаэволюцией) - отличается от предыдущей версии способом
определения констант. Если первоначально использовались константы из
терминального множества, то в AP_ meta в подмножестве нулевой арности имеется только
одна константа K. При выводе формулы, все К индексируются по порядку и затем
оцениваются с помощью того же самого или любого другого эволюционного
алгоритма. Последняя версия - AP_nf. В ней К оптимизируется подходящим методом.
Стоит отметить, что метод АП может быть использован не только
для поиска математических и логических выражений, но и для написания
компьютерных программ.
Нужно добавить в ОФМ элементы синтаксиса любого выбранного
для исполнения языка программирования. Тогда метод начнёт выстраивать
собственный алгоритм для решения поставленной задачи с указанными критериями.
В современной науке очень важно развитие этого подхода,
поскольку он может быть применен для создания интеллектуальных систем
управления.
3.
Вычислительный эксперимент
3.1 Методы,
использованные в программе
В данной дипломной работе был программно реализован метод
аналитического программирования и применён к задаче структурно-параметрического
синтеза управления системы динамическим объектом.
Программа была разработана на языке Python версии 2.7 в среде Eclipse Juno с использование
библиотеки для построения графиков Matplotlib.
В качестве метода поиска решения был выбран генетический
алгоритм с эволюционной стратегией типа (μ, λ).
3.2 Генетический
алгоритм с эволюционной стратегией типа (μ,
λ)
Особенность этой стратегии генетического алгоритма (ГА)
является то, что поколение родителей μ объединяется с
поколением потомков λ. Затем из получившегося
множества выбираются лучшие особи в количестве равном размерности μ.
Положительным качеством данного подхода является то, что
самые приспособленные особи гарантированно переходят из поколения в поколение,
что повышает уровень адаптации популяции в целом.
На первом шаге алгоритма генерируется начальное поколение . Оно состоит из бинарных строк - хромосом со случайным набором
признаков , , где - длина популяции.
Каждое - это целое число, представленное в двоичном коде. Оно является
порядковым номером элемента множества . Поэтому для того, чтобы не вышло за пределы , на него накладываются ограничения.
Помимо этого, к концу вектора хромосомы добавляется два числа,
которые не ограничиваются количеством элементов , а только количеством бит для двоичного представления. Они играют
роль параметров искомого выражения и не участвуют в обмене частей генома при
скрещивании.
Такой способ определения параметров выражения был выбран с целью
сократить множество терминальных символов, поскольку слишком большая
размерность множества по сравнению с другими могла привести к уменьшению разнообразия в
популяции.
На втором шаге в соответствие с целевыми функциями рассчитывается фитнесс (приспособленность) каждой хромосомы. При этом необходимо
ограничить управление .
В многокритериальных задачах часто невозможно найти особь,
представляющую оптимальное по всем критериям качества решение. Однако всегда
существуют наилучшие возможные варианты. Пригодность решения можно «установить»
по Парето [15].
Пусть существует два решения и . Говорят, что доминирует по Парето, если не хуже по всем критериям и хотя бы по одному критерию превосходит . Множество решений, которые доминируют и превосходят другие по
различным критериям, представляет фронт Парето (границу Парето).
Элементы этого множества обладают таким показателем как ранг. Ранг
особей, расположенных непосредственно на границе, равен 1. Если убрать эти
особи и определить новую границу, то составляющие её особи будут иметь ранг 2 и
так далее.
Задача содержит две целевые функции, определяющие критерии
качества управления. Первым критерием является быстродействие, вторым -
точность. Значение фитнесс-функции определяется исходя из ранга по Парето
выбранного решения, который определяется с помощью методов и класса .
Третий шаг алгоритма - отбор особей для формирования нового
поколения функцией . Родителями становятся только те хромосомы, у которых фитнесс
выше или равен вероятности , задаваемой случайным образом на каждой итерации селекции.
На четвертом шаге отобранные особи скрещиваются (функция ), для получения более приспособленного потомства. Этот процесс
представляет собой обмен участков хромосом между родителями. Вначале необходимо
объединить подсписки бинарных строк (функция ) так, чтобы хромосомы имели вид: . В данном случае был использован одноточечный кроссовер, поэтому
для каждой пары родителей случайным образом генерируется индекс точки скрещивания.
Далее хромосомы обмениваются частями, стоящими после точки разрыва, и образуют
две новые особи, которые записываются во множество .
Рис. 5. Пример операции скрещивания
На рисунке 5 изображен пример скрещивания при точке разрыва с
индексом 5.
Следующим шагом алгоритма является позиционная мутация (функция ). Это такой вид мутации, при котором вероятность мутации
уменьшается пропорционально позиции гена в хромосоме. Он был выбран в связи с
особенностью метода аналитического программирования. Чем ближе гены к началу
вектора, тем большее влияние они оказывают на результат.
Рис. 6. Блок-схема ГА с эволюционной стратегией (μ, λ)
На шестом шаге особи поколений и объединяются в единое множество . Из него выбираются наиболее приспособленные хромосомы, которые и
составят новое поколение. Количество, выбранных особей равно числу особей в P. Далее алгоритм повторяется со второго шага.
Критерием останова в данном случае служит заданное количество
поколений.
На рисунке 6 приведена блок-схема описанного алгоритма.
3.3 Функция
метода аналитического программирования
В программе преобразование целочисленного вектора из
популяции в математическое выражение осуществляется с помощью функции
где - это целочисленный вектор, а - это множество, содержащее подмножества функций различной
арности, включая параметры и терминальные символы
Для решения поставленной задачи для всех объектов управления было
выбрано подмножество параметров и терминальных символов вида:
где и - соответственно координаты системы и , а и - параметры управления, генерирующиеся в «хвосте» хромосом.
Подмножество функций, требующих один параметр:
где - аналог математической формулы
|
(20)
|
функция - аналог математической формулы
|
(21)
|
с некоторыми ограничениями,
а - аналог
(21)
|
|
с некоторыми ограничениями.
3.4 Метод
решения обыкновенных дифференциальных уравнений
Для интегрирования систем управления в форме Коши применен
численный алгоритм решения ОДУ - метод Рунге-Кутты четвёртого порядка [16]
(функция ).
Приближенное значение в последующих точках вычисляется по
итерационной формуле:
|
(22)
|
где
Этот метод имеет четвёртый порядок точности, т.е. суммарная ошибка
на конечном интервале интегрирования имеет порядок . Ошибка на каждом шаге порядка .
3.5 Осциллятор
Дуффинга
Программа осуществляет поиск оптимального управления для
динамического объекта в виде осциллятора Дуффинга.
Осциллятор Дуффинга - это простейшая одномерная нелинейная
система, которую можно представить обыкновенным дифференциальным уравнением
второго порядка
|
(27)
|
где
- коэффициент демпфирования,
- показатель жёсткости,
- показатель нелинейности.
В форме Коши данная модель при единичных параметрах выглядит
следующим образом:
|
(28)
|
Управление представляет собой функцию от координат состояния
|
(29)
|
и ограничено
3.6 Результаты
эксперимента
Исследование метода аналитического программирование для
структурно-параметрического синтеза управления происходило на системе ОДУ (28).
Эксперименты производились из различных начальных точек со
следующими параметрами:
- число итераций генетического алгоритма,
- количество особей в популяции,
- длина хромосомы,
- шаг интегрирования,
- терминальная точка,
- максимальное время моделирования,
- точность попадания в терминальную точку.
Среднее время работы одного эксперимента составило 824 секунды.
На основании проведенных опытов были получены следующие
результаты.
Для начальной точки результаты приведены в таблице 3.
Таблица 3. Результаты для начальной точки [1. 0,1.0]
№
|
Значение
функционала
|
Функция
|
1
|
[2.62, 0.00078]
|
|
2
|
[2.63, 0.00077]
|
|
3
|
[2.33, 0.0341]
|
|
4
|
[2.4,
9.16987e-05]
|
|
5
|
[2.32, 0.00983]
|
|
6
|
[3.65,
2.10036e-05]
|
|
7
|
[2.37, 0.00618]
|
|
8
|
[2.69, 0.00094]
|
|
9
|
[2.69, 0.00094]
|
|
10
|
[2.33, 0.00876]
|
|
11
|
[2.69, 0.00094]
|
|
12
|
[2.3, 0.02557]
|
|
13
|
[2.25,
2.72759e-05]
|
|
14
|
[2.24, 0.00064]
|
|
15
|
[2.37, 0.00173]
|
|
Лучшим оказалось управление, определяемое по функции:
|
(30)
|
со значениями функционалов:
|
(31)
|
|
(32)
|
Графики фазовых траекторий функции (30) с другими начальными
условиями приведены на рисунках 9-12.
Графики управления функции (30) с другими начальными
условиями приведены на рисунках 13-16.
Для начальной точки результаты приведены в таблице 4.
Таблица 4. Результаты для начальной точки [1. 0,1.5]
№
|
Значение
функционала
|
Функция
|
1
|
[3.96, 4.55440e-07]
|
|
2
|
[5.3, 0.00219]
|
|
3
|
[3.87,
8.31192e-05]
|
|
4
|
[5.24,
0.00013]
|
|
5
|
[5.3, 0.00219]
|
|
6
|
[5.7,
1.67794e-05]
|
|
7
|
[4.95, 0.00092]
|
|
8
|
[3.4, 4.87005e-06]
|
|
9
|
[5.56, 0.01320]
|
|
10
|
[4.37, 0.02912]
|
|
11
|
[4.13, 0.00025]
|
|
12
|
|
13
|
[4.28, 0.00018]
|
|
14
|
[3.96,
9.81495e-08]
|
|
15
|
[5.3, 0.00219]
|
|
|
|
|
|
На рисунках 17 и 18 соответственно представлены графики
фазовой траектории и управления, которое определяется по формуле:
|
(33)
|
со значениями функционалов:
Графики фазовых траекторий функции (33) с другими начальными
условиями приведены на рисунках 19-22.
Графики управления функции (33) с другими начальными
условиями приведены на рисунках 23-26.
Для начальной точки результаты приведены в таблице 5.
Таблица 5.
Результаты для начальной точки [2. 0,1.0]
№
|
Значение
функционала
|
Функция
|
1
|
[5.5, 0.00157]
|
|
2
|
[5.53,
0.00087]
|
|
3
|
[5.52,
5.36697e-05]
|
|
4
|
[6.27, 0.03468]
|
|
На рисунках 27 и 28 соответственно представлены графики
фазовой траектории и управления, которое определяется по формуле:
|
(36)
|
со значениями функционалов:
Графики фазовых траекторий функции (36) с другими начальными
условиями приведены на рисунках 29 - 32.
Графики управления функции (36) с другими начальными
условиями приведены на рисунках 33-36.
Для начальной точки результаты приведены в таблице 6.
Таблица 6. Результаты для начальной точки [2. 0,2.0]
№
|
Значение
функционала
|
Функция
|
1
|
[5.47, 0.0027]
|
|
2
|
[5.53, 3.00297e-05]
|
|
3
|
[5.72,
0.0001]
|
|
4
|
[5.69, 0.02601]
|
|
5
|
[5.79, 0.02954]
|
|
На рисунках 37 и 38 соответственно представлены графики
фазовой траектории и управления, которое определяется по формуле:
|
(39)
|
со значениями функционалов
Графики фазовых траекторий функции (36) с другими начальными
условиями приведены на рисунках 39-42.
Графики управления функции (36) с другими начальными
условиями приведены на рисунках 43-46.
Для начальной точки результаты приведены в таблице 7.
Таблица 7. Результаты для начальной точки [2. 0,3.0]
№
|
Значение
функционала
|
Функция
|
1
|
[7.38, 0.01016]
|
|
2
|
[8.27,
0.03115]
|
|
3
|
[10.0,
0.11827]
|
|
4
|
[7.91,
0.02802]
|
|
5
|
[8.72, 0.03251]
|
|
На рисунках 47 и 48 соответственно представлены графики
фазовой траектории и управления, которое определяется по формуле:
|
(42)
|
со значениями функционалов
|
(43)
|
|
(44)
|
Рис. 47. Фазовая траектория
|
Рис. 48. График управления
|
Рис. 49. Начальная точка =[1. 0,1.0]
Рис. 50. Начальная
точка =[1. 0,1.5]
|
|
Рис. 51. Начальная точка =[2. 0,1.0]
Рис. 52.
Начальная точка =[2. 0,2.0]
|
|
Графики фазовых траекторий функции (42) с другими начальными
условиями приведены на рисунках 49-52.
Графики управления функции (42) с другими начальными
условиями приведены на рисунках 53-56.
Рис. 53. Начальная точка =[1. 0,1.0]
Рис. 54.
Начальная точка =[1. 0,1.5]
|
|
Рис. 55. Начальная точка =[2. 0,1.0]
Рис. 56.
Начальная точка =[2. 0,2.0]
|
|
Множество решений (функции управления), полученное в
результате экспериментов достаточно разнообразно. Однако встречались также
одинаковые функции или мало отличающиеся, но имеющие одинаковые значения
функционалов. Такие решения могут быть притягивающими точками в пространстве
функций.
Заключение
В рамках дипломной работы был разработан программный
комплекс, позволяющий синтезировать управление динамическим объектом с помощью
метода аналитического программирования, использующий генетический алгоритм с
эволюционной стратегией (μ, λ). Для его тестирования был
проведён ряд экспериментов на примере осциллятора Дуффинга.
Целью экспериментов являлось перемещение системы из заданного
начального условия в терминальную точку с выполнением критериев точности и быстродействия.
Исследовано поведение синтезированной системы при различных
начальных условиях. Проведено большое количество экспериментов, из которых
отобраны наилучшие функции.
В результате получены графики фазовых траекторий и управлений, на
которых видно, что система работает в соответствие с требованиями качества.
Таким образом, было показано, что метод аналитического
программирования применим к задаче структурно-параметрического синтеза
управления.
Дальнейшим направлением развития данной работы могут послужить
следующие исследования и доработки программы:
1. Определение функции управления объектом для множества
начальных точек.
. Встроенные условные конструкции и циклы для создания
программного кода.
Список литературы
синтез регрессия параметрический динамический
1. Беллман
Р. Динамическое программирование. М.: Изд-во Иностранная литература, 1960 г.
400 стр.
2. Понтрягин
Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория
оптимальных процессов. 4-е изд. М.: Наука, 1983 г. 393 стр.
. Летов
A.M. Математическая теория процессов управления. М.: Наука, 1981 г. 256 стр.
. Калман
Р., Арбиб М., Фалб П. Очерки по математической теории систем. М.: Мир, 1971 г.
400 стр.
. Красовский
A.A. Системы автоматического управления полетом и их аналитическое
конструирование. М.: Наука, 1973 г. 558 стр.
6. Zelinka, I., Nolle, L., Oplatkova, Z. Analytic Programming
- Symbolic Regression by Means of Arbitrary Evolutionary Algorithms / Journal
of Simulation. Vol. 6 No 9. Pр. 44-56.
. Koza J.R. Genetic Programming: On the Programming of
Computers by Means of Natural Selection. Cambridge: MIT Press, 1992, 840 p.
. O’Neill M., Ryan C., Grammatical Evolution, IEEE
Transactions on Evolutionary Computation 5 (4), 2001, pp. 349-358.
9. Дивеев
А.И. Численный метод сетевого оператора для синтеза системы управления с
неопределенными начальными значениями // Известия РАН. Теория и системы
управления, 2012, №2, с. 63-78.
. Дивеев
А.И., Софронова Е.А. Структурно-параметрический синтез системы управления
методами генетического программирования // Труды Седьмого международного
симпозиума «Интеллектуальные системы» (INTELS'2006) Россия. Краснодар,
КИИЗ 26-30 июня 2006. М.: RUSAKI. С. 66-68.
. Дивеев
А.И., Софронова Е.А. Метод генетического программирования для структурно-параметрического
синтеза систем управления // Тезисы докладов Третьей международной конференции
по проблемам управления Россия. Москва. 20-22 июня 2006. Изд-во ИПУ. Т.1. С.
26.
12. Zelinka I., Analytic programming by Means of Soma Algorithm
in Proceedings of the 8th International Conference on Soft Computing
(MENDEL-02), Brno, Czech Republic: VUT v Brno, 2002, pp. 93-101.
. Zelinka I., Oplatkova Z.: 2003: Analytic programming -
Comparative Study. CIRAS’03, The second International Conference on
Computational Intelligence, Robotics, and Autonomous Systems, Singapore, 2003,
560 p.
. Zelinka, Ivan, Artificial Intelligence in The Problems of
Global Optimization (Czech Ed.) BEN, 2002, 190 p.
. Godfrey, Parke, Shipley, Ryan; Gryz, Jarek (2006).
«Algorithms and Analyses for Maximal Vector Computation», 2006, VLDB Journal
16: pp. 5-28.
16. Бахвалов
Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. - М.: Бином, 2001 г. 621
стр.