Алгоритмы оптимизации колонии муравьев

редактировать

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

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

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

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

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

Содержание

1 Обзор
- 1.1 Окружающие сети интеллектуальных объектов
- 1.2 Окружающие сети интеллектуальных объектов
- 1.2. Алгоритм и формулы
  - 2.1 Выбор края
  - 2.2 Обновление феромонов
- 3 Общие расширения
  - 3.1 Ant System (AS)
  - 3.2 Ant Colony System (ACS)
  - 3.3 Elitist Ant System
  - 3.4 Макс.-мин. Система муравьев (MMAS)
  - 3.5 Ранговая система муравьев (ASrank)
  - 3.6 Непрерывная ортогональная колония Муравьев (COAC)
  - 3.7 Рекурсивная оптимизация колонии муравьев
- 4 Конвергенция
- 5 Приложения
  - 5.1 Задача планирования
  - 5.2 Задача маршрута транспортных средств
  - 5.3 Задача назначения
  - 5.4 Задача установки
  - 5.5 Проблема выбора размера устройства в физическом проектировании наноэлектроники
  - 5.6 Оптимизация и синтез антенн
  - 5.7 Обработка изображений
  - 5.8 Другие приложения
- 6 Сложность определения
- 7 Алгоритмы стигмергии
- 8 Связанные методы
- 9 История
- 10 Ссылки
- 11 Публикации (выбранные)
- 12 Внешние ссылки
Обзор
В естественном мире муравьи некоторых видов (используемых) блуждают случайным и находят пищу вернуться в свою колонию, прокладывая феромоновые следы. Если другие муравьи найдут такой путь, они, скорее, будут идти по следу, а вместо этого будут следовать по следу, возвращаясь и подкрепляя его, если в конце концов найдут еду (см. Общение муравьев ).

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

Общий результат таков: когда один муравей находит хороший (т. Е. Короткий) путь от колонии к источнику пищи, другие муравьи с большей вероятностью последуют по этому пути, и положительная обратная связь в приводит к тому, что многие муравьи идут одним путем. Идея алгоритма муравьиной колонии состоит в том, чтобы имитировать это поведение с «симулированными муравьями», которые ходят вокруг графа, представляющего проблему, которую необходимо решить.
Окружающие сети интеллектуальных объектов
Требуются новые концепции, поскольку «интеллект» больше не централизован, но его можно найти во всех крохотных объектах. Антропоцентрические концепции, как известно, приводят к созданию ИТ-систем, в которых обработка данных, блоки управления и вычислительные силы централизованы. Эти централизованные подразделения постоянно увеличивают производительность, и их можно сравнить с человеческим мозгом. Модель мозга стала окончательным видением компьютеров. Окружающие сети интеллектуальных объектов и, рано или поздно, новое поколение информационных систем, которые еще более распространены и основаны на нанотехнологиях, в корне изменят эту концепцию. Маленькие устройства, которые можно сравнить с насекомыми, сами по себе не самым высоким интеллектом. Действительно, их интеллект можно отнести к довольно ограниченному. Например, интегрированный высокопроизводительный калькулятор, способ решения любых математических задач, в биочип, имплантированный в человеческое тело или интегрированный в интеллектуальную метку, предназначенную для коммерческих товаров. Однако, когда эти объекты соединяются между собой, они обладают разумом, которые можно сравнить с колонией муравьев или пчел. В случае определенных проблем этот тип интеллекта может быть лучше, чем рассуждения централизованной системы, подобной мозгу.

Природа предлагает несколько примеров того, как крохотные организмы, если они следуют одному и тому же основному правилу, может создать форму коллективного разума на макроскопическом уровне. Колонии социальных насекомых прекрасно иллюстрируют эту модель, которая сильно отличается от человеческих обществ. Эта модель на основе сотрудничества с индивидуальным и непредсказуемым поведением. Они используют различные функции для работы с определенными функциями и данными для этого очень ограниченным объемом информации. Например, колония муравьев представляет множество качеств, которые также можно применить к сети окружающих объектов. Колонии муравьев огром очень высокой способностью приспосабливаться к изменениям в окружающей среде, когда один человек не может выполнить поставленную задачу. Такая гибкость также будет очень полезна для мобильных сетей, которые постоянно развиваются. Пакеты информации, которые передаются от компьютера к цифровому объекту, ведут себя так же, как и муравьи. Они перемещаются по сети и переходят от одного узла к другому с целью как можно быстрее добраться до конечного пункта назначения.
Искусственная феромоновая система
Связь на основе феромонов является одним из наиболее эффективных способов общения, которые широко наблюдаются в природе. Феромон используется социальными насекомыми, такими как пчелы, муравьи и термиты; как для межагентской связи, так и для связи между агентом и роем. Из-за своих возможностей искусственные феромоны были приняты робототехнические системы с роботами и роями. Связь на основе феромонов осуществлялись методы, такие как химические или физические (RFID-метки, свет, звук) способами. Однако эти не смогли воспроизвести все аспекты феромонов, наблюдаемые в природе.

