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

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

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

Использование проецируемого света было представлено в статье IEEE 2007 года Гарнье, Саймоном и др. в качестве экспериментальной установки для изучения коммуникации с микроавтономными роботами на основе феромонов. В другом исследовании была представлена ​​система, в которой феромоны реализовывались через горизонтальный ЖК-экран, по которому двигались роботы, причем роботы имели направленные вниз датчики света для регистрации узоров под ними.

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

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

procedure ACO_MetaHeuristic is
    while not terminated do
        generateSolutions()
        daemonActions()
        pheromoneUpdate()
    repeat
end procedure

Выбор края

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

В целом, $k$муравей покидает штат $x$ заявить $y$ с вероятностью

$p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{z\in \mathrm {allowed} _{y}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}$

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

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

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

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

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

$\Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}$

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

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

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

Муравьиная система (АС)

Муравьиная система — это первый алгоритм ACO. Этот алгоритм соответствует представленному выше. Его разработал Дориго.

Система муравьиных колоний (СКУД)

В алгоритме системы муравьиной колонии исходная муравьиная система была модифицирована в трех аспектах:

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

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

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

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

Этот алгоритм контролирует максимальное и минимальное количество феромонов на каждом следе. Только лучший мировой тур или лучший тур итерации могут добавлять феромон в свой след. Чтобы избежать стагнации алгоритма поиска, диапазон возможных количеств феромонов на каждом следе ограничен интервалом [τ _max ,τ _min ). Все ребра инициализируются значением τ _max, чтобы обеспечить более тщательное исследование решений. Трассы повторно инициализируются до τ _max при приближении к стагнации.

Ранговая система муравьев (ASrank)

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

Параллельная оптимизация муравьев (PACO)

Разработана система муравьиной колонии (СКС) со стратегиями коммуникации. Искусственные муравьи делятся на несколько групп. Семь коммуникаций предложены методы обновления уровня феромонов между группами в ACS и работают над задачей коммивояжера.

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

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

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

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

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

Для некоторых версий алгоритма можно доказать, что он сходится (т. е. способен найти глобальный оптимум за конечное время). Первое свидетельство конвергенции алгоритма муравьиной колонии было сделано в 2000 году для алгоритма муравьиной системы на основе графов, а затем для алгоритмов ACS и MMAS. Как и большинство метаэвристик , очень сложно оценить теоретическую скорость сходимости. Анализ производительности непрерывного алгоритма муравьиной колонии по отношению к его различным параметрам (стратегия выбора ребра, метрика меры расстояния и скорость испарения феромонов) показал, что его производительность и скорость сходимости чувствительны к выбранным значениям параметров, и особенно к значению скорости испарения феромонов. В 2004 году Злочин и его коллеги показал, что алгоритмы типа ACO тесно связаны со стохастическим градиентным спуском , методом перекрестной энтропии и алгоритмом оценки распределения . Они предложили общий термин «поиск на основе модели» для описания этого класса метаэвристики .

Приложения

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

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

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

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

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

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

• Проблема последовательного заказа (СОП)
• Задача планирования цеха (JSP)
• Проблема планирования открытого цеха (OSP)
• Задача перестановочного потока (PFSP)
• Проблема тотального опоздания одной машины (SMTTP)
• Проблема общего взвешенного опоздания для одной машины (SMTWTP)
• Проблема планирования проектов с ограниченными ресурсами (RCPSP)
• Проблема планирования групповых цехов (GSP)
• Проблема общего опоздания на одной машине с временем установки, зависящим от последовательности (SMTTPDST)
• Задача планирования многоэтапных потоков (MFSP) с временем установки/переключения, зависящим от последовательности
• Проблемы планирования последовательности сборки (ASP)

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

