автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Агрерированная с многоагентным генетическим алгоритмом имитационная модель предприятия дистанционной торговли для решения задачи многокритериальной оптимизации

На правах рукописи

Хивинцев Максим Андреевич

Агрегированная с многоагентным генетическим алгоритмом имитационная модель предприятия дистанционной торговли для решения задачи многокритериальной оптимизации

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ (технические науки)

7 ОКТ 2015

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2015

005563140

005563140

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики»

Научный Акопов Андраник Сумбатович,

руководитель: доктор технических наук, доцент.

Официальные Косоруков Олег Анатольевич,

оппоненты: доктор технических наук, профессор, ФГБОУ ВО «Московский

государственный университет имени М.В.Ломоносова», заместитель декана факультета высшей школы управления и инноваций.

Пантелеев Андрей Владимирович

доктор физико-математических наук, профессор, ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)», заведующий кафедрой «Математическая кибернетика» факультета прикладной математики и физики.

Ведущая Федеральный исследовательский центр «Информатика и

организация: управление» Российской академии наук

Защита состоится 26 октября 2015 года в 16:00 на заседании диссертационного совета Д 212.048.09, созданного на базе ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», по адресу: 105187, Москва, ул. Кирпичная, д. 33, к 503.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики» по адресу: 101000, Москва, ул. Мясницкая, д.20, и на сайте http://www.hse.ru/sci/diss/.

Автореферат разослан

Ученый секретарь диссертационного совета, доктор технических наук

Гостев Иван Михайлович

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы исследования

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

Актуальной задачей является разработка ИМ сложных организационных структур, таких как предприятие дистанционной торговли (далее ПДТ). Дистанционная торговля через Интернет активно развивается в России. Из-за низких барьеров входа на рынок, в прошлые годы было создано около 200 тыс. Интернет-магазинов. Также большую популярность набирают трансграничные покупки в зарубежных Интернет-магазинах.

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

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

Таким образом, актуальна задача проектирования оптимизационных

3

модулей, предназначенных для поиска решений в многокритериальных оптимизационных задачах большой размерности, агрегированных с ИМ в рамках единого программного комплекса (далее ПК).

При этом можно выделить следующие ключевые проблемы, связанные с разработкой математического и программного обеспечения такого комплекса:

• Отсутствие теоретических и практических исследований по проектированию всеобъемлющей ИМ для ПДТ с учетом особенностей предприятия данного типа.

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

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

Эффективный метод поиска решений в оптимизационной задаче, агрегированной с ИМ ПДТ, востребован на практике. Степень разработанности проблемы

В научных трудах наблюдается отсутствие исследований по проектированию всеобъемлющей ИМ управления ПДТ. В то же время имеются наработки, моделирующие лишь отдельные бизнес-процессы (далее БП) торговой компании - например, работу склада, колл-центра, логистики (Борщев A.B., Глушак E.H., Лаврушина Е.Г. Miller К.). Но нет целостной ИМ, учитывающей специфику ключевых БП ПДТ.

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

1. Построение границы Парето методами зондирования пространства поиска решений, основанными на численных методах оптимизации (J.E. Fieldsend, S. Singh, S. Mostaghim, J. Teich, C.A. Coello, M.S. Lechunga, X.

4

Hu, R. Eberhart, M. Laumanns, P. K. Tripathi, S. K. Pal, Гуменникова A.B. и др.) Наиболее проработанный класс методов основан на генетических алгоритмах (Батищев Д.И., Курейчик В.М. и др.). Среди этих методов распространены: NSGA2 (К. Deb, S. Agrawal, A. Pratap, Т. Meyarivan, 2002), основанный на методе недоминируемой сортировки; SPEA2 (Е. Zitzler, М. Laumanns, L. Thiele, 2001), основанный на оценке силы Парето-доминирования.

2. Методы предварительного построения аппроксимационной поверхности отклика и последующий поиск Парето-оптимальных решений по этой поверхности (Егоров И.Н., Бабий Ю. И.). Такой подход дает возможность в ходе оптимизации свести к минимуму «дорогостоящие», с точки зрения затрат машинного времени, процедуры расчета с использованием решателей.

3. Методы визуализации границы Парето с помощью аппроксимационных методов (Лотов A.B., Бушенков В.А., Березкин В.Е., Каменев Г.К., и др.). Из большого набора полученных стохастическим образом решений с помощью аппроксимационных методов строится вероятный фронт Парето.

4. Изучение множества Парето, методы сужения множества Парето -локализация наилучших решений вдоль границы Парето. (Подиновский В.В., Ногин В.Д., Т. Саати, К. Миеттинен, Б. Руа и др.). Критерий выбора наиболее подходящих решений может быть определен, например, с учетом дополнительных предпочтений, полученных от лица, принимающего решения (далее ЛПР).

