共查询到20条相似文献,搜索用时 15 毫秒
1.
TSP问题是典型的NP难组合优化问题,而遗传算法是求解此类问题的一种方法。但遗传算法存在收敛速度慢和陷入局部最优的问题。针对上述问题并结合TSP的特点提出了一种改进的遗传算法,对传统遗传算法的各种操作与算子进行了优化与改进,较好地解决了种群多样性与算法收敛性的矛盾。实验结果表明,改进后的算法明显优于传统遗传算法,说明该算法具有良好的有效性与可行性。 相似文献
2.
介绍TSP问题与遗传算法的基本特点与原理,讨论用遗传算法解决TSPM题的编码方面,适应度函数设计方面的采用的方法,以及遗传操作算子包括选择算子,交叉算子和变异算子的应用现状以及效果,总结了算法的改进发展的趋势,并对解决TSP问题的前景提出了展望 相似文献
3.
钟宏伟 《内蒙古科技与经济》2004,(12):72-73
本文提出用遗传算法解决旅行商问题。全文分三部分进行讨论:首先提出问题、分析问题,给出问题的解决方案,然后给出遗传算法在TSP中的应用及实现,最后探讨了遗传算法解决旅行商问题自身具备的特点。 相似文献
4.
5.
分析了遗传算法和模拟算法的主要优缺点,提出一种用于求解旅行商问题(TSP)的改进遗传算法,该算法有效地将遗传算法和模拟退火算法相结合,在很大程度上缩短了算法的搜索时间;利用MATLAB对多种TSP问题进行仿真研究,实验结果证明了改进的遗传算法的有效性。 相似文献
6.
遗传算法是借鉴生物界自然选择和进化机制发展起来的全局的概率搜索算法,旅行商问题(TSP)是著名的NP问题,也是组合优化、计算机科学界经典的问题之一。本文简介了遗传算法的原理、设计方法和基本步骤,并着重用遗传算法对TSP问题进行近似求解。 相似文献
7.
8.
TSP问题作为NP难题的典型代表,计算机算法理论研究的热点,各种针对该问题的算法层出不穷。对近期出现的面向TSP问题的免疫遗传算法进行了介绍与总结,在分析了算法特点之后,提出了算法的改进方向,对TSP问题的研究进行了展望。 相似文献
9.
针对远航程无人水下航行器的路径规划问题,本文提出了一种基于旅行商(TSP)问题的路径规划的新方法。阐述了TSP问题的基本原理,并采用了模拟退火算法和遗传算法进行了仿真研究,获得较好的仿真结果。 相似文献
10.
两段式遗传算法求解CTSP 总被引:1,自引:0,他引:1
旅行商问题(TSP)是一类典型的NP完全问题,遗传算法(GA)是求解这类问题的常用方法之一。针对中国旅行商问题(CTSP),设计了两阶段遗传算法的改进策略。第一阶段在SGA基础上采取控制参数优化和保优操作,求得若干个较优解;第二阶段采用变异操作,在第一阶段较优解组成的种群基础上寻找最优解。用该策略迅速找到了CTSP最优解,该路径长度为15378km,比目前已知CTSP解更优。对遗传算法迅速求解TSP最优解提供了可行解决方案。 相似文献
11.
以简单TSP问题为例描述了传统蚁群算法过程,提出了其存在的问题及解决该问题的方法.提出了复杂TSP问题的定义,结合改进后的蚁群算法提出了解决复杂TSP问题的方法.通过实验表明,改进后的蚁群算法能够用于解决复杂TSP问题. 相似文献
12.
TSP问题是一类典型的NP完全问题,禁忌搜索算法是解决此类问题的智能优化方法之一。文章在研究了禁忌搜索算法的基本原理和算法步骤的基础上,建立了求解TSP问题的数学模型,设计了一个求解TSP问题的禁忌搜索算法程序,并进行了实验测试,实验结果表明,禁忌搜索算法能够有效地解决TSP问题。 相似文献
13.
14.
15.
混合遗传蚁群算法的改进及在TSP问题中的应用研究 总被引:1,自引:0,他引:1
蚁群算法(ACA)与遗传算法(GA)都属于仿生型优化算法,是解决组合优化问题的强有力工具,并都分别成功应用于旅行商问题(TSP)中.本文将两种算法进行融合,并给出了新的融合方式.实验结果表明,新的遗传蚁群混合算法有效地改进了算法的全局收敛性,并加快了收敛速度. 相似文献
16.
TSP问题即旅游最优路线问题,是数学领域中著名问题之一.如今,把TSP用于解决物流行业中运输线路优化已成为一种新的趋向.针对TSP问题没有一种简便、统一的求解方法,提出了改进的TSP算法,即把问题转化为求解最小树和图中悬挂点的匹配问题,从而大大缩小了TSP问题解的搜索空间,降低了求解难度,得到一种改进的求解方法,解决了供应链一对多配送问题. 相似文献
17.
针对传统遗传算法在巡回商旅问题优化计算中存在的弊端——收敛速度慢,迭代次数多。在传统遗传算法基础上,设计出一种加入人工选择和定向突变的优化改进算法。该优化算法通过人工方法保存具有有利变异个体和淘汰具有不利变异个体,有利变异个体进行杂交和变异,从而提高遗传算法的收敛速度,减少遗传算法的迭代次数。同时针对遗传算法易陷入局部最优解的情况,在优化算法中引入自适应参数算法,针对遗传算法的不同阶段,实现杂交概率和变异概率的自适应调节,防止算法陷入局部最优解。最后,采用国际标准的TSP测试集(TSPLIB)对优化算法的优良性进行验证,实验表明,对比其他算法,该优化算法在TSP最优解的质量上提高10%左右。 相似文献
18.
旅行商问题(TSP问题)是运筹学中一个十分典型的组合优化问题。TSP问题看似简单,但是解决起来十分复杂、困难,采用传统的、一般的算法是很难求出问题的最优解的。蚁群算法是根据蚂蚁寻找食物的行为模拟出来的新型仿生算法,可以用于解决复杂的组合优化问题。 相似文献
19.
TSP问题茁物流配送、选址等领域普遍存在,是当前相关领域研究的热点问题。本文提出在WebGIS环境下,利用遗传算法表求解该问题.首先,针对WebGIS数据,以实际地标经纬度信息作为初始点,提取路网拓扑结构,然后使用遗传算法采求解哈密顿路开最终给出优化路径。实验结装表明提出的方法具有良好的实际应用效果。 相似文献
20.
为研究不同遗传算子在遗传算法中的寻优作用大小,引入了多种交叉算子和多种变异算子,并以求解TSP问题为例,用MATLAB编程实现了基于各种遗传算子组合的遗传算法。在深入分析与对比实验数据的基础上,探讨了各种遗传算子在寻优过程中的作用及效率。最后,把本文的研究与其他类似研究做了对比分析。 相似文献