旅行商问题(TSP)

摘要： 针对传统蚁群算法在旅行商问题(TSP)中易陷入局部最优、收敛速度较慢等问题,提出一种结合价格波动策略与动态回溯机制的蚁群算法。在价格波动策略中,结合时间序列思想将蚁群算法完整迭代周期进行分类,并根据价格波动平衡,将影响价格波动的供求关系进行匹配。通过分析算法在不同分类中的不同需求,对信息素挥发因子进行自适应动态供给,加快算法收敛速度的同时改善解的多样性。当价格波动策略的供给关系无法实现平衡时,算法将面临局部最优问题,此时引入动态回溯机制,以迭代最优蚂蚁的个体相似度作为标准,将路径信息素回溯至相似度差异显著的时期,在保证收敛速度的同时能够有效跳出局部最优。通过MATLAB对TSP中的不同测试集进行仿真,结果表明该算法在保证收敛速度的基础上,有效提高了解的质量,在中大规模城市集上较好地平衡了多样性与收敛速度的关系。

摘要： 为给智能快递柜服务合理定价,分析快递柜服务对快递员和不在宅收件人的价值,构建末端配送的旅行商问题模型,提出在不同的快递交件条款和收件人在家不确定性情况下的快递柜服务价值计算方法。基于快递柜服务价值确定收件人和快递员应支付的费用。以某快递员责任范围内的实际配送数据为例,分3种情形计算快递员的配送距离,根据节约的配送成本计算快递柜服务价值,根据受益者负担原则确定收件人和快递员需要支付的快递柜服务价格。当所有收件人都在宅但把全部快件投递入柜时,快递柜按0.274元/单收费;当41%的收件人不在宅但把全部快件投递入柜时,快递柜向快递员和不在宅收件人分别按0.273元/单和1.005元/单收费;当把不在宅收件人的快件投递入柜而在宅收件人的快件投递到户时,快递柜向不在宅收件人按1.077元/单收费。

摘要： 对纤维检测装置进行扫描路径优化有助于进一步减少检测时间,提高检测效率。考虑到每一根纤维必须检测且只检测一次,同时具有旅行商问题(traveling salesman problem,TSP)的基本特征,提出了4倍物镜粗扫描、40倍物镜精扫描纤维坐标转化的锚框算法。针对实际扫描过程中的电机运动方式,对TSP数学模型的距离评估公式进行修正,采用元启发、启发式等算法进行最优路径求解,选取800、1200、1500等3种不同规模的点进行扫描路径距离与时间测试。实验结果表明:对比传统Z型全局扫描方式,文中提出的最短时间扫描算法在总扫描路径长度降低了53.0%~67.7%,总扫描时间降低了21.0%~41.9%。

摘要： 在利用标准人工蜂群算法求解全局最优解时,研究人员发现存在种群多样性降低、过早收敛、易陷入局部极值等问题。因此,在标准人工蜂群算法的初始化阶段,采用反向学习初始化种群,提高初始解的质量;在跟随蜂阶段,对适应度值不高的个体进行混沌扰动,以增加种群多样性,从而跳出局部极值。利用改进算法和标准人工蜂群算法分别对5个不同的旅行商问题(Traveling Salesman Problem,TSP)进行仿真实验,并对比两种算法的仿真结果。实验结果表明:利用改进的人工蜂群算法求解旅行商问题是可行且有效的;在稳定性方面,改进的人工蜂群算法优于标准人工蜂群算法。

摘要： 针对传统蚁群算法在求解旅行商问题(TSP)时存在收敛速度慢、易陷入局部最优等问题,提出一种引入特征迁移学习和匹配学习的双蚁型蚁群算法(BMACS)。首先,将种群动态分级为探索蚁和追踪蚁,其中适应度较高的为探索蚁,较低的为追踪蚁;其次,提出一种局部特征迁移机制,该机制下有两种策略,在特征迁移策略中,将探索蚁公共路径作为局部特征通过局部信息素奖励迁移到信息素矩阵中,进而提高探索蚁的影响力,加快算法收敛速度;在变异学习策略中,追踪蚁跟随探索蚁负责对次优路径的探索,自适应重构探索蚁路径,从而丰富种群多样性;最后,当算法停滞时,利用匹配学习机制将当前最优个体与相似度最高的历史最优个体进行交流学习,重组信息素,增加种群的多样性,进而提高算法跳出局部最优的能力。使用MATLAB对TSPLIB中的多组案例进行仿真实验,结果表明改进后的算法平衡了多样性和收敛速度,有效提高了解的质量。

