Алгоритмы оптимизации муравьиной колонии - Ant colony optimization algorithms

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Август 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

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

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

Обзор

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

Однако со временем феромоновый след начинает испаряться, что снижает его привлекательную силу. Чем больше времени требуется муравью, чтобы пройти по тропе и вернуться обратно, тем больше времени у феромонов для испарения. Короткий путь, для сравнения, проходит чаще, и поэтому плотность феромонов становится выше на более коротких путях, чем на более длинных. Испарение феромона также имеет то преимущество, что позволяет избежать схождения к локально оптимальному решению. Если бы не было испарения вообще, пути, выбранные первыми муравьями, были бы чрезмерно привлекательными для следующих. В этом случае исследование пространства решений будет ограничено. Влияние испарения феромона в реальных системах муравьев неясно, но очень важно в искусственных системах.^[9]

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

Окружающие сети интеллектуальных объектов

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

Природа предлагает несколько примеров того, как крохотные организмы, если все они следуют одному и тому же основному правилу, могут создать форму коллективный разум на макроскопическом уровне. Колонии социальных насекомых прекрасно иллюстрируют эту модель, которая сильно отличается от человеческих обществ. Эта модель основана на сотрудничестве независимых единиц с простым и непредсказуемым поведением.^[11] Они перемещаются по окрестностям для выполнения определенных задач и обладают для этого очень ограниченным объемом информации. Например, колония муравьев представляет множество качеств, которые также можно применить к сети окружающих объектов. Колонии муравьев обладают очень высокой способностью приспосабливаться к изменениям в окружающей среде, а также огромной силой в ситуациях, когда один человек не может выполнить данную задачу. Такая гибкость также была бы очень полезна для мобильных сетей объектов, которые постоянно развиваются. Пакеты информации, которые передаются от компьютера к цифровому объекту, ведут себя так же, как и муравьи. Они перемещаются по сети и переходят от одного узла к другому с целью как можно быстрее добраться до конечного пункта назначения.^[12]

Система искусственных феромонов

Коммуникация на основе феромонов - один из наиболее эффективных способов коммуникации, широко распространенный в природе. Феромон используется социальными насекомыми, такими как пчелы, муравьи и термиты; и для межагентской связи, и для связи между агентом и роем. Из-за своей возможности искусственные феромоны были приняты в робототехнических системах с несколькими роботами и роями. Связь на основе феромонов осуществлялась разными способами, например, химическими ^[13][14][15] или физические (метки RFID,^[16] свет,^{[17][18][19][20]} звук^[21]) способов. Однако эти реализации не смогли воспроизвести все аспекты феромонов, наблюдаемые в природе.

Использование проецируемого света было представлено в докладе IEEE 2007 года Гарнье, Саймоном и др.^[22] в качестве экспериментальной установки для изучения общения на основе феромонов с автономными микроботами. Другое исследование, предложившее новый метод общения с феромонами, COSΦ,^[23] Роботизированная система для роя основана на точной и быстрой визуальной локализации.^[24] Система позволяет моделировать практически неограниченное количество различных феромонов и предоставляет результат их взаимодействия в виде полутонового изображения на горизонтальном ЖК-экране, по которому движутся роботы. Чтобы продемонстрировать метод общения с феромонами, автономный микробот Colias был развернут в качестве роботизированной платформы для роя.^{[нужна цитата ]}

Алгоритм и формулы

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

процедура ACO_MetaHeuristic является    пока not_termination делать        generateSolutions () daemonActions () pheromoneUpdate () повторениеконец процедуры

Выбор края

Каждому муравью нужно построить решение для перемещения по графу. Чтобы выбрать следующее ребро в своем обходе, муравей будет учитывать длину каждого ребра, доступного из его текущего положения, а также соответствующий уровень феромона. На каждом шаге алгоритма каждый муравей выходит из состояния ${ displaystyle x}$ заявить ${ displaystyle y}$, что соответствует более полному промежуточному решению. Таким образом, каждый муравей ${ displaystyle k}$ вычисляет набор ${ displaystyle A_ {k} (x)}$ возможных расширений до текущего состояния на каждой итерации и переходит к одному из них по вероятности. Для муравья ${ displaystyle k}$вероятность ${ displaystyle p_ {xy} ^ {k}}$ переезда из штата ${ displaystyle x}$ заявить ${ displaystyle y}$ зависит от комбинации двух значений, привлекательность ${ displaystyle eta _ {xy}}$ хода, вычисленного с помощью некоторой эвристики, указывающей на априори желательность этого шага и уровень следа ${ displaystyle tau _ {xy}}$ хода, что указывает на то, насколько умело было совершать этот конкретный ход в прошлом. В уровень следа представляет собой апостериорную индикацию желательности этого движения.

