Комментарии 0
...комментариев пока нет
Муравьиный алгоритм | Задача коммивояжёра
Для того, чтобы реализовать алгоритм нам нужны виртуальные муравьи и виртуальная колония муравьев. Тажке нужна будет структура данных, для удобного хранения пути и длины пути, пройденного муравьем.
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;
}- Последовательно для каждого муравья, пока он может продолжать, выбираем ему следующую вершину.
- Если он посетил все вершины, то в случае того, что текущий найденный путь длиннее пути, найденного муравьем, мы обновляем текущий путь и обнуляем счетчик.
- Счетчик нужен для того, чтобы при нахождении нового (более короткого пути) алгоритм еще немного поработал, чтобы была возможность найти еще более короткий путь.
- Вспомним условие, что феромоны откладывают только те муравьи, которые выполнили поставленную задачу, поэтому на локальное обновление феромона влияют только такие муравьи.