Несмотря на обширную базу исследований в существующих промышленных системах имитационного моделирования (далее СИМ), класса AnyLogic, PowerSim, Arena и др., отсутствует инструментарий поиска рациональных решений, который включал бы в себя инструменты поиска Парето-оптимальных решений в многокритериальных оптимизационных задачах большой размерности с последующей визуализацией и сужением фронта Парето.

Объектом исследования является система поиска решений в многокритериальной оптимизационной задаче предприятия дистанционной

торговли с использованием имитационного моделирования.

Предметом исследования является агрегированная с многоагентным генетическим алгоритмом имитационная модель предприятия дистанционной торговли для решения задачи многокритериальной оптимизации.

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

Задачи исследования для достижения поставленной цели:

1. Спроектировать имитационную модель ПДТ с учетом выявленных особенностей при описании БП, а также имеющихся в данной области исследований.

2. На основе разработанной ИМ синтезировать многокритериальную оптимизационную задачу для поиска рациональных решений при управлении ПДТ.

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

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

5. Спроектировать программный комплекс (далее ПК), обеспечивающий на основе МАОАМО, агрегированной ИМ и других подсистем эффективную процедуру поиска рациональных решений при управлении ПДТ. Провести численные эксперименты для оценки разработанного ПК.

Методы исследования: системный анализ, имитационное моделирование, генетические алгоритмы, многокритериальная оптимизация, построение границы

Парето-оптимальных решений, разработка распределенных информационных систем.

Информационная база исследования. При построении ИМ использовались результаты статистического анализа, проведенного на основе исторических данных деятельности 3 крупных компаний, а также схемы БП тех же организационных структур. Исторические данные были собраны в единое информационное хранилище, которое использовалось для апробации предложенного метода поиска рациональных решений и разработанного на его основе ПК.

Научная новизна работы заключается в следующих новых научных результатах, выносимых на защиту:

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

2. На основе разработанной имитационной модели синтезирована задача математического программирования - задача многокритериальной оптимизации с тремя конкурентными критериями для поиска рациональных решений при управлении ПДТ.

3. Предложен новый многоагентнын генетический алгоритм (далее MAGAMO) для эффективного нахождения подмножества Парето в многокритериальной оптимизационной задаче, агрегированный по целевым функционалам с ИМ ПДТ. MAGAMO отличается от классической островной модели перераспределением пространства решений между агентами и наличием их интеллектуальной составляющей.

4. Разработан оригинальный комплекс программ для поиска рациональных решений с использованием спроектированной имитационной модели, подсистемы поиска подмножества Парето на

основе MAGAMO, визуализации фронта Парето, сужения фронта Парето. В результате произведено принципиальное расширение функционала системы имитационного моделирования в виде нового оптимизационного модуля.

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

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

Достоверность и обоснованность полученных результатов подтверждается их соответствием известным теоретическим и практическим данным, опубликованным в литературе, а также положительными результатами численных экспериментов, проведенных с использованием разработанной ИМ и многоагентного генетического алгоритма на реальных данных ПДТ.

Апробация результатов исследования. Основные результаты диссертационной работы докладывались и обсуждались на научно-методическом семинаре для аспирантов НИУ ВШЭ по специальности «Математическое моделирование, численные методы и комплексы программ» в 2013 г. и на научных конференциях, в т.ч. международных:

• «Информационные технологии в экономике, управлении и бизнесе», г. Москва, НИУ ВШЭ, 2013 г, 2015 г.;

• «IEEE Internationa] Conference on Systems, Man, and Cybernetics», r. Манчестер, Великобритания, 2013 г.;

• «V International Conference Optimization and Applications», г. Петровац, Черногория, 2014 г.;

• «XVI Апрельская международная научная конференция «Модернизация

8

экономики и общества», г. Москва, НИУ ВШЭ, 2015 г.

Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 3 статьи в рецензируемых журналах из перечня ВАК, 1 статья в рецензируемом научном журнале, 1 статья в сборниках трудов конференций.

Личный вклад автора - все представленные в диссертации результаты получены лично автором при участии научного руководителя, а именно: создана ИМ ПДТ, на основе которой синтезирована задача многокритериальной оптимизации; для ее решения разработан новый многоагентный генетический алгоритм, агрегированный с ИМ в рамках спроектированного ПК; произведена апробация ПК на реальных данных и его внедрение в действующую компанию.

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

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

И. СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации приводится спроектированная ИМ ПДТ, которая была построена в результате анализа и описания ключевых БП действующих компаний. Следующие БП определяют специфику деятельности ПДТ в сравнении с классическим торговым предприятием: привлечение клиентов, исполнение заказов, управление запасами.

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

9

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

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

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

Все формулы ИМ приводятся в таблице №2 и №4 в тексте диссертации. Учет перечисленных особенностей в ИМ позволил рассчитать 3 целевых показателя, на которые ориентируются при оценке успешности деятельности ПДТ в российских реалиях: заработанная прибыль, размер активной клиентской базы, оборачиваемость запасов. Благодаря комплексности ИМ на ее основе удалось синтезировать многокритериальную оптимизационную задачу, выделив не только 3 самых важных целевых функционала, но и наиболее действенные управляющие параметры, а также ограничения. ИМ была разработана с использованием методов системной динамики и программного продукта PowerSim Studio 8.

Стратегические управляющие параметры модели:

• q — уровень качества обработки заказов;

• a.j - доступность товаров на складе по товарным категориям (%);

• ml; - маркетинговая активность по i-ым регионам (%);

• m2j - маркетинговая активность по j-ым товарным категориям (%);

• тЗк - маркетинговая активность по k-ым сегментам клиентов (%).

• dt - соотношение стоимости доставки к стоимости товаров в i-ых

10

регионах (%);

Оперативные управляющие параметры модели:

* Vj(f) - уровень цен на j-ые товарные категории в период времени t (у.е.);

• ~ коэффициент интенсивности маркетинговой активности в период времени моделирования t (t — 1.. Г).

Зада ча. Необходимо вычислить оптимальные значения набора оперативных и стратегических управляющих параметров [q, а}, ml^rrilj, m3k, dh Vj(t), m(t)}, обеспечивающих максимальные значения прибыли (EBITDA) и размера клиентской базы (CBSUM) при минимальном времени оборачиваемости запасов L:

max {EBITDA},

{q,aj,mli,m2j,m3k,pj(t),di,m(t)}

max {CBSUM}, ,,,

{q,aj,mli,m2j,m3k,pj(t),di,m(t)] . min {L}.

