ID: 38433

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

Категория: Дипломная

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

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

Язык: Русский

Дата добавления: 2013-09-28

Размер файла: 3.77 MB

Работу скачали: 9 чел.

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

Инженерный факультет

Кафедра Кибернетики и мехатроники

УТВЕРЖДАЮ

Зав. кафедрой

Кибернетики и мехатроники

_____________ К.А.Пупков

«___»_____________2013 г.

ДИПЛОМНАЯ РАБОТА

на тему

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

550200-Управление в технических системах

Степень бакалавра техники и технологий

Разработчик:

Студент группы  ИУБ-402 (4 курс)

Студенческий билет №1032071048

_________________  К.В.Березин

     Руководитель:

          _____________ А.И.Дивеев

Москва  2013г.

Оглавление

[1] Введение [2] Постановка задачи [3] Генетическое программирование и генетический алгоритм [4] Метод сетевого оператора [4.1] Свойства сетевого оператора [4.2] [4.3] Матрица сетевого оператора [4.4] Вариации сетевого оператора [4.5] Вектор сетевого оператора [5] Метод интеллектуальной эволюции [6] Вычислительный эксперимент [7] Заключение [8] Список используемой литературы [9] Приложение

Введение

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

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

Развитие компьютерных технологий за последние десятилетия позволило создать вычислительные методы, которые способны найти структуру по математическому выражению. Один из таких методов — генетическое программирование, разработанный в 1992 году Джоном Коза[1]. Данный метод позволяет получить структуру математического выражения в виде строки символов, используя бесскобочную запись операторов и операндов на польском языке.

Впоследствии созданный Д. Коза метод, был существенно доработан. В 1999 г. О’Нейл и К. Райн создали метод грамматической эволюции[2], который кодировал части программы в формат бесскобочных битовых строк фиксированной длины. А в 2003 г. И. Зелинка создал метод аналитического программирования[3], использующий алгоритм дифференциальной эволюции для поиска оптимального решения.

В 2006 г. появился метод сетевого оператора[4-10], являющийся модификацией метода генетического программирования.

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

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

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

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

,             (1.1)

,             (1.2)

,               (1.3)

Где x, y — координаты центра масс объекта на плоскости, φ — угол между вектором скорости и осью x,  — компоненты вектора управления u = [,  , который регулирует напряжение на моторах в гусеницах робота.

Управление ограниченно так, что

           (1.4)

Как видно из выражения (1.4), управление может принимать как положительные, так и отрицательные значения. Функционалы (1.5) и (1.6) описывают задачу управления.

,               (1.5)

,                 (1.6)

— критическая ошибка.

,

 — время процесса управления.

 — малая положительная величина,   — максимальное время процесса управления,   ,  , —  конечные условия.

Множество начальных значений задано следующим образом:

.      (1.7)

Задача состоит в том, чтобы синтезировать систему управления и минимизировать функционалы так, чтобы

,           (1.8)

где  — множество параметров, которые нужно определить.

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

Для решения (1.1) — (1.8) будет использован метод сетевого оператора.

Генетическое программирование и генетический алгоритм

Историю создания генетического программирования уже была затронута во введении. Теперь же остановимся более подробно на принципах его работы и особенностях[11,15,16,24,27,28].

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

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

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

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

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

Алгоритм моделирует те процессы в популяциях, которые являются существенными для развития. Генетический алгоритм работает с совокупностью “особей” - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее “приспособленности” согласно тому, насколько “хорошо” соответствующее ей решение задачи. Воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи.

Генетический алгоритм состоит из следующих шагов:

1.  инициализация, или выбор исходной популяции хромосом;
2.  оценка приспособленности хромосом в популяции – расчет функции приспособленности для каждой хромосомы;
3.  проверка условия остановки алгоритма;
4.  селекция хромосом – выбор тех хромосом, которые будут участвовать в создании потомков для следующей популяции;
5.  применение генетических операторов – мутации и скрещивания;
6.  формирование новой популяции;
7.  выбор «наилучшей» хромосомы.

Преимущества генетического алгоритма:

+ Не требует информации о поверхности ответа;

+ Разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;

+ Стоик к попаданию в локальные оптимумы;

+ Хорошо работает при решении крупномасштабных проблем оптимизации;

+ Можно использовать для широкого класса задач;

+ Обладает простой реализацией;

+ Можно использовать в задачах с изменяющейся средой.

Недостатки:

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

Особенности:

1. Варианты решения кодируются битовой строкой (хромосома);

2. Поиск осуществляется в кодовом пространстве параметров;

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

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

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

6. Скрещивание обеспечивает построение пары новых  кодов решений на основе двух отобранных;

7. Мутация обеспечивает случайную вариацию кода возможного решения;

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

9. Решение - хромосома, которая дает наилучшее значение функции приспособленности.

Метод сетевого оператора

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

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

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

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

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

Множество переменных:

                (2.1)

Множество параметров:

                (2.2)

Множество унарных операций:

          (2.3)

Множество бинарных операций:

          (2.4)

Среди унарных операций всегда должна присутствовать тождественная операция:

,           (2.5)

Бинарные операции должны быть коммутативны

,           (2.6)

ассоциативны

,     (2.7)

 и иметь единичный элемент

,       (2.8)

Определение 1. Программная запись математического выражения[4] — это запись выражения с помощью элементов конструктивных множеств (2.1) — (2.4).

Определение 2. Графическая запись математического выражения[4] — это запись бинарной операции, которая отвечает следующим требованиям:

1) аргументами бинарной операции являются унарные операции или единица, соответствующая данной бинарной операции;

