蚁群优化算法PPTPPT学习教案

《蚁群优化算法PPTPPT学习教案》由会员分享，可在线阅读，更多相关《蚁群优化算法PPTPPT学习教案（59页珍藏版）》请在装配图网上搜索。

1、会计学1第一页，共59页。2去人工蜂群算法 细菌觅食(m sh)算法 萤火虫算法粒子群算法 人工鱼群算法 鸟群算法第1页/共59页第二页，共59页。3 GambardellaMacro Dorigo第2页/共59页第三页，共59页。42001年至今(zhjn)1996年-2001年意大利学者(xuzh)Dorigo1991年Dorigo1991年 启发各种改进算法的提出，应用领域更广 引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为第3页/共59页第四页，共59页。5F类比：F大肠杆菌(d chn n jn)在人体肠道内觅食的过程信息素：信息素多的地方显然经过这里

2、的蚂蚁多，因而会有更多的蚂蚁聚集过来。正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。第4页/共59页第五页，共59页。6第5页/共59页第六页，共59页。7第6页/共59页第七页，共59页。8相似之处在于(ziy)：都是优先选择信息素浓度大的路径。两者的区别在于(ziy)：（1）人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。（2）人工蚁群选择路径时不是盲目的，而是按一定规律有意识地寻找最短路径。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。第7页/共59页第八页，共59页。9第8页/共59页第九页，共59页。10u 蚂蚁k(k=1,2，,m)根据各

3、个城市间连接路径上的信息素浓度(nngd)决定其下一个访问城市，设 表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：()(),()()()0,kisiskkisisijx allowkttsallowttPtsallow tPkiju 信息更新(gngxn)公式为：1(1)(1)(),01ijijijnkijiiktt 第9页/共59页第十页，共59页。11u 针对蚂蚁释放信息素问题，等人曾给出3中不同的模型(mxng)，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：/kij0,kkiiQ L，第 只蚂蚁从城市 访问城市其他ij/kij0,kiiQ d，第 只蚂蚁从城市 访问城

4、市其他kij0,kiiQ，第 只蚂蚁从城市 访问城市其他其中(qzhng)，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度；d为城市间的距离。第10页/共59页第十一页，共59页。12u 采用(ciyng)分布式控制 u 每个个体只能感知局部(jb)的信息 u 个体可以改变环境 u 具有自组织性 u 是一类概率型的全局搜索方法 u 优化过程不依赖于优化问题本身的严格数学性质 u 是一种基于多主体(Multi-Agent)的智能算法 u 具有潜在的并行性 第11页/共59页第十二页，共59页。13u 子集越大信息正反馈的作用不明显，搜索的随机性增强，造成收敛(shul

5、in)速度变慢;u 反之，子集越小，搜索的随机性减弱，虽然收敛(shulin)速度较快，但是会使算法的全局性能降低，影响算法的稳定性。信息素挥发度 的选取 u 信息素挥发度的大小对蚁群算法的收敛性能影响极大;u 当 比较小时，搜索的全局性好，但收敛速度变慢;u 当 比较大时，收敛速度比较快，但是容易陷入局部最优。第12页/共59页第十三页，共59页。14u 启发式因子的大小则反映了在蚁群路径搜索(su su)中的随机性因素作用的强度;u 启发式因子的大小反映了在蚁群路径搜索(su su)中确定性因素作用的强度。总信息量Q的选取 u 总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算法的快

6、速收敛。蚂蚁的初始分布 u 所有蚂蚁初始时刻放在同一个城市;u 蚂蚁分布在不同的城市中。第13页/共59页第十四页，共59页。15u M.Dorigo曾经对经典的TSP问题求解复杂度进行过深入的研究，所得到的经验结果表明，算法的时间复杂度为O(NCn2m)，NC表示迭代次数(csh)，n表示城市数，m则表示参与搜索的蚂蚁数量。当参与搜索的蚂蚁数量m大致与规模大小n相等时，算法的时间复杂度变为O(NCn3)较强的鲁棒性 分布式计算 易于与其他(qt)方法结合 u需要较长的搜索时间u容易出现停滞现第14页/共59页第十五页，共59页。16每次循环(xnhun)之后给予最优解以额外的信息素量这样的解

7、被称为全局最优解（global-best solution）找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)带精英策略的蚂蚁(my)系统（Ant System with elitist strategy,ASelite）是最早的改进蚂蚁(my)系统。遗传算法中的精英策略 蚂蚁系统中的精英策略 传统的遗传算法可能会导致最适应个体的遗传信息丢失精英策略的思想是保留住一代中的最适应个体第15页/共59页第十六页，共59页。17信息素根据(gnj)下式进行更新 *(1)()ijijijijtt其中(qzhng)1mkijijk,0,kkijQkL如果蚂蚁 在本次循环中经过路径(i,j)否则*

