Муравьи и Python: ищем самые короткие пути

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

Алгоритмов оптимизации существует очень много. В этой статье будет разобран один из самых известных алгоритмов, заимствованных у природы – муравьиный алгоритм (ACO – Ant Colony Optimization).

Идея муравьиного алгоритма возникла в результате наблюдения за поведением реальных муравьёв. Отправной точкой положили исследования аргентинских муравьёв в 1989-1990 годах. Затем, в начале 90-х годов, Марко Дориго начал исследования для применения этой информации в практике. Он первый смог применить их стратегию для задачи по нахождению кратчайших маршрутов в графе.

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

Суть алгоритма довольно проста: изначально муравьи доставляют еду в муравейник беспорядочно каждый своей дорогой, охватывая тем самым самые различные маршруты. Во время движения муравьи оставляют пахучий след из феромонов на своём пути, тем самым обозначая маршруты. Соответственно, чем дорога короче, тем большее количество раз за одинаковое время муравьи успеют по ней пройти и смогут оставить на ней больше феромонов. Феромоны имеют свойство испаряться с течением времени. Из-за этого на длинных маршрутах остаётся меньше феромонов, чем на коротких, даже если по ним будет передвигаться одинаковое количество муравьёв. Таким образом, муравьи будут чаще выбирать самую «пахучую тропинку» и забывать пути с меньшим количеством феромонов.

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

Пока (не выполнены условия выхода) выполняются следующие операции алгоритма:

1. Создание муравьёв.

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

2. Поиск решений.

Формула для вычисления вероятности перехода муравья из вершины i в j:

где τij(t) – количество феромона между вершинами i и j, ηij – расстояние между этими вершинами. α, β – константные параметры. Их необходимо подбирать опытным путём, их значение должно быть такое, чтобы алгоритм не был слишком жадным и не застревал в локальных минимумах.

Чем ближе к нулю параметр β, тем меньше муравьи в выборе пути будут руководствоваться расстоянием между вершинами и будут ориентироваться только на феромон. С увеличением β значение близости растёт. Параметр α действует так же, но для уровня феромона.

Верхняя часть формулы описывает желание муравья перейти из вершины i в вершину j. Оно пропорционально близости вершины и уровню феромона на пути к ней.

Таким образом, вероятность перехода из вершины i в вершину j равняется желанию перейти в неё, делённому на сумму желаний перейти из вершины i ко всем доступным вершинам, которые ещё не были посещены. Сумма всех вероятностей равна 1.

Разложив все вероятности на числовой прямой от 0 до 1, можно сгенерировать рандомное вещественное число в этом интервале. Результат покажет, в какую вершину перейдёт муравей.

3. Обновление феромона.

Формула для пересчёта уровня феромона на каждой итерации алгоритма:

где ρ – скорость испарения, t – номер итерации, Lk(t) – цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/Lk(t) – феромон, откладываемый k-ым муравьём, использующим ребро (i, j).

Таким образом, количество феромона на ребре между i и j на новой итерации равно количеству феромона на старой итерации, умноженное на коэффициент испарения (феромон постоянно испаряется), и к полученному результату добавляется сумма всех новых порций феромона, который отложили все муравьи на этом участке. Добавка феромона, которую делает муравей, проходя по ребру, равна константе Q, делённой на длину маршрута L, пройденную муравьём k, при условии, что это ребро попало в маршрут муравья.

Сложность муравьиного алгоритма зависит от количества вершин, количества муравьёв и времени жизни колонии.

При помощи алгоритма эффективно решать задачу на нахождение оптимального маршрута. Эту задачу принято называть задачей коммивояжёра (TSP – Travelling Salesman Problem).

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

Например, торговцу нужно посетить 5 городов и вернуться в исходный. Находясь в городе отправления, у него для выбора доступно 4 города. Дальше он делает выбор из трёх городов и так далее. Значит, количество всех возможных вариантов равно 4*3*2*1 = 24, то есть (n-1)!, где n – количество городов.

