首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 156 毫秒
1.
求解不确定TSP问题的蚂蚁算法   总被引:1,自引:0,他引:1  
提出了不确定旅行商问题模型,该模型将路径长度看作动态可变的。从实际应用来说,该模型考虑了交通运行中的不确定情况,比经典旅行商问题更具有灵活性及实用价值,利用该模型得到的结果将更适于指导车辆对运行路线的选择。同时提出了一种基于蚂蚁算法的混合方法求解不确定旅行商问题,并给出了解的评价标准。实验结果显示,该方法能够加速蚂蚁算法的收敛性,可以有效求解不确定旅行商问题。  相似文献   

2.
分析了旅行商问题,结合蚁群算法的群体的协作与学习能力,提出了一种基于蚁群算法的的旅行商并行计算模式.该算法根据蚁群的本质特征,并结合计算中通讯的开销,采用了粗粒度模型,并引入变异思想,能够提高算法的收敛速度,以获得更好的优化解.通过旅行商问题的仿真实验获得的结果表明,该算法对于蚁群算法具有较好的改进效果,能够很好地解决旅行商一类的问题问题求解。  相似文献   

3.
基于遗传算法的双目标车辆路线优化研究   总被引:2,自引:0,他引:2  
本文对车辆路线优化问题建立了双目标多旅行商问题模型,提出一种求解旅行商问题混合遗传算法,并对双目标多旅行商问题提出了解决方案。基于实例的仿真结果表明,文章提出的算法和解决方案是可行而有效的。  相似文献   

4.
最小比率旅行商(MRTSP)问题竞争决策算法   总被引:8,自引:3,他引:8  
针对最小比率旅行商问题,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想、能求对称型最小比率旅行商问题的快速求解方法,经过数据测试和验证,获得了较好的结果。  相似文献   

5.
改进的MIMIC算法求解旅行商问题   总被引:2,自引:0,他引:2  
为了有效解决组合优化领域的旅行商问题,提出了一种改进的双变量相关的分布估计算法-MIMIC 算法.改进的MIMIC 算法将原有的二进制编码表达方式改为十进制编码,建立了求解旅行商问题的概率模型,描述了搜索空间上旅行路径的分布,以旅行路径的概率分布模型为基础进行随机采样,指导后代种群的产生,实现种群的进化以达到搜索最优旅行路径的目的.仿真实验表明,提出的改进的 MIMIC 算法是一种求解 TSP 问题的有效方法.  相似文献   

6.
考虑现有旅行商问题常忽略车辆载重对运输费用的影响,建立含权旅行商问题模型。在分析含权旅行商问题性质的基础上,提出离散粒子群优化算法求解含权旅行商问题。重新定义问题域的粒子速度、粒子位置等运算规则,引入惯性系数线性下降策略。实验表明,该算法可以有效用于含权旅行商问题的求解,并且对含权旅行商问题的求解性能优于遗传算法和模拟退火算法。  相似文献   

7.
王东  吴湘滨 《计算机应用》2007,27(11):2826-2829
Lin-Kernighan算法作为一种高效的组合优化问题优化算法,普遍应用于各种求解组合优化难题的算法中,尤其是旅行商问题的求解。通过对该类问题的可化简性论述,分析并建立了该类问题初始边集的概率化简模型,经实验分析方式确定了模型中的先验性概率值,并建立旅行商化简初始边集的随机算法。将该算法建立的边集作为链式Lin-Kernighan算法的参照优化边集,大幅度提高了链式Lin-Kernighan算法的求解性能,在与多种智能算法结合中取得了较好的收敛效果。  相似文献   

8.
蚁群算法是一种元启发式算法,其经典应用是解决旅行商问题。该算法有着先天的并行特性。介绍了该算法的两种并行实现策略,给出了蚁群算法的并行实现模型,分析了该算法并行实现需要解决的问题。  相似文献   

9.
将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好.  相似文献   

10.
利用确定性退火技术的旅行商问题求解算法*   总被引:2,自引:0,他引:2  
将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好.  相似文献   

11.
基于遗传算法求解TSP问题的一种算法   总被引:12,自引:1,他引:12  
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。  相似文献   

12.
基于知识库求解TSP问题的改进遗传算法   总被引:2,自引:0,他引:2  
旅行商问题是一个典型的、易于描述却难以处理的np完全问题,快速有效地解决旅行商问题具有重要的理论和实际意义。该文提出了一种改进的遗传算法求解旅行商问题。该算法将遗传算法和知识库结合起来,利用遗传算法全局搜索能力强和知识库具有存储记忆功能的特点,提高了遗传算法求解旅行商问题的效率。并通过实验数据对基本遗传算法和改进遗传算法的求解结果进行比较,证明改进遗传算法的可行性和有效性。最后给出了改进遗传算法的重要问题和新的研究方向。  相似文献   