В целом ${ displaystyle k}$муравей переезжает из штата ${ displaystyle x}$ заявить ${ displaystyle y}$ с вероятностью

${ displaystyle p_ {xy} ^ {k} = { frac {( tau _ {xy} ^ { alpha}) ( eta _ {xy} ^ { beta})} { sum _ {z в mathrm {разрешено} _ {x}} ( tau _ {xz} ^ { alpha}) ( eta _ {xz} ^ { beta})}}}$

куда

${ displaystyle tau _ {xy}}$ количество феромона, депонированного при переходе из состояния ${ displaystyle x}$ к ${ displaystyle y}$, 0 ≤ ${ displaystyle alpha}$ параметр для контроля влияния ${ displaystyle tau _ {xy}}$, ${ displaystyle eta _ {xy}}$ желательность перехода между состояниями ${ displaystyle xy}$ (априори знания, как правило ${ displaystyle 1 / d_ {xy}}$, куда ${ displaystyle d}$ это расстояние) и ${ displaystyle beta}$ ≥ 1 - параметр для контроля влияния ${ displaystyle eta _ {xy}}$. ${ displaystyle tau _ {xz}}$ и ${ displaystyle eta _ {xz}}$ представляют уровень следа и привлекательность для других возможных переходов между состояниями.

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

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

${ displaystyle tau _ {xy} leftarrow (1- rho) tau _ {xy} + sum _ {k} Delta tau _ {xy} ^ {k}}$

куда ${ displaystyle tau _ {xy}}$ количество феромона, депонированного для перехода в состояние ${ displaystyle xy}$, ${ displaystyle rho}$ это коэффициент испарения феромона и ${ Displaystyle Дельта тау _ {ху} ^ {к}}$ количество феромона, депонированного ${ displaystyle k}$муравей, обычно дается за TSP задача (с ходами, соответствующими дугам графа) на

${ displaystyle Delta tau _ {xy} ^ {k} = { begin {cases} Q / L_ {k} & { mbox {if ant}} k { mbox {использует кривую}} xy { mbox {в своем обзоре}} 0 & { mbox {иначе}} end {cases}}}$

куда ${ displaystyle L_ {k}}$ стоимость ${ displaystyle k}$тур муравья (обычно длительный) и ${ displaystyle Q}$ является константой.

Общие расширения

Вот некоторые из самых популярных вариантов алгоритмов ACO.

Система Муравьев (AS)

Система Ant - это первый алгоритм ACO. Этот алгоритм соответствует представленному выше. Его разработал Дориго.^[25]

Система колоний муравьев (ACS)

В алгоритме Ant Colony System исходная Ant System была изменена в трех аспектах: (i) выбор ребер смещен в сторону эксплуатации (т.е. в пользу вероятности выбора самых коротких ребер с большим количеством феромона); (ii) при построении решения муравьи изменяют уровень феромона на краях, которые они выбирают, применяя локальное правило обновления феромона; (iii) в конце каждой итерации только лучшему муравью разрешается обновлять следы, применяя измененное глобальное правило обновления феромонов.^[26]

Элитная система муравьев

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

Система Макс-Мин Муравей (MMAS)

Этот алгоритм контролирует максимальное и минимальное количество феромонов на каждом следе. Только лучший глобальный тур или лучший тур по итерациям могут добавить феромон к своему следу. Чтобы избежать остановки алгоритма поиска, диапазон возможных количеств феромонов на каждом следе ограничен интервалом [τ_{Максимум}, τ_мин]. Все ребра инициализируются как τ_{Максимум} чтобы заставить более высокое исследование решений. Следы повторно инициализируются на τ_{Максимум} при приближении к застою.^[27]

Ранговая система Ant (ASrank)

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

Непрерывная ортогональная колония муравьев (COAC)

Механизм депонирования феромонов COAC позволяет муравьям совместно и эффективно искать решения. Используя метод ортогонального проектирования, муравьи в возможной области могут быстро и эффективно исследовать выбранные ими регионы с улучшенными возможностями и точностью глобального поиска. Метод ортогонального проектирования и метод регулировки адаптивного радиуса также можно распространить на другие алгоритмы оптимизации для получения более широких преимуществ при решении практических задач.^[28]

Рекурсивная оптимизация колонии муравьев

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

