Коллективные следопыты из муравейника в сопровождении Питона

Алгоритм оптимизации муравьиной колонии ACO

Идея алгоритма навеяна поведением муравьиной колонии, особи которой быстро находят кратчайший путь до еды. Та информация, которую в процессе поиска оставляют муравьи — это пахучие следы феромонов, которые со временем испаряются. Если муравьи снуют по более короткому пути, они чаще по нему проходят и оставляют больше феромонов. Короткий путь будет пахнуть сильнее и привлекать муравьёв. Со временем все муравьи переключатся на более пахучие дорожки. Про длинные пути, где запах феромонов испарился, все забывают.

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

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

В компьютерном муравьином алгоритме роль муравьев играют узлы. В качестве феромонов выступает длина ребра между узлами. На каждом шаге выбирается минимальный путь. От выбранного узла — следующее ребро (узел), до которого расстояние минимальное. Момент окончания работы алгоритма — выполнения задачи, с учетом ограничивающих факторов.

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

Реализация алгоритма муравьиной колонии на Python

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

Задача коммивояжера

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

Муравьи путешествуют из начальной точки, через все города, с возвращением в точку старта.

Пример для реализации с помощью муравьиного алгоритма

Будем определять кратчайший путь для 6 городов, расположенных согласно следующей схеме.

В качестве коммивояжера будут выступать муравьи.

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

Алгоритм решения задачи коммивояжера с помощью муравьиного алгоритма

1. Количество муравьев n_ants задаем равным количеству городов.
2. Задаем матрицу расстояний distances между городами.
3. Задаем аналогичную матрицу феромонов pheromone. Матрицы distances[J, K] и pheromone[J, K] дают расстояние и силу феромонов между городами J и K. Инициализируем матрицу феромонов маленькими одинаковыми числами.
4. Цикл по всем итерациям.
5. Вызывается функция gen_all_paths, в которой в цикле по каждому муравью определяется его путь по городам. Каждый муравей начинает со своего города.
6. Рассчитываем матрицу вероятностей для перехода из одного города в другой для каждой пары городов (кроме уже посещенных) и привлекательность каждого города:

привлекательность = pheromone ** alpha * (1.0 / distance) ** beta

где

alpha – Сила (вес) феромона [0, 1]. По умолчанию = 1
beta (int или float) – Вес расстояния. По умолчанию = 1

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

Муравей продолжает двигаться из города в город в соответствие с выбранным правилом, пока не посетит все города.

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

8. В конце каждой итерации:

• Рассчитывается уровень феромона, добавленный в результате прохождения данного участка пути (функция spread_pheromone)
• Уровень феромона перерасчитывается в сторону уменьшения вследствие испарения “феромона” (умножение на коэффициент stamina).

9. Программа прекращает работу после заданного количества итераций.

Реализация муравьиного алгоритма на Python

Реализация выполнена на языке Python 3.11 во фреймворке Google Colaboratory.

Комментарии к коду программы

Запуск кода на выполнение.

В этом коде задаются:

• Матрица расстояний между городами. Схема выше приведена для примера. Показанный здесь прогон муравьиного алгоритма проводился не для 6, а для 10 городов.
• Количество итераций
• Количество муравьев задается равным числу городов

import numpy as np
n_iter = 300
# Вариант 1
distances = np.array([[np.inf, 22, 50, 62, 67, 66, 63, 53, 43,60],
                      [22, np.inf, 30, 46, 74, 79, 78, 74, 56, 64],
                      [50, 30, np.inf, 21, 78, 88, 92, 104, 82, 89],
                      [62, 46, 21, np.inf, 66, 81, 85, 115, 102, 108],
                      [67, 74, 78, 66, np.inf, 20, 30, 95, 103, 125],
                      [66, 79, 88, 81, 20, np.inf, 11, 83, 95, 122],
                      [63, 78, 92, 85, 30, 11, np.inf, 73, 88, 116],
                      [53, 74, 104, 115, 95, 83, 73, np.inf, 31, 62],
                      [43, 56, 82, 102, 103, 95, 88, 31, np.inf, 32],
                      [60, 64, 89, 108, 125, 122, 116, 62, 32, np.inf]])

# Количество муравьев = количеству городов
n_ants = len(distances)
ant_colony = AntColony(distances, n_ants=n_ants, n_best=n_ants, 
                       n_iterations=n_iter, stamina=0.5, alpha=1, beta=1)
