蚁群优化算法课件

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第,9,章 智能优化方法,Contents,遗传算法,1,蚁群优化算法,2,粒子群优化算法,3,蚁群优化算法,先看,1,个最优化例子,“旅行商问题”（,Travel Salesman Problem, TSP,问题）常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。,规则虽然简单，但在地点数目增多后求解却极为复杂。以,42,个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。,多年来全球数学家绞尽脑汁，试图找到一个高效的算法。,TSP,问题在物流中的描述是对应一个物流配送公司，欲将,n,个客户的订货沿最短路线全部送到。如何确定最短路线。,怎么办？,变种：例如工程实施过程中，分很多阶段，每个阶段都可以有多种不同的工程执行者、原材料、设计方案、效果等等不同的选择，如何为每个阶段选择一种执行方案，使得整个工程更快更好地完成？,当有很多阶段，每个阶段的选择也很多的时候，枚举变得不现实了，但是不枚举又有什么办法呢？,遗传算法可以求解吗？,GA,求解,TSP,问题：,编码：,1 3 5 4 2 6,交配、变异算子变得复杂了,有没有更好的办法？,蚁群优化算法（,Ant Colony Optimization, ACO,）,自然界的蚂蚁能够找到从蚁巢到食物的最短路径！,自然界的蜜蜂也能轻松解决“旅行商问题”？,2010,年,10,月,25,日，英国一项最新研究说，在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力，而这是一个吸引全世界数学家研究多年的大问题，如能理解蜜蜂的解决方式，将有助于人们改善交通规划和物流等领域的工作。,英国伦敦大学皇家霍洛韦学院等机构研究人员报告说，小蜜蜂显示出了轻而易举破解这个问题的能力。他们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。这是首次发现能解决这个问题的动物，研究报告发表在,美国博物学家,杂志上。,有没有更好的办法？,事实上，意大利学者,Dorigo,教授早在,1992,年已经通过模拟蚂蚁觅食行为，找到了一种求解离散组合最优化问题的智能优化算法：蚁群优化算法！,在,2000,年在,自然,上发表了相关论文,Marco Dorigo,比利时布鲁塞尔,大学教授,著名,蚁群优化算法的创始人,IEEE Fellow,IEEE Trans on,EC,副主编,Marco Dorigo,比利时布鲁塞尔,大学教授,著名,蚁群优化算法的创始人,IEEE Fellow,IEEE Trans on,EC,副主编,Dorigo,等大,V,级人物也对,PSO,产生了兴趣,粒子群优化算法的参数在线自适应调整的工作是一个有趣的研究方向，已经取得了一些,令人鼓舞的成果,(,encouraging results),(,60,),，将算法进行自适应方面的拓展研究是值得探索的。,顺便提一下,Contents,基本原理,1,算法流程,2,改进版本,3,相关应用,4,参数设置,5,5.1,基本原理,自然界蚂蚁群体在寻找食物的过程中，通过一种被称为信息素（,Pheromone,）的物质实现相互的间接通信，从而能够合作发现从蚁穴到食物源的最短路径。,通过对这种群体智能行为的抽象建模，研究者提出了蚁群优化算法（,Ant Colony Optimization, ACO,），为最优化问题、尤其是组合优化问题的求解提供了一强有力的手段。,自然界蚂蚁觅食行为,蚁群优化算法,5.1,基本原理,在自然界中，蚂蚁通过在环境中释放信息素来交流信息，完成协同寻路任务。,林盈,/,博士学位论文答辨,A,B,蚂蚁巢穴,食物,“双桥实验”,蚂蚁总以较大概率选择信息素浓度较高的路径；,较短路径上的信息素积累速度较快；,“,正反馈,”,作用使蚁群最终聚集到较短路径上。,5.1,基本原理,自然界蚂蚁觅食行为,蚁群优化算法,蚁群,搜索空间的一组有效解,问题的搜索空间,信息素浓度变量,一个有效解,问题的最优解,觅食空间,信息素,蚁巢到食物的一条路径,找到的最短路径,对应关系,蚂蚁间的通信,启发式搜索,5.1,基本原理,蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。,5.2,算法流程,路径构建,每只蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。,ACO,基本要素,信息素更新,当所有蚂蚁构建完路径后，算法将会对所有的路径进行全局信息素的更新。注意，我们所描述的是,AS,的,ant-cycle,版本，更新是在全部蚂蚁均完成了路径的构造后才进行的，信息素的浓度变化与蚂蚁在这一轮中构建的路径长度相关。,蚂蚁系统（,Ant System,，,AS,）是最基本的,ACO,算法，是以,TSP,作为应用实例提出的。,5.2,算法流程,路径构建,伪随机比例选择规则（,random proportional,）,对于每只蚂蚁,k,，路径记忆向量,R,k,按照访问顺序记录了所有,k,已经经过的城市序号。设蚂蚁,k,当前所在城市为,i,，则其选择城市,j,作为下一个访问对象的概率如上式。,J,k,(,i,),表示从城市,i,可以直接到达的、且又不在蚂蚁访问过的城市序列,R,k,中的城市集合。,h,(,i,j,),是一个启发式信息，通常由,h,(,i,j,)=1/,d,ij,直接计算。,t,(,i,j,),表示边,(,i,j,),上的信息素量。,Company,Logo,5.2,算法流程,路径构建,伪随机比例选择规则（,random proportional,）,长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。,a,和,b,是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。当,a,=0,时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当,b,=0,时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径往往与实际目标有着较大的差异，算法的性能比较糟糕。,5.2,算法流程,信息素更新,（,1,）在算法初始化时，问题空间中所有的边上的信息素都被初始化为,t,0,。,（,2,）算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于,1,的常数。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃之前构建过的较差的路径。,（,3,）蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。,（,4,）迭代（,2,），直至算法终止。,5.2,算法流程,信息素更新,m,是蚂蚁个数；,r,是信息素的蒸发率，规定,0q0,时,ACS,将和各种,AS,算法一样使用轮盘赌选择策略，我们称之为偏向探索（,bias exploration,）。,通过调整,q0,，我们能有效调节“开发”与“探索”之间的平衡，以决定算法是集中开发最优路径附近的区域，还是探索其它的区域。,5.3.4,蚁群系统,（,2,）使用信息素全局更新规则，每轮迭代中所有蚂蚁都已构建完路径后，在属于至今最优路径的边上蒸发和释放信息素。,不论是信息素的蒸发还是释放，都只在属于至今最优路径的边上进行，这里与,AS,有很大的区别。因为,AS,算法将信息素的更新应用到了系统的所有边上，信息素更新的计算复杂度为,O,（,n,2,），而,ACS,算法的信息素更新计算复杂度降低为,O,（,n,）。参数,r,代表信息素蒸发的速率，新增加的信息素,被乘上系数,r,后，更新后的信息素浓度被控制在旧信息素量与新释放的信息素量之间，用一种隐含的又更简单的方式实现了,MMAS,算法中对信息素量取值范围的限制。,5.3.4,蚁群系统,（,3,）引入信息素局部更新规则，在路径构建过程中，对每一只蚂蚁，每当其经过一条边,(,i,j,),时，它将立刻对这条边进行信息素的更新。,信息素局部更新规则作用于某条边上会使得这条边被其他蚂蚁选中的概率减少。这种机制大大增加了算法的探索能力，后续蚂蚁倾向于探索未被使用过的边，有效地避免了算法进入停滞状态。,5.3.4,蚁群系统,顺序构建,和,并行构建,。顺序构建是指当一只蚂蚁完成一轮完整的构建并返回到初始城市之后，下一只蚂蚁才开始构建；并行构建是指所有蚂蚁同时开始构建，每次所有蚂蚁各走一步（从当前城市移动到下一个城市）。对于,ACS,，要注意到两种路径构建方式会造成算法行为的区别。,在,ACS,中通常我们选择让所有蚂蚁并行地工作。,5.3.5,连续正交蚁群系统,连续正交蚁群算法（,Continuous Orthogonal Ant Colony, COAC,）：近年来，将应用领域扩展到连续空间的蚁群算法也在发展，连续正交蚁群就是其中比较优秀的一种。,COAC,通过在问题空间内自适应地选择和调整一定数量的区域，并利用蚂蚁在这些区域内进行正交搜索、在区域间进行状态转移、并更新各个区域的信息素来搜索问题空间中的最优解。,COAC,的基本思想是利用正交试验的方法将连续空间离散化。,5.4,相关应用,车辆路径问题,（,Vehicle Routing Problem,，,VRP,）,车间作业调度问题,（,Job-Shop Scheduling Problem,，,JSP,）,二次分配问题,（,Quadratic assignment,problem, QAP,）,网络路由,（,Network Routing,）,其他,子集问题,（,Set Problem,）,ACO,图像处理,数据挖掘,二维格模型蛋白质折叠问题,最短公共超序列问题,5.5,参数设置,参数,参考设置,蚂蚁数目,m,在用,AS,、,EAS,、,AS,rank,和,MMAS,求解,TSP,问题时，,m,取值等于城市数目,n,算法有较好性能；而对于,ACS,，,m,=10,比较合适。,信息素权重,a,与启发式信息权重,b,在各类,ACO,算法中设置,a,=1,，,b,=25,比较合适,。,信息素挥发因子,r,对于,AS,和,EAS,，,r,=0.5,；对于,AS,rank,，,r,=0.1,；对于,MMAS,，,r,=0.02,；对于,ACS,，,r,=0.1,，算法的综合性能较高。,初始信息素量,t,0,对于,AS,，,t,0,=,m,/,C,nn,；对于,EAS,，,t,0,=(,e,+,m,)/,rC,nn,；对于,AS,rank,，,t,0,=0.5,r,(,r,-1)/,rC,nn,；对于,MMAS,，,t,0,=1/,rC,nn,；对于,ACS,，,t,0,=1/,nC,nn,。,释放信息素的蚂蚁个数,w,在,AS,rank,中，参数,w,设置为,w,=6,。,进化停滞判定代数,rs,在,MMAS,中，参数,rs,设置为,rs,=25,。,信息素局部挥发因子,x,在,ACS,中，参数,x,设置为,x,=0.1,。,伪随机因子,q,0,在,ACS,中，参数,q,0,设置为,q,0,=0.1,。,Thank You !,