首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 128 毫秒
1.
宋晓宇  王丹 《计算机工程》2007,33(4):218-219
为了解决单一算法求解Job Shop调度问题存在的不足,该文提出了一种混合算法,将蚁群算法用于全局搜索。针对蚁群算法易于陷入局部最优的情况,提出了一种基于关键工序的邻域搜索方法,将使用此邻域搜索方法的TS算法作为局部搜索策略。利用TS算法较强的局部搜索能力,提高了蚁群算法的优化能力,达到改善Job Shop调度问题解的质量。实验结果表明,混合算法在较短的时间内,找到了FT10、LA24、LA36等典型benchmarks问题的最优解,得到的makespan的平均值较并行遗传算法(PGA)和TSAB算法均有所提高。  相似文献   

2.
基于蚁群算法求解最大团问题   总被引:2,自引:0,他引:2  
最大团问题是一种典型的NP完全问题, 是图论中一个经典的组合优化问题.研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法.通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷.仿真实验表明,图中的顶点数较多时,也取得了较好的结果.  相似文献   

3.
运输调度问题的蚁群算法研究   总被引:3,自引:0,他引:3  
蚁群算法是一种用于求解复杂组合优化的较新的启发式算法.本文简述了蚁群算法的基本原理及算法模型,通过分析研究现状指出了蚁群算法在实际应用中的局限性,最后给出解决一般运输调度问题的蚁群算法,并分析了其今后的发展方向.  相似文献   

4.
蚁群算法是模仿蚂蚁觅食行为的一种新的仿生学智能优化算法。针对其收敛速度慢和易陷入局部最优的不足,将细菌觅食算法和蚁群算法相结合,提出一种细菌觅食 蚁群算法。在蚁群算法迭代过程中,引入细菌觅食算法的复制操作,以加快算法的收敛速度;引入细菌觅食算法的趋向操作,以增强算法的全局搜索能力。通过经典的旅行商问题和函数优化问题测试表明,细菌觅食 蚁群算法在寻优能力、可靠性、收敛效率和稳定性方面均优于基本蚁群算法及两种改进蚁群算法。  相似文献   

5.
蚁群优化算法的研究现状及研究展望   总被引:17,自引:0,他引:17  
张航  罗熊 《信息与控制》2004,33(3):318-324
本文首先简要地介绍蚁群优化算法的来源、对应的生物原理和算法实现的框架.然后详细地讨论了算法的研究现状以及在各种优化问题中的应用情况,同时也指出了蚁群优化算法在当前应用中的一些不足.针对这些不足提出了解决方法,描述了几种蚁群优化算法的修正策略.最后对蚁群优化算法下一步的研究方向进行了展望.  相似文献   

6.
TSP问题是典型的NP—hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法,利用遗传算法生成信息素的分布,克服了蚁群算法中搜索时间长的缺陷。此外,在蚁群算法寻优中,采用交叉和变异的策略,改善了TSP解的质量。仿真结果显示,改进的蚁群算法是有效的。  相似文献   

7.
蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一。旅行商问题(TSP)是一个典型的组合优化问题,易于描述却难于求解。在介绍了求解旅行商问题的三种经典的蚁群算法的基本原理后,着重分析了蚁群算法的发展现状,总结出蚁群算法发展的五个方向,即基于局部优化算法的蚁群算法、对路径上的信息素更新方法进行改进、蚁群算法与其他算法的融合、对蚁群算法的控制参数进行优化和并行蚁群算法。而且这五个方向有相互融合的趋势。  相似文献   

8.
蚁群算法是一种解决组合优化问题的有效算法,已得到日益深入的研究,并逐渐得到应用。蚁群算法的一个不足是,算法参数的设置往往凭借经验,缺乏充足的依据。文章以车辆路径问题(vehicleroutingproblem,VRP)为例,从一个烟草配送的智能决策系统中抽取一定量的数据,对蚁群算法中各参数与算法收敛性之间的关系进行了大量的仿真实验,通过对实验结果的分析,给出了解决此类问题时的一种优化算法参数的方法。  相似文献   

