Optimization with extremal dynamics for the traveling salesman problem

By mapping the optimization problems to physical systems, the paper presents a general-purpose stochastic optimization method with extremal dynamics. It is built up with the traveling salesman problem (TSP) being a typical NP-complete problem. As self-organized critical processes of extremal dynamics, the optimization dynamics successively updates the states of those cities with high energy. Consequently, a near-optimal solution can be quickly obtained through the optimization processes combining the two phases of greedy searching and fluctuated explorations (ergodic walk near the phase transition). The computational results demonstrate that the proposed optimization method may provide much better performance than other optimization techniques developed from statistical physics, such as simulated annealing (SA). Since the proposed fundamental solution is based on the principles and micromechanisms of computational systems, it can provide systematic viewpoints and effective computational methods on a wide spectrum of combinatorial and physical optimization problems. (C) 2007 Elsevier B.V. All rights reserved.