Актуальные проблемы современной науки: тезисы докладов VІI Международной научно-практической конференции (Санкт-Петербург – Астана – Киев – Вена, 28 апреля 2016)
Секция: Экономические науки
ХАСАН АЛИ АЛЬ-АБАБНЕХ
кандидат технических наук
аспирант кафедры международной экономики
Национальный авиационный университет
г. Киев, Украина
ПРИМЕНЕНИЕ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ПРИ ПЛАНИРОВАНИИ ЭФФЕКТИВНОГО МАРШРУТА РЕКЛАМЫ
Главная цель организации маркетинговых коммуникаций - соединить в единое событие, время, место и атмосферу, для того чтобы заинтересованный и потенциальный потребители обратили внимание и оценили предназначенную для них информацию о товаре или услуге.
Процесс производства любого товара, в том числе и разработку рекламного проекта, можно разделить на этапы, проходя через которые изделие превращается из заготовки в товар, пригодный к применению. Одним из немаловажных этапов при разработке рекламного проекта является выбор оптимального маршрута размещения/движения рекламы.
Предложено применение муравьиных алгоритмов для решения задачи планирования маршрута размещения рекламных обращений. Муравьиный алгоритм (ant colony optimization, ACO) – один из эффективных полиномиальных алгоритмов для поиска оптимальных маршрутов на графах. В частности, это наиболее популярный алгоритм поиска приближенного решения задачи коммивояжера [4]. В основе алгоритма лежит поведение муравьиной колонии – маркировка более удачных путей большим количеством феромона. В экономическом контексте очень легко интерпретировать работу с феромоном: чем больше прибыль, тем больше оставляемого феромона. При этом под маршрутом будем понимать совокупность связанных и взаимодействующих друг с другом объектов, которые обеспечивают удовлетворение основных потребностей потребителей.
Использование муравьиного алгоритма имеет следующие преимущества:
– можно гибко регулировать субоптимальность поведения агентов;
– алгоритм обладает свойством real-time: число элементарных операций, выполняемых на каждом шаге для моделирования действий муравьев – одинаково;
– алгоритм моделирования поведения муравьев является хорошо масштабируемым;
– знания каждого муравья об окружающем мире в достаточной степени ограничены, и поэтому алгоритм отвечает свойству неполноты знаний агента.
Интересна особенность метода: тот факт, что адаптация распределения феромона к изменению окружающей среды происходит с некоторой задержкой, соответствует обстановке в реальном мире. Прежде, чем предприниматель адаптирует свое производство к последним изменениям рынка, должно пройти какое-то время.
Муравьиный алгоритм моделирует многоагентную систему. Ее агенты - муравьи. Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – он опустошается.
Пусть муравей находится в узле i, а узел j – это один из узлов, доступных для перехода. Вес ребра, соединяющего узлы i и j - , а интенсивность феромона на нем – . Тогда вероятность перехода муравья из i в j будет равна:
где α и β – это регулируемые параметры, определяющие важность составляющих (веса ребра и уровня феромонов) при выборе пути. Выбор правильного соотношения параметров является предметом исследований, и в общем случае производится на основании опыта.
Эффективность муравьиных алгоритмов сравнима с эффективностью общих метаэвристических методов, а в ряде случаев – и с проблемно-ориентированными методами. Муравьиные алгоритмы хорошо подходят для применения вместе с процедурами локального поиска, позволяя быстро находить начальные точки для них.
Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать анализ способа выбора настраиваемых параметров алгоритмов. В последние годы предлагаются различные способы адаптации параметров алгоритмов «на лету» [6]. Поскольку от выбора параметров сильно зависит поведение муравьиных алгоритмов, именно к этой проблеме обращено наибольшее внимание на данный момент.
Литература:
1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2005.
2. Ходашинський І.А. Идентификация нечетких систем: методы и алгоритмы // Проблемы управления. – 2009. – № 4. – С. 15–23.
3. Ходашинський І.А., Дудін П.А. Оценивание параметров функций принадлежности на основе алгоритма муравьиной колонии / Тр. науч.-техн. конф. «Интелектуальные системы» (IEEE AIS'07). — М.: Физ, 2007. — Т. 1. — С. 88—94.
4. Dorigo M., Stutzle T. Ant Colony Optimization. MIT Press, 2004.
5. Rudomin I., Millan E., Hernandez B. Fragment shaders for agent animation using finite state machines // Simulation Modelling Practice and Theory. V. 13, I.8, November 2005, pp. 741–751.
6. T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo, “Parameter Adaptation in Ant Colony Optimization” // Technical Report, IRIDIA, Université Libre de Bruxelles, 2010
