Диссертация (1137100), страница 9
Текст из файла (страница 9)
При этом агент может его инициировать сам,если по итогам 2 последних эволюционных циклов ему не удалось привнестиновые решений в . В результате агент меняется с первым закончившим свойэволюционный цикл агентом случайным числом от 1 до | | % 2 переменных из . Соответственно изменяется и = − .5758Для обновления значений производится селекция одного решения из , гдевероятность выбора прямо пропорциональна ().
Значения устанавливаютсяот выбранного решения. Выбор решения повторяется, если значение ни одной из«неактивных» переменных не было изменено.Работа MAGAMO останавливается, когда за определенное число последнихитераций обмена генетическим материалом между агентами не было найденоновых Парето-оптимальных решений.Схема работы MAGAMO представлена на рисунке 1. Зеленым цветомотмечены новые блоки, которые предлагается дополнить к существующему методуSPEA2 для его эффективного распараллеливания в концепции MAGAMO.Важной задачей при сокращении размера популяции является обеспечениевысокой вероятности схождения алгоритма к глобальному экстремуму. Этовыполнимо только при сохранении оптимального соотношения между длинойхромосомы и размером популяции. Поэтому сокращение размера популяциипредлагается достичь за счет уменьшения длины хромосомы, разбив пространствопеременных на кластеры и присвоив каждому вычислительному элементу сетисвой кластер, по которому он будет искать промежуточные результаты.
Этотпринцип заложен в новую предлагаемую методику эффективного решениямногокритериальных оптимизационных задач с функциями многих переменных,используя распределенную эволюционную сеть (РЭС, или distributed evolutionarynetwork - DEN) [96].Блок-схема MAGAMO изображена на рис. 13. Зеленым цветом выделеныблоки, которые отражают научную новизну в разработанном алгоритме.5859Рисунок 13. Блок-схема работы MAGAMOНаглядно принцип работы MAGAMO представлен на рис.
14.5960Рисунок 14. Принцип работы MAGAMO2.3 Программная реализация многоагентного генетического алгоритмаВ рамках диссертационной работы была создана программа управленияраспределенной эволюционной сетью (distributed evolutionary network – DEN) из 4вычислительных элементов (агентов), реализующая MAGAMO. Она представляетсобой Win32-приложение, написанное на языке программирования C# в средеразработке Microsoft Visual Studio 2013. Для ведения глобального архива лучшихрешений создана база данных Microsoft Sql Server 2008.
Управляющая программа6061и агенты «общаются» по протоколу TCP/IP. Распределенная эволюционная сетьбыла интегрирована со средой ИМ PowerSim Studio 8 с помощью компонентыPowerSim Engine, являющейся SDK-библиотекой, за счет чего MAGAMO сможетпроизводить расчет фитнес-функций по входным значениям переменных вимитационных моделях, разработанных в этой среде.Архитектурараспределеннойэволюционнойсетипредставленанаследующем рисунке 15.Расчет значений целевых функций имитационной моделив PowerSim Studioзначения переменныхзначения целевых функцийМногоагентный генетический алгоритм для многокритериальной оптимизации(MAGAMO): 4 агента, реализующих асинхронные эволюционные процессы,взаимодействующие через архив лучших решений.Агент 1Агент 2Агент 3Агент 4новые знач.
"неактивных" перем.новые решенияАрхив лучших решенийРисунок 15. Архитектура распределенной эволюционной сетиК распределенной эволюционной сети может быть подключено и более 4вычислительныхэлементов(агентов),такимобразомонаможетлегкомасштабироваться.2.4 Результаты апробации многоагентного генетического алгоритмаДля демонстрационного решения данной оптимизационной задачи спомощьюMAGAMOиспользоваласьразработаннаяраспределеннаяэволюционная сеть (distributed evolutionary network – DEN), состоящая из 4 агентов.Исходное распределение пространства решений по агентам носило случайныйравномерный характер.В результате работы системы на приближенных к реальности тестовыхданных были найдены 200 Парето-оптимальных решений за 1.5 часа.
Каждое6162решение приводит к комбинации из значений 3 целевых функций. Эти комбинациибыли экспортированы в специальный программный продукт Pareto Front Viewer,разработанный в ВЦ РАН [23, 33, 34], что позволило графически изобразить фронтПарето (рисунок 4).Для визуализации границы Парето выбрано представление на плоскости сиспользованием цветовой шкалы для третьего показателя: ось Ox – накопленнаяEBITDA в тыс. руб., ось Oy – размер активной клиентской базы в тыс.
чел., ось Oz– средняя оборачиваемость товарных запасов в днях. График представлен нарисунке 16.Рисунок 16. Визуализация границы Парето в Pareto Front ViewerДиаграмма позволяет ЛПР увидеть все равнозначные исходы и на основе егодополнительных предпочтений выбрать наиболее рациональный сценарий.Другим результатом апробации стало сравнение MAGAMO и классическойОстровной модели (вариант 1), на каждом из островов выполняется алгоритмSPEA2, с использованием тех же 4 процессоров.
Было произведено 30 тестовыхзапусков и установлен таймер останова по завершении 60 минут на 1 запуск. За этовремя качество и стабильность результатов у MAGAMO оказались значительнолучше (рисунок 17, таблица 3). Это объясняется сверхбольшой размерностьюзадачи и «попаданием» Островной модели при каждом тестовом запуске в разныелокальные оптимумы, а также меньше скоростью схождения. После этого6263Островная модель была перезапущена с двукратным увеличением размерапопуляции и критерием останова через 150 минут. Только при превышениивремени расчетов в 2,5 раза Островной модели удалось добиться примерно тех жерезультатов, что и MAGAMO.
Сравнение результатов Островной модели (вариант2) также представлены на рисунке 17 и таблице 3.Рисунок 17. Сравнение методов построения фронта ПаретоТаблица 3. Сравнение Островной модели и MAGAMOОстровнаяОстровнаямодель,модель,вариант 1вариант 230303060 мин60 мин150 минMAGAMOКоличество запусковВремя расчетов за 1 запускИскомое число Паретооптимальных решений самоговысокого ранга, найденных за194все запуски6364Лучший результат за запуск(найденных решений)Худший результат за запуск(найденных решений)Средний результат за всезапуски (найденных решений)Стандартное отклонение193 (99%)176 (91%)191 (98%)156 (80%)81 (42%)151 (78%)171 (88%)123 (64%)172 (89%)112610Сравнение MAGAMO (SPEA2) и MAGAMO (NSGA2) приведено на рис. 18.Рисунок 18. Сравнение SPEA2 и NSGA2Помимо сравнения с «Островной моделью» проводилась оценка MAGAMOна эталонных тестах поиска Парето-оптимальных решений.
Результаты тестовпоказали сопоставимые результаты с результатами других эволюционных методов(NSGA2, SPEA2) в случае выпуклой границы Парето без разрывов при небольшомпространстве поиска решений. На большом пространстве поиска решений6465эффективность MAGAMO превосходит распространённые эволюционные методыпостроения фронта Парето.2.5 Анализ устойчивости и сходимости многоагентного генетическогоалгоритмаКритерий сходимости эволюционного цикла на уровне агента: = 1 … – агенты – номер шага эволюции по агентам - количество новых Парето-оптимальных решений за очереднойэволюционный шаг по агентам −2 −1 = + + (17) – сумма новых Парето-оптимальных решенийза три последних эволюционных шага1, если ≤ ≤ и > ( ) = {(18),0где – определенное минимально-допустимое число новых Паретооптимальных решений за 3 последних шага эволюции.Критерий сходимости MGAMAO на глобальном уровне: – счетчик эволюционных циклов по агентам (количество итерацийполучения данных агентом из архива) – количество новых Парето-оптимальных решений за очереднойэволюционный цикл по агентам −2 −1 = + + (19) – сумма новых Парето-оптимальныхрешений за три последних эволюционных цикла = ∑=1 (20) – глобальный счетчик эволюционных цикловGlobalStatus(g)= {1, если ≤ ≤ и ∑=1 > (21),0где – определенное минимально-допустимое число новых Паретооптимальных решений за 3 последних эволюционных цикла.Анализ устойчивости и сходимости MAGAMO проводился по итогам 100запусков разработанной эволюционной сети на ИМ ПДТ.
По итогам них были6566сделаны выводы об устойчивости и сходимости данного алгоритма, которая быладостигнута в 30 реализациях из 30. Ниже представлены подтверждающие графики.(рисунок 19, 20):Анализ устойчивости и сходимости многоагентного ГА проводился по итогам30 запусков разработанной эволюционной сети на апробационной модели. Поитогам них были сделаны выводы об устойчивости и сходимости данногоалгоритма, которая произошла в 30 раз из 30.
Ниже представлены подтверждающиеэто графики по результатам 3 запусков эволюционной сети (рисунок 19, 20):Появление новых Парето-оптимальных решений более высокогорангакол-во новых решений250200150100500020406080100120№ эволюционного циклаСамое "медленное" схождениеСкорость схождения "в среднем" (50 запусков)Самое "быстрое" схождениеРисунок 19. График нахождения новых Парето-оптимальных решений болеевысокого рангаГрафик показывает, что новые Парето-оптимальные решения практическиперестали появляться после 90-ой стадии эволюции.6667Рисунок 20.
График динамики числа найденных Парето-оптимальныхрешенийГрафик показывает скорость роста размера найденного подмножестваПарето-оптимальных решений. Примерно к 70 стадии эволюции оно дошло доблизкого значения к целевым 200.2.6 ВыводыПроведенный анализ численных методов поиска Парето-оптимальныхрешений позволил определить возможности по комбинированию реализованных вних подходов и доработке существующих методов для повышения ихэффективности в задачах большой размерности, таких как синтезированнаямногокритериальная оптимизационная из разработанной имитационная модель.Полученные выводы легли в основу нового многоагентного генетическогоалгоритма(MAGAMO)позволяетформироватьдлямногокритериальнойподмножествооптимизации.Парето-оптимальныхАлгоритмрешенийи6768превосходит по эффективности аналоги.
Ключевая особенность алгоритма состоитв распределении пространства поиска решений между агентами и наличием ихинтеллектуальной составляющей.Была проведена программная реализация MAGAMO. Программа MAGAMOбыла агрегирована с разработанной имитационной моделью предприятиядистанционной торговли и синтезированной из нее оптимизационной задачей.Благодаря этому удалось провести успешную апробацию MAGAMO нараспределенной эволюционной сети из 4 агентов. В результате было найдено 200Парето-оптимальных решений.
Для оценки качества алгоритма было проведеносравнение с Островной моделью поиска решений и другими эволюционнымиметодами поиска решений. Для того, чтобы добиться примерно одинаковыхрезультатов, MAGAMO требуется в 2.5 раза меньше времени, чем островноймодели [94].Для проверки MAGAMO на сходимость и устойчивость были проведенычисленные эксперименты По итогам 30 запусков процесса поиска решений сделанвывод о сходимости и устойчивости алгоритма.6869Глава 3. Агрегированная реализация разработанной имитационноймодели и многоагентного генетического алгоритма в рамкахпрограммного комплекса3.1 Описание функционала и архитектуры программного комплексаПо результатам обзора функционала промышленных СИМ, было выявлено,что в них отсутствуют встроенные компоненты поиска Парето-оптимальныхрешений, а подключение дополнительных библиотек с известными численнымиметодами поиска Парето-оптимальных решений не позволяет осуществлятьэффективный поиск в задачах с большой размерностью пространства поискарешений по описанным выше причинам.К тому же решения, входящие в подмножество Парето-оптимальных, вполной мере не отвечает критерию рациональности, так как выдают равнозначныеальтернативы в условиях, когда ЛПР не могло идентифицировать своипредпочтения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
