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

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

005055066

УДК 517.977.58+004.825+004.023

Шаура Александр Сергеевич

Разработка методов структурно-параметрического синтеза для управления системами

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 5 НОЯ 2012

Ижевск - 2012

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ижевский государственный технический университет имени М.Т. Калашникова»

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

Тененев Валентин Алексеевич

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

Мурынов Андрей Ильич

доктор физико-математических наук, профессор Килин Александр Александрович

Ведущая организация: Федеральное государственное бюджетное учре-

ждение науки Институт машиноведения имени A.A. Благонравова Российской академии наук

Защита состоится 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, К.О. Stanley, R.Miikkulainen, S. Nolfí, D. Parisi, F. Gruau, H. Kitano, В.Г. Редько, Ю.Р. Цой - подходы к построению оптимальных нейронных сетей и моделей искусственного интеллекта на основе эволюционных методов. Большое значение имеют задачи оптимального управления движением мобильных технических систем.

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

В последние годы широкое развитие получили методы Data Mining, в частности деревья решений (Е.В. Hunt, J.Marin, P.J. Stone, J.R. Quinlan), и аппарат нечеткой логики (L. Zadeh, Т. Takagi, M. Sugeno, E. Mamdani) для моделирования и управления системами. Перспективным направлением стало использование этих технологий в сочетании с эволюционными методами. Эффективность такого подхода показана в работах J. Koza, F. Herrera, Н. 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 глав, заключения, библиографического списка, включающего 112 наименований. Текст диссертации изложен на 120 листах машинописного текста, содержит 36 рисунков, 12 таблиц.

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

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

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

Пусть одна из возможных реализаций S0 ={Г0,Х0) системы S имеет

структуру Т0 е Т, где ¥ множество возможных топологий системы, и соответствующий ей вектор параметров Х0, для которого можно считать, не ограничивая общности, что Х0 е R". Структура системы определяется множеством входящих в нее элементов G0 и соответствующим множеством связей между этими элементами Нс, т.е. Т0 = (G, IIG). G = где g,-eG, а G - множество всех ВОЗМОЖНЫХ элементов системы, На = \}ljj\, где hy характеризует наличие связи между g, и g} элементами системы S. В случае заданного вектора критериев F(S) для оценки оптимальности системы можно говорить о поставленной задаче структурно-параметрического синтеза вида:

F№X)) ТєТ, XsR" ' ^ ' V

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

Решение задачи оптимального управления системами требует решения задач условной, структурной и структурно-параметрической оптимизации в сочетании с использованием методов Data Mining: деревьев решений и аппарата нечеткой логики для построения модели управления системой.

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

Задача условной оптимизации рассмотрена в общем виде как минимизация целевой функции F{X) при заданной системе ограничений и /г, (X):

F(X) = F(Xux2,...,Xn)-* min, (2)

gi(X)<0, І = Щ, (3)

ЛДЛГ) = 0, i = l,m2. (4)

Решение задачи ищется в заданной области поиска I, ограниченной пределами изменения каждой из переменных:

I = {x = (xl,x2,...,xN)\ai <Xj <bj,i = \,2,..,n\. (5)

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

« г. \ronm r-onm грі \ronm І.

решении D, которому принадлежит решение X , г = ґ\Х ).

D = \x = (х1,х2, ...,лгдг)| gi(X)<0, і = = = (6)

и задачу совместного параллельного поиска минимума функции F(X) с учетом найденных допустимых элементов множества D. Такой подход позволяет перейти от решения задачи условной оптимизации к решению двух задач безусловной оптимизации, не используя систем барьеров и штрафов. Для их решения в модифицированном алгоритме реализовано взаимодействие двух популяций: F, предназначенной для поиска минимума исходной целевой функции F(X), и G, отвечающей за поиск допустимых особей, с функциями приспособленности F(X) и G{X) соответственно. Функция F{X) является исходной целевой функцией задачи (2) - (4), а G(X) представляет собой свертку из ограничений:

= 'fmax{g, (X), О} +'§>,. . (7)

..і ¡=i

Акцент делается на допустимость решения: на каждой итерации поиск минимума функции F{X) ведется преимущественно среди уже найденных

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

Общая схема взаимодействия популяций представлена на рис. 1.

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

Поиск решения начинается со случайно сгенерированной начальной популяции Р0. Затем особи помещаются в популяции Р и ё, где проводится одна итерация (либо к итераций) генетического алгоритма для получения следующих поколений и . После чего осуществляется скрещивание между популяциями и : те особи, которые лучше удовлетворяют ограничениям и те, для которых значение Р{Х) минимально, с большей вероятностью участвуют в скрещивании, и, следовательно, участвуют в формировании следующей популяции /¡+1. После скрещивания проводится оценка популяции Р1+1 и выбирается лучшая особь ХЬы и соответствующее ей значение целевой функции задачи (2) - (4). Если выполнено условие останова алгоритма, то поиск прекращается, и в качестве решения выступают значения ХЬе5, и РЬы. Если решение не найдено, алгоритм возвращается на

этап деления популяции /|+1 на популяции ? и б, снова генерирует в них следующие поколения.

Работа алгоритма исследована на примере минимизации сложных с точки зрения оптимизации функций Розенброка и Растригина большой размерности (до N = 100) с ярко, выраженным овражным и многоэкстремальным характером при различных системах ограничении и различных случаях расположения экстремума. Тестовые функции:

функция Розенброка:

£(100 • "*/2)2 + 0 -*,)2) ^тт, х,. е[-5,5], г = 1,2,...,М,

/=1

функция Растригина:

N

F(X) = £(*¡2 ~ 10со5(2лх,-)) +10А^ —>• тга, х, е[-5,5], / = 1,2,...,//.

¿=1

Ограничения задавались в виде многомерного кольца Л,2 < х} + хД, < , г = 1, N -1, для которого были исследованы случаи положения минимума как внутри, так и на границе области, заданной ограничениями. Проведено исследование изменения количества допустимых особей в поиуляции в процессе минимизации для каждого такого случая. Пример такой зависимости для функции Розенброка при N = 100 и ^ = 0,5, = 3 представлен на рис. 2.

1000000 100% 1000 -I

С

а) б)

