Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
УДК 517.977.58+004.825+004.023 Шаура
Александр Сергеевич Разработка методов структурно-параметрического синтеза для управления системами
Специальность 05.13.01 - Системный анализ, управление и обработка информации (в наук
е и технике)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук Ижевск - 2012
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Ижевский государственный технический университет имени М.Т. Калашникова
Научный консультант: доктор физико-математических наук, профессор Тененев Валентин Алексеевич
Официальные оппоненты: доктор технических наук, профессор Мурынов Андрей Ильич доктор физико-математических наук, профессор Килин Александр Александрович
Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт машиноведения имени А.А. Благонравова Российской академии наук
Защита состоится 1 ноября 2012 года в 1500 часов на заседании диссертационного совета Д 212.065.06 при ФГБОУ ВПО Ижевский государственный технический университет имени М.Т. Калашникова по адресу: 426069, г. Ижевск, ул. 30 лет Победы, 2, корп. 5.
Отзывы в 2-х экземплярах, заверенные печатью организации, просим направлять по адресу: 426069, г. Ижевск, ул. Студенческая, 7, Ученому секретарю совета Сяктереву В.Н. Тел./факс: (3412)59-05-49;
e-mail: dissovet@istu.ru.
С диссертацией можно ознакомиться в научной библиотеке Ижевского государственного технического университета имени М.Т. Калашникова.
Электронная версия автореферата размещена на официальном сайте Министерства образования и науки Российской Федерации.
Автореферат разослан 28 сентября 2012 г.
Ученый секретарь диссертационного совета кандидат технических наук, доцент В.Н. Сяктерев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность. Задачи структурно-параметрического синтеза возникают при проектировании и разработке технических систем, управлении движущимися объектами, оптимизации производственных и технологических процессов.
Управление сложными системами требует решения оптимизационных задач по нескольким критериям, характеризующихся многоэкстремальностью целевых функций и наличием ограничений. Наряду с задачей нахождения оптимальных параметров важной является задача выбора оптимальной структуры моделей. Известные методы оптимизации не позволяют эффективно решать подобные задачи в общем случае.
В отдельных областях деятельности существуют подходы для решения частных задач синтеза. Так во многих работах отечественных и иностранных исследователей рассматриваются вопросы синтеза РЭА: фильтров, усилителей, СКЦ; проблемы создания строительных конструкций; в работах таких авторов как J. Koza, K.O. Stanley, R.Miikkulainen, S. Nolfi, D. Parisi, F. Gruau, H. Kitano, В.Г. Редько, Ю.Р. Цой - подходы к построению оптимальных нейронных сетей и моделей искусственного интеллекта на основе эволюционных методов.
Большое значение имеют задачи оптимального управления движением мобильных технических систем.
Известные методы узко специализированы и не могут быть использованы для решения задач оптимального синтеза и управления в общем случае.
Применение эволюционных методов дает большие возможности для решения задач оптимизации, позволяет более эффективно справляться с проблемой многоэкстремальности и недифференцируемости функций, осуществлять эффективный перебор при поиске в многомерных пространствах.
В последние годы широкое развитие получили методы Data Mining, в частности деревья решений (E.B. Hunt, J.Marin, P.J. Stone, J.R. Quinlan), и аппарат нечеткой логики (L. Zadeh, T. Takagi, M. Sugeno, E. Mamdani) для моделирования и управления системами. Перспективным направлением стало использование этих технологий в сочетании с эволюционными методами.
Эффективность такого подхода показана в работах J. Koza, F. Herrera, H. Tanaka, N. Yamamoto, Д. Рутковской, В.А. Тененева. Отсутствие единого подхода к решению задач оптимального структурно-параметрического синтеза для управления системами приводит к необходимости сочетать методы различной природы на отдельных этапах построения модели.
Работа направлена на расширение спектра решаемых задач путем построения общего метода структурно-параметрического синтеза, используя возможности эволюционных вычислений и обобщая перспективные идеи и разработки в смежных областях научных исследований.
Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 - Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации, 5 - Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации и 7 - Методы и алгоритмы структурнопараметрического синтеза и идентификации сложных систем паспорта специальности 05.13.01 - Системный анализ, управление и обработка информации (в науке и технике).
Объектом исследования являются структурно-параметрические модели сложных и технических систем.
Предметом исследования являются методы оптимального структурнопараметрического синтеза для управления системами, основанные на применении эволюционных алгоритмов.
Целью диссертационной работы является разработка методов структурнопараметрической оптимизации на основе генетических алгоритмов для управления системами.
Задачи исследования 1. Разработать метод структурно-параметрической оптимизации на основе эволюционного алгоритма, обеспечивающий одновременный поиск наиболее простой структуры и оптимальных значений параметров для решения задач системного анализа, оптимизации, управления, принятия решения.
2. Построить генетический алгоритм для решения задач условной оптимизации, позволяющий непосредственно учитывать ограничения на этапе отбора.
3. Разработать метод структурно-параметрического синтеза нечетких продукционных правил, получаемых на основе деревьев, для построения моделей управления системами.
4. Реализовать разработанные алгоритмы и исследовать их на решении задач управления, структурно-параметрического синтеза и условной оптимизации.
Методы исследования, достоверность и обоснованность результатов. В работе использованы теоретические методы исследования и методы численного решения задачи оптимального синтеза, интеллектуальные методы организации управления системами. Работа строится на известных данных и теоретических положениях системного анализа, теории оптимизации и управления, математического моделирования, теории игр. Достоверность полученных результатов подтверждается корректностью разработанных математических моделей и методов, использованием известных положений фундаментальных наук, сходимостью полученных результатов с результатами применения существующих методов.
На защиту выносятся 1. Метод решения задач структурно-параметрической оптимизации на основе эволюционного подхода.
2. Метод построения нечетких продукционных правил, основанный на решении задачи структурно-параметрического синтеза.
3. Многопопуляционный генетический алгоритм решения задачи условной оптимизации.
4. Решение задачи оптимального управления движением в жидкости объекта с внешней жесткой оболочкой и внутренней движущейся материальной точкой.
Научная новизна результатов исследования и результатов, полученных лично автором, заключается в следующем:
- разработан метод структурно-параметрического синтеза на основе генетического алгоритма, позволяющий путем последовательного эволюционного усложнения структуры с одновременным поиском оптимальных значений параметров получить модель системы с заданными характеристиками;
- впервые поставлена и решена задача оптимального структурнопараметрического синтеза нечетких продукционных правил на основе эволюционного построения деревьев решений;
- построен метод условной оптимизации на основе совместного решения нескольких задач безусловной оптимизации с помощью многопопуляционного генетического алгоритма;
- с использованием алгоритма синтеза деревьев решений решена задача оптимального управления движением мобильных устройств в вязкой жидкости.
Практическая ценность. Разработанные в диссертации методы позволяют решать задачи управления и оптимального структурно-параметрического синтеза, в том числе и задачи условной оптимизации, обеспечивая принятие управленческих решений в процессе моделирования сложных и технических систем. В работе показана общность задач оптимизации, возникающих в различных областях деятельности. Предложенные подходы обладают в большой степени гибкостью и универсальностью и могут быть рекомендованы к использованию вне зависимости от природы исследуемых в задачах объектов.
Результаты диссертации могут быть использованы в учебном процессе высшей школы при подготовке соответствующих специалистов.
ичный вклад. Автором разработан генетический алгоритм оптимального структурно-параметрического синтеза и выполнена его реализация в виде программного пакета для решения задачи управления системами. Разработаны и реализованы методы решения задач условной оптимизации и построения деревьев решений. Получена система нечетких правил на основе дерева решений для управления движением системы за счет перемещения внутренней материальной точки.
Апробация работы. Основные положения диссертации докладывались и получили положительную оценку на следующих научных конференциях:
Региональная научно-техническая конференция Математическое и компьютерное моделирование технических и социально - экономических систем (Ижевск, 14 мая 2010г.); Всероссийская научно-практическая конференция Математические методы и интеллектуальные системы в экономике и образовании (Ижевск, май 2010г.); IX Международная научнопрактическая конференция Исследование, разработка и применение высоких технологий в промышленности (Санкт-Петербург, 22Ц23 апреля 2010г.);
конференция Понтрягинские чтения - XXII в рамках XXV Воронежской весенней математической школы Современные методы теории краевых задач (Воронеж, 3Ц9 мая 2011г.); II Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых Измерения, контроль и диагностика - 2012 (Ижевск, май 2012г.); IUTAM Symposium From mechanical to biological system - an integrated approach (Ижевск, июнь 2012г.).
По теме диссертации делались сообщения и доклады на научнопрактических конференциях ИжГТУ 2009-2012 гг.
Публикации. По теме диссертационной работы опубликовано 12 печатных работ, из них 4 в изданиях, рекомендованных ВАК. Получено два свидетельства о регистрации электронных ресурсов.
Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, библиографического списка, включающего 1наименований. Текст диссертации изложен на 120 листах машинописного текста, содержит 36 рисунков, 12 таблиц.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении дается обоснование актуальности диссертационного исследования, сформулированы цели и задачи, определяются объект и предмет исследования; отмечены научная новизна и практическая значимость полученных результатов; сформулированы научные положения, выносимые на защиту; приведена краткая характеристика работы.
Первая глава содержит обзор литературных источников по проблемам структурно-параметрического синтеза и оптимизации, рассмотрены концептуальные научные подходы к решению и обозначены недостатки существующих методов. Отдельное внимание уделено вопросам применения эволюционных алгоритмов, как мощному и универсальному средству решения многоэкстремальных задач поиска и оптимизации большой размерности, которое не накладывает специальных ограничений на вид функций как непрерывность или дифференцируемость. Представлена общая постановка задачи структурно-параметрического синтеза.
Пусть одна из возможных реализаций S0 T0, X0 системы S имеет ~ ~ структуру T0 T, где T множество возможных топологий системы, и соответствующий ей вектор параметров X0, для которого можно считать, не ограничивая общности, что X0 Rn. Структура системы определяется множеством входящих в нее элементов G0 и соответствующим множеством ~ связей между этими элементами HG, т.е. T0 G, HG. G gi, где gi G, а ~ G - множество всех возможных элементов системы, HG hij, где hij характеризует наличие связи между gi и g элементами системы S. В случае j заданного вектора критериев FS для оценки оптимальности системы можно говорить о поставленной задаче структурно-параметрического синтеза вида:
FST, XTTXR (1) ~, ext.
n На основе анализа литературных данных и современного состояния проблемы определены основные задачи диссертационного исследования.
Показана необходимость разработки методов решения задачи структурнопараметрического синтеза для управления сложными и техническими системами, в частности мобильными устройствами, использующими нетрадиционные движители.
Решение задачи оптимального управления системами требует решения задач условной, структурной и структурно-параметрической оптимизации в сочетании с использованием методов Data Mining: деревьев решений и аппарата нечеткой логики для построения модели управления системой.
Вторая глава посвящена разработке метода решения задачи условной оптимизации на основе многопопуляционного генетического алгоритма.
Задача условной оптимизации рассмотрена в общем виде как минимизация целевой функции F(X ) при заданной системе ограничений gi (X ) и hi (X ) :
F(X ) F(x1, x2,..., xN ) min, (2) gi(X ) 0, i 1, m1, (3) hi(X ) 0, i 1, m2. (4) Решение задачи ищется в заданной области поиска I, ограниченной пределами изменения каждой из переменных:
I X (x1, x2,..., xN ) ai xi bi, i 1, 2,.., N. (5) Из-за описанных в работе недостатков существующих методов решения задачи (2) - (5), предложен модифицированный генетический алгоритм, основанный на использовании дополнительной популяции для разделения исходной задачи условной оптимизации на задачу поиска точек допустимого множества опт опт решений D, которому принадлежит решение X, Fопт FX :
D X (x1, x2,..., xN ) gi (X ) 0, i 1, m1, hi (X ) 0, i 1, m2, (6) и задачу совместного параллельного поиска минимума функции F(X ) с учетом найденных допустимых элементов множества D. Такой подход позволяет перейти от решения задачи условной оптимизации к решению двух задач безусловной оптимизации, не используя систем барьеров и штрафов. Для их решения в модифицированном алгоритме реализовано взаимодействие двух ~ популяций: F, предназначенной для поиска минимума исходной целевой ~ функции F(X ), и G, отвечающей за поиск допустимых особей, с функциями приспособленности F(X ) и G(X ) соответственно. Функция F(X ) является исходной целевой функцией задачи (2) - (4), а G(X ) представляет собой свертку из ограничений:
im1 im G(X ) hi X . (7) maxg X , 0 i i1 i Акцент делается на допустимость решения: на каждой итерации поиск минимума функции F(X ) ведется преимущественно среди уже найденных ранее допустимых особей, либо (если допустимых еще не найдено) с учетом наиболее приспособленных особей с точки зрения допустимости. Связь двух популяций и двух подзадач реализуется в процессе скрещивания, проводимого ~ ~ между особями популяций F и G по классической схеме, но с выбором родителей из разных популяций.
Общая схема взаимодействия популяций представлена на рис. 1.
F(X ) F(X ) ~ ~ ~ F Fi1 F ~ ~ Pi copy cross Е Picros G(X ) G(X ) ~ ~ ~ s G Gi1 G Рис. 1. Схема взаимодействия популяций многопопуляционного генетического алгоритма условной оптимизации Поиск решения начинается со случайно сгенерированной начальной ~ ~ ~ популяции P0. Затем особи помещаются в популяции F и G, где проводится одна итерация (либо k итераций) генетического алгоритма для получения ~ ~ следующих поколений Fi1 и Gi1. После чего осуществляется скрещивание ~ ~ между популяциями Fi1 и Gi1: те особи, которые лучше удовлетворяют ограничениям и те, для которых значение F(X ) минимально, с большей вероятностью участвуют в скрещивании, и, следовательно, участвуют в ~ формировании следующей популяции Pi1. После скрещивания проводится ~ оценка популяции Pi1 и выбирается лучшая особь Xbest и соответствующее ей значение целевой функции Fbest задачи (2) - (4). Если выполнено условие останова алгоритма, то поиск прекращается, и в качестве решения выступают значения Xbest и Fbest. Если решение не найдено, алгоритм возвращается на ~ ~ ~ этап деления популяции Pi1 на популяции F и G, снова генерирует в них следующие поколения.
Работа алгоритма исследована на примере минимизации сложных с точки зрения оптимизации функций Розенброка и Растригина большой размерности (до N 100) с ярко выраженным овражным и многоэкстремальным характером при различных системах ограничении и различных случаях расположения экстремума. Тестовые функции:
функция Розенброка:
N F(X ) (100 (xi1 xi2 )2 (1 xi )2 ) min, xi [5, 5], i 1, 2,..., N, i функция Растригина:
N F(X ) (x 10cos(2xi )) 10N min, xi [5, 5], i 1, 2,..., N.
i i 2 Ограничения задавались в виде многомерного кольца R1 xi2 xi21 R2, i 1, N 1, для которого были исследованы случаи положения минимума как внутри, так и на границе области, заданной ограничениями. Проведено исследование изменения количества допустимых особей в популяции в процессе минимизации для каждого такого случая. Пример такой зависимости для функции Розенброка при N 100 и R1 0,5, R2 3 представлен на рис. 2.
F 100% 1000080% 1060% 40% 0,020% 0,000001 0% t, c t, c 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 а) б) Рис. 2. а) Зависимость невязки функции Розенброка; б) Зависимость процента допустимых особей в популяции от времени (минимум лежит внутри области) В работе проведено сравнение предложенного метода с известными методами решения задачи условной оптимизации.
Третья глава посвящена разработке методов решения задачи структурнопараметрического синтеза и рассмотрению сопутствующих ей отдельных аспектов, таких как решение задач структурной оптимизации, выбор и разработка генетического кодирования и генетических операторов для решения задачи оптимального структурно-параметрического синтеза в общем виде. На основе разработанных подходов построен метод структурно-параметрического синтеза нечетких продукционных правил, получаемых на основе деревьев решений.
Решение подзадачи структурной оптимизации сопряжено с определением способа построения оптимальной структуры. Наиболее перспективен метод направленного перебора, основанный на последовательном выращивании и усложнении топологий. В работе продемонстрирована эффективность применения такого подхода на решении коалиционной игры, суть которой в определении оптимального распределения выигрыша между участниками игры и нахождении соответствующего распределения игроков по коалициям.
Решение задачи начинается с бескоалиционной ситуации, когда каждый игрок действует индивидуально, но затем в процессах мутации и скрещивания создаются и увеличиваются коалиции до тех пор, пока не будет найдено требуемое решение. Для определения вектора дележа введен принцип справедливости, основанный на распределении выигрыша игроков пропорционально их вкладу в суммарный выигрыш коалиции.
Последовательное выращивание топологии позволяет избежать перебора излишне сложных структур, не требует решения задачи удаления ненужных элементов структуры и позволяет получить модель с наиболее простой топологией, не накладывая при этом явных ограничений на размер конечной структуры.
Для решения задачи (1) разработан генетический алгоритм, реализующий последовательное эволюционное выращивание структуры, в котором каждая особь популяции представляет одну возможную реализацию системы S, а ее генотип описывает множества элементов системы и связей между ними с соответствующим набором параметров.
Применение генетических алгоритмов требует разработки специального генетического кодирования структуры - определенного способа представления структурно-параметрических моделей в виде генотипов индивидов популяции генетического алгоритма. В качестве такого кодирования использован подход, основанный на применении исторической нумерации структурных новообразований (innovation number)1. Фенотип, т.е. структура модели, может быть представлена в виде некоторого графа (рис. 3а), которому взаимно однозначно ставится в соответствие генотип (рис. 3б) - кодированное представление графа.
Фенотип Генотип Node 1 Node 2 Node 3 Node 4 Node Гены Е Е Е Е Е узлов In 1 In 2 In 3 In 2 In 5 In 2 5 Out 4 Out 4 Out 4 Out 5 Out 4 Out Гены Enabled Disabled Enabled Enabled Enabled Enabled дуг Innov 1 Innov 2 Innov 3 Innov 4 Innov 5 Innov Е Е Е Е Е Е а) б) Рис. 3. Генетическое кодирование структуры: а) фенотип; б) генотип Суть исторической нумерации структурных новообразований у индивидов популяции в том, что каждый вновь появившийся в результате мутации элемент структуры получает свой уникальный порядковый номер, который не меняется у потомков в последующих поколениях (Innov, рис. 3). Генотип каждого индивида содержит информацию об узлах и дугах графа. Положение каждой дуги описывается номерами начального (In) и конечного (Out) узлов.
По мере последовательного увеличения структуры, с появлением новых узлов и дуг, информация об исчезнувших структурных образованиях не теряется, а хранится в генотипе в виде неактивных элементов структуры (Disabled, рис.3), и с определенной вероятностью эти элементы могут проявиться в следующих поколениях.
Рост структуры осуществляется в процессе мутации и возможен в виде появления новой вершины или новой дуги графа, соединяющей существующие вершины.
Скрещивание реализует обмен отдельными элементами структуры между индивидами популяции и основано на выявлении общей структурной части Stanley K.O., Miikkulainen R. Evolving Neural Networks through Augmenting Topologies // Evolutionary Computation, 2002, no. 2(10), pp. 99-127.
родительских особей. Историческая нумерация позволяет однозначно идентифицировать предка для любого индивида популяции, а для любых двух индивидов - выявить их общую часть в структуре. При скрещивании двух выбранных индивидов общая часть структуры родительской пары переходит потомку, а различные элементы структуры разыгрываются с учетом возможности пропорционально родительской приспособленности. Пример такого скрещивания представлен на рис. 4 (в генотипе выделена общая часть родительской структуры). Наличие в генотипах индивидов одинаковых исторических номеров свидетельствует о наличии общего исторического предка в предшествующем процессе эволюционного структурного роста.
Родитель 1 Родитель 2 Потомок 2 5 6 2 5 2 5 6 1 2 3 4 5 1 2 3 4 5 6 7 9 1 2 3 4 5 6 7 8 9 14 24 34 25 54 114 24 34 25 54 56 64 35 114 24 34 25 54 56 64 15 35 1Dis Dis Dis Dis Dis а) б) в) Рис. 4. Скрещивание: фенотипы и соответствующие им генотипы Представленный подход позволяет решить проблемы появления недопустимых особей и потери генетической информации в процессе скрещивания, а также проблему существования конкурирующих решений, поскольку генетическое кодирование позволяет однозначно представить произвольный граф, характеризующий структуру модели. Эффективность такого подхода исследована на примере оптимального синтеза нейронной сети для решения задачи регрессии.
Представленный в работе метод структурно-параметрического синтеза нечетких продукционных правил, получаемых на основе деревьев решений, основан на том, что деревья решений можно рассматривать как совокупность логических привил if A then B, представленных в иерархической последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. Такие правила в сочетании с функциями принадлежности и способом получения агрегированного выходного сигнала составляют базу нечетких правил для управления системой.
Для построения деревьев решений использован генетический алгоритм структурно-параметрического синтеза. Каждая особь популяции генетического алгоритма представляет собой некоторое возможное дерево решений.
Структурообразующими элементами дерева являются узлы, а дуги могут быть рассмотрены как свойства соответствующих узлов, из которых они выходят, поэтому в соответствии с алгоритмом структурно-параметрического синтеза структура дерева может быть закодирована в виде взаимосвязанных списков по следующей схеме:
Node (Узел) InnovID: int Type = {Root, Node} Edges: List
Условие на переменную (Variable) отражает на какую именно из переменных исходной задачи (VarID) накладывается ограничение и каков характер этого ограничения (Value).
В общем случае условия в узлах дерева и значения атрибутов на дугах могут носить произвольный характер: проверка равенства или неравенства, проверка булева значения конкретного оператора, проверка принадлежности к классу, проверка принадлежности к области (диапазону) значений.
Представленное на рис. 5 кодирование позволяет описать произвольное n-арное дерево с любыми условиями ветвления (рис 6).
Генотип Node 1 Node 2 Node Фенотип InnovID = 1 InnovID = 2 InnovID = Type = Root Type = Node Type = Node x1 < 0.5 x1 0.Edges... Edges... Edges...
Edges Edges Edges x3 = -1 x3 = Edge 1 Edge 2 Edge 1 Edge 2 Edge 3 Edge 1 Edge In = 1 In = 1 In = 2 In = 2 In = 2 In = 3 In = x3 = Out = 0 Out = 2 Out = 3 Out = 0 Out = 0 Out = 0 Out = Vars... Vars... Vars... Vars... Vars... Vars... Vars...
x2 < 0.8 x2 0.Vars Vars Vars Vars Vars Vars Vars VarID=1 VarID=1 VarID=3 VarID=3 VarID=3 VarID=2 VarID=Value = Value = Value = Value = Value = Value = Value = "< 0.5" " 0.5" "= -1" "= 0" "= 1" "< 0.8" " 0.8" Рис. 6. Кодированное представление дерева решений Начальная популяция генетического алгоритма формируется из минимально возможных деревьев, глубина которых равна 1, т.е. каждое такое дерево содержит только корень и листья. Функция приспособленности формируется на основании ошибки построения дерева по обучающему набору данных, Узлы Дуги Условия приспособленность Fitness определяется разностью между общим количеством данных - N и количеством неверно классифицированных - Misclassification:
Fitness = N - Misclassification. (8) Fitness = N означает, что все наблюдения классифицированы верно, а Fitness = - что нет ни одного верно классифицированного. Таким образом, чем выше приспособленность индивида, тем лучше его дерево описывает исходный набор данных и наоборот.
В процессе работы генетического алгоритма деревья растут за счет появления новых узлов в результате мутации и скрещивания до тех пор, пока не будет выполнено условие останова алгоритма и найдено решение.
Мутация реализует случайное появление новых узлов ветвления на месте листьев или корня дерева (рис. 7), при этом количество дуг с условиями, выходящих из нового узла, может быть зафиксировано и постоянно для всего дерева или меняться от одного узла к другому. Если новый узел возникает на месте корня дерева, то он становится новым корнем, а тот узел, который был им раньше - одним из его потомков (рис. 7а). Если новый узел возникает на месте листа дерева, то он замещает его (рис. 7б). Условия на новых дугах формируются из соответствующего числа выбранных атрибутов случайно взятой одной или нескольких переменных.
x4 < 0 x4 0 x4 < x1 < 0.5 x1 0.x1 < 0.5 x1 0. x3 = -1 x3 = x3 = x3 = -1 x3 = x3 = x4 < 0 x4 x2 < 0.8 x2 0.0 x4 < x2 < 0.8 x2 0.а) б) Рис. 7. Структурная мутация: а) появление нового узла на месте корня дерева;
б) появление нового узла на месте существующего листа 1 5 x4 x4 x1 < 0.x4 < x1 0.x4 < 0 x4 < 0 x4 < x1 < 0.8 x1 0.x3 = -1 x1 < 0.8 x1 0.x3 = 1 x1 < 0.5 x1 0.5 x1 < 0.5 x1 0.x3 = -x3 = x3 = x3 = x3 = - 2 x3 = x3 = 3 x3 = -1 x3 = 1 x3 = -1 x3 = x2 < 0.8 x2 0.8 x1 0.x3 = 0 x3 = x1 < 0. x2 < 0.8 x2 0.8 x2 < 0.8 x2 0.8 x1 < 0.8 x1 0.Родитель 1 Родитель 2 Потомок Рис. 8. Скрещивание, основанное на выявлении общей структурной части Скрещивание деревьев реализовано по тому же принципу, что и в общем алгоритме структурно-параметрического синтеза, путем выявления общей структурной части родителей (на рис. 8 общая часть выделена).
Потомки, получаемые в результате действия операторов скрещивания и мутации, также являются допустимыми деревьями решений.
Четвертая глава посвящена применению генетического алгоритма структурно-параметрического синтеза для решения задачи организации управления движением в вязкой жидкости тела с неизменяемой формой за счет перемещения внутренней массы. Задача решается в плоской постановке.
Перемещаемый объект с внешней жесткой оболочкой в форме цилиндра массой M содержит внутреннюю материальную точку массой m1, совершающую возвратно-поступательное движение по некоторому закону 1t 1t, 1tT (рис. 9). Движение тела и материальной точки рассматривается в неподвижной Oxy и подвижной O1 декартовых системах координат. Частота колебания внутренней точки в первой части периода выше, чем во второй, из-за чего в вязкой жидкости за период колебания происходит перемещение тела.
Управлять направлением движения тела можно поворотом оси, вдоль которой перемещается материальная точка, на угол относительно подвижной системы координат. Поворот направления колебаний на угол не означает, что тело будет двигаться в этом направлении. Для движения по некоторой заданной траектории необходимо подобрать закон изменения угла , зависящий от параметров движения 0,ub,vb: угла поворота тела 0, составляющих скорости ub, vb.
Характеристики движения тела определяются из решения уравнений движения:
dP1 dP P2 F1, P1 F2, dt dt dK ubP2 vbP G, dt dx ub cos0 b sin0, dt (9) dy ub sin0 b cos0, dt d , Рис. 9. Перемещаемый dt объект с внутренней P0 P20 K0 x0 y0 00 0, материальной точкой где P1 A1 m1ub m11t 1t, P2 A2 m1b m11t 1t - проекции вектора импульса в подвижной системе координат;
K B m1ub1 b1 m11t 11 m11t 11 - кинетический момент; F F1, F2 - сила, действующая со стороны жидкости на тело, G - момент этой вязкой силы; A1 M 1, A2 M 2, B J 3 ; M, J - масса тела и момент инерции без учета материальной точки; 1, 2, 3 коэффициенты присоединенных масс; - угловая скорость вращения; Ub (ub,vb) - век тор скорости движения тела (точки O1); u1 t, 1 t - проекции скорости движения материальной точки в подвижной системе координат; 0 - угол поворота подвижной системы координат O1 относительно неподвижной Oxy.
Для многократного численного решения уравнений движения вязкая сила и момент вязкой силы аппроксимируются зависимостями от основных параметров движения тела.
Заданную траекторию, по которой необходимо переместить тело, можно заменить кусочно-непрерывной линией. На каждом прямолинейном отрезке [Ai, Ai+1] необходимо обеспечить передвижение тела из начала Ai в конец отрезка Ai+1. В начальной точке отрезка Ai = (xi, yi) известны значения параметров движения (0i, ui, vi), необходимо определить управление, позволяющее попасть в конечную точку отрезка Ai+1 = (xi+1, yi+1).
Для перемещения тела в жидкости использован следующий закон движения внутренней точки (операция соответствует целой части числа):
1 , 1 sin 2 t T0, T0 1 , 1t , t 1 T0 2 1 (10) 1 cos2 21 , 2 1t 0.
Полученная задача оптимального управления может быть представлена в виде:
dx fx, , (11) dt где - управляющий параметр.
Для получения зависимости управляющей функции от параметров движущегося тела решается задача оптимального управления движением в заданную точку по кратчайшему маршруту. Задача сводится к дискретному аналогу и решение ищется с помощью разработанного генетического алгоритма условной оптимизации. В качестве критерия оптимальности взято минимальное отклонение тела от прямолинейной траектории:
t ytdt min, (12) при условии минимального отклонения конечной координаты тела от заданной точки:
x xk min. (13) Набор оптимальных траекторий передвижения тела (x,y) из точки (0;0) в точку (0;1) при разных значениях параметров (угол поворота тела 0, составляющих скорости ub, vb ) показан на рис. 10, а соответствующее оптимальное управление движением тела на рис. 11.
y 0,0,0,-0,-0,-0,6 x -0,4 -0,2 0 0,2 0,4 0,6 0,8 1 1,Рис. 10. Оптимальные траектории движения тела из точки (0;0) в точку (0;1) при различных значениях параметров 0 t, c t 0 5 10 15 20 25 30 35 ---Рис. 11. Соответствующее оптимальное управление движением тела из точки (0;0) в точку (0;1) Зависимость управления от параметров движущегося тела 0,u,v находится на основе системы нечеткого логического вывода Сугено. Нечеткие знания формулируются в виде нечетких продукционных правил вывода, задаваемых в форме if A then B:
Rr : if Air then y is Br, r 1, KR. (14) x i Условие xi Air соответствует условию разделения множества объектов xi wij, i 1,m 1; j 1,n и означает попадание величины xi в нечеткий интервал wij с функциями принадлежности xi и xi. Функция принадлежности xi соответствует условию xi wiq xi условию, а.
xi wiq При заданном векторе X xiT 0,u,vT определяются степени истинности каждого правила: r, r 1, K. Степени истинности соответствуют R значениям функций принадлежности левых частей (предпосылок):
gr Rr r min, k 1, gr, где - количество условий в данном правиле. В k k результате, агрегированный выходной сигнал определяется по формуле:
KR n F1X prjx, (15) pr0 r j KR r1 j r rкоэффициенты prj, r 1, KR; j 0, n определяются по имеющейся обучающей выборке.
Для получения продукционных правил типа if A then B использованы деревья решений, построенные на оптимальных траекториях (рис. 10) с помощью генетического алгоритма структурно-параметрического синтеза.
Для рассмотренной задачи организации управления движением в вязкой жидкости тела с неизменяемой формой за счет перемещения внутренней массы с заданным законом 1t 1t,1tT движения внутренней материальной точки с помощью генетического алгоритма структурно-параметрического синтеза на основе обучающего набора оптимальных траекторий (рис. 10) и соответствующего управления (рис. 11) получено следующее дерево решений:
v < 0.05 v 0. = < -0. -0.4 u u 0.u < 0 u < 0. = 7 5 = v < 0.v 0.u < 0.u 0.9 6 = u < 0.u 0.u -0.v < -0.01 v -0.01 u < -0. = = 2 = 1 = 3 = u < 0.u 0. = 2 = Рис. 12. Дерево решений В полученном дереве решений каждый путь из корня к листу определяет одно правило типа if A then B. Построенное дерево дает набор правил следующего вида:
if 0.05 then = if < 0.05 0 -0.60 u 0.07 then = if < 0.05 0 -0.60 u 0.04 u < 0.07 then = if < 0.05 0 -0.60 u -0.03 u < 0.04 then = if < 0.05 0 -0.60 u < -0.03 then = if < 0.05 0 < -0.60 0.02 u 0.12 then = if < 0.05 0 < -0.60 u 0 0.02 u < 0.12 then = if 0 < -0.60 v < 0.02 -0.01 u 0.17 then = if 0 < -0.60 u 0 < 0.02 -0.01 u < 0.17 then = if 0 < -0.60 u 0 < -0.01 then = if < 0.05 0 < -0.60 u < 0 then = Вся область значений управляющего параметра разбита на три интервала, и каждое правило определяет принадлежность управления к одному из них:
= 1, = 2, = 3 в зависимости от значений входных параметров. Итоговое четкое значение управляющего параметра определяется как средневзвешенное по формуле (15).
Полученные правила в совокупности с функциями принадлежности xi и xi и взвешенной суммой для получения агрегированного выходного сигнала определяют управление движением тела из одной точки в другую вдоль произвольной заданной траектории.
В четвертой главе дано описание программного пакета, реализующего разработанные методы для организации управления системами. Программный пакет содержит необходимые классы и методы для решения задач структурнопараметрического синтеза, структурной и условной оптимизации, построения деревьев решений по заданной таблице данных и получения системы нечетких продукционных правил на основе дерева решений для управления системами.
В заключении работы приведена общая характеристика работы и основные выводы по результатам диссертации.
ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ПО РАБОТЕ Результаты диссертационной работы позволяют расширить область применения эволюционных методов и повысить эффективность решения задач структурно-параметрического синтеза и оптимизации для управления сложными системами. В работе получены следующие основные выводы и результаты:
1. Разработан генетический алгоритм решения задачи условной оптимизации, основанный на использовании дополнительных популяций.
Сравнение при решении тестовых задач с известными методами на основе штрафных функций, в том числе и с самоадаптацией штрафа, показало, что в серии запусков при использовании многопопуляционного алгоритма среднее значение найденного минимума всегда меньше и к лучшему значению в серии запусков разработанный алгоритм сходится в 2,5 раза чаще. При этом скорость работы разработанного алгоритма до 5 раз выше при неактивных ограничениях и до 3 раз - при активных.
2. Разработан эволюционный метод решения задач структурнопараметрического синтеза, позволяющий наряду с оптимальными значениями параметров получить и наиболее простую структуру системы. Структурная оптимизация системы при обеспечении заданных значений параметров позволяет уменьшить в структуре количество элементов в 1,4 раза и связей в 1,8 раза по сравнению с использованием традиционных подходов.
3. В работе впервые поставлена и решена задача оптимального структурнопараметрического синтеза нечетких продукционных правил на основе построения деревьев решений с помощью разработанных методов. Такой подход позволяет строить произвольные деревья решений с возможностью использования в узлах до 5 условий различного типа, что позволяет получать компактные деревья и продукционные правила для систем нечеткого вывода.
4. Решена задача управления объектом, движущимся по заданной траектории в вязкой жидкости под действием перемещения внутренних материальных точек и нечетких правил. Построена база из 11 правил, позволяющая управлять движением тела из одной точки в другую вдоль произвольной заданной траектории.
5. Методы и алгоритмы реализованы в виде программного пакета для решения задач структурно-параметрического синтеза и зарегистрированы в ФГНУ ЦИТиС и ОФЕРНиО.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ 1. Прохоровская Е.В., Тененёв В.А., Шаура А.С. Генетические алгоритмы с вещественным кодированием при решении задач условной оптимизации // Интеллектуальные системы в производстве. - Ижевск: изд. ИжГТУ, - 2008.
С. 46 - 55.
2. Шаура А.С. Генетический алгоритм с параллельным поиском допустимых особей при решении задач условной оптимизации с ограничениямиравенствами // Интеллектуальные системы в производстве. - Ижевск: изд.
ИжГТУ, - 2009. С. 91 - 96.
3. Шаура А.С. Методы кодирования нейросетевой структуры при решении задач с помощью генетических алгоритмов // Материалы Региональной научнотехнической конференции Математическое и компьютерное моделирование технических и социально - экономических систем. - Ижевск: изд. ИжГТУ, - 2010. С. 54 - 56.
4. Шаура А.С. Модифицированный генетический алгоритм для задач условной оптимизации // Материалы Всероссийской научно-практической конференции Математические методы и интеллектуальные системы в экономике и образовании: Тез. докл. - Ижевск: Типография ГОУ ВПО УДГУ, - 2010. С. 128 - 131.
5. Шаура А.С. Решение задачи условной оптимизации с помощью генетических алгоритмов // Сборник трудов IX Международной научно практической конференции Исследование, разработка и применение высоких технологий в промышленности Т.3: Тез. докл. - СПб.: изд. Политехнического университета, - 2010. С. 170-174.
6. Модифицированный генетический алгоритм для решения задач условной оптимизации: свидетельство о регистрации электронного ресурса № 16503 // Тененев В.А., Шаура А.С. Инв. № 50201050246, дата регистрации 10.12.2010.
7. Шаура А.С. О применении генетических алгоритмов к решению коалиционных игр // Современные методы теории краевых задач: материалы Воронежской весенней математической школы Понтрягинские чтения: Тез.
докл. - Воронеж: Издательско-полиграфический центр Воронежского государственного университета, - 2011. С. 214 - 215.
8. Шаура А.С. Применение генетических алгоритмов для решения игровых задач с коалиционной структурой // Интеллектуальные системы в производстве.
- Ижевск: изд. ИжГТУ, - 2011. С. 68 - 74.
9. Генетический алгоритм для решения игровых задач с коалиционной структурой: свидетельство о регистрации электронного ресурса № 17777 // Тененев В.А., Шаура А.С. Инв. № 50201250032, дата регистрации 10.01.2012.
10. Построение деревьев решений с помощью генетического алгоритма структурно-параметрического синтеза // Интеллектуальные системы в производстве. - Ижевск: изд. ИжГТУ, - 2012. С. 72 - 80.
11. Шаура А.С. Решение задачи структурно-параметрической оптимизации с помощью генетических алгоритмов. // Материалы II Всероссийской научнотехнической конференции студентов, аспирантов и молодых ученых Измерения, контроль и диагностика - 2012. - Ижевск: изд. ИжГТУ, - 2012.
С. 21 - 22.
12. Tenenev V., Vetchanin E., Shaura A. Motion control of a rigid body in viscous fluide // From Mechanical to Biological Systems - an Integrated Approach.
IUTAM Symposium: Book of Abstracts. - Moscow-Izhevsk: Publishing Center Institute of Computer Science, - 2012. Pp. 62 - 63.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям