Метод муравьиной колонии и алгоритм его реализации

Роевой интеллект и его наиболее распространённые методы реализации

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

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

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

Ключевые слова: искусственный интеллект, artificial intelligence, роевой интеллект, swarm intelligence, метод роя частиц, particle swarm optimization, муравьиный алгоритм, ant colony optimization, метод пчелиного улья, artificial bee colony optimization

Обратите внимание

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

Рассмотреть основные алгоритмы роевого интеллекта;

Провести сравнительные анализ методов реализации РИ;

Проверить актуальность развития алгоритмов реализации.

Ещё давным-давно люди стали интересоваться так называемым “роевым поведением” — каким образом птицы летят на юг огромными косяками, не сбиваясь с курса. Как огромные колонии муравьёв работают так слаженно и возводят структуры, по сложности не уступающие современным мегаполисам.

Как пчёлы могут так точно определять и добывать в необходимом для всей колонии питание. Все эти большие группы животных/насекомых можно объединить одним общим словом — рой.

Благо, человечество не стоит на месте и, развиваясь, люди стали изобретать компьютеры, при помощи которых инженеры стали моделировать “роевой интеллект” (РИ) — попытки сделать роботизированные, автоматические и автоматизированные рои.

Хоть далеко не все попытки были успешными, но, тем не менее, они положили начало созданию РИ, заложив к его основанию некоторые фундаментальные правила.

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

Стоит так же отметить, что непосредственно такой термин как “Роевой интеллект” был введён Ван Цзином и Херардо Бени в 1989 году.

Так же модель подразумевает наличие так называемой “многоагентная система”, которая определяется как система, состоящая из множества интеллектуальных агентов — программ, способных самостоятельно на протяжении некого, достаточно длительного промежутка времени, выполнять поставленную задачу.

Важно

Предлагаем взглянуть немного подробнее на разнообразные методы реализации роевого интеллекта на рис. 1:

Рис. 1. Общий график методов роевого интеллекта

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

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

– теория отрицательного отбора;

– теория иммунной сети;

– теория клональной селекции.

Другие алгоритмы наименее всего распространены и редко используются, поэтому мы лишь перечислим некоторые из них:

– метод капель воды, находящий либо наиболее близкие, либо наиболее оптимальные “пути для воды”, подобно рекам;

– алгоритм кукушки — основан на паразитировании, подобно тому, как некоторые виды кукушек откладывали яйца в чужие гнёзда, со временем научившись имитировать цвета чужих яиц;

– метод альтруизма, основанный на том, что каждый агент “заботится” об окружающих, не обращая внимания на себя;

– метод гравитационного поиска — заключён в соблюдении закона всемирного тяготения (все тела притягиваются друг к другу), а именно в поиска наиболее качественных, “тяжёлых”, агентов.

Метод роя частиц (МРЧ)

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

Самая первая компьютерная модель МРЧ была придумана ещё в далёком 1986 Крейгом Рейнольдсом. Он, занимаясь созданием графической модели, придумал довольно простые правила поведения для частиц роя, действуя по которым, рой выглядел крайне похожим на реальный аналог птичьего роя.

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

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

– Все агенты должны избегать пересечения с окружающими их агентам;

– Каждая частица должна корректировать свою скорость в соответствии со скоростями окружающих её частиц;

– Каждый агент должен стараться сохранять достаточно малое расстояние между собой и окружающими его агентами.

Рис. 2. Метод работы МРЧ

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

Совет

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

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

При этом постоянно происходит расчёт искомой функции и поиск наилучшего значения. На рис. 3 приведен пример работы МРЧ.

Рис. 3. Пример работы роя методом МРЧ

Концепцию данного алгоритма описывает формула, согласно которой корректируется модуль и направление скорости агентов.

v⍵v+rnd()(Pbest-x)c1+rnd()(gbest-x)c2, где:

⍵ — коэффициент инерции, определяющий баланс между тем, насколько широко будет “заходить” в исследовании агент и тем, насколько сильно агент будет желать остаться рядом с найденными ранее оптимальными решениями;

Pbest — координаты наилучшей найденной агентом точкой;

gbest — координаты наилучшей роевой точки;

x — текущие координаты точки;

rnd() — случайный коэффициент, принимающий значение от 0 до 1;

c1, c2 — постоянные ускорения.

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

Муравьиный алгоритм

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

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

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

Обратите внимание

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

Кроме того, «феромон» может испаряться, что создает динамичность алгоритму.

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

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

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

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

Рис. 4. Пример нахождения муравьями нового пути при появлении препятствия

Муравьиный алгоритм представим в виде следующего набора команд:

– Пока (не выполнены условия выхода):

Создание агентов;

Поиск подходящего решения;

Изменение феромона;

Вспомогательные действия (не обязательно).

Далее рассмотрим каждый шаг подробнее:

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

– Также указывается первоначальное значение феромона, чтобы значения не были нулевыми.

Поиск подходящего решения:

– Вероятность того, что произойдет переход из вершины i в j, можно определить по формуле:, где τij(t) — уровень феромона, dij– эвристическое расстояние,— константные параметры.

– Если= 0, с большей вероятностью выберется ближайший город;

– Если= 0, выбор будет основываться лишь на феромоне;

Необходим найденный экспериментальным способом компромисс между этими двумя величинами

– Уровень феромона изменяется по формуле:, где

Муравьиные алгоритмы

Аннотация: Данная лекция посвящена методам оптимизации, основанным на поведении муравьиных колоний (Ant Colony Optimization – ACO), которые в последнее время получили широкое распространение.

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

Важно

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

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

Муравьи появились на земле более 100 миллионов лет назад и в настоящее время их популяция составляетособей [1], общий вес которой соизмерим с весом проживающих людей. Большинство муравьев являются социальными насекомыми, которые живут колониями от 30 до миллиона особей.

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

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

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

Слово “stigmergy” образовано из двух греческих слов: “stigma”, означающее знак; “ergon” – работа. Особи воспринимают сигналы (в виде знаков), которые порождают некоторый отклик или действие. Определены две формы стигметрии[2]: сематектоническая (sematectonic) и знаковая(sign-based).

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

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

Остальные муравьи воспринимают “запах” отложенного феромона и стараются следовать по отмеченному пути. Это порождает асинхронную и непрямую схему коммуникации, где муравьи передают информацию друг другу с помощью феромона.

Совет

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

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

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

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

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

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

Рассмотрим эксперименты с препятствиями, которые показаны на рис.12.1,рис.12.2,рис.12.3,рис.12.4 [3].

Рис. 12.1. Движение муравьев без препятствия.
Рис. 12.2. Препятствие на пути между гнездом и пищей.
Рис. 12.3. Начальная фаза движения муравьев с препятствием.
Рис. 12.4. Выбор муравьями кратчайшего пути.

Здесь на первом рисунке показано движение муравьев между гнездом и источником пищи без препятствия. Далее на рис.12.1,рис.12.2,рис.12.3,рис.12.4 показан характер движения в том случае, когда на пути возникло препятствие.

Из рисунков видно, что при появлении препятствия в начальной фазе движения рис.12.

3 муравьи с одинаковой вероятностью выбирают и короткий и длинный путь поскольку концентрация феромона сначала одинакова для обоих вариантов.

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

Не менее известный эксперимент с двумя мостами был проведен с колонией аргентинских муравьев, который представлен на рис.12.5,рис.12.6 [4].Здесь на пути между гнездом и пищей необходимо сделать выбор одного из двух мостов.

Рис. 12.5. Эксперимент с двумя мостами.
Рис. 12.6. Выбор кратчайшего пути.

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

