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

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

作　　者：吴婷[1] 陈玉旺[2] 汪烨[1] 

机构地区：[1]上海电机学院机械学院,上海200240 [2]上海交通大学自动化系,上海200240

出　　处：《控制理论与应用》2010年第6期715-720,共6页Control Theory & Applications

基　　金：上海市教育委员会重点学科建设项目(J51902);上海市高校选拔培养优秀青年教师科研专项基金资助项目(SDJ08001);上海市教委晨光计划项目(09CG69)

摘　　要：旅行商问题(travelingsale sman problem,TSP)具有很强的理论研究和工程应用价值.在定义离散状态变量和局部适应度的基础上,分析了TSP优化解的微观特征;将自组织临界(self-organized critic ality,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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]