蚁群算法简述及实现

蚁群算法简述及实现1蚁群算法的原理分析蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(ReinforcementLearningSystem)。引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。（a）（b）（c）图1蚁群路径搜索实例这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。2人工蚁群算法描述蚁群算法可以看作为一种基于解空间参数化概率分布模型(ParameterizedProbabilisticModel)的搜索算法框架(Model-basedsearchalgorithms)。在蚁群算法中,解空间参数化概率,模型的参数就是信息素,因而这种参数化概率分布模型就是信息素模型。在基于模型的搜索算法框架中,可行解通过在一个解空间参数化概率分布模型上的搜索产生,此模型的参数用以前产生的解来更新,使得在新模型上的搜索能够集中在高质量的解搜索空间内。这种方法的有效性建立在高质量的解总是包含好的解构成元素的假设前提下。通过学习这种解构成元素对解的质量的影响有助于找到一种机制,并通过解构成元素的最佳组合来构造出高质量的解。一般来说,一个记忆模型的搜索算法通常使用以下两步迭代来解决优化问题:1)可行解通过在解空间参数化概率分布模型上的搜索产生。2)用搜索产生的解来更新参数化概率模型,即更新解空间参数化概率分布的参数,使得在新模型上的参数搜索能够集中在高质量的解搜索空间内。在蚁群算法中,基于信息素的解空间参数化概率模型(信息素模型)以解构造图的形式给出。在解构造图上,定义了一种作为随机搜索机制的人工蚁群,蚂蚁通过一种分布在解构造图上被称为信息素的局部信息的指引,在解构造图上移动,从而逐步的构造出问题的可行。信息素与解构造图上的节点或弧相关联,作为解空间参数化概率分布模型的参数。由于TSP问题可以直接的映射为解构造图(城市为节点,城市间的路径为弧,信息素分布在弧上),加之TSP问题也是个NP难题,所以,蚁群算法的大部分应用都集中在TSP问题上。一般而言,用于求解TSP问题、生产调度问题等优化问题的蚁群算法都遵循下面的统一算法框架。算法1：求解组合优化问题的蚁群算法设置参数,初始化信息素踪迹While(不满足条件时)dofor蚁群中的每只蚂蚁for每个解构造步(直到构造出完整的可行解)1)蚂蚁按照信息素及启发式信息的指引构造一步问题的解;2)进行信息素局部更新。(可选)endforendfor1)以某些已获得的解为起点进行邻域(局部)搜索;(可选)2)根据某些已获得的解的质量进行全局信息素更新。endwhileend在算法1中,蚂蚁逐步的构造问题的可行解,在一步解的构造过程中,蚂蚁以概率方式选择信息素强且启发式因子高的弧到达下一个节点,直到不能继续移动为止。此时蚂蚁所走过的路径对应求解问题的一个可行解。局部信息素更新针对蚂蚁当前走过的一步路径上的信息素进行,全局信息素更新是在所有蚂蚁找到可行解之后,根据发现解的质量或当前算法找到的最好解对路径上的信息素进行更新。3蚁群算法与其他搜索算法比较3.1蚁群算法与进化算法比较近年来,遗传算法(GA)、进化规划(EvolutionaryPlanning)、进化策略(EvolutionaryStrategies)在理论和应用上发展迅速、效果显著并逐渐走向了融合,形成了一种新颖的模拟进所走过的路径便是TSP问题的一个可行解。式(4.1)中的ηij通常取城市i和城市j之间距离的倒数。α和β分别表示信息素和启发式因子的相对重要程度。当所有蚂蚁完成一次周游以后,各路径上的信息素根据下式更新。τijt+n=ρ∆τij=其中ρ(0<ρ<l)表示信息残留系数,用1-ρ表示信息素的挥发系数。关于∆τijk的计算方法,M.Dorigo曾给出三种不同的实现方法,分别对应三种不同的蚂蚁系统模型ant-cyclesystem、ant-densitysystem以及ant-quantitysystem在ant-cyclesystem模型中：∆τijk=在ant-densitysystem模型中：∆τijk=在ant-quantitysystem模型中：∆τijk=上面公式中,Q为一正常数,表示蚂蚁循环一周或者一个过程在经过的路径上所释放的信息素总量。Lk表示第k只蚂蚁在本次循环中所经过的路径的长度。以上三种模型的区别在于:第一种模型利用的是蚁群的整体信息,即走完一个循环以后才进行残留信息量的全局调整;而后两种模型中蚂蚁每走一步(即从时间t到t+1)都要更新残留的信息量,而不是等到所有的蚂蚁完成对所有的城市访问以后。4.3蚂蚁系统模型的实现从上面的蚂蚁系统模型来看,其寻找最优解的过程实际上是一个有限的递推过程,因而也适合在计算机上实现。AS算法的实现可用以下的伪代码来描述:算法2：AS算法1.初始化设t=0；{t为计时器}Nc=0；{Nc为迭代次数计算器}τij（t）=C；{τij（t）为每条路径（i，j）设的信息素量的初值Δτij=0；{信息素增量的初值设为0}ηij由某种启发式算法确定；{在TSP中，ηij=1/dij}tabuk=Φ;{在初始阶段，禁忌表为空}将m只蚂蚁随机地置于n个节点上；设置s=1；{s为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中}fork=1tondofork=1tobi（t）dotabuk（s）=i；2.重复直至禁忌表满为止{这一步要重复（n-1）次}设置s=s+1；fori=1tondofork=1tobi（t）do以概率Pijkt将蚂蚁k移动到城市j；将刚刚选择到的城市j加入到禁忌表中在ant-cyclesystem模型中：按照（4.4）式计算∆在ant-densitysystem模型中：按照（4.5）式计算∆在ant-quantitysystem模型中：按照（4.6）式计算∆3.记录到目前为止的最短路径ifNc<Ncmax则清