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

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

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

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

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

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

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

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. Отсутствие улучшения целевой функции на заданном предельном количестве эпох расчёта подряд.

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


многоагентные системы метод муравьиной колонии
Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Последние комментарии
Дрон-камикадзе и ракеты с искусственным интеллектом: как в России создали умные боеприпасы и планируют применять в деле
Современная микроэлектроника, включая микроконтроллеры и процессоры для современных ПК, является продуктом высокотехнологического производства и
Как работает Любовь? Квантовая связь нейронной активности Людей
ребят,вот вам смешно,а квантовая связь влюбленных то существует.и я не шучу. мой парень видел глюки и в этих глюках присутствовала я.(если что,в
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
0  
Всего статей 2562
0  
Всего комментариев 1031
0  
Пользователей 264