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

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

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

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

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

Поэтому был разработан многоагентный генетический алгоритм для многоцелевой оптимизации (MAGAMOy. Данный алгоритм использует в своей основе принципы известного генетического алгоритма SPEA2, параллельные вычисления для оценки значений фитнес-функций и приспособленности популяции и др. Вместе с тем имеется существенное отличие MAG AM О от известных параллельных ГА, в том числе от так называемой «островной» модели ГА, заключающееся в том, что в MAG AM О имеются интеллектуальные агенты, представляющие собой независимые ГА (исполнимые на отдельных вычислительных кластерах или в потоках), между которыми осуществляется распределение пространства искомых переменных. При этом центральный процесс отвечает за отбор решений наивысшего ранга Парето и формирование границы Парето^[2][3].

Далее будет рассмотрен пример применения MAGAMO для решения многокритериальной оптимизационной задачи в разработанной имитационной модели типового интернет-магазина, относящейся к классу задач сверхбольшой размерности. Для реализации математической модели типового интернет-магазина используется система имитационного моделирования Powersim Studio. Для формирования множества Парето-оптимальных решений применяется генетический алгоритм MAGAMO. Для визуализации границы Парето используется основанный на методах аппроксимации программный продукт Pareto Front Viewer, разработанный в Вычислительном центре РАН.

Многокритериальная оптимизационная задача типового интернет-магазина С использованием методов системной динамики разработана типовая (референтная) имитационная модель для крупного интернет-магазина^[4].

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

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

Следует отметить, что в модели выделяются следующие оперативные управляющие параметры, оптимальные значения которых формируются весьма часто (в частности, еженедельно):

• • уровень цен на товарные категории;
• • комиссия с одного заказа за доставку, но регионам;
• • интенсивность маркетинговой активности.

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

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

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

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

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

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

• • при определении ценовой политики средняя маржинальность продаж каждой товарной категории в каждом периоде должна быть в диапазоне от заданного минимального уровня маржи до максимально допустимого;
• • стоимость доставки в каждом периоде должна составлять от 0 до максимального заданного уровня в процентах от стоимости товара;
• • качество обслуживания должно быть более 0 и меньше либо равно максимально допустимого уровня;
• • доступность товаров на складе по каждой категории должна быть от минимально допустимого уровня до 100%;
• • интенсивность маркетинговой активности в каждом периоде должна быть от 0 до максимально допустимого уровня;
• • сумма коэффициентов маркетинговой активности по регионам, категориям, сегментам потребительских предпочтений равна 1;
• • оборачиваемость запасов в каждом периоде не должна превышать заданный максимальный уровень в днях;
• • доля рынка в количественном выражении в каждом периоде на каждом региональном уровне должна быть не ниже минимального уровня;
• • доля рынка в количественном выражении в каждом периоде по каждой категории должна быть не ниже минимального уровня.

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

Факторами, влияющими на вероятность покупки, являются:

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

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

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

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

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

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

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

На рис. 5.5 представлена диаграмма, демонстрирующая причинно-следственные связи модели.

Введем следующие обозначения.

Индексы, используемые в модели:

• • t = t₀, t₀ +1,…, Т — индекс периода (быстрое время: 1 период = = 1 неделя), Т — горизонт планирования (52 недели «год);
• • г = 1,2,…, / — индекс регионов (городов);
• • j = 1,2,…, J — индекс товарных категорий;
• • k = 1, 2,…, К — индекс сегментов потребительских предпочтений;
• • w = 1, 2,…, W — индекс периода последней покупки (номера недели).

Рис. 5.5. Диаграмма причинно-следственных связей

Экзогенные переменные:

• • Sj (t) — сезонная потребительская активность данного периода по j-м товарным категориям, %;
• • infj (t) — прогнозируемое изменение уровня цен по j-м товарным категориям с учетом инфляции и сезонного регулирования среднерыночных цен для данного периода, %;
• • v_i>k j — исходный объем рынка по i-м регионам, k-u сегментам потребительских предпочтений, j-м товарным категориям, шт.;
• • cbj k _w — исходная клиентская база, сегментированная по 2-м регионам, k-м сегментам потребительских предпочтений, w-м периодам последней покупки, чел.;
• • r_w(t) — степень готовности повторных клиентов, разделенных по периодам последней покупки, к следующей покупке, %;
• • av — среднее число покупок клиентами за период;
• • e_kj — базовая эластичность по цене по k-м сегментам потребительских предпочтений и j-м категориям;
• • /, — длительность исполнения заказа по i-м регионам, дней;
• • а_; — длительность оборачиваемости товарных запасов по j-м категориям, дней;
• • abj — уровень базовой доступности товаров на складе по категориям, %;
• • b — коэффициент нелинейного роста длительности оборачиваемости склада при повышении доступности товаров на складе;
• • (3j — доля возвратов после продажи по j-м категориям товаров, %;
• • и — доля неликвидного в возвратном потоке товаров, %;
• • cpj — исходная средняя себестоимость товаров по j-м категориям, руб.;
• • DCj — расходы на доставку 1 кг в i-й регион, руб/кг;
• • W/(t) — средний вес товара в j-й категории, кг;
• • mb — базовый маркетинговый бюджет, руб.;
• • ос₀, ос_х, ос₂ — коэффициенты, используемые для определения функции операционных расходов на обработку одного заказа (ос₀, ос, — руб.);
• • тс₀, тс_ь тс₂ — коэффициенты, используемые для определения функции управленческих расходов (тс₀, тс_х — руб.);
• • с — уровень комиссии за прием платежей, %.

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

• • q — уровень качества обработки заказов;
• • а: — доступность товаров на складе по товарным категориям,

о/.

/о,.

• • ml у — маркетинговая активность по i-м регионам, %;
• • т2у — маркетинговая активность по j-м товарным категориям, %;
• • m3 — маркетинговая активность по k-м сегментам потребительских предпочтений, %.

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

• • pj (t) — средние цены на j-e товарные категории в период времени t, руб.;
• • dj (t) — соотношение стоимости доставки к стоимости товаров в i-х регионах в период времени ?, %;
• 1
• • m (t) — коэффициент интенсивности маркетинговой активности в период времени t.

Приведем динамику основных показателей модели (эндогенных переменных) в момент времени t.

• Суммарный объем рынка:

где ssj (t) — накопленная потребительская активность:

• Число клиентов в активной клиентской базе:

где Qij (t) обозначает динамику продаж в штуках и будет определено ниже.

• Максимальный потенциал продаж повторным (лояльным) клиентам:

• Вероятность покупки повторными клиентами:

Так, например, фактор влияния цены вычисляется через отклонение установленной итоговой цены на товар (pj (t)) (с учетом цены за доставку от среднерыночной с использованием подхода, основанного на эластичности. При этом коэффициент эластичности (?/>у), в свою очередь, имеет степенную зависимость от отклонения от среднерыночной цены. А динамика среднерыночной цены определяется инфляцией infj (t) и прогнозом уровня конкуренции, определяемым случайным отклонением, заданным через нормальное распределение.

• Динамика объема продаж в штуках:

• Динамика объема продаж в деньгах:

• Динамика себестоимости в денежном выражении:

где Plj (t) — накопленный индекс цен по товарным категориям, который зависит от инфляции, влияния конкуренции и сезонных колебаний среднерыночных цен.

• Динамика общих расходов:

где ОС = ос₀+ос_]е^ОС2'¹ — норма операционных затрат на один заказ; MB (t) = mb-m (t) — маркетинговый бюджет данного периода;

MC (t) = max{тс₀ +тс_{ ln ((Q_/ • 0,9} —зависимость управленческих расходов от объема продаж в штуках, причем они не могут быть более чем на 10% ниже, чем в прошлом периоде.

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

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

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

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

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

Далее можно сформулировать задачу поиска оптимального стратегического и оперативного управления для типового интернет-магазина.

Задача. Необходимо вычислить оптимальные значения набора оперативных и стратегических управляющих параметров {q, a_r т., m2., m3_k, Pj (t), d^t), m (t)}, обеспечивающих максимальные значения прибыли и размера клиентской базы при минимальном времени оборачиваемости запасов:

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

• ограничение на уровень маржинальности:

• ограничение на долю рынка по городам:

ограничение на долю рынка по товарным категориям:

• ограничение на скорость оборачиваемости запасов:

В рассматриваемой модели, содержащей 5 товарных категорий, 6 городов, 3 клиентских сегмента, 52 недели, 3 целевых функции, с учетом ограничений размерность решений достигает примерно 380 000, что характеризует размерность задачи как сверхбольшую.

• [1] Акопов А. С. К вопросу проектирования интеллектуальных систем управления сложными организационными структурами. Ч. 2. Программная реализациясистемы управления инвестиционной деятельностью вертикально-интегрированной нефтяной компании // Проблемы управления. 2011. № 1. С. 47—54.
• [2] Akopov A. S., Hevencev М. A. A multi-agent genetic algorithm for multi-objectiveoptimization // Proceedings of IEEE International Conference on Systems, Man andCy hematics, 2013. Manchester: IEEE, 2013. P. 1391 — 1395.
• [3] Лотов А. В., Поспелова И. И. Многокритериальные задачи принятия решений: учеб, пособие. М.: МАКС Пресс, 2008.
• [4] Хивинцев М. Л. у Акопов Л. С. Применение многоагентного генетическогоалгоритма для поиска оптимальных стратегических и оперативных решений //Бизнес-информатика. 2014. № 1 (27). С. 44—54.