基于组合变异和分组优化的单亲遗传算法求解旅行商问题

针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法。算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力。仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强。

一种应用于旅行商问题的莱维飞行转移规则蚁群优化算法

针对旅行商问题(TSP)提出了一种基于莱维飞行转移规则的蚁群优化算法。该算法结合了基于莱维飞行和蚁群系统算法(ant colony system,ACS)的转移规则,形成了一种动态权重的混合转移规则,该策略能够有效地帮助算法跳出局部最优,增强全局搜索能力。此外,随机多路径优化3-opt策略通过随机抽取部分路径与当前最优路径组合,增加算法的多样性。当算法陷入停滞时,采用信息素平均随机重置策略重置路径上的信息素浓度,有助于算法跳出局部最优。实验结果显示,所提算法在处理多个不同规模的TSP实例时,与最优解的误差保持在3%以内,证明了该算法在TSP中具备出色的收敛性和避免陷入局部最优解的能力。

带冲突图的着色旅行商问题模型与算法

着色旅行商问题是多旅行商问题的一个重要变种,它被广泛地应用于带有重叠区域的多机工程系统。现有的着色旅行商问题难以有效应对带冲突的场景,这种冲突通常表现为两个城市不允许被同一旅行商访问。受带冲突图的组合优化问题的启发,提出了带冲突图的着色旅行商问题,且给出了其形式化的表达。带冲突图的着色旅行商问题是一个NP难问题,精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解。为了求解更大规模的实例,提出了一个有效的模因算法。该模因算法采用了自适应大规模邻域搜索算子。对比模因算法和精确算法,模因算法在20个小规模实例中的9个结果更好,在18个实例上展现了其远超精确算法的求解速度。而比较模因算法和其他启发式算法,模因算法在全部14个中等规模实例上均取得了更好结果。此外,消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性。

利用改进匈牙利算法求解旅行商问题

针对传统的匈牙利算法在求解旅行商问题(travelling salesman problem,TSP)时会导致多回路闭合的问题,提出了破环机制,设计了破环匈牙利算法。通过采用分配问题的描述方法对旅行商问题进行建模,并建立二者之间的转换关系,论证了TSP可行解的充分必要条件是对应分配问题的可行解与辅助边结合后仅包含一个环路,对6个标准旅行商进行测试和对比分析,验证算法的有效性。实验结果表明:在不同的数据集中,改进匈牙利算法能有效求出TSP问题的解。

基于图卷积和注意力神经网络的旅行商问题新解法

旅行商问题是一个经典的组合优化问题。为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能。对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例。发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022 s,0.0178 s,1.7643 s,2.3074 s和2.0538 s。因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中。

求解动态旅行商问题的蚁群优化算法新策略

动态旅行商问题是标准旅行商问题的一个扩展,由于其现实应用广泛,吸引了大量研究者的兴趣。蚁群优化算法可以转化历史环境信息,天然具有适应动态改变的能力,可以解决动态旅行商问题。使用蚁群优化算法解决优化问题时,算法探索能力和利用能力的权衡是一个关键问题。传统的思路是在搜索前期侧重探索能力,使蚁群充分获取搜索空间的信息,随着搜索过程的进行逐渐增强利用能力,使蚁群逐渐收敛。然而,以上思路不利于在动态场景中快速获得质量较高的解。针对动态旅行商问题,提出了一种新的探索-利用权衡策略,在环境变化后,首先使用模拟退火算法增强利用能力以快速获得质量较高的解,在解质量难以提高时再使用自适应性轮盘赌选择方法帮助算法跳出局部极值。在权重变化的动态旅行商问题上的实验证明,所提新策略优于其它蚁群优化算法及变体。

求旅行商问题的幂律变换优化蚁群算法

为解决旅行商问题,依据蚁群系统在蚁群算法中的优化,提出一种基于幂律变换的优化蚁群算法。首先,利用幂律变换优化蚁群算法以改善信息素局部更新公式;然后,在状态转移中使用幂律变换种群走过每条路径的次数,并通过归一化处理来分析信息素局部更新所造成的影响,以加快模型收敛速度;最后,随机加入莱维飞行对全局信息素进行扰乱,防止模型过早陷入局部最优。经过TSPLAB数据库提供的大量实例验证,幂律变换优化蚁群算法在保持较快收敛速度的基础上,能有效避免模型过早陷入局部最优。