Рис. 2. а) Зависимость невязки функции Розенброка; б) Зависимость процента допустимых особей в популяции от времени (минимум лежит внутри области)

В работе проведено сравнение предложенного метода с известными методами решения задачи условной оптимизации.

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

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

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

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

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

Применение генетических алгоритмов требует разработки специального генетического кодирования структуры - определенного способа представления структурно-параметрических моделей в виде генотипов индивидов популяции генетического алгоритма. В качестве такого кодирования использован подход, основанный на применении исторической нумерации структурных новообразований (innovation number)1. Фенотип, т.е. структура модели, может быть представлена в виде некоторого графа (рис. За), которому взаимно однозначно ставится в соответствие генотип (рис. 36) - кодированное представление графа.

Генотип

Фенотип

Гены Node 1 Node 2 Node 3 Node 4 NodeS

узлов

©-»©-»О

Гены дуг

In 1 In 2 In 3 In 2 In 5 In I

Out 4 Out 4 Out 4 Out 5 Out 4 Out 5

Enabled Disabled Enabled Enabled Enabled Enabled

Innov 1 Innov2 Innov J Innov 4 Innov5 Innov9

а)

б)

Рис. 3. Генетическое кодирование структуры: а) фенотип; б) генотип

Суть исторической нумерации структурных новообразований у индивидов популяции в том, что каждый вновь появившийся в результате мутации элемент структуры получает свой уникальный порядковый номер, который не меняется у потомков в последующих поколениях (Innov, рис. 3). Генотип каждого индивида содержит информацию об узлах и дугах графа. Положение каждой дуги описывается номерами начального (In) и конечного (Out) узлов. По мере последовательного увеличения структуры, с появлением новых узлов и дуг, информация об исчезнувших структурных образованиях не теряется, а хранится в генотипе в виде неактивных элементов структуры (Disabled, рис.3), и с определенной вероятностью эти элементы могут проявиться в следующих поколениях.

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

Скрещивание реализует обмен отдельными элементами структуры между индивидами популяции и основано на выявлении общей структурной части

1 Stanley K.O., Miikkulainen R. Evolving Neural Networks through Augmenting Topologies // Evolutionary Computation, 2002, no. 2(10), pp. 99-127.

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

Родитель 1 Родитель 2 Потомок

...л, .v t_1_I ? - : ' _; [ 1лз i _

а) б) в)

Рис. 4. Скрещивание: фенотипы и соответствующие им генотипы

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

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

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

Xode (Узел) InnovlD: iilt Type = {Root, Node} Edges: List <Edge>

Edge (Дуга)

Irr. int Out: int

Variabler. List <Variable>

Variable (Переменная)

VarlD: int Value: TValue

Рис. 5. Система связанных списков для кодирования фенотипа

В соответствии с представленной схемой (рис. 5) при кодировании дерева для каждого узла (Node), не являющегося листом, в генотип записывается порядковый номер появления этого узла (InnovlD) в фенотипе индивидов популяции, тип этого узла (Туре): Root - если узел является корнем дерева и Node - в противном случае, а также список дуг, выходящих из кодируемого узла (Edges). Дуги дерева (Edge) характеризуются входным (In) и выходным (Out) узлами и списком условий на переменные (Variables) при которых происходит переход по данной дуге. Если дуга оканчивается листом, то Out = 0. Условие на переменную (Variable) отражает на какую именно из переменных исходной задачи (VarlD) накладывается ограничение и каков характер этого ограничения (Value).

В общем случае условия в узлах дерева и значения атрибутов на дугах могут носить произвольный характер: проверка равенства или неравенства, проверка булева значения конкретного оператора, проверка принадлежности к классу, проверка принадлежности к области (диапазону) значений. Представленное на рис. 5 кодирование позволяет описать произвольное л-арное дерево с любыми условиями ветвления (рис 6)._

Node 1 . Node 2 . Node 3

з InnovlD — 1 InnovlD = 2 InnovlD — 3

Type = Root 7>pe = Node Type =Node

Edges ... Edges... Edges...

Edge 1 Edge 2

In'I ln=l

Oui = 0 Out-2

Van... Vars...

і і

Van VMS .

VarID=l VarlD' 1

Value = Value —

"< 0.5" "Ï 0.5"

1 !>,.*

Edge 1 Edge 2 Edge 3

In = 2 In -2 In = 2

Oui = 3 0uc = 0 Out-a

Vars... Vars... Vars...

Vara. Vara Vars

Уаг11>Ъ Value - VarlD=3 Value = 0" VarlD^l Value = », I«

Edge 1 Edge 2

ln = 3 Out- 0 Vars... In-3 0ul = 0 Vars...

v«rs. Vars

VarlD= 2 Value = "< 0.8" Varll>= 2 Value = ">0.8"

Рис. 6. Кодированное представление дерева решений

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

приспособленность Fitness определяется разностью между общим количеством данных - N и количеством неверно классифицированных - Misclassification:

Fitness = N-Misclassification. (8)

Fitness = N означает, что все наблюдения классифицированы верно, a Fitness = О - что нет ни одного верно классифицированного. Таким образом, чем выше приспособленность индивида, тем лучше его дерево описывает исходный набор ' данных и наоборот.

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

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

Рис. 7. Структурная мутация: а) появление нового узла на месте корня дерева; б) появление нового узла на месте существующего листа

Родитель I Родитель 2 Потомок

Рис. 8. Скрещивание, основанное на выявлении общей структурной части

Скрещивание деревьев реализовано по тому же принципу, что и в общем алгоритме структурно-параметрического синтеза, путем выявления общей структурной части родителей (на рис. 8 общая часть выделена).

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

Четвертая глава посвящена применению генетического алгоритма структурно-параметрического синтеза для решения задачи организации управления движением в вязкой жидкости тела с неизменяемой формой за счет перемещения внутренней массы. Задача решается в плоской постановке. Перемещаемый объект с внешней жесткой оболочкой в форме цилиндра массой М содержит внутреннюю материальную точку массой т1, совершающую возвратно-поступательное движение по некоторому закону (рис. 9). Движение тела и материальной точки рассматривается в неподвижной Оху и подвижной 0)^Т1 декартовых системах координат. Частота колебания внутренней точки в первой части периода выше, чем во второй, из-за чего в вязкой жидкости за период колебания происходит перемещение тела. Управлять направлением движения тела можно поворотом оси, вдоль которой перемещается материальная точка, на угол ср относительно подвижной системы координат. Поворот направления колебаний на угол ф не означает, что тело будет двигаться в этом направлении. Для движения по некоторой заданной траектории необходимо подобрать закон изменения угла ф, зависящий от параметров движения ф = ср(<р0,г/й,У4): утла поворота тела ф0, составляющих скорости иь, уа .