Конвергенция

Для некоторых версий алгоритма можно доказать, что он сходится (т. Е. Способен найти глобальный оптимум за конечное время). Первое свидетельство сходимости алгоритма муравьиной колонии было сделано в 2000 году, это был алгоритм графовой системы муравьев, а позже - алгоритмы ACS и MMAS. Как большинство метаэвристика, теоретическую скорость сходимости очень сложно оценить. Анализ производительности алгоритма непрерывной колонии муравьев по отношению к его различным параметрам (стратегия выбора края, метрика измерения расстояния и скорость испарения феромона) показал, что его производительность и скорость сходимости чувствительны к выбранным значениям параметров, и особенно к значению скорости испарения феромона.^[31] В 2004 году Злочин и его коллеги^[32] показали, что алгоритмы типа COAC могут быть ассимилированы методами стохастический градиентный спуск, на кросс-энтропия и оценка алгоритма распределения. Они предложили эти метаэвристика как "модель, основанная на исследованиях ".

Приложения

Задача о рюкзаке: Муравьи предпочитают меньшую каплю меда более обильному, но менее питательному сахару.

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

Первый алгоритм ACO был назван системой муравьев.^[25] и он был направлен на решение проблемы коммивояжера, в которой цель состоит в том, чтобы найти кратчайший путь туда и обратно, чтобы связать ряд городов. Общий алгоритм относительно прост и основан на наборе муравьев, каждый из которых совершает один из возможных круговых обходов по городам. На каждом этапе муравей выбирает переход из одного города в другой в соответствии с некоторыми правилами:

1. Он должен посетить каждый город ровно один раз;
2. У далекого города меньше шансов быть выбранным (видимость);
3. Чем интенсивнее феромоновый след, проложенный на краю между двумя городами, тем больше вероятность того, что этот край будет выбран;
4. Завершив свое путешествие, муравей откладывает больше феромонов на всех краях, которые он пересек, если путь короткий;
5. После каждой итерации следы феромонов испаряются.

Проблема с расписанием

• Проблема последовательного упорядочивания (СОП) ^[33]
• Планирование работы магазина проблема (JSP)^[34]
• Планирование открытых магазинов проблема (OSP)^[35][36]
• Задача перестановочного потока (PFSP)^[37]
• Проблема полного опоздания одной машины (SMTTP)^[38]
• Проблема общей взвешенной задержки на одной машине (SMTWTP)^[39][40][41]
• Проблема планирования проекта с ограниченными ресурсами (RCPSP)^[42]
• Проблема планирования групповых магазинов (GSP)^[43]
• Проблема полного опоздания на одной машине с временем настройки, зависящим от последовательности (SMTTPDST)^[44]
• Задача планирования многоступенчатого технологического процесса (MFSP) с зависимым от последовательности временем настройки / переключения^[45]

Проблема с маршрутизацией автомобиля

• Емкостная проблема маршрута транспортного средства (CVRP)^[46][47][48]
• Проблема с маршрутизацией нескольких депо (MDVRP)^[49]
• Проблема маршрута транспортного средства (PVRP)^[50]
• Проблема с разделением маршрута доставки (SDVRP)^[51]
• Задача стохастической маршрутизации транспортных средств (SVRP)^[52]
• Проблема с маршрутизацией автомобиля при приеме и доставке (VRPPD)^[53][54]
• Проблема маршрутизации транспортных средств с временными окнами (VRPTW)^{[55][56][57][58]}
• Проблема зависимого от времени маршрута транспортного средства с временными окнами (TDVRPTW)^[59]
• Проблема маршрутизации транспортных средств с временными окнами и несколькими работниками службы (VRPTWMS)

Проблема с присвоением

• Квадратичная задача о назначении (QAP)^[60]
• Обобщенная проблема присваивания (ЗАЗОР)^[61][62]
• Проблема с присвоением частот (ФАП)^[63]
• Проблема распределения избыточности (РЭП)^[64]

Задайте проблему

• Установить проблему с крышкой (SCP)^[65][66]
• Проблема с разделом (SPP)^[67]
• Проблема разделения дерева графа с ограничениями по весу (WCGTPP)^[68]
• Задача о взвешенном по дуге l-мощности дерева (AWlCTP)^[69]
• Множественная задача о ранце (МКП)^[70]
• Задача максимального независимого множества (MIS)^[71]

Проблема размера устройства в физическом дизайне наноэлектроники

