I'm designing a genetic algorithm to solve the travelling salesman problem. So far, I've gotten fairly good results. I'm now trying to improve on them by implementing some sort of diversification scheme (like fitness sharing and crowding), although I'm struggling with the conceptualisation of the inter-solution distance a bit.
Solutions represent a path that goes through all cities, i.e. a permutation of the order in which they are visited. This is represented in my code by np.arrays. If I want to know how similar two solutions are, I basically want to find the distance between two permutations of n_cities elements. I currently have two ideas for the distance function.
- Levenshtein distance, which is simply 'how many atomic edits are two sequences removed from each other.
- Hamming distance, which denotes the number of positions that are the same.
Note that, for each solution, I make sure to cycle it so it starts in the same position (city). Otherwise these metrics won't make sense.
Which of them is more appropriate? Is there a better solution? I've browsed a number of articles, but haven't really found an answer yet.