• Проблема маршрутизации мощных транспортных средств (CVRP)
• Задача маршрутизации транспортных средств с несколькими депо (MDVRP)
• Периодическая задача маршрутизации транспортных средств (PVRP)
• Проблема маршрутизации разделенного средства доставки (SDVRP)
• Задача стохастической маршрутизации транспортных средств (СВРП)
• Проблема выбора маршрута транспортного средства при получении и доставке (VRPPD)
• Проблема маршрутизации транспортных средств с временными окнами (VRPTW)
• Проблема выбора маршрута транспортного средства в зависимости от времени с временными окнами (TDVRPTW)
• Проблема маршрутизации транспортных средств с временными окнами и несколькими сервисными работниками (VRPTWMS)

Проблема с назначением

• Квадратичная задача о назначениях (QAP)
• Обобщенная задача назначения (GAP)
• Проблема присвоения частот (FAP)
• Проблема распределения избыточности (RAP)

Установить проблему

• Установить проблему с укрытием (SCP)
• Проблема с разделами (SPP)
• Проблема разделения дерева графов с ограничением по весу (WCGTPP)
• Проблема взвешенного по дуге l-мощности дерева (AWlCTP)
• Задача о множественном рюкзаке (МКП)
• Задача максимального независимого множества (MIS)

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

• Оптимизация схемы усилителя чувствительности на основе 45-нм КМОП, основанной на оптимизации муравьиных колоний (ACO), может привести к оптимальным решениям за очень минимальное время.
• Синтез обратимых схем на основе оптимизации муравьиных колоний (ACO) может значительно повысить эффективность.

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

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

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

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

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

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

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

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

Ниже приведены шаги, необходимые для обнаружения границ с использованием ACO:

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

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

$\eta _{(i,j)}={\tfrac {1}{Z}}*Vc*I_{(i,j)},$

где $I$ это изображение размера $M_{1}*M_{2}$,

$Z=\sum _{i=1:M_{1}}\sum _{j=1:M_{2}}Vc(I_{i,j})$

является коэффициентом нормализации, а

${\begin{aligned}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{aligned}}$

$f(\cdot )$ можно рассчитать с помощью следующих функций:

$f(x)=\lambda x,\quad {\text{for x ≥ 0; (1)}}$

$f(x)=\lambda x^{2},\quad {\text{for x ≥ 0; (2)}}$

$f(x)={\begin{cases}\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (3)}}\\0,&{\text{else}}\end{cases}}$

$f(x)={\begin{cases}\pi x\sin({\frac {\pi x}{2\lambda }}),&{\text{for 0 ≤ x ≤}}\lambda {\text{; (4)}}\\0,&{\text{else}}\end{cases}}$

Параметр $\lambda$ в каждой из вышеперечисленных функций настраивает соответствующие формы функций.

Шаг 2: Процесс строительства. Движение муравья основано на 4-связных пикселях или связных 8 - . Вероятность перемещения муравья определяется уравнением вероятности $P_{x,y}$

Шаг 3 и шаг 5: Процесс обновления. Матрица феромонов обновляется дважды. на шаге 3 след муравья (данный $\tau _{(x,y)}$ ) обновляется, где, как и на шаге 5, обновляется скорость испарения следа, которая определяется как:

$\tau _{new}\leftarrow (1-\psi )\tau _{old}+\psi \tau _{0}$,

где $\psi$ коэффициент распада феромона $0<\tau <1$

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

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

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

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

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

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

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

Стигмергические алгоритмы

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

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

Генетические алгоритмы (ГА)

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

Алгоритм оценки распределения (EDA)

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

Имитированный отжиг (SA)

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

Реактивная поисковая оптимизация

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

Табу-поиск (TS)

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

Искусственная иммунная система (ИИС)

Смоделировано на основе иммунной системы позвоночных.

Оптимизация роя частиц (PSO)

Метод роевой разведки .

Интеллектуальные капли воды (IWD)

Алгоритм оптимизации на основе роя, основанный на естественных каплях воды, текущих в реках.

Алгоритм гравитационного поиска (GSA)

Метод роевой разведки .

Метод кластеризации колоний муравьев (ACCM)

Метод, использующий подход кластеризации, расширяющий ACO.

Стохастический диффузионный поиск (SDS)

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

История

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

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

