search_tour_ants {gor}

Ant colony optimization algorithm for the TSP

Description

Ant colony optimization (ACO) heuristic algorithm to search for a low-distance tour of a TSP instance. ACO is a random algorithm; as such, it yields better results when longer searches are run. To guess the adequate parameter values resulting in better performance in particular instances requires some experimentation, since no universal values of the parameters seem to be appropriate to all examples.

Usage

search_tour_ants(
  d,
  n,
  K = 200,
  N = 50,
  beta = 3,
  alpha = 5,
  dt = 1,
  rho = 0.05,
  log = FALSE
)

Arguments

d

Distance matrix of the TSP instance.

n

Number of vertices of the complete TSP graph. It can be less than the number of rows of the distance matrix d.

K

Number of tour-searching ants. Defaults to 200.

N

Number of iterations. Defaults to 50.

beta

Inverse temperature which determines the thermal probability in selecting the next vertex in tour. High beta (low temperature) rewards lower distances (and thus it gets stuck sooner in local minima), while low beta (high temperature) rewards longer tours, thus escaping from local minima. Defaults to 3.

alpha

Exponent enhancing the pheromone trail. High alpha means a clearer trail, low alpha means more options. It defaults to 5.

dt

Basic pheromone enhancement at each iteration. It defaults to 1.

rho

Parameter in the (0,1) interval controlling pheromone evaporation rate. Pheromones of the chosen tour increase in dt*rho, while excluded pheromones diminish in 1-rho. A rho value near 1 means select just one tour, while lower values of rho spread the probability and more tours can be explored. It defaults to 0.05.

log

Boolean. When TRUE, it also outputs two vectos recording the performance of the algorithm. It defaults to FALSE.

Details

ACO is an optimization paradigm that tries to replicate the behavior of a colony of ants when looking for food. Ants leave after them a soft pheromone trail to help others follow the path just in case some food has been found. Pheromones evaporate, but following again the trail reinforces it, making it easier to find and follow. Thus, a team of ants search a tour in a TSP instance, leaving a pheromone trail on the edges of the tour. At each step, each ant decides the next step based on the pheromone level and on the distance of each neighboring edge. In a single iteration, each ant completes a tour, and the best tour is recorded. Then the pheromone level of the edges of the best tour are enhanced, and the remaining pheromones evaporate.

Default parameter values have been chosen in order to find the optimum in the examples considered below. However, it cannot be guarateed that this is the best choice for all cases. Keep in mind that no polynomial time exact algorithm can exist for the TSP, and thus harder instances will require to fine-tune the parameters. In any case, no guarantee of optimality of tours found by this method can be given, so they might be improved further by other methods.

Value

A list with two components: $tour contains a permutation of the 1:n sequence representing the tour constructed by the algorithm, $distance contains the value of the distance covered by the tour. When log=TRUE, the output list contains also the component $Lant, best tour distance found in the current iteration, and component $Lopt, best tour distance found before and including the current iteration.

Author(s)

Cesar Asensio

See Also

compute_distance_matrix computes matrix distances using 2d points, improve_tour_2opt improves a tour using 2-exchanges, plot_tour draws a tour

Examples

## Regular example with obvious solution (minimum distance 32)
m <- 6   # Generate some points in the plane
z <- cbind(c(rep(0,m), rep(2,m), rep(5,m), rep(7,m)), rep(seq(0,m-1),4))
n <- nrow(z)
d <- compute_distance_matrix(z)
set.seed(2)
b <- search_tour_ants(d, n, K = 70, N = 20)
b$distance    # Distance 32 (optimum)
plot_tour(z,b)

## Random points
set.seed(1)
n <- 15
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
b <- search_tour_ants(d, n, K = 50, N = 20)
b$distance    # Distance 32.48669 
plot_tour(z,b)