基于极值动力学的自组织优化算法求解TSP问题

Self-organized optimization algorithm with extremal dynamics for the traveling salesman problem

中文关键词  TSP问题  组合优化  极值动力学  自组织优化算法

英文关键词  traveling salesman problem  combinatorial optimization  extremal dynamics  self-organized optimization

中文摘要

      旅行商问题(traveling salesman problem, TSP)具有很强的理论研究和工程应用价值. 在定义离散状态变量和局部适应度的基础上, 分析了TSP优化解的微观特征; 将自组织临界(self-organized criticality, SOC)的概念引入到组合优化领域, 提出了一种基于极值动力学的自组织优化算法. 该算法利用快速下降和间断涨落的动态搜索过程, 高效地遍历解空间中的局部最优解. 针对TSPLIB中典型实例, 计算结果表明其求解效率和优化性能均优于模拟退火和遗传算法等优化方法. 文中算法提供了一种全新的思路, 有助于从系统角度理解组合优化问题的复杂性, 并分析合理的优化动力学过程.

英文摘要

      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.