蚁群算法 课件.ppt

1、蚁群算法,1.概述 2.基本蚁群算法 3.蚁群算法的参数选择 4.改进的蚁群算法 5.蚁群算法的应用实例,什么是群？ 指的是蜂群、鸟群、蚁群、鱼群等等，具有社会群居行为的动物。 群的特征： 1.相互作用的相邻个体的集合 2.个体的行为简单，只能完成一般工作 3.智能化的集体行为,1.概述,a.个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为。 b.没有一个集中控制中心，分布式、自组织 c.作为群体协同工作时，能够实现出非常复杂的行为特征智能,蚂蚁的觅食过程 1.随机移动 2.遇到食物分泌信息素 3.在搬运食物回家的路上留下信息素 4.其他蚂蚁发现留有信息素的路径结束漫游，沿该路径移

2、动，遇到食物同样开始分泌信息素。 5.信息素会随时间挥发，短路径上的信息素相对浓度高。,1.概述,什么是蚁群算法 蚁群算法的特点 1.能觉察小范围区域内状况，并判断出是否有食物或其他同类的信息激素轨迹； 2.能释放自己的信息激素； 3所遗留的信息激素数量会随时间而逐步减少。 蚂蚁系统：模拟蚁群突现聚集行为的蚁群算法，是作为一类新的计算模式引入的。 蚂蚁系统的提出,1.概述,它是一种通用的启发式算法，可用来解决各种不同的组合优化问题。,1.蚂蚁之间通过环境进行通信。 2.蚂蚁对环境的反应由其内部模式决定。 3.在个体水平上，每只蚂蚁仅根据环境做出独立选择。,2.1蚁群算法的原理 蚁群算法的思想：

3、 用蚂蚁的行走路线表示待求解问题的可行解，每只蚂蚁在解空间中独立的搜索可行解，解的质量越高，在“行走路线”上留下的信息激素也就越多，随着算法的推进，代表较好解的路线上的信息激素逐渐增多，选择它的蚂蚁也逐渐增多，最终整个蚁群在正反馈的作用下集中到代表最优解的路线上，也就找到了最优解。 人工蚁群与自然蚁群的异同点： 相似处：优先选择信息素浓度大的路径 区别：1.人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。 2.人工蚁群在选择下一条路径的时候，是按一定算法规律有意识的寻找最短路径，而不是盲目的。,2.基本蚁群算法,2.2蚁群算法的实现 各路径上信息激素物质的浓度为 ij(t+n)=(1-)

4、ij(t)+ij ij(t)表示时刻t在路径edge(i,j)上释放的信息素量；表示在时间t到t+n之间所经过路径上信息激素的蒸发系数；（1-）为信息激素残留因子 本次迭代中第k只蚂蚁释放在路径上的信息激素量 其中，,2.基本蚁群算法,Q为宜常量，用来表示蚂蚁释放的信息激素量， Lk是第k只蚂蚁完成一次旅行时所走过的路径总长度。,2.基本蚁群算法,Pkij(t)表示第k只蚂蚁由城市i向城市j转移的概率 式中allowedk表示第k只蚂蚁下一步允许选择的城市集合； 为信息启发式因子，表示轨迹的相对重要性； 为期望启发式因子，表示能见度的相对重要性； ij(t)为启发函数，表示蚂蚁从城市i转移到城

5、市j期望程度， ij(t)通常取城市i与城市j之间距离的倒数。 pkij(t)是关于信息激素量ij(t)和启发式因子ij的函数。 ij(t)给出了在过去有多少只蚂蚁选择走同一条路径的信息，而ij则表明一个城市越近，蚂蚁就越有可能向该城市移动。,2.基本蚁群算法,蚁群算法求解TSP的流程图如图8-1所示：,M.Dorigo提出了三种蚁群算法模型，本节所给出的算法称为Ant-Cycle;另外两个算法分别称为Ant-Quantity和Ant-Density,其差别主要是kij表示方式的区别。 在Ant-Quantity模型中， 在Ant-Density模型中,2.基本蚁群算法,蚁群算法的本质：蚁群算

6、法实际上是正反馈原理和启发式算法向结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息激素，而且用到了城市间距离的倒数作为启发式因子。实验结果表明， Ant-Cycle算法比Ant-Quantity和Ant-Density有更好的性能。原因是Ant-Cycle利用的是全局信息来更新路径上的信息激素量，而后两种算法使用的是局部信息。 蚁群算法优化过程的本质： 选择机制，信息量越大的路径，被选中的概率越大； 更新机制，路径上面的信息量会随蚂蚁的经过而增长，同时也随着时间的推移逐渐减小； 协调机制，蚂蚁之间实际上是通过信息量来相互通信、协同工作的。,2.基本蚁群算法,3.1蚁群算法参数对其性能的

