Матренин Павел Викторович. Разработка адаптивных алгоритмов роевого интеллекта в проектировании и управлении техническими системами

Краткое описание

Матренин Павел Викторович. Разработка адаптивных алгоритмов роевого интеллекта в проектировании и управлении техническими системами: автореферат дис. ... кандидата Технических наук: 05.13.01 / Матренин Павел Викторович;[Место защиты: ФГАОУ ВО «Национальный исследовательский Томский государственный университет»], 2018

Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Новосибирский государственный технический университет»
На правах рукописи

Матренин Павел Викторович
РАЗРАБОТКА АДАПТИВНЫХ АЛГОРИТМОВ РОЕВОГО ИНТЕЛЛЕКТА
В ПРОЕКТИРОВАНИИ И УПРАВЛЕНИИ ТЕХНИЧЕСКИМИ СИСТЕМАМИ
05.13.01 - Системный анализ, управление и обработка информации
(в отраслях информатики, вычислительной техники и автоматизации)
Диссертация
на соискание ученой степени
кандидата технических наук
Научный руководитель
доктор технических наук, профессор
Манусов Вадим Зиновьевич
Новосибирск - 2018
Оглавление
ВВЕДЕНИЕ 6
1. Обзор и анализ методов решения оптимизационных задач 15
1.1. История развития теории оптимизации 15
1.2. Обзор методов оптимизации 23
1.2.1. Детерминированные методы 23
1.2.2. Стохастические методы 31
1.3. Алгоритмы роевого интеллекта 38
1.3.1. История развития роевого интеллекта 38
1.3.2. Области применения алгоритмов роевого интеллекта 39
1.3.3. Ограничения на применение роевых алгоритмов 41
1.4. Выводы по разделу 1 44
2. Адаптивные алгоритмы роевого интеллекта 45
2.1. Системное представление алгоритмов роевого интеллекта 45
2.1.1. Введенные обозначения 45
2.1.2. Роевой алгоритм как система 48
2.1.3. Обобщенная схема работы роевого алгоритма 51
2.1.4. Взаимодействие роевого алгоритма и решаемой задачи 53
2.2. Описания роевых алгоритмов по разработанной схеме 54
2.2.1. Алгоритм роя частиц 54
2.2.2. Алгоритм колонии муравьев 57
2.2.3. Алгоритм роя светлячков 60
2.2.4. Алгоритм косяка рыб 62
2.2.5. Алгоритм роя пчел 65
2.2.6. Выделение отличительных черт роевых алгоритмов 67
2.3. Адаптация алгоритмов под условия задач 69
2.3.1. Интерфейс между алгоритмами и оптимизационными задачами 69
2.3.2. Мета-оптимизация 71
2.3.3. Схема предложенного алгоритма адаптации 73
2.4. Повышение эффективности применения роевых алгоритмов 76
2.4.1. Выбор используемых структур данных 76
2.4.2. Учет постоянной составляющей критерия оптимальности 77
2.4.3. Взаимодействие с пользователем 79
2.4.4. Использование параллельных вычислений 80
2.5. Выводы по разделу 2 82
3. Адаптивные алгоритмы роевого интеллекта в задачах оптимизации в
электроэнергетике 84
3.1. Оптимизация размещения источников реактивной мощности 85
3.1.1. Постановка задачи оптимизации источников реактивной мощности. 86
3.1.2. Применение адаптивных роевых алгоритмов для оптимизации
источников реактивной мощности 87
3.1.3. Вычислительные эксперименты в задаче оптимизации источников
реактивной мощности 88
3.1.5. Оптимизация размещения установок компенсации реактивной
мощности в сетях 0,4 кВ электроснабжения АО «УЭХК» 90
3.1.6. Оперативное управление источниками реактивной мощности 92
3.1.7. Двухкритериальная задача оптимальной компенсации реактивной
мощности 97
3.2. Оптимизация коэффициентов трансформации 101
3.2.1. Постановка задачи оптимизации коэффициентов трансформации ... 102
3.2.2. Применение адаптивных роевых алгоритмов для оптимизации
коэффициентов трансформации 104
3.2.3. Вычислительные эксперименты в задаче оптимизации коэффициентов
трансформации 104
3.2.4. Анализ результатов в задаче оптимизации коэффициентов
трансформации 106
3.3. Оптимизация модели прогнозирования электропотребления 108
3.4. Выводы по разделу 3 110
4. Исследование адаптивных алгоритмов роевого интеллекта в задаче
календарного планирования 113
4.1. Содержательное описание задачи календарного планирования 113
4.2. Математическая модель оптимизационной задачи job-shop 115
4.3. Обзор используемых методов оптимизации 117
4.3.1. Детерминированные методы в задачах календарного планирования 117
4.3.2. Стохастические методы в задачах календарного планирования 119
4.4. Применение роевых алгоритмов для решения задачи календарного
планирования 120
4.4.1. Алгоритмы с непрерывным пространством поиска 120
4.4.2. Алгоритмы с дискретным пространством поиска 122
4.5. Вычислительные эксперименты на тестовых задачах 124
4.5.1. Описание набора тестовых задач 124
4.5.2. Влияние эвристических коэффициентов роевых алгоритмов 125
4.5.3. Сравнение результатов использованных методов 129
4.5.4 Сравнение с результатами других авторов 131
4.5.5. Устойчивость эволюционной адаптации 133
4.6. Выводы по разделу 4 136
5. Разработанное программное обеспечение 138
5.1. Выбор инструментальных средств разработки 138
5.2. Применение разработанных алгоритмов роевого интеллекта в
программных комплексах 141
5.2.1. Программный интерфейс взаимодействия алгоритмов роевого
интеллекта и задачи оптимизации 141
5.2.2. Взаимодействие алгоритмов роевого интеллекта и «Simulink» 144
5.2.3. Взаимодействие алгоритмов роевого интеллекта и «RastrWin3» 146
5.3. Система календарного планирования 149
5.3.1. Приложение для решения задач календарного планирования 149
5.3.2. Применение для составления учебных расписаний 152
5.4. Визуализация популяционных алгоритмов 156
5.5. Выводы по разделу 5 160
ЗАКЛЮЧЕНИЕ 162
СПИСОК СОКРАЩЕНИЙ 167
СПИСОК ЛИТЕРАТУРЫ 168
Приложение А. Акты о внедрении результатов работы 186
Приложение Б. Свидетельства на программы для ЭВМ 189
Приложение В. Программный интерфейс библиотеки роевых алгоритмов .... 193
Приложение Г. Размерности задач календарного планирования Operational
Research Library 197

