• Муравьиный алгоритм — это алгоритм оптимизации, вдохновленный поведением муравьев при поиске пути от места к месту. Он используется для решения комбинаторных задач, в частности задачи коммивояжера. В алгоритме создается множество виртуальных муравьев, которые последовательно принимают решения о выборе следующего города для посещения на основе локальной информации о расстояниях и феромонах.
• Каждый муравей рассчитывает вероятность перехода в следующий город на основе феромонов, которые выпускаются на путях, и на основе эвристической информации, такой как расстояние или привлекательность. Муравьи выбирают путь с большей вероятностью и обновляют феромоны, основываясь на качестве выбранного пути.
• В процессе итераций муравьи обновляют пути согласно найденным лучшим решениям, что позволяет улучшать глобальное решение со временем. Муравьиный алгоритм позволяет достичь хорошего приближения к оптимальному решению задачи коммивояжера и другим комбинаторным задачам, используя коллективный интеллект и феромоны виртуальных муравьев для поиска оптимального пути.
• Держите красивое изображение муравьев, сгенерированное при помощи LeonardoAI

• Для того чтобы хранить города и расстояния между ними (вершины и ребра) будем использовать структуру данных Граф.
• Для представления графа будем использовать матрицу смежности, поэтому нужна структура данных Матрица.

Представление графа позволит нам знать количество вершин, количество ребер, и позволит узнавать есть ли ребро между вершинами V1 и V2

Основы муравьиного алгоритма.

• Муравьиный алгоритм работает поэтапно. Основные этапы муравьиного алгоритма:

1. Инициализация. Создается колония виртуальных муравьев, обычно количество муравьев делают равным количеству вершин в графе. Инициализируется стартовое положение каждого муравья. Все рёбра инициализируются начальным количеством феромона.
2. Поиск решения. Муравьи отправляются в свободное путешествие. Муравей последовательно посещает вершины, пока не попадет в тупик или не дойдет до стартовой вершины. Решения муравья зависит от раскиданного феромона и расстояний до вершин.
3. Локальное обновление феромонов. В зависимости от того, выполнил ли муравей поставленную задачу, напрямую зависит, будет ли он откладывать феромоны. Если задача не выполнена, то муравей не оставляет феромоны на своем пути, иначе муравей, в зависимости от длины своего пути, оставляет на своем пути феромоны. Это позволяет усилить путь для будущих муравьев и учитывать локальную информацию о качестве пути.
4. Определение лучшего решения. Если муравей выполнил поставленную задачу, его путь и длина этого пути сохраняется. (Если конечно длина этого пути, короче уже имеющегося)
5. Глобальное обновление феромонов. После того, как все муравьи завершат свою работу, делается глобальное обновление феромонов, которое учитывает локальное обновление феромона и испарение феромона.
6. Повторение. Процесс построения решений и обновления феромонов повторяется заданное количество раз или до достижения критерия остановки. После каждого прогона муравьев качество решения обычно улучшается.

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

Используемые формулы и объяснение

• Вероятность перехода муравья из одной вершины в другую

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

• Локальное обновление феромона

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

• Глобальное обновление феромона

Количество феромона на ребре между вершинами i и j на новой итерации равно количеству феромона на текущей итерации, умноженное на коэффициент испарения + локальное обновление феромона на ребре между вершинами i и j

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

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

struct AntPath {
    std::vector<std::size_t> vertices;
    double distance = 0;
};

struct Ant {
     explicit Ant(std::size_t start_vertex = 0);

     AntPath path;

     std::vector<std::size_t> visited;
     std::size_t start_location = 0, current_location = 0;
     bool can_continue = true;

     void MakeChoice(const Graph<double> &g, const Matrix<double> &p, double a, double b);
     double getRandomChoice();
     std::vector<std::size_t> getNeighborVertexes(const Graph<double> &g)
};

