首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 136 毫秒
1.
一种求解TSP问题的相遇蚁群算法   总被引:6,自引:0,他引:6  
赵文彬  孙志毅  李虹 《计算机工程》2004,30(12):136-137,185
蚁群算法是由意大利学者M.Dorigo等人首先提出的一种新型的仿生算法。蚁群算法与其他算法同样存在搜索速度慢,易于陷于局部最优。该文提出一种改进的相遇算法克服了以上的缺陷。通过对TSP问题的仿真结果表明,提出的相遇算法与基本蚁群算法相比搜索速度和性能都有一定的提高。  相似文献   

2.
介绍了一种求解TSP问题的分段交换蚁群算法。分段交换蚁群算法把小窗口、随机分段优化求解、模拟退火充分交换的思想引入蚁群算法,把蚁群算法和模拟退火算法融合。该算法在蚁群算法陷入局部最优解的情况下,能改进其局部最优解,并可减少迭代次数。仿真实验表明取得了较好的效果。  相似文献   

3.
容迟网络的概率路由算法根据节点与信宿节点之间相遇的概率判断是否转发报文,但相遇概率不能真正准确地反映报文递交成功的概率.针对该问题,提出一种基于蚁群算法的概率路由算法,结合蚁群算法的基本原理改进信息素浓度的更新机制和报文转发机制.仿真结果表明,与传统的概率路由算法相比,改进后的概率路由算法报文递交率较高,开销率较小.  相似文献   

4.
常规蚁群算法具有搜索时间较长,易于过早地收敛于非最优解的缺陷。为了提高蚂蚁一次周游的质量,采用具有轮盘赌方式的最大最小蚁群算法(MMAS+RW),即在依据概率选择下一个城市时采用轮盘赌的方式。提出一种具有分段和变异特性的蚁群算法。该算法融合了分段的分而治之思想和遗传算法中的变异,有利于保持群体多样性的特性,是在采用轮盘赌方式的最大最小蚁群算法陷入局部最优解的情况下,引入随机分段和遗传算法的变异操作来优化当前最优解,改善解的质量,改进蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验表明取得了较好的效果。  相似文献   

5.
具有分段和变异特性的蚁群算法求解TSP问题   总被引:2,自引:1,他引:1  
常规蚁群算法具有搜索时间较长,易于过早地收敛于非最优解的缺陷.为了提高蚂蚁一次周游的质量,采用具有轮盘赌方式的最大最小蚁群算法(MMAS RW),即在依据概率选择下一个城市时采用轮盘赌的方式.提出一种具有分段和变异特性的蚁群算法.该算法融合了分段的分而治之思想和遗传算法中的变异,有利于保持群体多样性的特性,是在采用轮盘赌方式的最大最小蚁群算法陷入局部最优解的情况下,引入随机分段和遗传算法的变异操作来优化当前最优解,改善解的质量,改进蚁群算法易于过早地收敛于非最优解的缺陷.仿真实验表明取得了较好的效果.  相似文献   

6.
蚁群算法及其应用研究进展   总被引:11,自引:2,他引:9  
蚁群算法作为一种仿生进化算法,是受到真实蚁群觅食机制的启发而提出的.首先介绍了蚁群算法的基本原理和工作机制,然后分别就蚁群算法的理论和应用的研究现状进行了综述,主要包括蚁群算法的参数设置,蚁群算法的改进,蚁群算法的收敛性以及蚁群算法在组合优化问题和连续优化问题中的应用,并进一步给出了它们的研究重点和发展方向,最后是关于蚁群算法的研究展望和面临的挑战,提出了蚁群算法研究中值得探讨的一些课题.  相似文献   

7.
针对喂料器的位置确定的条件下,研究拱架式贴片机的元器件贴装顺序优化问题.建立了新的拱架式贴片机贴装顺序的数学模型.针对问题的路径寻优特点,把混合蛙跳算法与蚁群算法相融合,实现对贴片机的元件贴装顺序优化问题的求解.在算法中提出了适应于贴片机实际贴装情况的分段启发函数、分段信息素以及信息素的分段更新策略等多种改进方法.为验证算法有效性,以20块实际生产的PCB为实例进行了测试.实验结果表明,算法具有较好的求解精度和全局搜索能力,与文献中的单一混合蛙跳算法相比,平均效率提高了7.89%;与蚁群算法相比,平均效率提高了3.79%.  相似文献   