2) аргументом унарной операции является либо бинарная операция, либо элемент из множеств переменных или параметров;

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

Любую программную запись математического выражения можно перевести в графическую запись.

Свойства сетевого оператора

Определение 3. Сетевой оператор — это ориентированный граф, обладающий следующими свойствами[4].

1) в графе отсутствуют циклы;

2) к любому узлу, не являющемуся источником, имеется хотя бы один путь от узла-источника;

3) от любого узла, который не является стоком, имеется хотя бы один путь до узла-стока;

4) каждому узлу источнику соответствует элемент из множества переменных X и множества параметров Q;

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

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

На основании определения 3 сетевой оператор можно формально записать с помощью упорядоченного набора из шести множеств

где G — сетевой оператор,  — множество узлов,  — множество дуг или множество упорядоченных пар узлов,  X — множество переменных (2.1), Q — множество параметров (2.2),  — множество унарных операций (2.3),  — множество бинарных операций (2.4).

Любой ориентированный граф обладающий свойствами (1 — 6) сетевого оператора описывается математическим выражением.

Любой сетевой оператор с L узлов и N + P < L узлов-источников описывается L - N - P математическими выражениями.

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

1) унарные операции выполняются только для дуги, которая выходит из узла, не имеющего ни одной входящей в него дуги;

2) после вычисления унарной операции по дуге эту дугу исключают из графа;

3) вычисление бинарной операции над узлом выполняется сразу после унарной операции связанной с дугой входящей в данный узел;

4) вычисления заканчиваются, когда в графе будут исключены все дуги.

Определение 4. Однотипные сетевые операторы[4] — это сетевые операторы, для которых выполняются следующие условия:

а) узлы-источники совпадают;

б) используют одинаковые конструктивные множества:

Определение 5. Подобные сетевые операторы[4] — это однотипные сетевые операторы, у которых одинаковое число узлов.

Определение 6. Структурно-подобные сетевые операторы[4] — это подобные сетевые операторы, которые отличаются только унарными и бинарными операциями, связанными с дугами и узлами.

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

Рис. .Пример сетевого оператора

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

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

Рис. . Граф сетевого оператора после первой итерации

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

Рис. . Граф сетевого оператора после второй итерации

Рис. . Граф сетевого оператора после третьей итерации

Рис. . Граф сетевого оператора после четвертой итерации

Рис. . Граф сетевого оператора после пятой итерации

Рис. . Граф сетевого оператора после шестой итерации

Рис. . Граф сетевого оператора после седьмой итерации

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

,

,

,

.

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

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

.

,

,

,

,

,

.

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

  = 0 ,  = 1,

 ,  = 0 ,

 = 0 , = 0 ,

 = 0 ,  = 0.

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

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

,

,

,

,

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

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

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

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

Для данного уравнения имеются множества:

,

,

,

.

На рисунке 9 изображен граф сетевого оператора из рассмотренного нами примера.

