Hash Functions for Permutation-Based Problems

In addition to being a measure of quality, the fitness function is used in permutation-based problems to compare solutions. However, this can be misleading since many permutations have the same fitness value. In this paper, we investigate the impact of using a hash function to differentiate solutions over the search process. We first introduce a new efficient hash function that minimizes 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 Travelling Salesman Problem 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 paper is not intended to provide an improvement over the state-of-the-art, our work nevertheless reveals a positive effect when using the hash functions during the optimisation process.

Experimental Results

Comparison of existing hash functions:

Instance SLO Srand
h3 h1 hp1 hp2 h3 h1 hp1 hp2
eil51 0 1 0 0 0 62 0 1
berlin52 0 0 0 0 0 74 2 1
st70 0 6 0 0 0 140 11 5
eil76 0 2 1 0 1 158 11 6
pr76 0 4 0 0 0 171 8 12
gr96 0 3 1 0 0 281 10 19
rat99 0 5 0 0 0 359 18 21
kroA100 0 4 1 0 0 363 22 19
kroB100 1 4 0 0 1 315 12 17
kroC100 0 0 1 2 1 333 22 13
kroD100 0 4 1 0 2 374 11 20
kroE100 0 8 1 0 1 332 20 18
rd100 0 1 0 0 1 341 16 20
eil101 0 3 0 0 0 314 15 22
lin105 0 6 0 0 1 409 16 18
pr107 0 7 0 0 1 399 14 13
pr124 0 12 0 0 0 720 33 32
bier127 0 6 0 0 5 706 28 28
ch130 1 7 1 0 4 691 27 25
gr137 0 13 0 2 3 769 45 28
pr144 0 7 0 2 0 918 35 29
ch150 0 11 0 0 4 992 49 48
kroA150 0 15 1 2 4 893 39 44
kroB150 1 14 0 0 3 937 36 49
pr152 0 16 0 0 1 1,007 51 63
u159 0 10 0 2 2 1,173 49 42
rat195 0 22 1 2 5 1,703 83 94
d198 0 33 2 4 10 1,979 80 89
gr202 0 21 1 2 13 2,054 84 99
ts225 0 37 2 1 19 2,642 142 110
gr229 1 47 2 2 15 2,701 152 137
gil262 0 36 1 4 26 4,150 192 186
a280 2 74 5 4 31 4,510 224 200
lin318 1 40 2 4 45 6,341 308 313
rd400 2 119 11 5 99 11,328 571 509
fl417 3 130 6 8 97 12,964 564 595
gr431 2 146 8 5 127 13,981 662 644
pcb442 3 187 11 12 138 15,106 605 666
rat575 4 473 16 27 382 28,843 1,360 1,293
AVERAGE 0.54 39.33 1.95 2.31 26.72 3,116.23 144.28 142.26