Введение

Алгоритм оптимизации

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

Обзор

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

Сети интеллектуальных объектов

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

Искусственная феромоновая система

Связь на основе феромонов – один из наиболее эффективных способов коммуникации, широко распространенный в природе. Феромоны используются социальными насекомыми, такими как пчелы, муравьи и термиты, как для взаимодействия между агентами, так и для коммуникации в рое. Благодаря своей реализуемости, искусственные феромоны нашли применение в многороботных и роевых робототехнических системах. Коммуникация на основе феромонов реализовывалась различными способами, включая химические или физические (RFID-метки, свет, звук). Однако эти реализации не смогли полностью воспроизвести все аспекты феромонов, наблюдаемые в природе. Использование проецируемого света было представлено в статье IEEE 2007 года Гарнье, Саймоном и др. в качестве экспериментальной установки для изучения феромоновой коммуникации с микроавтономными роботами. Другое исследование представило систему, в которой феромоны были реализованы посредством горизонтального ЖК-экрана, по которому перемещались роботы, оснащенные направленными вниз световыми датчиками для регистрации узоров под ними.

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

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

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

Система муравьев — первый алгоритм ACO. Этот алгоритм соответствует описанному выше. Он был разработан Дориго.

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

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

Система "максимально-минимально" (MMAS)

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

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

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

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

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

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

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

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

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

Сближение

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

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

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

Публикации (избранные)

М. Дориго, 1992. Оптимизация, обучение и естественные алгоритмы, диссертация на соискание ученой степени доктора философии, Политехнический университет Милана, Италия. М. Дориго, В. Маниеццо и А. Колорни, 1996. "Система муравьев: оптимизация колонией взаимодействующих агентов", IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26 (1): 29–41. М. Дориго и Л. М. Гамбарделла, 1997. "Система муравьиной колонии: подход к кооперативному обучению для решения задачи коммивояжера". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66. М. Дориго, Г. Ди Каро и Л. М. Гамбарделла, 1999. "Муравьиные алгоритмы для дискретной оптимизации". Artificial Life, 5 (2): 137–172. E. Bonabeau, M. Dorigo и G. Theraulaz, 1999. Интеллект роя: от естественных систем к искусственным, Oxford University Press. М. Дориго и Т. Штуцле, 2004. Оптимизация муравьиной колонией, MIT Press. М. Дориго, 2007. "Оптимизация муравьиной колонией". Scholarpedia. C. Blum, 2005. "Оптимизация муравьиной колонией: введение и современные тенденции". Physics of Life Reviews, 2: 353–373. М. Дориго, М. Бираттари и Т. Штуцле, 2006. Оптимизация муравьиной колонией: искусственные муравьи как метод вычислительного интеллекта. TR/IRIDIA/2006-023. Mohd Murtadha Mohamad, "Планирование движения сочлененных роботов с использованием стратегии поиска пищи муравьями", Journal of Information Technology, специальные выпуски по искусственному интеллекту, том 20, № 4, с. 163–181, декабрь 2008. N. Monmarché, F. Guinand & P. Siarry (ред.), "Искусственные муравьи", август 2010, в твердом переплете, 576 с. А. Кажаров, В. Курейчик, 2010. "Алгоритмы оптимизации муравьиной колонии для решения транспортных задач", Journal of Computer and Systems Sciences International, том 49, № 1, с. 30–43. C. M. Pintea, 2014. Advances in Bio-inspired Computing for Combinatorial Optimization Problems, Springer. K. Saleem, N. Fisal, M. A. Baharudin, A. A. Ahmed, S. Hafizah и S. Kamilah, "Протокол самооптимизированной маршрутизации, вдохновленный муравьиной колонией, на основе кросс-слойной архитектуры для беспроводных сенсорных сетей", WSEAS Trans. Commun., vol. 9, no. 10, pp. 669–678, 2010. K. Saleem и N. Fisal, "Улучшенный алгоритм муравьиной колонии для самооптимизированной маршрутизации данных в беспроводных сенсорных сетях", Networks (ICON) 2012 18th IEEE International Conference on, pp. 422–427. Abolmaali S, Roodposhti FR. Оптимизация портфеля с использованием метода муравьиной колонии: тематическое исследование на Тегеранской фондовой бирже. Journal of Accounting. 2018, март; 8(1).