K-Means聚类下的改进蚁群算法优化TSP问题

在解决旅行商问题(Traveling Salesman Problem, TSP)上,提出了一种新的求解思路即基于K-means聚类思想下的改进型蚁群算法,目的是优化TSP最短路径。先将整体TSP中分布的全部节点利用K-means聚类思想将其分成若干子TSP,再通过对基础蚁群算法(Ant Colony Algorithm, ACA)中信息素更新策略的改进,解决传统蚁群算法在面对大规模TSP问题时有迭代时间长、收敛速度慢和易陷入局部最优解的缺陷。在对每一个子TSP求解最优路径后再将各部分连接,使其融合成为一条完整TSP的最优路径。经验证该算法不仅优化了最短路径降低了误差率,同时大大缩短运算时间,提高了运算效率。     

用随机神经网络优化求解C-TSP

基于动态随机神经网络(DRNN:Dynamical Random Neural Network)求解典型旅行商优化问题TSP(Traveling Salesman Problem),通过简化方程参数的改进算法,针对解决大规模TSP的求解效果在时间以及路径寻优上所存在的问题,提出一种新的分区方案来解决中国31城市的旅行商问题.所获得的最优路径结果与目前公开文献中已有的其他神经网络所解的结果相比较,显示出采用随机神经网络解决多于10个变量TSP问题的优越性.实验结果表明,采用该方法解决31个城市TSP的优化,所得出的最短距离(15 112.7km)比已有5种算法的结果都要少.     

邻域分区蚁群算法在TSP中的应用

在大规模的TSP求解中,单一的使用蚁群算法会面临优化性能和时间性能这一问题,因此,应先把大规模的TSP按基于距离阈值的近邻聚类分区法划为小规模TSP优化问题来并行求解,再把各子区域中心找一条最佳路径连接起来．     

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

蚁群算法虽然具有鲁棒性和发现较好解的能力,但其搜索时间较长,当规模较大时易陷入局部最优解。本文通过求解TSP问题,对其进行改进。通过在特定情况下对路径进行逐步遍历比较来降低陷入局部最优解的可能性,找出最优解。实验验证结果表明,这种改进蚁群算法对求解TSP问题有较好的效果。     

用简单遗传算法求解TSP问题的参数组合研究

首先介绍用遗传算法求解CTSP问题的实验方法，描述了实验中群体规模、联赛规模参数对TSP问题计算时间复杂性及求解质量的影响。根据实验数据总结出两条规律：（1）对N＝34的TSP问题，群体规模在3000与4000之间，易获得最优解；（2）联赛规模在本规模的2‰附近时，易获得最优解。通过对不同规模（15－34）TSP问题的试验，发现两条规律对TSP问题求解具有普遍有效性。从理论上分析了群体规模和联赛规模对TSP问题求解质量和时间复杂性的影响，通过时间复杂性分析，表明实验规律对快速求解组合优化问题具有一定的指导性。     

基于摹加代数优化的装配线平衡方法

基于摹加代数,将一类装配线平衡问题转化为TSP问题.在摹加运算的基础上,将装配线平衡问题的优先关系图转化为混合图中的TSP问题,通过案例演示,以改进的遗传算法为求解混合图中的TSP算法,以路径最短为目标函数.利用随机变异跳出局部最优,最终结果收敛于全局最优或近似全局最优.     

一种改进的基于教与学的优化算法求解旅行商问题

提出了一种改进的基于教与学的优化算法(TLBO)求解旅行商(TSP)问题,阐述了TLBO算法的基本思想和求解步骤,给出了算法流程,针对算法在解决大规模问题时易陷入局部最优的缺陷,引入混沌搜索机制对其进行了改进.着重研究了改进后的TLBO算法求解TSP问题的求解结果和性能分析,通过benchmark实例进行了仿真实验,结果表明:与诸如遗传算法和粒子群优化算法等已有启发式算法相比,改进后的TLBO算法在求解TSP问题时性能更为优越,从而为TSP问题的求解找到了一条新途径.     

基于信息权重自适应蚁群算法求解TSP问题

为了提高蚁群算法求解TSP问题的寻优效果和计算效率,在传统蚁群算法的基础上,将信息权重系数引入路径选择机制及信息素调节机制,根据城市聚度,动态调整路径选择概率;根据路径寻优结果,自适应调整各路径信息量分布,提出了基于动态路径选择机制及自适应信息量更新的动态自适应蚁群算法,克服了传统蚁群算法计算收敛慢,容易陷入局部最优,个体早熟等缺陷。算法应用于Oliver30和Ch150两个TSP实例仿真,并与传统蚁群算法进行对比。结果表明:自适应蚁群改进算法可以有效地求解TSP问题,并且在求解效率和求解质量上都取得很好的效果。     

基于自适应层次谱聚类与遗传优化的TSP算法

提出一种基于自适应层次谱聚类与遗传优化的算法求解大规模TSP,算法首先构建一种自适应相似矩阵,并应用到谱聚类算法中实现城市的初步聚类,当聚类城市规模超过设定阈值,用上述自适应谱聚类算法进行层次聚类,直到每类城市规模均小于阈值;其次,采用结合了最近邻与禁忌思想的改进遗传算法求解GTSP,得类间最短回路;最后,用改进遗传算法求解每类城市群的最优解,综合类间GTSP最短回路以及类内TSP最优解,即得大规模旅行商问题的最优解.实验结果表明,该算法能够取得相对较优解且求解效率显著提高.     