Пустьиобозначают число муравьев на путях A и B соответственно в момент времени. Эмпирически было найдено, что вероятность выбора моста в момент временипроисходит в соответствии со следующей формулой [4]:

( 12.1)

гдехарактеризует степень “привлекательности” неисследованной ветви, иопределяет смещение при использовании феромона в процессе выбора варианта решения. На основе вероятностей, определяемых (12.1), правило выбора муравьем моста можно сформулировать следующим образом. Пусть случайным образом генерируется число U(0,1) в интервале (0,1).

Если, то муравей выбирает путь A, иначе – путь B.

Отметим, что несмотря на то, что муравьиная колония демонстрирует сложное адаптивное поведение, которое позволяет ей решать трудные задачи, поведение одного муравья подчиняется достаточно простым правилам.

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

Обратите внимание

Искусственный муравей алгоритмически моделирует простое поведение реального муравья (точнее его интересующие нас аспекты). Логика поведения искусственного муравья представлена в алгоритме А12.1 [2].

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

Электронный научный журнал Международный студенческий научный вестник ISSN 2409-529X

1Юрлов А.А. 1 Бурмистров А.В. 11 Пензенский государственный технологический университет

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

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

Роевые алгоритмы впервые были предложены Херардо Бени и Ван Цзином в 1989 году [1]. Эти алгоритмы рассматривают самоорганизующуюся многоагентную систему. Агенты обычно довольно просты, но локально взаимодействуя вместе, создают так называемый роевой интеллект.

Примерами таких систем в природе могут служить апроксимационные алгоритмы, относящиеся к классу метаэвристик, такие как:

– муравьиный алгоритм (Ant colony optimization);

– метод роя частиц (Particle swarm optimization);

– пчелиный алгоритм (Bees algorithm) и др.

Перечисленные выше алгоритмы были реализованы для решения различных NP-полных задач.

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

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

Сформулируем задачу в терминах теории графов.

Важно

В неориентированном взвешенном графе G=(X,A), каждому ребру (xi, xj) которого сопоставлен вес L(xi,xj), требуется найти гамильтонов контур наименьшей стоимости, причем контур необязательно должен содержать все ребра графа.

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

Решить поставленную задачу можно разными способами, которые отличаются точностью и скоростью решения. Наибольшую вычислительную трудоемкость имеют эвристические методы. Более приемлемыми являются метаэвристические методы.

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

Рассмотренные выше алгоритмы разрабатывались в рамках научного направления, которое можно назвать «природные вычисления». Исследования в этой области начались в середине 90-х годов XX века, автором идеи является Марко Дориго. В основе этой идеи лежит моделирование поведения колонии муравьев.

Колония муравьев представляет собой систему с очень простыми правилами автономного проведения особей. Однако, несмотря на примитивность поведения каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным.

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

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

Совет

Разработаны модификации муравьиного алгоритма, на основе которых получены более качественные решения для задачи поиска минимального гамильтонова цикла на тестах Эйлона для 50, 75 и 98 вершин. Для теста Эйлона с 30 вершинами оптимальное решение находится за 1-2 секунды [5].

Рассмотрим данный алгоритм на основе примера неориентированного нагруженного графа (рис. 1 а). Матрица весов дуг приведена на рис. 1 б. Матрица интенсивности феромона приведена на рис. 1 в. Требуется отыскать минимальный гамильтонов контур в графе. Начальная вершина x1.

а б в

Рис. 1. Пример поиска кратчайшего пути: а – граф; б – матрица весов дуг; в – матрица интенсивности феромона

Муравьиный алгоритм является итерационным. Каждая итерация состоит из следующих шагов:

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

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

На этом же шаге задается начальный уровень феромона, τij > 0 (рис. 1,в).

Шаг 2. Поиск решения. Находим вероятность перехода из вершины xi в вершину xj определяется по формуле 1.

(1)