• В 1959 году Пьер-Поль Грассе изобрел теорию стигмергии , чтобы объяснить поведение термитов при строительстве гнезд ;
• В 1983 году Денебур и его коллеги изучали поведение муравьев коллективное ;
• 1988 г., и Мойсон Мандерик написал статью о самоорганизации муравьев;
• 1989 год — работа Госса, Арона, Денебура и Пастилса о коллективном поведении аргентинских муравьев , которая даст представление об алгоритмах оптимизации муравьиных колоний;
• 1989 г., реализация модели пищевого поведения Эблинга и его коллег;
• В 1991 году М. Дориго предложил муравьиную систему в своей докторской диссертации (опубликованной в 1992 году). ). Технический отчет, извлеченный из диссертации, написанный в соавторстве с В. Маньеццо и А. Колорни. был опубликован пять лет спустя;
• В 1994 году Appleby и стюард из British Telecommunication Plc опубликовали первое приложение для телекоммуникационных сетей.
• В 1995 году Гамбарделла и Дориго предложили ant-q , предварительная версия системы муравьиных колоний как первое расширение муравьиной системы;
• 1996 г. Гамбарделла и Дориго предложили систему колоний муравьев.
• 1996 г., публикация статьи о муравьиной системе;
• В 1997 году Дориго и Гамбарделла предложили систему колоний муравьев, гибридизированную с локальным поиском;
• В 1997 году Шундервурд и его коллеги опубликовали улучшенное приложение для телекоммуникационных сетей;
• В 1998 году Дориго запускает первую конференцию, посвященную алгоритмам ACO;
• В 1998 году Штютцле предлагает первоначальные параллельные реализации ;
• В 1999 году Гамбарделла, Тайлард и Агацци предложили macs-vrptw , первую систему с несколькими колониями муравьев, применяемую для решения задач маршрутизации транспортных средств с временными окнами.
• 1999: Бонабо, Дориго и Тераулаз публикуют книгу, посвященную главным образом искусственным муравьям.
• 2000, специальный выпуск журнала Future Generation Computer Systems, посвященный муравьиным алгоритмам.
• В 2000 году Хоос и Штютцле изобретают муравьиную систему «максимум-минимум» ;
• 2000 г., первые приложения к планированию , последовательности планирования и удовлетворению ограничений ;
• 2000 г. Гутжар представляет первые доказательства конвергенции алгоритма колоний муравьев.
• 2001 год — первое использование алгоритмов COA компаниями ( Eurobios и AntOptima );
• В 2001 году Иреди и его коллеги опубликовали первый многокритериальный алгоритм.
• 2002 г., первые приложения в построении расписания, байесовские сети;
• В 2002 году Бьянки и ее коллеги предложили первый алгоритм решения стохастической задачи;
• 2004 г. Дориго и Штютцле публикуют книгу «Оптимизация колоний муравьев» в MIT Press.
• 2004, Злочин и Дориго показывают, что некоторые алгоритмы эквивалентны стохастическому градиентному спуску , методу перекрестной энтропии и алгоритмам оценки распределения.
• 2005 г., первые приложения к проблемам сворачивания белков .
• В 2012 году Прабхакар и его коллеги публикуют исследование, касающееся работы отдельных муравьев, общающихся в тандеме без феромонов, что отражает принципы организации компьютерных сетей. Модель связи сравнивают с протоколом управления передачей .
• 2016 г., первая заявка на разработку пептидной последовательности.
• 2017 год, успешная интеграция многокритериального метода принятия решений PROMETHEE в алгоритм ACO ( алгоритм HUMANT ).

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