Использование проецируемого света было представлено в статье 2007 IEEE Гарнье, Саймоном и др. в качестве экспериментальной установки для изучения общения на основе феромонов с автономными микроботами. Другое исследование, предложено новый метод связи с феромонами, COSΦ, для роботизированной системы роя, основано на точной и быстрой визуальной локализации. Система позволяет моделировать неограниченное количество феромонов и предоставляет результат их взаимодействия в виде полутонового изображения на горизонтальном ЖК-экране. Чтобы использовать метод коммуникации с феромонами, автономный микробот Colias былнут в роботизированной платформе для роя.
Алгоритм и формулы
В алгоритмах оптимизации муравьиной колонии искусственный муравей представляет собой простую вычислительную платформу. агент, который ищет хорошие решения заданной задачи оптимизации. Чтобы применить муравьиной колонии, задача должна быть оптимизирована в алгоритме поиска кратчайшего пути на взвешенном графе. На первом этапе каждой итерации каждый муравей стохастически строит решение, то есть порядок, в котором должны следовать ребра в графе. На втором этапе сравниваются пути, найденные разными муравьями. Последний шаг состоит в обновлении уровней феромонов на каждом краю.
```
процедура ACO_MetaHeuristic isв то время как not_termination do generateSolutions () daemonActions () pheromoneUpdate () конец процедуры
```
Выбор края
Каждый муравей должен построить решение для перемещения по графу. Чтобы выбрать следующее ребро в своем туре, соответствующее положение каждого ребра, соответствующего уровню феромона. На каждом шаге алгоритма каждый муравей переходит из состояния $x {\ displaystyle x}$ $x$ в состояние $y {\ displaystyle y}$ $y$ , соответствующее более полное промежуточное решение. Таким образом, каждый муравей $k {\ displaystyle k}$ $k$ вычисляет набор $A k (x) {\ displaystyle A_ {k} (x)}$ $A_ {k} (x)$ широко расширений в текущее состояние на каждой итерации и по вероятности переходит к одному из них. Для муравья $k {\ displaystyle k}$ $k$ вероятность $pxyk {\ displaystyle p_ {xy} ^ {k}}$ $p_ {xy} ^ {k}$ переход из состояния $x {\ displaystyle x}$ $x$ для состояния $y {\ displaystyle y}$ $y$ зависит от комбинации двух значений, привлекательность $η xy {\ displaystyle \ eta _ {xy}}$ $\ eta _ {xy}$ ход, вычисленный с помощью некоторой эвристики, указывающий на априорную желательность этого хода и уровень следа $τ xy {\ displaystyle \ tau _ {xy}}$ $\ tau _ {xy}$ хода, что указывает на то, насколько умелым было совершить этот конкретный ход в прошлом. Уровень следа представляет собой апостериорную индикацию желательности этой.

Как правило, $k {\ displaystyle k}$ $k$ -й муравей переходит из состояния $x {\ displaystyle x}$ $x$ в состояние $y {\ displaystyle y}$ $y$ с вероятностью

$pxyk = (τ xy α) (η xy β) ∑ z ∈ allowedx (τ xz α) (η xz β) {\ displaystyle p_ {xy} ^ {k} = {\ frac {(\ tau _ {xy} ^ {\ alpha}) (\ eta _ {xy} ^ {\ beta})} {\ sum _ {z \ in \ mathrm {allowed} _ {x}} (\ tau _ {xz} ^ {\ alpha}) (\ eta _ {xz} ^ {\ beta})}}}$ $p_ {xy} ^ {k} = {\ frac {(\ tau _ {xy} ^ {\ alpha}) (\ eta _ {xy} ^ {\ beta})} {\ sum _ {z \ in \ mathrm {allowed} _ {x}} (\ tau _ {xz} ^ {\ alpha}) (\ eta _ {xz} ^ {\ beta})}}$

где

$τ xy {\ displaystyle \ tau _ {xy }}$ $\ tau _ {xy}$ - количество феромона, отложившееся для перехода из состояния $x {\ displaystyle x}$ $x$ в $y {\ displaystyle y}$ $y$ , 0 ≤ $α {\ displaystyle \ alpha}$ $\ alpha$ - параметр для управления областью $τ xy {\ displaystyle \ tau _ {xy}}$ $\ tau _ {xy}$ , $η xy {\ displaystyle \ eta _ {xy }}$ $\ eta _ {xy}$ - желательность перехода состояния $xy {\ displaystyle xy}$ $xy$ (априорное знание, обычно $1 / dxy {\ displaystyle 1 / d_ {xy}}$ $1 / d _ {{xy}}$ , где $d {\ displaystyle d}$ $d$ - расстояние ce) и $β {\ displaystyle \ beta}$ $\ beta$ ≥ 1 - параметр для управления текущей $η xy {\ displaystyle \ eta _ {xy}}$ $\ eta _ {xy}$ . $τ xz {\ displaystyle \ tau _ {xz}}$ $\ tau _ {xz}$ и $η xz {\ displaystyle \ eta _ {xz}}$ $\ eta _ {xz}$ предусмотреть уровень следа и привлекательность для других переходов между состояниями.
Обновление феромона
Следы обновляются, когда все муравьи завершают свое решение, увеличивая или уменьшая уровень обычно соответствующих движений, которые были частично «хороших» или «плохих» решений соответственно. Пример глобальных правил обновления феромонов:

