一个基于填充函数变换的对称TSP问题的局部搜索算法

该文提出了求对称TSP问题近优解的填充函数算法。首先，在用局部搜索算法求得对称TSP问题的一个局部极小解后，对该问题作填充函数变换得到一新的组合优化问题，新问题的局部极小解和最优解分别是原问题的局部极小解和最优解，而且在对称TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中，新问题只有一个已知的局部极小解。随后用局部搜索算法求新问题的一个局部极小解，它或者是已知的局部极小解，或者是对称TSP问题的更好的局部极小解。对多个标准实例的计算试验表明，该文所构造的算法优于直接求解对称TSP问题的局部搜索算法。     

分支限界法求解实际TSP问题

提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算.下界值是根据当前路径来计算的,简单易行且占用空间少.上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍.实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程.提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索.     

旅行商问题优化解之间关系的分析

旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.     

基于改进ACS-3-opt蚁群算法的TSP

在ACS-3-opt算法求解中,大规模TSP问题易于停滞。该文提出一种改进的算法,在ACS-3-opt算法停滞后,自适应地调整具有局部搜索能力蚂蚁的数量,并通过提高最小信息素的阈值扩大搜索空间,当算法再次停滞时,增强算法两次停滞时最优路径的公共路径上的信息素,为算法的运行提供较好的初始信息,并引导算法朝最优解的方向进行求解。大中型规模TSP问题的求解结果表明,该算法能够有效地跳出局部最优,解的质量优于ACS-3-opt算法。     

利用粒子滤波求解旅行商问题

针对现有优化算法求解旅行商问题(TSP)时容易陷入局部极值的缺点,提出一种基于粒子滤波的优化搜索算法,该算法将TSP最优路径的搜索过程看成是一个动态时变系统。阐述了利用粒子滤波求解TSP最优路径的基本思想,给出了该方法的具体实现步骤。为了增强算法跳出局部极值的能力,在采样过程中引入了遗传算法的交叉和变异操作来丰富样本的多样性。最后为了验证新算法的有效性,进行了仿真实验,结果表明基于粒子滤波的优化算法能够找到比其他优化算法更好的解。     

基于分段混合蛙跳算法的旅行商问题求解

