armpomor / ant_colony_optimization Goto Github PK

Муравьиный алгоритм (алгоритм оптимизации подражанием муравьиной колонии, англ. ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближённых решений задачи коммивояжёра, а также решения аналогичных задач поиска маршрутов на графах. Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии к источнику питания, и представляет собой метаэвристическую оптимизацию.

Для отображения графиков необходима Plotly v.2.12.1 На первом графике отображается зависимость длины маршрута от количества итераций, на втором наиболее популярный маршрут за данное количество итераций.

Все константы можно изменять в config.py Количество городов ограничено до 52.

1. ЗАДАЧА: Найти кратчайший гамильтонов цикл.

2. Генерируем взвешенный полный граф.

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

4. В основе алгоритма лежит формула, по которой высчитывается вероятность перехода из вершины i в вершину j:

    P_j = 100(pow(n_j, beta) * pow(t_j, alpha)) / sum(pow(n_k, beta) * pow(t_k, alpha)), где
   

   P_j - вероятность перехода из i в j; n_j - величина обратная расстоянию между i и j t_j - количество феромона между i и j; beta - величина, определяющая «жадность» алгоритма; alpha - величина, определяющая «стадность» алгоритма; знаменатель - это сумма таких же произведений (желаний), как и в числителе, только из i во все возможные вершины, за исключением тех, которые уже посещены. Если коэфициент alpha = 0, то получается жадный алгоритм, то есть муравей ищет самые короткие расстояния и игнорирует количество феромона. Если коэфициент beta = 0, то муравей реагирует только на количество феромона оставленого предыдущими муравьями и не учитывает расстояние между вершинами. Вероятность перехода из i в j равна желанию перейти туда деленное на сумму желаний перехода из i во все вершины, которые доступны и непосещены.

5. Когда высчитаны все вероятности из данной вершины (сумма вероятностей должна быть равна 100%), генератором случайных чисел (random) (вспомни разверстку рулетки, т.е. чем шире диапазон, тем больше вероятность, что мы туда попадем) выбирается следующая вершина для посещения и муравей переходит в выбранную вершину.

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

7. По пути следования муравей откладывает феромон. Общая длина пути пройденного первым муравьем пусть будет равна L (т.е. это сумма весов ребер, по которым прошел муравей.). На основании этой длины L вычисляется, d_t - константа для обновления значений феромона на пути, который прошел муравей, т.е. это близость. d_t = Q / L, где Q - некая константа, которая подбирается так, чтобы d_t была сопоставима с прошлыми значениями, чтобы числа получились не слишком маленькие. Новое количество феромона вычисляется: t_new_j = p * t_j + sum(d_t), где p - коэффициент испарения феромона, принимается значение меньше единицы; t_j - старое значение феромона на ребре; sum(d_t) - сумма всех новых порций феромона, которые отложили все муравьи на этом ребре.

8. Количество муравьев равно количеству городов.

9. Каждый муравей начинает маршрут из другого города.

10. После того как все муравьи прошли по своим маршрутам, обновляем феромон. На всех ребрах сначала уменьшаем феромон, умножив его количество на коэффициент испарения, а потом на тех ребрах по которым прошли муравьи, увеличиваем на высчитанную близость.

11. Запускаем муравьев по новой, начинается новая итерация.