$τ xy ← (1 - ρ) τ xy + ∑ k Δ τ xyk {\ displaystyle \ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ sum _ {k} \ Delta \ tau _ {xy} ^ {k}}$ $\ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ sum _ {k} \ Delta \ tau _ {xy} ^ {k}$

где $τ xy {\ displaystyle \ tau _ {xy}}$ $\ tau _ {xy}$ - количество феромон, отложившийся при переходе между состояниями $xy {\ displaystyle xy}$ $xy$ , $ρ {\ displaystyle \ rho}$ $\ rho$ - коэффициент испарения феромона, а $Δ τ xyk {\ displaystyle \ Delta \ tau _ {xy} ^ {k}}$ $\ Delta \ tau _ {xy} ^ {k}$ - количество феромона, депонированного $k {\ displaystyle k}$ $k$ муравьем, обычно дается для TSP задача (с движениями, предоставляется дугам графа) на

$Δ τ xyk = {Q / L k, если муравей k использует кривую xy в своем обходе 0, иначе {\ displaystyle \ Delta \ tau _ {xy} ^ {k} = {\ begin {cases} Q / L_ {k} {\ t_dv {if ant использует}} k {\ t_dv {curve}} xy {\ t_dv {в своем обзоре}} \\ 0 {\ t_dv {в случае потери}} \ end { case}}}$ $\ Delta \ tau _ {xy} ^ {k} = {\ begin {cases} Q / L_ {k} {\ t_dv {if ant}} k {\ t_dv {использует кривую }} xy {\ t_dv {в своем обзоре}} \\ 0 {\ t_dv {else}} \ end {cases}}$

где $L k {\ displaystyle L_ {k}}$ $L_ {k}$ - стоимость $k {\ displaystyle k}$ $k$ тур муравья (т типично длина) и $Q {\ displaystyle Q}$ $Q$ - постоянная величина.
Общие расширения
Вот некоторые из наиболее популярных вариантов алгоритмов ACO.
Ant System (AS)
Ant System - это первый алгоритм ACO. Этот алгоритм соответствует представленному выше. Он был разработан Дориго.
Система колоний муравьев (ACS)
В алгоритме системы колоний муравьев исходная система муравьев была изменена в трех аспектах: (i) выбор края смещен в сторону эксплуатация (т.е. предпочтение вероятности выбора самых коротких ребер с большим феромонов); (ii) при построении решений муравьи изменяют уровень феромона на краях, которые они выбирают, применяя локальное правило обновления феромона; (iii) в конце каждой итерации только лучший муравей может обновлять следы, применяемое изменяемое глобальное правило обновления феромонов.
Elitist Ant System
В этом алгоритме глобальная лучшее решение оставляет феромон на своем следе после каждой итерации (даже если этот след не пересматривался) вместе со всеми другими муравьями.
Max-Min Ant System (MMAS)
Этот алгоритм контролирует максимальное и минимальное количество феромонов на каждом следе. Только лучший мировой тур или лучший тур по итерациям феромон к своему следу добавить. Чтобы избежать остановки алгоритма поиска, диапазон возможностей алгоритма на каждом следе ограничен интервалом [τ max, τ min ]. Все ребра инициализируются значением τ max, чтобы ускорить поиск решений. При приближении к стагнации трейлы повторно инициализируются до τ max.
Система Ant на основе ранга (ASrank)
Все решения ранжируются в соответствии с их длиной. Только фиксированное количество лучших муравьев в этой итерации может обновлять свои испытания. Количество отложенных феромона взвешивается для каждого раствора с более короткими путями, чем растворы с более короткими путями.
Непрерывная ортогональная колония муравьев (COAC)
Механизм депонирования феромонов COAC позволяет муравьям совместно и эффективно искать решения. Используя метод ортогонального проектирования, методы исследования в области глобального поиска позволяют быстро и эффективно исследовать выбранные имионы. Метод ортогонального проектирования и метод настройки радиуса также можно распространить на другие алгоритмы оптимизации для предоставления более широких возможностей при решении практических задач.
Рекурсивная оптимизация колонии муравьев
Это рекурсивная форма муравья система, которая разделяет весь поисковый домен на несколько субдоменов и решает задачу на этих субдоменах. Результаты со всех поддоменов сравниваются, и несколько лучших из них продвигаются на следующий уровень. Поддомены, соответствующие выбранным результатам, далее разделяются, и процесс повторяется до тех пор, пока не будет получен результат с желаемой точностью. Этот метод был протестирован на некорректных задачах геофизической инверсии и хорошо работает.
Сходимость
Для некоторых версий алгоритма можно доказать, что он сходится (т. Е. возможность найти глобальный оптимум за конечное время). Первое свидетельство сходимости алгоритма муравьиной колонии было сделано в 2000 году, это был алгоритм графовой системы муравьев, а позднее - алгоритмы ACS и MMAS. Как и в большинстве метаэвристик, очень трудно оценить теоретическую скорость сходимости. Анализ производительности алгоритма непрерывной колонии муравьев по отношению к его различным параметрам (стратегия выбора края, метрика измерения расстояния и скорость испарения феромона) показал, что его производительность и скорость сходимости чувствительны к выбранным значениям параметров, и особенно к значению скорости испарения феромона. В 2004 году Злочин и его коллеги показали, что алгоритмы типа COAC могут быть ассимилированы методами стохастического градиентного спуска, на кросс-энтропийной и оценке алгоритма распределения. Они предложили эту метаэвристику как "".
Приложения
Задача о ранце : муравьи предпочитают меньшую каплю меда более обильному, но менее питательному сахару.
Алгоритмы оптимизации муравьиной колонии были применены ко многим комбинаторным Оптимизация задач, от квадратичного присвоения до сворачивания белка или маршрутизации транспортных средств, а также множество производных методов были адаптированы к динамическим задачам в реальных переменных, стохастическим задачам, множественным целям и параллельные реализации. Он также использовался для выработки почти оптимальных решений задачи коммивояжера. У них есть преимущество перед подходами моделирования отжига и генетическим алгоритмом для решения аналогичных задач, когда граф может динамически изменяться; алгоритм муравьиных колоний может работать непрерывно и адаптироваться к изменениям в реальном времени. Это представляет интерес для сетевой маршрутизации и городских транспортных систем.

Первый алгоритм ACO был назван системой муравьев и был направлен на решение задачи коммивояжера, цель которой - найти кратчайший путь туда и обратно, чтобы связать серию городов. Общий алгоритм относительно прост и основан на наборе муравьев, каждый из которых совершает один из возможных круговых обходов по городам. На каждом этапе муравей выбирает переход из одного города в другой в соответствии с некоторыми правилами:
1. он должен посетить каждый город ровно один раз;
2. у удаленного города меньше шансов быть выбранным (видимость);
3. Чем интенсивнее феромоновый след, проложенный на краю между двумя городами, тем больше вероятность, что этот край будет выбран;
4. Завершив свое путешествие, муравей откладывает больше феромонов на всех края пройдены, если путь короткий;
5. После каждой итерации следы феромонов испаряются.
Проблема планирования
- (SOP)
- Планирование работы магазина проблема (JSP)
- Открытое планирование Проблема (OSP)
- Проблема с перестановочным потоком (PFSP)
- Проблема общего опоздания на одной машине (SMTTP)
- Всего на одной машине проблема взвешенного опоздания (SMTWTP)
- проблема планирования проекта с ограниченными ресурсами (RCPSP)
- проблема планирования группового цеха (GSP)
- проблема общего опоздания на одном компьютере с зависимостью от исходного сету p раз (SMTTPDST)
- Задача планирования доступного технологического процесса (MFSP) с зависящим от установки времени / переключения
Проблема с маршрутизацией транспортных средств
- Проблема с ограниченным маршрутизацией транспортных средств (CVRP)
- Мульти- депо Проблема выбора маршрута транспортных средств (MDVRP)
- Проблема маршрута транспортных средств периода (PVRP)
- Проблема выбора марш рута транспортных средств доставки (SDVRP)
- Проблема стохастического маршрута транспортных средств доставки (SVRP)
- Проблема с маршрутизацией транспортных средств с приемом и доставкой (VRPPD)
- Проблема с маршрутизацией транспортных средств с временными окнами (VRPTW)
- Зависящая от вр емени проблема маршрутизации транспортных средств с временными окнами (TDVRPTW)
- Проблема маршрутизации транспортных средств с временными окнами и барьерами работниками службы (VRPTWMS)
Проблема назначения
- Задача квадратичного назначения (QAP)
- Общая проблема назначения (GAP)
- (FAP)
- (RAP)
Установить проблему
- Установить проблему покрытия (SCP)
- Проблема (SPP)
- Дерево графа с ограничениями веса развития проблема разделения (WCGTPP)
- l-кардинал, взвешенный по дуге Задача дерева (AWlCTP)
- Задача с множеством ранцев (MKP)
- Задача независимого множества (MIS)
Проблема выбора размера устройства в физическом дизайне наноэлектроники
- Оптимизация муравьиной колонии (ACO) Оптимизация схемы считывающего усилителя на основе 45 нм CMOS может привести к оптимальным решениям за очень минимальное время.
- Синтез обратимых схем на основе оптимизации колоний муравьев (ACO) может повысить эффективность.
Оптимизация и синтез антенн
Петлевые вибраторы 10 × 10, синтезированные с помощью алгоритма ACO Петлевые вибраторы 10 × 10, синтезированные с помощью алгоритма ACO
Для оптимизации формы антенн можно использовать алгоритмы муравьиных колоний. В качестве примера можно рассмотреть антенны RFID-меток на основе алгоритмов муравьиной колонии (ACO), петлевых и отключающих вибраторов 10 × 10
Обработка изображений
Алгоритм ACO используется при обработке изображений для края изображения. Обнаружение и связывание краев.
- Обнаружение краев:
График здесь представляет собой двухмерное изображение, и муравьи проходят через один пиксель, вносящий феромон. Перемещение муравьев от одного пикселя к другому направлено локальным изменением значений интенсивности изображения. Это движение вызывает отложение феромона наивысшей плотности по краям.

Следующие шаги включают обнаружение края с помощью ACO:

Шаг 1: Инициализация:. Случайным образом поместите $K {\ displaystyle K}$ $К$ муравьев на изображение $IM 1 M 2 {\ displaystyle I_ {M_ {1} M_ {2}}}$ $I_ {M_ {1} M_ {2}}$ где $K = (M 1 ∗ M 2) 1 2 {\ displaystyle K = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}}}$ $K = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}}$ . Матрица феромонов $τ (i, j) {\ displaystyle \ tau _ {(i, j)}}$ $\ tau _ {(i, j)}$ инициализируется случайным значением. Основная проблема в процессе инициализации - определение эвристической матрицы.

