共查询到20条相似文献,搜索用时 281 毫秒
1.
2.
两段式遗传算法求解CTSP 总被引:1,自引:0,他引:1
旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一。针对中国旅行商问题(CTSP),设计了两阶段遗传算法的改进策略。第一阶段在SGA基础上采取控制参数优化和保优操作,求得若干个较优解;第二阶段采用变异操作,在第一阶段较优解组成的种群基础上寻找最优解。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。 相似文献
3.
分析了遗传算法和模拟算法的主要优缺点,提出一种用于求解旅行商问题(TSP)的改进遗传算法,该算法有效地将遗传算法和模拟退火算法相结合,在很大程度上缩短了算法的搜索时间;利用MATLAB对多种TSP问题进行仿真研究,实验结果证明了改进的遗传算法的有效性。 相似文献
4.
为研究不同遗传算子在遗传算法中的寻优作用大小,引入了多种交叉算子和多种变异算子,并以求解TSP问题为例,用MATLAB编程实现了基于各种遗传算子组合的遗传算法。在深入分析与对比实验数据的基础上,探讨了各种遗传算子在寻优过程中的作用及效率。最后,把本文的研究与其他类似研究做了对比分析。 相似文献
5.
TSP问题是典型的NP难组合优化问题,而遗传算法是求解此类问题的一种方法。但遗传算法存在收敛速度慢和陷入局部最优的问题。针对上述问题并结合TSP的特点提出了一种改进的遗传算法,对传统遗传算法的各种操作与算子进行了优化与改进,较好地解决了种群多样性与算法收敛性的矛盾。实验结果表明,改进后的算法明显优于传统遗传算法,说明该算法具有良好的有效性与可行性。 相似文献
6.
介绍TSP问题与遗传算法的基本特点与原理,讨论用遗传算法解决TSPM题的编码方面,适应度函数设计方面的采用的方法,以及遗传操作算子包括选择算子,交叉算子和变异算子的应用现状以及效果,总结了算法的改进发展的趋势,并对解决TSP问题的前景提出了展望 相似文献
7.
8.
就多维背包问题的求解,提出一个基于遗传算法的启发式算法(MKPGA)。该算法中加入了一个利用问题特性知识的启发式修复算子以帮助求解。测试实例使用270个不同特性的多维背包问题,实验结果表明,该算法对多维背包问题的求解十分有效,能获得不同特性问题的高质量解。 相似文献
9.
遗传算法是借鉴生物界自然选择和进化机制发展起来的全局的概率搜索算法,旅行商问题(TSP)是著名的NP问题,也是组合优化、计算机科学界经典的问题之一。本文简介了遗传算法的原理、设计方法和基本步骤,并着重用遗传算法对TSP问题进行近似求解。 相似文献
10.
《科技风》2017,(16)
旅行商问题是一个组合优化问题,具有重要的实际意义。而遗传算法是求解旅行商问题的典型算法之一。本文首先介绍了旅行商问题的定义以及它的研究背景、发展现状和常用算法。在此基础上,详细阐述了遗传算法原理。通过改进这些算子,改进了传统的遗传算法,提高了算法的效率,降低了它的时间及空间复杂度。本文使用路径总长度的倒数作为适应度函数,保证了解向着最优化方向发展。然后选择部分交叉算子来产生新个体,保证了迭代的效率。变异算子利用位点变异,使算法变得简单,易行。最后,使用MATLAB语言进行编程,解决了城市数目分别为15和25时的两个实际问题。通过对这两个问题的收敛速度的对比、分析,总结了遗传算法求解旅行商问题的特点。 相似文献
11.
12.
TSP问题的最优化研究及求解实例 总被引:2,自引:0,他引:2
本文首先描述了旅行商问题(简称TSP),介绍了TSP问题的发展历史,并提出了自己的观点,然后对基于模拟退火算法的神经网络求解TSP问题的具体技术线路进行了详细介绍,最后建立了一个求解TSP问题的实例模型,用C语言编制程序,给出了运行结果。 相似文献
13.
14.
TSP问题是一个典型的NP完全问题。近年来,学者们尝试用多种算法来解决TSP产生的“组合爆炸”问题。其中,遗传算法因为其自身的优点,逐渐成为解决TSP问题的有效手段之一。在对TSP问题和遗传算法充分描述的基础上,利用遗传算法模拟TSP问题,并给出了计算机实现过程以及实验结果。 相似文献
15.
提出供应商管理库存(VMI)与第三方物流(TPL)集成供应链管理模式,构建VMI&TPL模式下的VRP优化模型.模型考虑“多供应商,单TPL,单制造商”的供应链网络,TPL负责统一为所有供应商配送货物.为提高求解效率,将求解过程分为两个部分:TPL首先基于节约法建立旅行商问题(TSP)基础数据,然后通过调用TSP基础数据来安排车辆分配与路线计划.VRP模型采用模拟退火遗传算法进行求解,通过算例对模型的求解策略及其有效性进行了说明. 相似文献
16.
17.
针对基本蚁群算法存在收敛速度慢,易陷于局部最优解等缺点,提出了一种求解旅行商(TSP)问题的改进的自适应蚁群算法。 相似文献
18.
TSP问题茁物流配送、选址等领域普遍存在,是当前相关领域研究的热点问题。本文提出在WebGIS环境下,利用遗传算法表求解该问题.首先,针对WebGIS数据,以实际地标经纬度信息作为初始点,提取路网拓扑结构,然后使用遗传算法采求解哈密顿路开最终给出优化路径。实验结装表明提出的方法具有良好的实际应用效果。 相似文献
19.
对求解旅行商问题(TSP)的回溯搜索算法进行并行化的设计和改进,对该并行算法进行了详细描述。在MPI并行计算环境下应用该并行算法进行计算,求出了旅行商问题的最优解。实验结果表明,该并行算法适合求解小规模旅行商问题。 相似文献