基于反馈校正原理的非对称旅行商问题的自收敛优化算法

A self-convergent algorithm for the asymmetric traveling salesman problem based on feedback adjustment mechanism

中文关键词  非对称旅行商问题  组合优化  蚁群算法  弧排除算法

英文关键词  asymmetric traveling salesman problem  combinatorial optimization  ant colony-optimization  arcexcluding algorithm

中文摘要

      针对非对称旅行商问题(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.