Dynamics of local search heuristics for the traveling salesman problem
Weiqi Li, Bahram Alidaee · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · 2002
This paper experimentally investigates the dynamical behavior of a search process in a local heuristic search system for a combinatorial optimization problem. Or-opt heuristic algorithm is chosen as the study subject, and the well-known traveling salesman problem (TSP) serves as a problem testbed. This study constructs the search trajectory by using the time-delay method, evaluates the dynamics of the local search system by estimating the correlation dimension for the search trajectory, and illustrates the transition of the local search process from high-dimensional stochastic to low dimensional chaotic behavior.