Характеристики движения тела определяются из решения уравнений движения:

Л ш

ш

^- = иь со<ф0)-УА8т(ф0), т

^ = ы45т(ф0)+у4со!<ф0), ш

(9)

О ¿Фо _

Рис. 9. Перемещаемый - ю >

объект с внутренней ^(0)=р2(0) = 4о) = х(0)=Яо)=Фо(0)= 0, материальной точкой 14 / '

где Р1 =(А1 +г»і)иь +7»!(4,(О-ЮТ!,(>)), Р2 = (Л2 +т1У>ь +™1(т)|(/) + а^1(г)) -проекции вектора импульса в подвижной системе координат; Л: = 5со-ш1(иіті1 -У4^1)-/»,(4і(0-сатіі)гіі + + - кинетический

момент; К = - сила, действующая со стороны жидкости на тело, Є -

момент этой вязкой силы; Д = М+Я.], А2=М+Х2, B = J+X3; М, / - масса тела и момент инерции без учета материальной точки; , Х2, коэффициенты присоединенных масс; ш - угловая скорость вращения; \]ь = (иь, vh) - вектор скорости движения тела (точки О,); м1 = ¿(7), V] = г|(7) - проекции скорости движения материальной точки в подвижной системе координат; ср0 - угол поворота подвижной системы координат 0£г\ относительно неподвижной Оху.

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