class AntColonyOptimization {
public:
    explicit AntColonyOptimization(const Graph<double> &graph);

    AntPath SolveSalesmansProblem();

private:
    const double kAlpha_ = 1.0;
    const double kBeta_ = 2.0;
    const double kPheromone0_ = 1;
    const double kQ_ = 5.0;
    const double kEvaporation_ = 0.2;

    Graph<double> graph_;
    Matrix<double> pheromone_;

    std::vector<Ant> ants_;

    void CreateAnts();
    void UpdateGlobalPheromone(const Matrix<double> &local_pheromone_update);
};

AntColonyOptimization class

• Основной метод называется SolveSalesmansProblem, будет возвращать самый выгодный путь, найденный муравьями.
• Коэффициенты kAlpha kBeta kPheromone0, kQ, kEvaporation определяются и подбираются опытным путем под каждую задачу
• Класс AntColonyOptimization будет конструироваться от графа, в котором нужно решить задачу коммивояжёра.
• Метод CreateAnts будет создавать муравьев и задавать начальную инициализацию каждому муравью
• Метод UpdateGlobalPheromone делает глобальное обновление феромона, приминает на вход локальную соостовляющую обновления феромона.

Ant struct

• Конструируется от стартовой вершины.
• Хранит в себе структуру AntPath для удобного хранения пройденного пути и длины пройденного пути
• Поле visited будет хранить посещенные вершины муравьев, для того чтобы повторно не посещать уже пройденные вершины.
• start_location — начальная вершина (вершина старта) муравья, current_location — текущее положение муравья

Конструктор AntColonyOptimization

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

AntColonyOptimization::AntColonyOptimization(const Graph<double> &graph)
        : graph_(graph), kQ_(0.015 * graph.getGraphWeight()) {
   const std::size_t kVertexesCount = graph_.getVertexesCount();
   Matrix<double> matrix(kVertexesCount);
   for (std::size_t row = 0; row != kVertexesCount; ++row)
       for (std::size_t col = 0; col != kVertexesCount; ++col)
           if (row != col) matrix(row, col) = kPheromone0_;

   pheromone_ = std::move(matrix);
}

Реализация основных методов

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

void AntColonyOptimization::CreateAnts() {
    const auto kAntsCount = graph_.getVertexesCount();
    ants_.resize(kAntsCount);

    for (std::size_t i = 0, size = ants_.size(); i != size; ++i)
        ants_[i] = Ant(i);
}

Метод глобального обновления феромона

• Добавил ограничение на испарение феромона, пусть минимально возможным количеством феромона не ребре будет 0.01

void AntColonyOptimization::UpdateGlobalPheromone(const Matrix<double> &lpu) {
    // lpu - local pheromone update
    for (std::size_t from = 0, size = lpu.getRows(); from != size; ++from) {
        for (std::size_t to = 0; to != size; ++to) {
            pheromone_(from, to) = (1 - kEvaporation_) * pheromone_(from, to) + lpu(from, to);
            if (pheromone_(from, to) < 0.01 and from != to)
                pheromone_(from, to) = 0.01;
        }
    }
}

Метод генерация случайного числа для вероятности
Так как вероятность — это число в пределах [0, 1], генерировать будем в этих же пределах

double Ant::getRandomChoice() {
    std::uniform_real_distribution<> dist(0.0, 1.0);
    std::default_random_engine re(system_clock::now().time_since_epoch().count());
    return dist(re);
}

Метод получения возможных для посещения вершин от текущего положения

std::vector<std::size_t> Ant::getNeighborVertexes(const Graph<double> &g) {
    std::vector<std::size_t> vertexes;
    for (std::size_t to = 0; to != graph.getVertexesCount(); ++to) {
         bool edge_is_exist = g(current_location, to) != 0;
         bool vertex_is_unvisited = std::find(visited.begin(), visited.end(), to) == visited.end()
         if (edge_is_exist and vertex_is_unvisited)
              vertexes.push_back(to);
    }
    return vertexes;   
}

