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

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

Так, с помощью методов системной динамики можно описать важнейшие взаимосвязи между финансовыми и материальными потоками крупной компании и исследовать динамику ключевых показателей деятельности (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 = t0, t0 +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-м товарным категориям с учетом инфляции и сезонного регулирования среднерыночных цен для данного периода, %;
  • vi>k j — исходный объем рынка по i-м регионам, k-u сегментам потребительских предпочтений, j-м товарным категориям, шт.;
  • cbj k w исходная клиентская база, сегментированная по 2-м регионам, k-м сегментам потребительских предпочтений, w-м периодам последней покупки, чел.;
  • rw(t) — степень готовности повторных клиентов, разделенных по периодам последней покупки, к следующей покупке, %;
  • av — среднее число покупок клиентами за период;
  • ekj — базовая эластичность по цене по k-м сегментам потребительских предпочтений и j-м категориям;
  • • /, — длительность исполнения заказа по i-м регионам, дней;
  • • а; — длительность оборачиваемости товарных запасов по j-м категориям, дней;
  • abj — уровень базовой доступности товаров на складе по категориям, %;
  • b — коэффициент нелинейного роста длительности оборачиваемости склада при повышении доступности товаров на складе;
  • • (3j — доля возвратов после продажи по j-м категориям товаров, %;
  • и — доля неликвидного в возвратном потоке товаров, %;
  • cpj — исходная средняя себестоимость товаров по j-м категориям, руб.;
  • DCj — расходы на доставку 1 кг в i-й регион, руб/кг;
  • W/(t) — средний вес товара в j-й категории, кг;
  • mb — базовый маркетинговый бюджет, руб.;
  • ос0, осх, ос2 коэффициенты, используемые для определения функции операционных расходов на обработку одного заказа (ос0, ос, - руб.);
  • тс0, тсь тс2 коэффициенты, используемые для определения функции управленческих расходов (тс0, тсх — руб.);
  • с — уровень комиссии за прием платежей, %.

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

  • 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) накопленный индекс цен по товарным категориям, который зависит от инфляции, влияния конкуренции и сезонных колебаний среднерыночных цен.

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

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

MC(t) = max{тс0 +тс{ ln((Q/ • 0,9} —зависимость

управленческих расходов от объема продаж в штуках, причем они не могут быть более чем на 10% ниже, чем в прошлом периоде.

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

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

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

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

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

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

Задача. Необходимо вычислить оптимальные значения набора оперативных и стратегических управляющих параметров {q, ar т., m2., m3k, 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.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >