search_tour_genetic {gor}

Genetic Algorithm for the TSP

Description

Genetic algorithm for TSP. In addition to crossover and mutation, which are described below, the algorithm performs also 2-opt local search on offsprings and mutants. In this way, this algorithm is at least as good as chained 2-opt search.

Usage

search_tour_genetic(
  d,
  n,
  Npop = 20,
  Ngen = 50,
  beta = 1,
  elite = 2,
  Pini = NA,
  local = 1,
  verb = TRUE,
  log = FALSE
)

Arguments

d

Distance matrix of the TSP instance.

n

Number of vertices of the TSP complete graph.

Npop

Population size.

Ngen

Number of generations (iterations of the algorithm).

beta

Control parameter of the crossing and selection probabilities. It defaults to 1.

elite

Number of better fitted individuals to pass on to the next generation. It defaults to 2.

Pini

Initial population. If it is NA, a random initial population of Npop individuals is generated. Otherwise, it should be a matrix; each row should be an individual (a permutation of the 1:n sequence) and then Npop is set to the number of rows of Pini. This option allows to chain several runs of the genetic algorithm, which could be needed in the hardest cases.

local

Average fraction of parents + offsprings + mutants that will be taken as starting tours by the local search algorithm improve_tour_2opt. It should be a number between 0 and 1. It defauls to 1.

verb

Boolean to activate console echo. It defaults to TRUE.

log

Boolean to activate the recording of the distances of all tours found by the algorithm. It defaults to FALSE.

Details

The genetic algorithm consists of starting with a tour population, which can be provided by the user or can be random. The initial population can be the output of a previous run of the genetic algorithm, thus allowing a chained execution. Then the routine sequentially perform over the tours of the population the crossover, mutation, local search and selection operations.

The crossover operation takes two tours and forms two offsprings trying to exploit the good structure of the parents; see crossover_tours for more information.

The mutation operation performs a "small" perturbation of each tour trying to escape from local optima. It uses a random 4-exchange, see perturb_tour_4exc and search_tour_chain2opt for more information.

The local search operation takes the tours found by the crossover and mutation operations and improves them using the 2-opt local search heuristic, see improve_tour_2opt. This makes this algorithm at least as good as chained local search, see search_tour_chain2opt.

The selection operation is used when selecting pairs of parents for crossover and when selecting individuals to form the population for the next generation. In both cases, it uses a probability exponential in the distance with rate parameter "beta", favouring the better fitted to be selected. Lower values of beta favours the inclusion of tours with worse fitting function values. When selecting the next population, the selection uses elitism, which is to save the best fitted individuals to the next generation; this is controlled with parameter "elite".

The usefulness of the crossover and mutation operations stems from its abitily to escape from the 2-opt local minima in a way akin to the perturbation used in chained local search search_tour_chain2opt. Of course, more iterations (Ngen) and larger populations (Npop) might lower the result, but recall that no random algorithm can guarantee to find the optimum of a given TSP instance.

This algorithm calls many times the routines crossover_tours, improve_tour_2opt and perturb_tour_4exc; therefore, it is not especially efficient when called on large problems or with high populations of many generations. Input parameter "local" can be used to randomly select which tours will start local search, thus diminishing the run time of the algorithm. Please consider chaining the algorithm: perform short runs, using the output of a run as the input of the next.

Value

A list with four 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, $generation contains the generation is which the minimum was found and $population contains the final tour population. When log=TRUE, the output includes several lists of distances of tours found by the algorithm, separated by initial tours, offsprings, mutants, local minima and selected tours.

Author(s)

Cesar Asensio

References

Hromkovic Algorithms for hard problems (2004), Hartmann, Weigt, Phase transitions in combinatorial optimization problems (2005).

See Also

crossover_tours performs the crosover of two tours, gauge_tour transforms a tour into a canonical sequence for comparison, search_tour_chain2opt performs a chained 2-opt search, perturb_tour_4exc transforms a tour using a random 4-exchange, improve_tour_2opt improves a tour using the 2-opt algorithm, improve_tour_3opt improves a tour using the 3-opt algorithm, build_tour_nn_best nearest neighbor heuristic, build_tour_2tree double-tree heuristic, compute_tour_distance computes tour distances, compute_distance_matrix computes a distance matrix, plot_tour plots 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)
bc <- search_tour_genetic(d, n, Npop = 5, Ngen = 3, local = 0.2)
bc     # Distance 32
plot_tour(z,bc)

## 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)
bg <- search_tour_genetic(d, n, 5, 3, local = 0.25)
bg     # Distance 32.48669
plot_tour(z,bg)