赵工的个人空间


专业技术部分转网页计算转业余爱好部分


 图像处理与人工智能

首页 > 专业技术 > 图像处理与人工智能 > 人工智能蚁群算法
人工智能蚁群算法

蚁群算法ACO(Ant Colony Optimization)又称蚂蚁算法,是一种用来在图中寻找优化路径几率的算法。蚁群算法由Dorigo于1992年提出,灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

1. 蚁群算法基本原理:

蚁群优化算法是模拟蚂蚁觅食的原理。蚂蚁在觅食过程中能够在其经过的路径上留下称为信息素的物质,并在觅食过程中感知这种物质的强度,并指导行动方向。它们总是朝着该物质强度高的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。
某一条路径越短,路径上经过的蚂蚁越多,其信息素遗留的也就越多,信息素的浓度也就越高,蚂蚁选择这条路的几率也就越高,由此构成正反馈过程,从而逐渐逼近最优路径。
人工蚂蚁的搜索主要包括三种行为:
·蚂蚁利用信息素进行相互通信
·蚂蚁的记忆行为
·蚂蚁的集群活动
常见有多种蚁群算法过程。
1)蚂蚁系统:
蚂蚁系统是最早的蚁群系统,其搜索过程大致为:
在初始时刻,m只蚂蚁随机放置于初始地点中,各个路径上的信息素初始值相等,设τij(0)=τ0,可设初始值τ0=m/Lm,Lm为由最近邻启发式方法构造的路径长度。
其次,蚂蚁k按照随机比例规则选择下一步要转移的地点,其选择概率为:
蚁群算法
其中,τij为(i,j)上的信息素;ηij=1/dij为从地点i转移到地点j的启发式因子;ak为蚂蚁k下一步被允许访问的地点集合。
为了不让蚂蚁选择已经访问过的地点,采用禁忌表tak来记录蚂蚁k当前所走过的地点。经过t时刻,所有蚂蚁都完成一次周游,计算每只蚂蚁所走过的路径长度,并保存最短的路径长度,同时更新各边上的信息素。
信息素挥发,蚂蚁在它们经过的边上释放信息素,计算公式为:
蚁群算法        蚁群算法
式中,ρ为信息素挥发系数,0<ρ≤1。第k只蚂蚁向它经过的边释放的信息素为:
蚁群算法
根据公式,蚂蚁构建的路径长度dij越小,则路径上各边就会获得更多的信息素,在以后的迭代中就更有可能被其他蚂蚁选择。
蚂蚁完成一次循环后,清空禁忌表,重新回到初始地点,准备下一次周游。
蚂蚁系统在解决小规模TSP问题时性能尚可,能较快发现最优解,但是随着测试问题规模的扩大,系统性能下降比较严重,容易出现停滞现象,因此出现大量改进算法。
TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
2)精英蚂蚁系统:
精英蚂蚁系统是对基本蚂蚁系统算法的改进,其设计思想是对每次循环之后给予最优路径额外的信息素量,找出这个解的蚂蚁称精英蚂蚁。将这条最优路径记为Tbs,针对路径Tbs的额外强化是通过向Tbs中的每一条边增加e/Lbs大小的信息素得到,其中e是一个参数,定义了给予路径Tbs的权值大小,Lbs代表了Tbs的长度。信息素的更新公式为:
蚁群算法
其中,最后一项的定义为:
蚁群算法
使用精英策略并选取一个适当的e值,将使得蚂蚁系统算法不但可以得到更好的解,而且能够在更少的迭代次数下得到一些更好的解。
3)最大-最小蚂蚁系统:
最大-最小蚂蚁系统是到目前为止解决TSP问题最好的算法方案之一,主要做了以下改进:
⑴将各条路径可能的外激素浓度限制于[τmin,τmax],超出这个范围的值被强制设为τmin或τmax。这可以避免算法过早收敛于局部最优解,有效地避免某条路径上的信息素量远大于其余路径,避免所有蚂蚁都集中到同一条路径上。
⑵信息素的初始值被设定为其取值范围的上界。在算法的初始时刻,ρ取较小的值时,算法有更好的发现较好解的能力。
⑶强调对最优解的利用。每次迭代结束后,只有最优解所属路径上的信息被更新,从而更好地利用了历史信息。
所有蚂蚁完成一次迭代后,对路径上的信息做全局更新:
蚁群算法
蚁群算法
允许更新的路径可以是全局最优解,或本次迭代的最优解。逐渐增加全局最优解的使用频率,会使该算法获得较好的性能。
4)基于排序的蚁群算法:
基于排序的蚂蚁系统的改进思想是:在每次迭代完成后,蚂蚁所经路径将按从小打到的顺序排列,算法根据路径长度赋予不同的权重,路径长度越短权重越大。全局最优解的权重为w,第r个最优解的权重为max{0,w-r},则信息素更新规则为:
蚁群算法
式中:
蚁群算法
5)蚁群系统:
蚁群系统是Dorigo等提出来的改进的蚁群算法,改进体现的三个方面:
·除了全局信息素更新规则外,还采用了局部信息素更新规则
·信息素挥发和信息素释放动作只在至今最优路径的边上执行
·采用不同的路径选择规则,能更好地利用蚂蚁所积累的搜索经验
在蚁群系统中,位于地点i的蚂蚁k,根据伪随机比例规则选择地点j作为下一个访问的地点。路径选择规则由下式给出:
蚁群算法      蚁群算法
式中,q为均匀分布在区间[0,1]中的一个随机量;0≤q0≤1,是一个参数;J为根据以上公式给出的概率分布产生出来的一个随机比例,其中ɑ=1。
蚁群系统的全局信息素更新规则为:
蚁群算法        蚁群算法
蚁群系统的局部信息更新规则方式为:
在路径构建过程中,蚂蚁每经过一条边(i,j),都将立刻调用这条规则更新该边上的信息素:
蚁群算法
式中,ξ和τ0为两个参数,0<ξ<1,τ0为信息素的初始量。
局部更新的作用在于,蚂蚁每一次经过边(i,j),该边的信息素τij将会减少,从而使得其他蚂蚁选中该边的概率相对减少。