基于策略池-扩张机制的改进遗传算法求解旅行商问题

针对传统遗传算法(GA)在求解旅行商问题(TSP)时,因种群多样性丢失、局部搜索能力减弱导致算法寻优效率低、易早熟等问题,提出了一种基于策略池-扩张机制的改进遗传算法(SPEM-IGA)。根据不同目的设计了两组策略池,为增强解的搜索深度,构造由2-opt、启发式插入、贪婪算子组成的局部搜索策略池;为扩大解的搜索范围,再将近邻插入、翻转、片段交换、循环左移算子组成全局搜索策略池。根据种群多样性水平,设计了基于策略池的随机选择机制,并使种群动态扩张,能有效改善种群的多样性,平衡算法的全局与局部搜索能力。通过精英优选保留种群中的优质个体,以加快算法收敛速度。仿真实验表明,与现有文献相比,基于策略池-扩张机制的改进遗传算法具有更好的求解精度和稳定性。

基于带容量约束的着色旅行商问题的多机器人调度

电商仓储的高速发展对多拣选机器人的任务调度分配问题提出了更高的要求,着色旅行商问题在城市任务上的定性描述已经逐渐无法满足实际问题中的定量分析的需求。为了降低综合成本,提高拣选效率,拟在着色旅行商问题的基础上结合有容量限制的车辆路径问题,提出一种带容量约束的着色旅行商问题,来更好地构建以总路径成本最小为目标的多拣选机器人的调度模型,并设计相应的变邻域搜索算法对模型进行求解。实验结果表明,相较于基于遗传算法及其改进算法,变邻域搜索算法在求解带容量约束的着色旅行商问题上更具优越性,该模型及其求解算法具有一定实用价值。

基于量子近似优化算法的旅行商问题研究

用量子近似优化方法对旅行商问题的一个变种进行算法设计和实现,并在模拟器上进行了仿真。结果表明,在量子比特足够的情况下,该算法能在量子计算机上以多项式时间进行旅行商问题变种的求解,并达到近似比1.5之内的近似程度,为利用量子计算机求解NP难问题提供了一种思路。

基于Transformer的旅行商问题解法

在针对旅行商问题(Travelling Salesman Problem)的近似求解算法中,传统启发式算法收敛速度较慢,准确性较低。为解决上述问题,该文提出一种基于Transformer的神经网络方法。该方法使用神经网络,可有效提高近似解的求解速度和准确性,并使用Transformer注意力机制全面提高神经网络的性能。该方法使用强化学习进行训练,使用束搜索算法进行搜索。使用该方法对随机50节点的旅行商问题进行测试,试验结果表明该种基于Transformer的旅行商问题解法,可在较低的复杂度前提下,得到近似于精确解的效果。

基于改进自适应遗传算法的旅行商问题研究

传统遗传算法因其强大的全局搜索能力成为了解决旅行商问题的优选之一,但它较差的局部搜索能力限制了该算法在寻求最优解时的效能。为解决此问题,笔者通过改良圈算法优化初始解,在进化过程中自适应调整进行各遗传操作的概率,结合模拟退火算法的关键步骤metropolis准则和加入逆转操作,基于随机模拟的策略对遗传算法进行改进并将其应用于求解旅行商问题。仿真结果表明,改进的遗传算法在算法收敛速度、收敛效果和解质量方面均优于传统遗传算法。

基于量子蚁群算法的旅行商问题求解及算法评估

量子蚁群算法是一种将量子理论与传统蚁群算法结合的高效生物进化算法,主要应用于故障诊断、路径规划、图像分割等问题的优化.基于传统蚁群算法的流程,介绍量子蚁群算法中的量子理论基础以及量子理论如何应用于蚁群算法.通过若干旅行商问题实例分析量子蚁群算法较传统蚁群算法的优势.针对目前研究多以离散指标来评估不同算法、难以直观显示不同算法综合差别的问题,提出一种综合评估算法搜索效率的方法,成功应用于量子蚁群算法和传统蚁群算法的对比,具有一定的实践意义.

基于改进的指针网络深度强化学习算法求解旅行商问题

