Hash Functions for Combinatorial Optimisation Problems

Fitness functions are a measure of solution quality. However they fail to differentiate between different solutions with the same fitness, and this lack of ability to distinguish between solutions can have a detrimental effect on the search process. In this work, we investigate, for the Travelling Salesman Problem (TSP) (and soon other problems), the impact of using a hash function to differentiate solutions during the search process. We first introduce a new efficient hash function that minimises the risk of collision (two different permutations having identical hash values). We then analyse its impact on three different metaheuristics: Iterative Local Search (ILS), Genetic Algorithm (GA) and Memetic Algorithm (MA). Experiments conducted on the TSP show that the use of our hash function is more efficient to detect cycles in ILS and provides a more relevant convergence rate of a population in GA and MA. Whereas this work is not intended to provide an improvement over the state-of-the-art, it nevertheless reveals a positive effect when using the hash functions during the optimisation process.