Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem
Vojtěch Uher, Pavel Krömer · 2022
The traveling salesman problem is a well-known NP-hard permutation optimization problem. It is often successfully solved by nature-inspired metaheuristics such as differential evolution (DE) and particle swarm optimization (PSO). Both algorithms are originally designed for real-parameter optimization in a continuous space. The crucial problem is an appropriate solution representation - a mapping between continuous search space and discrete permutation space. In this work, we study the popular random key (RK) encoding and its properties. We point out its typical issues (solution redundancy, sorting) and propose a novel permutation representation based on the Lehmer code (LC) encoding and its factorial representation. Both encodings are tested with DE and PSO metaheuristics on popular TSP instances. The results are very promising as the LC often significantly overcomes the performance of the RK.