摘要： 针对传统模拟退火算法在求解问题时容易陷入局部最优解的情况,本文通过设计一种自适应的升温控制因子,提出了一种求解旅行商问题(TSP)的自适应升温模拟退火算法,有效地控制局部寻优达到全局寻优能力,并证明了改进的自适应模拟退火算法收敛性.通过TSPLIB数据库对改进算法全局寻优效果的测试,结果表明改进后的算法具有全局寻优能力、泛化性强等特点:即在TSPLIB提供的绝大部分TSP问题数据中,均能找到全局最优解,且收敛速度快.

摘要： 遗传算法(GA)的全局搜索能力强,易于操作,但其收敛速度慢,易陷入局部最优值.针对以上问题,利用深度强化学习模型SAC对遗传算法进行改进,并将其应用至旅行商问题(TSP)的求解.改进算法将种群作为与智能体(agent)交互的环境,引入贪心算法对环境进行初始化,使用改进后的交叉与变异运算作为agent的动作空间,将种群的进化过程视为一个整体,以最大化种群进化过程的累计奖励为目标,结合当前种群个体适应度情况,采用基于SAC的策略梯度算法,生成控制种群进化的动作策略,合理运用遗传算法的全局和局部搜索能力,优化种群的进化过程,平衡种群收敛速度与遗传操作次数之间的关系.对TSPLIB实例的实验结果表明,改进的遗传算法可有效地避免陷入局部最优解,在提高种群收敛速度的同时,减少寻优过程的迭代次数.

摘要： 为应对传统蚁群算法在解决旅行商问题(TSP)中求解精度不高、算法易早熟等问题,提出融合奖惩学习策略的动态分级蚁群算法(DHL-ACS).首先将蚁群动态划分为帝国蚁、殖民蚁及国王蚁,其中帝国蚁与殖民蚁执行局部信息素更新,国王蚁执行全局信息素更新,在局部信息素更新中帝国蚁执行较大权重系数,负责对较优解的开发增强算法导向性,殖民蚁执行较小权重系数,负责对次优解的探索保证算法多样性,并利用帝国蚁与殖民蚁交换优质解的方式提高解的精度.其次提出一种改进的学习策略,通过奖励帝国蚁与殖民蚁的公共路径以实现较优解的同化作用,进而提高算法收敛速度;进一步当算法停滞时,引入反馈算子来减少国王蚁路径上的信息素,以达到对较高信息素路径的惩罚作用,从而提高种群多样性,增强算法跳出局部最优能力.通过对多组TSP数据集实验对比分析,实验结果表明改进后的算法很好地平衡了收敛速度与多样性之间的关系,尤其应对大规模TSP问题,能有效改善解的精度.

摘要： 针对传统蚁群算法在解决旅行商问题(TSP)时所存在的收敛速度慢、易陷入局部最优等问题,提出了基于动态重组和协同交流策略的蚁群优化算法(RCACO).首先,将蚁群划分为贪婪蚁群和探索蚁群,两类蚁群执行不同的路径构建规则和信息素更新策略,以平衡算法的收敛速度和多样性.其次,采用一种基于线索二叉树的新型动态重组算子,并根据不同的重组策略对解集进行有导向性的动态重组,以提升算法的多样性.进一步,提出一种基于相似度和潜力值的协同交流策略,从全局的角度出发,找到最有潜力成为最优解的路径,并对这些路径给予信息素奖励,以提升算法的收敛速度.最后,算法还加入了停滞规避策略,以帮助蚁群跳出局部最优,提升算法的求解精度.通过Matlab对TSPLIB中的多组案例进行仿真实验,与传统蚁群算法和其他优化算法进行对比分析,仿真结果表明,改进的蚁群算法显著提高了收敛速度和求解精度.