针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题,提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径,在搜索的后期引入邻域搜索(个体邻域,局部最优领域,全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解,进行全局更新和局部更新,避免迂回搜索。在局部更新中,每一个青蛙都有机会得到更新。实验结果表明,与遗传算法、蚁群算法、基本蛙跳算法相比,S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。     

混合模拟退火及分散搜索优化过道布置问题

针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对24个不同规模的测试问题进行验算与对比,结果表明所提算法的求解质量与平稳性均优于基本模拟退火算法和分散搜索算法,且较已有的4种方法更具求解优势。     

基于禁忌表的定位算法求解TSP问题

本文提出了一种基于禁忌表的定位算法求解TSP问题的快速、高效近似算法。这种算法结合了禁忌搜索算法中禁忌表及大规模构造算法和定位改进算法求解规模较大的TSP问题。计算机实例仿真证明,算法在求解质量和求解速度两方面高于著名的启发式算法的解。该算法针对TSP问题提出,是非常有效的。     

求解TSP的改进信息素二次更新与局部优化蚁群算法

针对蚁群（ACO）算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法（IPDULACO）。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛。然后,在搜索过程中,当蚁群陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题（TSP）进行仿真实验,实验结果表明,对于小规模的TSP,IPDULACO可以在较少的迭代次数内获得已知最优解;对于较大规模的TSP,IPDULACO可以在较少的迭代次数内获得更精确的解。因此,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度,可以高效求解TSP。     

一种混合局部搜索算法的嵌套分区算法

提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题.该算法使用加权抽样法产生初始最可能域,用带约束的3-opt局部搜索算法搜索每个子域的最优解,然后对Lin-Kemighan算法进行了改进,并且用改进的Lin-Kemighan算法搜索每个裙域的最优解,最后通过实验分析法确定了子域和裙域最优的抽样个数及初始最可能域的长度.对TSPLIB中15个问题实例的仿真结果表明,所提出的混合局部搜索算法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解.     

自适应动态邻域布谷鸟混合算法求解TSP问题

针对离散布谷鸟算法求解旅行商问题时邻域搜索效率低和易陷入局部最优解等问题,提出了一种自适应动态邻域布谷鸟混合算法（Adaptive Dynamic Neighborhood Hybrid Cuckoo Search algorithm,ADNHCS）。为了提升邻域搜索效率,设计了一种圆限定突变的动态邻域结构来降低经典算法的随机性;此外,提出了可根据迭代过程进行自适应参数调整的策略,并结合禁忌搜索算法来提升全局寻优的能力。使用MATLAB和标准TSPLIB数据库中的若干经典算例对算法性能进行了实验仿真,结果表明与其他基于布谷鸟算法、经典和新型群智能优化算法相比,ADNHCS算法在全局寻优能力以及稳定性方面表现更优。     

动态信息素更新和路径奖惩的蚁群算法

针对蚁群算法容易陷入局部最优,收敛速度慢,难以解决大规模问题的情况,提出依据信息熵和停滞次数的动态信息素的更新策略和基于最优路径集合的奖惩策略的蚁群算法,在动态信息素更新策略中,利用收敛系数来动态调节信息素,从而有效地平衡算法的多样性和收敛性。在搜索过程中,通过持续增大收敛系数,加快了收敛速度;当信息熵降低或者停滞次数达到一定数值时,通过降低收敛系数,跳出局部最优。同时基于最优路径集合,对较优路径进行奖励,对其他路径进行惩罚,通过减少蚂蚁每一步可选城市的数量,加快了收敛速度。并且使用三种局部优化方法,从而进一步提高解的精度。经过实验测试,该算法用于解决旅行商问题（traveling salesman problem,TSP）,具有较高的求解精度,并能有效平衡解的精度和收敛速度的矛盾。     

求解TSP问题的自适应离散型布谷鸟算法

对于求解的TSP问题,提出了一种自适应离散型布谷鸟算法（Adaptive Discrete Cuckoo Search,ADCS）。在基于布谷鸟搜索算法（Cuckoo Search,CS）的搜索原理下构造TSP问题的路径求解策略。针对离散型算法整体调整容易破坏已形成的较优路径和随着算法迭代数目增加导致种群多样性下降这两个缺陷,设计了一种针对路径的自适应型局部调整算子和全局随机扰动策略,采用了简单的2-opt优化算子作为局部优化算子以加快算法的收敛速度。最后采用多组不同规模的标准TSPLIB数据与其他的优化算法进行对比实验,结果表明ADCS算法在求解精度和稳定性方面具有优势。     

一种结合局部搜索策略的求解TSP的演化算法

介绍了一种结合局部搜索策略的求解流动旅行商问题（TSP）的演化算法。该算法的主要思想是将局部搜索策略在邻域内搜索的快速性与演化方法在全局搜索上的鲁棒性结合起来，从而跳离局部最优。将该算法用于TSPLIB中部分TSP实例上的试验结果表明：与传统的各种求解TSP的演化方法相比，该算法在获得全局最优解的精确度上有了一定的改善。     

基于汉明距离的改进粒子群算法求解旅行商问题

针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。     

一种适用于求解TSP问题的改进的禁忌算法

利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法（MTS）。该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区,然后对区域连接,生成初始解;同时生成每个城市的k邻居列表,利用k邻居列表和改进的禁忌策略来突破局部最优。通过对CHN144问题及若干TSPLIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解。     

改进的智能蚁群算法在TSP问题中的应用

研究旅行商领域优化路径问题,解决目前蚁群算法易陷入局部最优、搜索时间长等问题.为加快算法的速度优化结果,提出了一种改进的求解TSP问题的智能蚁群优化算法.算法前期采用了一种最近节点选择策略对路径进行优化,提高了搜索效率,使之适应大规模问题求解;后期改进了基本蚁群算法中信息素、挥发因子的更新规则,通过改进使得每轮搜索后信息素的增量能更好地反映求解的质量,有效地避免陷入局部最优,加快了收敛.通过改进后的蚁群算法,对TSPLIB中部分问题的仿真结果表明,在避免陷入局部最优和缩短搜索时间方面都取得了很好的效果.证明采取的优化蚁群算法,是可行有效的.     

基于路径交换的求解TSP混合蚁群算法

将蚁群算法与局部搜索优化算法结合，可抑制蚁群算法早熟收敛问题，并能提高蚁群算法的收敛速度。通过建立有效的局部搜索优化算法的参照优化边集，提高其求解质量和效率；引入路径交换策略提高蚁群算法的收敛速度和寻优能力。实验结果表明改进的混合蚁群算法能求解规模在2000个城市以内的旅行商问题的全局最优解。     

求解旅行商问题的多样化搜索帝国竞争算法

帝国竞争算法是一种局部搜索能力较强的群智能优化算法，但过度的局部搜索会导致多样性丢失并陷入局部最优。针对这一问题提出基于多样化搜索的帝国竞争算法（MSSICA）。将国家定义为一条可行解，将王国定义成四种特性不同的组合人造解方式。在搜索时使用区块机制保留各自的优势解片段，并对不同的帝国使用差异化的组合人造解方式以搜索不同解空间的有效可行解信息。在陷入局部最优时，使用多样化搜索策略注入均匀分布的可行解替换较无优势的解以提升多样性。实验结果显示，多样化搜索策略可以有效地改善帝国算法的求解多样性，并提升求解质量与稳定性。     

一种求解TSP问题的多种群并行遗传算法

遗传算法是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点.减少了收敛于局部极值的可能,也增加了处理的并行性.因此可以利用并行遗传算法研究典型的TSP问题的求解.提出一种有效的多种群并行算法求解旅行商(TSP)问题,应用多种群遗传并行进化的思想,并在种群之间进行遗传信息交流,以解决经典遗传的收敛到局部最优值问题.仿真实验结果表明,方法在解的精度上以及解的质量上优于经典的遗传算法.