где Pij,k – функция вероятности перехода (где i – номер вершины в которой производится выбор, j – вершина, в которую должен направится муравей, k – номер муравья, движущегося по ребрам графа); τij – количество феромона, оставленного муравьями на ребре (хi,хj); ηij – величина, обратная весу (длине) ребра (хi,хj) (ηij =1/Lij, где Lij – расстояние между вершинами хi и хj ); α, β – эмпирические коэффициенты.

При α=0 выбор ближайшего города наиболее вероятен, т. е. алгоритм становится жадным. При β = 0 выбор происходит только на основании феромона, что приводит к субоптимальным решениям. Поэтому необходим компромисс между этими величинами, который находится экспериментально [6]. Принимаем значения α = 1, β = 2. Индекс m в сумме пробегает по всем не пройденным вершинам, смежным сi.

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

После расчета вероятностей перехода из вершины x1 в вершины x2-x6, получаем отрезок (рулетка) с секторами вероятностей (рис. 2).

Рис. 2. Отрезок с секторами вероятностей

«Рулетка» вероятностей, размеченная функцией Pij,k, имеет неравные сектора. Чем ближе вершина и чем больше значение феромона, тем больше сектор. Таким образом, муравей использует и опыт предшественников τij, и здравый смысл ηij, и случайный фактор, т.е. все как в жизни [6].

Случайное число I1 = 75, полученное генератором случайных чисел попадает на 4 сектор. Этот сектор указывает на вершину 5. Далее муравей будет выбирать маршрут из этой вершины. Вершина 1 заносится в список запрещенных вершин (tabu list).

Окончательное построенное дерево кратчайших путей состоит из дуг (рис. 3 е):

(х1,х5), (х5,х3), (х3,х4), (х4,х2), (х2,х6), (х6,х1)

Общая длина маршрута х1-х5-х3-х4-х2-х6-х1 имеет длину 19+19+19+14+8+11= 90.

Обратите внимание

Шаг 3. Обновление феромона. Уровень феромона обновляется в соответствии с формулой (2).

, (2)

где ρ – интенсивность испарения, Lk (t) – цена текущего решения для k-го муравья, Q – параметр, имеющий значение порядка цены оптимального решения, т. е. Q/Lk(t)– феромон, откладываемый k-ым муравьём, использующим ребро (i,j).

Рис. 3. Текущие деревья кратчайшего пути – а, б, в, г, д и окончательное построенное дерево кратчайших путей – е

Для нахождения оптимального решения, в алгоритме муравья предусмотрено «испарение» феромона. Это достигается введением коэффициента ρ в итеративной формуле (2), применяющейся после каждого цикла обхода графа [6].

Заключение

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

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

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

Важно

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

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

Библиографическая ссылка

Юрлов А.А., Бурмистров А.В. РЕШЕНИЕ NP-ПОЛНЫХ ЗАДАЧ НА ОСНОВЕ МЕТОДА АДАПТИВНОГО ПОВЕДЕНИЯ МУРАВЬИНОЙ КОЛОНИИ // Международный студенческий научный вестник. – 2015. – № 3-2.;
URL: http://eduherald.ru/ru/article/view?id=12484 (дата обращения: 26.02.2019).

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

1Еременко Ю.И. 1 Цуканов М.А. 1 Соловьев А.Ю. 11 Старооскольский технологический институт им. А.А. УгароваВ статье излагается подход для структурной оптимизации энергетических систем. Выявлены основные задачи структурной оптимизации энергетических сетей.

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

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

В работе рассматривается его реализация, а также сравнение результатов моделирования для задач различных размерностей с работой генетического алгоритма.алгоритм муравьиных колоний1. Еременко Ю.И., Глущенко А.И. О решении неформализуемых и плохоформализуемых задач методами иммунных алгоритмов // Информационные технологии. – 2011. – № 7. – С. 2–72. Семенов М.Е.

