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.

  1. Levenshtein distance, which is simply 'how many atomic edits are two sequences removed from each other.
  2. 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.

  • 1
    $\begingroup$ As you state, there are multiple ways of comparing to solutions and thus their distance. Which is more appropriate depends on what your goal is. $\endgroup$ – Juho Nov 22 '20 at 20:34
  • $\begingroup$ Well, my ultimate goal is finding the best solution (i.e., the one with the smallest route length). The reason for implementing this distance metric is so I can use it in either a crowding step (for each best solution I select, remove the most similar one from the selection pool so it cannot be selected), or a fitness sharing algorithm (penalise solutions based on their proximity to other solutions). $\endgroup$ – Inkidu616 Nov 22 '20 at 20:38
  • 1
    $\begingroup$ I doubt that we will be able to predict which of these will make your genetic algorithm most effective. That requires experimentation and trial-and-error. $\endgroup$ – D.W. Nov 22 '20 at 21:54
  • 1
    $\begingroup$ Cross-posted: stackoverflow.com/q/64959096/781723, cs.stackexchange.com/q/132544/755. Please do not post the same question on multiple sites. Thank you! $\endgroup$ – D.W. Nov 22 '20 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.