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

摘要：

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

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

所属期刊栏目：27

分类号：TP18(自动化基础理论)

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

在线出版日期：2010-09-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：715-720