Существуют различные методы определения эвристической матрицы. Для приведенного ниже примера приведенная матрица была приведена на основе статистики: графические данные в позиции пикселя (i, j).

$η (я, j) знак равно 1 Z ∗ V c ∗ I (i, j) {\ displaystyle \ eta _ {(i, j)} = {\ tfrac {1} {Z}} * Vc * I_ {(i, j)}}$ $\ eta _ {( i, j)} = {\ tfrac {1} {Z}} * Vc * I _ {(i, j)}$

Где $I {\ displaystyle I}$ $I$ - изображение размером $M 1 * M 2 {\ displaystyle M_ {1} * M_ {2}}$ $M_ {1} * M_ {2}$ . $Z = ∑ я = 1: M 1 ∑ j = 1: M 2 V c (I i, j) {\ displaystyle Z = \ sum _ {i = 1: M_ {1}} \ sum _ {j = 1: M_ {2}} Vc (I_ {i, j})}$ $Z = \ sum _ {i = 1: M_ { 1}} \ sum _ {j = 1: M_ {2}} Vc (I_ {i, j})$ , который является коэффициентом нормализации

$V c (I i, j) = f (| I ( i - 2, j - 1) - I (i + 2, j + 1) | + | I (i - 2, j + 1) - I (i + 2, j - 1) | + | I (i - 1, j - 2) - I (i + 1, j + 2) | + | I (i - 1, j - 1) - I (i + 1, j + 1) | + | I (i - 1, j) - I (i + 1, j) | + | I (i - 1, j + 1) - I (i - 1, j - 1) | + | I (i - 1, j + 2) - I (i - 1, j - 2) | + | I (i, j - 1) - I (i, j + 1) |) {\ displaystyle {\ begin {align} Vc (I_ {i, j}) = f \ left (\ left \ vert I _ {(i-2, j-1)} - I _ {(i + 2, j + 1)} \ right \ vert + \ left \ vert I _ {(i -2, j +1)} - I _ {(i + 2, j-1)} \ right \ vert \ right. \\ + \ left \ vert I _ {(i-1, j-2)} - I _ {(i + 1, j + 2)} \ right \ vert + \ left \ vert I _ {(i-1, j -1)} - I _ {(i + 1, j + 1)} \ right \ vert \\ + \ left \ vert I _ {(i-1, j)} - I _ {(i + 1, j)} \ right \ vert + \ left \ vert I _ {(i-1, j + 1)} - I _ {(i-1, j-1)} \ right \ vert \\ + \ left. \ left \ vert I_ {(i-1, j + 2)} - I _ {(i-1, j-2)} \ right \ vert + \ left \ vert I _ {(i, j-1)} - I _ {(i, j +1)} \ right \ vert \ right) \ end {align}}}$ ${\ displaystyle {\ begin {align} Vc (I_ {i, j}) = f \ left (\ left \ vert I _ {(i-2, j-1)} - I _ {(i + 2, j + 1)} \ right \ vert + \ left \ vert I _ {(i- 2, j + 1)} - I_ {(я + 2, j-1)} \ right \ vert \ right. \\ + \ left \ vert I _ {(i-1, j-2)} - I _ {(i + 1, j + 2)} \ right \ vert + \ left \ vert I _ {(i- 1, j-1)} - I _ {(i + 1, j + 1)} \ right \ vert \\ + \ left \ vert I _ {(i-1, j)} - I _ {(i + 1, j)} \ right \ vert + \ left \ vert I _ {(i-1, j + 1)} - I _ {(i-1, j-1)} \ right \ vert \\ + \ осталось. \ left \ vert I _ {(i-1, j + 2)} - I _ {(i-1, j-2)} \ right \ vert + \ left \ vert I _ {(i, j-1) } - I _ {(i, j + 1)} \ right \ vert \ right) \ end {align}}}$

