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

1. Введение в алгоритм

В 1991 году М. Дориго из Миланского политехнического института предложил Ant System для решения задач комбинаторной оптимизации, таких как TSP.Имитация поведения муравья при поиске пищиалгоритм оптимизации.

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

Возьмите пример для иллюстрации:Муравьи стартуют из точки А с той же скоростью и пищей в точке D и могут случайным образом выбрать маршрут ABD или ACD. Предполагая, что в начале есть один муравей для каждого маршрута распределения и один шаг в единицу времени, на этом рисунке показана ситуация через 9 единиц времени: муравей, идущий ABD, достигает конечной точки, а муравей, идущий ACD, только достигает точки C, что составляет половину пути.

Ситуация, когда прошло 18 единиц времени: муравьи, идущие по ABD, получили пищу и вернулись в начальную точку A после достижения конечной точки, а муравьи, идущие по ACD, только что пришли в точку D.Если предположить, что феромон, оставленный каждым муравьем, составляет одну единицу, то через 36 единиц времени все муравьи, стартовавшие вместе, разными путями добыли пищу из точки D. В это время маршрут АБД проходит дважды туда и обратно. в каждом месте 4 ед, а маршрут АКД туда-обратно, а феромон в каждом месте 2 ед, и соотношение 2:1 Процесс поиска пищи продолжается, и по указанию феромона колония муравьев отправляет дополнительного муравья (всего 2) по маршруту ABD, в то время как на маршруте ACD остается еще один муравей. Еще через 36 единиц времени накопление феромонных единиц на двух линиях составляет 12 и 4 при соотношении 3:1. Если вышеуказанные правила будут продолжаться, колония муравьев отправит другого муравья по маршруту ABD (всего 3 муравья), в то время как на маршруте ACD все еще есть один муравей. Еще через 36 единиц времени накопление феромонных единиц на двух линиях составляет 24 и 6, при соотношении 4:1. Если это будет продолжаться, согласно указаниям феромона, все муравьи в конечном итоге откажутся от маршрута ACD и выберут маршрут ABD. Это эффект положительной обратной связи, упомянутый ранее.

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

Разница между искусственными муравьиными колониями и естественными муравьиными колониями:

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

2. Муравьиная система

Муравьиная система предлагается с TSP в качестве примера приложения, который является самым основным алгоритмом ACO (алгоритм муравьиной колонии).Нижеследующее описывает рабочий механизм алгоритма оптимизации муравьиной колонии, рассматривая основной процесс AS для решения проблемы TSP как пример. Во-первых, математическая модель задачи TSP выглядит следующим образом:==Алгоритм AS для решения проблемы TSP состоит из двух шагов: построение пути и метод обновления феромонов. ==

2.1 Строительство пути

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

2.2 Обновление феромонов

здесь$C^{nn}$Указывает длину кратчайшего пути.

Чтобы смоделировать муравьев, оставляющих больше феромона на более коротком пути, когда все муравьи достигают конечной точки, необходимо снова обновить концентрацию феромона каждого пути, причем обновление феромона также разделено на две части: Сначала после каждого раунда феромоны на всех путях в проблемном пространстве будут испаряться, а затем все муравьи выделяют феромоны на ребрах, через которые они проходят, в соответствии с их собственной длиной пути. Улетучивание феромонов(испарение) Процесс улетучивания феромонных следов — это процесс, при котором концентрация феромонных следов на каждом соединении автоматически и постепенно ослабевает.Этот процесс улетучивания в основном используется дляИзбегайте слишком быстрой концентрации алгоритма на локальной оптимальной области., что помогает расширить область поиска.усиление феромонов(подкрепление) Процесс улучшения является дополнительной частью алгоритма оптимизации муравьиной колонии, который называется методом автономного обновления (и методом онлайн-обновления). Таким образом, могут быть достигнуты централизованные действия, которые не могут быть выполнены одним муравьем. Метод автономного обновления базового алгоритма муравьиной колонии заключается в равномерном обновлении остаточной информации после того, как все муравьи в муравьиной колонии завершат посещение n городов.

Ниже приведен пример, иллюстрирующий:где матрица D представляет расстояние между городами

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

