Introducing a hash function for the travelling salesman problem for differentiating solutions
Mehdi El Krari, Rym Nesrine Guibadj, John Robert Woodward, Denis Robilliard · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2021
Solution comparison is a process used in different classes of evolutionary algorithms. It can be either for choosing a better solution or differentiating a pair of solutions. While there is no doubt that the fitness function allows determining the best solution, its use to distinguish between solutions is questionable, especially for combinatorial optimisation problems. This short paper focuses on the Travelling Salesman Problem (TSP). 39 instances of the TSPLIB are chosen, two solution samples are generated for each instance. A collision analysis of the fitness function one the TSP is presented, then an introduction to an efficient hash function with almost zero collisions.