$f (⋅) {\ displaystyle f (\ cdot)}$ $f (\ cdot)$ можно вычислить с помощью следующих функций:. $f (x) = λ x для x ≥ 0; (1) {\ Displaystyle е (х) = \ лямбда х, \ квад {\ текст {для х ≥ 0; (1)}}}$ $f (x) = \ lambda x, \ quad {\ text {для x ≥ 0; (1)}}$ . $f (x) = λ x 2 для x ≥ 0; (2) {\ Displaystyle е (х) = \ лямбда х ^ {2}, \ четырехъядерный {\ текст {для х ≥ 0; (2)}}}$ $f (x) = \ lambda x ^ {2}, \ quad {\ text {для x ≥ 0; (2)}}$ . $f (x) = {sin ⁡ (π x 2 λ) для 0 ≤ x ≤ λ; (3) 0, иначе {\ displaystyle f (x) = {\ begin {cases} \ sin ({\ frac {\ pi x} {2 \ lambda}}), {\ text {для 0 ≤ x ≤} } \ lambda {\ text {; (3)}} \\ 0, {\ text {else}} \ end {cases}}}$ $f (x) = {\ begin {case} \ sin ({\ frac {\ pi x} {2 \ lambda}}), {\ text {для 0 ≤ x ≤}} \ lambda {\ text {; (3)}} \\ 0, {\ text {else}} \ end {case}}$ . $f (x) = {π x sin ⁡ (π x 2 λ), для 0 ≤ x ≤ λ ; (4) 0, иначе {\ displaystyle f (x) = {\ begin {cases} \ pi x \ sin ({\ frac {\ pi x} {2 \ lambda}}), {\ text {для 0 ≤ х ≤}} \ лямбда {\ текст {; (4)}} \\ 0, {\ text {else}} \ end {cases}}}$ $f (x) = {\ begin {cases} \ pi x \ sin ({\ frac {\ pi x} {2 \ лямбда}}), {\ text {для 0 ≤ x ≤}} \ lambda {\ text {; (4)}} \\ 0, {\ text {else}} \ end {case}}$ . Параметр $λ {\ displaystyle \ lambda}$ $\ lambda$ в каждой из вышеуказанных функций регулирует соответствующие формы функций.. Шаг 2 Процесс построения:. Движение муравья основано на 4-связанных пикселей или 8-соединенных пикселей. Вероятность, с которой движется муравей, определяется уравнением вероятности $P x, y {\ displaystyle P_ {x, y}}$ $P _ {{x, y}}$ . Шаг 3 и Шаг 5 Процесс обновления:. Матрица феромонов обновляется дважды. на шаге 3 обновляется след муравья (заданный как $τ (x, y) {\ displaystyle \ tau _ {(x, y)}}$ $\ tau _ {(x, y)}$ ), где, как и на шаге 5, испарение скорости следа обновляется, что задается уравнением ниже.. $τ новый ← (1 - ψ) τ старый + ψ τ 0 {\ displaystyle \ tau _ {new} \ leftarrow (1- \ psi) \ tau _ {old} + \ psi \ tau _ { 0}}$ $\ tau _ {new} \ leftarrow (1- \ psi) \ tau _ {old} + \ psi \ tau _ {0}$ , где $ψ {\ displaystyle \ psi}$ $\ psi$ - коэффициент распада феромона $0 < τ < 1 {\displaystyle 0<\tau <1}$ $0 <\ tau <1$

Шаг 7 После принятия решения:. того, как K муравьев переместились на фиксированное расстояние L за N итераций, решение, является ли это ребро или нет, основывается на пороговом значении T на феромонной матрице τ. Пороговое значение для приведенного ниже примера вычисляется на основе метода Оцу..

Край изображения, обнаруженный с помощью ACO:. Изображения генерируются с использованием различных функций, заданных уравнениями (1) - (4).
- Край связывание: ACO также доказала свою эффективность в алгоритмах граничного соединения.
Другие приложения
- Прогноз банкротства
- Классификация
- Ориентированная на соединение сетевая маршрутизация
- Сетевая маршрутизация без соединения
- Интеллектуальный анализ данных
- Дисконтированные денежные потоки при планировании проектов
- Распределенные поиск информации
- Проектирование энергетических и электрических сетей
- Проблема планирования рабочего процесса сети
- Тормозящий пептид дизайн для белковых взаимодействий
- Интеллектуальная система тестирования
- Power разработка электронных схем
- Сворачивание белка
- Идентификация системы
Сложность определения

С алгоритмом ACO, Кратчайший путь на графике между точками A и B основан из нескольких путей. Этот алгоритм является уникальным методом исследования зависимости от авторов и использования этого определения. Вообще говоря, алгоритмы муравьиной колонии рассматривают как метаэвристики метаэвристики, где представлено решение муравьем, движущимся в пространстве поиска. Муравьи отмечают лучшие решения и принимают во внимание предыдущие отметки для оптимизации поиска. Их можно рассматривать как вероятностные многоагентные алгоритмы, использующие распределения вероятностей для перехода между каждой итерацией. В своих версиях комбинаторных задач они используют итеративное построение решений. По мнению некоторых авторов, то, что отличает алгоритмы ACO от других родственников (таких как алгоритмы для оценки распределения или оптимизации роя частиц), заключается именно в их конструктивном аспекте. В результате комбинаторных задачх возможно, что в итоге будет найдено лучшее решение, даже если ни один муравей не эффективным. Таким образом, в примере «Коммивояжер» не обязательно, чтобы муравей действительно смог построить из самых сильных сегментов лучших решений. Однако это определение может быть проблематичным в случае проблем с действующими переменными, когда не существует структуры «соседей». Коллективное поведение социальных насекомых станет источником вдохновения для исследователей. Широкое разнообразие алгоритмов самоорганизации в биологических системах привело к системе «интеллекта роя », которая представляет собой очень общую структуру, в которой вписываются алгоритмы муравьиной колонии.
Алгоритмы стигмергии
На практике существует большое количество алгоритмов, претендующих на звание «муравьиных колоний», не всегда разделяющих общую схему оптимизации каноническими муравьиными колониями. На практике использования обмена информацией между муравьями через среду (принцип называемый «stigmergy ») надлежащим для того, чтобы алгоритм алгоритма муравьинойии был использован. Этот принцип побудил некоторых авторов создать термин «ценность» для методов и поведения, основанных на поиске пищи, сортировка личинок, разделении труда и транспортировке.
Связанные методы
- Генетические алгоритмы (GA) поддерживает набор решений, а не одно. Процесс поиска превосходных решений имитирует процесс эволюции, когда решения объединяются или видоизменяются для изменений пула решений, а решения более низкого качества отбрасываются.
- оценка алгоритма распределения (EDA) - это эволюционный алгоритм, который заменяет традиционные операторы воспроизведения операторами управляемыми моделями. Такие модели извлекаются из совокупности с использованием методов машинного обучения и представляются в виде вероятностных графических моделей, из которых взяты образцы или сгенерированы новые решения с помощью использования кроссовера.
- Имитация отжига (SA) - это связано с этим методом глобальной оптимизации. который пересекает пространство поиска решения, генерируется соседние решения. Всегда принимается превосходящий сосед. Низкий сосед принимается вероятностно на основании разницы в качестве и температурных параметров. Параметр температуры изменяется по мере выполнения алгоритма, чтобы изменить характер поиска.
- Оптимизация реактивного поиска фокусируется на сочетании машинного обучения с оптимизацией путем добавления внутреннего цикла обратной связи для самонастройки свободных параметров алгоритма. характеристикам проблемы, экземпляра и локальной ситуации вокруг текущего решения.
- Поиск табу (TS) аналогичен моделированию отжига в том, что оба пересекают пространство решений, проверяя мутации отдельных решение. В то время как имитация отжига генерирует только одно измененное решение, запретный поиск генерирует множество измененных решений и переходит к решению с наименьшей пригодностью из сгенерированных. Чтобы предотвратить зацикливание и стимулировать большее перемещение по пространству решений, поддерживается список запретов частичных или полных решений. Запрещается переходить к решению, содержащему элементы списка запретов, который обновляется по мере того, как решение пересекает пространство решений.
- Алгоритмы искусственной иммунной системы (ИИС) моделируются на основе иммунной системы позвоночных.
- Оптимизация роя частиц (PSO), метод разведки роя
- Интеллектуальные капли воды (IWD), алгоритм оптимизации на основе роя, основанный на естественных каплях воды, текущих в реках
- Алгоритм гравитационного поиска (GSA), метод интеллекта роя
- Метод кластеризации муравьиных колоний (ACCM), метод, использующий кластерный подход, расширяющий ACO.
- Стохастический диффузионный поиск (SDS), метод вероятностного глобального поиска и оптимизации на основе агентов, который лучше всего подходит для задач, где целевая функция может быть разложена на несколько независимых частичных функций
История
Изобретатели а также. Пионерами в этой области являются Марко Дориго, Лука Мария Гамбарделла.
Хронология алгоритмов COA
Хронология алгоритмов оптимизации муравьиной колонии.
- 1959, Пьер-Поль Грассе изобрел теорию стигмергии, чтобы объяснить поведение строительства гнезд у термитов ;
- 1983 г. Денебург и его коллеги изучили коллективное поведение муравьев ;
- 1988, и у Мойсона Мандерика есть статья о самоорганизации среди муравьев;
- 1989, работа Госса, Арон, Денебург и Пастилс о коллективном поведении аргентинских муравьев, которое даст представление об алгоритмах оптимизации муравьиной колонии;
- 1989 г., реализация модели пищевого поведения Эблингом и его коллегами;
- 1991 г. М. Дориго использует систему муравьев в докторской диссертации (опубликованной в 1992 г.). Технический отчет, извлеченный из диссертации, в соавторстве с В. Маниеццо и А. Колорни был опубликован пятью годами позже;
- 1994 г. Appleby и Steward of British Telecommunications Plc опубликовали первое приложение для телекоммуникаций 91>сетей
- 1995, Гамбарделла и Дориго предложили ant-q, предварительную версию системы муравьиной колонии, в качестве первой версии системы муравьев;.
- 1996 г., Гамбарделла и Дориго предложили система колоний муравьев
- 1996 г., публикация статьи о системе муравьев;
- 1996, Хус и Штюцле изобрели максимальная система муравьев ;
- 1997 г., Дориго и Гамбарделла предложили систему колоний муравьев, гибридизированную с локальным поиском;
- 1997 г. Шундервурд и его коллеги опубликовали улучшенное приложение для телекоммуникационных сетей;
- 1998 г. Дориго запускает первую конференцию, посвященную алгоритам ACO;
- 1998 г., Штюцле предлагает начальные параллельные реализации ;
- 1999 г., Гамбарделла, Тайярд и Агацци предложили macs-vrptw, система множественных колоний первая муравьев, примененная к проблемам маршрутизации транспортных средств с временными окнами,
- 1999, Бонабо, Дориго и Тераулаз издают книгу, посвященную в основном искусственным муравьям
- 2000, специальный выпуск Future Generation Журнал компьютерных систем по алгоритмам муравьев
- 2000, первые приложения для планирование, используйте планирование и удовлетворительного В связи с ограничениями ;
- 2000 г. Гутъар предоставляет первое свидетельство сходимости для алгоритма колоний муравьев
- 2001 г., использование первого алгоритмов сертификата подлинности компаний (Eurobios и Ant Optima );
- 2001 г., Иреди и его коллеги опубликовали первый многоцелевой алгоритм
- 2002 г., первые приложения для построения расписания, байесовские сети;
- 2002 г., Бьянки и ее коллеги предложили первый алгоритм для стохастической проблемы;
- 2004 г., Дориго и Штюцле издают книгу «Оптимизация колоний Муравьев» с MIT Press
- 2004 г., Злохин и Дориго показывают что некоторые алгоритмы эквивалентны стохастического градиенту, первый метод кросс-энтропии и
- 2005 г., приложения к проблемам сворачивания белка.
- 2012 г., Прабхакар и его коллеги публикуют исследования, соответствующие работы отдельных муравьев, общение в тандеме без феромонов, что отражает принципы организации компьютерной сети. связи сравнивалась с Протоколом управления передачей.
- 2016, первое приложение для разработки пептидных последовательностей.
- 2017, успешная интеграция многокритериального метода методов метода PROMETHEE в алгоритме ACO (Алгоритм HUMANT ).
Ссылки
Публикации (выбрано)
- М. Дориго, 1992.
- М. Дориго, В. Маниеццо и А. Колорни, 1996. «Муравьиная система: оптимизация посредством колонии сотрудничающих агентов Оптимизация, обучение и естественные алгоритмы, докторская диссертация.>», IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26 (1): 29–41.
- M. Dorigo LM Gambardella, 1997.« Система колоний муравьев: подход совместного обучения к проблеме коммивояжера ". IEEE Transactions on Evolutionary Computing, 1 (1): 53–66.
- М. Дориго, Г. Ди Каро и Л. М. Гамбарделла, 1999. «Муравьиные алгоритмы для дискретной оптимизации ». Искусственная жизнь, 5 (2): 137–172.
- Э. Бонабо, М. Дориго и Г. Тераулаз, 1999. Интеллект роя: от естественных к искусственным системам, O Издательство Ксфордского университета. ISBN 0-19-513159-2
- M. Дориго и Т. Штютцле, 2004. Оптимизация колонии муравьев, MIT Press. ISBN 0-262-04219-3
- M. Дориго, 2007. «Оптимизация муравьиной колонии». Scholarpedia.
- С. Блюм, 2005 "Оптимизация колонии муравьев: введение и последние тенденции ". Physics of Life Reviews, 2: 353-373
- M. Дориго, М. Бираттари и Т. Штютцле, 2006 Оптимизация колонии муравьев: искусственные муравьи как метод вычислительного интеллекта. TR / IRIDIA / 2006-023
- Мохд Муртадха Мохамад, «Планирование движения шарнирных роботов с использованием стратегии поиска муравьев», Журнал информационных технологий - специальные вопросы искусственного интеллекта, Том 20, № 4, стр. 163– 181, декабрь 2008 г., ISSN 0128-3790.
- N. Monmarché, F. Guinand P. Siarry (ред.), «Искусственные муравьи», август 2010 г., переплет 576 стр. ISBN 978-1-84821-194-0.
- А. Кажаров, В. Курейчик, 2010. «Алгоритмы оптимизации муравьиной колонии для решения задач транспортного », Международный журнал компьютерных и системных наук, Том. 49. № 1. С. 30–43.
- С-М. Пинтеа, 2014 г., Достижения в области биотехнологических вычислений для задач комбинаторной оптимизации, Springer ISBN 978-3-642-40178-7
- К. Салим, Н. Фисал, М. А. Бахарудин, А. А. Ахмед, С. Хафиза и С. Камила, «Самооптимизируемый протокол маршрутизации, вдохновленный колонией муравьев, на основе межуровневой архитектуры для беспроводных сенсорных сетей», WSEAS Trans. Commun., Т. 9, вып. 10. С. 669–678, 2010. ISBN 978-960-474-200-4
- К. Салим и Н. Фисал, «Усовершенствованный алгоритм муравьиной колонии для самооптимизирующейся маршрутизации с гарантированной передачей данных в беспроводных сенсорных сетях», Сети (ICON), 2012 18-я Международная конференция IEEE, стр. 422–427. ISBN 978-1-4673-4523-1
- Abolmaali S, Roodposhti FR. Оптимизация портфеля с использованием метода муравьиных колоний на примере Тегеранской фондовой биржи. Бухгалтерский журнал. 2018 Март; 8 (1).
Внешние ссылки
- Scholarpedia Страница оптимизации муравьиной колонии
- Домашняя страница оптимизации муравьиной колонии
- «Оптимизация муравьиной колонии» - российское научно-исследовательское сообщество
- AntSim - Моделирование Алгоритмы муравьиной колонии
- MIDACO-Solver Программное обеспечение для оптимизации общего назначения на основе оптимизации муравьиной колонии (Matlab, Excel, VBA, C / C ++, R, C #, Java, Fortran и Python)
- Университет Кайзерслаутерна, Германия, AG Wehn: апплет для оптимизации колонии муравьев Визуализация коммивояжера с множеством опций и параметров (Java-апплет)
- Симулятор муравьиной фермы
- Моделирование алгоритма муравья (Java-апплет)
- Системная структура Java Ant Colony