Ant algorithm. Solving the traveling salesman problem
In this article, I would like to explain the working of the ant algorithm and solve the traveling salesman problem with its help. The solution to the problem comes down to exiting any vertex of the graph, going through all the vertices one at a time using the shortest path, and returning to the starting point. At the end of the article you will find an implementation of the algorithm in Go.
Brute force method
The easiest way to solve this problem is by brute force. Only this method is suitable for a small number of vertices. As the growth of vertices increases, the computational complexity increases many times over, and at some point we simply won’t have enough of them to solve the problem using this method.
Operating principles of the ant algorithm
When an ant runs towards a target, it is guided by two parameters: range and the amount of pheromone deposited by the previous generation of ants. The closer the nearest point is and the more pheromone deposited on the road, the more likely he is to follow this path. We use a probabilistic approach.
P is the probability of choosing from a path from the current vertex i to the next vertex j.
n is the inverse parameter of the distance between cities from the current vertex i to the next vertex j. (see following formula)
t is the amount of pheromone from the current vertex i to the next vertex j.
b is a parameter that allows you to adjust the algorithm by distance. The larger the value, the greater the influence of the amount of pheromone on the choice of direction; at b = 0.0 it will not be taken into account at all.
a is a parameter that allows you to adjust the algorithm according to the amount of pheromone. The larger the value, the greater the influence of distance on the choice of direction; with a = 0.0 it will not be taken into account at all.
Σ (n^b + t^a) is the sum of all distances and pheromones of unvisited vertices from the current vertex i to the next vertex j.
Algorithm explanation
Main function SolveTravelingSalesmanProblem. It calls auxiliary functions and returns us the best path, its visited vertices and the length of the route.
Main loop
In it, we simply run 100 iterations of our algorithm in order to find the best solution during this time. With each iteration we select the best path.
Cycle through an ant colony
In it we launch one ant from each vertex of the graph. This allows us to distribute the pheromone evenly along the entire path and increase the variety of solutions. If we launch ants constantly from the same vertex, we will reinforce the same paths.
Path building cycle
In it, we track the path of a specific ant along the entire route until all vertices are visited, starting and finishing at the starting point. Each ant chooses the next vertex based on probability (see formula for finding P).
Pheromone update (updateDistanceMatrix)
After the ant passes along its path, we update the pheromone on the passed edges, thereby strengthening the short path. It is worth noting that the more ants pass along a given path, the more pheromone will be on it. Runs after each ant passes.
Evaporation of pheromones (evaporatePheromones)
We reduce the amount of pheromones on all edges. Thus, we reduce the gain of one path and give the opportunity to be found by other paths. Triggers after passing the entire ant colony.
Adding new trails (addNewTrails)
Adding a pheromone based on the path taken reduces solution stagnation and helps find new paths. Triggers after passing the entire ant colony. We strengthen the current path so that the next colony takes it into account.
Description of the algorithm
Graph structure
// Graph представляет граф с матрицей смежности
type Graph struct {
adjacencyMatrix [][]int
}// NewGraph создает новый граф
func NewGraph(vertexCount int) *Graph {
matrix := make([][]int, vertexCount)
for i := range matrix {
matrix[i] = make([]int, vertexCount)
}
return &Graph{adjacencyMatrix: matrix}
}// AddEdge добавляет ребро в граф
func (g *Graph) AddEdge(from, to, weight int) {
if from < 0 || from >= len(g.adjacencyMatrix) || to < 0 || to >= len(g.adjacencyMatrix[from]) {
// Индексы вне диапазона, ничего не делаем
return
}
g.adjacencyMatrix[from][to] = weight
}Constants
const (
alpha = 9.0 // регулировка алгоритма по расстоянию (чем больше значение, тем большее будет влияние расстояния на выбор направления, при alpha = 0.0 вообще не будет учитываться)
beta = 5.0 // регулировка алгоритма по количеству феромона (чем больше значение, тем большее будет влияние количества феромона на выбор направления, при beta = 0.0 вообще не будет учитываться)
p = 0.7 // скорость испарения феромона
)Main function
// SolveTravelingSalesmanProblem решает задачу коммивояжера с использованием муравьиного алгоритма
func SolveTravelingSalesmanProblem(graph *graph.Graph) TsmResult {
distanceMatrix := graph.GetAdjacencyMatrix()
n = len(distanceMatrix)
Q = 5 * float64(n)
// Координаты вершин
pheromones := initPheromones() // Wt След
deltaPheromones := initDeltaPheromones() // DWt Матрица приращений следа
Lmin := math.MaxFloat64 // начальное значение длины - infinity
bestPath := make([]int, n+1) // n+1 для возврата в исходную точку
for k := 0; k < 100; k++ { // Основной цикл
for ant := 0; ant < n; ant++ { // Цикл по муравьям
visited := make([]bool, n) // Список непосещенных вершин
currentCity := ant // Начальная вершина для муравья ant
visited[currentCity] = true
path := []int{currentCity} // Начало пути
for len(path) < n { // Цикл построения пути
probabilities := calculateProbabilities(pheromones, distanceMatrix, currentCity, visited) // Каждой вершине - свой вес
nextCity := selectNextCity(probabilities) // Выбор направления
visited[nextCity] = true // Tabu list увеличился
path = append(path, nextCity)
currentCity = nextCity // Начало дуги = конец предыдущей
}
path = append(path, path[0]) // Конец пути (возвращаемся в исходную точку)
// проходимся по всему пути и суммируем длины
L := calculatePathLength(path, distanceMatrix)
// Проверка минимальной длины пути
if L < Lmin {
Lmin = L
copy(bestPath, path)
}
// Пометка дуг феромоном
updateDistanceMatrix(deltaPheromones, path, L)
}
evaporatePheromones(pheromones, p) // Испарение феромонов
addNewTrails(pheromones, deltaPheromones, p) // Добавление новых следов
}
return TsmResult{
Vertices: bestPath,
Distance: Lmin,
}
}Pheromone update
// updateDistanceMatrix помечает дуги феромоном
func updateDistanceMatrix(deltaPheromones [][]float64, path []int, L float64) {
for i := 0; i < len(path)-1; i++ {
from := path[i]
to := path[i+1]
deltaPheromones[from][to] += Q / L
}
}Pheromone evaporation
// Испарение феромона
func evaporatePheromones(pheromones [][]float64, p float64) {
for i := range pheromones {
for j := range pheromones[i] {
pheromones[i][j] *= (1 - p)
}
}
}Adding new tracks
// Добавление новых следов
func addNewTrails(pheromones, deltaPheromones [][]float64, p float64) {
for i := range pheromones {
for j := range pheromones[i] {
pheromones[i][j] += deltaPheromones[i][j] * p
}
}
}Useful materials
Conclusion
The ant algorithm is an effective method for solving the traveling salesman problem, especially when the number of vertices is large and the brute force method becomes impractical. Using a probabilistic approach and a pheromone mechanism, the algorithm allows one to find approximate solutions that can be very close to optimal.
A complete and detailed description of the algorithm's operation can be found in my GitHub.
