Содержание к диссертации
Введение
Глава 1. Имитационная модель предприятия дистанционной торговли 13
1.1 Выработка рациональных решений с помощью имитационного моделирования 13
1.2 Ключевые Бизнес-процессы предприятия дистанционной торговли 24
1.3 Имитационная модель для получения значений целевых функционалов оптимизационной задачи 25
1.4 Многокритериальная оптимизационная задача предприятия дистанционной торговли 35
1.5 Выводы 44
Глава 2. Разработка многоагентного генетического алгоритма 45
2.1 Используемые численные методы решения многокритериальных оптимизационных задач 45
2.2 Теоретические основы многоагентного генетического алгоритма, разработанного для формирования подмножества Парето
2.3 Программная реализация многоагентного генетического алгоритма 60
2.4 Результаты апробации многоагентного генетического алгоритма 61
2.5 Анализ устойчивости и сходимости многоагентного генетического алгоритма 65
2.6 Выводы 67
Глава 3. Агрегированная реализация разработанной имитационной модели и многоагентного генетического алгоритма в рамках программного комплекса 69
3.1 Описание функционала и архитектуры программного комплекса 69
3.2 Предлагаемые методы визуализации и сужения множества Парето-оптимальных решений 74
3.3 Агрегация разработанной имитационной модели с многоагентным генетическим алгоритмом и другими подсистемами 81
3.4 Результаты численных экспериментов с использованием разработанного программного комплекса 82
3.5 Выводы з
Заключение 85
Список литературы
- Имитационная модель для получения значений целевых функционалов оптимизационной задачи
- Многокритериальная оптимизационная задача предприятия дистанционной торговли
- Программная реализация многоагентного генетического алгоритма
- Агрегация разработанной имитационной модели с многоагентным генетическим алгоритмом и другими подсистемами
Введение к работе
Актуальность темы исследования
В настоящее время задачи бизнес-информатики становятся задачами большой размерности, большой вычислительной сложности и требуют новые подходы к решению. В частности, имитационное моделирование (далее ИМ) оказывается очевидно необходимым для задач бизнес-информатики, в которых целевой функционал не может быть записан в явном виде и посчитан напрямую -его можно вычислить с помощью имитационной модели (далее ИМ).
Актуальной задачей является разработка ИМ сложных организационных структур, таких как предприятие дистанционной торговли (далее ПДТ). Дистанционная торговля через Интернет активно развивается в России. Из-за низких барьеров входа на рынок, в прошлые годы было создано около 200 тыс. Интернет-магазинов. Также большую популярность набирают трансграничные покупки в зарубежных Интернет-магазинах.
В результате на рынке электронной торговли, как частного случая рынка дистанционной торговли, наблюдается перенасыщение и, как следствие, консолидация отрасли вокруг крупных игроков под воздействием жесточайшей конкуренции. В такой ситуации лидерам отрасли нужно балансировать между развитием и оптимизацией, регулярно корректировать свою стратегию и тактику, находить резервы эффективности и принимать взвешенные управленческие решения в условиях серьезной конкуренции. Для помощи в выработке подобных инициатив может служить ИМ деятельности компании, агрегированная с многокритериальной оптимизационной задачей по целевым функционалам.
ИМ крупных организационных структур, таких как лидеры рынка дистанционной торговли, представляют собой многомерную системно-динамическую модель, в которой многократные расчеты значений целевых функционалов в рамках оптимизационной задачи требуют значительных вычислительных ресурсов. Поэтому на фоне существенного расширения вычислительных возможностей современных аппаратно-программных средств все большую актуальность приобретают эффективные оптимизационные модули для решения сложных оптимизационных задач.
Таким образом, актуальна задача проектирования оптимизационных
модулей, предназначенных для поиска решений в многокритериальных оптимизационных задачах большой размерности, агрегированных с ИМ в рамках единого программного комплекса (далее ПК).
При этом можно выделить следующие ключевые проблемы, связанные с разработкой математического и программного обеспечения такого комплекса:
Отсутствие теоретических и практических исследований по проектированию всеобъемлющей ИМ для ПДТ с учетом особенностей предприятия данного типа.
Необходимость построения эффективных алгоритмов поиска решений (в частности, класса генетических алгоритмов) в многокритериальных оптимизационных задачах, в которых значения целевых функционалов должны быть посчитаны с использованием ИМ.
Отсутствие интеграции программных компонент, обеспечивающих возможность поиска рациональных решений (определение наилучших сценариев) с использованием ИМ путем построения границы Парето, ее визуализации и сужения.
Эффективный метод поиска решений в оптимизационной задаче, агрегированной с ИМ ПДТ, востребован на практике.
Степень разработанности проблемы
В научных трудах наблюдается отсутствие исследований по проектированию всеобъемлющей ИМ управления ПДТ. В то же время имеются наработки, моделирующие лишь отдельные бизнес-процессы (далее БП) торговой компании - например, работу склада, колл-центра, логистики (Борщев А.В., Глушак Е.Н., Лаврушина Е.Г. Miller К.). Но нет целостной ИМ, учитывающей специфику ключевых БП ПДТ.
Направления исследований в области построения множества Парето-оптимальных решений многокритериальных оптимизационных задач, которые могут лечь в основу оптимизационного модуля системы, можно разделить на следующие условные группы:
1. Построение границы Парето методами зондирования пространства поиска решений, основанными на численных методах оптимизации (0\Е. Fieldsend, S. Singh, S. Mostaghim, J. Teich, С A. Coello, M.S. Lechunga, X.
Hu, R. Eberhart, M. Laumarms, P. К. Tripathi, S. K. Pal, Гуменникова A.B. и др.) Наиболее проработанный класс методов основан на генетических алгоритмах (Батищев Д.И., Курейчик В.М. и др.). Среди этих методов распространены: NSGA2 (К. Deb, S. Agrawal, A. Pratap, Т. Meyarivan, 2002), основанный на методе недоминируемой сортировки; SPEA2 (Е. Zitzler, М. Laumarms, L. Thiele, 2001), основанный на оценке силы Парето-доминирования.
-
Методы предварительного построения аппроксимационной поверхности отклика и последующий поиск Парето-оптималъных решений по этой поверхности (Егоров И.Н., Бабий Ю. И.). Такой подход дает возможность в ходе оптимизации свести к минимуму «дорогостоящие», с точки зрения затрат машинного времени, процедуры расчета с использованием решателей.
-
Методы визуализации границы Парето с помощью аппроксимационных методов (Лотов А.В., Бушенков В.А., Березкин В.Е., Каменев Г.К., и др.). Из большого набора полученных стохастическим образом решений с помощью аппроксимационных методов строится вероятный фронт Парето.
-
Изучение множества Парето, методы сужения множества Парето -локализация наилучших решений вдоль границы Парето. (Лодиновский В.В., Ногин В. Д., Т. Саати, К. Миеттинен, Б. Руа и др.). Критерий выбора наиболее подходящих решений может быть определен, например, с учетом дополнительных предпочтений, полученных от лица, принимающего решения (далее ЛПР).
Несмотря на обширную базу исследований в существующих промышленных системах имитационного моделирования (далее СИМ), класса AnyLogic, PowerSim, Arena и др., отсутствует инструментарий поиска рациональных решений, который включал бы в себя инструменты поиска Парето-оптимальных решений в многокритериальных оптимизационных задачах большой размерности с последующей визуализацией и сужением фронта Парето.
Объектом исследования является система поиска решений в многокритериальной оптимизационной задаче предприятия дистанционной
торговли с использованием имитационного моделирования.
Предметом исследования является агрегированная с многоагентным генетическим алгоритмом имитационная модель предприятия дистанционной торговли для решения задачи многокритериальной оптимизации.
Цель исследования заключается в разработке имитационной модели и эффективных вычислительных процедур, реализованных в виде программного комплекса, обеспечивающего поиск рациональных управленческих решений в результате решения многокритериальной оптимизационной задачи для предприятия дистанционной торговли.
Задачи исследования для достижения поставленной цели:
-
Спроектировать имитационную модель ПДТ с учетом выявленных особенностей при описании БП, а также имеющихся в данной области исследований.
-
На основе разработанной ИМ синтезировать многокритериальную оптимизационную задачу для поиска рациональных решений при управлении ПДТ.
-
Провести системный анализ существующих методов, алгоритмов и программных продуктов, предназначенных для поиска решений в многокритериальных оптимизационных задачах большой размерности с использованием ИМ.
-
Разработать новый многоагентный генетический алгоритм (далее MAGAMO), предназначенный для нахождения подмножества Парето с использованием агрегированной с ним ИМ, отличающейся большим пространством поиска решений. Провести апробацию MAGAMO для поставленной оптимизационной задачи.
-
Спроектировать программный комплекс (далее ПК), обеспечивающий на основе MAGAMO, агрегированной ИМ и других подсистем эффективную процедуру поиска рациональных решений при управлении ПДТ. Провести численные эксперименты для оценки разработанного ПК.
Методы исследования: системный анализ, имитационное моделирование, генетические алгоритмы, многокритериальная оптимизация, построение границы
Парето-оптимальных решений, разработка распределенных информационных систем.
Информационная база исследования. При построении ИМ использовались результаты статистического анализа, проведенного на основе исторических данных деятельности 3 крупных компаний, а также схемы БП тех же организационных структур. Исторические данные были собраны в единое информационное хранилище, которое использовалось для апробации предложенного метода поиска рациональных решений и разработанного на его основе ПК.
Научная новизна работы заключается в следующих новых научных результатах, выносимых на защиту:
-
Разработана имитационная модель предприятия дистанционной торговли, отличающаяся от существующих более полным математическим описанием деятельности компании благодаря учету особенностей бизнес-процессов, что позволяет формировать целевые функционалы для многокритериальной оптимизационной задачи, решаемой многоагентным генетическим алгоритмом, и учетом сложной динамики трансформации клиентской базы.
-
На основе разработанной имитационной модели синтезирована задача математического программирования - задача многокритериальной оптимизации с тремя конкурентными критериями для поиска рациональных решений при управлении ПДТ.
-
Предложен новый многоагентный генетический алгоритм (далее MAGAMO) для эффективного нахождения подмножества Парето в многокритериальной оптимизационной задаче, агрегированный по целевым функционалам с ИМ ПДТ. MAGAMO отличается от классической островной модели перераспределением пространства решений между агентами и наличием их интеллектуальной составляющей.
-
Разработан оригинальный комплекс программ для поиска рациональных решений с использованием спроектированной имитационной модели, подсистемы поиска подмножества Парето на
основе MAGAMO, визуализации фронта Парето, сужения фронта Парето. В результате произведено принципиальное расширение функционала системы имитационного моделирования в виде нового оптимизационного модуля.
Теоретическая значимость исследования состоит в разработанной ИМ ПДТ, в которой реализован новый подход к прогнозированию продаж, использующий коэффициент трансформации клиентской базы. Благодаря заложенным особенностям ИМ позволяет вычислить целевые функционалы для поставленной многокритериальной оптимизационной задачи. Также новый теоретический результат получен в виде многоагентного генетического алгоритма для формирования подмножества Парето с использованием ИМ.
Практическая значимость исследования заключается в том, что разработанный ПК апробирован на модели реально действующей организационной структуры (ПДТ) и используется при выработке управленческих решений (имеется справка о внедрении).
Достоверность и обоснованность полученных результатов подтверждается их соответствием известным теоретическим и практическим данным, опубликованным в литературе, а также положительными результатами численных экспериментов, проведенных с использованием разработанной ИМ и многоагентного генетического алгоритма на реальных данных ПДТ.
Апробация результатов исследования. Основные результаты диссертационной работы докладывались и обсуждались на научно-методическом семинаре для аспирантов НИУ ВШЭ по специальности «Математическое моделирование, численные методы и комплексы программ» в 2013 г. и на научных конференциях, в т.ч. международных:
«Информационные технологии в экономике, управлении и бизнесе», г. Москва, НИУ ВШЭ, 2013 г., 2015 г.;
«IEEE International Conference on Systems, Man, and Cybernetics», r. Манчестер, Великобритания, 2013 г.;
«V International Conference Optimization and Applications», г. Петровац, Черногория, 2014 г.;
«XVI Апрельская международная научная конференция «Модернизация
экономики и общества», г. Москва, НИУ ВШЭ, 2015 г.
Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 3 статьи в рецензируемых журналах из перечня ВАК, 1 статья в рецензируемом научном журнале, 1 статья в сборниках трудов конференций.
Личный вклад автора - все представленные в диссертации результаты получены лично автором при участии научного руководителя, а именно: создана ИМ ПДТ, на основе которой синтезирована задача многокритериальной оптимизации; для ее решения разработан новый многоагентный генетический алгоритм, агрегированный с ИМ в рамках спроектированного ПК; произведена апробация ПК на реальных данных и его внедрение в действующую компанию.
Подготовка к публикации полученных результатов проводилась как автором самостоятельно, так и в соавторстве с научным руководителей, причем вклад диссертанта был определяющим. Апробация результатов исследования на конференциях проводилась автором самостоятельно.
Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения, списка использованной литературы, включающего 99 наименований, списка сокращений и условных обозначений, приложения. Общий объем диссертации составляет ПО страниц.
Имитационная модель для получения значений целевых функционалов оптимизационной задачи
Имитационное моделирование — это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему и с ней проводятся эксперименты с целью получения информации об этой системе. Экспериментирование с моделью называют имитацией. Имитация, в свою очередь, — это постижение сути явления, не прибегая к экспериментам на реальном объекте). [2]
К имитационному моделированию прибегают, когда: дорого или невозможно экспериментировать на реальном объекте; невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические переменные; необходимо сымитировать поведение системы во времени.
Цель имитационного моделирования состоит в воспроизведении поведения исследуемой системы на основе результатов анализа наиболее существенных взаимосвязей между ее элементами или другими словами — разработке симулятора исследуемой предметной области для проведения различных экспериментов. [2]
С помощью имитационного моделирования можно ответить на множество вопросов, возникающих в момент принятия решения, однако очень часто эти вопросы остаются без ответов до тех пор, пока предполагаемые изменения не будут осуществлены. Но после того как изменения проделаны, цена исправления ошибочных решений становится значительно выше. Имитационное моделирование дает возможность тестировать разные идеи, «проигрывая» их на компьютерной модели, что намного дешевле, чем проводить множество испытаний и исправлений ошибок на реальных процессах.
Существует известная проблема поиска субоптимальных решений в имитационных моделях «больших систем», таких как, система управления технологическими режимами сложного производства, система оптимального управления финансовыми и материальными потоками крупной корпорации, система управления инвестиционным портфелем и др. [1]. Поиск субоптимальных решений в подобных системах должен осуществляться по множеству, как правило, конкурентных и разномасштабных критериев со сложными ограничениями.
Проблема заключается в том, что оптимизация сразу по нескольким критерияи требует значительных временных и вычислительных ресурсов. При этом, так как целевые функции многих переменных (более 10) порождают многомерное пространство поиска решений, вычислительная сложность оптимизационной задачи, как правило, становится преградой к ее решению за допустимое время. Аналитическое описание и строгое решение такой задачи на практике, как правило, не осуществимо.
В то же время, решение - это выбор наиболее приемлемой альтернативы из возможного многообразия вариантов. Цель процесса принятия решений -обеспечить движение к намеченной цели.
Имитационное моделирование позволяет вырабатывать именно рациональные решения - это продуманные, взвешенные решения, принятые на основе выбора, сравнения вариантов и учета многих факторов; другими словами -выгодное целесообразное решение, выбор которого подкреплен результатами объективного анализа. Рациональное решение в отличие от основанного на суждении не зависит от опыта, накопленного в прошлом [36, 38].
Последовательность выработки и принятия рационального решения выглядит следующим образом [98]:
Такое схематичное линейное движение в процессе принятия решения может быть уместным и эффективным при решении задачи с большим количеством явных переменных, которые необходимо структурировать и расставить по местам. Эта система наилучшим образом проявляет себя тогда, когда направлена на решение задач, поддающихся анализу, задач, в которой все переменные могут быть измерены и структурированы с помощью логических действий.
Имитационное моделирование позволяет осуществлять полный цикл выработки и принятия рационального решения. Для этого необходимо создать целостный программный комплекс, позволяющий не только оценивать альтернативы с помощью имитационного моделирования, но и оказывать поддержку лицу, принимающему решения, в выборе одной из них. большинства зарубежных продуктов характерна узкая специализация, фрагментарность предлагаемых решений. В то время как российские разработчики часто стремятся расширить возможности своего продукта, дополнить его новой функциональностью, их зарубежные коллеги дробят продукт на части, каждая из которых решает вполне определенную задачу.
Критерий достаточности функционала СИМ: хорошо реализованный системно-динамический подход к моделированию, возможность подключения гибко-настраиваемого модуля решения оптимизационных задач (в т.ч. многокритериальных), работающего с большим числом варьируемых параметров и графический вывод результата.
Scilab и Simulink - хорошо реализован дискретно-событийный подход к моделированию, но он слабо подходит к стратегическому управлению. Интеграция с MatLab дает возможность использования встроенных в MatLab численных методов. Для управления необходимо знание синтаксиса MatLab. Имеется возможность распараллеливания вычислений. Нельзя из MatLab управлять моделью, только из тех средств. Имеется графический вывод результата.
Arena - OptQuest - по заверению разработчиков до 10 параметров, 1 цель, на основе метаэвристик рассеянного поиска. Имеется графический вывод результата
AnyLogic - OptQuest - по заверению разработчиков до 10 параметров, 1 цель, на основе метаэвристик рассеянного поиска. Возможность подключения Java-приложений и управления испод них. Имеется графический вывод результата
PowerSim - движок PowerSim Solver, в основе генетические алгоритмы, существует проблема быстродействия и точности решений при 10 варьируемых параметрах. Многоцелевая оптимизация достигается только через взвешенную сумму значений критериев. Возможность подключения библиотеки SDK и сторонних приложений, написанных на C++, С#, Java. Отсутствует графический вывод результатов.
Многокритериальная оптимизационная задача предприятия дистанционной торговли
Метод хищник-жертва (predator-prey) предложил Лауманс (М. Laumanns) с соавторами в 1998 г. о MOPSO (Multi-Objective Swarm Optimization) - вариация оптимизации методом роя частиц для многокритериальной оптимизации. о CIAC - вариация оптимизации методом колонии муравьев для многокритериальной оптимизации. Наиболее проработанной в литературе темой является использование генетических алгоритмов (далее ГА) для решения оптимизационных задач. Доказано, что ГА обладают значительно большей временной эффективностью, чем простой метод перебора, и рядом плюсов по сравнению с другими численными способами решения оптимизационных задач. Классическая модель ГА была впервые предложена в 1975 J. Holland [18], в дальнейшем (D. Goldberg выдвинул ряд гипотез и теорий, помогающих глубже понять природу генетических алгоритмов. ГА получили много вариаций, в т.ч. много исследований посвящено использованию ГА для многокритериальной оптимизации. Разработано большое количество методов: На основе ГА разработаны различные методы нахождения Парето-оптимальных решений в многокритериальных оптимизационных задачах [8,9,17]:
VEGA (Vector Evaluated Genetic Algorithm) был предложен в 1984 году Шафером. В данном методе селекция производится для каждого из К критериев отдельно, тем самым промежуточная популяция заполняется равными порциями индивидов, отобранных по каждому из критериев.
FFGA (Fonseca and Fleming s Multiobjective Genetic Algorithm 1993) представляет собой основанную на Парето-доминировании процедуру ранжирования индивидов, где ранг каждого индивида определяется числом доминирующих его индивидов
MOGA (Multi-ObjectiveGeneticAlgorithm), предложенный Фонсека (С М. Fonseca) и Флемингом (P. J. Fleming) в 1993 г. [10]. В методе предполагается, что ранг агента равен числу агентов в популяции, которые его доминирует.
NPGA (Niched Pareto Genetic Algorithm) (1994) был предложен Хорном, принципиально отличается от двух предыдущих, так как в нем заложен механизм поддержания разнообразия. Метод основан на формировании популяционных ниш [19].
NSGA (Srinivas and Deb in 1994) и NSGA-II (Fast and Elitist Multiobjective Genetic Algorithm for Multi-Objective Optimization (Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T Meyarivan, 2002) — развитием метода недоминируемой сортировки является метод, в котором при формировании архивов отвергают агентов, расстояние которых до других агентов в архиве не превышает заданной величины.
SPEA (Strength Pareto Evolutionary Algorithm (1998)) и SPEA-2 (Eckart Zitzler, Marco Laumanns, and Lothar Thiele, 2001). Иное правило ранжирования агентов популяции используется в методе Парето силы (Paretostrength). Развитием алгоритма SPEA является алгоритм SPEA-2, который подобно алгоритму NGSA-Писпользует оценки равномерности Парето-аппроксимации Важным свойством метода SPEA является возможность априорного задания количества итоговых точек в искомой аппроксимации множества
Метод адаптивных взвешенных сумм (AdaptiveWeightedSum (AWS) method) предложили Рю, Ким и Ван (J-Н. Ryu, S. Kim,H. Wan). Метод основан на аддитивной свертке частных критериев оптимальности, но, в отличие от классического метода суммы взвешенных критериев (WeightedSum (WS) method) [1], также использующего такую свертку, предполагает адаптацию весовых коэффициентов в процессе итераций на основе информации о текущем положении подобласти поиска.
Что касается поиска Парето-оптимальных решений путем зондирования пространства, то тут возникает проблема вычислительной сложности, в связи с чем значительные усилия исследователей направлены на сокращение времени вычислений за счет применения алгоритмов параллельных вычислений. Значимым преимуществом ГА является возможность эффективного распараллеливания вычислений [3,4]. Однако ГА всегда имеет риск схождения к локальным субоптимальным решениям вместо глобальных. Но для ЛПР в ряде задач достаточно и суб-оптимального решения, близкого по значению к глобальному оптимуму.
В ряде сравнительных исследований по эффективности вышеперечисленных методов установлено, что SPEA-2 и NSGA-II лучшие остальных методов справляются со своей задачей. Причем, при выпуклом фронте Парето SPEA-2 сходится быстрее, чем NSGA-II. При невыпуклом фронте - наоборот.
Эккарт Цитцлер, Марко Ломание и Лотар Тиеле разработали алгоритм с архивом, использующий понятие силы (или, что более корректно, хилости), и известный как Strength Pareto Evolutionary Algorithm (или SPEA). На данный момент его улучшенный вариант, SPEA2, непосредственно конкурирует с NSGA-II и другими стохастическими многокритериальными алгоритмами оптимизации8 . Как и NSGA-II, SPEA2 сохраняет архив наилучших найденных особей на границе Парето, равно как и некоторое количество других особей. Однако в SPEA2 используется Парето-мера wimpiness, и степень перенаселения популяции определяется на основе расстояний между особями в многокритериальном пространстве, а не в пространстве рангов. Мера схожести в SPEA2 [6] вычисляется как расстояние до других особей популяции, в частности, до k-й ближайшей особи.
Программная реализация многоагентного генетического алгоритма
По результатам обзора функционала промышленных СИМ, было выявлено, что в них отсутствуют встроенные компоненты поиска Парето-оптимальных решений, а подключение дополнительных библиотек с известными численными методами поиска Парето-оптимальных решений не позволяет осуществлять эффективный поиск в задачах с большой размерностью пространства поиска решений по описанным выше причинам.
К тому же решения, входящие в подмножество Парето-оптимальных, в полной мере не отвечает критерию рациональности, так как выдают равнозначные альтернативы в условиях, когда ЛПР не могло идентифицировать свои предпочтения. На практике визуализация найденной границы Парето может помочь ЛПР уточнить свои предпочтения, с помощью которых удастся выявить более и менее рациональные из подмножества Парето-оптимальных, воспользовавшись дополнительной информации от ЛПР и методом «справедливых компромиссов» для сужения фронта Парето. Для СИМ предлагается добавить компоненты визуализации и сужения множества Парето-оптимальных решений. После сужения в сформированном множестве останутся рациональные решения-альтернативы. В заключение первой главы рассмотрен метод «справедливых компромиссов» для сужения фронта Парето.
Реализация функционала программного комплекса проходила в 4 этапа: 1. Разработан программный модуль, реализующий работу MAGAMO в среде программирования Microsoft Visual Studio на языке программирования С#. 2. Разработана подсистема управления имитационной моделью, которая была также реализована в среде программирования Microsoft Visual Studio на языке программирования С#. Из нее вызываются методы модели, спроектированной в программном средстве для имитационного 69 моделирования PowerSim Studio 8. Программа управления расчетами ИМ работает с этой библиотекой, в которой содержится модель и предопределенные методы для работы с ней, среди них: Reset() -перезапуск модели, Advance() - шаг модели на один временной интервал, методы для присваивания значений «public-переменным» модели, Sim.Variables.Find("Ha3BaHHe переменной»).№шіЬег - получение и присваивание значения переменной, и т.п. 3. Разработана подсистема управления РЭС и интегрирована с программной реализацией ГА и подсистемой управления ИМ, став связующим звеном для обеих подсистем. Таким образом, целевые оптимизационные функции модели стали функциями приспособленности в ГА, а значения варьируемых параметров ИМ были закодированы в хромосомах, которыми стали наделены особи в популяции ГА. Программа получила пользовательский интерфейс с возможностью запуска, задания настроек функционирования алгоритма и выгрузки финальных результатов в Microsoft Excel. 4. Программа была интегрирована с программными продуктами по визуализации и сужению фронта Парето. В результате была создан программный комплекс, осуществляющий поддержку полного цикла выработки рациональных решений в многомерных имитационных моделях. Вся распределенная вычислительная система агентов способна к масштабированию, так как может состоять из любого разумного числа ЭВМ. Разработанный программный комплекс, включающий в себя следующие компоненты: 1. Win-32 приложение с графическим интерфейсом, управляющее запуском эволюционной сети из N агентов, и связывающее остальные компоненты. 2. Win-32 приложение, реализующее алгоритм MAGAMO на стороне Агента. 3. Система имитационного моделирования - PowerSim Studio 8. 70 4. База данных Microsoft Sql Server 2008 для хранения архивных решений, подключенная к агентам через набор интерфейсов OLE DB. 5. Средство для визуального найденного фронта Парето - Pareto Front Viewer. Найденный набор решений передается из базы данных в Pareto Front Viewer через их выгрузку в MS Office Excel. 6. Программный продукт для ввода дополнительной информации о предпочтениях ЛПР и сужения на ее основе фронта Парето с помощью метода справедливого компромисса. Программный продукт разработан под руководством В. Ногина в СПбГУ. Его интеграция с найденным набором решений осуществлена через MS Office Excel. Финальный набор рациональных решений также экспортируется в MS Office Excel.
Компоненты 1, 2, 4, 5 являются оригинальными - они были разработаны в рамках диссертационного исследования. Win-32 приложения были созданы в Microsoft Visual Studio 2013 на языке программирования С# (фрагмент программного кода, реализующего агентный подход, содержится в Приложении 2). Для их интеграции с имитационной моделью из PowerSim Studio 8 в Microsoft Visual Studio 2013 была использована библиотека PowerSim Engine. С помощью нее можно управлять запуском имитационной модели извне, передавая в модель входные переменные и получая значения рассчитанных целевых функций на выходе.
Агрегация разработанной имитационной модели с многоагентным генетическим алгоритмом и другими подсистемами
Таким образом, общая методика исследования задач принятия решения на основе математического моделирования может быть реализована в рамках одного из следующих подходов.
Первый подход. Для заданной многокритериальной задачи оптимизации находится множество её Парето-оптимальных решений, а выбор конкретного оптимального варианта из множества Парето -оптимальных предоставляется ЛПР
Второй подход. Как уже было сказано выше, производится сужение множества Парето-оптимальных исходов (в идеале - до одного элемента) с помощью некоторых формализованных процедур, что облегчает окончательный исход для ЛПР. Отметим, что такое сужение может быть произведено только при наличии дополнительной информации о критериях или свойствах оптимального решения.
Наиболее логичным и последовательным представляется путь построения бинарного отношения предпочтения, более сильного, чем отношение Парето, позволяющего сузить множество выбираемых вариантов до приемлемых с точки зрения ЛПР размеров. Разумеется, для этого потребуется некоторая дополнительная информация, которую придётся получить от ЛПР. Это может быть информация о критериях, о самих сравниваемых вариантах и т.п. Задача, стоящая перед создателями методов, заключается в том, чтобы с помощью этой информации обосновать свои действия по сужению выбора и гарантировать ЛПР от того, чтобы ни один из вариантов, представляющих для него интерес, не был потерян в процессе оптимизации.
76 После построения фронта Парето, ЛПР необходимо представить для принятия решения пригодный для практического анализа объем данных. В связи с эти возникает проблема сужения множества Парето. Существуют следующие методы сужения множества Парето-оптимальных решений
Идея активного участия ЛПР в МКО привела к разработке многочисленных интерактивных методов, состоящих в чередующихся процедурах выбора и автоматического расчета. В обзорах литературы указываются разные базовые методы. Например, стоит упомянуть методы ARBDS [21], CONTEXT[22], GUESS[23], NIMBUS (Nondifferentiable Interactive Multiobjective Bundle-based optimization System). Этот метод разработан в Хельсинском университете (г. Хельсинки, Финляндия) под руководством профессора К. Миеттинен и др.
Удачное решение проблемы сужения множества Парето осуществляется на основе так называемых «квантов информации» об отношении предпочтения [2], которые характеризуют готовность ЛПР проявлять определенную гибкость в процессе принятия решений - уступать по одним критериям ради получения выигрыша по каким-то другим критериям. Заметим, что наличие «кванта информации» может быть охарактеризовано и в терминах относительной важности критериев.
В общем случае алгоритм учёта набора «квантов» информации для сужения множества Парето выглядит следующим образом. Пусть задан набор «квантов» UQ,...,UQ . Обозначим через т = т0 размерность векторного критерия /. На первом шаге строится матрица 7\, порождённая вектором UQ. ВВОДИТСЯ матрица Q1 = 7\. Если р0 = 1, то других «квантов» нет, и алгоритм завершается. Если р0 1, то строятся образы оставшихся «квантов» T±UQ, ..., T±UQ. ЕСЛИ среди них есть хотя бы один вектор 7\UQ 0, алгоритм завершается с предупреждением о противоречивости исходного набора «квантов». Все векторы T±UQ О отбрасываются. Если все векторы оказались отброшены, алгоритм завершается. Если нет, то оставшиеся векторы переобозначаются как i , ...,1 1 , и алгоритм переходит на следующий шаг. Пусть проделано s — 1 шагов, построены матрицы Тк размерности пгк X пгк_1, к = 1, s — 1 и известна текущая матрица Qs-i-Остаются неучтёнными «кванты» ul_t,..., u -l1- На s-ом шаге строится матрица Ts, порождённая вектором ul_t. Вычисляется Qs = TSQS_1. Если ps-1 = 1, то «квантов» больше нет, и алгоритм завершает свою работу. Если же ps-i 1? т0 строятся образы «квантов» Tsu _1,..., Т3и . Если среди получившихся векторов есть такие, которые не имеют строго положительных компонент, то алгоритм завершается с предупреждением о противоречивости исходного набора «квантов». Все векторы, не имеющие отрицательных компонент, удаляются. Оставшиеся переобозначаются как uj,..., u s. Если векторов не осталось, алгоритм завершается. Если ps 1, алгоритм переходит к следующему шагу. Алгоритм конечен, так как на каждом шаге s выполняется ps ps-1, а р0 — конечное число. Отсюда же видно, что алгоритм сделает не более р0 шагов, где р0 — количество исходных «квантов». Метод сужения множества Парето с использованием квантов информации об отношении предпочтения ЛПР реализован в программе, получившей название ParSetRe, разработанной в Санкт-Петербургском Государственном Университете. Пользователь может задать набор критериев, сформировать список вариантов, ввести информацию о предпочтениях и получить суженное множество альтернатив (рис. 26,27,28). Программа представляет собой jar-файл, поэтому для её запуска необходима предустановленная среда исполнения Java (англ. ЖЕ — Java Runtime Environment).