Разработка методов группового управления на основе эволюционных алгоритмов многокритериальной оптимизации

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

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

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

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

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

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

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

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

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

Поставленная цель обусловила необходимость решения следующих основных задач:

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

• анализ моделей, вычислительной точности и эффективности генетических алгоритмов многокритериальной оптимизации на основе мультиагентных моделей и стратегии межагентного взаимодействия (кооперации и координации между динамическими объектами);

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

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

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

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

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

Технология распределенной интеллектуальной системы в настоящее время не применена в системах управления системами энергетики. Однако у этого подхода есть большой потенциал к управлению крупномасштабным и среднего масштаба возобновляемых источников энергии, распределенным источникам энергии (DER) и гибкой, гибридной интеграции в будущих автоматических системах. По крайней мере, два главных европейских проекта R&D (Микро-Сеть и CRISP) исследовали такой потенциал.

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

Отсутствие общих подходов к решению задач, возникающих при групповом управлении роботами в заранее неизвестной и динамически изменяющейся среде, существенно ограничивает их реальное применение. Далее подчеркивается, что традиционный подход в решении задач многоцелевой оптимизации коллективного поведения роботов является оптимизация по доминирующему критерию, в то время как все остальные критерии кроме выбранного главным рассматриваются в качестве ограничения [4,8] или с помощью коэффициентов [2,3]. Однако такой подход к решению подобных задач значительно снижает эффективность принимаемых решений. Эволюционные алгоритмы (ЭА) представляют собой алгоритмы оптимизации (поиска наилучшего решения в предметной области), основанные на некоторых формализованных принципах естественного эволюционного процесса. Основное их преимущество заключается в возможности решения многоэкстремальных задач с большой размерностью за счет сочетания элементов случайности и детерминированности точно так, как это происходит в природной среде.

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

В третьей главе анализируется применение параллельных генетических алгоритмов в задачах многокритериальной оптимизации коллективного поведения динамических объектов. Недостаток известных алгоритмов коллективного распределения целей в группах динамических объектов заключается в том, что в отличие от стратегии централизованного управления децентрализованная стратегия не гарантирует оптимального решения групповой задачи, поскольку решение принимается каждым членом группы самостоятельно. Для того, чтобы гарантировать нахождения оптимального решения групповой задачи децентрализованным образом, группа динамических объектов должна принимать решения не самостоятельно, а распределяя групповую задачу между всеми членами группы. Для этого вводиться параллельные генетические алгоритмы многокритериальной оптимизации пГАМКО.

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

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

4.4. Выводы.

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

На основе статистического анализа показатели качества различных методов миграции и замен параллельных эволюционных алгоритмов многокритериальной оптимизации, можно сказать, что все три похода параллелизма и еще серийный метод имеют очень похожие результаты по сравнению с истинным Парето-фронтом. Параллельные методы имеют на много меньше вычислительные затраты по сравнению с серийным методом и имеют линейный характер относительно N — числа объектов управления (см. Рис 4.17) особенно динамический метод поскольку, время для миграции уменьшается из поколения в поколение. Далее можно подчеркивать, что у каждого метода есть свои преимущества (см. таб. 4.8), в частности динамический метод имеет самый низкий индекс распространения и размер доминирующего пространства на 2% меньше. Это происходит из-за невысокого разнообразия особей и высокого давления отбора, особенно в начале эволюции. Пока случайный метод имеет высокий индекс распространения и размер доминирующего пространства на 7% больше — этот факт демонстрирует низкое давления отбора случайного метода и высокое разнообразие особей. С другой стороны, динамический метод имеет самый высокий индекс разницы покрытия на 18% по сравнению с серийным подходом.

Заключение

.

В процессе проведенных в диссертационной работе исследований получены следующие основные результаты:

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