Рис. . Пример графа сетевого оператора

Матрица сетевого оператора

Для представления сетевого оператора в памяти ПК мы используем матрицу сетевого оператора (МСО). Она основана на матрице смежности ориентированного графа A = [], , где L количество узлов графа.

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

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

Рис. . Граф сетевого оператора с топологической нумерацией

Каждый номер узла связан со строкой матрицы. Сетевому оператору, показанному на рисунке 10, соответствует  матрица:

МСО =,  имеет верхний треугольный вид из-за нумерации узлов. Одной МСО недостаточно для вычисления математического выражения, так как она не содержит информации о параметрах и переменных. Эта информация хранится в базовых значениях  вектора узлов.

.                 (3.1)

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

. (3.2)

Чтобы вычислить математическое уравнение по его МСО, нужно последовательно взглянуть на ее строки i =   . В каждой строке i мы рассматриваем элементы, следующие за диагональным элементом,. Если среди них имеется ненулевой элемент, то производится подсчет согласно уравнению (2.2).

Для данной МСО получим:

,

,

,

,

,

,

,

=

=

Вариации сетевого оператора

Вариация сетевого оператора — это такое изменение сетевого оператора, которое приводит к однотипному сетевому оператору[4].

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

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

Номер вариации	Наименование вариации
0	Изменение унарной операции, связанной с дугой сетевого оператора.
1	Изменение бинарной операции, связанной с узлом сетевого оператора.
2	Добавление дуги вместе с унарной операцией.
3	Удаление дуги, если узел, куда дуга входит, имеет еще входящую дугу.
4	Увеличение номеров узлов.
5	Уменьшение номеров узлов.
6	Добавление узла бинарной операцией и входящей в узел дуги, связанной с унарной операцией.
7	Удаление узла вместе с входящей в него дугой, если узел является узлом-стоком и в него входит только одна дуга.

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

0) Определяем дугу  и меняем номер унарной операции, с которой связана дуга .

1) Определяем узел  и меняем номер бинарной операции, с которой связан узел

2) Определяем два узла  и добавляем дугу между ними  вместе с унарной операцией .

3) Определяем дугу , проверяем, если в узел j входит еще одна дуга , то удаляем дугу .

4) Определяем номер j, который будет присвоен последнему узлу L. Проверяем, если не существует узлов, начиная с номера j, откуда выходят дуги, входящие в узел L, то узлу L присваиваем номер j, L = j и увеличиваем на единицу номера всех узлов, начиная с j + 1.

5) Определяем номер j, которому будет присвоен последний номер L. Проверяем, если из узла j не выходит ни одна дуга, то узлу j присваиваем номер L, а всем остальным узлам, начиная с номера j+1, уменьшаем номера на единицу.

6) Добавляем еще один узел  с бинарной операцией  и дугу  с унарной операцией .

7) Удаляем последний узел L, B = B – {L}, с входящей в него дугой .

Структурная вариация сетевого оператора — это вариация, которая меняет множество дуг С сетевого оператора.

Структурная вариация меняет матрицу смежности сетевого оператора. Из элементарных вариаций структурными являются вариации 2 – 5.

Вариации 0, 1 не меняют матрицу смежности сетевого оператора и приводят к структурно подобным сетевым операторам.

Полный сетевой оператор — сетевой оператор, для которого невозможно выполнить вариацию 1 добавления дуги[4].

Собственная вариация сетевого оператора — это вариация, которая не изменяет количество узлов сетевого оператора.

Из элементарный вариаций собственными являются0 — 5.

Вектор сетевого оператора

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

Поэтому существует и другая конструкция представления сетевого оператора — вектор сетевого оператора.

Определение 9. Вектор сетевого оператора — это вектор, размерность которого равна количеству узлов в сетевом операторе. Каждый элемент вектора сетевого оператора является упорядоченным множеством из двухэлементных упорядоченных множеств. Первый элемент двухэлементного множества указывает на номер узла сетевого оператора. Если номер узла совпадает с номером элемента, то второй элемент двухэлементного множества указывает на номер бинарной операции, в остальных случаях – на номер унарной операции[4].

Рассмотрим вектор сетевого оператора

,

где  – множество из двухэлементных множеств

,