旅行商问题是组合优化问题中的经典问题,而深度强化学习的发展为该类问题的求解提供了新思路。在基于指针网络的深度强化学习算法求解旅行商问题中,策略网络和价值网络的编码器都采用了复杂的长短期记忆网络结构,这在求解大规模旅行商问题时会造成训练时间过长的现象。鉴于输入节点间位置顺序的无关性,本文对指针网络中编码器的循环神经网络进行了修改,将策略网络和价值网络编码器中的长短期记忆网络都替换为一维卷积神经网络,最终提出了一种改进的基于指针网络的深度强化学习算法,其在相同求解问题规模上所需要的训练时间比原模型减少12%~15%,实验结果充分验证了本文改进算法的有效性。

基于基因库求解旅行商问题的遗传算法

针对传统遗传算法(genetic algorithm,GA)求解旅行商问题(traveling salesman problem,TSP)存在寻优效率低、实验结果缺乏一致性等问题,提出了一种基于基因库的遗传算法(genetic algorithm based on genes pool,GPGA)。GPGA从种群中搜索减小哈密顿圈长度的边,并当做优良基因构成基因库。父代哈密顿圈在基因库引导下产生更优的子代哈密顿圈,基因库也随着种群的不断进化而同步更新,引导种群个体逐步向最优解靠近。算例结果表明在同样条件下,GPGA比传统遗传算法和几种改进遗传算法的性能更优。

基于MTSP问题的公共图书馆智慧配送服务

随着“互联网+”思维和图书馆服务模式与水平的发展,纸质资源的物流配送成为图书馆借阅平台的最后环节。如何在智慧图书馆智能服务平台中降低图书馆的配送成本、均衡配送员的工作量、提升配送效率是智慧服务的研究方向。在智能计算研究中,解决TSP旅行商问题常采用蚁群算法,因为蚁群算法能利用信息正反馈和启发式信息诱导,从而找出多目标遍历的最优解。针对图书馆馆际与社区物流配送的多旅行商MTSP问题,使用混合蚁群优化算法来实现图书纸质资源最后配送路径最优化处理,可以更好地实现配送效率的综合提升。图书馆高效率优质服务可以更好地提升阅读质量。

基于信息熵的改进蚁群算法求解TSP问题

针对蚁群算法求解精度低、易陷入局部最优的缺点,提出一种基于信息熵的自适应改进蚁群算法。通过算法自身特性定义结合熵值对种群参数进行自适应优化;采用分组合作的信息素更新策略,通过较活跃性个体引导整个种群,扩大搜索范围;通过对较优路径的奖励,平衡收敛速度和搜索范围之间的关系;在种群信息熵过低时,加入局部搜索策略,进一步提高算法精度。实验结果表明,相较于蚁群算法,改进算法具有较好的求解精度以及跳出局部最优的能力。

面向多起点均衡多旅行商问题的进化算法

为解决多起点均衡多旅行商问题,分析问题的特点,从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发,提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标,构建新型评价函数,设计双染色体编码方式。在此基础上,引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集TSPLIB上,与其它求解多旅行商问题的进化算法进行对比,验证算法的有效性。

SizeScale:求解旅行商问题(TSP)的新算法

旅行商 ( TSP)问题是组合优化中最典型的 NP-Hard问题之一 ,目前关于该问题的启发式算法主要分为两类 :环路构造算法和环路改进算法 .对于第 1类算法 ,首次提出了在环路构造中成批加入顶点 ,同时在构造过程对环路进行局部优化的思想 ,由此得到了一种新的算法 :Size Scale-Construct,它的解质量极大地改进了现有的环路构造算法 .对于第 2类算法 ,在分析局部最优解与全局最优解之间关系的基础上 ,提出了另一个采用局部最优解的交集作为初始环路的新算法 :Size Scale-Improve.实验结果表明该算法在解的质量和求解速度上都较大地改进了现有最好的环路改进算法 ;另一方面 。

旅行商问题(TSP)的几种求解方法

旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题,其可能的路径数目与城市数目是呈指数型增长的,求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP,接着论述了六种目前针对TSP比较有效的解决方法(模拟退火算法、禁忌搜索算法、Hopfie ld神经网络优化算法、蚁群算法、遗传算法和混合优化策略)的基本思想,并且简单阐述了它们的求解过程,最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。