引用本文:白杰,朱俊,杨根科,潘常春.基于反馈校正原理的非对称旅行商问题的自收敛优化算法[J].控制理论与应用,2012,29(6):689~696.[点击复制]
BAI Jie,ZHU Jun,YANG Gen-ke,PAN Chang-chun.A self-convergent algorithm for the asymmetric traveling salesman problem based on feedback adjustment mechanism[J].Control Theory and Technology,2012,29(6):689~696.[点击复制]
基于反馈校正原理的非对称旅行商问题的自收敛优化算法
A self-convergent algorithm for the asymmetric traveling salesman problem based on feedback adjustment mechanism
摘要点击 3139  全文点击 3111  投稿时间：2011-03-28  修订日期：2011-10-24
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/j.issn.1000-8152.2012.6.CCTA110310
  2012,29(6):689-696
中文关键词  非对称旅行商问题  组合优化  蚁群算法  弧排除算法
英文关键词  asymmetric traveling salesman problem  combinatorial optimization  ant colony-optimization  arcexcluding algorithm
基金项目  国家自然科学基金资助项目(61074150).
作者单位E-mail
白杰 上海交通大学 自动化系, 系统控制与信息处理教育部重点实验室 baijie@sjtu.edu.cn 
朱俊 江苏骏龙电力科技股份有限公司  
杨根科 上海交通大学 自动化系, 系统控制与信息处理教育部重点实验室  
潘常春* 上海交通大学 自动化系, 系统控制与信息处理教育部重点实验室 pan_cc@sjtu.edu.cn 
中文摘要
      针对非对称旅行商问题(ATSP), 提出基于反馈校正原理的自收敛求解算法框架. 该方法核心是依据ATSP问题松弛模型的对偶关系推断与ATSP最优解无关弧集合的弧排除算法. 该算法框架以ATSP问题的初始弧集合作为“参考输入”, 以ATSP最优解的上下界求解算法作为“控制对象”, 以弧排除算法作为“反馈校正控制器”, 其“反馈输入”是“控制对象”的输出差值. 算法迭代过程中, 上下界差值缩小, 排除弧集合增加, 算法呈现出自收敛性. 该框架集成了数学规划方法和启发式算法的优点, 论文从理论证明和仿真分析说明了该自收敛算法的有效性.
英文摘要
      A novel algorithmic framework based on the feedback adjustment mechanism is proposed to solve the asymmetric traveling salesman problem (ATSP). The main idea of the algorithm is to continuously exclude arcs not belonging to the optimal solution, using the dual information of the relaxed ATSP problem. The initial arc-set is regarded as the “reference input”; the lower-bound solver and the upper-bound solver are treated as the “controlled plant”; the algorithm for excluding arcs not belonging to the optimal solution is considered the “feedback controller”, to which the feedback input is the difference of the outputs from the “controlled plant”. During the process of iterations, with the gap between the lower-bound and the upper-bound is reduced gradually, the cardinality of the excluding arcs will be augmented which guarantees the algorithm of self-convergence to the optimal solution. This work integrates the mathematical programming and the heuristic method, the superiority of which over an isolated single method is shown theoretically and illustrated computationally, demonstrating the efficiency.