Заданную траекторию, по которой необходимо переместить тело, можно заменить кусочно-непрерывной линией. На каждом прямолинейном отрезке необходимо обеспечить передвижение тела из начала А, в конец отрезка А,+1. В начальной точке отрезка Л,- = (х„ уд известны значения параметров движения (<рт, Uj, V,), необходимо определить управление, позволяющее попасть в конечную точку отрезка = (*;+/, >>;+;).

Для перемещения тела в жидкости использован следующий закон движения внугренней точки (операция (| |) соответствует целой части числа):

рх sin

г <

р, cos

г--

2

г>

{ \

/

, X — t — -

7Т V Т0

r0 = fli +

1

(10)

2®! / 2со1 Л1(/) = 0.

Полученная задача оптимального управления может быть представлена в виде:

(11)

dt

где ф - управляющий параметр.

Для получения зависимости управляющей функции <р от параметров движущегося тела решается задача оптимального управления движением в заданную точку по кратчайшему маршруту. Задача сводится к дискретному аналогу и решение ищется с помощью разработанного генетического алгоритма условной оптимизации. В качестве критерия оптимальности взято минимальное отклонение тела от прямолинейной траектории:

¡¡ЛфЛ^гшп, (12)

о

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

|x-jct| ->min. (13)

Набор оптимальных траекторий передвижения тела (х,у) из точки (0;0) в точку (0;1) при разных значениях параметров (угол поворота тела ср0,

составляющих скорости иь, уь ) показан на рис.10, а соответствующее оптимальное управление движением тела на рис. 11.

У

Рис. 10. Оптимальные траектории движения тела из точки (0;0) в точку (0;1) при различных значениях параметров

Ф

3 т-

Рис. 11. Соответствующее оптимальное управление движением тела из точки

(0;0) в точку (0;1)

Зависимость управления от параметров движущегося тела ф = ф(ф0,м,у) находится на основе системы нечеткого логического вывода Сугено. Нечеткие знания формулируются в виде нечетких продукционных правил вывода, задаваемых в форме if A then В:

Rr : if е Air then у is Br, r = Tj^. (14)

Условие Xj e Alr соответствует условию разделения множества объектов

х, (w,y), / = \,т -1; j = \,п и означает попадание величины х; в нечеткий

интервал wfj с функциями принадлежности Ц+(х;) и Функция

принадлежности (х,) соответствует условию х^{м>!я), а условию

При заданном векторе Х= (х,)г =(ф0,м,у)т определяются степени истинности каждого правила: аг, г = 1, К х. Степени истинности соответствуют значениям функций принадлежности левых частей (предпосылок): аг = тт(ц*)& = 1, где gr - количество условий в данном правиле Кг. В

результате, агрегированный выходной сигнал определяется по формуле:

] и

f\W=T:—X«r Pro + LPrjXj

t-r 1

r=l

(15)

коэффициенты prJ,r = l,KR;j = 0,n определяются по имеющейся обучающей выборке.

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

Для рассмотренной задачи организации управления движением в вязкой жидкости тела с неизменяемой формой за счет перемещения внутренней массы с заданным законом Pi(0 = fei(i).Tli('))r Движения внутренней материальной точки с помощью генетического алгоритма структурно-параметрического синтеза на основе обучающего набора оптимальных траекторий (рис. 10) и соответствующего управления (рис. 11) получено следующее дерево решений:

Рис. 12. Дерево решений

В полученном дереве решений каждый путь из корня к листу определяет одно правило типа if A then В. Построенное дерево дает набор правил следующего вида:

if v > 0.05 then Ф = 3

if v < 0.05 л ф0 > -0.60 л и > 0.07 then ф = 3

if V < 0.05 л ф0 > -0.60 л и > 0.04 л и < 0.07 then ф = 2

if V < 0.05 л ф0 > -0.60 л и > -0.03 л и < 0.04 then ф = 2

if V < 0.05 л ф0 > -0.60 л и < -0.03 then ф - 3

if V <0.05 л ф0 <-0.60 л V >0.02 л и >0.12 then ф =1

if V <0.05 л ф0 <-0.60 л и >0 л V >0.02 л и <0.12 then ф = 2

if ф0 <-0.60 л v < 0.02 л V >-0.01 л и >0.17 then ф = 1

if ф0 < -0.60 л и > 0 л v < 0.02 л V > -0.01 л и < 0.17 then ф = 2

if ф0 <-0.60 л и >0 л V <-0.01 then ф = 1

if v < 0.05 л ф0 < -0.60 л и < 0 then ф = 3

Вся область значений управляющего параметра ф разбита на три интервала, и каждое правило определяет принадлежность управления к одному из них: ф=1, ф = 2, ф~3 в зависимости от значений входных параметров. Итоговое четкое значение управляющего параметра определяется как средневзвешенное по формуле (15).

Полученные правила в совокупности с функциями принадлежности ц+(х, ) и и взвешенной суммой для получения агрегированного выходного

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

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

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

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

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

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

18

работы разработанного алгоритма до 5 раз выше при неактивных ограничениях и до 3 раз - при активных.

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

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

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

5. Методы и алгоритмы реализованы в виде программного пакета для решения задач структурно-параметрического синтеза и зарегистрированы в ФГНУ «ЦИТиС» и ОФЕРНиО.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

1. Прохоровская Е.В., Тененёв В.А., Шаура A.C. Генетические алгоритмы с вещественным кодированием при решении задач условной оптимизации // Интеллектуальные системы в производстве. - Ижевск: изд. ИжГТУ, - 2008. С. 46-55.

2. Шаура A.C. Генетический алгоритм с параллельным поиском допустимых особей при решении задач условной оптимизации с ограничениями-равенствами // Интеллектуальные системы в производстве. - Ижевск: изд. ИжГТУ,-2009. С. 91-96.

3. Шаура A.C. Методы кодирования нейросетевой структуры при решении задач с помощью генетических алгоритмов // Материалы Региональной научно-технической конференции «Математическое и компьютерное моделирование технических и социально - экономических систем». - Ижевск: изд. ИжГТУ, -2010. С. 54-56.

4. Шаура A.C. Модифицированный генетический алгоритм для задач условной оптимизации // Материалы Всероссийской научно-практической конференции «Математические методы и интеллектуальные системы в экономике и образовании»: Тез. докл. - Ижевск: Типография ГОУ ВПО УДГУ, -2010. С. 128-131.

5. Шаура A.C. Решение задачи условной оптимизации с помощью генетических алгоритмов // Сборник трудов IX Международной научно-

\ J

практической конференции «Исследование, разработка и применение высоких технологий в промышленности» Т.З: Тез. докл. - СПб.: изд. Политехнического университета,-2010. С. 170-174.

6. Модифицированный генетический алгоритм для решения задач условной оптимизации: свидетельство о регистрации электронного ресурса № 16503 // Тененев В .А., Шаура A.C. Инв. № 50201050246, дата регистрации 10.12.2010.

7. Шаура A.C. О применении генетических алгоритмов к решению коалиционных игр // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Ионтрягинские чтения»: Тез. докл. - Воронеж: Издательско-полиграфический центр Воронежского государственного университета, -2011. С. 214-215.

8. Шаура A.C. Применение генетических алгоритмов для решения игровых задач с коалиционной структурой // Интеллектуальные системы в производстве. - Ижевск: изд. ИжГТУ, - 2011. С. 68 - 74.

9. Генетический алгоритм для решения игровых задач с коалиционной структурой: свидетельство о регистрации электронного ресурса № 17777 // Тененев В.А., Шаура A.C. Инв. № 50201250032, дата регистрации 10.01.2012.

10. Построение деревьев решений с помощью генетического алгоритма структурно-параметрического синтеза // Интеллектуальные системы в производстве. — Ижевск: изд. ИжГТУ, - 2012. С. 72 - 80.

11. Шаура A.C. Решение задачи структурно-параметрической оптимизации с помощью генетических алгоритмов. // Материалы II Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Измерения, контроль и диагностика - 2012». - Ижевск: изд. ИжГТУ, - 2012. С. 21-22.

12. Tenenev V., Vetchanin Е., 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.

В авторской редакции

Подписано в печать 26. 09.12. Усл. печ. л. 1,16. Заказ № 289. Тираж 100 экз. Издательство Ижевского государственного технического университета имени М. Т. Калашникова Отпечатано в типографии Издательства ИжГТУ. 426069, Ижевск, Студенческая, 7

Условные обозначения и сокращения.

Введение.

Глава 1 Структурно-параметрический синтез в задачах управления.

1.1 Проблема управления сложными системами.

1.2 Задача структурно-параметрического синтеза.

1.3 Применение генетических алгоритмов для решения задач оптимизации

Выводы.

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

2.1 Постановка задачи условной оптимизации.

2.2 Методы решения оптимизационных задач с ограничениями.

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

2.4 Многопопуляционный генетический алгоритм для решения задач условной оптимизации.

2.5 Исследование многопопуляционного генетического алгоритма на решении задач условной оптимизации.

Выводы.

Глава 3 Генетический алгоритм структурно-параметрического синтеза для управления системами.

3.1 Структурная оптимизация.

3.3.1 Последовательное эволюционное выращивание структуры как подход к решению задач структурного синтеза.

3.3.2 Решение задачи управления группой объектов с помощью структурного синтеза.

3.2 Структурно-параметрическая оптимизация.

3.2.1 Эволюционный алгоритм решения задачи структурно-параметрической оптимизации.

3.2.2 Генетическое кодирование.

3.2.3 Оператор мутации.

3.2.4 Оператор скрещивания.

3.2.5 Применение структурно-параметрического синтеза для решения задачи построения нейронной сети.

3.3 Построение дерева решений с помощью генетического алгоритма структурно-параметрической оптимизации.

3.3.1 Деревья решений.

3.3.2 Генетическое кодирование деревьев решений.

3.3.3 Функция'1 приспособленности деревьев решений и генетические операторы скрещивания и мутации.

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

Выводы.

Глава 4 Решение задачи управления движением системы с помощью генетического алгоритма структурно-параметрического синтеза.

4.1 Движение системы за счет перемещения внутренней массы.

4.2 Управление движением системы.

4.3 Программный пакет для решения задач управления системами.

Выводы.

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

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

В отдельных областях деятельности существуют подходы для решения частных задач синтеза. Так во многих работах отечественных и иностранных исследователей рассматриваются вопросы синтеза РЭА: фильтров, усилителей, СКЦ; проблемы создания строительных конструкций; в работах таких авторов rt ' I,} Ii 1 ( 1 1 ц | f \ -J '<^4 (1 м I Ii j i\ ( Ь л , t ' Ii, t * И ht '' I,1 ' 'и i как J. Koza, K.O. Stanley, Ri Miikkulainen, S^ Nolfi, D. Parisi,F. Gruau,1 H: Kitano, В.Г. Редько, Ю.Р. Цой - подходы к построению оптимальных нейронных сетей и моделей искусственного интеллекта на основе эволюционных методов. Большое значение имеют задачи оптимального управления движением мобильных технических систем.

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

В последние годы широкое развитие получили методы Data Mining, в частности деревья решений ; (E.Bi Hunt^ v Stone, J.R. Quinlan), и аппарат нечеткой логики (L. Zadeh, Т. Takagi, М. Sugeno, Е. Mamdani) для моделирования и управления системами. Перспективным направлением стало 5 использование этих технологий в сочетании с эволюционными методами. Эффективность такого подхода показана в работах J. Koza, F. Herrera, Н. Tanaka, N. Yamamoto, Д. Рутковской, В.А. Тененева. Отсутствие единого подхода к решению задач оптимального структурно-параметрического синтеза для управления системами приводит к необходимости сочетать методы различной природы на отдельных этапах построения модели.

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

Область исследования. Диссертационная работа выполнена в соответствии с пунктами 4 — «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации», 5 - «Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации» и 7 - «Методы и алгоритмы структурноt параметрического i,синтеза 11 и,4 идентификации; .сложных;; систем»!'¿паспорта,. специальности' 05.l3.0P'- «Системный 'анализ, управление и»]обработка' i информации (в науке и технике)».

Объектом исследования являются структурно-параметрические модели сложных и технических систем.

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

Целью диссертационной работы является разработка методов структурно-параметрической оптимизации на основе генетических алгоритмов для управления системами. Задачи исследования 1. Разработать метод структурно-параметрической оптимизации 1 на основе i' эволюционного алгоритма, обеспечивающий одновременный поиск наиболее простой структуры и оптимальных значений параметров для решения задач системного анализа, оптимизации, управления, принятия решения. •Г 2. Построить генетический алгоритм для решения задач условной оптимизации, позволяющий непосредственно учитывать ограничения на этапе отбора.

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

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

Методы исследования, достоверность и обоснованность результатов.

В работе использованы теоретические методы исследования и методы | численного решения задачи оптимального синтеза, интеллектуальные методы V организации управления системами. Работа строится на известных данных и теоретических положениях системного анализа, теории оптимизации и ^й'и'Л* и ;управления, \математического моделирования, „ теориимигр. Достоверность ,

1 <*111 : дай^.о хм ^ ^¡.АО^Ч'^ > полученных результатов подтверждается корректностью "разработанных математических моделей и методов, использованием известных положений фундаментальных наук, сходимостью полученных результатов с результатами применения существующих методов. На защиту выносятся

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

2. Метод построения нечетких продукционных правил, основанный на решении задачи структурно-параметрического синтеза.

3. Многопопуляционный генетический алгоритм решения задачи условной оптимизации. кн/'^ 4. Решение задачи оптимального управления , движением в | жидкости

IV'/;» ' " , 1 V ,с ', ' ' 1 1 • Ь

И* объекта с внешней жесткой оболочкой и внутренней движущейся материальной точкой.

Научная новизна результатов исследования и результатов, полученных лично автором, заключается в следующем: я*

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

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

I'

Т генетического алгоритма;

- с использованием алгоритма синтеза деревьев решении решена задача

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

V I

Практическая ценность. Разработанные в диссертации методы ' * .• позволяют^,;решать- задачи < ; управления,. ли; * оптимального;/,„структурно-, ? )( ! 1 обеспечивая принятие управленческих решений в процессе моделирования сложных и технических систем. В работе показана общность задач оптимизации, возникающих в различных областях деятельности. Предложенные подходы обладают в большой степени гибкостью и универсальностью и могут быть рекомендованы к использованию вне зависимости от природы исследуемых в задачах объектов. ,, Результаты диссертации могут быть использованы в учебном процессе

Ш\ высшей школы при подготовке соответствующих специалистов. с IV

Личный вклад. Автором разработан генетический алгоритм у," и( оптимального структурно-параметрического синтеза и выполнена его ж; II реализация в виде , программного пакета для решения , задачи управления

ТО М "'Г' 1" »4 'Ь >> ^П'Г'Л^П''1 1 ' '' ' ' Vм {>7/ '' системами. Разработаны и реализованы методы решения задач условной оптимизации и построения деревьев решений. Получена система нечетких

IV ( V Л

Я 1л у 8 4

I! правил на основе дерева решений для управления движением системы за счет перемещения внутренней материальной точки.

Апробация работы. Основные положения диссертации докладывались и получили положительную оценку на следующих научных конференциях: Региональная научно-техническая конференция «Математическое и компьютерное моделирование технических и социально - экономических систем» (Ижевск, 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» (Ижевск, июнь 2012r.).

1,1'' i f w i» * ' и' 4 'f ^ t ''(¿»T i ' t "л \ \>' '■)'1 » »'J t ' '' N''1 / Л1!

По теме диссертации делались1 сообщения и доклады на ¡ научнопрактических конференциях ИжГТУ 2009-2012 гг.

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

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, библиографического списка, включающего 112 наименований. Текст диссертации изложен на 120 листах машинописного текста, содержит 36 рисунков, 12 таблиц.

выводы

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

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

Методы и алгоритмы реализованы в виде программного пакета для решения задач структурно-параметрического синтеза и управления и зарегистрированы в ФГНУ «ЦИТиС» и ОФЕРНиО.

ЗАКЛЮЧЕНИЕ

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

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

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

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

1 > компактные деревья и продукционные правила для систем нечеткого вывода.

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

5. Методы и алгоритмы реализованы в виде программного пакета для решения задач структурно-параметрического синтеза и зарегистрированы в ФГНУ «ЦИТиС» и ОФЕРНиО.

1. Автоматизация поискового конструирования / Под ред. А.И. Половинкина.

2. М.: Радио и связь, 1981. 344 с.

3. Акимов C.B. Общая методология синтеза различных классов транзисторныхусилителей СВЧ // Труды учебных заведений связи. 2001. №166. С. 79-83.

4. Акимов C.B. Опыт использования универсальной модели лестничной цепи //56.я НТК СПбГУТ. 2004. С. 74.

5. Бабак Л.И. Синтез согласующих цепей и цепей связи транзисторныхширокополосных усилителей по областям иммитанса // Радиотехника и электроника. 1995. Т. 40, № 10. С. 1550 1560.

6. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука,1987. 600 с.

7. Волкова Л.Ю., Яцун С.Ф. Управление движением трехмассового робота,перемещающегося в жидкой среде // Нелинейная динамика. 2011. Т. 7, №4. С. 845-857.

8. Воробьев H.H. Коалиционные игры // Теория вероятностей и ее применения.1967. Т. 12, №2. С. 289-306.

9. Гилл Ф., МюррэйУ. Численные методы условной оптимизации. М.: МИР, 1977. 297 с.

10. Гуляшинов А.Н., Тененев В.А., Якимович Б.А. Теория принятия решений в сложных социотехнических системах. Ижевск: Изд. ИжГТУ, 2005. 280 с.

11. Дербин A.C., Завгородний М.А., Иванов П.Н., ЛыпарьЮ.И. Модели структурного синтеза систем управления // XXX Юбилейная неделя науки СПбГТУ. 2002. Ч. 7. С. 58.

12. Директор С., Рорер Р. Введение в теорию систем. М.: МИР, 1974. 464 с.

13. Дорофеев С.Ю. Интеллектуальная система автоматизированного проектирования СВЧ-устройств INDESYS / С.Ю. Дорофеев, Л.И. Бабак, A.C. Барышников и др. // Информационные технологии. 2010. № 2. С. 42 -48.

14. Исаев С.А. Решение задач нелинейного программирования с использованием схем самоадаптации при построении штрафных функций // Исследовано в России. 2005. № 126. URL: http://zhurnal.ape.relarn.ru/articles/2005/126.pdf (дата обращения: 25.09.2011).

15. Козлов В.В., Онищенко Д.А. О движении в идеальной жидкости тела, содержащего внутри себя подвижную сосредоточенную массу // ПММ. 2003. Т. 67, № 4. С.620 633.

16. Козлов В.В., Рамоданов С.М., О движении изменяемого тела в идеальной1.и

17. V.w*- »' ' ^ V'""! '«vw»'ни*,v Ч!' л;íW >''>Ми, " V» Ч I' • « ' «»• V I • О» »Ц \ » ',9 " * rfil'* ,v Í жидкости//ПММ. 2001Т. 65,-№4. С: 592-601: ^1. Члt ' , 'Ч « ^

18. Лоран П.-Ж. Аппроксимация и оптимизация. М.: МИР, 1975. 496 с.

19. Лыпарь Ю.И. Автоматизация проектирования избирательных усилителей и генераторов. Л.: Изд. ЛГУ, 1983. 164 с.

20. Лыпарь Ю.И. База знаний для систем проектирования и обучения // Региональная информатика-96. 1996. Ч. 2. С. 251 -252.

21. Лыпарь Ю.И., Станкевич Л.А. Когнитивные структуры в системе управления гуманоидного робота // Мехатроника, автоматизация, управление. 2002. № 7. С. 7 10.

22. Методы робастного, нейро-нечеткого и адаптивного управления / Под. ред. Н.Д. Егупова. М.: Изд. МГТУ им. Н.Э. Баумана, 2002. 744 с.л ' , ' 1 . м' ' Л '''' '

23. Новиков Д.А., Петраков С.Н. Курс теории активных систем. М.: СИНТЕГ, 1999. 108 с.

24. Одрин В.М., Картавов С.С. Морфологический анализ систем. Построение морфологических таблиц. Киев: Наукова думка, 1977. 280 с.

25. Оуэн Г. Теория игр. М.: Мир, 1971. 229 с.

26. Паклин Н.Б., Тененев В.А. Гибридный генетический алгоритм с дополнительным обучением лидера // Интеллектуальные системы в производстве. 2003. № 2. С. 181 206.

27. Прохоровская Е.В., Тененев В.А., Шаура A.C. Генетические алгоритмы с вещественным кодированием при решении задач условной оптимизации // Интеллектуальные системы в производстве. 2008. № 2. С. 46-55.

28. Рамоданов С.М., Тененев В.А. Движение тела с переменной геометрией масс в безграничной вязкой жидкости // Нелинейная динамика. 2011. Т. 7. № 3. С. 635-648.

29. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия, 2004. 452 с.

30. Свирщева Э.А. Структурный синтез неизоморфных систем с однороднымиt \) I . л; , ' > ' J.s ** • )» , ' ■ . > и . j if -и ;компонентами. Харьков: ХТУРЕ, 1998. 256 с. '

31. Сушков Ю.А. Об одном способе организации случайного поиска // Автоматика и вычислительная техника. 1974. № 6. С. 41 48.

32. Тененев В.А. Применение генетических алгоритмов с вещественным кроссовером для минимизации функций большой размерности // Интеллектуальные системы в производстве. 2006. № 1. С. 93 107.

33. Тененев В.А., Ветчанин Е.В. Управляемое движение тела в жидкости при возвратно-поступательном перемещении внутренней материальной точки // Интеллектуальные системы в производстве. 2011. №2. С. 62 72.

34. Тененев В.А., Якимович Б.А. Генетические алгоритмы в моделировании систем. Ижевск: изд. ИжГТУ, 2010. 308 с.

35. Тененев В.А., Якимович Б.А., ПаклинН.Б. Оптимальное управление детерминированными и нечеткими системами // Вестник ИжГТУ. 2003. №4. С. 35-40.

36. Черноусько Ф.Л., Болотник H.H. Мобильные роботы, управляемые движением внутренних тел // Труды института математики и механики УрО РАН. 2010. Т. 16, №5. С. 213 222.

37. Шаура A.C. Генетический алгоритм с параллельным поиском допустимых особей при решении задач условной оптимизации с ограничениями-равенствами // Интеллектуальные системы в производстве. 2009. № 1. С. 91-96.

38. Шаура A.C. Построение деревьев решений с помощью генетического алгоритма структурно-параметрического синтеза // Интеллектуальные системы в производстве. 2012. № 1. С. 72 80.

39. Шаура А.С. Решение задачи условной оптимизации с помощью генетических алгоритмов // Сборник трудов IX Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». 2010. Т. 3. С. 170 174.

40. Abadie J., Carpentier J. Generalization of the Wolfe reduced gradient method to the case of nonlinear constraints // Optimization (R. Fletcher, ed.). 1969. P. 37 -49.

41. AlonsoL., SchottR. Random Generation of Trees. Boston: Kluwer Academic• 1 HI , , 'I1. Publishers, 1995. 208 p.

42. Boers E.J.W., Kuiper H., Happel B.L.M. Designing modular artificial neural networks // Proc. Computing Science in the Netherlands. 1993. Pp. 87 96.

43. Box MJ. A new method of constrained optimization and a comparison with other methods // Comput. J. 1965. Vol. 8. P. 42 52.

44. BreimanL., Friedman J.H., Olshen R. A., Stone C. J. Classification and regression trees. California: Wadsworth & Brooks, 1984. 368 p.

45. Cangelosi A., Parisi D., Nolfi S. Cell division and migration in a genotype for neural networks // Network: Computation in Neural Systems. 1993. Vol. 5. Pp. 497-515.

46. Casillas J., Gordon O., del Jesus M.J. Genetic tuning of fuzzy rule deep structures for linguistic modeling. Technical Report DECSAI-010102. Granada: University of Granada, 2001. 8 p.

47. Chen D. Graph-Based Evolutionary Design of Arithmetic Circuits / D. Chen, T. Aoki, N. Homma et al. // IEEE trans, on Evolutionary Computation. 2002. Vol. 6, № l.Pp. 86-100.

48. At, r. >.,.,,', 50. Childress S., Spagnolie S.E., Tokieda T., A ,bug on a raft: recoil locomotion in ai) ' ^ 1 ' r > ^Pw/i' /< 7 ■ ■ v.* >,,/•'' 11 '' 1 viscous fluid//J. Fluid Mech. 2011. Vol. 669. PP: 527-556: " • ' '

49. De Jong K.A. Analysis of the behavior of class of genetic adaptive systems: PhD thesis. University of Michigan, 1975.

50. Espejo P.G., VenturaS., HerreraF. A survey on the application of genetic programming to classification // IEEE Transactions on Systems, Man and Cybernetics. 2010. Vol. 40, №2. Pp. 121 144.

51. Fiacco A.V., McCormic G. P. Extensions of SUMT for nonlinear programming: equality constraints and extrapolation // Mgnt Sci. 1966. Vol. 12. P. 816 829.

52. Friedman P., Pinder K.L. Optimization of a simulation model of a chemical plant // Ind. Eng. Chem. Process Des Develop. 1972. Vol. 11. P. 512 520.

53. Garcia-Almalanza A.L., Tsang E.P.K., Galvan-Lopez E. Evolving Decision Rules1.I 1 " ■ « 1 sto Discover Patterns // Computational methods in financial engineering. 2008. №2. Pp. 239-255.

54. Ghani S.N. An improved complex method of function minimization // Computer Aided Design. 1972. Vol. 4. P. 71 78.

55. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Boston: Addison-Wesley, 1989. 412 p.

56. Goldberg D.E. Real-coded Genetic Algorithms, Virtual Alphabets and Blocking // Complex Systems. 1991. №5. Pp. 139 167.

57. Gruau F. Automatic definition of modular neural networks // Adaptive Behavior. 1995. Vol.3. Pp. 151-183.

58. Gruau F. Genetic synthesis of Boolean neural networks with a cell rewriting developmental process // Proc. of the Int'l Workshop on Combinations of Genetic Algorithms and Neural Networks. 1992. Pp. 55 74.

59. GuinJ.A. Modification of the complex method of constrained optima // Comput. J. 1968. Vol. 10. P. 416 417.

60. Herrera F., Lozano M., Verdegay J.L. Tackling real-coded genetic algorithms: operators and tools for the behavior analysis // Artificial Intelligence Review. 1998. Vol. 12, №4. Pp. 265 319.

61. Holland J.H. Adaptation in Natural and Artificial Systems. Michigan: University of Michigan Press, 1975. 183 p.

62. Holstien R.B. Artificial genetic adaptation in computer control systems: PhD thesis. University of Michigan, 1971.

63. Hooke R., Jeeves T.A. Direct search solution of numerical and statisticalproblems // JACM. 1961. Vol. 8. P. 212 229.., > > ii*

64. Howe M.S. On the force and moment on a body in an incompressible fluid, with application to rigid bodies and bubbles at high and low Reynolds numbers // Q. J. Mech. Appl. Math. 1995. № 48. Pp. 401 426.

65. Kalganova T., Miller J.F. Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness // Proceedings of 1st NASA. 1999. Pp. 54.

66. Ke Tang, Tsang E.P.K., Xin Yao. A Memetic Genetic Programming with Decision Tree-based Local Search for Classification Problems // Evolutionary Computation. 2011. Pp. 917 924.

67. KitanoH. Designing neural network using genetic algorithms with graph generating system // Complex Systems. 1990. Vol. 4. Pp. 461 476.

68. Koza J.R. Concept formation and decision tree induction using the genetic programming paradigm. In Parallel Problem Solving from Nature // Proceedings of 1st Workshop. 1990. Pp. 124 128.

69. Koza J.R. Genetic Programming: On the Programming of Computers by Meansif t 1 • • < <• i • v<, <Y f r > * ' ' > " » '< * ' 1 * ,.< \ :

70. Koza J.R. Automated Synthesis of Analog Electrical Circuits by Means of Genetic Programming / J.R. Koza, F.H. Bennett, D. Andre et al. // IEEE trans, on Evolutionary Computation. 1997. Vol. 1, № 2. P. 109 128.

71. Koza J.R. Human-Competitive Machine Intelligence by Means of Genetic Algorithm // MI: Center for the Study of Complex Systems. 1999. Pp. 15 22.

72. Koza J.R., Rice J.P. Genetic generation of both the weights and architecture for a neural network // Proceedings of the IJCNN. 1991. Vol. 2. Pp. 397 404.

73. Lawrence J.P., Emad F.P. An adaptive rahdomized pattern search // Proceedings of 1972 IEEE Conference on Decision Control and 11th Symposium on Adaptive Processes, New Orleans, 13-15 December. 1972. P. 421-425.

74. Lindenmayer A., Rozenberg G. Automata, Languages, . Development. Amsterdam: North-Holland, 1976.529 p^ >Y '*"'"' J)' M'

75. Luus R., Jaakola T.H.I. Optimization by direct search and systematic reduction of the size of search region // A. I. Ch. E. Journal. 1973. Vol. 19. P. 760 766.

76. Man K.F., Tang K.S., Kwonq S. Genetic Algorithms for Control and Signal Processing. Berlin: Springer, 1997. 211 p.

77. Mendes R.R.F., Voznika F. de B., Freitas A.A. Discovering fuzzy classification rules with genetic programming and co-evolution // Proceedings of 5th European Conference on Principles and Practice of Knowledge Discovery in Databases. 2001. Pp. 314-325.

78. Miller G.F., Todd P.M., Hegde S.U. Designing neural networks using genetic algorithms // Proceedings of the Third International Conference on Genetic Algorithms. 1989. Pp. 379 384.

79. Mittal R, Dong H., Bozkurttas M. A versatile sharp interface immersed boundary method for incompressible flows with complex boundaries // J. of Computational Physics. 2008. Vol. 227. Pp. 4825 4852.

80. Mugele R.A. A program for optimal control of nonlinear processes // IBM ,, i ., , Systems Journal. 1962. Vol. 1. P. 2 17. ,., \ ,, i , > t\ . . . <tf ¡«Wi^M'.^ -ah*.1

81. Nagarajan U., Kantor G., Hollis R.L. Trajectory Planning and Control of an Underactuated Dynamically Stable Single Spherical Wheeled Mobile Robot // Proceedings of the 2009 IEEE international conference on Robotics and Automation. 2009. Pp. 2803 2808.

82. Nelder J.A., Mead R. A simplex method for function minimization // Comput. J. 1965. Vol. 7. P. 308-313.

83. Nolfi S., Floreano D. Synthesis of Autonomous Robots Through Evolution // Trends Cogn Sci. 2002. №6. Pp. 31 37.

84. Nolfi S., Parisi D. Genotypes for neural networks // Handbook of brain theory and neural networks. 1995. Pp. 431 -434.

85. Nolfi S., Parisi D. Growing neural networks. Technical report. Rome: Institute of ' Psychology, 1991. 15 p. ' w '

86. NordinP., BanzhafW., and Francone F. D. Efficient evolution of machine code for CISC architectures using instruction blocks and homologous crossover //- Advances in Genetic Programming. 1999. Pp. 275 299.

87. Quinlan J.R. Induction of Decision Trees // Machine Learning. 1986. Vol. 1. Pp. 81-106.

88. Regolin E.N. and Pozo A.T.R. Bayesian automatic programming // Proceedings of the 8th European Conference on Genetic Programming. 2005. Pp. 38 — 49.

89. SaravananN. and FogelD.B. Evolving neural control systems // IEEE Expert. ' 1995. Vol. 10. Pp. 16-22.

90. Singer E. Simulation and optimization of oil refinery design // Chem. Eng. Progr. Symp. Ser. 1962. Vol. 37. P. 58.

91. Spendley W., Hext G.R., Himsworth F. R. Sequential application of simplex designs in optimization and evolutionary design // Technometrics. 1962. Vol. 4. P. 44i461.

92. Sripramong T., Toumazou C. The Invention of CMOS Amplifier Using Genetici,s ¡¡.i' Programming and Current-Flow Analysis//IEEE transactions on computer-aided , „design of integrated circuits and systems. 2002. Vol. 21, № 11. P. 1237 — 1252.

93. Stanley K.O., Miikkulainen R. Evolving Neural Networks through Augmenting Topologies // Evolutionary Computation. 2002. № 2(10). Pp. 99 127.

94. Swann W.H. Report on the development of a new direct search method of optimization // CIL Research Note 64/3. 1964.

95. Takagi T., Sugeno M. Fuzzy Identification of Systems and Its Applications to Modeling and Control // IEEE Trans. SMC. 1985. Vol. 15, No. 1, Pp. 116 132.

96. 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. 2012. Pp. 62-63.

97. Tomic F., Nudehi S., Flynn L.L. Design, Fabrication and Control of Spherobot: ,

98. A Spherical Mobile Robot // J. Intell. Robot Syst. 2012. Vol. 67, №2. Pp. 117 -131.

99. Vaario J., OnitsukaA. and ShimoharaK. Formation of Neural Structures // Proceedings of the Fourth European Conference on Artificial Life. 1997. Pp. 214-223.

100. Wang P., TsanqP.K., WeiseT. Using gp to evolve decision rules for classification in financial data sets // Proc. of the 9th IEEE ICCI. 2010. Pp. 722 -727.

101. Whitley D., GruauF., PyeattL.D. Cellular encoding applied to neurocontrol// Proc. Of the 6th International Conference on Genetic Algorithms. 1995. Pp. 460

102. Whitley D. Genetic Algorithms and Neural Networks // Genetic Algorithms in Engineering and Computer Science. 1995. Pp. 191-201.

103. Whitley D., Starkweather T., Bogart C. Genetic algorithms and neural network: optimizing connections and connectivity // Parallel Computing. 1990. Vol. 14. Pp. 347-361.

104. Wieland A. Evolving neural network controllers for unstable systems // International Joint Conference on Neural Networks. 1991. Vol. 2. Pp. 667 673.

105. Wo-Chiang Lee. Genetic Programming Decision Tree for Bankruptcy Prediction // Proceedings of the 2006 Joint Conference on Information Sciences JCIS. 2006. Pp. 4-7.

106. Xin Yao. Evolving Artificial Neural Networks // Proceedings of the IEEE. 1999. Vol. 87, №9. Pp. 1423 1447.

107. Yangsheng Xu, Yongsheng Ou. Control the Single Wheel Robots. SpringerVerlag, 2005. 212 p.

108. ZhangB.-T., MuhlenbeinH. Evolving optimal neural networks using genetic algorithms with Occam's razor // Complex Systems. 1993. Vol. 7. Pp. 199 220.

109. Zwicky F. Discovery, Invention, Research through the Morphological Approach. New York: McMillan, 1969. 276 p.469.