8.
基于改进蚁群算法的线缆路径规划技术研究   总被引:1,自引:0,他引:1       下载免费PDF全文
线缆布线是复杂机电产品设计中的普遍性难题。针对线缆布局设计中存在的效率低、可靠性差等问题,提出了一种基于改进蚁群算法的线缆路径规划方法。采用分段式空间划分方法对待布线空间进行环境建模,同时对布线空间进行栅格化处理,以获取三维布线路径的规划空间。为解决基本蚁群算法在进行路径搜索时路径点容易发散的问题,引入了基于重力规则的蚁群算法路径搜索策略,提高了路径规划的真实度。在仿真实验中,将所提出的方法与基本蚁群算法进行了对比分析,验证了该算法的可行性和有效性。  相似文献   

9.
蚁群算法是一种新型的模拟进化算法,是受到真实蚁群的觅食机制的启发而提出的。介绍了蚁群算法的基本原理和工作机制,并分别就蚁群算法的理论和应用进行了阐述,包括蚁群算法改进的不同算法以及蚁群算法在各个领域中的应用,并进一步给出了研究重点和发展方向。  相似文献   

10.
一种基于MMAS的具有奖罚机制的分组蚁群算法   总被引:1,自引:0,他引:1  
蚁群算法是由意大利学者M.Dorigo等人提出,近几年迅速发展起来,并得到广泛应用的一种模拟进化的优化类算法.然而蚁群算法和其他进化算法一样存在搜索速度慢、易陷入局部最优的缺点.为了克服上述的不足,在MMAS基础上提出一种具有奖罚机制的分组蚁群算法,即在MMAS基础上对蚂蚁进行分组,利用蚂蚁组之间合作和组内蚂蚁相遇合作思想,并引入奖罚机制对信息素更新.实验数据表明改进后的算法避免了停滞陷入局部最优的现象且加快了搜索速度,最优解也较优.  相似文献   

11.
一种改进的求解TSP问题的演化算法   总被引:43,自引:0,他引:43  
演化算法是解决组合优化问题的高效搜索算法.该文在现有求解TSP问题的演化算法的基础上,通过引入映射算子、优化算子以及增加一些控制策略,提出了一种高效的演化搜索算法.实验表明,该算法是有效的,通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明,其中实例CHN144得到的最短路径为30353.860997,优于吴斌等运用分段算法得到的最短路径30354.3,亦优于朱文兴等人的结果,实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同,实例pr136得到的最短路径值为96770.924122,优于TSPLIB中提供的最短路径96772,对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径,该算法不仅很容易收敛到问题的最优解,而且求解速度极快.  相似文献   

12.
针对基本离散粒子群优化(DPSO)算法收敛速度慢、易于陷入局部最优等问题,提出了一种基于优秀系数的局部搜索混沌离散粒子群优化(ILCDPSO)算法并用于求解旅行商问题(TSP)。基于轮盘赌选择原理,给每段路径设定一个合理的优秀系数,以提高短边被选择的概率,从而有利于提高算法的寻优能力和收敛速度;为了进一步提高解的精确性,在算法机制中添加了局部搜索策略,通过调整每个城市在给定邻域内的城市路径,提高算法的局部搜索能力;另外,在算法的迭代公式中加入了混沌序列来提高粒子的随机性和多样性,增强了算法的全局搜索能力。最后用国际通用的TSP数据库(TSPLIB)中的若干经典实例对算法进行了测试,并与粒子群优化(PSO)算法、改进的PSO(IPSO)算法和混沌PSO(CPSO)算法等进行了比较。实验数据显示,在相同的实验条件下,与其他算法相比,ILCDPSO算法获得最优解的平均迭代次数较少且获得最优解的次数比例最高。研究结果表明,加入优秀系数后,ILCDPSO算法在收敛速度、全局寻优能力以及稳定性方面均优于其他算法。  相似文献   

13.
传统蚁群算法在解决旅行商问题(TSP)有较大的优势,但也存在一些不足,如收敛速度慢、易陷入局部最优等。针对这些问题,提出区域破坏重建的蚁群优化算法(RDRACO)。RDRACO应用区域破坏重建算法解决因信息素积累而陷入局部最优的问题,并将蚁群算法的信息素更新规则和全局更新策略进行了调整,使之与该算法匹配。另外在蚁群路径选择中加入2-Opt算子,加快收敛速度和提高收敛精度。实验采用TSPLIB中的20个经典TSP数据集对RDRACO进行仿真实验,仿真结果表明:RDRACO算法通过较少的迭代次数就可找出数据集较小TSP的已知最优路径,并在数据集较大TSP收敛精度上有显著的优化。RDRACO在提高收敛速度的同时具有较高的精度和较好的鲁棒性。  相似文献   

14.
基于Spark的蚁群优化算法   总被引:2,自引:0,他引:2  
为应对大数据时代中组合优化问题的求解,基于云计算框架Spark,借助其基于内存、分布式的特定,提出一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集,由此给出相应的一系列转换算子,实现了蚂蚁构造解过程的并行化。通过在旅行商问题(TSP)求解的仿真实验结果说明了所提出的并行算法的可行性;并在同等实验环境下对比基于MapReduce的蚁群优化算法,优化速度提升达10倍以上。  相似文献   

