共查询到20条相似文献,搜索用时 31 毫秒
1.
针对基本蚁群算法存在收敛速度慢,易陷于局部最优解等缺点,提出了一种求解旅行商(TSP)问题的改进的自适应蚁群算法。 相似文献
2.
3.
《科技风》2017,(16)
旅行商问题是一个组合优化问题,具有重要的实际意义。而遗传算法是求解旅行商问题的典型算法之一。本文首先介绍了旅行商问题的定义以及它的研究背景、发展现状和常用算法。在此基础上,详细阐述了遗传算法原理。通过改进这些算子,改进了传统的遗传算法,提高了算法的效率,降低了它的时间及空间复杂度。本文使用路径总长度的倒数作为适应度函数,保证了解向着最优化方向发展。然后选择部分交叉算子来产生新个体,保证了迭代的效率。变异算子利用位点变异,使算法变得简单,易行。最后,使用MATLAB语言进行编程,解决了城市数目分别为15和25时的两个实际问题。通过对这两个问题的收敛速度的对比、分析,总结了遗传算法求解旅行商问题的特点。 相似文献
4.
TSP(旅行商问题)是一个学术界广泛研究的问题,长期以来吸引了众多学者对其进行研究。在蚁群算法(ACA)的研究中,TSP同样起着重要的作用。首先对TSP问题和基本蚁群算法进行了介绍,然后改进了蚁群算法的状态转移概率公式和信息素更新策略,并且应用该改进蚁群算法对TSPLIB中的两个典型问题进行仿真,实验结果比较理想。 相似文献
5.
混合遗传蚁群算法的改进及在TSP问题中的应用研究 总被引:1,自引:0,他引:1
蚁群算法(ACA)与遗传算法(GA)都属于仿生型优化算法,是解决组合优化问题的强有力工具,并都分别成功应用于旅行商问题(TSP)中.本文将两种算法进行融合,并给出了新的融合方式.实验结果表明,新的遗传蚁群混合算法有效地改进了算法的全局收敛性,并加快了收敛速度. 相似文献
6.
蚁群算法是一种新型高效的启发式优化算法,在解决优化组合问题特别是TSP求解问题上具有很高效率.本文在分析了蚁群算法的基本原理和工作机制的基础上,从信息素的更新改进实现对节点重复率的控制,并通过仿真实验实现相关参数的最优选择.实验证明,改进算法可以有效地减少蚂蚁行走的盲目性,提高了蚁群算法在迭代过程中更新TSP最优解的能力. 相似文献
7.
根据蚁群算法和模拟退火算法的特点,提出了一种基于目标函数梯度的模拟退火蚁群混合算法。该算法充分考虑了目标函数的梯度,当目标函数的梯度过小时,加强当前最优解对应的信息素,使算法快速收敛;当目标函数的梯度过大时,引入回火策略以提高解的质量。将基于目标函数梯度的模拟退火蚁群混合算法用于旅行商问题,结果表明,与常规模拟退火蚁群算法相比,改进算法的收敛速度和解的质量均有一定程度的改善。 相似文献
8.
基于最少旅行商数,旅行商间的路径平衡,遍历城市的时间窗等约束条件,建立数学模型,用改进的模拟退火算法,优化多旅行商遍历路径,该算法增加了记忆因子,记住最小的局部最优点,防止程序跳过全局最优点后跳不回来。通过仿真实例验证了该算法的可行性,且符合实时性的要求。 相似文献
9.
10.
本文针对一维、二维多选择整数背包问题的教学模型,采用动态规划和蚁群算法对其进行求解,并对蚁群算法作了适当的改进.随机数据实验表明,随着问题规模的扩大,动态规划算法的计算复杂度将急剧增大,造成求解困难,而基本蚁群算法及改进蚁群算法能够快速有效地求得问题近优解,且改进蚁群算法解的质量比原算法平均提高了2.8%. 相似文献
11.
12.
分析了遗传算法和模拟算法的主要优缺点,提出一种用于求解旅行商问题(TSP)的改进遗传算法,该算法有效地将遗传算法和模拟退火算法相结合,在很大程度上缩短了算法的搜索时间;利用MATLAB对多种TSP问题进行仿真研究,实验结果证明了改进的遗传算法的有效性。 相似文献
13.
对求解旅行商问题(TSP)的回溯搜索算法进行并行化的设计和改进,对该并行算法进行了详细描述。在MPI并行计算环境下应用该并行算法进行计算,求出了旅行商问题的最优解。实验结果表明,该并行算法适合求解小规模旅行商问题。 相似文献
14.
为了解决多人旅行商问题,文章提出了一种基于二叉树编码的改进遗传算法。将多旅行商问题转化为等效的AOV图,并将其转化成二叉树,然后进行遍历编码,再用改进的遗传算子进行算法优化。该算法克服了一维编码的局限性,通过仿真实验验证了其有效性及比普通的一位编码遗传算法更高的执行效率。 相似文献
15.
对于求解旅行商问题,提出一种采用迁移算子和变异算子寻求最优解的新型生物地理学算法。通过仿真结果,验证了该算法的可行性和有效性。 相似文献
16.
旅行商(TSP)问题是一个典型的NP难问题,作者以此为背景,叙述了近几年来研究人员改进粒子群优化算法求解非连续域的研究情况,并对将来的研究方向进行了预测。 相似文献
17.
一种改进的并行混合遗传算法在求解TSP问题中的应用 总被引:1,自引:0,他引:1
遗传算法(GeneticAlgorithm,GA)是一种基于自然群体遗传机制的有效搜索算法。由于它在搜索空间中同时考虑许多点,这样就减少了收敛于局部极小的可能,也增加了处理的并行性。因此,可以利用并行遗传算法(PGA)研究典型的组合优化实例-TSP问题(旅行商问题)的求解问题,提出一种改进的主从式并行混合遗传算法求解TSP问题。实验结果表明,该方法在解的精度和速度上优于以前的算法。 相似文献
18.
19.
蚁群算法是模仿蚂蚁寻找路径的一种智能化启发武算法.带时间窗的车辆路径问题(VSPTW)是在基本的车辆路径问题(VSP)上增加了时间窗约束条件的一种变化形式,是一个典型的NP难问题.通过采用一种改进的路径构建方法和信息素更新策略,构造一个改进的蚁群算法来求解多目标的VSPTW.与基本AS(Ant System)算法比较结果显示,该算法对于求解VSPHTW问题具有较好的性能. 相似文献