• Оптимизация муравьиных колоний (ACO) для схемы сенсорного усилителя на основе 45 нм CMOS может привести к оптимальным решениям за очень минимальное время.^[72]
• Синтез обратимых цепей на основе оптимизации муравьиных колоний (ACO) может значительно повысить эффективность.^[73]

Оптимизация и синтез антенн

Петлевые вибраторы 10 × 10, синтезированные с помощью алгоритма ACO^[74]

Вибраторы Unloopback 10 × 10, синтезированные с помощью алгоритма ACO^[74]

Для оптимизации формы антенн можно использовать алгоритмы муравьиных колоний. В качестве примера можно рассмотреть антенны RFID-меток на основе алгоритмов муравьиной колонии (ACO),^[75] петлевые и откатные вибраторы 10 × 10^[74]

Обработка изображений

Алгоритм ACO используется при обработке изображений для обнаружения краев изображения и связывания краев.^[76][77]

• Обнаружение края:

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

Ниже приведены шаги, необходимые для обнаружения края с помощью ACO:^[78][79][80]

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

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

${ Displaystyle eta _ {(я, j)} = { tfrac {1} {Z}} * Vc * I _ {(i, j)}}$

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

${ 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 верт право) конец {выровнено}}}$

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

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

Край изображения обнаружен с помощью ACO:
Изображения ниже созданы с использованием различных функций, заданных уравнениями (1) - (4).^[81]

• Связь краев:^[82] ACO также доказала свою эффективность в алгоритмах граничного соединения.

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

• Прогноз банкротства^[83]
• Классификация^[84]
• Ориентированный на соединение сетевая маршрутизация^[85]
• Сетевая маршрутизация без установления соединения^[86][87]
• Сбор данных^{[84][88][89][90]}
• Дисконтированные денежные потоки в календарном планировании проекта^[91]
• Распространено поиск информации^[92][93]
• Проектирование энергетических и электрических сетей^[94]
• Проблема планирования рабочего процесса сетки^[95]
• Дизайн ингибирующих пептидов для белок белковые взаимодействия^[96]
• Интеллектуальная система тестирования^[97]
• Мощность конструкция электронной схемы^[98]
• Сворачивание белков^{[99][100][101]}
• Идентификация системы^[102][103]

Сложность определения

В алгоритме ACO кратчайший путь на графике между двумя точками A и B строится из комбинации нескольких путей.^[104] Трудно дать точное определение того, что алгоритм является или не является колонией муравьев, потому что определение может варьироваться в зависимости от авторов и использования. Вообще говоря, алгоритмы муравьиных колоний считаются заселен метаэвристика где каждое решение представлено муравьем, перемещающимся в пространстве поиска.^[105] Муравьи отмечают лучшие решения и принимают во внимание предыдущие отметки для оптимизации поиска. Их можно рассматривать как вероятностный мультиагент алгоритмы с использованием распределение вероятностей чтобы сделать переход между каждым итерация.^[106] В своих версиях комбинаторных задач они используют итеративное построение решений.^[107] По мнению некоторых авторов, то, что отличает алгоритмы ACO от других родственников (таких как алгоритмы для оценки распределения или оптимизации роя частиц), заключается именно в их конструктивном аспекте. В комбинаторных задачах возможно, что в конечном итоге будет найдено лучшее решение, даже если ни один муравей не окажется эффективным. Таким образом, в примере задачи «Коммивояжер» вовсе не обязательно, чтобы муравей действительно путешествовал по кратчайшему маршруту: кратчайший путь можно построить из самых сильных сегментов лучших решений. Однако это определение может быть проблематичным в случае проблем с действительными переменными, когда не существует структуры «соседей». Коллективное поведение социальные насекомые остается источником вдохновения для исследователей. Широкое разнообразие алгоритмов (для оптимизации или без) самоорганизации в биологических системах привело к концепции "рой интеллект ",^[10] что является очень общей структурой, в которую вписываются алгоритмы муравьиных колоний.

Алгоритмы стигмергии

На практике существует большое количество алгоритмов, претендующих на звание «муравьиных колоний», но не всегда разделяющих общую схему оптимизации каноническими муравьиными колониями.^[108] На практике использование обмена информацией между муравьями через окружающую среду (принцип, называемый "стигмергия ") считается достаточным для того, чтобы алгоритм принадлежал к классу алгоритмов муравьиной колонии. Этот принцип побудил некоторых авторов создать термин" ценность "для организации методов и поведения, основанных на поиске пищи, сортировке личинок, разделении труда и кооперации. транспорт.^[109]

Связанные методы