Алгоритмы структурной оптимизации сетей связи / М.Е. Семенов, А.Ю. Соловьев, О.В. Тимченко // Системы управления и информационные технологии. – 2009. – № 3.1 (37). – С. 195–199.3. Штовба С.Д. Муравьиные алгоритмы // Exponenta Pro. Математика в приложениях. – 2003. – № 4. – C. 70–75.4. Меркурьев Г.В. Оперативно-диспетчерское управление энергосистемами. – СПб.

: Издание Центра подготовки кадров энергетики, 2002. – 116 с.5. Colorni A., Dorigo M., Maniezzo V. Distributed optimization by Ant Colonies. Proceedings of the First European Conference on Artifical Life. – Paris, France, 1991. – Р. 134–142.

Сокращение расходов на строительство энергетических систем является важной и актуальной задачей.

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

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

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

Алгоритмы муравьиных колоний для решения задач размещения

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

Совет

Обозначим через I = (1,…,n) множество конечных потребителей, каждое из которых должно быть подключено только к одному объекту энергораспределения; J = (1,…

, m) – множество мест, в которых можно разместить объект энергораспределения; bij ≥ 0, i ∈ I, j ∈ J – стоимость подключения j-го объекта энергораспределения к i-му конечному потребителю.

Стоимость прямо пропорциональна стоимости укладки кабеля, стоимости кабеля и расстоянию между объектом и потребителем; qj > 0, j ∈ J – емкость объекта энергораспределения, выраженная в допустимом количестве подключаемых к нему конечных потребителей; cj ≥ 0, j ∈ J – стоимость установки объекта энергораспределения на j-м месте-кандидате; xij ∈ {0, 1} принимает свои значения в зависимости от того, к какому объекту энергораспределения подключен текущий конечный потребитель; yj ∈ {0, 1} принимает значения в зависимости от того, установлен ли объект энергораспределения в текущем месте.

Задача с ограниченным числом подключаемых конечных потребителей. Эта задача формализуется следующим образом:

(1)

(2)

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

Задача с ограниченным числом объектов энергораспределения. Имея множество мест возможной установки объектов энергораспределения J ∈ {1, …

, m}, из всех возможных множеств, формирующих структуру системы, необходимо выбрать такое множество S ⊆ J, чтобы суммарная функция затрат была минимальной, и все конечные потребители, принадлежащие множеству I ∈ {1, …

, n}, были подключены, но при этом число объектов энергораспределения не должно превышать заданного числа p. Теперь задачу можно сформулировать так:

(3)

Используйте алгоритмы пчелиной колонии для решения нерешаемых задач

Алгоритмы искусственной пчелиной колонии (Simulated Bee Colony, SBC) моделируют поведение медовых пчел и могут быть применены для поиска решений трудных или нерешаемых комбинаторных задач.

В этой статье я объясню, что представляют собой алгоритмы SBC, опишу типы задач, которые можно решать с помощью этих алгоритмов, и представлю полноценный пример, где для решения задачи коммивояжера (Traveling Salesman Problem) используется один из алгоритмов SBC.

Хороший способ прочувствовать алгоритмы SBC и понять суть этой статьи — изучить демонстрационную программу, процесс выполнения которой показан на рис. 1.

Обратите внимание

Эта программа использует алгоритм SBC для анализа набора из 20 городов (помеченных буквами от A до T) и поиска кратчайшего маршрута, по которому можно посетить каждый город ровно один раз.

Данные по городам искусственно сформированы так, чтобы лучший маршрут начинался в городе A, продолжался вплоть до города T по порядку, а его длина составляла 19,0 единиц.

Рис. 1. Демонстрации алгоритма SBC

За кулисами алгоритм SBC создает экземпляр улья со 100 искусственными пчелами, у каждой из которых имеется случайное потенциальное решение. Изначально лучшее из случайных решений дает длину маршрута, равную 95,0 единицам.

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

В конце цикла обработки SBC лучшее найденное решение охватывает 16 городов из 20, а длина маршрута составляет 26,5 — близко к оптимальному решению, но все же не совсем то.

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

