В данном материале рассмотрен так называемый метод муравьиной колонии для решения задачи коммивояжера.
Муравьи – социальные насекомые, которые живут в коллективе – колонии. Число муравьёв в одной колонии может достигать нескольких миллионов, а сама колония может быть распределена по территории в десятки и сотни километров. В то же время, колония не имеет централизованного управления, а обмен информацией между особями осуществляется при помощи непрямого обмена, благодаря феромону, который муравьи оставляют в процессе своего передвижения в пространстве.
С одной стороны, чем больше муравьёв проходит по определённому пути, тем выше на нём концентрация феромона. С другой стороны, при выборе одного пути из нескольких альтернативных, наиболее высока вероятность выбора муравьём того пути, концентрация феромона на котором выше.
Описанные принципы жизнедеятельности колонии муравьёв лежат в основе рассматриваемого метода. Сам метод и реализация его алгоритма могут быть эффективно использованы при решении задачи коммивояжёра. Применительно к методу, коммивояжёр – это муравей, которому необходимо по кратчайшему маршруту посетить все муравейники, ни разу не вернувшись в тот, где он уже был.
1. Ввод исходных данных и инициализация параметров настройки и переменных алгоритма.
2. Определение вероятностей перехода из одного муравейника в другой.
3. Генерация случайного маршрута движения каждого муравья из последнего местонахождения с учётом рассчитанных в п. 2 вероятностей перехода; определение результирующей длины каждого маршрута (критерий оптимизации); сохранение в памяти вариантов маршрутов с наилучшим значением критерия.
4. Расчёт изменения концентрации феромона между двумя муравейниками и нового значения концентрации феромона.
5. Повторение процедуры с п. 2 до выполнения одного или нескольких выбранных условий окончания.
6. Вывод вариантов маршрутов, обеспечивающих наилучшее значение критерия оптимальности.
Исходными данными являются:
– количество муравейников (M);
– количество муравьёв, приходящихся на один муравейник (n);
– координаты муравейников Xi, Yi.
Параметрами настройки алгоритма являются:
– степень влияния феромона (α);
– степень влияния расстояния (β);
– коэффициент, учитывающий испарение феромона (φ).
Переменными алгоритма являются:
Общее количество муравьёв (N):
Расстояние между муравейниками (Dij):
Среднее расстояние между муравейниками (D):
Параметр видимости j-го муравейника из i-го муравейника (νij):
Количество феромона на пути из i-го в j-й муравейник:
Вероятность перехода из муравейника i в муравейник j зависит от количества феромона, находящегося на пути между этими муравейниками, и видимости муравейника (определяется запахом, доносящимся из самого муравейника), в который осуществляется переход, с учётом степеней влияния феромона и расстояния между муравейниками:
Поскольку на первой эпохе расчёта принято единичное значение феромона, одинаковое для всех вариантов перехода, на ней значимо только расстояние между городами.
Для каждого из N муравьёв генерируется маршрут движения из последнего местонахождения случайным образом, с учётом вероятностей перехода, полученных на этапе 2. Для каждого из полученных маршрутов рассчитывается целевая функция общей протяжённости маршрута.
Изменение концентрации феромона на каждом участке зависит от протяжённости этого участка. В общем случае, чем короче участок, тем большее количество муравьёв успеют пройти по нему за один и тот же промежуток времени, и на нём останется большее количество феромона, по сравнению с более протяжённым участком.
Вместе с тем, необходимо учитывать испарение феромона с участка с течением времени. Таким образом, если за одну эпоху работы алгоритма участок оказался не задействован, количество феромона на нём уменьшится.
Изменение концентрации феромона за одну эпоху рассчитывается по соотношению:
где Wij q(t) – протяжённости маршрутов, в которые входит отрезок пути между муравейниками i, j на эпохе расчёта t; q – индекс маршрута, включающего отрезок пути между муравейниками i, j; Nq – количество маршрутов, включающих отрезок пути между муравейниками i, j.
1. Выполнение заданного предельного количества эпох расчёта.
2. Отсутствие улучшения целевой функции на заданном предельном количестве эпох расчёта подряд.
Решением или решениями задачи являются такие маршруты, полученные за всё время работы алгоритма, которые обеспечивают минимум целевой функции.