2. 自适应蚁群算法:

蚁群算法在构造解的过程中,利用随机选择策略,这种策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象。在选择策略方面采用确定性选择和随机选择相结合的选择策略,并且在搜索过程中动态地调整确定性选择的概率;当进化到一定代数后,进化方向基本确定,这时对路径上信息量做动态调整。
缩小最好和最差路径上的信息量的差距,并且适当加大随机选择的概率,以小于1对解空间的更完全搜索,可以有效地克服基本蚁群算法的不足,此算法属于自适应算法。
蚂蚁在行进过程中常常选择信息量较大的路径,但许多蚂蚁选中同一条路径时,该路径中的信息量就会陡然增大,从而使得多只蚂蚁集中到某一条路径上,造成一种堵塞和停滞现象,表现在使用蚁群算法解决问题时就容易导致早熟和局部收敛。
自适应蚁群算法建立了一种新的自适应的信息量更新策略。当问题规模较大时,由于信息量挥发系数的存在,使那些从未被搜索过的路径上的信息量减小到接近为0,从而降低了算法在这些路径上的搜索能力;反之,当某条路径中信息量较大时,这些路径中的信息量增大,搜索过的路径再次被选择的机会就会变得较大。
搜索过的路径再次被选择的机会变大,会影响算法的全局搜索能力,此时通过固定地变化挥发系数虽然可以提高全局搜索能力,但却使算法的收敛速度降低。自适应蚁群算法提出一种自适应的改变τ值的方法,将信息素更新的公式变为:
蚁群算法
式中,φ(m)=m/c,是一个与收敛次数m成正比的函数,收敛次数m越多,φ(m)的取值越大,c为常数。
根据解的分布情况自适应地进行信息量的更新,从而动态地调整各路径上的信息量强度,使蚂蚁既不过分集中也不过分分散,从而避免了早熟和局部收敛,提高全局搜索能力。

3. 蚁群算法的重要规则:

⑴避障规则:如果蚂蚁要移动方法有障碍物,会随机选择另一个方向。
⑵播散信息素规则:每只蚂蚁在刚找到食物或者窝时,撒的信息素最多,并随着走远的距离,撒的信息素越来越少。
⑶范围:蚂蚁观察到的范围是一个方格世界,有一个参数为速度半径,一般为3,那么能观察到的范围是3x3的方格世界,并且能移动的距离也在这个范围内。
⑷移动规则:每只蚂蚁都朝向信息素最多的方向移动,当周围没有信息素指引时,蚂蚁会按照自己原来运动的方向惯性运动下去,而且在运动方向有一个随机小扰动。为了防止蚂蚁原地转圈,会记住最近刚走过了哪些点,如果发现要走的下一点已经在最近走过了,就会尽量避开。
⑸觅食规则:在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去,否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过对窝的信息素做出反应,而对食物信息素没反应。
⑹环境:蚂蚁所在的环境是一个虚拟世界,其中有障碍物、其他蚂蚁、信息素,信息素有两种,一种是找到食物的蚂蚁撒的食物信息素,一种是找到窝的蚂蚁撒的窝信息素。每只蚂蚁都仅仅能感知它范围内的环境信息,环境以一定的速率让信息素消失。
根据这几条规则,蚂蚁之间并没有直接关系,但是每只蚂蚁都和环境发生交互,通过信息素这个纽带,实际上把各个蚂蚁之间关联起来。

 

Copyright@dwenzhao.cn All Rights Reserved   备案号:粤ICP备15026949号
联系邮箱:dwenzhao@163.com  QQ:1608288659