Метод выбора следующей вершины

void Ant::MakeChoice(const Graph<T> &g, const Matrix<double> &p, double a, double b) {
    if (path.vertices.empty()) {
        path.vertices.push_back(current_location);
        visited.push_back(current_location);
    }

   std::vector<std::size_t> neighbor_vertexes = getNeighborVertexes(g);

   if (neighbor_vertexes.empty()) {
       can_continue = false;
       if (graph(current_location, start_location) != 0) {
           path.vertices.push_back(start_location);
           path.distance += graph(current_location, start_location);
       }
       return;
  }

   std::vector<double> choosing_probability(neighbor_vertexes.size());

   {
        // Подсчет вероятности перехода муравья из одной вершины в другую
        std::vector<double> wish;
        std::vector<double> probability; 
        double summary_wish = 0.0f;
        for (auto v : neighbor_vertexes) {
                double t = p(current_location, v);
                double w = g(current_location, v);
                double n = 1 / w;
                wish.push_back(std::pow(t, alpha) * std::pow(n, beta));
                summary_wish += wish.back();
       }

       for (std::size_t neighbor = 0; neighbor != neighbor_vertexes.size(); ++neighbor) {
           probability.push_back(wish[neighbor] / summary_wish);
           if (neighbor == 0)
               choosing_probability[neighbor] = probability.back();
           else
               choosing_probability[neighbor] = choosing_probability[neighbor - 1] + probability.back();
        }
   }

   // Определение следующей вершины, которую посетит муравей
   std::size_t next_vertex = 0;
   double choose = getRandomChoice();

   for (std::size_t n = 0; n != neighbor_vertexes.size(); ++n ) {
       if (choose <= choosing_probability[n ]) {
           next_vertex = neighbor_vertexes[n ];
           break;
       }
   }

   path.vertices.push_back(next_vertex);
   path.distance += graph(current_location, next_vertex);
   visited.push_back(next_vertex);
   current_location = next_vertex;
}

• choosing_probability — это массив, который представляет из себя следующее:
  Допустим есть три возможные вершины для посещения и вероятности их посетить равны соответственно {0.2 0.5 0.3}
  Таким образом в массиве choosing_probability будет лежать {0.2 0.7 1.0} — это нужно для того, можно было выбрать следующую вершину, сгенерировав случайное число от 0 до 1.
• wish это массив желаний муравья, отвечающий за числитель в формуле "Вероятность перехода муравья из вершины i в j"
• summary_wish отвечает за знаменатель в этой же формуле.

Главный метод, объединяющий функционал и решающий задачу коммивояжёра

AntPath AntColonyOptimization::SolveSalesmansProblem() {
    if (graph_.IsEmpty())
         return {};

    constexpr std::size_t kMaxIterationsWithoutImprovement = 100;
    const std::size_t kVertexesCount = graph_.getVertexesCount();
    std::size_t counter = 0;

    AntPath path;
    path.distance = kInf<double>;

    while (counter++ != kMaxIterationsWithoutImprovement) {
        Matrix<double> local_pheromone_update(kVertexesCount, 0.0);
        CreateAnts();

        for (auto &ant : ants_) {
            while (ant.can_continue)
                ant.MakeChoice(graph_, pheromone_, kAlpha_, kBeta_);

            auto ant_path = ant.path;
            if (ant_path.vertices.size() == kVertexesCount + 1) {
                 if (path.distance > ant.path.distance) {
                     path = std::move(ant.path);
                     counter = 0;
                }

                for (std::size_t v = 0; v != ant_path.vertices.size() - 1; ++v)
                    local_pheromone_update(ant_path.vertices[v], ant_path.vertices[v + 1]) += kQ_ / ant_path.distance;
            }
        }
        UpdateGlobalPheromone(local_pheromone_update);
    }
    return path;
}

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