您好,欢迎访问三七文档
1.概述2.基本蚁群算法3.蚁群算法的参数选择4.改进的蚁群算法5.蚁群算法的应用实例什么是群?指的是蜂群、鸟群、蚁群、鱼群等等,具有社会群居行为的动物。群的特征:1.相互作用的相邻个体的集合2.个体的行为简单,只能完成一般工作3.智能化的集体行为a.个体间不仅能够交互信息,还能够处理信息,根据信息改变自身行为。b.没有一个集中控制中心,分布式、自组织c.作为群体协同工作时,能够实现出非常复杂的行为特征——智能蚂蚁的觅食过程1.随机移动2.遇到食物分泌信息素3.在搬运食物回家的路上留下信息素4.其他蚂蚁发现留有信息素的路径结束漫游,沿该路径移动,遇到食物同样开始分泌信息素。5.信息素会随时间挥发,短路径上的信息素相对浓度高。什么是蚁群算法蚁群算法的特点1.能觉察小范围区域内状况,并判断出是否有食物或其他同类的信息激素轨迹;2.能释放自己的信息激素;3所遗留的信息激素数量会随时间而逐步减少。蚂蚁系统:模拟蚁群突现聚集行为的蚁群算法,是作为一类新的计算模式引入的。蚂蚁系统的提出它是一种通用的启发式算法,可用来解决各种不同的组合优化问题。1.蚂蚁之间通过环境进行通信。2.蚂蚁对环境的反应由其内部模式决定。3.在个体水平上,每只蚂蚁仅根据环境做出独立选择。2.1蚁群算法的原理蚁群算法的思想:用蚂蚁的行走路线表示待求解问题的可行解,每只蚂蚁在解空间中独立的搜索可行解,解的质量越高,在“行走路线”上留下的信息激素也就越多,随着算法的推进,代表较好解的路线上的信息激素逐渐增多,选择它的蚂蚁也逐渐增多,最终整个蚁群在正反馈的作用下集中到代表最优解的路线上,也就找到了最优解。人工蚁群与自然蚁群的异同点:相似处:优先选择信息素浓度大的路径区别:1.人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。2.人工蚁群在选择下一条路径的时候,是按一定算法规律有意识的寻找最短路径,而不是盲目的。2.2蚁群算法的实现各路径上信息激素物质的浓度为τij(t+n)=(1-ρ)∙τij(t)+Δτijτij(t)表示时刻t在路径edge(i,j)上释放的信息素量;ρ表示在时间t到t+n之间所经过路径上信息激素的蒸发系数;(1-ρ)为信息激素残留因子本次迭代中第k只蚂蚁释放在路径上的信息激素量其中,Q为宜常量,用来表示蚂蚁释放的信息激素量,Lk是第k只蚂蚁完成一次旅行时所走过的路径总长度。Pkij(t)表示第k只蚂蚁由城市i向城市j转移的概率式中allowedk表示第k只蚂蚁下一步允许选择的城市集合;α为信息启发式因子,表示轨迹的相对重要性;β为期望启发式因子,表示能见度的相对重要性;ηij(t)为启发函数,表示蚂蚁从城市i转移到城市j期望程度,ηij(t)通常取城市i与城市j之间距离的倒数。pkij(t)是关于信息激素量τij(t)和启发式因子ηij的函数。τij(t)给出了在过去有多少只蚂蚁选择走同一条路径的信息,而ηij则表明一个城市越近,蚂蚁就越有可能向该城市移动。蚁群算法求解TSP的流程图如图8-1所示:M.Dorigo提出了三种蚁群算法模型,本节所给出的算法称为Ant-Cycle;另外两个算法分别称为Ant-Quantity和Ant-Density,其差别主要是Δτkij表示方式的区别。在Ant-Quantity模型中,在Ant-Density模型中蚁群算法的本质:蚁群算法实际上是正反馈原理和启发式算法向结合的一种算法。在选择路径时,蚂蚁不仅利用了路径上的信息激素,而且用到了城市间距离的倒数作为启发式因子。实验结果表明,Ant-Cycle算法比Ant-Quantity和Ant-Density有更好的性能。原因是Ant-Cycle利用的是全局信息来更新路径上的信息激素量,而后两种算法使用的是局部信息。蚁群算法优化过程的本质:①选择机制,信息量越大的路径,被选中的概率越大;②更新机制,路径上面的信息量会随蚂蚁的经过而增长,同时也随着时间的推移逐渐减小;③协调机制,蚂蚁之间实际上是通过信息量来相互通信、协同工作的。3.1蚁群算法参数对其性能的影响蚁群算法中的参数主要包括信息激素残留因子1-ρ、信息启发式因子α、期望启发式因子β、蚂蚁数目m、信息激素强度Q。信息激素挥发因子ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度;而信息激素残留因子1-ρ反映了蚂蚁之间个体相互影响的强弱。启发式因子α反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度,其值越大,蚂蚁选择以前走过路径的可能性就越大,搜索的随机性减弱;而当启发式因子α值过小时,则易使蚁群的搜索过早陷于最优。期望启发式因子β反映了启发式信息在指导蚁群搜索过程中的相对重要程度,其大小反映了蚁群寻优过程中先验性、确定性因素的作用强度。其值越大,则蚂蚁在某个局部点上选择局部最短路径的可能性越大,虽然这时算法的收敛速度得以加快,但蚁群搜索最优路径的随机性减弱,易陷于局部最优。在Ant-Cycle模型中,信息激素强度Q为蚂蚁循环一周时释放在所经路径上的信息激素总量,其作用是为了充分利用有向图上的全局信息反馈量,使得算法在正反馈机制作用下以合理的演化速度搜索到所求问题的全局最优解。Q越大,则在蚂蚁已遍历路径上的信息激素的累积加快,可以加强蚁群搜索时的正反馈性能,有助于算法的快速收敛。3.2蚁群算法参数选择方法用蚁群算法求解问题,都存在算法有关参数的选择问题,较好的参数组合将会使得算法具有全局搜索能力和较快的收敛速度;相反,不好的参数组合则会使得算法收敛速度过快或过慢,并且容易陷入局部最优解。由于缺乏理论指导,算法参数一般采用试探法来确定,造成工作量大,并且很难得到最优的参数选择,从而影响了算法的使用性能。文献【5】对基本蚁群算法的4个参数作了对比实验,即假定蚂蚁数目m等于城市的数目n;信息激素强度Qϵ{0.3,0.5,0.7,0.9,0.999};参数αϵ{0,0.5,1,2,5}和βϵ{0,1,2,5},分别表示信息激素水平和城市间的距离对转移概率的贡献程度。为了分析这些参数组合对算法性能的影响,固定前两个参数,而对α与β各种组合进行分析,总共需要20组实验;但是若考虑Q的影响,想做彻底的分析需要做100组实验,在加上蚂蚁数目m,则实验的组数难以承受。更重要的是,这些参数实际上相互耦合,相互联系,具有复杂的关系,仅取这些粗糙的值进行组合,难以找到参数的最优组合。段海滨在对蚁群算法参数选择规律实验分析的基础上,总结出一种“三步走”选择蚁群算法最优组合参数的有效方法,具体步骤如下:⑴确定蚂蚁数目,按城市规模/蚂蚁数目≈1.5的选择策略来确定蚂蚁的总数目;⑵参数粗调,即调整取值范围较大的信息启发式因子α、期望启发式因子β以及信息激素强度Q等参数,以得到较理想的解;⑶参数微调,即调整取值范围较小的信息激素挥发因子ρ。以上步骤反复进行,直到最终确定出一组较为理想的组合参数为止。蚁群算法的参数是影响蚁群算法求解性能和效率的关键因素,到目前为止蚁群算法还没像其他的启发式算法那样已形成系统的分析方法和具有坚实的数学基础,其参数的选择更多的是依靠实验和经验,没有定理来确定。蚁群算法的优点:⑴具有较强的鲁棒性。⑵采用分布式计算机制。⑶具有良好的启发性。⑷易与其他方法结合。改进的蚁群算法包括①Ant-Q蚁群算法②ACS算法③最大-最小蚂蚁系统④自适应蚁群算法4.1Ant-Q蚁群算法Dorigo等人在基本蚁群算法的基础上提出了Ant-Q蚁群算法,Ant-Q算法中用来指引蚂蚁初始寻优的一个状态传递方程,也称行为选择机制为式中δ为AQ值相对重要性系数;q为[0,1]上的随机数;q0是初始设定的参数,q≤q0≤1,q0值越大,蚂蚁在转移时随机选择节点的概率就越小;J是式(8-4)式中计算出的概率;HE的作用同ηij;AQ为学习因子,用来指导蚂蚁的运动,也按照式(8-8)更新,即式(8-7)式(8-8)进一步揭示了Ant-Q算法与强化学习算法的联系。实验结果表明,与基本蚁群算法相比,Ant-Q算法更具有一般性,而且更有利于全局搜索。4.2ACS算法ACS算法继承了Ant-Q算法的优点并对基本蚁群算法模型做出了几点重要改进:⑴ACS算法中,蚂蚁在寻找最佳路径的过程中只使用局部信息,即采用局部信息对外信息激素浓度进行调整。⑵在蚂蚁所有寻优过程结束后,再一次调整信息激素浓度,而这次采用全局信息,只对过程中发现的路径上的信息激素浓度进行加强。1.ACS算法的状态转移策略位于城市i的蚂蚁k在t时刻选择下一城市j的策略如下:其中0q01是初始设定的参数;qϵ(0,1)为一随机数;S是根据式(8-10)决定的随机变量,即如果随机数q小于初始值q0,则根据启发信息选择最大的一个;如果q﹥q0,则根据式(8-10),根据概率的大小来选择下一个城市。这样既保证了搜索的收敛性性能好,又增强了搜索策略的多样性,以避免过早的陷于搜索停滞状态。信息激素局部更新策略信息激素局部更新的作用是使已选择的边对后来的蚂蚁具有较小的影响力,从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市i转移到城市j后,edge(i,j)上的信息激素量可按式(8-11)进行更新,即τij(t+1)=(1-ξ)*τij(t)+ξ∙τ0(8-11)其中ξ为(0,1)区间上的可调参数;τ0为常数。信息激素全局更新策略当所有蚂蚁走完全部城市后,只有经过那些路径边上的蚂蚁才允许释放信息激素,按照式(8-12)进行更新。其中ρ为信息激素蒸发系数;Lk为最优路径的长度。这种策略的目的是为了增强那些属于最优路径上的边的信息激素,可以大大增加这些边上的信息激素。4.3最大-最小蚂蚁系统为了克服在Ant-Q算法中可能出现的停滞现象,Thomas等提出了最大-最小蚂蚁系统,该算法主要做了如下改进:①每次迭代结束后,只有最优解所属路径上的信息被更新,从而更好地利用了历史信息;②为了避免算法过早收敛于并非全局最优的解,将各条路径可能的外激素浓度限制于[τmin,τmax],超出这个范围的值被强制设为τmin或τmax,一方面避免了某条路径上的信息激素远大于其他路径的信息激素浓度,从而有效降低了过早停滞的可能。另一方面,不会因为某路径的信息激素浓度过低而丧失发现新路径的可能。各路径上外激素的起始浓度设为τmax,在算法的初始时刻,ρ取较小的值时,算法有更好的发现较好解的能力。所有蚂蚁完成一次迭代后,按式(8-13)对路径上的信息作全局更新。允许更新的路径可以是全局最优解,或本次迭代的最优解。实践证明,逐渐增加全局最优解的使用频率,会使该算法获得较好的性能。需要说明的是,仅采用最大-最小信息激素浓度的限制还不足以在较长的时间里持续消除停滞现象,因此,可以对其进一步改进,比如在该算法中引入信息激素的平滑机制等。4.4自适应蚁群算法蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。这种算法在构造解的过程中,利用随机选择策略,这种选择策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象,这是造成蚁群算法不足之处的根本原因。针对蚁群算法加速收敛和早熟、停滞现象的矛盾,因此提出了一种基于分布均匀度的自适应蚁群算法。该算法根据优化过程中解的分布均匀度,动态地调整信息量更新策略和选择路径概率,这样,可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。为此基于常规数学模型引入“聚度”的概念来衡量解的均匀程度,从而决定每次选择路径的概率以及信息量更新的策略。具体方法如下:定义8.1设从城市i共有r条路到达另外r个城市i1,i2,…,ir,另设上一次迭代中,经过这r条路径上的蚂蚁分别为a1,a2,…,ar,令城市i的聚度为若在上一次迭代中,m只蚂蚁遍历时经过以城市i为起点的r条路径的s条,设经过他们的蚂蚁个数分别a1,a2,…,ar,这些值均不为0,而其余路径上的蚂蚁个数均为0。城市的聚度i随s的减小而
本文标题:蚁群算法
链接地址:https://www.777doc.com/doc-4573962 .html