蚁群算法的改进与应用

【作者】 秦玲；

【导师】 陈崚；

【作者基本信息】 扬州大学 ， 计算机应用技术， 2004， 硕士

【摘要】 人们从仿生学的机理中受到启发，提出许多解决复杂优化问题的新方法，统称为元启发(metahueristic)算法，如遗传算法、进化策略、模拟退火、蚁群算法、禁忌搜索(tabu search)算法等，并成功地应用于实际问题，蚁群算法(ant colony algorithm，简称ACA)是最近几年才提出来的一种新型的模拟进化算法，它是由意大利学者M．Dorigo，V．Mahiezzo，A．Colorni等人受到人们对自然界中真实蚁群集体行为的研究成果的启发而首先提出来的。他们充分利用蚁群搜索食物的过程与旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程中个体之间的信息交流与相互协作最终找到从蚁群到食物源的最短路径的原理解决了TSP问题，取得了很好的结果。随后，蚁群算法被用来求解job-shop调度问题、指派问题、序列求序(sequential ordering)等NP完全问题，显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的优越性，证明它是一种具有广阔发展前景的好方法。 但是，蚁群算法仍然存在一些缺陷：如在性能方面，算法的收敛速度和所得解的多样性、稳定性等性能间存在矛盾：这是因为蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从复杂无章的路径中找出一条较好的路径，如果一味加快收敛速度则很可能导致蚂蚁的搜索陷入局部最优造成早熟、停滞现象。应用范围方面，蚁群算法的应用尚且局限在较小的范围中，难以处理连续空间的优化问题：由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适用，而对线性和非线性规划等连续空间的优化问题的求解不能直接应用。 本文首先详细介绍了基本蚁群算法并综述了当前国内外蚁群算法的研究现状；分析了蚁群算法中蚂蚁搜索过程的本质，针对上述蚁群算法存在的问题，在第四章提出了平衡蚁群算法收敛速度解的性能之间矛盾，提高其性能的四种改进蚁群算法，并总结当前研究工作，分析相关问题，给出了我们在该方面工作的进一步研究思路。 第一种算法是基于分布均匀度的自适应蚁群算法，根据优化过程中蚂蚁的分布均匀度，动态地调整下一次迭代过程中蚂蚁分布的大致范围，同时根据不同蚂蚁选择的各条路径构成解的好坏程度有差别的自适应更新相应路径上的信息量。第二种算法模拟蚂蚁感觉和知觉行为，将蚂蚁的搜索过程分为三个阶段，在不同阶段有差别的采取不同的优化机制，成功地避免蚂蚁完全受信息量影响的“道听途说”而造成的干扬州大学石贞{一学位论文扰和自日选路，第三种算法是改进的增强型蚁群算法，通过增强全局(或局部)最优解和全局(或局部_次优解的路径上的信息量浓度以及对它们进行交叉和变异操作的遗传优化方法来改进增强型蚁群算法.第四种算法在算法中引入免疫遗传学(i mmunogenetics)及免疫系统中的浓度控制机制，调节蚂蚁遍历过程中的信息量分布，弓!用小生境技术(n iche)，将蚁群分化为若干小子群独立进化.实验证明这四种算法平衡了收敛速度与解的多样性之间的矛后，有效避免了早熟和停滞现象. 在研究过程中，我们发现基本蚁群算法的一个不可忽视的应用缺陷是不太适合求解连续性优化问题，为此在第五章，我们还提出一种用蚁群算法求解连续空间优化问题的方法，将解空间划分成若干子域，在蚁群算法的每一次迭代中，首先根据信息量求出解所在的子域，然后在该子域内已有的解中确定解的具体的值.实践证明，这种方、法可推广应用到其他连续空间的优化问题之中，突破了基本蚁群算法的应用局限，为将该算法应用于连续性优化问题提出了新的途径， 另外，我们还把蚁群算法应用于o一1背包问题，武器一目标分配问题、Flow一shoP问题以及Qos路由问题，都获得了比较好的应用，取得了较好的效果.特别是在解决Qos成组多播路由问题的改进蚁群算法中，不但简化了算法中参数的选取过程，还避免了将各个度量参数的简单归一，算法能充分保证实际网络Qos需求. 在本文中，我们提出求解TSP问题的四种提高蚁群算法性能的改进算法，给出该方面工作的进一步研究思路;同时改进基本蚁群算法结构，使其适应于求解连续优化问题;研究其优化本质，将其应用于除TSP问题外的五种不同应用问题，大量应用实例的实验结果证明，这些改进的蚁群算法不但加速了蚁群算法的收敛速度，提高了优化所得解的质量，而且扩大了蚁群算法的应用范围.更多还原

【Abstract】 Ant colony algorithm (AC) has emerged recently as a new meta-heuristic for NP-hard problems in combinatorial optimization. This meta-heuristic also includes evolutionary algorithms, neural networks, simulated annealing which all belong to the class of problem-solving strategies derived from nature. Dorigo, Maniezzo, and Colorni [Dorigo M, Maniezzo V, Colorni A., 1996], using the Traveling Salesman Problem (TSP) [Dorigo M, Gambardella L. M.,1997] as example, introduced the first AC algorithm. With the further study in this area, ant colony algorithm is widely applied to the problems of Job-shop Scheduling Problem (JSP)[ Colorni A., Dorigo M, Maniezzo V.,1994], the Quadratic Assignment Problem (QAP)[ Maniezzo V,1999, Maniezzo V, Carbonaro A.,2000], the Sequential Ordering Problem (SOP)[Gambardella L. M., Dorigo M.,1997] and some other NP complete problems. It demonstrates its superiority of solving complicated combinatorial optimization problems.But,there are still some faults in ant colony algorithm. Firstly, the diversity and stability of the solutions searched by ant colony are in conflict with convergence speed of the algorithm. The reason is that the movements of the individuals in ant colony are stochastic though they can evolve to the optimal path by interchange information, and they can hardly find a optimum one from a mass of paths within a short time when the problem scale is large enough, eyelessly accelerate the convergence speed will make the ants’ local search and lead to premature and stagnation of the algorithm easily. Secondly, classical ant colony algorithm demands of discrete solution space since each ant only can selete limitedly at each step, so this algorithm is useful for discrete optimization problems such as combinational optimization problem, but not suitable for solving optimization problems with continuous space such as linear or non-linear programming problems.In this paper, we first introduce classical ant colony algorithm and give a summary about its current research work. In chapter four, we analyze the essence of its search processe , produce four kinds of new unproved algorithms, and discuss our intending research work in this area.The first algorithm is based on the equilibrium of ant distribution, in this method,the distribute area of ants in the interation were adjusted automaticly, and the pheromone on the trail was updated differently according the quality of the solution it constructed. The second algorithm is produced according to the sensor and consciousness behavior of ants, the optimization process was looked as three distinguished phase, and in each phase we use different optimiazation mechanism. Thus, the blindness trail selection only by pheromone was avoided successfully. The third algorithm is an improved augment ant colony optimization method.it uses the operations of crossover and mutation of GA and has higher capacity of global optimization. The fourth algorithm introduces density control mechanism in immunogenetics to adjust the distribute of ants, and the ant colony is devided into some small independent colonies using niche technology in the iteration process. The experimental results show that these four algorithms overcome the conflict between the convergence speed and solution diversity, and avoid the premature and phenominon efficiently.In our research work, we find a noteworthy defect of basic ant colony algorithm that it is not suitable for solving continuous optimization problem. So, in chaper five, we bring forward a new novel algorithm to which crossover and mutation operation is added , and the experimental results tested on non-linear programming problems demenstrate the superiority of our method ,it shows that this algorithm is suitable for solving continus problems especially such problems with large scale.Meanwhile,, we also make full use of the ants’ capability of finding optimal solutions, applicate the ant colony algorithm to 0-1 Knapsack problem ,Weapon Target Assignment problem, Flow-Shop problem. Particularly, we produce an improved更多还原