• Генетические алгоритмы (GA) поддерживает набор решений, а не одно. Процесс поиска превосходных решений имитирует эволюцию, когда решения комбинируются или видоизменяются для изменения пула решений, а решения более низкого качества отбрасываются.
• An оценка алгоритма распределения (EDA) - это эволюционный алгоритм который заменяет традиционные операторы воспроизведения операторами, управляемыми моделями. Такие модели изучаются у населения с помощью методов машинного обучения и представляются в виде вероятностных графических моделей, из которых можно выбирать новые решения.^[110][111] или генерируется из управляемого кроссовера.^[112][113]
• Имитация отжига (SA) - это связанный метод глобальной оптимизации, который пересекает пространство поиска, генерируя соседние решения текущего решения. Всегда принимается превосходящий сосед. Низший сосед принимается вероятностно на основании разницы в качестве и температурном параметре. Параметр температуры изменяется по мере выполнения алгоритма, чтобы изменить характер поиска.
• Оптимизация реактивного поиска фокусируется на сочетании машинного обучения с оптимизацией путем добавления внутреннего цикла обратной связи для самонастройки свободных параметров алгоритма в соответствии с характеристиками проблемы, экземпляра и локальной ситуации вокруг текущего решения.
• Табу поиск (TS) аналогичен моделированию отжига в том, что оба они пересекают пространство решений, проверяя мутации отдельного решения. В то время как имитация отжига генерирует только одно измененное решение, запретный поиск генерирует множество измененных решений и переходит к решению с наименьшей пригодностью из сгенерированных. Чтобы предотвратить зацикливание и стимулировать большее перемещение по пространству решений, поддерживается список запретов частичных или полных решений. Запрещается переходить к решению, содержащему элементы списка запретов, который обновляется по мере прохождения решением пространства решений.
• Искусственная иммунная система (AIS) алгоритмы моделируются на основе иммунной системы позвоночных.
• Оптимизация роя частиц (PSO), а рой интеллект метод
• Умные капли воды (IWD), алгоритм оптимизации на основе роя, основанный на естественных каплях воды, текущих в реках.
• Алгоритм гравитационного поиска (GSA), a рой интеллект метод
• Метод кластеризации колоний муравьев (ACCM), метод, использующий кластерный подход, расширяющий ACO.
• Стохастический диффузионный поиск (SDS), агентно-ориентированный вероятностный метод глобального поиска и оптимизации, который лучше всего подходит для задач, в которых целевая функция может быть разложена на несколько независимых частичных функций.

История

Изобретатели Франс Мойсон и Бернард Мандерик. К пионерам в этой области относятся Марко Дориго, Лука Мария Гамбарделла.^[114]

Хронология алгоритмов COA

Хронология алгоритмов оптимизации муравьиных колоний.