• М. Дориго , 1992. Оптимизация, обучение и естественные алгоритмы , докторская диссертация, Миланский политехнический университет, Италия.
• М. Дориго, В. Маньеццо и А. Колорни, 1996. « Муравьиная система: оптимизация колонией взаимодействующих агентов », Транзакции IEEE по системам, человеку и кибернетике – Часть B, 26 (1): 29–41.
• М. Дориго и Л. М. Гамбарделла , 1997. « Система муравьиных колоний: подход к совместному обучению к проблеме коммивояжера ». Транзакции IEEE по эволюционным вычислениям, 1 (1): 53–66.
• М. Дориго, Дж. Ди Каро и Л. М. Гамбарделла, 1999. « Муравьиные алгоритмы для дискретной оптимизации. Архивировано 6 октября 2018 г. в Wayback Machine ». Искусственная жизнь, 5 (2): 137–172.
• Э. Бонабо, М. Дориго и Г. Тераулаз, 1999. Роевой интеллект: от естественных к искусственным системам , Oxford University Press. ISBN   0-19-513159-2
• М. Дориго и Т. Штютцле, 2004. Оптимизация колонии муравьев , MIT Press. ISBN   0-262-04219-3
• М. Дориго, 2007. «Оптимизация муравьиной колонии» . Схоларпедия.
• К. Блюм, 2005 г. « Оптимизация колонии муравьев: введение и последние тенденции ». Обзоры физики жизни, 2: 353-373.
• М. Дориго, М. Бираттари и Т. Штютцле, 2006. Оптимизация муравьиной колонии: искусственные муравьи как метод вычислительного интеллекта . ТР/ИРИДИЯ/2006-023
• Мохд Муртадха Мохамад, «Планирование движения шарнирно-сочлененных роботов с использованием стратегии добывающих муравьев», Журнал информационных технологий - специальные вопросы искусственного интеллекта, Vol. 20, № 4, стр. 163–181, декабрь 2008 г., ISSN   0128-3790 .
• Н. Монмарше, Ф. Гинан и П. Сиарри (редакторы), «Искусственные муравьи», август 2010 г., твердый переплет, 576 стр. ISBN   978-1-84821-194-0 .
• А. Кажаров, В. Курейчик, 2010. « Алгоритмы оптимизации муравьиной колонии для решения транспортных задач », Journal of Computer and Systems Sciences International, Vol. 49. № 1. С. 30–43.
• СМ. Пинтеа, 2014, Достижения в области биовычислений для решения задач комбинаторной оптимизации , Springer ISBN   978-3-642-40178-7
• К. Салим, Н. Фисал, М. А. Бахарудин, А. А. Ахмед, С. Хафиза и С. Камила, «Колония муравьев вдохновила самооптимизируемый протокол маршрутизации, основанный на межуровневой архитектуре для беспроводных сенсорных сетей», WSEAS Trans. Коммун., вып. 9, нет. 10, стр. 669–678, 2010. ISBN   978-960-474-200-4
• К. Салим и Н. Фисал, «Усовершенствованный алгоритм Ant Colony для самооптимизируемой гарантированной маршрутизации данных в беспроводных сенсорных сетях», Networks (ICON), 18-я Международная конференция IEEE, 2012 г., стр. 422–427. ISBN   978-1-4673-4523-1
• Аболмаали С, Рудпошти FR. Оптимизация портфеля с использованием метода муравьиной колонии на примере Тегеранской фондовой биржи. Журнал бухгалтерского учета. Март 2018 г.;8(1).

Внешние ссылки

• Страница оптимизации колонии муравьев в Scholarpedia
• Домашняя страница оптимизации колонии муравьев
• «Оптимизация муравьиных колоний» - Российское научно-исследовательское сообщество
• AntSim — моделирование алгоритмов муравьиной колонии
• MIDACO-Solver Программное обеспечение для оптимизации общего назначения, основанное на оптимизации колоний муравьев (Matlab, Excel, VBA, C/C++, R, C#, Java, Fortran и Python)
• Университет Кайзерслаутерна, Германия, А.Г. Вен: Апплет оптимизации муравьиной колонии Визуализация коммивояжера, решенная с помощью системы ant с многочисленными опциями и параметрами (Java-апплет)
• Моделирование алгоритма муравья (Java-апплет)
• Системная платформа Java Ant Colony
• Реализация алгоритма оптимизации муравьиной колонии (блокнот Python)