Автореферат (1137099), страница 4
Текст из файла (страница 4)
Научнаяновизна присутствует в блоках 1, 3 и 4.16Рисунок 2. Принцип работы MAGAMOВ разделе 2.2 диссертации представлено техническое описание MAGAMO.Введем следующие ключевые обозначения:• = 1. . – агенты• – размер популяции• – длина хромосомы• = 2 – размер архива лучших решений -агента• – глобальный архив результирующих Парето-оптимальных решений• – целевой размер глобального архива.• , – конкретная особь в единой популяции для и • ≻ означает, что i-ая особь доминирует по Парето j-ую особь.• = 1.
. – шаг эволюции• – популяция на шаге эволюции 17• – популяция архивного множества на шаге эволюции • = 1. . – массив всех переменных, составляющий общее пространствопоиска решений. Причем элементы массива одной переменнойпредставляются как самостоятельные переменные .• – набор «активных» переменных для -агента, варьируемых в ходе ГА.• = − – набор «неактивных» переменных для -агента, значениякоторых фиксированы в ходе одного эволюционного цикла -агента.• – определенное количество генов для кодирования значений каждойпеременнойПри реализации MAGAMO каждым из -агентов используютсяследующие ключевые операторы и формулы:1)Исходное распределение пространства поиска решений между агентами.Бинарная длина пространства поиска решений = ∑1 .Исходно распределять пространство решений по агентам необходиморавномерно и добиваться максимальной однородности переменных внутриодного агента, чтобы длина хромосомы агентов =была схожей.
Длядостижения однородности распределения следует использовать экспертный истатистических анализ, выявляющий степень зависимости переменных друг отдруга и объединять наиболее зависимые в единые кластеры.В результате равномерного распределение переменных по агентам, каждыйагент получает свой массив «активных» переменных , по которым будетпроисходить поиск решений. Создается начальная популяция 0 . Переменныекодируются с помощью кода Грея, также для переменных с большой областьюдопустимых значений применяется логарифмическое кодирование.Остальные переменные становятся для агента «неактивными» сослучайными фиксированными значениями. Их значения не меняются до моментаочередного перераспределения пространства решений между агентами.2)Расчет фитнес-функции для -ой особи выглядит следующим образом:() = () + (),(8)где величина () отражает силу Парето-доминирования, а () – коэффициент18разряженности.() = ∑ ∈ + ,≻ (),(9)() = |{ | ∈ + ∧ ≻ }|(10)при этом:– это мощность множества особей j из множества + , которыедоминируют по Парето i-ую особь.() =1 +2,(11)при этом – это геометрическая дистанция до -ого ближайшегоэлемента, где величину следует определять по формуле: = √ + .3)(12)Формирование нового архива решений:+1 = { | ∈ + ∧ () < 1} .(13)Если число элементов в +1 превышает , то необходимо сократитьмножество +1 посредством оператора усечения, при котором в результате|+1 | − итераций исключаются особи с минимальным расстоянием до другойособи.Иначе если +1 меньше , тогда в +1 необходимо добавить − |+1 |штуклучшихдоминируемыхрешенийссамойбольшойфункциейприспособленности из + .4)Оператор селекции реализован в виде бинарного турнирного отбора.
Всеособи случайным образом разделяются на пары, для каждой из которыхустраивается турнир. В турнире побеждает особь с более высоким значением(), после чего она допускается к скрещиванию.5)Операторскрещиванияпорезультатамэкспериментоврешеноиспользовать 2-х точечный.6)Оператор мутации. Вероятность мутации задается в диапазоне[0.005 ; 0.02].7)Обновление глобального архива происходит по средствам копированияв него результирующей популяции +1 после завершения эволюционного цикла19очередного агента.
Затем происходит расчет () для каждой особи множества и из него исключаются ||− особей с самым низким значением ().8)Перераспределение пространства поиска решений между агентами.Каждые эволюционных циклов происходит перераспределение пространствапоиска решений между агентами. При этом агент может его инициировать сам,если по итогам 2 последних эволюционных циклов ему не удалось привнестиновые решений в . В результате агент меняется с первым закончившим свойэволюционный цикл агентом случайным числом от 1 до | | % 2 переменных из . Соответственно изменяется и = − .
Для обновления значений производится селекция одного решения из , где вероятность выбора прямопропорциональна (). Значения устанавливаются от выбранного решения.Выбор решения повторяется, если значение ни одной из «неактивных»переменных не было изменено.Критерий сходимости эволюционного цикла на уровне агента: = 1 … – агенты – номер шага эволюции по агентам - количество новых Парето-оптимальных решений за очереднойэволюционный шаг по агентам.Тогда сумма новых Парето-оптимальных решений за три последнихэволюционных шага определяется как: −2 −1 = + + .(14)Статус активности агента:1, если ≤ ≤ и > ( ) = {,(15)0где – определенное минимально-допустимое число новых Паретооптимальных решений за 3 последних шага эволюции.Критерий сходимости MGAMAO на глобальном уровне: – счетчик эволюционных циклов по агентам (количество итерацийполучения данных агентом из архива) – количество новых Парето-оптимальных решений за очереднойэволюционный цикл по агентам.20Тогда сумма новых Парето-оптимальных решений за три последнихэволюционных цикла определяется как: −2 −1 = + + .(16)Глобальный счетчик эволюционных циклов: = ∑=1 (17)Глобальный статус активности:GlobalStatus(g)= {1, если ≤ ≤ и ∑=1 > ,(18)0где – определенное минимально-допустимое число новых Парето-оптимальных решений за 3 последних эволюционных цикла.Анализ устойчивости и сходимости MAGAMO проводился по итогам 50запусков на ИМ ПДТ.
По итогам них были сделаны выводы об устойчивости исходимости данного алгоритма, которая была достигнута в 50 реализациях из 50.Ниже представлены графики, демонстрирующие скорость схождение (рис. 3, 4):Рисунок 3. Общее число найденныхРисунок 4. Появление новых Парето-Парето-оптимальных решенийоптимальных решений более высокогорангаПринцип, заложенный в MAGAMO, получил программную реализацию,описанную в разделе 2.3 и в третьей главе диссертации в виде компонентыпрограммного комплекса.Для демонстрационного решения рассматриваемой оптимизационной21задачи с помощью MAGAMO использовалась распределенная эволюционнаясеть, состоящая из 4 агентов.
Исходное разбиение пространства поиска решенийбыло произведено экспертным путем с учетом однородности переменных. Врезультате работы MAGAMO на тестовых данных были найдены 200 Паретооптимальных решений за 1.5 часа. Каждое решение приводит к комбинации иззначений 3 целевых функций. Эти комбинации были экспортированы вспециальный программный продукт Pareto Front Viewer, разработанный в ВЦРАН (ныне ФИЦ ИУ РАН) под руководством Лотова А.В., что позволилографически изобразить фронт Парето (рисунок 5): ось Ox – накопленная EBITDAв руб.; ось Oy – размер активной клиентской базы в чел.; ось Oz – средняяоборачиваемость товарных запасов в днях (цветовая шкала).Рисунок 5.
Визуализация границы Парето в Pareto Front ViewerДиаграмма позволяет ЛПР увидеть все равнозначные исходы и на основе егодополнительных предпочтений выбрать наиболее рациональный сценарий.Другим результатом апробации стало сравнение MAGAMO (на 4процессорах), SPEA2 (на 1 процессоре) и SPEA2 в виде «Островной модели» (на4 процессорах) – рис. 6, табл. 1.
Под «качество» подразумевается среднее кол-вонайденных решений за все запуски, под «стабильностью» – стандартноеотклонение в массиве из кол-ва решений по итогам каждого запуска. «Качество»и «стабильность» результатов у MAGAMO оказалось значительно лучше. Этообъясняется умением MAGAMO распределять пространство поиска решениймежду агентами, тем самым сокращать длину хромосомы и размер популяции,22при сверхбольшой размерности задачи. С использованием «Островной модели»удалось добиться сопоставимых по качеству результатов только при увеличениивремени расчетов в 2,5 раза (правый столбец в табл. 1).Оценка MAGAMO проводилась также на эталонных тестах поиска Паретооптимальных решений. Результаты тестов показали сопоставимые результаты срезультатами других эволюционных методов (NSGA2, SPEA2) в случае выпуклойграницы Парето без разрывов при небольшом пространстве поиска решений.
Набольшом пространстве поиска решений (при длине хромосомы от 100 генов)эффективность MAGAMO превосходит другие эволюционные методы.Качество найденных Парето-оптимальных решений200Количество Паретооптимальных решенийвысшего ранга из всехзапусковMAGAMO (SPEA2)кол-во найденных решений180160140120Островная модель(SPEA2), число особей = n10080Островная модель(SPEA2), число особей = 3n6013579 11 13 15 17 19 21 23 25 27 29№ запускаРисунок 6. Качество найденных Парето-оптимальных решенийТаблица 1.
Сравнение Островной модели и MAGAMOMAGAMOКоличество запусковВремя расчетов за 1 запускSPEA2(1 процессор)ОстровнаяОстровнаямодель,модель,вариант 1вариант 23030303060 мин60 мин60 мин150 минЧисло Парето-оптимальных решений самоговысокого ранга, найденных за все запуски = 194Лучший результат за запуск(найденных решений)Худший результат за запуск(найденных решений)Средний результат за все запуски193 (99%)41 (21%)176 (91%)191 (98%)156 (80%)0 (0%)81 (42%)151 (78%)171 (88%)12 (6%)123 (64%)172 (89%)23(найденных решений)Стандартное отклонение10112610В третьей главе описан разработанный программный комплекс (далее ПК),включающий в себя следующие компоненты:1.
Win-32 приложение с графическим интерфейсом, управляющее запускомэволюционной сети из N агентов и связывающее остальные компоненты.Архитектура распределенной сети представлена на рис. 7. Она может легкомасштабировать и содержать больше агентов.2. Win-32 приложение, реализующее MAGAMO на стороне Агента.3. Система имитационного моделирования – PowerSim Studio 8.4. База данных Microsoft Sql Server 2008 для хранения архивных решений,подключенная к агентам через набор интерфейсов OLE DB.5. Средство визуализации найденного фронта Парето – Pareto Front Viewer.Найденный набор решений передается из базы данных в Pareto Front Viewerчерез выгрузку в файл в определенном формате.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