V {q,aj,mli,m2 j,m3k,pj(t),di,m(t')}

при выполнении следующих ограничений в каждый момент времени t:

( м,Шп < PiW - 1 < М,тах

1 CPj,Plj(0 ~ 1

Msiminj < XU Qi,j(t)/ZUEk=i Vixj(t), yJ o-m

MS2min: <

Ll(t) + L2(t) < Lmax.

Ограничения распространяются на уровень маржинальности по категориям СMjmin и Mjmax), на минимально-допустимую долю рынка по городам (М52т'п;) и категориям (MSlmm.), на срок максимальной оборачиваемости запасов Lmax.

Накопленная прибыль (EBITDA) рассчитывается по формуле:

EBITDA =Si=t0(G(i)-F(t)), (3)

где G(t) - доходы с продаж за период, £(t) - расходы за период. Расчет данных показателей приведен в разделе 1.4 диссертации.

Размер активной клиентской базы рассчитывается по формуле:

CBSUM = ZUSL CBiXw(T), (4)

где CBi k w(T) - количество клиентов в конечный период моделирования Т по /'ым городам, &-ым сегментам потребителей, iv-ым неделям совершения последней

11

покупки

Динамика средней оборачиваемости запасов в течение периода моделирования рассчитывается по формуле:

I = £[=Соал(0 + £2 ш/т, (5)

где средневзвешенный срок исполнения заказов:

¿КО - Я^Е^ЛСРДО * / (1 - /?;)} / СРДО; (6)

средняя оборачиваемость складских запасов:

¿2(0 = ^=1{СРД0 * Оу * (а;/аЬу)6} СРДО, (7)

где СРДО - суммарная себестоимость по категории в период г, - доля возвратов после продажи по категориям, ай, - уровень базовой доступности на складе товаров по категориям, Ь - коэффициент нелинейного роста длительности оборачиваемости склада при повышении доступности товаров на складе.

ИМ является многомерной и содержит следующие настраиваемые измерения: кластеры товарных категорий, кластеры городов (регионы), клиентские сегменты, периоды моделирования. Данные измерения могут содержать заданное число элементов. Для демонстрационного решения рассматриваемой оптимизационной задачи для действующего ПДТ было определено 5 кластеров товарных категорий, 6 кластеров городов, 3 клиентских сегмента, 12 месяцев моделирования. Таким образом, общее число переменных в оптимизационной задаче достигает 98, что характеризует ее размерность как сверхбольшую и требует новых подходов к эффективному решению.

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

В сложных системно-динамических ИМ, таких как разработанная ИМ ПДТ,

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

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

Из метаэвристических алгоритмов выгодно выделяется класс генетических алгоритмов (далее ГА) тем, что ГА обладают важным преимуществом -возможность распараллеливания вычислений и, тем самым, масштабирование вычислительных возможностей, что очень актуально при решении оптимизационных задач большой размерности. Однако ГА всегда имеет риск схождения к локальным субоптимальным решениям вместо глобальных. Но для лица, принимающего решения (далее ЛПР), при управлении ПДТ достаточно найденных субоптимальных решений, близких к глобальным.

Классическая модель ГА была впервые предложена в 1975 J. Holland, в дальнейшем D. Goldberg выдвинул ряд гипотез и теорий, помогающих глубже понять природу ГА. К настоящему моменту на основе ГА разработаны различные методы нахождения Парето-оптимальных решений:

• VEGA (Vector Evaluated Genetic Algorithm) предложен в 1984 году Шафером. В данном методе селекция производится для каждого из критериев отдельно.

• FFGA (Fonseca and Fleming's Multiobjective Genetic Algorithm 1993) представляет собой основанную на Парето-доминировании процедуру ранжирования индивидов

• MOGA (Multi-Objective Genetic Algorithm), предложенный Фонсека (С. М. Fonseca) и Флемингом (P. J. Fleming) в 1993 г. В методе предполагается, что ранг особи равен числу особей в популяции, которые ее доминируют.

• NPGA (Niched Pareto Genetic Algorithm) (1994) был предложен Хорном, принципиально отличается от двух предыдущих, так как в нем заложен

13

механизм поддержания разнообразия.

• NSGA-II (Fast and Elitist Multiobjective Genetic Algorithm for Multi-Objective Optimization (Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, T Meyarivan, 2002)) — является развитием метода недоминируемой сортировки NSGA (Srinivas and Deb, 1994), в котором при формировании архива отвергаются особи с расстоянием до других особей в архиве не превышаем заданной величины.

• SPEA-2 (Strength Pareto Evolutionary Algorithm (Eckart Zitzler, Marco Laumanns, and Lothar Thiele, 2001)) является развитием метода SPEA (1998) и основан на принципе оценки Парето-силы для ранжирования особей.

• Метод адаптивных взвешенных сумм (AdaptiveWeightedSum method) предложили J-H. Ryu, S. Kim,H. Wan. Метод основан на аддитивной свертке частных критериев оптимальности с адаптируемыми коэффициентами.

В ряде сравнительных исследований по эффективности вышеперечисленных методов установлено, что SPEA-2 и NSGA-II лучше прочих справляются со своей задачей. Причем установлено, что при выпуклом фронте Парето SPEA-2 сходится быстрее, чем NSGA-II.

Для повышения временной эффективности вычислительной процедуры значительные усилия исследователей направлены на сокращение времени поиска решений за счет применения алгоритмов параллельных вычислений. Первым систематическим изучением параллельных ГА с множеством популяций была диссертация Р.Б.Гроссо (Grosso). Сегодня существуют следующие методики распараллеливания вычислений для ГА:

• Островная модель - это самый распространенный метод распараллеливания вычислений, при котором каждый процессор реализует собственный ГА на выделенной ему части всей популяции. С определенной периодичностью происходит обмен части популяции между «островами».

• Однопопуляционный алгоритм - главный процессор содержит всё поколение в своей памяти и выполняет операторы селекции, кроссовера и мутации. Функции пригодности индивидов вычисляются на других процессорах.

• Клеточный алгоритм - в этом случае каждым процессорным элементом в один момент времени обрабатывается один индивид.

Проведенный анализ вариаций ГА для поиска Парето-оптимальных

14

решений позволил выявить ключевой фактор их неэффективности в задачах с большим пространством поиска решений - это длина L кодирующей хромосомы. Величина L прямо пропорциональна необходимому размеру популяции и, соответственно, кол-ву расчетов фитнес-функции. С хромосомой из более чем 10 переменных (условная длина более 100 генов) перечисленные методы поиска Парето-оптимальных решений теряют свою эффективность. Полученные выводы легли в основу нового многоагентного генетического алгоритма для многокритериальной оптимизации (multi-agent genetic algorithm for multi-objective optimization - MAGAMO). Его эффективность достигается за счет особой методики распараллеливания вычислений, при которой L -> min.

В основе MAGAMO лежит динамическое взаимодействие асинхронных интеллектуальных агентов, каждый из которых выполняет свой эволюционный процесс согласно методу SPEA2. Данный метод был выбран, т.к. в сравнительных исследованиях он показывает лучшие результаты при выпуклом фронте Парето с неизолированными решениями, а функциям в разработанной ИМ свойственны эти характеристики. Задача по определению оптимальных настроек генетических операторов не ставилась, чтобы точнее оценить качество предлагаемой методики распараллеливания вычислений.

Отличия MAGAMO от параллельной модификации SPEA2 в виде «Островной модели» заключаются в следующем:

1. В MAGAMO используется агентный подход для распараллеливания вычислений - все пространство поиска решений делится между агентами (в отличие от «островов», где оно фиксировано) поэтому каждый агент имеет фитнес-функцию, содержащую лишь свой набор активных переменных (L -> min). С определенной периодичностью пространство поиска решений перераспределяется между агентами.

2. Агенты, в отличие от «островов», наделены элементами интеллекта - они могут самостоятельно инициировать обмен лучшими результатами поиска в случае, если другие агенты достигли очередного улучшения своих субоптимальных решений.

3. В MAGAMO используется общий (глобальный) архив лучших решений, через который происходит обмен результатами поиска между агентами

по завершении очередного эволюционного цикла.

За счет перечисленных особенностей МАвАМО эффективнее справляется с нахождение подмножества Парето с использование разработанной ИМ, чем 8РЕА2 на одном процессоре и классическая «Островная модель». Результаты сравнения приведены в разделе 2.4 диссертации.

Блок-схема МАОАМО изображена на рис. 1. Серым цветом выделены блоки, которые отражают научную новизну в разработанном алгоритме.

С Начало работы Эволюционной сети из N агентов

Исходное распределение пространства

поиска решений между агентами

Г»

Начало работы Агента № 1

Начало работы Агента № 2.

1. Создание исходной популяции

[ Начало нового эволюционного Л V цикла агента )

1

2. Реализация алгоритма поиска Парето-оптимальных решений 5РЕА2

1

3. Выгрузка новых Парето-оптимальных решений в глобальныйархив

---- 4. Глобальный критерий ^ " ■___сходимости достигнут?_______"*" ^Гнет

5. Перераспределение пространства поиска решений между агентами (опционально по критерию)

1

з. Получение новых значений неактивных переменньк из глобального архив

т.

->

I (аналогично Агенту №1) |

' В глобальном архиве содержатся > искомые решения. Конец работы агентов и всей Эволюционной сети.

Рисунок 1. Блок-схема работы МАвАМО

Принцип работы МАвАМО наглядно представлен на рис. 2. Научная новизна присутствует в блоках 1,3 и 4.

1. Перераспределение пространства поиска решений между агентами

2. Поиск Парето-оптимальных решений методом ЗРЕА2

I

Агент №1

>Ц I ХЗ |*< | ХБ | Х6 | Х~7~|

0 2 4 6 8 '

Глобальный архив

Фронт Парею высшего ранга

3. Запись, чтение и отбор лучших решений из глобального архива

4. Получение значений «неактивных» переменных агентами (не назначенных для оптимизации данному агенту)

Рисунок 2. Принцип работы МАСАМО

В разделе 2.2 диссертации представлено техническое описание МАОАМО. Введем следующие ключевые обозначения: • к = 1.. К — агенты N - размер популяции I - длина хромосомы

Ык = 2Nk - размер архива лучших решений к-агента А - глобальный архив результирующих Парето-оптимальных решений Ма - целевой размер глобального архива. £,_/' - конкретная особь в единой популяции для I и у I > ] означает, что ;-ая особь доминирует по Паретоу'-ую особь. £ = 1.. Т - шаг эволюции Рс - популяция на шаге эволюции t

17

• Рс - популяция архивного множества на шаге эволюции Ь

• 17=1 ..V - массив всех переменных, составляющий общее пространство поиска решений. Причем элементы массива одной переменной представляются как самостоятельные переменные V.

• - набор «активных» переменных для к-агента, варьируемых в ходе ГА.

• - набор «неактивных» переменных для Аг-агента, значения которых фиксированы в ходе одного эволюционного цикла ¿-агента.

• Ср - определенное количество генов для кодирования значений каждой переменной

При реализации ¡\tAGAMO каждым из ^-агентов используются следующие ключевые операторы и формулы:

1) Исходное распределение пространства поиска решений между агентами. Бинарная длина пространства поиска решений Ь = 5л С».

Исходно распределять пространство решений по агентам необходимо равномерно и добиваться максимальной однородности переменных внутри одного агента, чтобы длина хромосомы агентов 1к = £ была схожей. Для достижения однородности распределения следует использовать экспертный и статистических анализ, выявляющий степень зависимости переменных друг от друга и объединять наиболее зависимые в единые кластеры.

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

Остальные переменные становятся для агента «неактивными» со случайными фиксированными значениями. Их значения не меняются до момента очередного перераспределения пространства решений между агентами. 2) Расчет фитнес-функцин для г'-ой особи выглядит следующим образом:

^(0 = Д(0 + 0, (8)

где величина Д(£) отражает силу Парето-доминирования, а £>(¿) - коэффициент

18

разряженности.

R(0=ZjePt+Pt,j>iSW. (9)

при этом:

S(Q = \{j \ j е Pt + Pt Л i > ;'}| (10)

- это мощность множества особей j из множества Pt + Pt, которые доминируют по Парето г'-ую особь.

= (И)

при этом о/ - это геометрическая дистанция до fe-oro ближайшего элемента, где величину к следует определять по формуле:

к = Vn +Ñ. (12)

3) Формирование нового архива решений:

Pt+1 = {í|íe Pt + PtAF(i)<i}. (13)

Если число элементов в Pt+1 превышает TV, то необходимо сократить множество Pt+i посредством оператора усечения, при котором в результате |Pt+1| — N итераций исключаются особи с минимальным расстоянием до другой особи.

Иначе еслиРс+1 меньше N, тогда в Pt+1 необходимо добавить N — l^t+il штук лучших доминируемых решений с самой большой функцией приспособленности из Pt + Pt.

4) Оператор селекции реализован в виде бинарного турнирного отбора. Все особи случайным образом разделяются на пары, для каждой из которых устраивается турнир. В турнире побеждает особь с более высоким значением F(i), после чего она допускается к скрещиванию.

5) Оператор скрещивания по результатам экспериментов решено использовать 2-х точечный.

6) Оператор мутации. Вероятность мутации М задается в диапазоне [0.005 ; 0.02].

7) Обновление глобального архива А происходит по средствам копирования в него результирующей популяции Pt+1 после завершения эволюционного цикла

очередного агента. Затем происходит расчет Я" (0 для каждой особи множества А и из него исключаются особей с самым низким значением /?(/)■

8) Перераспределение пространства поиска решений между агентами. Каждые Т эволюционных циклов происходит перераспределение пространства поиска решений между агентами. При этом агент может его инициировать сам, если по итогам 2 последних эволюционных циклов ему не удалось привнести новые решений в Л. В результате агент меняется с первым закончившим свой эволюционный цикл агентом случайным числом от 1 до | % 2 переменных из г>". Соответственно изменяется и V - . Для обновления значений производится селекция одного решения из А, где вероятность выбора прямо пропорциональна F(¿). Значения устанавливаются от выбранного решения. Выбор решения повторяется, если значение ни одной из «неактивных» переменных не было изменено.

Критерий сходимости эволюционного цикла на уровне агента: а = 1 ...А — агенты

Ца ~ номер шага эволюции по агентам

/с'0- количество новых Парето-оптимальных решений за очередной эволюционный шаг по агентам.

Тогда сумма новых Парето-оптимальных решений за три последних эволюционных шага определяется как:

/а = к^+к^+к^ . (14)

Статус активности агента:

г1, если <3<(?а<^и/а>/?

АдешБЬатВак7а) =

(15) О

где Р - определенное минимально-допустимое число новых Парето-оптимальных решений за 3 последних шага эволюции. Критерий сходимости МСАМАО на глобальном уровне:

еа - счетчик эволюционных циклов по агентам (количество итераций получения данных агентом из архива)

Каа ~ количество новых Парето-оптимальных решений за очередной эволюционный цикл по агентам.

20

Тогда сумма новых Парето-оптимальных решений за три последних эволюционных цикла определяется как:

Ра=Ка 2+Ка 1+Ка-

Глобальный счетчик эволюционных циклов:

д = Е2=1 еа

Глобальный статус активности:

GlobalStatus(g)=

= (1, если G<g<G и Y.a=i > £

О

(16)

(17)

(18)

где £ - определенное минимально-допустимое число новых Парето-оптимальных решений за 3 последних эволюционных цикла. Анализ устойчивости и сходимости МАОАМО проводился по итогам 50 запусков на ИМ ПДТ. По итогам них были сделаны выводы об устойчивости и сходимости данного алгоритма, которая была достигнута в 50 реализациях из 50. Ниже представлены графики, демонстрирующие скорость схождение (рис. 3, 4):

Общее число найденных Парето-оптимальных решений

Появление новых Парето-оптимальных решений более высокого ранга

20 40 60 80 100 1 Ne эволюционного цикла

■ — — Самое "быстрое" схождение

-Скорость схождения "в среднем" (50 запусков)

....... Самое "медленное" схождение

20 40 60 80 100 i:

№ эволюционного цикла

.......Самое "медленное" схождение

-Скорость схождения "в среднем" (50 запусков)

— — Самое "быстрое" схождение

Рисунок 3. Общее число найденных Парето-оптимальных решений

Рисунок 4. Появление новых Парето-оптимальных решений более высокого ранга

Принцип, заложенный в МАОАМО, получил программную реализацию,

описанную в разделе 2.3 и в третьей главе диссертации в виде компоненты

программного комплекса.

Для демонстрационного решения рассматриваемой оптимизационной

21

задачи с помощью MAGAMO использовалась распределенная эволюционная сеть, состоящая из 4 агентов. Исходное разбиение пространства поиска решений было произведено экспертным путем с учетом однородности переменных. В результате работы MAGAMO на тестовых данных были найдены 200 Парето-оптимальных решений за 1.5 часа. Каждое решение приводит к комбинации из значений 3 целевых функций. Эти комбинации были экспортированы в специальный программный продукт Pareto Front Viewer, разработанный в ВЦ РАН (ныне ФИЦ ИУ РАН) под руководством Лотова A.B., что позволило графически изобразить фронт Парето (рисунок 5): ось Ох - накопленная EBITDA в руб.; ось Oy - размер активной клиентской базы в чел.; ось Oz - средняя оборачиваемость товарных запасов в днях (цветовая шкала).

Edgeworth-Pareto Haß

Рисунок 5. Визуализация границы Парето в Pareto Front Viewer

Диаграмма позволяет ЛПР увидеть все равнозначные исходы и на основе его дополнительных предпочтений выбрать наиболее рациональный сценарий.

Другим результатом апробации стало сравнение MAGAMO (на 4 процессорах), SPEA2 (на 1 процессоре) и SPEA2 в виде «Островной модели» (на 4 процессорах) — рис. 6, табл. 1. Под «качество» подразумевается среднее кол-во найденных решений за все запуски, под «стабильностью» - стандартное отклонение в массиве из кол-ва решений по итогам каждого запуска. «Качество» и «стабильность» результатов у MAGAMO оказалось значительно лучше. Это объясняется умением MAGAMO распределять пространство поиска решений между агентами, тем самым сокращать длину хромосомы и размер популяции,

22

при сверхбольшой размерности задачи. С использованием «Островной модели» удалось добиться сопоставимых по качеству результатов только при увеличении времени расчетов в 2,5 раза (правый столбец в табл. 1).

Оценка МАОАМО проводилась также на эталонных тестах поиска Парето-оптимальных решений. Результаты тестов показали сопоставимые результаты с результатами других эволюционных методов (7\(50А2, БРЕА2) в случае выпуклой границы Парето без разрывов при небольшом пространстве поиска решений. На большом пространстве поиска решений (при длине хромосомы от 100 генов) эффективность МАОАМО превосходит другие эволюционные методы.

Качество найденных Парето-оптимальных решений

(5РЕА2), число особей = Зп

60

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 № запуска

Рисунок 6. Качество найденных Парето-оптимальных решений

Таблица 1. Сравнение Островной модели и МАСАМО

МАОАМО вРЕА2 (1 процессор) Островная модель, вариант 1 Островная модель, вариант 2

Количество запусков 30 30 30 30

Время расчетов за 1 запуск 60 мин 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%)

(найденных решений)

Стандартное отклонение 11 10 26 10

В третьей главе описан разработанный программный комплекс (далее ПК), включающий в себя следующие компоненты:

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

2. Win-32 приложение, реализующее MAG AMO на стороне Агента.

3. Система имитационного моделирования - PowerSim Studio 8.

4. База данных Microsoft Sql Server 2008 для хранения архивных решений, подключенная к агентам через набор интерфейсов OLE DB.

5. Средство визуализации найденного фронта Парето - Pareto Front Viewer. Найденный набор решений передается из базы данных в Pareto Front Viewer через выгрузку в файл в определенном формате.

6. Программный продукт для ввода дополнительной информации о предпочтениях ЛПР и сужения на ее основе фронта Парето с помощью метода справедливого компромисса. Программный продукт разработан Басковым О.В. под руководством Ногина В.Д. в СПбГУ. Его интеграция с решениями MAGAMO осуществлена через MS Office Excel. Финальный набор рациональных решений также экспортируется в MS Office Excel.

Win-32 приложения были разработаны в Microsoft Visual Studio 2013 на языке программирования С# (фрагмент кода представлен в Приложении диссертации). Архитектура ПК представлена на рисунке 8. Компоненты MAGAMO созданы в рамках диссертационного исследования и агрегированы в едином ПК с прочими компонентами.

Для их интеграции с ИМ из PowerSim Studio 8 в Microsoft Visual Studio 2013 была использована библиотека PowerSim Engine (фрагмент интеграционного кода представлен в разделе 3.3 диссертации). С помощью нее можно управлять запуском ИМ извне, передавая в модель входные переменные и получая значения рассчитанных целевых функций на выходе.

Расчет значений целевых функций имитационной модели в PowerSim Studio

значения переменных значения целевых функций

Многоагентный генетический алгоритм для многокритериальной оптимизации (MAG AMO): 4 агента, реализующих асинхронные эволюционные процессы, взаимодействующие через архив лучших решений.

Агент 1

Агент 2

Агент 3

Агент 4

У

новые знач. неактивных перем. новые решения

Архив лучших решений

Рисунок 7. Архитектура распределенной эволюционной сети

Рисунок 8. Архитектура программного комплекса

ПК реализует следующую функциональность: разработка системно-динамических ИМ, управление расчетами в ИМ, нахождение Парето-оптимальных решений в ИМ, визуализация фронта Парето, ввод дополнительной информации о предпочтениях ЛПР и сужение фронта Парето, вывод конечных

25

результатов - рациональных решений.

В заключении четвертой главы представлены проведенные вычислительные эксперименты. После демонстрации полученных результатов ЛПР, от него поступила дополнительная информация о предпочтениях, которая была учтена при использовании метода справедливых компромиссов для сужения фронта Парето. В результате фронт Парето был сужен с 200 точек, найденных в результате апробации ПК в 3 главе, до 6, из которых ЛПР предстоит окончательно выбрать одну из альтернатив с учетом избранной долгосрочной стратегии. Таким образом, ПК обеспечивает ЛПР эффективным инструментом для поиска рациональных решений в многомерных ИМ сложных организационных структур.

Отдельное исследование было проведено на выявление оптимального значения вероятности мутации. Так, наилучшей скорости схождения удалось добиться при вероятности мутации в диапазоне [0.005; 0.02]. Другое исследование показало, что начальную популяцию следует создавать с как можно более вариативным набором хромосом, что рекомендуется и для обычного ГА.

Предложенный метод поиска Парето-оптимальных решений на основе МАвАМО может быть агрегирован не только с ИМ ПДТ, но и других сложных объектов. Для дальнейшего развития предложенного метода следует изучить ограничения его эффективного использования для объектов другого класса.

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

2. На основе разработанной ИМ синтезирована многокритериальная оптимизационная задача с 3 конкурентными критериями для поиска рациональных решений при управлении ПДТ.

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

4. Разработан новый многоагентный генетический алгоритм (МАСАМО), предназначенный для нахождения подмножества Парето с использованием агрегированной с ним ИМ, отличающейся большим пространством поиска решений. Успешно проведена апробация МАОАМО

для поставленной оптимизационной задачи.

5. Спроектирован программный комплекс, обеспечивающий на основе MAGAMO, агрегированной ИМ и других подсистем эффективную процедуру поиска рациональных решений при управлении ПДТ. Проведены численные эксперименты для оценки разработанного ПК.

6. Произведено внедрение программного комплекса в действующую компанию ООО «РитейлСистем», что, по оценкам руководства, существенно повысило качество управления компанией. Имеется справка о внедрении.

IV. СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Работы, опубликованные автором в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК:

• Хивинцев М. А., Акопов А. С. Распределенная эволюционная сеть для решения многокритериальных оптимизационных задач в системах имитационного моделирования // Бизнес-информатика. М.: НИУ ВШЭ, 2013. 3(25). С. 34-40, 0.5 п.л. (вклад автора - 0.4 п.л.)

• Хивинцев М. А., Акопов А. С. Применение многоагентного генетического алгоритма для поиска оптимальных стратегических и оперативных решений // Бизнес-информатика. М.: НИУ ВШЭ, 2014. 1 (27). С. 23-33, 0.7 п.л. (вклад автора - 0.6 п.л.)

• Хивинцев М. А. Реализация программного комплекса, включающего в себя агрегированную с многоагентным генетическим алгоритмом имитационную модель и другие компоненты, для решения задачи многокритериальной оптимизации // Инновации и инвестиции. -— 2015. — № 5. — С. 185-192, 0.6 п.л.

Работы, опубликованные в других изданиях:

• Хивинцев М.А. Целевое управление компанией с использованием систем имитационного моделирования // Современная наука: актуальные проблемы теории и практики. Сер. Экономика и право. М.: Научные технологии, 2013. 11. С. 46-52, 0.4 п.л.

• Akopov, A.S. Hevencev, М.А. A Multi-agent genetic algorithm for multi-objective optimization // Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. Manchester, England, October 13-16, 2013. P. 1391 -1395, 0.3 п.л. (вклад автора - 0.2 п.л.)

Лицензия ЛР №020832 от «15» октября 1993 г. Подписано в печать «¿¿>> 015 г. Формат 60x84/16

Бумага офсетная. Печать офсетная.

Усл. печ. л._.

Тираж /ОО экз. Заказ № О

Типография издательства НИУ ВШЭ, 125319, г. Москва, Кочновский пр-д., д. 3.