2. Анализ многокритериального характера задачи группового управления динамическими объектами и применение концепции доминирования по Парето. Показал, что формирование множества Парето может быть вычислительно дорогое и зачастую невозможное, так как сложность основных приложений предотвращает точные методы их применения. По этой причине был разработан целый ряд стратегий стохастического поиска, таких как табу поиска, моделирование отжига и оптимизация колонии муравьев. Обычно они не гарантируют определения оптимального компромисса, но пытаются найти хорошее приближение, т. е. набор векторов решений, цель которых, не слишком далека от оптимального вектора цели [29]. Стандартный генетический алгоритм (СГА) является высокоэффективным средством оптимизации, но отсутствие в нем эффективных средств поддержания разнообразия в популяции на протяжении всего процесса поиска приводит к ее преждевременному вырождению. Следствием этого является возможность СГА локализовать за один запуск лишь одно экстремальное решение, что существенно снижает эффективность его использования при решении многоэкстремальных задач. Однако, обладая свойством параллелизма, генетический алгоритм (ГА) как универсальный метод оптимизации имеет полноценные возможности к нахождению всех оптимальных решений, распределенных в поисковом пространстве.

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

4. Анализ существующей литературы, посвященной эволюционным алгоритмам многокритериальной оптимизации, и параллельным эволюционным алгоритмам многокритериальной оптимизации. Парадигма параллельных эволюционных алгоритмов многокритериальной оптимизации концептуально делит общее население на ряд самостоятельных, отдельных (суб) популяцийальтернативный взгляд замечает несколько мелких, разрозненных одновременно выполняемых МКЭА (в каждый процессор часто проводятся отдельные острова) (аналогичным образом в задачах децентрализованного управления см. 1.4.1). Хотя на каждом острове популяция развивается в изоляции, в исполнении большинства пГАМКО, особи иногда мигрируют между островами на основе некоторого отбора.

5. Разработан новый метод коллективного распределенного управления группой динамических объектов на основе параллельных эволюционных алгоритмов многокритериальной оптимизации, который позволяет обеспечить линеаризацию вычислительной сложности задачи группового управления. Алгоритм, предложенный в работе быль разработан в С++ с интерфейсом MatLab и с помощью этого тулбокса было разработано имитационное моделирование управления ветропарками, которое позволяет избегать ненужной переориентации в время местной турбулентности, вибрация и усталость на лезвиях у в корпусе ветрогенератора, найти оптимальное равновесие между полученной энергией и энергией используемой для переориентации, результаты показывают, что предлагаемый метод на 20% более эффективно, чем классическое централизованное управление (см. предложение А).

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

Рис 4.17). Причем это происходит особенно с динамическим методом, поскольку время для миграции уменьшается из поколения в поколение. Далее следует подчеркивать, что у каждого метода есть свои преимущества, в частности динамический метод имеет самый низкий индекс распространения и размер доминирующего пространства на 2% меньше. Это происходит из-за невысокого разнообразия особей и высокого давления отбора, особенно в начале эволюции. Пока случайный метод имеет высокий индекс распространения и размер доминирующего пространства на 7% больше — этот факт демонстрирует низкое давления отбора случайного метода и высокое разнообразие особей. С другой стороны, динамический метод имеет самый высокий индекс разницы прикрытия на 18% по сравнению с серийным подходом.

7. Доказано преимущество параллельных эволюционных алгоритмов многокритериальной оптимизации с помощью сравнительного анализа алгоритмов коллективного распределения целей (см. Рис 4.17). Предложенный алгоритм многокритериальной оптимизации позволяет повысить эффективность коллективного поведения взаимодействующих динамических объектов за счет более эффективного распределения целей путем организации итерационной процедуры оптимизации коллективного решения. Эта процедура и алгоритмы обеспечивают следующие преимущества распределенных по сравнению с централизованными методами [9]. Отсутствие жестких требований по производительности динамических объектов группы, поскольку размерность решаемой ими задачи существенно меньше размерности задач, решаемых централизованными системами управления. Во-вторых, снижаются требования к пропускной способности каналов связи между динамическими объектами группы из-за уменьшения объемов передаваемой каждым роботом информации благодаря применению предлагаемого метода динамических миграций и замен. В-третьих, обеспечивается высокая живучесть системы, поскольку выход из строя отдельного динамического объекта (или даже нескольких динамических объектов) не приводит к выходу из строя всей группы в целом и к невыполнению задачи, поставленной перед всей группой. Это достигается тем, что в процессе коллективного распределения целей функционирование каждого динамического объекта фактически контролируется всеми остальными динамическими объектами группы путем систематического учета поступающей от него информации. Поэтому при выходе из строя какого-либо робота и отсутствии информации о его состоянии и принимаемых им решениях остальные роботы группы перераспределяют между собою числившиеся за ним цели.