基于点线回路优化求解TSP的一个新算法

快速有效地解决TSP问题,有着重要的理论价值和极高的实际应用价值。提出了基于点线回路优化求解TSP的算法,首先将原基本回路切去一些点(线段、路径)变成残缺回路,然后把切去的点(线段、路径)重新插入到残缺回路的所有节点之间,生成新的基本回路,切去点(线段、路径)的数量,从一个变到基本回路节点数的一半。算法实现容易、运行速度快,生成的结果接近其最优解。算法尽量避免了陷入局部极小,使得在短时间内能够求解较大规模的TSP问题。     

电子商务环境下的物流配送

在对传统的 TSP(旅行售货员问题 )研究的基础上 ,结合电子商务环境下物流配送的特点 ,提出了一种对 TSP问题的改进方法。该方法在保证配送中心把商品送到每个商店的基础上 ,可以使配送中心在送货过程中所走过的路程比采用传统的 TSP方法所走过的路程要短。     

多阶段动态车辆路径问题实时优化策略

针对多阶段动态车辆路径单决策和多决策问题,分别提出了平均距离策略和分区分批旅行商策略.前者优先安排不能延迟的顾客,然后根据路径的平均顾客距离选择可延迟顾客;后者根据阶段内决策的时间界限只在最后一次决策才考虑拒绝和延迟.实例仿真结果表明,新策略都具有较好的优化效果.     

PRM蚁群融合算法的AGV路径规划研究

针对AGV运货时需一次性取多件货物的路径规划问题,提出一种PRM算法与蚁群算法相结合的融合算法,将问题拆分为路径的选择与TSP问题分布解决,即先利用PRM算法进行AGV路径规划,再利用蚁群算法决策出取货顺序,生成总的路径。最后采用matlab进行仿真实验,并与A*算法进行对比,结果证明了PRM蚁群融合算法比A*算法得出的路径更短、效率更高。     

Hopfield网络求解旅行商问题有效性的研究

对Hopfield网络求解旅行商问题的有效性进行了研究,实验结果表明使用Hopfield网络求解TSP问题时存在两难问题,提高解有效性概率导致解的路径长度优化能力降低,而提高解的路径长度优化能力导致解有效性概率降低.     

基于出行偏好和路径长度的路径规划方法

针对基于最短路径的路径规划方法只关注路径长度,而基于轨迹的路径规划方法过度依赖用户偏好的问题,提出一种同时考虑用户出行偏好和路径长度的路径规划方法.首先,利用长短期记忆模型从历史出行轨迹中提取用户的出行偏好;其次,采用Markov链Monte Carlo采样技术将用户的出行偏好引入启发式搜索算法A*中,在道路网络中搜索...     

遗传算法求解TSP的进化策略

本文提出用遗传算法（ＧＡ）求解旅行商问题（ＴＳＰ）的一整套进化策略，包括染色体的编码、反向运算、循环运算、交换运算．其中除反向运算外，均与通常的ＧＡ算法所采用的策略不同．文中解释了它们的几何意义．用该算法求解中国３１个城市的ＴＳＰ问题得到了１５４０４公里的新的路径长度．计算结果表明整个算法是有效的     

基于形态拟合的时间序列距离计算

针对现有的距离度量方法度量准确度低且计算效率低的问题,提出了基于形态拟合的距离度量算法.该算法使用滑动聚集平均近似方法对序列进行分段降维处理,计算降维后的分段序列的动态弯曲路径,并计算处于动态弯曲路径上的分段序列之间的欧式距离,以所有分段序列的欧式距离的累积值作为最终的距离计算结果.实验表明基于形态拟合的距离度量算法具有度量准确度高且计算效率高的优点.     

拱架式贴片机贴装路径优化

贴片机工作时贴装头需在喂料器与印刷电路板之间频繁移动，缩短贴装头移动距离是提高贴装效率的重要途径。对多头拱架式贴片机贴装路径优化问题进行研究，分析贴装头沿喂料器移动取料时贴装路径变化，建立贴装头移动距离表达式。以贴装头移动距离最小为目标建立贴装路径优化模型，以贴装位置编号对取贴顺序编码，利用遗传算法对取贴顺序和取料方向进行优化。分析不同取料方式下贴装路径差异和结构特点，结果表明：双向取料与近侧取料在贴装点位置分布偏于PCB单侧较多时出现结构性差异，采用双向取料可获得比近侧取料更短的贴装路径，更利于提高贴装效率。     

一种求解TSP的高效遗传算法

根据TSP适应度地貌特征,通过将传统的反转变异算子(Simple Inversion Operator,SIM)与插入变异算子(Insertion Operator,IM)进行组合,设计出了一种可变邻域搜索的复合变异算子(Greed Invert-Insertion Operator,GIIM)。在此基础上,结合常规的部分匹配交叉(PartiallyMatched Crossover,PMX)与带有精英策略的退火选择,构造出了一种求解TSP的高效遗传算法(SEGA)。仿真测试表明,提出的算法不但具有很强的全局搜索能力,且收敛速度快;其测试结果与最新文献和国际标准测试库TSPLIB中的最优路径相比,或相同或更优。