Когда вы поймете, как можно применить SBC для решения одной задачи, вы сможете адаптировать приведенный здесь алгоритм SBC для решения собственных задач.

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

https://www.youtube.com/watch?v=Um_Qw4UrgUE

В статье предполагается, что вы владеете навыками программирования минимум на среднем уровне. Пример в этой статье написан на C#, но весь код спроектирован так, чтобы его было легко перенести в другие языки программирования. Думаю, вы найдете эту статью весьма интересной, а умение использовать алгоритмы SBC позволит вам повысить свою квалификацию.

О пчелах

В обычной колонии пчел, например Apis mellifera (медоносная пчела домашняя), предполагается, что пчелы со временем выполняют разные роли. В типичном улье может быть от 5000 до 20 000 особей.

Взрослые особи (в возрасте от 20 до 40 дней), как правило, становятся фуражирами (foragers). Фуражиры обычно выполняют одну из трех ролей: активные фуражиры, фуражиры-разведчики и неактивные фуражиры.

Активные фуражиры летят к источнику нектара, обследуют соседние источники, собирают нектар и возвращаются в улей.

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

В любой момент некоторое количество пчел-фуражиров неактивно. Они ждут неподалеку от входа в улей.

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

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

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

Задача коммивояжера

Задача коммивояжера (Traveling Salesman Problem, TSP) — одна из самых широко изученных задач в области компьютерных наук. Существует множество вариаций TSP, но неформально задача сводится к поиску кратчайшего маршрута, позволяющего посетить каждый город в заданном наборе ровно один раз.

Взглянув на рис. 1 , вы заметите, что демо-программа SBC использует набор из 20 городов, которые произвольно помечены буквами от A до T. Допустимый маршрут состоит из упорядоченного набора меток 20 городов, где каждый город встречается только раз. Следовательно всего имеется 20! = 2 432 902 008 176 640 000 возможных маршрутов.

С каждой парой городов сопоставлено значение расстояния. Простоты ради, если c1 < c2, то расстояние между городами c1 и c2 равно порядковому расстоянию (ordinal distance) между метками городов. Если c1 > c2, расстояние в 1,5 раза больше порядкового расстояния между c1 и c2.

Важно

Поэтому расстояние от A до B равно 1,0 произвольным единицам, расстояние от B до A — 1,5 единицам, расстояние от A до C — 2,0 единицам и т. д. Следовательно, самый оптимальный маршрут, позволяющий посетить каждый город лишь раз, — A -> B-> C -> …

-> T, а кратчайшая длина маршрута — (20–1) * 1,0 = 19,0.

В большинстве вариантов TSP расстояния между городами не подсчитываются искусственно. Вместо этого расстояния скорее всего хранятся в какой-либо структуре данных для поиска.

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

Кроме того, в одних вариациях TSP предполагают, что расстояние от любого города c1 до города c2 идентично таковому от города c2 до c1, а в других подобных предположений не делают.

Кроме как в тривиальных ситуациях, «лобовой» поиск кратчайшего пути не применим. Например, при наличии 20 городов, даже если бы вы могли оценивать миллион маршрутов в секунду, анализ всех 20! возможных путей потребовал бы более 77 000 лет. Именно для таких крайне трудных комбинаторных задач оптимизации отлично подходят алгоритмы SBC.

Эквивалент задачи TSP реализуется в классе CitiesData, показанном на рис. 2. Полный исходный код демонстрационной программы SBC доступен по ссылке code.msdn.microsoft.com/mag0411BeeColony.

Рис. 2. Определение класса CitiesData

Оптимизация методом колонии муравьев. Алгоритм ACOR

Привет, хабра. Хочу поделиться имеющийся у меня информацией по методам оптимизации, а именно по оптимизации методом колонии муравьев. В данной статье представлен алгоритм ACOR (Ant Colony Optimization for continuous domain). В будущем планирую представить еще несколько алгоритмов колонии муравьев. Может быть кому-нибудь пригодиться в университете или по работе.