all_time_shortest_path, all_time_shortest_len = ant_colony.run()
print (f"\nСамый короткий путь за {n_iter} итераций: Path: {all_time_shortest_path}  
        Len: {all_time_shortest_len}")

Основной код программы

Определяется класс муравьиной колонии AntColony, с его свойствами и методами.

Основной цикл работы программы оформлен в виде функции класса run.

import random as rn
import numpy as np
from numpy.random import choice as np_choice

class AntColony(object):
    def __init__(self, distances, n_ants, n_best, n_iterations, stamina, alpha=1, beta=1):
        """
        Аргументы:
            distances (2D numpy.array): Квадратная матрица расстояний. 
            По диагонали стоит np.inf = плюс бесконечность
            n_ants (int): Число муравьев в каждой итерации
            n_best (int): Число удачливых муравьев, оставивших феромон
            n_iteration (int): Номер итерации
            stamina (float): Стойкость феромона к испарению [0, 1]. 
            Это доля оставшегося феромона. 
            Чем меньше число, тем быстрее он испаряется.
            alpha (int или float): Сила (вес) феромона [0, 1]. По умолчанию = 1
            beta (int или float): Вес расстояния. По умолчанию = 1
        """
        self.distances  = distances
        self.pheromone = np.ones(self.distances.shape) / len(distances)
        self.path = np.matrix(np.ones((n_ants,n_ants)) * np.inf)
        self.visited = []
        self.all_inds = range(len(distances))
        self.n_ants = n_ants
        self.n_best = n_best
        self.n_iterations = n_iterations
        self.stamina = stamina
        self.alpha = alpha
        self.beta = beta

    # Оставить феромон на ребре графа и пересчитать
    def spread_pheromone(self, all_paths, n_best, shortest_path):
        sorted_paths = sorted(all_paths, key=lambda x: x[1])
        for path, dist in sorted_paths[:n_best]:
            for move in path:
                self.pheromone[move] += 1.0 / self.distances[move]

    # Получить расстояние между городами
    def get_path_dist(self, path):
        total_dist = 0
        for ele in path:
            total_dist += self.distances[ele]
        return total_dist

    # Выбор города для перехода
    def pick_move(self, pheromone, dist, visited):
        pheromone = np.copy(pheromone)
        pheromone[list(visited)] = 0

        val = pheromone ** self.alpha * (( 1.0 / dist) ** self.beta)

        norm_val = val / val.sum()
        # Случайный выбор (рулетка)
        move = np_choice(self.all_inds, 1, p=norm_val)[0]

        return move

    # Получить путь одного муравья
    def gen_path(self, start):
        path = []
        cities_visited = []
        visited = set()
        visited.add(start)
        cities_visited.append(start)
        prev = start
        for i in range(len(self.distances) - 1):
            move = self.pick_move(self.pheromone[prev], self.distances[prev], cities_visited)
            path.append((prev, move))
            prev = move
            visited.add(move)
            cities_visited.append(move)
        path.append((prev, start)) # going back to where we started
        path_dist = self.get_path_dist((path))
        self.visited = cities_visited

        return path, path_dist, cities_visited

    # Получить пути всех муравьев
    def gen_all_paths(self):
        all_paths = []
        all_dist = []
        all_visits = []
        for i in range(self.n_ants):
            path, dist, visited = self.gen_path(i)
            all_paths.append((path, dist))
            all_dist.append(dist)
            all_visits.append(visited)
        return all_paths, all_dist, all_visits

    # Основной цикл расчета
    def run(self):
        shortest_len = None
        all_time_shortest_len = 999999999
        all_time_shortest_path = ("placeholder", np.inf)
        for i in range(self.n_iterations):
            iter_paths, iter_dist, iter_visits = self.gen_all_paths()
            shortest_len = min(iter_dist)
            min_len_index = np.argmin(iter_dist)
            shortest_path = min(iter_paths)
            self.spread_pheronome(iter_paths, self.n_best, shortest_path=shortest_path)
            shortest_path = iter_visits[min_len_index]
            shortest_len = iter_dist[min_len_index]

            if shortest_len < all_time_shortest_len:
                all_time_shortest_len = shortest_len
                all_time_shortest_path = shortest_path
                print(f"Кратчайший путь в итерации:  {i+1}  Path: {shortest_path} Len: {shortest_len}")
            self.pheromone = self.pheromone * self.stamina
        return all_time_shortest_path, all_time_shortest_len

Результат выполнения программы

Приведен журнал выполнения кода.

Кратчайший путь в итерации:  1  Path: [2, 3, 0, 1, 4, 5, 6, 7, 8, 9] Len: 435.0
Кратчайший путь в итерации:  2  Path: [8, 0, 1, 2, 3, 5, 6, 4, 7, 9] Len: 427.0
Кратчайший путь в итерации:  3  Path: [4, 5, 6, 8, 9, 7, 0, 1, 2, 3] Len: 405.0
Кратчайший путь в итерации:  6  Path: [8, 7, 0, 1, 2, 3, 4, 5, 6, 9] Len: 402.0
Кратчайший путь в итерации:  9  Path: [7, 8, 9, 0, 1, 2, 3, 4, 5, 6] Len: 366.0

Самый короткий путь за 300 итераций: Path: [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]  Len: 366.0

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

Конечно, количество городов очень маленькое. Но сам алгоритм отрабатывает очень эффективно.

Применение муравьиного алгоритма

1. Оптимизация маршрутизации в компьютерных, телекоммуникационных сетях или сетях передачи данных. Алгоритм помогает в поиске оптимального пути для передачи информации, учитывая различные факторы, такие как пропускная способность, задержка и стоимость связи.
2. Решение задачи коммивояжера — задачи нахождения кратчайшего пути, проходящего через все заданные города и возвращающегося в исходный город. Он может быть применен в логистике, транспортировке грузов, планировании маршрутов доставки и других задачах, где требуется планирование оптимального пути.

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

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

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

5. Оптимизация маршрутов транспорта в логистических цепочках. Алгоритм может помочь в нахождении оптимальных маршрутов доставки грузов или планировании маршрутов транспортных средств для снижения времени и затрат на доставку.

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

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

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

В заключение

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