Ant системы описывают поведения муравьев, как они ведут себя при поиске пищи. Было отмечено, что муравьи прокладывают тропы феромонов, и таким образом они исследуют свое окружение. Успешные тропы (например, тех, которые ведут к и от источника питания) насыщаются феромоном, поэтому все все больше и больше муравьев используют их (форма обучения или коллективная память). Благодаря этому в начале 1990-х годов, для научных исследований в области использования таких моделей поведения, были разрешены сложные комбинаторные проблемы, такие как задача коммивояжера (TSP). Оригинальные модели вычислений, известных как Ant системы (AS) работали достаточно хорошо для мелких проблем TSP, но не для более крупных примеров. Это способствовало созданию более сложных моделей, в частности, основные идеи объединения с AS эффективной стратегии локального поиска (LS). В исследовании этой области доминируют работы нескольких ведущих ученых, ( www.aco-metaheuristic.org , книга, "муравейника Оптимизация" на Dorigo и Stützle (2004) и ACO статьи в Dorigo на Scolarpedia ).Их исследования показали (см., например, Stützle и Dorigo, 1999), что с помощью различных вариаций ACO можно решить довольно большие проблемы TSP точно или близки к известному оптимальному решению, с приемлемым уровнем производительности. Подход был также найден эффективным в задачах маршрутизации автотранспорта, и в некоторых динамических проблемах маршрутизации. Однако, в отличие от некоторых других мета-эвристиких методов, его широкомасштабное применение менее очевидно, хотя оно имеет четкие ссылки на места так называемых Скопление разведки (более подробно см. раздел 8.2.3 ). Например, в связи с последним, Бэтти, Desyllas и Даксбери (2002, 2003) успешно применяются такие идеи к моделированию поведения пешеходов на людных улицах используя феромоны, а не дискретные трассы. Основная процедура для ACO TSP выглядит следующим образом:
Пусть т число муравьев, которые будут использоваться, п количество городов (М <= N) и Т итерации, кол-процесса. Пусть L т служит мерой расстояния между городами, а также определить параметры задачи: а, β (См. ниже).Мы также определяем начальное значение феромона, т т каждой дуги (I, J), соединяющая города я и /.
· определяем каждого из муравьев на случайно выбранном городе
· строим тур городов для каждого муравья следующим образом: для муравьев в настоящее время город і посещен и непосещенный j определяется вероятностной силой действия феромона, а такжк определяетсярасстояние от і до j (см. далее ниже)
· При желании можно улучшить каждый из индивидуальных туров порожденных муравьев с помощью локального поиска эвристических
· Повторите эту процедуру для каждого муравья, а после выполнения каждой итерации обновите феромон, согласно приведенным ниже формулам.
Определение вероятности функции:для муравьев применяется стандартные функции вероятности (т.е. должен ли муравей в настоящее время посетить город J?) В настоящее время город i во время итерации т имеет вид:
В этом выражении множество N является действующими в настоящее время в окрестности этого муравьями, т. е. множество городов еще не посещались. Эта вероятностная функция представляет собой комбинацию из двух составляющих: во-первых, сила следа феромонов , а второй фактор расстояния распада. Если a= 0, то феромоны компонента не оказывает никакого воздействия и вероятностные назначения на основе какой город ближе, то есть это типичные жадные эвристики, а если β = 0 задача на основе силы следа феромонов, который был найден приведет к стагнации решений и не дастеоптимальный обход туров .Пример испытания значения параметров а = 1 и β = 2
Обновление феромонов трассы: в теории феромонов тропы могут быть постоянно обновляется после каждого муравья завершившего турне.На практике оказалось, что обновление следа значения после завершения муравьими всех итераций является более эффективным. Обновление включает в себя два компонента: во-первых, свести все тропы значений на постоянный множитель, ρ (аналогичный процесс испарения), а затем добавить прирост на основе длины пути к-того муравья L K (T) , для всех муравьев:
Такое обновление гарантирует, что во-первых, пути не стали более насыщенным с феромонами и во-вторых, муравьи посетили пути, которые делают кратчайшие туры, чьи феромоны значения увеличились в наибольшей степени - повторного исполнения приговора или учебного процесса. Stützle и Dorigo (1999) обнаружили, что качество решений может быть значительно улучшено незначительные изменения в этой схеме. Во-первых, за счет ограничения максимальных и минимальных значений ценности феромонов, могут осуществляться инициализацией значения и устанавливаться в верхней границе этого диапазона, а во-вторых, позволяя лишь обновление след значимых путей, самыми эффективными муравьями, а не всеми муравьями (этот подход может также снизить накладные расходы на память алгоритм значительно). С учетом этих изменений авторам удалось решить проблемы с 1500 + городов (например, TSPLIB теста fl1577) дает результаты определенного диапазона [22286,22358], что сопоставимо с истинно оптимальным решением для этой проблемы 22249.