L — число узлов в сетевом операторе,  — номер узла сетевого оператора, если , то  — номер бинарной операции, иначе — номер унарной операции, , .

По матрице сетевого оператора всегда можно построить вектор сетевого оператора, и наоборот, по вектору сетевого оператора всегда можно построить ту же матрицу сетевого оператора, по которой построен вектор.

В качестве примера можно рассмотреть матрицу

Вектор сетевого оператора для данной матрицы имеет вид:

Метод интеллектуальной эволюции

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

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

Его основные положения:

1. Инициализация. (Генерация множества возможных решений).

2. Оценка возможных решений по производительности функций.

3. Формирование решений с разными базисами.

4. Создание новых возможных решений: отбор, скрещивание, мутация на решениях с разными базисами.

5. Оценка новых возможных решений, замена плохих решений на лучшие.

6. Проверка условия смены эпох.

7. Проверка критерия остановки.

Рассмотрим шаги алгоритма более подробно.

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

.          (4.1)

Решение задач (1.2) — (1.8) при поиске оптимального математического выражения зависит от множества сетевых операторов Z.

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

.

.

Такой нулевой вектор никак не влияет на базовое решение.

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

,             (4.2)

H — количество возможных решений.

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

          (4.3)

P — число параметров, c — количество бит целой части числа, d —количество бит дробной части.

Множество возможных решений содержит пары

.               (4.4)

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

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

,

где

Все возможные решения сортируем по показателю .

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

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

,               (4.7)

— базис .

Такой подход основан на идее пчелиного алгоритма[39-44], который имитирует поведение колонии пчел при поиске мест, где можно раздобыть как можно больше нектара. Сначала часть пчел определяет количество нектара на случайно выбранных участках,  а затем, чем больше на данном участке предполагается найти нектара, тем больше пчел летит в этом направлении.

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

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

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

Решением задачи станет новое множество Парето, сформированное из решений с нулевым рангом Парето.

Вычислительный эксперимент

Для решения задачи синтеза (1.1) — (1.8) были выбраны следующие базовые решения

,             (5.1)

,          (5.2)

где

,

,

.

На рисунке 11 изображен сетевой оператор выражений (5.1) — (5.2).

Рис. . Сетевой оператор базового решения

Матрица сетевого оператора будет иметь следующий вид

Для нахождения решения были выбраны следующие параметры алгоритма:

- начальное множество возможных решений = 512

- количество поколений = 128

- количество скрещиваний в одном поколении 256

- количество поколений между эпохами = 32

- количество базовых решений = 5

- вероятность мутации = 0.7.

Определенны конечные условия .

Были получены следующие решения:

,

,

где

,

,

,

.

Матрица сетевого оператора полученного решения:

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

Рис. . Движение робота в плоскости X,Y

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

Рис. . Движение робота при новых начальных условиях

Рис. . Симуляция с начальными условиями x(0)=1, y(0)=-1.

Рис. . Симуляция с начальными условиями x(0)=1, y(0)=1.

Рис. . Симуляция с начальными условиями x(0)=-1, y(0)=1.

На рисунке 14 изображена траектория движения робота от точки к точке. Управление движение представлено на рисунках 15 и 16. Как видно из рисунков мобильный робот проходит через все точки, и управление не выходит за рамки ограничений. Рассмотренный метод интеллектуальной эволюции позволил синтезировать нелинейную систему управления для мобильного робота. Полученная система управления позволяет роботу придерживаться любой траектории представленной виде множества точек на плоскости.

Заключение

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

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

Список используемой литературы