13.
武妍  包建军 《计算机应用》2006,26(10):2433-2436
在分析量子进化基本概念的基础上,提出了一种新的求解TSP的混合量子进化算法(MQEA)。该算法将三段优化局部搜索算法融入量子进化机制,采用一种基于边的编码方法,应用最近邻规则设置初始参数,并设计了排序交叉算子以扩展种群的搜索范围。通过选取国际通用旅行商问题(TSP)实例库(TSPLIB)中的多个实例进行测试,表明新算法具有高的精确度和鲁棒性,即使对于中大规模问题(城市数大于500),也能以很小的种群和微小的相对误差求得满意解。  相似文献   

14.
作业处理中的柔性使得作业调度更为灵活,作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例,给出了算法实现串行调度和并行调度的具体区别,并给出了串行和并行调度的结果。结果表明,并行相对于串行对算法效率的提高与柔性大小相关,与作业的规模成反比。  相似文献   

15.
ACA(Ant Colony Algorithm)是一种可以有效求解组合优化的TSP(Travelling Salesman Problem)问题的方法。然而,当TSP问题的规模较大时,该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA(Improved AP Ant Colony Algorithm)的求解方法。利用AP(Affinity Propagation)聚类对大规模旅行商问题进行处理,将大规模旅行商问题分为若干子问题,并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合,得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真,实验结果表明,基于聚类集成的蚁群算法具有更好的求解效果。  相似文献   

16.
动态信息素更新蚁群算法在指派问题中的应用   总被引:2,自引:0,他引:2       下载免费PDF全文
姜长元 《计算机工程》2008,34(15):187-189
建立指派问题的数学模型,将其转化为旅行商问题,利用蚁群算法求解此问题。蚁群算法是一种解决组合优化问题的有效算法,但同样存在搜索速度慢,易于陷于局部最优的缺陷。该文提出一种具有动态信息素更新的蚁群算法,通过具体的算例分析,表明该算法比传统的蚁群算法有更快的收敛速度和较好的稳定性。  相似文献   

17.
旅行商问题的人工免疫算法   总被引:4,自引:0,他引:4  
1 引言旅行商问题(TSP)是一个典型的有序组合优化问题,可以看成是许多领域内复杂工程优化问题的抽象形式。研究TSP问题的求解方法对解决复杂工程优化问题具有重要的参考价值。对于TSP问题,目前还没有完全有效的求解方法,但是,多年来人们一直在不停地探索。近年来,模拟自然界生物进化过程的求解TSP问题的方法不断见诸文献,但以基于  相似文献   

18.
刘强  姜麟  吴云 《微计算机信息》2012,(3):165-166,178
旅行商问题(Traveling Salesman Problem,TSP)是一类离散的、NP(Non-deterministic Polynomial)完全的组合优化问题,有着广泛的应用背景和许多的求解方法。该文介绍了用粒子群优化算法求解旅行商问题,并与模拟退火算法和遗传算法相比较,通过实验结果说明了粒子群优化算法在解决大规模组合优化问题上的有效性和可行性。  相似文献   

19.
基于演化计算的最短避障路径算法设计   总被引:1,自引:1,他引:1  
在工程应用、自动化、人工智能等诸多领域中有很多数学模型可以归结为寻求最短避障路径的问题。在环境模型的表达上,该文利用最小多边形包络法处理过的障碍物,即把障碍物描述成为多边形。在搜索策略上,利用演化算法求解TSP的算法——改进的郭涛算法的思想。针对TSP问题和最短避障路径问题的不同,在染色体的有效范围和基因的选取范围等处对算法进行修改,并且引入了基因库,成功地用演化算法解决了最短避障路径问题。  相似文献   

20.
基于改进萤火虫算法求解旅行商问题   总被引:2,自引:0,他引:2  
鉴于TSP问题是古老的组合优化难题,而萤火虫算法在求解函数优化问题中表现出优良的性能,因此,本文利用改进的萤火虫算法求解TSP问题.首先,在分析了旅行商问题的特点后,采用整数编码的方式来表示萤火虫的位置.然后,在标准萤火虫算法的位置更新过程中引入了对数递减的惯性权重来影响萤火虫的迭代过程,同时结合了遗传算法中的选择,交叉,变异以及进化逆转操作来提高每一次迭代中种群的多样性及种群的搜索能力,并将改进的算法解决TSP问题.最后,通过Matlab仿真实验表明改进的算法在求解TSP问题时具有更好收敛速度和优化效果.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号