Постановка задачи

Рассматриваем решение детерминированной задачи оптимизации.

Детерминированная задача оптимального решения формулируется следующим образом

где R^n – n-мерное пространство, D – область допустимых значений вектора варьируемых параметров, S – n-мерный вектор варьируемых параметров, S* – оптимальное значение вектора варьируемых параметров, F(S) – целевая функция (критерий оптимальности), F(S*) – оптимальное значение критерия оптимальности.

Общие сведения

Алгоритм ACOR (Ant Colony Optimization for continuous domain) успешно заменяет дискретный алгоритм ACO без необходимости вносить какие-либо изменения в его схему.

Другие алгоритмы непрерывной оптимизации хоть и основаны на алгоритме ACO (continuous-ACO, API, алгоритм непрерывно взаимодействующих колоний муравьев (CIAC)), но в большинстве своем не повторяют его схему.

Основная идея ACOR – приращение компонентов вектора варьируемых параметров, полученного на зависимом (от феромонов) вероятностном выборе компонентов.

Это достигается путем замены дискретного распределения вероятностей непрерывной функцией, называемой функцией плотности вероятностей (Probability Density Function (PDF)), так же известной как распределение Гаусса.

Алгоритм ACOR использует «ядро» Гаусса (Gaussian Kernel) для взвешенного суммирования нескольких функций плотности вероятности. «Ядро» Гаусса – G^i(S) определяется по формуле

где k – число функций плотности вероятности, i – измерение, ωl – весовая функция, μl^i – вектор средних значений (вектор математических ожиданий), σl^i – вектор дисперсий.

Рисунок 1 – Пример «ядра» Гаусса, состоящего из четырех функций Гаусса

Совет

Модель феромонов ACOR определяется ранжирования архива решений T. На каждой итерации, полученный набор решений добавляется в архив решений T и упорядочивается по критерию оптимальности.

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

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

Схема алгоритма

Для удобного представления решений используют массив решений, представленный в таблице 1.

В таблице решений, решения хранятся согласно их рангу (s1^i– лучшее), ωl – вес каждой функции плотности вероятности, ω1≥ω2≥⋯≥ωn, «ядро» Гаусса для i-го шага – G^i (S), которое вычисляется, используя только i-ый компонент всех k решений в архиве T.

Таблица 1 – Таблица решений

Для получения решения, муравей на каждом шаге i=1,…,n, выбирает значение решения S^i в n-мерной задачи оптимизации.
1) Для k-муравьев случайным образом получают решения s^1,…,s^n.
2) Упорядочивают значения целевой функции, где ранг решения l=1 является лучшим.

3) Вычисляют вес ωl для каждого решения

где q – коэффициент. При фиксированном k, малое значение q (~ 0) означает, что только функция плотности вероятности лучшего решения будет использована для создания нового решения, в то время как при большом значении q, получается более равномерная вероятность.

При большом значении q, уменьшается скорость получения конечного результата. 4) Вычисляют вероятность каждого решения

5) Методом рулетки, случайно выбирают одно решение – Sl, используя рассчитанную вероятность.
6) Полагают, что математическое ожидание μl^i равно sl^i.
7) Вычисляют дисперсию (отклонение от sl^i) в i-ом измерении по формуле

где i∈[1:n], а ξ – коэффициент, который определяет испарение феромонов (ξ>0). Получают решение, используя генератор случайных чисел и распределение вероятностей, полученных с помощью «ядра» Гаусса. 9) Вычисляют значений целевой функции каждого решения.

10) Добавляют полученные решения в архив решений T.

11) Упорядочивают полученные решения.

12) Сохраняют k решения в архиве T.

13) Если лучшее решение удовлетворяет критериям поиска, завершают поиск, иначе переходят на третий шаг.