15.
基于选路优化的改进蚁群算法   总被引:7,自引:0,他引:7  
蚁群算法在处理大规模优化问题时效率很低。为此对蚁群算法提出了基于选路优化的两点改进:(1)引入选路优化策略,减少了算法中蚁群的选路次数,显著提高了算法的执行效率。(2)在选路操作中,只根据当前城市的前C个距离最近的且未经过城市为候选城市计算选择概率,从而减少单个蚂蚁选路的计算量。尤其对于以往较难处理的大规模TSP问题,改进算法在执行效率上有明显的优势。模拟实验结果表明改进算法较之基本蚁群算法在收敛速度有明显提高。  相似文献   

16.
蚁群优化算法是一种能应用于求解旅行商问题(Traveling Salesman Problem,TSP)的智能算法,但蚁群算法在求解TSP路径规划问题中存在收敛速度慢、易陷入局部最优解问题,而将蚂蚁算法的蚁群分组,能增加全局搜索能力,提高求解路径规划性能。通过分析蚁群分组大小与蚁群算法性能的关系,并提出了一种自适应分组蚁群算法,采用一种随迭代分组数减少策略方法,并将其应用于对TSP路径规划问题求解。通过实验结果对比表明,自适应分组蚁群算法在收敛速度和搜索质量方面都有了明显提高。  相似文献   

17.
一种求解函数优化问题的单亲遗传算法   总被引:2,自引:0,他引:2  
1 引言求解函数优化问题,特别是多峰函数的优化问题,由于传统的遗传算法将杂交算子作为主要算子,在选择压力的作用下,群体的多样性在进化过程中存在逐步降低的现象,最后以致趋同,进而过早收敛。文[1]也指出“杂交算子在搜索过程中存在着严重的成熟化效应,它在起搜索作用的同时,不可避免地使群体的多样性趋于0,从而逐渐减小自己的搜索范围,引起过早收敛”。  相似文献   

18.
一种求解TSP问题的单亲遗传算法   总被引:15,自引:0,他引:15  
1 前言 TSP问题可描述为:给定一个城市的集合,寻找一条从集合中的某个城市出发,访问每个城市一次且仅一次,最后回到出发点的最短路径。这已被证明是一个NP难解问题。求解TSP问题,遗传算法通常采用序号编码和非序号编码两种解表达方式。其中序号编码相对简单直接,其代表性的有“邻接表达”、“普通表达”和“路径表达”等几种编码方式,后者是最自然的表达方式。序号编码方式的杂交算子难于设计,杂交后解的合法性是需着重考虑的问题。虽然目前已提出了一些基于路径表达的杂交算子,如PMX、OX和CX,但普遍计算额外开销很大,而且杂交算子的使用对群体的多样性存在很大影响,容易使算法过早收敛。  相似文献   

19.
Modeling the dynamics of ant colony optimization   总被引:6,自引:0,他引:6  
The dynamics of Ant Colony Optimization (ACO) algorithms is studied using a deterministic model that assumes an average expected behavior of the algorithms. The ACO optimization metaheuristic is an iterative approach, where in every iteration, artificial ants construct solutions randomly but guided by pheromone information stemming from former ants that found good solutions. The behavior of ACO algorithms and the ACO model are analyzed for certain types of permutation problems. It is shown analytically that the decisions of an ant are influenced in an intriguing way by the use of the pheromone information and the properties of the pheromone matrix. This explains why ACO algorithms can show a complex dynamic behavior even when there is only one ant per iteration and no competition occurs. The ACO model is used to describe the algorithm behavior as a combination of situations with different degrees of competition between the ants. This helps to better understand the dynamics of the algorithm when there are several ants per iteration as is always the case when using ACO algorithms for optimization. Simulations are done to compare the behavior of the ACO model with the ACO algorithm. Results show that the deterministic model describes essential features of the dynamics of ACO algorithms quite accurately, while other aspects of the algorithms behavior cannot be found in the model.  相似文献   

20.
增强型的蚁群优化算法   总被引:8,自引:1,他引:8  
旅行商问题是一个NP-Hard组合优化问题。根据蚁群优化算法和旅行商问题的特点,论文提出了对蚁群中具有优质解的蚂蚁个体所走路径上的信息素强度进行增强的方法,并同其他的优化算法进行了比较,仿真结果表明,对具有全局和局部最优解的个体所走路径上的信息素强度进行增强的蚁群优化算法比标准的蚁群优化算法和其他优化算法在执行效率和稳定性上要高。  相似文献   

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

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