摘要： 针对蚁群算法在求解旅行商问题(TSP)时出现的收敛速度慢和多样性较差的问题,提出结合协同机制与动态调控策略的双蚁群算法.首先,将蚁群根据适应度值动态地划分为导向蚁和合作蚁,从而构成异构双蚁群.其次,异构双蚁群采用协同机制平衡算法多样性和收敛速度:导向蚁在路径构建时引入传播因子,增大蚂蚁选择新路径的概率,扩大搜索范围,提高算法多样性;合作蚁受导向蚁中最优路径的引导,当路径相似度达到阈值时,启动合作算子,加快算法收敛速度.最后,引入动态调控策略,在全局信息素更新时引入自适应调控算子,对全局最优路径的信息素进行正向激励或反向惩戒,加快收敛速度的同时避免算法陷入局部最优.求解TSP测试集的实验结果表明,该算法不仅提高了解的质量,保证了算法多样性,而且加快了算法收敛速度,尤其在大规模城市问题中效果更为明显.

摘要： 本发明涉一种基于改进和声搜索优化蚁群算法旅行商问题求解方法，包括以下步骤：(1)城市十进制编码，和声算法解向量设置，构建目标函数；(2)初始化蚁群参数；(3)初始化蚂蚁位置；(4)选择下一个城市，并进行局部信息素浓度更新；(5)重复执行步骤(4)直到当前蚂蚁访问完所有城市；(6)哨兵策略；(7)重复执行步骤(3)到步骤(6)直到所有蚂蚁完成访问所有城市；(8)记忆库更新、计算记忆库所有和声目标函数值的平均值LA和构建解向量库；(9)采用改进和声算法产生新和声记。

摘要： 本发明公开了一种基于伪旅行商问题的船舶引航排班方法与装置，涉及一种船舶引航排班问题模型与基于伪旅行商问题的求解方法。方法依次包括以下步骤：根据问题描述，确定问题约束条件，建立船舶引航排班数学模型；将船舶引航排班问题数学模型转化为伪旅行商问题模型；采用改进智能水滴算法求解该伪旅行商问题模型，找出最优引航排班计划。本发明针对智能水滴算法启发性不足，容易陷入局部最优等缺点，提出了基于最优候选结点子群的选择策略，提高了搜索效率和算法精度，采用改进智能水滴算法，求解引航员指派模型，有效提高了求解结果的精度。

摘要： 本发明公开了一种运用基于重用策略的智能群体算法优化动态旅行商问题的方法。传统的旅行商问题需要在一个静态的搜索空间中找到一条代价最小的哈密顿回路。但实际上，现实世界中一些可以以旅行商问题为模型的应用并不都是静态的。它们的问题模型中的城市集合和权重矩阵是动态变化的。在动态环境中，上一次环境中搜索结果可以被新环境下的群体重用并得以学习。这样可以缩小问题的搜索空间，从而让算法在更短的时间内搜索到更优的路径。本发明提出了一种更具现实意义的动态旅行商建模方法以及将一种对历史搜索结果重新利用的策略，在实验中，通过设定环境不同程度的改变来测试方法的动态性能，证明了本发明在不同的动态环境下均合理有效。

摘要： 本发明公开了一种解决多目标多旅行商问题的改进蚁群方法，通过改变禁忌表使蚁群每只蚂蚁可以独立构造一个可行解。相比于传统每次随机选择一只蚂蚁移动，多蚂蚁协作构造可行解而言有着效率和均匀度上的优越性。此外，改进蚁群方法添加的策略还包括信息素矩阵随机初始化、修改状态转移公式使蚂蚁在配送点间移动时有一定概率回到仓库中心和额外加入多轮以各个目标优化为导向的信息素更新等。算法步骤如下，对信息素矩阵进行随机初始化后，蚁群将利用改进的状态转移公式结合轮转选择算法逐次挑选下一步配送点直至构造出可行解。可行解加权打分后，以此打分作为信息素添加量的基准，结合子路径的多项特征进行多轮次不同量的信息素添加。

摘要： 本发明公开了一种基于覆盖旅行商问题求解的路径规划方法，属于人工智能的强化学习、深度学习和组合优化领域。所述方法通过利用深度神经网络自动挖掘实例特征的特点提出了新的模型来求解CSP问题，解决了传统方法需要过多的领域知识进行求解的缺点，并极大地提高了求解速度。针对现有深度神经网络求解质量低的问题，采用了数据增强的方式扩充样本数量，利用多起点技术多次求解减少了预测误差，并提出了针对CSP问题的Mask策略对解的构造进行约束。结合简单局部搜索算法进行改进，进一步地提高了求解质量。与现有的DNN求解方法相比显著缩小了最优间隙，与启发式算法相比取得了超过20倍的速度提升，更适合在实时性要求高的场景中使用。

