Self-organized optimization algorithm with extremal dynamics for the traveling salesman problem
基于极值动力学的自组织优化算法求解TSP问题

Traveling salesman problem(TSP) has wide applications on optimization theory and engineering practice. With the definition of discrete state variables and local fitness, we analyze the microscopic characteristics of TSP solutions and present a novel self-organized optimization algorithm with extremal dynamics. In this algorithm, the local optimal solutions can be effectively found by the optimization dynamics combining greedy search with fluctuated explorations. Computational results on typical TSP benchmark problems in TSPLIB demonstrate that the proposed algorithm outperforms competing optimization techniques, such as simulated annealing(SA) and genetic algorithm(GA). Since this optimization method considers the micro-mechanisms of computational systems, it provides a systematic viewpoint on computational complexity and effectively helps the design of optimization dynamics on a wide spectrum of combinatorial optimization problems.