8、,0,ijQL如果边(i,j)是所找出的最优解的一部分否则第16页/共59页第十七页，共59页。18 表示精英蚂蚁引起(ynq)的路径(i,j)上的信息素量的增加 是所找出的最优解的路径长度(chngd)特点：是精英蚂蚁的个数 Lu 可以使蚂蚁系统找出更优的解u 找到这些解的时间更短 u 精英蚂蚁过多会导致搜索早熟收敛第17页/共59页第十八页，共59页。19 蚁群系统的状态转移(zhuny)规则 0arg max (,)(,),ku allowedr ur uqqsS如果按先验知识选择路径否则其中(qzhng)，S根据下列公式得：到()(),()()()0,kijijkkisisijs al

9、lowedttjallowedttPtotherwiseu 一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：第18页/共59页第十九页，共59页。20 蚁群系统(xtng)全局更新原则 1,(,)0,gbLr s如果(r,s)全局最优路径否则(,)(1)(,)(,)r sr sr su 只有全局最优的蚂蚁才被允许释放(shfng)信息素。u 目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。u 全局更新在所有蚂蚁都完成它们的路径之后执行，用下式对所建立的路径进行更新：第19页/共59页第二十页，共59页。21 蚁群系统(xtng)局部更新原则 u 类似于蚁

10、密和蚁量模型(mxng)中的更新规则 u 蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新(,)(1)(,)(,)01r sr sr s其中，u 实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度nnLnn0Ln1u 局部更新规则可以有效地避免蚂蚁收敛到同一路径第20页/共59页第二十一页，共59页。22信息素轨迹更新(gngxn)原则 u在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改(xigi)的轨迹更新原则如下：u 表示迭代最优解或全局最优解的值。u在蚁群算法(sun f)中主要使用全局最优解，而在MMAS中则主要使用迭代最优解。第2

11、1页/共59页第二十二页，共59页。23信息素轨迹(guj)的限制 uMMAS对信息素轨迹的最小值和最大值分别施加了 和 的限制(xinzh)，从而使得对所有信息素轨迹 ，有u 的选取要基于两点假设：1.最优解在搜索停滞发生(fshng)之前不久被找出。2.对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定第22页/共59页第二十三页，共59页。24信息(xnx)素轨迹的平滑化u基本思想：通过增加选择有着低强度信息(xnx)素轨迹量解元素的概率以提高探索新解的能力u平滑机制有助于对搜索空间(kngjin)进行更有效的探索*max()()()()ijijijtttt*()()ijij

12、tt其中,01,和分别为平滑化之前和之后的信息素轨迹量第23页/共59页第二十四页，共59页。25第24页/共59页第二十五页，共59页。26第25页/共59页第二十六页，共59页。27TSP问题(wnt)u问题描述：旅行(lxng)商按一定的顺序访问n个城市，使得每个城市都被访问且仅能被访问一次而使花费代价最小，从图论的观点来看，就是找出一个最短的封闭回路。uTSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长uTSP在许多工程领域具有广泛的应用价值，例如电路板布线、机器人控制、交通路由等。第26页/共59页第二十七页，共59页。28第27页/共59页第二十八页，共5