3. Улучшенный алгоритм муравьиной колонии

Вышеупомянутый базовый алгоритм AS, в TSP не более 75 городов, результаты все еще относительно идеальны, но когда масштаб проблемы расширяется, способность решения проблем AS значительно снижается. Затем предлагаются некоторые улучшенные версии алгоритмов АС.Общим моментом этих улучшенных версий АС является расширение возможностей исследования оптимального решения в процессе поиска муравьев.Разница между ними заключается только в стратегии управления поиском.

3.1 Элитная система муравьев (Elitist Ant System, EAS)

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

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

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

Его феромон обновляется следующим образом:

3.2 Ранговая муравьиная система (Rank-based AS, ASrank)

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

3.3 Муравьиная система MAX-MIN (MMAS)

Сначала рассмотрим несколько вопросов: Вопрос 1: Для крупномасштабных TSP из-за ограниченного числа поисковых муравьев и случайного распределения муравьев во время инициализации не заставит ли это муравьев искать только небольшую часть всех путей и думать, что они нашли лучший путь , все муравьи быстро собираются на один путь, а действительно отличный путь не ищут? Вопрос 2: Когда все муравьи многократно строят один и тот же путь, это означает, что алгоритм вошел в застойное состояние. В настоящее время, независимо от того, является ли это базовым AS, EAS или ASRank, в последующем итеративном процессе больше нет лучшего пути. Хотя эффект сходимости этих алгоритмов "простой и быстрый", мы все знаем правду, что поспешности недостаточно. Есть ли способ использовать итерационный процесс после стагнации алгоритма для дальнейшего поиска, чтобы гарантировать, что решение ближе к реальному? цель найдена?

Для муравьиной системы MAX-MIN 1. Алгоритм модифицирует метод обновления феромонов AS и позволяет только итерационному оптимальному муравью (муравью, который построил кратчайший путь в этой итерации) или оптимальному муравью на данный момент высвобождать феромон; 2. Концентрация феромона на пути ограничена диапазоном [MAX, MIN]; 3. Кроме того, начальное значение феромона задается как верхний предел его значения, что способствует повышению поисковой способности на начальном этапе работы алгоритма. 4. Во избежание застоя поиска феромоны на всех ребрах в проблемном пространстве переинициализируются.

Улучшение 1 заимствовано из системы Essence Ant, но с небольшими отличиями.

• В EAS только лучшим на данный момент муравьям разрешено выделять феромоны, в то время как в MMAS не только лучшие на данный момент муравьи могут выделять феромоны, но и лучшие повторяющиеся муравьи.
• Фактически, итеративное оптимальное правило обновления и оптимальное правило обновления на сегодняшний день взаимозаменяемы в MMAS.
• Относительная частота, с которой используются эти два правила, будет влиять на эффективность поиска алгоритма.
• Пока для обновления феромона используется только оптимальное правило обновления, направление поиска очень сильное, и алгоритм быстро сойдется в окрестности Tb; напротив, если используется только итеративное оптимальное правило обновления, способность исследования алгоритм улучшится, но эффективность поиска упадет.

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

• Муравьи выбирают следующий город на основе эвристической информации и концентрации феромонов.
• Определен диапазон значений эвристической информации.
• Когда концентрация феромона также ограничена в пределах диапазона, вероятность pk(i,j) того, что муравей k, находящийся в городе i, выберет город j в качестве следующего города, также будет ограничена в пределах интервала.

Улучшение 3, так что на начальном этапе алгоритма феромон на всех ребрах в пространстве задач инициализируется оценочным значением τmax, а скорость испарения феромона очень мала (в MMAS скорость испарения обычно устанавливается равной 0,02).

• На начальном этапе алгоритма разница в концентрации феромонов на разных ребрах будет только медленно увеличиваться, поэтому MMAS обладает более сильной поисковой способностью, чем базовые AS, EAS и ASrank на начальном этапе.
• Повышение исследовательской способности алгоритма на начальном этапе помогает муравьям осуществлять поиск в глобальном масштабе с «широким видением», а затем постепенно сужать объем поиска и, наконец, останавливаться на глобальном оптимальном пути.

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

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

4. Система муравьиной колонии