В этой постановке задачи торговцу нужно объехать все города и вернуться в исходный, а направление движения не имеет значения. Это называется симметричной задачей коммивояжёра. Следовательно, половину вариантов можно не учитывать, так как, например, варианты ABCDEA и AEDCBA будут эквивалентны. Значит, количество маршрутов для 5 городов равно 24/2=12, а конечная формула количества вариантов для симметричной задачи будет выглядеть так: (n-1)!/2.

Сложность задачи методом полного перебора растёт факториально. Несложно по формуле вычислить количество вариантов для большего количества городов:

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

Задача коммивояжёра – одна из трансвычислительных задач. Это значит, что уже на довольно небольшом количестве городов (66 и более) лучшее решение простым методом перебора вариантов не может быть найдено никакими самыми мощными компьютерами меньше чем за миллиарды лет. Поэтому, гораздо разумнее находить решение этой задачи при помощи алгоритмов оптимизации.

Рассмотрим реализацию алгоритма на языке Python.

Код написан в соответствие с описанием алгоритма и формулами выше. В алгоритме есть два важных фактора: феромон τ и видимость η. Феромон τ относится к оставшейся информации на каждом пути, по которому проходят муравьи. Видимость η обозначает обратное расстояние между узлами. Вероятность P состоит из произведения феромона τ и видимости η и их суммы. При кратчайшем пути, высоком уровне феромона τ, а также высокой видимости η вероятность P становится выше. Следовательно, в строках 39-40 происходит подсчёт вероятности P. Затем, строка 41 выбирает последовательность кратчайших путей при помощи вероятности P. Наконец, строки 55-64 обновляют феромон τ с коэффициентом испарения ρ. Параметр Q – это сумма феромонов в постоянном значении. Вернувшись к строке 37, новая последовательность маршрутов определена для следующего вычисления.

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

Вывод программы:

Для того чтобы добавить данным «реальности», представим, что эти вершины – это местоположение на карте банкоматов, которые необходимо посетить инкассаторам. Стоит отметить, что знаниями о том, как инкассация строит свои маршруты, мы не располагаем, но этот алгоритм – это один из вариантов того, как их маршруты можно оптимизировать.

Рассмотрим задачу с количеством муравьёв, равным 40 (size_pop=40), итераций, равным 30 (max_iter=30) и вершин – 40. Функция cal_total_distance рассчитывает длину пути. Затем при помощи matplotlib.pyplot происходит вывод графиков. Также выводится время выполнения программы, которое мы дальше будем сравнивать для разного количества вершин.

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

Как мы видим, маршрут очень длинный и беспорядочный. Никому бы не понравилось ездить по такому маршруту. Путём подбора значений параметров удалось выяснить, что при количестве муравьёв и итераций, равных 40 и 30 соответственно, алгоритм почти всегда останавливается на этом решении:

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

40 – относительно небольшое число вершин. Можно посмотреть, как алгоритм будет вести себя на более сложных графах и как долго будет находить решение. При тех же параметрах на более сложных графах время работы алгоритма заметно увеличивается. Чтобы как-то сократить время выполнения, уменьшим количество муравьёв до 20 и итераций – до 5. Так выглядит результат работы на графе из 1000 вершин:

А так – на 2000:

Выглядит очень страшно. И выполнение заняло больше двух минут. Результат работы алгоритма для большего количества вершин (например, для 10000) дождаться было бы уже гораздо сложнее.

В рейтинге самых быстрых языков программирования Python стабильно занимает одно из последних мест. Зачастую логика, выполняющаяся на других языках за миллисекунды, на Python занимает несколько секунд. Существуют способы ускорения кода на Python. Например, пакет PyPy, который делает код быстрее. Или Cython – расширение языка, в котором поддерживается прямой вызов функций и методов C/C++ и строгая типизация. Он может ускорить работу более чем в 30 раз.

Также можно использовать реализацию алгоритма на другом языке программирования, например, на C/C++. Или научить программу эффективно использовать ресурсы компьютера: оптимизировать её под многопоточность и использовать код на ассемблере, чтобы обращаться к процессору напрямую, без компилятора высокого уровня. Но скорость и оптимизация кода – это уже тема для других объёмных статей.

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