13、9页。29下面以TSP为例说明基本蚁群算法(sun f)模型。u首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择(xunz)下一个城市j的概率为:u 表示边（i，j）上的信息素浓度；是启发信息，d是城市i和j之间的距离；和反映了信息素与启发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。)1(,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(ji),(/1),(jidjiktabu第28页/共59页第二十九页，共59页。30u当所有蚂蚁完成(wn chng)周游后，按以下公式进行信息素更新。u其中，为小于1的常数(ch

14、ngsh)，表示信息的持久性。)2()()(1mkkijijijijijtnt)3(0otherwiselijLQkkkiju其中，Q为常数；表示第k只蚂蚁在本次迭代中走过的路径长度。kL第29页/共59页第三十页，共59页。31InitializationDistribute the ants,Modify the tabu Calculate the probability of moving between citiesi+Update pheromone between cities Meet the requirement of the solution Number of trav

15、erse city i=1outputMove to j and modify the tabuNYCalculate the distance each ant walks the loopYNEach ant choose the next city 第30页/共59页第三十一页，共59页。32第31页/共59页第三十二页，共59页。33第32页/共59页第三十三页，共59页。34第33页/共59页第三十四页，共59页。35第34页/共59页第三十五页，共59页。361.5602e+04ACATSP(C,100,10,1,5,0.1,100)第35页/共59页第三十六页，共59页。37第3

16、6页/共59页第三十七页，共59页。38趋向性操作(cozu)设细菌种群大小为S，一个细菌所处(su ch)的位置表示一个问题的候选解，细菌i的信息用D维向量表示为12,1,2,iiiiDiS 细菌i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置表示为细菌i的每一步趋向性操作表示如下：(1,)(,)()()iijk lj k lC ijC(i)0 表示向前游动的步长单位 表示旋转后选择的一个随机前进方向()j第37页/共59页第三十八页，共59页。39第38页/共59页第三十九页，共59页。40第39页/共59页第四十页，共59页。41F类比：其他群智能算法的聚群行为(xngwi

17、)：F花蜜源比较差的侦查蜂转向花蜜源比较好的侦查蜂，变成跟随蜂 -舞蹈F 亮度比较弱的萤火虫转向亮度比较好的萤火虫-荧光素第40页/共59页第四十一页，共59页。42F其他群智能算法的淘汰(toti)机制：F花蜜源比较差的侦查蜂转向花蜜源比较好的侦查蜂过程 淘汰(toti)花蜜源比较差的蜜蜂F萤火虫亮度比较弱的淘汰(toti)第41页/共59页第四十二页，共59页。43前提(qint)经过复制操作后算法的种群(zhn qn)大小不变第42页/共59页第四十三页，共59页。44第43页/共59页第四十四页，共59页。45第44页/共59页第四十五页，共59页。46输入：运行(ynxng)相关的参

18、数组初始化（菌落在搜索环境中随机散开，并初始化每一个(y)个体的健康指标向量，三层循环的l,j,k索引均为0）驱散(q sn)索引：l=l+1jNc?复制（依据health进行排序，淘汰后一半，复制前一半）驱散（对每一个细菌：取一随机数，若小于驱散概率，则重新初始化）kNre?lNed?复制索引:k=k+1寻优终止输出环境最好的位置和相应值趋向索引:j=j+1种群趋向是重初始趋向索引重初始化趋向，复制索引j=0,k=0第45页/共59页第四十六页，共59页。47第46页/共59页第四十七页，共59页。48自适应步长调整策略 在趋向行为中，原始BFO使用固定(gdng)步长求解问题不利于算法的收

19、敛。因此提出了一种基于细菌拥挤度的自适应步长调整策略。当 crowd较小时，细菌以较大的步长寻优;当crowd 较大时，细菌以较小的步长寻优。这样能够保证算法在优化初期有很强的全局搜索能力(nngl)，在优化后期有很强的局部开采能力(nngl)。第47页/共59页第四十八页，共59页。49基于环境感知的细菌觅食优化算法 在趋向行为中，赋予细菌对周围细菌状态进行感知。在执行(zhxng)中，所有细菌按照适应度分成两类：优于适应度平均值的，通过追踪最优细菌进行搜索；劣于适应度平均值的，通过追踪细菌群体中心位置进行搜索。第一种情况：相当于细菌位置的精细(jngx)搜索。第二种情况：有助于全局最优和快

20、速收敛。第48页/共59页第四十九页，共59页。50具有协同思想的细菌觅食优化算法 针对细菌趋向行为中随机翻转和游动环节，引入PSO算法粒子向个体和社会学习的思想，赋予细菌能够记忆当前细菌群体的最优位置和最优解。在翻转过程中适应度变差，则向群体最优学习。若随机转向(zhunxing)失效，则反方向学习。除此之外：基于免疫进化的细菌(xjn)觅食优化算法基于高斯分布的细菌(xjn)觅食算法第49页/共59页第五十页，共59页。51车间调度问题(wnt)（Job-Scheduling Problem，简称JSP），指车间有一些机器和一些工件，每个工件都有其特定的加工顺序，现用m台机器加工n个工件，

21、每个工件都有若干有序操作组成，每个操作必须在指定的机器上才能完成。每台机器在同一时刻只能进行一个工序操作。第50页/共59页第五十一页，共59页。52第51页/共59页第五十二页，共59页。53第52页/共59页第五十三页，共59页。54实际(shj)实验的Benchmark算例第53页/共59页第五十四页，共59页。55BFO算法的JSP问题性能(xngnng)测试（minF=59）第54页/共59页第五十五页，共59页。56环境(hunjng)感知BFO算法的JSP问题性能测试（minF=58）第55页/共59页第五十六页，共59页。57具有协同思想(sxing)的BFO算法的JSP问题性能测试（minF=59）第56页/共59页第五十七页，共59页。58BFO算法与PSO算法30次随机测试(csh)结果比较第57页/共59页第五十八页，共59页。59第58页/共59页第五十九页，共59页。