Метод муравьиной колонии и алгоритм его реализации

В данном материале рассмотрен так называемый метод муравьиной колонии для решения задачи коммивояжера.

Общие принципы жизнедеятельности муравьиной колонии

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

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

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

Этапы алгоритма

1. Ввод исходных данных и инициализация параметров настройки и переменных алгоритма.

2. Определение вероятностей перехода из одного муравейника в другой.

3. Генерация случайного маршрута движения каждого муравья из последнего местонахождения с учётом рассчитанных в п. 2 вероятностей перехода; определение результирующей длины каждого маршрута (критерий оптимизации); сохранение в памяти вариантов маршрутов с наилучшим значением критерия.

4. Расчёт изменения концентрации феромона между двумя муравейниками и нового значения концентрации феромона.

5. Повторение процедуры с п. 2 до выполнения одного или нескольких выбранных условий окончания.

6. Вывод вариантов маршрутов, обеспечивающих наилучшее значение критерия оптимальности.

1. Ввод исходных данных и инициализация параметров настройки и переменных алгоритма

Исходными данными являются:
– количество муравейников (M);
– количество муравьёв, приходящихся на один муравейник (n);
– координаты муравейников Xi, Yi.

Параметрами настройки алгоритма являются:
– степень влияния феромона (α);
– степень влияния расстояния (β);
– коэффициент, учитывающий испарение феромона (φ).

Переменными алгоритма являются:
Общее количество муравьёв (N):

Расстояние между муравейниками (Dij):

Среднее расстояние между муравейниками (D):

Параметр видимости j-го муравейника из i-го муравейника (νij):

Количество феромона на пути из i-го в j-й муравейник:

2. Определение вероятностей перехода из одного муравейника в другой

Вероятность перехода из муравейника i в муравейник j зависит от количества феромона, находящегося на пути между этими муравейниками, и видимости муравейника (определяется запахом, доносящимся из самого муравейника), в который осуществляется переход, с учётом степеней влияния феромона и расстояния между муравейниками:

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

3. Генерация случайного маршрута движения муравьёв

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

4. Расчёт изменения концентрации феромона

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

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

Изменение концентрации феромона за одну эпоху рассчитывается по соотношению:

,

где Wij q(t) – протяжённости маршрутов, в которые входит отрезок пути между муравейниками i, j на эпохе расчёта t; q – индекс маршрута, включающего отрезок пути между муравейниками i, j; Nq – количество маршрутов, включающих отрезок пути между муравейниками i, j.

5. Условия окончания вычислительной процедуры и вывод результатов

1. Выполнение заданного предельного количества эпох расчёта.

2. Отсутствие улучшения целевой функции на заданном предельном количестве эпох расчёта подряд.

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


многоагентные системы метод муравьиной колонии
Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • Четверть населения Финляндии, будет обучена работе с роботами и нейросетями.
  • Финляндии предстоит расти и расти, перед тем, как она сможет выйти на мировой рынок с технологиями искусственного интеллекта и все же, это не мешает
  • Как искусственный интеллект передает информацию от людей, потерявших способность говорить?
  • Несколько групп ученых смогли преобразовать команды головного мозга в речь с помощью компьютера-синтезатора. Для того, чтобы это сделать, они
  • К 2025 году, роботы строители, могут составить 10 процентов рабочей силы Японии.
  • Япония является одной из стран, в которой автоматизация процесса строительства, происходит очень медленно. Роботы на практике показывают лишь то, что
  • Интуитивный Алгоритм Технологической Сингулярности на основе Сильного Искусственного Интеллекта «Smart-MES»
  • Технологическая Сингулярность означает такое быстрое развитие прогресса, связанное с созданием сообщества Сильных Искусственных Интеллектов, когда
  • Видеокамеры научились различать телефоны в руках автомобилистов
  • Совсем недавно, в Москве, Сергей Собянин сделал официальное заявление, что с 2019 года в Москве заработают камеры, которые будут отслеживать опасных
Последние комментарии
Каким был первый робот в мире? Происхождение слова "Робот"
Восхищения нет предела делу ваших рук и идей. Хочется склонить голову перед вашим трудом, хотя твердо придерживаюсь Библии (не поклоняться идолам)
Как работает Любовь? Квантовая связь нейронной активности Людей
Я думаю, когда начнется квантовое взаимодействие мржду человеком и ИИ это и будет началом конца.
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Мы в социальных сетях
Статистика
0  
Всего статей 1545
0  
Всего комментариев 75
0  
Пользователей 69