Список литературы

ЗАКЛЮЧЕНИЕ
В настоящей диссертации разработаны математическая модель, обобщающая алгоритмы роевого интеллекта, и унифицированная схема применения роевых алгоритмов для оптимизации технических систем. Проведено исследование адаптационных свойств роевых алгоритмов и модифицированы известные методы мета-оптимизации. На основании выполненных исследований можно сделать следующие выводы и обобщения.
1. Проведен анализ оптимизационных задач проектирования и управления
техническими системами, а также методов их решения. Выявлены следующие особенности рассматриваемых задач оптимизации: сложная топология
пространства поиска решений, многокритериальность, многофакторность, наличие как дискретных, так и непрерывных управляемых переменных и ограничений, динамические изменения условий задач, высокая вычислительная сложность. Показано, что необходимо применять методы оптимизации, имеющие свойства гибкости, самоорганизации, позволяющие за приемлемое время получать решения, близкие к оптимальным. К ним относятся алгоритмы роевого интеллекта, эффективность которых основана на способах решения задач, созданных природой за миллиарды лет и при этом имеющих математические доказательства эффективности, основанные на теории конечных цепей Маркова.
2. Раскрыты причины трудностей в применении алгоритмов роевого интеллекта для решения оптимизационных задач на практике: отсутствие единой классификации и терминологии, отсутствие единого подхода к описанию и применению алгоритмов, необходимость настройки алгоритмов и методологические сложности в соединении алгоритмов и решаемых задач. Указанные трудности, обобщенно названные трудностями адаптации, снижают эффективность применения алгоритмов роевого интеллекта, что в свою очередь, не позволяет в полной мере улучшать показатели технических систем при решении оптимизационных задач.
3. Разработана новая модель описания, реализации и применения алгоритмов роевого интеллекта на основе проведенного системного анализа роевых алгоритмов. Введены правила классификации и единая терминология, упрощающие анализ и повышающие эффективность создания и применения роевых алгоритмов. Дано системное определение алгоритмам роевого интеллекта, описаны общие для них принципы и схема работы, что позволило выделить общие и уникальные для каждого алгоритма приемы, обеспечивающие их большую или меньшую эффективность в различных классах оптимизационных задач. Предложенная модель алгоритмов роевого интеллекта обеспечивает стандартизацию, повышение гибкости и переносимости создаваемого программного обеспечения, повышение скорости разработки.
4. Проведена модернизация существующих методов мета-оптимизации алгоритмов роевого интеллекта. Показано, что эффективная адаптация алгоритмов роевого интеллекта для решения практических задач имеет два основных аспекта. Первым является устранение тесных зависимостей между реализацией алгоритмов и моделями оптимизируемых систем. Для этого введен интерфейс между алгоритмами и задачами оптимизации, позволяющий выполнить их соединение без необходимости вносить изменения в математические модели алгоритмов и в модели оптимизируемых систем. Необходимые особенности, такие как масштабирование значений управляемых переменных, учет ограничений и дискретность, учитываются в интерфейсе. Задача оптимизации становится для алгоритма черным ящиком, как и алгоритм для задачи. Вторым аспектом адаптации является настройка значений эвристических коэффициентов роевых алгоритмов под определенный класс задач. Показано, что эффективным методом такой настройки является мета-оптимизация на базе генетического алгоритма по аналогии с эволюционной адаптацией в природе. Проведенные вычислительные эксперименты подтвердили, что предложенный метод адаптации обеспечивает повышение эффективности не только для задач, для которых выполнена адаптация, но и для других задач данного подкласса.
5. Раскрыты возможности применения адаптивных алгоритмов роевого интеллекта для решения задач оптимизации в проектировании и управлении электроэнергетическими системами. Решена многокритериальная гибридная задача определения положений и мощностей компенсирующих установок для компенсации реактивной мощности. Задача имеет свойства как дискретной, так и непрерывной оптимизации, поскольку мощности установок непрерывны, но места их допустимого размещения дискретны. Данная задача рассмотрена как одно- и двухкритериальная, как проектная и как задача оперативного управления. Показано, что при решении задачи как многокритериальной, лицо, принимающее решения, получает больше информации о вариантах улучшения системы, что особенно важно, если среди критериев часть влияет на краткосрочные показатели, часть на долгосрочные и необходимо соблюдать баланс тактических и стратегических целей. Эксперименты проводились для различных электроэнергетических систем: подсистема электроснабжения Ангарского
электролизного химического комбината, подсистема электроснабжения ОА «Уральский электрохимический комбинат», фрагмента энергетической системы Таджикистана. Применение адаптивных алгоритмов роевого интеллекта позволяет снизить потери активной мощности на 5-20 %. Проведено сравнение адаптивных алгоритмов роевого интеллекта с роевыми алгоритмами без разработанной адаптации и другими оптимизационными методами (генетический алгоритм, градиентные методы). Эффективность решений адаптивных алгоритмов выше на 2-9 %, чем роевых алгоритмов без адаптации. Показано, что эффективность решений адаптивных алгоритмов выше на 2-9 %, чем роевых алгоритмов без адаптации. При этом существующие программные аналоги, применяемые для оптимизации электроэнергетических систем, не позволяют решать многокритериальные задачи или задавать все необходимые ограничения. Кроме того, были на практике подтверждены выводы теоретического анализа о преимуществе алгоритма роя пчел в задачах динамической оптимизации, поскольку частицы роя пчел при правильно настроенных параметрах алгоритма всегда рассредоточены по нескольким альтернативным окрестностям в
пространстве поиска решений. Адаптивные алгоритмы роевого интеллекта использованы в решении задачи выбора коэффициентов трансформации в системах электроснабжения 110-220 кВ. Проведенные вычислительные эксперименты показали, что при оптимизации с использованием адаптивных алгоритмов роевого интеллекта в рассмотренной системе можно добиться снижения потерь активной мощности с 48,01 МВт до 45,83 МВт (4,5 %). Выявлено, что рассматриваемый класс задач обладает сложной топологией, при которой оказываются малоэффективными применяемые в данной задаче методы, основанные на направленном переборе, эвристических правилах или нечеткой логике. Показано, что эффект от применения адаптивного алгоритма роя частиц с настраиваемым ограничением скорости на 28,9 % выше, чем эффект от указанных методов для рассмотренной
электроэнергетической системы.
6. Работоспособность и эффективность разработанных адаптивных алгоритмов роевого интеллекта протестирована на задачах оптимизации из Operational Research Library. Разработана схема для применения роевых алгоритмов, выполняющих поиск как в непрерывном пространстве поиска решений, так и в дискретном. Установлено, что алгоритмы роевого интеллекта могут быть успешно применены для решения задач календарного планирования. Вычислительными экспериментами показано, что предложенная эволюционная адаптация повышает эффективность роевых алгоритмов на величину до 12 %. По 85 % задач получены результаты, совпадающие с наилучшими результатами в опубликованных работах других авторов, по отдельным задачам отклонение составило не более 2,5 %. Подтверждена устойчивость адаптации, поскольку повышение эффективности адаптивных алгоритмов роевого интеллекта происходит не только для отдельных задач, под которые выполнена адаптация, но и для других задач того же класса.
7. Разработан унифицированный интерфейс между программными реализациями алгоритмов роевого интеллекта и моделями оптимизируемых объектов для различных языков программирования и программных комплексов, используемых для моделирования электроэнергетических систем. Разработанные программные библиотеки позволяют прикладным специалистам легко применять алгоритмы роевого интеллекта в решении оптимизационных задач. Для этого не требуется внесение изменений в модели оптимизируемых систем, созданных в специализированных широко используемых средах моделирования, таких как «Matlab», «Simulink», «RastrWin», а также в программных комплексах, написанных на языках программирования высокого уровня. Разработаны и внедрены программные приложения для демонстрации применения разработанных алгоритмов. Создан программный комплекс для решения задач календарного планирования, позволяющий работать с исходными данными задач календарного планирования, решать их различными методами и выводить результаты решений в различных форматах. Для анализа работы стохастических алгоритмов оптимизации разработано и внедрено в учебный процесс интерактивное приложение, выполняющее визуализацию их работы. Приложение используется в рамках учебных дисциплин, посвященных методам оптимизации и системам искусственного интеллекта.
Перспективным направлением дальнейших исследований является совершенствование разработанных методов и алгоритмов (повышение точности получаемых решений и увеличение быстродействия) для применения в оптимизации сложных многокритериальных технических систем с учетом их стохастических и динамических свойств, а также в задачах управления в реальном времени. Использование разрабатываемых адаптивных алгоритмов роевого интеллекта в указанных задачах является перспективным средством повышения качества функционирования технических систем и их экономической эффективности. На данный момент практическими направлениями развития работы являются решение задач оптимизации в управлении потоками электроэнергии в системах распределенной генерации и в структурно¬параметрическом проектировании трансформаторов с высокотемпературной сверхпроводящей обмоткой.