• 1959, Пьер-Поль Грассе изобрел теорию стигмергия объяснить поведение постройки гнезда в термиты;^[115]
• 1983 г. Денебур и его коллеги изучали коллективное поведение из муравьи;^[116]
• 1988 год, и у Мойсона Мандерика есть статья о самоорганизация среди муравьев;^[117]
• 1989 г., работа Госса, Арона, Денебура и Пастелса коллективное поведение аргентинских муравьев, который даст представление об алгоритмах оптимизации муравьиной колонии;^[118]
• 1989, внедрение модели пищевого поведения Эблингом и его коллегами;^[119]
• 1991 г. М. Дориго предложил система муравьев в его докторской диссертации (опубликованной в 1992 г.^[6]). Технический отчет, взятый из диссертации, в соавторстве с В. Маниеццо и А. Колорни.^[120] был опубликован пятью годами позже;^[25]
• В 1994 г. Appleby и Steward of British Telecommunications Plc опубликовали первое приложение телекоммуникации сети^[121]
• 1995 г. Гамбарделла и Дориго предложили ant-q, ^[122] предварительная версия системы муравьиной колонии как первая версия системы муравьев; ^[25].
• 1996 г., Гамбарделла и Дориго предложили система колоний муравьев ^[123]
• 1996 г., публикация статьи о муравьиной системе;^[25]
• 2000, Хус и Штютцле изобретают макс-мин система муравьев;^[27]
• 1997 г. Дориго и Гамбарделла предложили гибридную систему колоний муравьев с локальным поиском;^[26]
• В 1997 г. Шундервурд и его коллеги опубликовали улучшенное приложение для телекоммуникации сети;^[124]
• 1998, Дориго запускает первую конференцию, посвященную алгоритмам ACO;^[125]
• 1998 г., Штюцле предлагает начальные параллельные реализации;^[126]
• 1999, Гамбарделла, Тайяр и Агацци предложили macs-vrptw, первая система с несколькими колониями муравьев, применяемая для решения проблем с маршрутизацией транспортных средств с временными окнами, ^[127]
• 1999, Бонабо, Дориго и Тераулаз издают книгу, посвященную главным образом искусственным муравьям.^[128]
• 2000, специальный выпуск журнала Future Generation Computer Systems, посвященный алгоритмам муравьев.^[129]
• 2000 г., первые заявки на планирование, последовательность планирования и удовлетворение ограничений;
• 2000 г., Гутъар представляет первое свидетельство конвергенция для алгоритма муравьиных колоний^[130]
• 2001 г., первое использование алгоритмов COA компаниями (Eurobios и АнтОптима );
• 2001 г. Иреди и его коллеги опубликовали первую многоцелевой алгоритм^[131]
• 2002 г., первые приложения в построении расписания, байесовские сети;
• 2002 г. Бьянки и ее коллеги предложили первый алгоритм для стохастический проблема;^[132]
• 2004, Дориго и Штютцле издают книгу об оптимизации муравьиной колонии в MIT Press. ^[133]
• 2004 г. Злочин и Дориго показывают, что некоторые алгоритмы эквивалентны стохастический градиентный спуск, то кросс-энтропийный метод и алгоритмы оценки распределения^[32]
• 2005 г., первые заявки на сворачивание белка проблемы.
• В 2012 году Прабхакар и его коллеги публикуют исследования, касающиеся работы отдельных муравьев, общающихся в тандеме без феромонов, что отражает принципы организации компьютерной сети. Коммуникационная модель сравнивалась с Протокол управления передачей.^[134]
• 2016, первое приложение к дизайну пептидной последовательности.^[96]
• 2017 г. успешная интеграция многокритериального метода принятия решений PROMETHEE в алгоритм ACO (HUMANT алгоритм ).^[135]

Рекомендации

Публикации (выбрано)

• М. Дориго, 1992. Оптимизация, обучение и естественные алгоритмы, Докторская диссертация, Миланский политехнический университет, Италия.
• М. Дориго, В. Маниеццо и А. Колорни, 1996 г. "Система Ant: оптимизация колонией сотрудничающих агентов ", IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26 (1): 29–41.
• М. Дориго и Л. М. Гамбарделла, 1997. "Система муравьиных колоний: совместный подход к решению проблемы коммивояжера ". IEEE Transactions on Evolutionary Computing, 1 (1): 53–66.
• М. Дориго, Дж. Ди Каро и Л. М. Гамбарделла, 1999 г. "Алгоритмы Ant для дискретной оптимизации ". Искусственная жизнь, 5 (2): 137–172.
• Э. Бонабо, М. Дориго и Г. Тераулаз, 1999. Ройный интеллект: от естественных к искусственным системам, Oxford University Press. ISBN  0-19-513159-2
• М. Дориго и Т. Штютцле, 2004. Оптимизация колонии муравьев, MIT Press. ISBN  0-262-04219-3
• М. Дориго, 2007. «Оптимизация колонии муравьев». Scholarpedia.
• К. Блюм, 2005 г. "Оптимизация колонии муравьев: введение и последние тенденции ". Physics of Life Reviews, 2: 353-373.
• М. Дориго, М. Бираттари и Т. Штютцле, 2006 г. Оптимизация колонии муравьев: искусственные муравьи как метод вычислительного интеллекта. TR / IRIDIA / 2006-023
• Мохд Муртадха Мохамад, «Планирование движения шарнирных роботов с использованием стратегии поиска муравьев», Журнал информационных технологий - Специальные вопросы искусственного интеллекта, том 20, № 4, стр. 163–181, декабрь 2008 г., ISSN  0128-3790.
• Н. Монмарше, Ф. Гинанд и П. Сиарри (редакторы), «Искусственные муравьи», август 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
• К. Салим и Н. Физал, «Усовершенствованный алгоритм муравьиной колонии для самооптимизированной маршрутизации с гарантированной передачей данных в беспроводных сенсорных сетях», Networks (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: апплет для оптимизации колоний муравьев Визуализация коммивояжера, решаемая системой ant с множеством опций и параметров (Java-апплет)
• Симулятор Муравьиной Фермы
• Моделирование алгоритма Ant (Java-апплет)
• Системная платформа Java Ant Colony