9.
尽管蚁群优化算法在优化计算中有大量应用,但在大规模优化问题中蚁群算法仍存在搜索时间过长、易于停滞现象等等应用瓶颈。基于这些原因,根据经济学组织交易成本理论,文中提出一种新的通过聚类来降低优化问题规模的蚁群优化算法:基于聚类的蚂蚁优化算法,并从理论上表明比其他蚁群优化算法提高了收敛速度并延迟停滞现象。  相似文献   

10.
基于蚁群算法求路径规划问题的新方法及仿真   总被引:6,自引:1,他引:6  
该文提出了一种基于蚁群算法求解路径规划问题的新方法及其仿真,蚁群算法就是对自然界中蚂蚁的寻食过程进行模拟而得出的一种模拟进化算法。与传统的算法相比,该算法的主要特点是正反馈和并行性,正反馈使得该算法能很快发现较好解,并行性使得该算法易于实现并行计算。虽然蚁群算法在时间复杂度上可能不如传统的算法,但是理论研究表明该方法是一种基于种群的鲁棒性较强的模拟进化算法。最后,利用Java语言对蚁群算法和改进的Dijkstra算法进行了仿真,并进行了比较。  相似文献   

11.
二次蚁群算法在运输调度问题中的应用   总被引:2,自引:0,他引:2  
蚁群算法在解决车辆路径问题VRP(Vehicle Routing Problem)上表现了很大优势,但也存在全局搜索能力较低、易出现停滞等缺陷.提出的二次蚁群算法是指先用改进的自适应蚁群算法对VRP求得一个可行解,再用求解旅行商问题TSP(Traveling Salesman Problem)的蚁群算法对所得到的解进一步优化,从而得到最优解.从两个实验仿真结果的数据上看,该算法具有很强的搜索能力,克服了基本蚁群算法的某些弊端,能够有效地求解车辆路径问题.  相似文献   

12.
一种改进的蚁群算法在TSP问题中的应用研究   总被引:1,自引:0,他引:1  
刘少伟  王洁 《计算机仿真》2007,24(9):155-157,186
蚁群算法是近几年发展起来的一种新型的拟生态启发式算法,它已经被成功地应用在旅行商(TSP)问题上.由于基本蚁群算法存在过早陷入局部最优解和收敛性较差等缺点,文中对基本蚁群算法在基于蚁群系统的基础上进行了改进,在信息素的更新和解的搜索过程中更多地关注了局部最优解的信息,以使算法尽可能地跳出局部最优,并且改进后的算法对一些关键参数更容易控制.多次实验表明改进的蚁群算法在解决TSP问题上与基本蚁群算法相比有较好的寻优能力和收敛能力.这种算法可以应用在其它组合优化问题上,有一定的工程应用价值.  相似文献   

13.
蚁群算法具有较强的鲁棒性和优良的分布式计算机制.研究重点是对现有的求解带硬时间窗的车辆路径问题VRP-H(Vehicle Routing Problem with Hard Time Windows)的蚁群算法作出更好的改进,使得算法的计算效率更高且得到的解更优,提出了蚁群算法的改进算法-改进的自适应蚁群算法.该算法先用自适应蚁群算法对VRP-H求得一个可行解,再利用多种改善方法对初始解进一步优化,从而得到最优解.测试时选用Solomon提出的题库,结果表明该算法能够有效地求解VRP-H.  相似文献   

14.
Ant Colony Optimization (ACO) is a metaheuristic that has recently been applied to scheduling problems. We propose an ACO algorithm for the Single Machine Total Weighted Tardiness Problem and compare it to an existing ACO algorithm for the unweighted problem. The proposed algorithm has some novel properties that are of general interest for ACO optimization. A main novelty is that the ants are guided on their way through the decision space by global pheromone information instead of using only local pheromone information. It is also shown that the ACO optimization behaviour can be improved when priority scheduling heuristics are adapted so that they appropriately reflect absolute quality differences between the alternatives before they are used by the ants. Further improvements can be obtained by identifying situations where the ants can perform optimal decisions.  相似文献   

15.
基于多蚁群的并行ACO算法   总被引:2,自引:0,他引:2       下载免费PDF全文
通过改变蚁群优化(ACO)算法行为,提出一种新的ACO并行化策略——并行多蚁群ACO算法。针对蚁群算法存在停滞现象的缺点,改进选择策略,实现具有自适应并行机制的选择和搜索策略,以加强其全局搜索能力。并行处理采用数据并行的手段,能减少处理器间的通信时间并获得更好的解。以对称TSP测试集为对象进行比较实验,结果表明,该算法相对于串行算法及现有的并行算法具有一定的优势。  相似文献   

16.
Nowadays, the Traveling Salesman Problem (TSP) is one of the most studied combinational optimization problems that researchers study. Although it is easy to define, its solution is hard. Therefore, it is one of the NP-hard problems in the research literature. It can be used to solve real-life problems such as route planning and scheduling, and transportation and logistics applications. In this study, for TSP, an interface that can run on mobile devices using Android and IOS operating systems is developed. Real-world data are used online by the interface. Locations, and the distance between them, are obtained instantly by Google Maps APIs. Genetic (GA) and ant colony optimization (ACO) algorithms are used to solve the TSP. Furthermore, users have also been allowed to conduct trials for different parameter values. The application developed has been tested on two different datasets. The test results show that for the determination of the optimum route, the ACO algorithm is better than the GA. However, when considering the run times, GA works much faster than ACO.  相似文献   

17.
Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.  相似文献   

18.
Job Shop Scheduling Problem (JSSP) is one of classic combinatorial optimization problems and has a long research history. Modern job shop has following characteristics: increasingly complicated processes, small batch and personalized requirement, which lead to complex correlations among processes. Complex correlations of processes, involving nested correlations besides serial and parallel correlations, propose a new task for JSSP research. Decomposing JSSP into two nested sub problems of order of arranging processes and machine arrangement, this research integrates the traditional thought of complex method into the ant colony optimization (ACO) to develop a nested optimization method in order to solve the new task. This paper is divided into four parts: first, the model of JSSP with complex associated processes is constructed and the difficulties to solve which are analyzed and listed; second, the definition of “order of arranging processes” is originally proposed, based on which the mathematical model available for the complex method is developed, taking process starting time as design variables of the first level optimization. The steps of the first level optimization and the secondary nested flow chart are detailed with the demonstration of the effectiveness of the complex method’s iteration mechanism; third, based on the representation of features the order of arranging processes obtained by the first level optimization combined with the first-in first-out rule owns, the corresponding modified ACO algorithm, involving pheromone positive perception and reverse spreading mechanism, is put forward to realize the second level optimization, which result is taken as the objective function value of the complex vertex to realize the secondary nested optimization strategy; finally, taking plentiful JSSP with complex associated processes as study cases, a serial of comparative experiments are done respectively adopting the genetic algorithm, ACO algorithm, particle swarm optimization algorithm, some combinations of heuristic algorithms respectively in the nested two levels, and the proposed nested optimization method, and experiment results attest the reliability and superiority of the proposed method.  相似文献   

19.
蚁群算法的收敛速度分析   总被引:2,自引:2,他引:2  
黄翰  郝志峰  吴春国  秦勇 《计算机学报》2007,30(8):1344-1353
蚁群算法(ACO)作为一类新型的机器学习技术,已经广泛用于组合优化问题的求解,同时也应用于工业工程的优化设计.相对于遗传算法(GA),蚁群算法的理论研究在国内外均起步较晚,特别是收敛速度的分析理论是该领域急待解决的第一大公开问题.文中的研究内容主要是针对这一公开问题而开展的.根据蚁群算法的特性,该研究基于吸收态Markov过程的数学模型,提出了蚁群算法的收敛速度分析理论.作者给出了估算蚁群算法期望收敛时间的几个理论方法,以分析蚁群算法的收敛速度,并结合著名的ACS算法作了具体的案例研究.基于该文提出的收敛速度分析理论,作者还提出ACO-难和ACO-易两类问题的界定方法;最后,利用ACS算法求解TSP问题的实验数据,验证了文中提出的分析结论,得出了初步的算法设计指导原则.  相似文献   

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

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