蚁群算法

蚁群算法提纲9.1概述9.2基本原理9.3蚂蚁系统9.4蚁群算法的参数分析9.5改进——蚁群系统9.6特点及应用9.1算法概述蚁群算法：通过人工模拟蚂蚁觅食过程，即个体之间的信息交流和协作最终找到从蚁穴到食物源的最短路径。应用：智能搜索，全局优化特点：鲁棒性，正反馈，分布式计算，易于和其他算法结合蚂蚁搜寻食物具体过程：在蚁群总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。之后蚂蚁选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。9.2基本原理蚁群的自组织行为“双桥实验”开始时，无信息素分布，蚂蚁以等概率进行路径选择。引入随机干扰后，一条路径上的蚂蚁开始增多，使得该路径上的信息素增多，从而引导更多的蚂蚁选择这条路径。最后的结果是：到达极限，所有的蚂蚁都从左边较短的路径寻找食物（正反馈过程）。实现了由随机选择到自适应选择的优化行为过程。改进的蚁群算法的基本思想用引入信息素的正反馈为基础，通过对较好的潜在解的增强，来实现对最优解的搜索。引入信息素的挥发机制(负反馈)，为了避免正反馈中的早熟现象。也就避免了搜索陷入局部最优。9.3蚂蚁系统蚂蚁系统是最早提出群算法，是对真实蚁群协作过程的模拟，后来发展的算法其核心思想都是基于蚂蚁系统。蚂蚁系统旨在寻求一条连接两点或多点的单向闭合路径的优化问题，即TSP问题。TSP问题（旅行商问题）就是求一条遍历所有n个城市并且每个城市仅经过一次的最短路径。蚂蚁觅食和优化问题对照优化问题蚂蚁觅食各个状态要遍历的各个路径解蚂蚁经过的一条完整路径最优解最短路径各状态的吸引度信息素的浓度状态更新信息素更新目标函数路径长度蚂蚁系统的模型与实现解决TSP问题在算法的初始时刻，将m只蚂蚁随机放到n座城市，然后蚂蚁同时由一个城市到另一个城市，逐步完成搜索过程。整个算法的迭代过程以N为刻度，1=N=Nmax(Nmax为最大迭代次数)。在每次迭代中，以t为刻度，0=t=n,蚂蚁k（k=1,2,3，…，m）根据概率转换规则选择下一个城市，由此可以生成一个由n个城市组成的行动路线，并伴有信息素的更新。影响蚂蚁转移到下一城市的因素1禁忌列表（tube）禁忌表是为了避免蚂蚁重复走进同一个城市的一个数据结构。设tubek为蚂蚁k的禁忌表，则蚂蚁k在经过城市i以后，就将该城市加入到自己的禁忌表tubek中，表示下一次不能再选择城市i。用tubek(s)示禁忌表中第s个元素，也即蚂蚁所走过的第s个城市；完成一次周游后，即遍历n个城市后，清空禁忌表。2能见度定义为距离的倒数。η=1/d。两个城市的距离越近，能见度越高，被选择的愿望越大，由此引导蚂蚁的搜索。这种信息是固定不变的，称为启发信息。3信息素当蚂蚁由城市i选择城市j后算法将在ij路径上遗留信息素，是一种动态的全局信息，代表了由城市i到j的获知性愿望。反映了蚂蚁在解决问题过程中的经验积累和向其他蚂蚁学习的能力。信息素有增加和减少两方面。挥发机制是为了避免残留信息素过多导致残留信息淹没启发信息。下面是信息素更新公式：4概率转换规则每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：在时刻t，蚂蚁k从城市i转移到城市j的概率为ijijkkkkiJsisisijijkijdtabuniJiJjiJjtttttpk/1,,,2,1)()(,0)(,)]([)]([)]([)]([)()(下一步允许的城市的集合α、β分别表示信息素和启发式因子的相对重要程度。上述四个因素控制着蚂蚁系统实现路径选择和信息素更新策略，两者相互配合，实现模型的正负反馈机制，促使人工蚂蚁收敛于最优解。针对信息素更新策略又出现了三种模型：蚁量模型，蚁密模型，蚁周模型。蚁量模型蚁密模型蚁周模型在该模型中全局信息更新，较之前两种方法性能更优。原因是在蚁周模型中用到了全局信息，即蚂蚁释放在路径上的信息素量与其所得解的质量成正比。周游长度越短的蚂蚁，释放在其经过的路径上的信息素量就越多，而前两种模型在搜索解时，只使用了局部信息，没有用到任何解的信息。AS算法下面以蚁周模型为例，总结蚂蚁系统算法的流程。初始化：t=0;NC=0;τij(t)=C;Δτij(t)=0;将m只蚂蚁放到n座城市上禁忌表已满？s=s+1将m只蚂蚁按照其各自计算的转移概率pijk选择下一城市，并将该城市加入到禁忌表中。计算所有m只蚂蚁走过的周游长度Lk；更新当前的最优路径。计算Δτijk，更新信息素；t=t+n；NC=NC+1终止条件满足否？清空所有禁忌表置禁忌表索引s=1;并将其起点城市加入各自禁忌表中输出最优结果YNYNAS算法可以表述如下：在算法的初始时刻，将m只蚂蚁随机地放到n座城市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此时各路径上的信息素量相等，设τij(0)=C（C为一较小的常数）。接下来，每只蚂蚁根据路径上残留的信息素量和启发式信息（两城市间的距离）独立地选择下一座城市。在时刻t，蚂蚁k从城市i转移到城市j的概率pijk(t)为：9.4蚁群算法的参数分析讨论的参数包括：α——信息素的相对重要程度；β——启发式因子的相对重要程度；ρ——信息素蒸发系数（(1-ρ)表示信息素的持久性系数）；Q——蚂蚁释放的信息素量。在蚂蚁搜索解的过程中，所有蚂蚁都选择同样的路径，即系统不再搜索较好的解，称为停滞现象。当参数设置为某些值时，算法迭代到一定代数后将出现停滞现象。其原因是因为较好路径上的信息素远大于其它边上的，从而使所有蚂蚁都选择相同的路径。α=0时，信息素就不起作用，相当于没有了反馈信息，实验结果表明这时算法效果不如有反馈信息时的结果。（P258）1、参数α、β对AS算法性能的影响信息素启发因子α的取值：当α取较大的值时，意味着在选择路径时，路径上的信息素非常重要；当α取较小的值时，蚁周算法变成随机的贪婪算法。自启发量因子β的取值：β过小，将导致蚂蚁群体陷入随机搜索，在此种情况下很难找到最优解，而且收敛较慢。β过大，算法会很快找到一个最优解，但是容易陷入局部最优。反馈信息的作用：使得算法在寻优过程中产生一个选择压力，促使算法较快地趋向于一组较优的解。蚁周模型中不同的参数（α、β）组合对算法的影响●-算法能发现已知的最好解，且不出现停滞现象；∞-算法不能发现最好解，且不出现停滞现象；Φ-算法不能发现最好解，且出现停滞现象。2信息挥发系数ρ的影响在蚁群算法中，蚂蚁具有记忆功能，这种功能由ρ体现出来，1-ρ为信息素的残留系数。ρ增大，残留信息减少，负反馈增强，随机性增强，利于发现更多最优解，但收敛速度降低。ρ减小，残留信息增多，正反馈增强，随机性减弱，容易陷入一个范围狭小的搜索空间。虽然收敛速度加快，但搜索质量不高。为了测试蚂蚁数m对蚁周模型性能的影响，用该模型来求解4×4方格问题。众所周知，当方格的边长为10时，其最优解为160。在该实验中，分别取蚂蚁数为m∈{4,8,16,32,64}。3蚂蚁数m对AS算法的影响4×4方格问题的一个可选解下图为实验所得的结果，从图中可以看出当M≈N时，蚁周模型可以在最少的迭代次数内找到最优解。在对随机分布的16城市的实验中也能得到同样的结果。在求解4×4网格问题时，每只蚂蚁找到最优解的周游次数与蚂蚁总数之间的关系，5次运行的平均结果。蚂蚁数目m：m较小时，会使未走过的路径上的信息素减小到接近0，即搜索的随机性减弱，虽然收敛速度加快，但算法的全局性能降低，算法稳定性差，容易过早停滞。m过大，会使曾被搜索过的路径上的信息素过于平均，收敛速度减慢。4总信息量Q的分析总信息量Q为蚂蚁遍历一次所释放的信息素总量，在算法中为常量。Q越大，信息素积累越多，收敛速度越快。选参原则：（三步走）1确定蚂蚁数目，可参照“问题规模约为蚂蚁数目的1.5倍”；2参数粗调α、β，常用的几种组合（α=1，β=1），（α=1，β=2），（α=1，β=5），（α=0.5，β=5）；3参数细调ρ，ρ通常设定在0.5以下。9.5蚁群系统蚁群系统（ACS）是AS算法的改进版本，与AS算法主要区别在于：（i）在选择下一座城市时，ACS算法更多地利用了当前的较好解；（ii）只在全局最优解所属的边上增加信息素；（iii）每次当蚂蚁从城市i转移城市j时，边ij上的信息素将会适当的减少。转换规则：在ACS算法中，蚂蚁使用伪随机比率选择规则选择下一座城市。即对位于城市i的蚂蚁k，以概率q0移动到城市l，其中l为使τil(t)*[ηilβ]达到最大的城市。该选择方式意味着蚂蚁将以概率q0将最大可能的城市选入蚂蚁所构造的解；除此之外，蚂蚁以(1-q0)的概率按下式选择下一座城市j。在ACS算法中，蚂蚁的状态转移公式为：其中q0∈(0,1)为常数，q∈(0,1)为随机数，τiu(t)表示t时刻城市i与城市u之间的信息素，ηiu表示城市i与城市u之间的启发式因子，β表示启发式因子的相对强弱。在选择下一座城市之前随机生成q，如果q的值小于等于常数q0，则从城市i到所有可行的城市中找出[τiu(t)][ηiuβ]最大的城市，即为下一个要选择的城市；如果随机数q大于q0，则按下式来选择下一座城市。其中Jk(i)为蚂蚁k当前的可行城市集合。局部信息素更新局部信息素更新的作用是使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有被选中的边有更强的探索能力。在ACS算法中，当蚂蚁从城市i转移到城市j后，边ij上的信息素量按下式进行更新：其中τ0为常数，ξ∈(0,1)为可调参数。全局信息素更新针对全局最优解所属的边按下式进行更新：其中Lgb为当前最好解的长度，ρ为信息素蒸发系数。将ACS算法与AS算法，模拟退火（SA），进化规划（EP），遗传算法（GA），模拟-遗传（遗传算法与模拟退火算法的组合，简称AG）进行了比较，发现ACS算法在大多数情况下要优于其它算法，至少性能相当。在解决非对称TSP问题是，ACS算法更具优势。下表为对比实验结果（表中显示了问题的整数解、小数解（在圆括号中）和发现最优整数解所需的迭代次数，问题的最优解用黑体加粗显示）。ACS与GA，EP，SA，AG的对比