1.  Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Massachusetts, London, MA:MIT Press, 1992, 819 p.
2.  O'Neill M., Ryan C. Grammatical Evolution. Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers, 2002.
3.  Zelinka I: Analytic programming by Means of Soma Algorithm// Mendel ’02 In: Proc. 8th International Conference on Soft Computing Mendel’02, Brno, Czech Republic, 2002, 93-101.
4.  Дивеев А.И., Сафронова Е.А. Метод сетевого оператора и его применение в задачах управления. - М.:РУДН,2012.-182с.
5.  Diveev A.I., Sofronova E.A. Application of network operator method for synthesis of optimal structure and parameters of automatic control system// Proceedings of 17-th IFAC World Congress, Seoul, 2008, 05.07.2008 – 12.07.2008. P. 6106 – 6113
6.  Diveev A.I., Sofronova E.A. Numerical method of network operator for multi-objective synthesis of optimal control system// Proceedings of Seventh International Conference on Control and Automation (ICCA’09) Christchurch, New Zealand, December 9-11, 2009. P. 701-708
7.  Дивеев А.И. Синтез адаптивной системы управления методом сетевого оператора// Сб. статей Вопросы теории безопасности и устойчивости систем. М.: ВЦ РАН. 2010. Вып. 12. С. 41-55.
8.  Diveev A.I., Sofronova E.A. The Network Operator Method for Search of the Most Suitable Mathematical Equation. Chapter in the book Bio-Inspired Computational Algorithms and Their Applications/ Edited by Shangce Gao. Intech. Printed 2012. February, Croatia. P. 19-42.
9.  Diveev A.I. A Numerical Method for Network Operator for Synthesis of a Control System with Uncertain Initial Values. Journal of Computer and Systems Sciences International, 2012, Vol. 51, No. 2, P. 228–243.
10.  Diveev A.I. A multiobjective synthesis of optimal control system by the network operator method. In Proceedings of international conference «Optimization and applications» (OPTIMA 2009) (Petrovac, Montenegro, September 21-25, 2009), P. 21-22.
11.  Дивеев А. И., Софронова Е. А. “Основы генетического программирования Учебно-методическое пособие” - М.: Изд-во РУДН, 2006;
12.  T. Weise. Global Optimization Algorithms - Theory and Application: Ph.D Thesis. - University of Kassel, 2008.
13.  Электронный журнал «МОЛОДЕЖНЫЙ НАУЧНО-ТЕХНИЧЕСКИЙ ВЕСТНИК». Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл No. ФС77-51038. ISSN 2307-0609.
14.  Дивеев А.И. Метод сетевого оператора. –  М.: Учреждение Российской академии наук Вычислительный центр им. А.А. Дородницына РАН, 2010.
15.  Панченко Т.В. Генетические алгоритмы. Под ред. Тарасевича Ю.Ю. // г.Астрахань: Издательский дом «Астраханский университет», 2008 г. - 88с.
16.  Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company,2011.
17.  Dubins L.E. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math., 1957, Vol. 79. P. 497-516.
18.  Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S., Zaidi M. The Bees Algorithm - A Novel Tool for Complex Optimisation Problems. Proc. 2nd Virtual International Conference on Intelligent Production Machines and Systems (IPROMS2006), 2006, Cardiff, UK, pp. 454-459.
19.  Reynolds R.G. An Introduction to Cultural Algorithms In Proceedings of the Third Annual Conference on Evolutionary Programming San Diego, California, February 24-26, 1994 pp 131-139.
20.  Евстигнеев Д. В. “Интеллектуальный мобильный робот” - М.: Энергия, 2008;
21.  Лернер А. Я., Розенман Е. А. “Оптимальное управление” - М.: Энергия, 1970;
22.  Ли Э. Б., Маркус Л. “Основы теории оптимального управления” - М.: Наука, 1972;
23.  M. Dorigo, V. Maniezzo. Parallel Genetic Algorithms: Introduction and Overview of Current Research. // Parallel Genetic Algorithms: Theory and Applications. / Ed. by J. Stenders. - Amsterdam, IOS Press, 2012.
24.  Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. Рудинский И.Д. - М.: Горячая линия - Телеком, 2009 г. - 452с.
25.  Дивеев А.И., Софронова Е.А., ИДЕНТИФИКАЦИЯ СИСТЕМЫ ЛОГИЧЕСКОГО ВЫВОДА МЕТОДОМ СЕТЕВОГО ОПЕРАТОРА - Вестник Российского университета дружбы народов. Серия: Инженерные исследования. 2010.№ 4. С. 51-59.
26.  Дивеев А.И., Софронова Е.А. Генетический алгоритм для многокритериального структурно-параметрического синтеза // Вестник Российского университета дружбы народов. Серия «Инженерные исследования». — 2007. — № 4. — С. 126—131.
27.  Дивеев А.И., Софронова Е.А. Метод генетического программирования для автоматического подбора формул в задаче структурного синтеза системы управления // Труды инсти тута Системного анализа РАН. Динамика неоднородных систем / Под ред. Ю.С. Попкова. — М.: ИСА РАН: КомКнига, 2006. — Вып. 10(1). — С. 14—26.
28.  Дивеев А.И., Крылова М.В., Софронова Е.А. Метод генетического программирования для многокритериального структурно-параметрического синтеза систем автоматического управления // Вопросы теории безопасности и устойчивости систем: Сб. статей. — М.: ВЦ РАН, 2008. — Вып. 10. — С. 93—100.
29.  GOLDIN D. A., PAVLOV B. V., CHESNOKOV A. M. Structures of informational control complex of technical systems/IFAC Symposium on Manufacturing, Modeling, Management and Control. MIM 2000. Greece, 2000. Preprints, P. 217-221.
30.  Грибова В.В., Клещев А.С., Шалфеева Е.А. Управление программными средствами в интеллектуальных системах//Изв. РАН. ТиСУ. 2010. № 6. С. 122-137.
31.  Васильев В. И., Ильясов Б. Г. Интеллектуальные системы. Теория и практика. М.: Радиотехника, 2009. 392 с.
32.  Кусимов С. Т., Васильев В. И., Ильясов Б. Г. Управление динамическими системами в условиях неопределенности М.: Наука, 1998. 625 с.
33.  K. J. Astrom and B. Wittenmark, Adaptive Control, Addison-Wesley, 1989, 2d ed. 1994.
34.  Юревич Е. И. Теория автоматического управления. - СПб.: БXB-Петербург, 2007. - 560с.
35.  Растригин Л.А. Современные принципы управления сложными объектами. - М.: Сов. радио, 1980. - 232 с.
36.  Artificial evolution in computer aided design: from the optimization of parameters to the creation of assembly programs G. Squillero COMPUTING, 2011, pp. 103-120
37.  R. G. Reynolds, “An Introduction to Cultural Algorithms, ” in Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scienfific Publishing, pp 131–139, 1994.
38.  Robert G. Reynolds, Bin Peng. Knowledge Learning and Social Swarms in Cultural Systems. Journal of Mathematical Sociology. 29:1-18, 2005
39.  Pham D.T., Ghanbarzadeh A., Koc E, Otri S, Rahim S., Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2009
40.  Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees Algorithm – A Novel Tool for Complex Optimisation Problems Manufacturing Engineering Centre, Cardiff University, Cardiff CF24 3AA, UK.
41.  Карпенко А. П., Селиверстов Е. Ю.Обзор методов роя частиц для задачи глобальной оптимизации (Particle Swarm Optimization) ,2009.
42.  Гришин А. А., Карпенко А. П.Исследование эффективности метода пчелиного роя в задаче глобальной оптимизации, август 2010.
43.  A. S. Mohais, R. Mendes, Ch. Ward, Ch. Posthoff. Neighborhood Re-structuring in Particle Swarm Optimization. // Proceedings of the Australian Conference on Artificial Intelligence. - 2009, pp. 776-785. W. Elshamy, H.
44.  M. Emara, A. Bahgat. Clubs-based Particle Swarm Optimization. //  Swarm Intelligence Symposium. - 2008, pp. 289 – 296
45.  http://www.aiportal.ru
46.  http://elibrary.ru
47.  http://cyberleninka.ru/
48.  http://www.science-education.ru/
49.  http://www.network-operator.com/

Приложение

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

unit Calc3;

interface

const

 infinity=1e8;

 eps=1e-8;

 pokmax=16;

function Ro_1(z:real):real;

function Ro_2(z:real):real;

function Ro_3(z:real):real;

function Ro_4(z:real):real;

function Ro_5(z:real):real;

function Ro_6(z:real):real;

function Ro_7(z:real):real;

function Ro_8(z:real):real;

function Ro_9(z:real):real;

function Ro_10(z:real):real;

function Ro_11(z:real):real;

function Ro_12(z:real):real;

function Ro_13(z:real):real;

function Ro_14(z:real):real;

function Ro_15(z:real):real;

function Ro_16(z:real):real;

function Ro_17(z:real):real;

function Ro_18(z:real):real;

function Ro_19(z:real):real;

function Ro_20(z:real):real;

PAGE   \* MERGEFORMAT53