7、影响 蚁群算法中的参数主要包括信息激素残留因子1-、信息启发式因子 、期望启发式因子、蚂蚁数目m、信息激素强度Q。 信息激素挥发因子的大小直接关系到蚁群算法的全局搜索能力及其收敛速度；而信息激素残留因子1-反映了蚂蚁之间个体相互影响的强弱。 启发式因子 反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值越大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性减弱；而当启发式因子 值过小时，则易使蚁群的搜索过早陷于最优。,3. 蚁群算法参数选择,期望启发式因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映了蚁群寻优过程中先验性、确定性因素的作用强度。其值越大，则

8、蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然这时算法的收敛速度得以加快，但蚁群搜索最优路径的随机性减弱，易陷于局部最优。 在Ant-Cycle模型中，信息激素强度Q为蚂蚁循环一周时释放在所经路径上的信息激素总量，其作用是为了充分利用有向图上的全局信息反馈量，使得算法在正反馈机制作用下以合理的演化速度搜索到所求问题的全局最优解。Q越大，则在蚂蚁已遍历路径上的信息激素的累积加快，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。,3. 蚁群算法参数选择,3.2蚁群算法参数选择方法 用蚁群算法求解问题，都存在算法有关参数的选择问题，较好的参数组合将会使得算法具有全局搜索能力和较快的收敛速

9、度；相反，不好的参数组合则会使得算法收敛速度过快或过慢，并且容易陷入局部最优解。由于缺乏理论指导，算法参数一般采用试探法来确定，造成工作量大，并且很难得到最优的参数选择，从而影响了算法的使用性能。文献【5】对基本蚁群算法的4个参数作了对比实验，即假定蚂蚁数目m等于城市的数目n；信息激素强度Q0.3,0.5, 0.7, 0.9, 0.999；参数0, 0.5, 1, 2, 5和0, 1, 2, 5，分别表示信息激素水平和城市间的距离对转移概率的贡献程度。,3. 蚁群算法参数选择,为了分析这些参数组合对算法性能的影响，固定前两个参数，而对 与各种组合进行分析，总共需要20组实验；但是若考虑Q的影响

10、，想做彻底的分析需要做100组实验，在加上蚂蚁数目m，则实验的组数难以承受。更重要的是，这些参数实际上相互耦合，相互联系，具有复杂的关系，仅取这些粗糙的值进行组合，难以找到参数的最优组合。 段海滨在对蚁群算法参数选择规律实验分析的基础上，总结出一种“三步走”选择蚁群算法最优组合参数的有效方法，具体步骤如下：确定蚂蚁数目，按城市规模/蚂蚁数目1.5的选择策略来确定蚂蚁的总数目；参数粗调，即调整取值范围较大的信息启发式因子 、期望启发式因子以及信息激素强度Q等参数，以得到较理想的解； 参数微调，即调整取值范围较小的信息激素挥发因子。,3. 蚁群算法参数选择,以上步骤反复进行，直到最终确定出一组较为

11、理想的组合参数为止。 蚁群算法的参数是影响蚁群算法求解性能和效率的关键因素，到目前为止蚁群算法还没像其他的启发式算法那样已形成系统的分析方法和具有坚实的数学基础，其参数的选择更多的是依靠实验和经验，没有定理来确定。,3. 蚁群算法参数选择,蚁群算法的优点： 具有较强的鲁棒性。 采用分布式计算机制。 具有良好的启发性。 易与其他方法结合。 改进的蚁群算法包括 Ant-Q蚁群算法 ACS算法 最大-最小蚂蚁系统 自适应蚁群算法,4.改进的蚁群算法,4.1 Ant-Q蚁群算法 Dorigo等人在基本蚁群算法的基础上提出了Ant-Q蚁群算法， Ant-Q算法中用来指引蚂蚁初始寻优的一个状态传递方程，也

12、称行为选择机制为 式中 为AQ值相对重要性系数；q为0,1上的随机数； q0是初始设定的参数， qq01, q0值越大，蚂蚁在转移时随机选择节点的概率就越小；J是式（8-4）式中计算出的概率；HE的作用同ij；AQ为学习因子，用来指导蚂蚁的运动，,4.改进的蚁群算法,也按照式(8-8)更新，即 式(8-7)式(8-8)进一步揭示了Ant-Q算法与强化学习算法的联系。实验结果表明，与基本蚁群算法相比， Ant-Q算法更具有一般性，而且更有利于全局搜索。 4.2 ACS算法 ACS算法继承了Ant-Q算法的优点并对基本蚁群算法模型做出了几点重要改进： ACS算法中，蚂蚁在寻找最佳路径的过程中只使用

13、局部信息，即采用局部信息对外信息激素浓度进行调整。 在蚂蚁所有寻优过程结束后，再一次调整信息激素浓度，而这次采用全局信息，只对过程中发现的路径上的信息激素浓度进行加强。,4.改进的蚁群算法,1.ACS算法的状态转移策略 位于城市i的蚂蚁k在t时刻选择下一城市j的策略如下： 其中0q01是初始设定的参数；q (0,1)为一随机数；S是根据式(8-10)决定的随机变量，即,4.改进的蚁群算法,如果随机数q小于初始值q0，则根据启发信息选择最大的一个；如果q q0，则根据式(8-10),根据概率的大小来选择下一个城市。这样既保证了搜索的收敛性性能好，又增强了搜索策略的多样性，以避免过早的陷于搜索停滞

14、状态。 信息激素局部更新策略 信息激素局部更新的作用是使已选择的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市i转移到城市j后，edge(i,j)上的信息激素量可按式(8-11)进行更新，即 ij(t+1)=(1-)*ij(t)+0 (8-11) 其中为(0,1)区间上的可调参数； 0为常数。,4.改进的蚁群算法,信息激素全局更新策略 当所有蚂蚁走完全部城市后，只有经过那些路径边上的蚂蚁才允许释放信息激素，按照式(8-12)进行更新。 其中为信息激素蒸发系数；Lk为最优路径的长度。 这种策略的目的是为了增强那些属于最优路径上的边的信息激素，可以大大增加这

15、些边上的信息激素。,4.改进的蚁群算法,4.3最大-最小蚂蚁系统 为了克服在Ant-Q算法中可能出现的停滞现象，Thomas等提出了最大-最小蚂蚁系统，该算法主要做了如下改进： 每次迭代结束后，只有最优解所属路径上的信息被更新，从而更好地利用了历史信息； 为了避免算法过早收敛于并非全局最优的解，将各条路径可能的外激素浓度限制于min ,max，超出这个范围的值被强制设为min或max，一方面避免了某条路径上的信息激素远大于其他路径的信息激素浓度，从而有效降低了过早停滞的可能。另一方面，不会因为某路径的信息激素浓度过低而丧失发现新路径的可能。各路径上外激素的起始浓度设为max，在算法的初始时刻，

16、 取较小的值时，算法有更好的发现较好解的能力。所有蚂蚁完成一次迭代后，按式(8-13),4.改进的蚁群算法,对路径上的信息作全局更新。 允许更新的路径可以是全局最优解，或本次迭代的最优解。实践证明，逐渐增加全局最优解的使用频率，会使该算法获得较好的性能。需要说明的是，仅采用最大-最小信息激素浓度的限制还不足以在较长的时间里持续消除停滞现象，因此，可以对其进一步改进，比如在该算法中引入信息激素的平滑机制等。,4.改进的蚁群算法,4.4自适应蚁群算法 蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨

17、在强化性能较好的解，却容易出现停滞现象，这是造成蚁群算法不足之处的根本原因。针对蚁群算法加速收敛和早熟、停滞现象的矛盾，因此提出了一种基于分布均匀度的自适应蚁群算法。该算法根据优化过程中解的分布均匀度，动态地调整信息量更新策略和选择路径概率，这样，可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。为此基于常规数学模型引入“聚度”的概念来衡量解的均匀程度，从而决定每次选择路径的概率以及信息量更新的策略。具体方法如下：,4.改进的蚁群算法,定义8.1 设从城市i共有r条路到达另外r个城市i1,i2,ir,另设上一次迭代中，经过这r条路径上的蚂蚁分别为a1,a2,ar,令城市i的聚度为 若在上一

18、次迭代中，m只蚂蚁遍历时经过以城市i为起点的r条路径的s条，设经过他们的蚂蚁个数分别a1,a2,ar,这些值均不为0，而其余路径上的蚂蚁个数均为0。城市的聚度i随s的减小而增大。 为使聚度的大小达到有效的平衡，以在改善蚂蚁搜索速度的同时避免局部优化，可考虑根据城市i的聚度sta(i)来,4.改进的蚁群算法,确定蚂蚁在该城市时下一步可选择的路径数，可取为 在路径选择过程中，蚂蚁仅考虑信息量最高的条路径。显然，当城市的聚度越大时，越大，蚂蚁下一步的分布范围越来越广；反之，聚度越小，蚂蚁搜索时分布范围就越小。 为了调整各个路径被选中的概率，引入“信息权重”这个量来限制信息量和期望程度，其总体原则是要

19、使信息量大的和当前局部最优的路径被选择的概率较大。,4.改进的蚁群算法,定义8.2以城市i为起点的r条路径按其信息量由高到低排序，序号依次存于数组rank中，即数组元素rankj的值为路径(i,j)的序号。下一步可供选择的路径条数为w，取 q=w/r，计算 则ij为路径(i,j)的信息权重。应用信息权重ij，蚂蚁由城市i按式(8-18)的概率选择城市j,即,4.改进的蚁群算法,式中对各路径上的信息量及期望程度都乘上了信息权重ij。 路径(i,j)的信息权重ij反映了蚂蚁从城市i选择下一个城市j时，路径(i,j)上的信息量ij(t)以及可访问度ij(t)对蚂蚁选择概率的影响程度。对于信息量较大的

20、路径，其信息权重较大，蚂蚁选择该路径的概率也较大。自适应更新信息量的过程如下： 根据信息量的均匀度自适应的进行信息量的更新，以动态调整各条路径上的信息量的分布，使其不至于过分集中或者分散，避免在加速收敛的同时成熟。信息量局部更新可根据以下策略：,4.改进的蚁群算法,由于蚂蚁常常选择信息量较大的路径，当多只蚂蚁选中同一路径后，信息量增加的幅度太大就容易使多只蚂蚁集中到该路径，因此取1/dij为增加的信息量。若选择该路径的蚂蚁达到一定数量或多数蚂蚁选择该路径后因当前距离超过上一次的最优路径长度终止遍历(这里分别设定为m/3和m/5),信息量则取-10/d0ij,这时可大幅度削减其信息量使其趋于各条

21、路径信息量的平均值，从而使蚂蚁选择其他路径的可能性增加，让搜索到的解趋于多样化。 信息量的整体更新可根据以下策略：,4.改进的蚁群算法,式中Ll(t)为本次迭代过程中第l只蚂蚁遍历的路径全长；l为第l只蚂蚁所对应的解对该路径上的信息量更新的影响程度。 l的计算方法为：设经过路径(i,j)的蚂蚁总数为K，对他们在本次迭代中遍历的路径全长由小到大进行排序，所得序号存放于数组rank中，即rankl表示第l只蚂蚁对应的序号。 算法的具体步骤为 算法1 自适应蚂蚁算法。 (1)初始化。随机产生m个初始解，设其中经过路径(i,j)的初始解有s个，他们的总长度分别为L1,L2,LS,则路径(i,j)上的初

22、始信息量为 其中Q为常数,4.改进的蚁群算法,(2)迭代过程,4.改进的蚁群算法,算法二选择算法 将allowedk集合中各条路径上的信息量由大到小排序，选择前w条路径将其序号记入数组rank中。计算与城市i相连的个路径的信息权重，按式(8-18)选择城市j。,4.改进的蚁群算法,4.5其他改进算法 除了Ant-Q蚁群算法、ACS算法、最大-最小蚂蚁系统、自适应蚁群算法等改进的蚁群算法外，还有其他的改进算法， 如引入变异算子、对信息激素进行重新分配、加入扰动等。 1.引入变异算法的目的是使信息激素的更新不过分集中，避免过早停滞。 2.信息激素的分配：基本上是采用全剧最好信息激素与迭代最好信息激

23、素混用的方法。 文献【14】采用类似于遗传算法中的选择算子，即当在非停滞状态时，信息激素的释放范围比基本蚁群算法缩小，对每次迭代所得到的部分较差的解，可以停止信息的分配，这样可以克服基本蚁群算法初期的长时间盲目搜索状态，加速收敛。,4.改进的蚁群算法,3.转移概率即加入扰动，即对转移概率中的ij(t)ij的参数和进行重新定义，如下面的扰动策略： 扰动策略的引入使得转移概率和信息激素更新规则同时得到变化，使其成为确定性与随机性同时作用动态机制。可以较好的平衡局部更新与全局更新的关系，达到全局优化的目的。,4.改进的蚁群算法,蚁群算法在解决很多组合优化问题上都取得比较理想的效果。一类应用于静态组合优化问题，另一类用于动态组合优化问题。另外，将蚁群算法对其他问题的解决也取得一定的进展，如大规模集成电路中的综合布线以及电信网络中的路由、参数优化、电力系统无功优化方面的应用。 1. 用蚁群算法求解TSP问题 31个城市的仿真结果如下图所示,5. 蚁群算法的应用实例,5. 蚁群算法的应用实例,