| 引用本文: | 吴婷,陈玉旺,汪烨.基于极值动力学的自组织优化算法求解TSP问题[J].控制理论与应用,2010,27(6):715~720.[点击复制] |
| WU Ting,CHEN Yu-wang,WANG Ye.Self-organized optimization algorithm with extremal dynamics for the traveling salesman problem[J].Control Theory and Technology,2010,27(6):715~720.[点击复制] |
|
| 基于极值动力学的自组织优化算法求解TSP问题 |
| Self-organized optimization algorithm with extremal dynamics for the traveling salesman problem |
| 摘要点击 2745 全文点击 1569 投稿时间：2009-02-25 修订日期：2009-08-17 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/j.issn.1000-8152.2010.6.CCTA090172 |
| 2010,27(6):715-720 |
| 中文关键词 TSP问题 组合优化 极值动力学 自组织优化算法 |
| 英文关键词 traveling salesman problem combinatorial optimization extremal dynamics self-organized optimization |
| 基金项目 上海市教育委员会重点学科建设项目(J51902); 上海市高校选拔培养优秀青年教师科研专项基金资助项目(SDJ08001); 上海市教委晨光计划项目(09CG69). |
|
| 中文摘要 |
| 旅行商问题(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. |