Search code examples
python-3.xnumpygenetic-algorithmtraveling-salesman

"unique" crossover for genetic algorithm - TSP

I am creating a Genetic Algorithm to solve the Traveling Salesman Problem.

Currently, two 2D lists represent the two parents that need to be crossed:

path_1 = np.shuffle(np.arange(12).reshape(6, 2))
path_2 = np.arange(12).reshape(6,2)

Suppose each element in the list represents an (x, y) coordinate on a cartesian plane, and the 2D list represents the path that the "traveling salesman" must take (from index 0 to index -1).

Since the TSP requires that all points are included in a path, the resulting child of this crossover must have no duplicate points.

I have little idea as to how I can make such crossover and have the resulting child representative of both parents.

Solution

  • You need to use an ordered crossover operator, like OX1.

    OX1 is a fairly simple permutation crossover. Basically, a swath of consecutive alleles from parent 1 drops down, and remaining values are placed in the child in the order which they appear in parent 2.

    I used to run TSP with these operators: