Содержание к диссертации
ВВЕДЕНИЕ 6
1. ПРОБЛЕМЫ АНАЛИЗА И СИНТЕЗА В СИСТЕМАХ
УПРАВЛЕНИЯ С СИММЕТРИЕЙ 14
Понятие симметрии 14
Примеры систем с симметрией 17
Концепция информационно - управляющих систем 23
1.3.1. Сравнительный анализ моделей 24
Модели вход-выход 25
Модели в пространстве состояний 26
Проблемы управления и оптимизации в ИУС 27
Принцип эволюционных вычислений 31
Разновидности эволюционных вычислений; 33
л 1.6.1. Генетические алгоритмы 33
Генетическое программирование 37
Эволюционное программирование 38
Эволюционные стратегии» 39
1.7. Выводы к разделу Г. Основные задачи исследования 41
2. МЕТОД СТРУКТУРНО-ИНВАРИАНТНОГО
АНАЛИЗА. 43
2.1. Определение симметрии в моделях систем управления * 43
2.1.1. Применение перестановок 50
2.2. Классификация симметрии моделей систем управления 51
2.2.1. Визуальная симметрия 51
2.2.2І Скрытая симметрия> 54
2.2.3. Алфавитная симметрия 54
.*, 2.2.4. Динамическая симметрия. 55
2.2:5: Зеркальная симметрия 56
2.2:6. Поворотная симметрия 57
2.2.7. Зеркально - поворотная симметрия 57
2:3. Декомпозиция систем с симметрией 58?
2.4. Построение декомпозирующих преобразований 59
2.5: Особенности декомпозиции систем с поворотной
симметрией 64
Декомпозиция и преобразования Фурье 65
Пример применения метода 69
2.7.1. Анализ симметрии и декомпозиция модели 72*
2.8. Выводы к разделу 2 77
3 ПРИКЛАДНЫЕ ЗАДАЧИ СТРУКТУРНО - ИНВАРИАНТНОГО
АНАЛИЗА 78
# 3.1. Схема применения структурно - инвариантного анализа 78
3.2. Симметрия в линейной задаче оптимального управления с квадратичным
критерием качества 79
* 3.3. Декомпозиция линейной задачи оптимального управления с
квадратичным критерием качества 86
Специальные типы движений в симметричных системах 90
Синхронизация систем с симметрией 94
Системы, близкие к симметричным 97
Симметрирование динамических систем 100
Эволюционный подход к многокритериальной оптимизации в системах координатно - параметрического управления 102
Оптимизация по Парето 103
Применение эволюционных вычислений 104
Особенности применения метода в системах координатно-параметрического управления 106
Выводы к разделу 3 107
* 4. МОДЕЛИРОВАНИЕ И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ 109
4.1. Параметры и работа генетического алгоритма 109
Кодирование элементов популяции. 110
Функция пригодности 111
4.1.3 Отбор 112
4.2. Генетические операторы 114
Мутация 114
Рекомбинация 115
4.3. Некоторые свойства генетических алгоритмов 117
Шаблоны и строящие блоки 117
Неявный параллелизм 121
Проблема настройки генетических алгоритмов 124
Моделирование генетических алгоритмов 125
(% 4.5.1. Применение функций Уолша 126
4.5.2. Модель Изинга 129
Моделирование и проблемы управления генетическим алгоритмом 132
Построение алгебраической модели генетического алгоритма 136
Пространство состояний популяции 137
Оператор отбора 138
Оператор мутации 139
Оператор рекомбинации 140
Схема замещения. 141
Схема замещения для бинарного алфавита. 146
Выводы к разделу 4 148
5.СТРУКТУРНО - ИНВАРИАНТНЫЙ АНАЛИЗ ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ 150
5.1. Симметрия в генетических алгоритмах 150
5.1.1. Инвариантные шаблоны ....157
Особенности структурно - инвариантного анализа генетических алгоритмов 158
Групповые структуры бинарных хромосом 160
Задачи оптимизации с небинарным кодированием хромосом. 164
5:5. Групповые структуры в пространстве поиска ив пространстве состояний
Обобщенные шаблоны 170
Групповые свойства генетических операторов 173
Инвариантные подмножества и ниши. 174
Инвариантная рекомбинация 175
Групповые свойства схемы замещения 178
5.8. Декомпозиция в генетическом алгоритме 181
Преобразование Фурье схемы замещения 182
Преобразование Фурье при бинарном алфавите кодирования. 186
Алгоритм формирования ниш 190
Выводы к разделу 5 191
6. СТРУКТУРНО - ИНВАРИАНТНЫЙ АНАЛИЗ И СИММЕТРИРОВАНИЕ ЭЛЕКТРОТЕРМИЧЕСКИХ УСТАНОВОК ...193
Электротермические установки и их применение 193
Управление электротермическими установками. 195
Управление электрическим режимом ЭТУ 198
6.4; Явление "дикой" и "мертвой" фаз. 200
Проблема симметрирования электрического режима ЭТУ 202
Математическое моделирование электротермических установок 202
Координатно-параметрическая: модель ЭТУ 205
Симметрии в модели ЭТУ 208
Исследование особенностей режимов работы ЭТУ 213
Исследование критических режимов работы ЭТУ. 218
Исследование прекосов режима работы ЭТУ. 219
Исследование явления "дикой" и "мертвой" фаз. 221
Декомпозиционный способ симметрирования ЭТУ 223
Симметрирующая система регулирования фазных токов 226
Выбор оптимальных настроек симметрирующего регулятора. 230
6.13.1. Применение генетического алгоритма 232
6.14. Выводы к разделу 6 238
7 СТРУКТУРНО - ИНВАРИАНТНЫЙ АНАЛИЗ В ЗАДАЧАХ
ИЗВЛЕЧЕНИЯ ЗНАНИЙ НА РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ 240
7.1. Проблема и методы извлечения знаний в больших информационных
системах 240
7.1.1. Понятие знания 241-
Классификация методов извлечения знаний 244
Реляционное решение задач построения ассоциативных правил и
классификаций. 245
7.3.1. Ассоциации данных, ассоциативные правила и классификации 246
5"
(*/ 7.4. Прямые и обратные задачи на базах данных 250
Построение ассоциаций путем генерации управляемых запросов 252
Эволюционный подход к решению задачи 254
Построение генетического алгоритма управления запросами 255
Генетическое программирование в задаче поиска ассоциативных связей 257
Хромосомы SQL 262
Функция пригодности 265
Операция рекомбинации 268
Операция мутации 269
Применение вложенных запросов 270
Особенности реализации генетических алгоритмов средствами SQL -запросов 272
Особенности кодирования. 273
Смысловые ниши 274
Программно - алгоритмический комплекс "Система эволюционных вычислений.." 277
Эксперименты с системой 279
Задача извлечения знаний 280
Динамика эволюционного процесса 281
Рекомендации по внедрению системы эволюционных вычислений в банковские информационные системы 286
Выводы к разделу 7 288
ЛИТЕРАТУРА / 290
ПРИЛОЖЕНИЯ
I. УСТРОЙСТВО И МОДЕЛИРОВАНИЕ ЭЛЕКТРОТЕРМИЧЕСКИХ
УСТАНОВОК 310
1.1. Основные элементы конструкций электротермической установки 310
11) 1.2. Короткие сети электротермических установок. 313
Построение координатно-параметрической модели ЭТУ 316
Модель привода перемещения электродов 324
И. ПРОГРАММНЫЕ СИСТЕМЫ ИЗВЛЕЧЕНИЯ ЗНАНИЙ 326
Ш. ПРОГРАММНО - АЛГОРИТМИЧЕСКИЙ КОМПЛЕКС "СИСТЕМА
ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЙ ". 333
III. 1. Модуль агрегирования базы данных: 333
Ш.2. Модуль генетического алгоритма 334
Ш.З. Модуль оценки индивидуумов 334
Ш.4. Модуль выделения ассоциативных связей 335
IV. ИССЛЕДОВАНИЕ РАБОТЫ АЛГОРИТМОВ СЭВ ПРИ РЕШЕНИИ ЗАДАЧ
РАЗЛИЧНЫХ КЛАССОВ 338
IV. 1. Исследование влияния параметров алгоритма на его производительность 340
IV.2. Исследование влияния функции пригодности 341
IV.3. Исследование влияния методов отбора 344
V. ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ
РАБОТЫ: 350
d,
Введение к работе
Развитие вычислительной техники и информационных технологий значительно расширяет возможности управления объектами самой разной природы. Это ведет к появлению систем управления нового типа, структура которых включает как динамические, так и информационные подсистемы. Подобные системы управления относятся к информационно - управляющими системами. В настоящее время концепция информационно - управляющих систем (ИУС) заменяет концепции САУ и АСУ, объединив их в,единую систему. Такое объединение требует создания единой методологической основы исследования информационно - управляющих систем.
С точки зрения традиционной классификации систем информационно -управляющую систему, как правило, нельзя отнести к одному определенному типу, потому что в ее структуру могут входить линейные, нелинейные, непрерывные и дискретные подсистемы, а также программное обеспечение. Это приводит к проблеме моделирования в «ИУС. Сложность решения данной проблемы обусловлена тем, что в информационно -управляющих системах существуют не только процессы, моделируемые функциями действительного переменного, но и данные, для моделирования которых применяют структуры данных. При этом наиболее распространенной структурой данных является реляционная структура, реализуемая в соответствующих базах данных.
Вследствие этого современные модели информационно - управляющих систем объединяют в себе как традиционные модели в виде систем дифференциальных или разностных уравнений, так и; более общие модели, например, в виде отношений и операций над ними.
Такая ситуация привела к необходимости разработки новых подходов к исследованию подобных систем.
Очевидно, невозможно построить универсальные методы решения задач анализа и синтеза в ИУС, одинаково пригодные как для динамических,
7 так и для информационных подсистем. Но поскольку эти подсистемы
составляют одну систему и взаимодействуют, существуют общие принципы
их исследования.
Одним из таких принципов является принцип симметрии. Симметрия является фундаментальным свойством, присущим объектам и процессам окружающего мира, и отражаемым в их моделях. Симметрия проявляется как свойство инвариантности модели исследуемого объекта или системы относительно определенных преобразований, выполняемых в модели. Инвариантом может быть структура системы, структура данных или числовая величина, например, значение критерия качества управления.
Поэтому разработка методов исследования и применения свойства симметрии в информационно - управляющих системах представляет собой актуальную проблему, имеющую теоретическое и прикладное значение.
Методологической основой анализа и применения симметрии является теория групп. Несмотря на значительный арсенал теоретико - групповых методов, они не являются рабочим инструментом в задачах исследования ИУС, что объясняется высокой степенью абстракции методов теории групп.
В связи с этим актуальными становятся прикладные исследования, призванные построить методы и алгоритмы применения теоретико -групповых методов к решению прикладных задач в информационно -управляющих системах.
Целью настоящей работы является разработка элементов теории и алгоритмов структурно - инвариантного анализа информационно -управляющих систем с симметрией.
Достижение данной цели позволяет решить важную научную проблему исследования информационно - управляющих систем с единых позиций, включающих анализ и применение симметрии для декомпозиции систем и решения некоторых задач оптимизации.
8 Проблематика данной диссертации и ее результаты составляют метод
структурно - инвариантного анализа, включающий в себя комплекс
аналитических и алгоритмических решений, выносимых на защиту:
единый подход к исследованию свойства симметрии и применению его в задачах анализа и синтеза в динамических и информационных подсистемах информационно - управляющих систем;
единый подход к оптимизации информационно - управляющих систем на основе принципа эволюционных вычислений;
формализация проблемы анализа симметрии в информационно -управляющих системах методами теории групп;
формализация задач синхронизации и симметрирования в многосвязных динамических системах с симметрией;
формализация задач извлечения знаний в виде ассоциативных правил и классификаций на реляционных базах данных;
декомпозиционный метод решения задач синхронизации и симметрирования в многосвязных динамических системах;
метод построения ассоциативных правил и классификаций в реляционных базах данных на основе эволюционных вычислений;
Основные результаты работы получены с применением методов теории конечных групп и теории представлений конечных групп, методов эволюционных вычислений, теории преобразований Фурье, элементов теории реляционных баз данных. Для получения некоторых результатов применялось математическое моделирование и вычислительный эксперимент.
Научная новизна работы состоит в разработке элементов теории анализа и синтеза информационно - управляющих систем с симметрией на основе декомпозиции и принципа эволюционных вычислений.
В работе получены следующие новые научные результаты.
1. Выполнен; анализ проблемы и формальная постановка задач
исследования симметрии; в информационно - управляющих системах методами теории групп.
Предложена классификация; симметрии в моделях информационно -управляющих систем с выделением понятий визуальной, скрытой, динамической, алфавитной, симметрии и их теоретико-групповая интерпретация.
Методом приведения линейных представлений конечных групп симметрии решена задача декомпозиции многомерных моделей динамических систем с симметрией и построены соответствующие; декомпозирующие преобразования.
Исследованы и формализованы задачи синхронизации! и симметрирования в многосвязных динамических системах на основе принципа симметрии. Предложен эволюционный метод решения проблемы синтеза симметрирующих регуляторов динамических систем как задачи многокритериальной оптимизации.
5; Методом математического моделирования исследованы критические режимы работы трехфазной электротермической; установки и показана возможность возникновения явлений "дикой" и "мертвой" фаз при і штатном способе управления установкой.
6: Построен декомпозиционный метод решения задач синхронизации и симметрирования в многосвязных динамических системах.
Построена модель генетического алгоритма в пространстве состояний популяции, использующая понятие схемы замещения и единое представление генетических операторов мутации и рекомбинации; при помощи обобщенных масок и позволяющая применить к исследованию и настройке алгоритмов структурно - инвариантный анализ.
Получен метод построения ниш генетического алгоритма на основе структурно - инвариантного анализа модели алгоритма в пространстве состояний.
9. Формализована задача извлечения знаний в виде ассоциативных
правил и классификаций на реляционных базах данных.
10. Предложен эволюционный метод построения ассоциативных правил и
классификаций на реляционных базах данных.
Практическая ценность результатов работы, заключается в универсальности метода структурно- инвариантного анализа, применение которого возможно как в динамических, так и в информационных подсистемах информационно-управляющих систем.
Метод применим не только к системам с симметрией, но и к системам, близким к симметричным, обладающим достаточной грубостью.
Процедуры структурной декомпозиции многомерных моделей систем с симметрией не требуют решения проблемы собственных значений. Поэтому их применение возможно в моделях, имеющих векторно-матричную форму с нечисловыми матрицами.
Формализация и принцип решения задач симметрирования многосвязных динамических систем применимы к системам исследованного класса любой размерности. Поэтому полученные в работе результаты решения задачи симметрирования трехфазной электротермической установки применимы к подобным установкам с любым числом фаз. Данный подход применим также к любым системам, использующим трех- и многофазные системы электропитания, в которых управление осуществляется путем изменения фазных сопротивлений.
Декомпозиционный алгоритм симметрирования трехфазной
электротермической установки исключает возникновение явления "дикой" и "мертвой" фаз, что значительно повышает качество управления электрическим режимом установки.
Принцип симметрии и принцип эволюционных вычислений являются единой методологической основой решения исследованных в работе проблем анализа и синтеза в информационно-управляющих системах.
Преимуществом системы эволюционных вычислений, реализующей алгоритмы, построенные в работе, является то, что она не требует создания новых форматов данных и работает на реляционных базах данных, составляющих большинство эксплуатируемых на практике баз данных.
Исследования по теме диссертации выполнялись в рамках выполнения хоздоговорных научно - исследовательских работ по темам, связанным с автоматизацией электротермических печей различных типов. Принципы построения симметрирующих регуляторов фазных токов защищены двумя авторскими свидетельствами на изобретения и внедрены в проект реконструкции печей типа РКЗ-48Ф.
Обобщение практических результатов применения принципа симметрии позволило сформулировать методологию структурно-инвариантного анализа и применить ее не только в технических, но и в информационных системах к решению задач, возникающих при создании корпоративных систем поддержки принятия решений.
Полученные в работе алгоритмические решения реализованы в программно - алгоритмическом комплексе «Система эволюционных вычислений» (СЭВ). Данный комплекс предназначен для применения в корпоративных информационных системах поддержки принятия решений в банковско - финансовой сфере и представляет собой открытую инструментальную среду, настраиваемую на конкретные задачи. Комплекс внедрен в опытную эксплуатацию в Главном управлении Центрального банка РФ по Тульской области.
Некоторые материалы и результаты исследований данной работы внедрены в учебный процесс высшего образования. Метод эволюционных вычислений включен в курс лекций по дисциплине «Информационное обеспечение систем управления» специальности 071900 «Информационные системы и технологии». Специальные технологии программирования, разработанные и примененные в данной работе, освещены в учебном пособии по программированию в системе Mathematica.
12
Щ Работа состоит из введения, семи разделов, заключения
В первом разделе выполнен анализ состояния исследований по проблеме диссертации: рассматривается концепция информационно -управляющих систем, принцип симметрии, принцип эволюционных вычислений, вводятся необходимые понятия и определения и на содержательном уровне формулируются задачи исследования.
Во втором разделе излагается формальный математический аппарат, составляющий основу метода структурно — инвариантного анализа информационно - управляющих систем с симметрией.
В третьем разделе рассмотрены формализации прикладных задач
структурно - инвариантного анализа и способы их решения с применением
декомпозиции на основе свойства симметрии. Исследуется применение
декомпозиции в линейной задаче оптимального управления с квадратичным
критерием качества с симметрией. Рассматривается задача синхронизации
движений динамических систем. Задача синхронизации может быть
сформулирована как задача оптимального управления, функционал качества
в которой имеет дополнительные ограничения. Это позволяет
сформулировать задачи синхронизации двух типов: терминальную задачу
синхронизации и динамическую задачу синхронизации.
fp Четвертый раздел посвящен анализу методов эволюционных
вычислений и построению модели генетического алгоритма как основного эволюционного алгоритма, применяемого в данных методах.
Модель генетического алгоритма строится в рамках алгебраического подхода с целью применения к исследованию и настройке алгоритмов структурно - инвариантный анализа.
В пятом разделе структурно - инвариантный анализ применяется к исследованию генетических алгоритмов.
Согласно основной концепции структурно - инвариантного анализа
исследуются групповые свойства модели генетического алгоритма и
^ симметрии, допускаемые моделью. Для этих целей применяется модель
13 генетического алгоритма, разработанная в предыдущем разделе. Строится
декомпозиция модели генетического алгоритма методом, описанным в
