В последние годы интенсивно разрабатывается научное направление с названием «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. Эти механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении нескольких миллионов лет. Среди так называемых “Soft computing techniques”, разработанных за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся:
- Генетические алгоритмы (GAs)
- Основываются на естественном отборе и генетике
- Муравьиные алгоритмы (Ant Colony Optimization – ACO, Ant Systems – AS)
- Моделируют поведение муравейника
Имитация самоорганизации муравьиной колонии составляет основу муравьиных алгоритмов оптимизации. Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным.
Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 90-х годов. На сегодняшний день уже получены хорошие результаты для оптимизации таких сложных комбинаторных задач, как задача коммивояжера, задача оптимизации маршрутов грузовиков, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых графиков, задача календарного планирования и многие другие. Особенно эффективны муравьиные алгоритмы при динамической оптимизации процессов в распределенных нестационарных системах, например, трафиков в телекоммуникационных сетях.
Муравьи относятся к социальным насекомым, образующим коллективы. Коллективная система способна решать сложные динамические задачи по выполнению совместной работы, которая не могла бы выполняться каждым элементом системы в отдельности в разнообразных средах без внешнего управления, контроля или координации. В таких случаях говорят о роевом интеллекте (Swarm intelligence), как о замысловатых способах кооперативного поведения, то есть стратегии выживания. Одним из подтверждений оптимальности поведения муравьиных колоний является тот факт, что сеть гнёзд суперколоний близка к минимальному остовному дереву графа их муравейников.
Основу поведения муравьиной колонии составляет самоорганизация, обеспечивающая достижения общих целей колонии на основе низкоуровневого взаимодействия. Колония не имеет централизованного управления, и её особенностями являются обмен локальной информацией только между отдельными особями (прямой обмен – пища, визуальные и химические контакты) и наличие непрямого обмена, который и используется в муравьиных алгоритмах. Таким образом, в общем случае рассматриваются слепые муравьи, не способные чувствовать близость пищи. Непрямой обмен – стигмержи (stigmergy), представляет собой разнесённое во времени взаимодействие, при котором одна особь изменяет некоторую область окружающей среды, а другие используют эту информацию позже, когда в неё попадают. Биологи установили, что такое отложенное взаимодействие происходит через специальное химическое вещество – феромон (pheromone), секрет специальных желёз, откладываемый при перемещении муравья. Концентрация феромона на пути определяет предпочтительность движения по нему.
Адаптивность поведения реализуется испарением феромона, который в природе воспринимается муравьями в течение нескольких суток. Мы можем провести некоторую аналогию между распределением феромона в окружающем колонию пространстве, и «глобальной» памятью муравейника, носящей динамический характер.
Муравьиные алгоритмы представляют собой вероятностную жадную эвристику, где вероятности устанавливаются, исходя из информации о качестве решения, полученной из предыдущих решений. Они могут использоваться как для статических, так и для динамических комбинаторных оптимизационных задач. Сходимость гарантирована, то есть в любом случае мы получим оптимальное решение, однако скорость сходимости неизвестна.
Началось всё с изучения поведения реальных муравьёв. Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Именно он впервые сумел формализовать поведение муравьёв и применить стратегию их поведения для решения задачи о кратчайших путях. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач при помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты.
Идея муравьиного алгоритма – моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути. Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным. Рассмотрим случай, показанный на рисунке, когда на оптимальном доселе пути возникает преграда. В этом случае необходимо определение нового оптимального пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. То же самое будет происходить и на обратной стороне преграды. Однако, те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен.
Очевидная положительная обратная связь быстро приведёт к тому, что кратчайший путь станет единственным маршрутом движения большинства муравьёв. Моделирование испарения феромона – отрицательной обратной связи – гарантирует нам, что найденное локально оптимальное решение не будет единственным – муравьи будут искать и другие пути. Если мы моделируем процесс такого поведения на некотором графе, рёбра которого представляют собой возможные пути перемещения муравьёв, в течение определённого времени, то наиболее обогащённый феромоном путь по рёбрам этого графа и будет являться решением задачи, полученным с помощью муравьиного алгоритма.
Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде:
Пока (условия выхода не выполнены):
1. Создаём муравьёв
2. Ищем решения
3. Обновляем феромон
4. Дополнительные действия {опционально}Теперь рассмотрим каждый шаг в цикле более подробно:
- Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
- На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
-
Вероятность перехода из вершины i в вершину j определяется по следующей формуле
$$\color{white}{\displaystyle p_{i,j}={\frac {(\tau _{i,j}^{\alpha })(\eta _{i,j}^{\beta })}{\sum (\tau _{i,j}^{\alpha })(\eta _{i,j}^{\beta })}}}$$ Где :
$\tau_{i,j}(t)$ – это количество феромонов на ребре$i , j$ ;
$\alpha$ - параметр, контролирующий влияние$\tau_{i,j}(t)$ ;
$\eta {i,j}$ - привлекательность ребра $i , j$ (начальное значение, как правило, $1 / d{i , j}$, где$d$ расстояние);
$\beta$ - параметр, контролирующий влияние$\eta_{i,j}$ .
-
Уровень феромона обновляется в соответствии с приведённой формулой $$\color{white}\tau {i,j}=(1-\rho )\tau{i,j}+\Delta \tau _{i,j}$$
Где :
$\tau_{i,j}$ — количество феромона на дуге$i,j$
$\rho$ — скорость испарения феромона
$\Delta \tau_{i,j}$ — количество отложенного феромона, обычно определяется как:
${\displaystyle \Delta \tau {i,j}^{k}={\begin{cases}1/L{k}\0\end{cases}}}$
где$L_{k}$ — стоимость$k$ -го пути муравья (обычно длина).
- Обычно здесь используется алгоритм локального поиска, однако он может также появиться и после поиска всех решений.
Для того чтобы построить подходящий муравьиный алгоритм для решения какой-либо задачи, нужно:
- Представить задачу в виде набора компонент и переходов или набором неориентированных взвешенных графов, на которых муравьи могут строить решения
- Определить значение следа феромона
- Определить эвристику поведения муравья, когда строим решение
- Если возможно, то реализовать эффективный локальный поиск
- Выбрать специфический ACO алгоритм и применить для решения задачи
- Настроить параметр ACO алгоритма
Также определяющими являются:
- Количество муравьёв
- Баланс между изучением и использованием
- Сочетание с жадными эвристиками или локальным поиском
- Момент, когда обновляется феромон
При помощи алгоритма эффективно решать задачу на нахождение оптимального маршрута. Эту задачу принято называть задачей коммивояжёра (TSP – Travelling Salesman Problem).
Есть разные варианты постановки этой задачи. В классической постановке коммивояжёр (странствующий торговец) должен объехать определённое количество городов по замкнутому маршруту, посетив каждый из них только один раз. При этом, чем длина маршрута будет меньше, тем лучше.
Например, торговцу нужно посетить 5 городов и вернуться в исходный. Находясь в городе отправления, у него для выбора доступно 4 города. Дальше он делает выбор из трёх городов и так далее. Значит, количество всех возможных вариантов равно $432*1 = 24$, то есть
В этой постановке задачи торговцу нужно объехать все города и вернуться в исходный, а направление движения не имеет значения. Это называется симметричной задачей коммивояжёра. Следовательно, половину вариантов можно не учитывать, так как, например, варианты ABCDEA и AEDCBA будут эквивалентны. Значит, количество маршрутов для 5 городов равно
Сложность задачи методом полного перебора растёт факториально. Несложно по формуле вычислить количество вариантов для большего количества городов:
| Количество городов | Количество возможных путей |
|---|---|
| 5 | 12 |
| 6 | 60 |
| 7 | 360 |
| 8 | 2520 |
| 9 | 20160 |
| 10 | 181440 |
| 11 | 1814400 |
| 12 | 19958400 |
| 13 | 239500800 |
| 14 | 3113510400 |
| 15 | 43589145600 |
| 16 | 653837184000 |
| 17 | 10461394944000 |
| 18 | 177843714048000 |
Как мы видим, количество возможных путей при увеличении количества городов очень быстро растёт, и простым перебором вариантов (методом грубой силы) задачу становится решить гораздо менее возможно.
Задача коммивояжёра – одна из трансвычислительных задач. Это значит, что уже на довольно небольшом количестве городов (66 и более) лучшее решение простым методом перебора вариантов не может быть найдено никакими самыми мощными компьютерами меньше чем за миллиарды лет. Поэтому, гораздо разумнее находить решение этой задачи при помощи алгоритмов оптимизации.
Рассмотрим реализацию алгоритма на языке Python.
Код написан в соответствие с описанием алгоритма и формулами выше. В алгоритме есть два важных фактора: феромон τ и видимость η. Феромон τ относится к оставшейся информации на каждом пути, по которому проходят муравьи. Видимость η обозначает обратное расстояние между узлами. Вероятность P состоит из произведения феромона τ и видимости η и их суммы. При кратчайшем пути, высоком уровне феромона τ, а также высокой видимости η вероятность P становится выше. Следовательно, в строках 39-40 происходит подсчёт вероятности P. Затем, строка 41 выбирает последовательность кратчайших путей при помощи вероятности P. Наконец, строки 55-64 обновляют феромон τ с коэффициентом испарения ρ. Параметр Q – это сумма феромонов в постоянном значении. Вернувшись к строке 37, новая последовательность маршрутов определена для следующего вычисления.
class ACO_TSP: # класс алгоритма муравьиной колонии для решения задачи коммивояжёра
def __init__(self, func, n_dim, size_pop=10, max_iter=20, distance_matrix=None, alpha=1, beta=2, rho=0.1):
self.func = func
self.n_dim = n_dim # количество городов
self.size_pop = size_pop # количество муравьёв
self.max_iter = max_iter # количество итераций
self.alpha = alpha # коэффициент важности феромонов в выборе пути
self.beta = beta # коэффициент значимости расстояния
self.rho = rho # скорость испарения феромонов
self.prob_matrix_distance = 1 / (distance_matrix + 1e-10 * np.eye(n_dim, n_dim))
# Матрица феромонов, обновляющаяся каждую итерацию
self.Tau = np.ones((n_dim, n_dim))
# Путь каждого муравья в определённом поколении
self.Table = np.zeros((size_pop, n_dim)).astype(int)
self.y = None # Общее расстояние пути муравья в определённом поколении
self.generation_best_X, self.generation_best_Y = [], [] # фиксирование лучших поколений
self.x_best_history, self.y_best_history = self.generation_best_X, self.generation_best_Y
self.best_x, self.best_y = None, None
def run(self, max_iter=None):
self.max_iter = max_iter or self.max_iter
for i in range(self.max_iter):
# вероятность перехода без нормализации
prob_matrix = (self.Tau ** self.alpha) * (self.prob_matrix_distance) ** self.beta
for j in range(self.size_pop): # для каждого муравья
# точка начала пути (она может быть случайной, это не имеет значения)
self.Table[j, 0] = 0
for k in range(self.n_dim - 1): # каждая вершина, которую проходят муравьи
# точка, которая была пройдена и не может быть пройдена повторно
taboo_set = set(self.Table[j, :k + 1])
# список разрешённых вершин, из которых будет происходить выбор
allow_list = list(set(range(self.n_dim)) - taboo_set)
prob = prob_matrix[self.Table[j, k], allow_list]
prob = prob / prob.sum() # нормализация вероятности
next_point = np.random.choice(allow_list, size=1, p=prob)[0]
self.Table[j, k + 1] = next_point
# рассчёт расстояния
y = np.array([self.func(i) for i in self.Table])
# фиксация лучшего решения
index_best = y.argmin()
x_best, y_best = self.Table[index_best, :].copy(), y[index_best].copy()
self.generation_best_X.append(x_best)
self.generation_best_Y.append(y_best)
# подсчёт феромона, который будет добавлен к ребру
delta_tau = np.zeros((self.n_dim, self.n_dim))
for j in range(self.size_pop): # для каждого муравья
for k in range(self.n_dim - 1): # для каждой вершины
# муравьи перебираются из вершины n1 в вершину n2
n1, n2 = self.Table[j, k], self.Table[j, k + 1]
delta_tau[n1, n2] += 1 / y[j] # нанесение феромона
# муравьи ползут от последней вершины обратно к первой
n1, n2 = self.Table[j, self.n_dim - 1], self.Table[j, 0]
delta_tau[n1, n2] += 1 / y[j] # нанесение феромона
self.Tau = (1 - self.rho) * self.Tau + delta_tau
best_generation = np.array(self.generation_best_Y).argmin()
self.best_x = self.generation_best_X[best_generation]
self.best_y = self.generation_best_Y[best_generation]
return self.best_x, self.best_y
fit = runГраф, на котором будет происходить поиск решения, можно сгенерировать случайным образом. Сначала генерируются координаты точек, затем при помощи модуля spatial из библиотеки scipy происходит вычисление матрицы расстояний (расстояние от каждой вершины до каждой вершины).
import numpy as np
from scipy import spatial
num_points = 2000 # количество вершин
points_coordinate = np.random.rand(num_points, 2) # генерация рандомных вершин
print("Координаты вершин:\n", points_coordinate[:10], "\n")
# вычисление матрицы расстояний между вершин
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
print("Матрица расстояний:\n", distance_matrix)Для того чтобы добавить данным «реальности», представим, что эти вершины – это местоположение на карте банкоматов, которые необходимо посетить инкассаторам. Стоит отметить, что знаниями о том, как инкассация строит свои маршруты, мы не располагаем, но этот алгоритм – это один из вариантов того, как их маршруты можно оптимизировать.
Рассмотрим задачу с количеством муравьёв, равным 40 (size_pop=40), итераций, равным 30 (max_iter=30) и вершин – 40. Функция cal_total_distance рассчитывает длину пути. Затем при помощи matplotlib.pyplot происходит вывод графиков. Также выводится время выполнения программы, которое мы дальше будем сравнивать для разного количества вершин.
import time
import matplotlib.pyplot as plt
import pandas as pd
# вычисление длины пути
def cal_total_distance(routine):
num_points, = routine.shape
return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
def main():
# создание объекта алгоритма муравьиной колонии
aca = ACO_TSP(func=cal_total_distance, n_dim=num_points,
size_pop=40, # количество муравьёв
max_iter=10, distance_matrix=distance_matrix)
best_x, best_y = aca.run()
# Вывод результатов на экран
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_x, [best_x[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
for index in range(0, len(best_points_)):
ax[0].annotate(best_points_[index], (best_points_coordinate[index, 0], best_points_coordinate[index, 1]))
ax[0].plot(best_points_coordinate[:, 0],
best_points_coordinate[:, 1], 'o-r')
pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])
# изменение размера графиков
plt.rcParams['figure.figsize'] = [20, 10]
plt.show()
if __name__ == "__main__":
start_time = time.time() # сохранение времени начала выполнения
main() # выполнение кода
print("time of execution: %s seconds" %abs (time.time() - start_time)) # вычисление времени выполненияЧтобы убедиться, что алгоритм эффективен и способен искать оптимальный путь, для наглядности можно сначала значительно понизить точность алгоритма и посмотреть, как выглядит неоптимальный рандомный маршрут. Вот результат работы программы при количестве муравьёв и итераций, равных 1:
Как мы видим, маршрут очень длинный и беспорядочный. Никому бы не понравилось ездить по такому маршруту. Путём подбора значений параметров удалось выяснить, что при количестве муравьёв и итераций, равных 40 и 30 соответственно, алгоритм почти всегда останавливается на этом решении:
При увеличении параметров результат работы программы уже не меняется. Значит, этих значений алгоритму было достаточно, чтобы найти самый короткий и оптимальный замкнутый маршрут на карте.
40 – относительно небольшое число вершин. Можно посмотреть, как алгоритм будет вести себя на более сложных графах и как долго будет находить решение. При тех же параметрах на более сложных графах время работы алгоритма заметно увеличивается. Чтобы как-то сократить время выполнения, уменьшим количество муравьёв до 20 и итераций – до 5. Так выглядит результат работы на графе из 1000 вершин:
А так – на 2000:
Выглядит очень страшно. И выполнение заняло больше двух минут. Результат работы алгоритма для большего количества вершин (например, для 10000) дождаться было бы уже гораздо сложнее.
В рейтинге самых быстрых языков программирования Python стабильно занимает одно из последних мест. Зачастую логика, выполняющаяся на других языках за миллисекунды, на Python занимает несколько секунд. Существуют способы ускорения кода на Python. Например, пакет PyPy, который делает код быстрее. Или Cython – расширение языка, в котором поддерживается прямой вызов функций и методов C/C++ и строгая типизация. Он может ускорить работу более чем в 30 раз.
Также можно использовать реализацию алгоритма на другом языке программирования, например, на C/C++. Или научить программу эффективно использовать ресурсы компьютера: оптимизировать её под многопоточность и использовать код на ассемблере, чтобы обращаться к процессору напрямую, без компилятора высокого уровня.
Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям, то такой подход может стать эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию. Ряд экспериментов показывает, что эффективность муравьиных алгоритмов растёт с ростом размерности решаемых задач оптимизации. Хорошие результаты получаются для нестационарных систем с изменяемыми во времени параметрами, например, для расчётов телекоммуникационных и компьютерных сетей. В Интернете можно найти описание применения муравьиного алгоритма для разработки оптимальной структуры съёмочных сетей GPS в рамках создания высокоточных геодезических и съёмочных технологий. В настоящее время на основе применения муравьиных алгоритмов получены хорошие результаты для таких сложных оптимизационных задач, как задача коммивояжёра, транспортная задача, задача календарного планирования, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых трафиков и ряд других.
Качество получаемых решений во многом зависит от настроечных параметров в вероятностнопропорциональном правиле выбора пути на основе текущего количества феромона и от параметров правил откладывания и испарения феромона. Возможно, что динамическая адаптационная настройка этих параметров может способствовать получению лучших решений. Немаловажную роль играет и начальное распределение феромона, а также выбор условно оптимального решения на шаге инициализации.
Перспективными путями улучшения муравьиных алгоритмов являются различные адаптации параметров с использованием базы нечётких правил и их гибридизация, например, с генетическими алгоритмами. Как вариант, такая гибридизация может состоять в обмене через определённые промежутки времени текущими наилучшими решениями.