CODEWITHSUNDEEP
algorithmmatlabcomputer-sciencegenetic-algorithmtraveling-salesman
MaartenVL
MaartenVL

Reputation: 3

TSP Genetic Algorithm - path representation and identical tour problem

We are implementing path representation to solve our travelling salesman problem using a genetic algorithm. However, we were wondering how to solve the issue that there might be identical tours in our individuals, but which are recognised by the path representation as different individuals. An example:

Example image

Each individual consists of an array, in which the elements are the cities visited in order.

Individual 1:
[1 2 3 4 5]

Individual 2:
[4 5 1 2 3]

You can see that the tour in 1 and 2 are actually identical, only the "starting" location is different.

We see some solutions to this problem, but we were wondering which one would be the best, or if there are best practices to overcome this problem from literature/experiments/....

Solution 1

Sort each individual to see if the individuals are identical:

 1. pick an individual
 2. shift the elements by 1 element to the right (at the end of the array, elements are placed at the beginning of the array)
 3. check if this shift now matches an individual
 4. if not, repeat steps 3 to 4

Solution 2

1. At the start if the simulations, choose a fixed starting point of the cities.
2. If the fixed starting point would change (mutation, recombination,...) then
3. Shift the array so that chosen starting point is back on first index.

Solution 3

1. Use the adjacency representation to check which individuals are identical. 
2. Pass this information on to the path representation.
3. This is used to "correct" the individuals.

Solution 1 and 2 seem time consuming, although 2 would probably need much less computing time. Solution 3 would need to constantly switch from one to the other representation.

Then there is also the issue that in our example the tour can be read in 2 ways:

[1 2 3 4 5]

is the same as

[5 4 3 2 1]

Again here, are there any best practises the solve this?

Upvotes: 0

Views: 1005

Answers (1)

Nelfeal
Nelfeal

Reputation: 13269

Since you need to visit every city and return to the origin city, you can simply fix the origin. That solves your problem of shifted equivalent tours outright.

For the other, less important issue of mirrored tours, you can start by sorting your individuals by cost (which you probably already do), and check any pair of tours with equal costs using a simple palindrome-checking algorithm.

Upvotes: 1

Related Questions