蚁群算法概述

1分数:___________任课教师签字：___________华北电力大学研究生结课作业学年学期：2010学年第二学期课程名称：人工智能与知识工程学生姓名：张华壮学号：2102221007题目：蚁群算法概述提交时间：2011/4/132蚁群算法概述摘要:群智能算法是一种新兴的人工智能方法，已成为越来越多研究者的关注焦点。蚁群算法是群智能算法的一个重要的分支，是意大利学者M.Dorigo通过模拟蚁群觅食行为提出的[1]。本文首先介绍了群智能的概念及特点，然后详细介绍基本蚁群算法的原理及其优缺点。在此基础上又介绍了五种针对基本蚁群算法的改进算法，最后针对蚁群算法的应用做了简要的介绍。【关键词】群智能；蚁群算法；改进算法Abstract:Swarmintelligenceisanewlydevelopingmethodinthefieldofartificialintelligence.Ithasbecomethefocusofmoreandmoreresearchers.AntcolonyalgorithmisanimportantbranchofSwarmintelligentalgorithm.ItwasproposedbyanItalianscholarM.Dorigothroughsimulatingtheforagingbehaviorsofantcolony.Thispaperfirstintroducedtheconceptandcharacteristicofswarmintelligence,andthenintroducedtheprincipleofbasicantcolonyalgorithmandtheiradvantagesanddisadvantages.Onthisbasis,Iintroducefiveimprovedalgorithmsofbasicantcolonyalgorithmandtheapplicationofantcolonyalgorithm.【Keywords】Swarmintelligence;Antcolonyalgorithm;Improvedalgorithm3目录目录...........................................................................................................................................................31绪论.......................................................................................................................................................41.1群智能的概念.............................................................................................................................41.2群智能的特点.............................................................................................................................41.3蚁群算法的基本思想.................................................................................................................42蚁群算法概述.......................................................................................................................................52.1蚁群算法基本原理.......................................................................................................................52.2蚁群算法的优点与不足...............................................................................................................72.3本章小结.....................................................................................................................................73改进的蚁群优化算法............................................................................................................................83.1带精英策略的蚁群算法...........................................................................................................83.2基于优化排序的蚂蚁系统.......................................................................................................83.3蚁群系统...................................................................................................................................83.4最大-最小蚂蚁系统.................................................................................................................93.5最优-最差蚂蚁系统.................................................................................................................94蚁群优化算法的应用..........................................................................................................................10参考文献.................................................................................................................................................1041绪论仿生优化算法是人工智能研究领域的一个重要的分支，其中包括模拟生物界中自然选择和遗传机制的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法以及模拟鸟类群体捕食行为的粒子群算法等。1.1群智能的概念蚂蚁、蜜蜂和鸟类等社会性的群居动物可以通过分工协作完成诸如发现新的食物源、建筑庞大复杂的巢穴、跨越几千公里迁徙到指定地区等复杂的任务。通过对这些动物的研究产生了群智能的概念。群智能指的就是“无智能的主体通过合作表现出智能行为的特性”[2]，是一种基于生物群体行为规律的计算技术。1.2群智能的特点群智能有如下特点和优点[2]：(1)群体中相互合作的个体是分布的(Distributed)，这样更能够适应当前网络环境下的工作状态。(2)没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。(3)可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability)。(4)由于系统中个体的增加而增加的系统通信开销在这里是十分小的，系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。1.3蚁群算法的基本思想现实生活中单个蚂蚁的能力和智力非常简单，但它们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力在没有任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的抽象，提出了人工蚁的概念。人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种解决方案，整个蚁群相互合作在全局范围内找出问题的较优的解决方案。（2）人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。（4）人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。5（5）在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况，（6）不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局部信息，而没有前瞻性的预测未来的状态。图1：二元桥实验初始状态图2：二元桥实验结束状态2蚁群算法概述下面详细介绍蚁群算法原理及其优缺点。2.1蚁群算法基本原理蚁群算法[3]可以表述如下：初始时刻，各条路径上的信息素量相等，设τij(0)=C（C为常数），蚂蚁k（k=1,2,3,…,m）在运动过程中根据各条路径上的信息6量决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻t，蚂蚁k从城市i选择城市j的转移概率kijp(t)为：k()()(),ifjJ()()()0,otherwisekijijkisisijsJittitpt(2.1)其中，Jk(i)={1，2，……，n}-tabuk表示蚂蚁k下一步允许选择的城市。列表tabuk记录了蚂蚁k在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次周游，此时蚂蚁k所走过的路径便是TSP问题的一个可行解。(2.1)式中的ηij是一个启发式因子，被称为能见度因子。在AS算法中，ηij通常取城市i与城市j之间距离的倒数。α和β分别反映了在蚂蚁的运动过程中已积累的信息和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（2.2）式更新。ijijijtnt)()1((2.2)mkkijij1(2.3)其中ρ(0ρ1)表示路径上信息素的挥发系数，1-ρ表示信息素的持久系数；△τij表示本次迭代边(ij)上信息素的增量。△τkij表示第k只蚂蚁在本次迭代中留在边(ij)上的信息素量。如果蚂蚁k没有经过边(ij)，则△τkij的值为0。△τkij