摘要： 本发明公开了一种求解广义旅行商问题的圈生成算法，包括以下步骤：S1、搜索所有服务节点之间的最短路，将GTSP转化为TSP；S2、构建初始费用矩阵；S3、构造指派问题并求解；S4、由指派问题的解获取联接了网路中所有元素的序列集合；S5、由序列生成圈、合成圈；S6、判断是否生成最终回路，如果是，输出结果；否则计算圈之间的费用并构造费用矩阵，返回S3进行构造指派问题生成圈,直到生成一个圈时结束算法。根据本发明，可以在多项式时间内求得一个NP难问题的近似最优解，避免了现有方法计算效率低下的问题。

摘要： 本发明公开一种基于深度强化学习的二次旅行商问题求解方法和系统，方法包括以下步骤：S1：定义二次旅行商问题，即在有向完全图中的某一顶点，访问剩余所有点集一次且仅一次后回到出发点所需的旅行成本；S2：构建求解二次旅行商问题的深度强化学习框架；S3：通过所述深度强化学习框架求解所述二次旅行商问题，得到访问点序列。本发明在极短时间内就能求得二次旅行商问题的近似解，避免了精确解方法求解时间过长，不能实时计算，实时响应，甚至对于问题规模的扩大，并不能得到有效解的问题；同时由于深度强化学习框架模型的拟合能力，避免了启发式算法对迭代计算框架的搭建以及设计者的专业知识的依赖。

摘要： 本发明涉及计算机人工智能技术领域，公开了一种基于改进的鲸鱼优化算法的旅行商问题求解方法，包括：设置算法参数；利用混沌映射初始化种群位置；计算个体适应度并记录当前最优解个体；进入迭代阶段，得到更新的概率p；通过判断概率p和系数向量A，选择一种方式更新鲸鱼位置；进入模拟退火阶段，计算新的种群适应度；依据贪婪规则判断位置是否进行更新，更新则输出全局最优鲸鱼位置和适应度，否则直接以模拟退火概率P接受新种群的位置，然后输出全局最优鲸鱼位置和适应度，选择适应度值最小的作为最优路径。与现有技术相比，本发明精度更高、收敛速度快、鲁棒性强和全局搜索范围广，能够跳出局部最优，具有突出的性能。

摘要： 本发明公开了一种基于BAS改进的粒子群优化算法求解旅行商问题的方法，其步骤为：S1、初始化相关参数，包括城市数量、粒子群数量以及最大迭代次数；S2、初始化城市坐标、每个粒子的位置和速度；S3、通过BAS算法产生随机速度，并根据适应度大小选择速度；S4、更新每个粒子的位置和速度；S5、分别保存个体最优和群体最优；S6、重复步骤S3、S4和S5，当迭代次数达到预设的上限后，停止迭代；S7、停止迭代后，输出当前群体最优对应的位置序列。本发明在传统的粒子群算法中引入了BAS算法，利用BAS算法更新粒子群的速度和位置，可以解决传统粒子群算法容易陷入局部最优的缺点，该方法提高了搜索速度，并且更加稳定，提高了解决旅行商问题的效率。

摘要： 本发明属于计算机人工智能技术领域，公开了一种基于改进鲸鱼优化算法的旅行商问题求解方法及系统，包括：对标准WOA算法的参数进行优化，设计和开发了新的搜索结构以及鲸鱼个体的位置更新方法，提出MnWOA算法；选用高维度非线性复杂目标函数集作为测试对象，对MnWOA进行寻优能力测试;同时，利用经典的旅行商问题测试集验证了MnWOA的实际性能。与现有技术相比，本发明提出的MnWOA算法能够有效地解决旅行商问题，展现出了搜索速度快，计算复杂度低，收敛精度高，全局搜索能力强的特点，并且该算法还具备进一步规避局部最优值的能力，具有很好的参考价值和研究意义。