Контенус

колония муравьев

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

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

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

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

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

Алгоритм был представлен мистером Дориго в 1991 году и изначально предназначался для TSP (коммивояжера). Представим решаемую задачу в виде поиска кратчайшего пути в график.

Структура алгоритма муравьиной колонии выглядит следующим образом:

Инициализировать
Повторять до максимального количества циклов
1. Каждый муравей строит решение
2. Улучшение решений локальный поиск
3. Вознаграждайте лучшие решения, добавляя феромоны
4. Испарить следы феромона

Алгоритмы типа ACO имеют доказательства сходимости, которые не будут показаны в этом курсе.

Инициализация (случай TSP)

Les м муравьи случайным образом распределяются по нет города. Для каждого муравья запретный список назначенный ему, он содержит его стартовый список. Следы феромонов инициализируются значением против ненулевой положительный. Каждое ребро графа ij имеет свой отмеченный феромоновый след Т_ij=с.

Построение решения и локальный поиск

муравьи к размещен в городе я прямо сейчас ты выберите город назначения я с точки зрения :

Видимость этого города нет_ij (расстояние в случае TSP)
Количество феромона Т_ij(т) оседает на трассе.

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

Каждый муравей действует таким образом, пока не пройдет через все города.

Конец цикла

Для каждого муравья к, вычисляем длину его поворота л_к(т) тогда его табу-лист очищается (кроме инициализации).

Затем обновляются следы феромонов:

Т_ij(т+1)=р*Т_ij(т)+феромоны_ij(т) с п между 0 и 1 и феромоны_ij(т) количество феромонов, отложенных муравьями на костях ij ездить на велосипеде ты.

Испарение с дорожки рассчитывается непосредственно по предыдущей формуле. На самом деле p представляет постоянство следа, то есть память о количестве феромонов, которое мы сохраняем для следующего цикла. Будь то р=1, нет испарения и, следовательно, нет ограничения автокаталитического явления. Будь то р=0, система не имеет памяти, учитывается только последний выполненный цикл.

Для каждого муравья к прохождение через гребень ij, это увеличивает количество отложенного феромона в соответствии со следующим расчетом:

феромоны_ij(t) += Q/L_к(т) куда Вопрос представляет собой квоту феромонов, выделяемую каждому муравью (часто Q=100). Идея состоит в том, чтобы равномерно снабжать феромонами весь путь, пройденный муравьем.

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

Варианты алгоритма: MMAS

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