crossover_tours {gor}

Crossover operation used by the TSP genetic algorithm

Description

Crossover operation used by the TSP genetic algorithm. It takes two tours and it computes two "offsprings" trying to exploit the structure of the cycles, see below.

Usage

crossover_tours(C1, C2, d, n)

Arguments

C1

Vertex numeric vector of the first parent tour.

C2

Vertex numeric vector of the second parent tour.

d

Distance matrix of the TSP instance. It is used in the computation of the low-weight perfect matching.

n

The number of vertices of the TSP complete graph.

Details

In the genetic algorithm, the crossover operation is a generalization of local search in which two tours are combined somehow to produce two tours, hopefully different from their parents and with better fitting function values. Crossover widens the search while trying to keep the good peculiarities of the parents. However, in practice crossover almost never lowers the fitting function when parents are near the optimum, but it helps to explore new routes. Therefore, it is always a good idea to complement crossover with some deterministic local search procedure which can find another local optima; crossover also helps in evading local minima.

In this routine, crossover is performed as follows. Firstly, the edges of the parents are combined in a single graph, and the repeated edges are eliminated. Then, the odd degree vertices of the resulting graph are matched looking for a low-weight perfect matching using a greedy algorithm. Adding the matching to the previous graph yields an Eulerian graph, as in Christofides algorithm, whose final step leads to the first offspring tour. The second tour is constructed by recording the second visit of each vertex by the Eulerian walk, and completing the resulting partial tour with the nearest neighbor heuristic.

Value

A two-row matrix containing the two offsprings as vertex numeric vectors.

Author(s)

Cesar Asensio

See Also

search_tour_genetic implements a version of the genetic algorithm for the TSP.

Examples

set.seed(1)
n <- 25
z <- cbind(runif(n,min=1,max=10),runif(n,min=1,max=10))
d <- compute_distance_matrix(z)
c1 <- sample(1:n)
c2 <- sample(1:n)
c12 <- crossover_tours(c1, c2, d, n)
compute_tour_distance(c1, d)        # 114.5848
compute_tour_distance(c2, d)        # 112.8995
compute_tour_distance(c12[1,], d)   # 116.3589
compute_tour_distance(c12[2,], d)   # 111.5184