Метод муравьиной колонии и алгоритм его реализации
Роевой интеллект и его наиболее распространённые методы реализации
Вданной статье мы хотели бы описать роевой интеллект и его различные методы. Задачей анализа всевозможных методов роевого интеллекта является сравнение трёх его наиболее популярных способов реализации. Особый акцент сделан на муравьином, пчелином алгоритмах и методе роя частиц.
Рассмотрены их особенности, сферы применения и математический аппарат, их реализующий. Кроме того, приведено краткое описание некоторых иных, менее популярных, алгоритмов роевого интеллекта.
На основании полученных данных в конце делается вывод о преимуществах перед другими способами реализации, даётся краткое заключение о перспективах развития, а также подведён некий итог разнообразным методам роевого интеллекта.
Ключевые слова: искусственный интеллект, 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
В последние годы алгоритмы, заимствованные у природных систем, широко применяются в различных отраслях науки и техники. Это связано с тем, что природа за многие годы эволюции выработала действенные технологии оптимизации.
Использование таких алгоритмов в решении задач дискретной оптимизации, позволяют находить оптимальные значения параметров объектов и структур. Одной из перспективных технологий является методы, основанные на роевых алгоритмах. Данные метод описывают коллективное поведение децентрализованной самоорганизующейся системы.
Роевые алгоритмы впервые были предложены Херардо Бени и Ван Цзином в 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).
О применении мультиагентных алгоритмов муравьиных колоний для решения задачи структурной оптимизации в энергетических системах
В частности, были предложены задача с ограниченным числом подключаемых потребителей и задача с ограниченным числом объектов энергораспределения. Обе эти задачи относятся к классу дискретных задач оптимизации и являются трудноразрешимыми при использовании классическими методами и алгоритмами.
Поэтому в данной работе предлагается оригинальный подход на основе методов искусственного интеллекта. Подход основан на применении метода имитации