Вышеупомянутые EAS, ASrank и MMAS представляют собой небольшую модификацию AS для повышения производительности. В 1997 году Дориго, основатель алгоритма муравьиной колонии, предложил новый алгоритм ACO с новым механизмом в статье Система муравьиной колонии: подход к совместному обучению к задаче коммивояжера, которая является историей развития алгоритма муравьиной колонии. , еще одна веха.

Между ACS и AS есть три основных отличия: 1. ИспользуйтеПравило псевдослучайного масштабаВыбор следующего узла города устанавливает баланс между развитием текущего пути и изучением нового пути. 2.Правила глобального обновления феромонаФеромон испаряется и высвобождается только на ребрах, которые на данный момент принадлежат наилучшему пути. 3.Добавлено правило локального обновления феромонов, каждый раз, когда муравей проходит через край в пространстве, он удаляет определенное количество феромона на краю, чтобы увеличить вероятность того, что последующие муравьи исследуют другие пути.

5. Применение алгоритма

проблема с рюкзаком

Определение коэффициентов: размер колонии: В общем случае количество муравьев в муравьиной колонии не превышает количества узлов в графе TSP.Условие прекращения: 1 Учитывая максимальное количество внешних циклов, муравьев достаточно для работы; 2 Текущее оптимальное решение одинаково для K последовательных раз и остановок, где K — заданное целое число, указывающее, что алгоритм сошелся и больше не нуждается в продолжении; 3 Правила управления целевым значением, нижняя граница и значение ошибки заданной задачи оптимизации (целевая минимизация), когда разница между целевым значением, полученным алгоритмом, и нижней границей меньше заданного значения ошибки, алгоритм завершает работу.

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

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

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

Прикрепил:Сценарии применения алгоритма муравьиной колонии

Применение алгоритма муравьиной колонии в оптимизации телекоммуникационных маршрутов:

Алгоритм муравьиной колонии достиг определенных результатов в оптимизации маршрутизации телекоммуникаций. И HP, и British Telecom проводили исследования в этой области в середине-конце 1990-х годов и разработали маршрутизацию колоний муравьев (ACR). Каждый муравей, как и в алгоритме оптимизации муравьиной колонии, динамически обновляет записи таблицы маршрутизации в соответствии со своим опытом и производительностью в сети. Если муравей имеет относительно большую задержку из-за заблокированного маршрута в сети, то эта запись в таблице будет значительно расширена. При этом информационное обновление системы осуществляется по механизму улетучивания феромонов, тем самым отбрасывая устаревшую маршрутную информацию. Таким образом, когда текущий оптимальный маршрут перегружен, алгоритм ACR может быстро найти другой альтернативный оптимальный маршрут, тем самым улучшая баланс, нагрузку и коэффициент использования сети. В настоящее время прикладные исследования в этой области все еще разогреваются, поскольку распределенная информационная структура, нестационарные стохастические динамические характеристики сетей связи и асинхронная эволюция состояний сети очень схожи с алгоритмической природой и характеристиками АСО.

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

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

Применение алгоритма муравьиной колонии в задаче комбинаторной оптимизации:

ACO также успешно применяется во многих классических задачах комбинаторной оптимизации, таких как задача квадратичного программирования (QAP), планирование пути робота, планирование рабочего процесса, раскраска графа и другие задачи. После многих лет разработки ACO стал одним из нескольких важных алгоритмов, которые могут эффективно решать практические задачи квадратичного программирования. Появился пример применения АС в задаче планирования рабочих мест, который показывает возможности применения АС в этой области. Использование MAX-MIN AS для решения QAP также дало идеальные результаты, а данные расчетов в эксперименте доказывают, что этот метод лучше, чем более ранний алгоритм SA для решения QAP, а производительность сравнима с производительностью алгоритма поиска табу. Всесторонняя оптимизация производственного процесса и управление специальными материалами реализуются с помощью ACO, а ценность инженерного применения ACO подтверждается сравнением с генетическими алгоритмами, алгоритмами имитации отжига и поиска запретов.

Другие приложения:

Назначение и оптимизация цели атаки оружием

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

рекомендовать: Алгоритм муравьиной колонии Другие отличные блогиblog.CSDN.net/QQ_33829154…