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

针对非对称旅行商问题(ATSP),提出基于反馈校正原理的自收敛求解算法框架.该方法核心是依据ATSP问题松弛模型的对偶关系推断与ATSP最优解无关弧集合的弧排除算法.该算法框架以ATSP问题的初始弧集合作为"参考输入",以ATSP最优解的上下界求解算法作为"控制对象",以弧排除算法作为"反馈校正控制器",其"反馈输入"是"控制对象"的输出差值.算法迭代过程中,上下界差值缩小,排除弧集合增加,算法呈现出自收敛性.该框架集成了数学规划方法和启发式算法的优点,论文从理论证明和仿真分析说明了该自收敛算法的有效性.

基于阈值深度优先策略求解非对称旅行商问题的混合分枝定界算法

针对非对称旅行商问题(ATSP)模型计算难问题,提出了一种基于深度和广度方向混合搜索的启发式策略的分枝定界算法.该算法采取有阈值的深度优先加广度加权随机搜索的策略确定分枝节点,通过求解附加弧段约束的分配问题确定下界,通过消除子环的修补算法确定上界,从而有效综合了确定性方法的准确性和启发式方法的快速性.将此算法应用于求解经典TSPLIB库中的全部ATSP问题和热轧调度的仿真研究,表现出了较高的效率和可行性.

旅行商问题的综述教学研究

旅行商问题是数学上的组合优化问题,是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视,对其的求解亦提出了各种不同算法;同时就该问题还提出了各种推广形式,但就该问题的教学研究却很少有人涉及。针对这些情况,本文就该问题的综述与教学做几方面的研究,以提高对该问题的教学质量、增强学生的学习积极性。

基于剪枝算法解决非对称TSP问题的算法研究

在科研和生活中,旅行商问题(Travelling Salesman Problem,TSP)是个非常有研究价值的问题,其中非对称TSP问题(Asymmetric Travelling Salesman Problem)的应用场景更为广泛。针对TSP问题,国内外提出了很多求解算法,但这些算法大多是研究对称TSP问题的,以及在时间复杂度、迭代次数等方面还存在一些不足。文章提出了笨人算法(Fool algorithm),其核心思想是不断淘汰最不满足要求的解,直至解只剩下唯一一个,即为本次运算的解。笨人算法在时间复杂度和运算过程上相比于其他算法会略差一些,但其运算结果集通常方差较小。经过实验分析,基于剪枝原理的算法分析有一定的实验效果,也为非对称TSP问题的研究提供了一个新的角度。

一种新的求解ATSP问题的PBIL算法

该文将二进制的人口增量学习算法(PBIL)改进为整数(集值)形式(multiplePBIL),并提出了一种新的基于城市间连接关系的非对称旅行商问题(ATSP)的解法。这种解法结合了集值人口增量学习算法和TSP问题的启发式搜索3-opt加强方法。混沌定位,分布式随机遍历构架和判断进化结束条件的可能性分布的熵的确定是该解法的三大创新之处。

用小生境模拟退火算法求解热轧调度问题

建立了特殊生产工艺约束下热轧调度问题的非对称旅行商问题的数学模型,采用小生境模拟退火算法求解该模型,提出用小生境邻域构造法构造搜索子空间,以提高模拟退火算法的效率。实验结果表明小生境模拟退火算法能够更快地找到更好的解,并优于局部搜索算法和传统模拟退火算法。

基于隶属云模型蚁群算法与LK搜索的TSP求解

提出一种求解TSP的算法,采用"问题无关的进化算法与问题相关的局部搜索相结合"的策略。采用基于云模型的蚁群算法来产生足够好的解;改进传统的LK算法,新加入5种搜索删除集与添加集元素的准则,以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33810内变化的TSP,比较该学派与其他学派算法的偏离率与运行时间,结果均显示该算法更优,有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。