ch2智能理论--蚁群算法

蚁群优化算法起源20世纪90年代，意大利学者Dorigo等人从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出一种新型的模拟进化算法——蚁群算法，它是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题取得了较好的试验结果。虽然研究时间不长，但是目前的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法。蚁群优化算法应用领域蚁群算法能够用于解决大多数优化问题或者能够被转化为优化求解的问题。目前，其应用领域已扩展到─多目标优化─数据分类─数据聚类─模式识别─生物系统建模─流程规划─信号处理─机器人控制─决策支持─仿真和系统辩识蚁群优化算法研究背景群智能理论研究领域有两种主要的算法：─蚁群算法(AntColonyOptimization,ACO)对蚂蚁群落食物采集过程的模拟已成功应用于许多离散优化问题。─微粒群算法(ParticleSwarmOptimization,PSO)起源于对简单社会系统的模拟。最初模拟鸟群觅食的过程，后来发现它是一种很好的优化工具。蚁群优化算法研究背景群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但与梯度法及传统的演化算法相比，主要优点为：─无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性─以非直接的信息交流方式确保了系统的扩展性─并行分布式算法模型，可充分利用多处理器─对问题定义的连续性无特殊要求─算法实现简单蚁群优化算法研究背景群智能方法的易于实现体现在：─算法中仅涉及各种基本的数学操作─数据处理过程对CPU和内存的要求不高─只需要目标函数的输出值，不需要它的梯度信息。蚁群优化算法研究背景已完成的群智能理论和应用方法研究证明─群智能方法能够有效解决大多数全局优化问题─群智能潜在的并行性和分布式特点为处理大量的、以数据库形式存在的数据提供了技术保证。无论从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是有重要学术意义和现实价值。蚁群优化算法研究现状从Dorigo在90年代最早提出蚁群算法—-蚂蚁系统(AntSystem,AS)，并将其应用于解决TSP问题开始，基本的蚁群算法得到了不断的发展和完善，并在其他许多实际优化问题求解中进一步得到了验证。AS改进版─共同点：增强蚂蚁搜索过程中对最优解的探索能力─差异：搜索控制策略蚁群优化算法研究现状最初提出的AS有三种版本：Ant-density、Ant-quantity、Ant-cycle前两种算法中，蚂蚁在两个位置节点间每移动一次后即更新信息素。Ant-cycle中，所有蚂蚁都完成了自己的行程后，才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。─与其它各种通用的启发式算法相比，在不大于75城市的TSP中，它们的求解能力比较理想。但是当问题规模扩展时，AS的解题能力大幅度下降。蚁群优化算法研究现状其后的ACO研究工作主要都集中在AS性能的改进方面。较早的一种改进是精英策略(ElitistStrategy)，其思想是：─在算法开始后，对所有已发现的最好路径给予额外增强，并将随后与之对应的行程记为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。─这种改进型算法能以更快的速度获得更好的解。但是若选择的精英过多，则算法会由于较早收敛于局部次优解，而导致搜索的过早停滞。蚂蚁寻食过程寻找路径时，在路径上释放出一种特殊的信息素。碰到没有走过的路口，随机挑选一条路径，并释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率相对较大。正反馈：最优路径上激素浓度越来越大，其它路径上激素浓度随时间的流逝而消减。最终整个蚁群找出最优路径。简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点。可随机选择的路线：ABD或ACD。设初始时每条路线分配一只蚂蚁，每单位时间行走一步上图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。简化的蚂蚁寻食过程本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A走ACD的蚂蚁刚好走到D点。简化的蚂蚁寻食过程设蚂蚁每经过一处所留下的信息素为一个单位。36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物。─ABD的路线往返了2趟，每一处的信息素为4个单位─ACD的路线往返了1趟，每一处的信息素为2个单位─信息素比值为2:1─按信息素指导，蚁群在ABD路线上增派一只蚂蚁(共2只)，ACD路线上仍然是一只蚂蚁。简化的蚂蚁寻食过程72个时间单位后，两条线路上的信息素单位积累为12和4，比值为3:1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁(共3只)，ACD路线上仍然是一只蚂蚁。再36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，按信息素指导，最终所有蚂蚁会放弃ACD路线，都选择ABD路线，这就是正反馈效应。自然蚁群与人工蚁群算法人工蚁群中把具有简单功能的工作单元看作蚂蚁。相似处：优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。区别：人工蚁群能记忆已访问过的节点，在选择下条路径时是按一定算法规律有意识地寻找最短路径。如，TSP问题中可预先知道当前城市到下一个目的地的距离。蚁群算法与TSP问题初始的蚁群算法是基于图的蚁群算法(graph-basedantsystem，GBAS)，2000年由Gutjahr在FutureGenerationComputingSystems提出。TSP问题表示为N个城市的有向图：G=(N,A)目标函数─w=(i1,i2,…,in)为城市1,2,…,n的一个排列─(dij)nn为城市间距离矩阵1,2,...,,,NnAijijN11llniilfwd蚁群算法与TSP问题设m只蚂蚁在图的相邻节点间移动，协作异步地得到解。蚂蚁计算出下一步所有可达节点的一步转移概率，并按此概率实现一步移动，依此往复。一步转移概率由图中每条边上的两类参数决定：信息素值、可见度(即先验值)。信息素的更新有2种方式：挥发——所有路径上信息素以一定比率减少增强——给评价值“好”(有蚂蚁走过)的边增加信息素基于图的蚁群系统(GBAS)STEP0对n个城市的TSP问题，城市间的距离矩阵为：(dij)nn给TSP图中的每一条弧(i,j)赋信息素初值：ij(0)=1/|A||A|：表示图中弧(i,j)的数目，即矩阵(dij)nn中不为零的数；设有m只蚂蚁工作，都从同一城市i0出发当前最好解是：w*=(1,2,…,n)目标函数：1,2,...,,,NnAijijN11llniilfwd基于图的蚁群系统(GBAS)STEP1(外循环)若满足算法停止规则，停止计算，输出计算得到的最好解给定外循环的最大数目，表明有足够的蚂蚁工作；当前最优解连续K次相同而停止，K是给定的整数，表示算法已收敛；给定优化问题的下界和误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。否则使蚂蚁s(1sm)从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集。基于图的蚁群系统(GBAS)STEP2(内循环)按蚂蚁1sm的顺序分别计算在城市i，若L(s)=N或{l|(i,l)A,lL(s)}=，完成蚂蚁s的计算。否则，若T={l|(i,l)A,lL(s)}-{i0}，以概率到达j，L(s)=L(s){j}，il=j若L(s)N且T=，则到达i0，L(s)=L(s){i0}，il=i0重复STEP2110ijijijlTkjTkpjT基于图的蚁群系统(GBAS)STEP3对蚂蚁1sm，若L(s)=N，按L(s)中城市的顺序计算路径长度；若L(s)N，路径长度置为无穷大(即不可达)。比较m只蚂蚁的路径长度，记走最短路径的蚂蚁为t。若f(L(t))f(w*)，则w*=L(t)修改信息素值对固定的K1，挥发因子k满足：加强w*路径上的信息素挥发其他路径上的信息素，经过k次挥发，非最优路径的信息素逐渐减少至消失。k=k+1，重复STEP111111,11,kkijijkijkijwwkkijw是上的一条弧不是上的一条弧1ln1,,ln1kkkkkKk关于信息素蚂蚁以信息素的概率分布来决定从城市i到j的转移，信息素更新过程由两部分组成─挥发——每个连接上信息素逐渐减弱的过程由(1-k-1)ij(k-1)表示，该过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。挥发过程是所有弧都进行的，与蚂蚁数量无关。─增强——观察蚁群中每只蚂蚁找到的路径，选择最优路径上的弧进行信息素增强，实现单个蚂蚁无法实现的集中行动。增强过程是蚁群优化算法中可选的部分。关于信息素信息素的更新分为离线和在线两种方式。─离线方式（同步更新方式）主要思想是在若干只蚂蚁完成n个城市的访问后，统一对残留信息进行更新处理。─在线更新（异步更新方式）蚂蚁每走一步，立即回溯并且更新行走路径上的信息素。基于图的蚁群系统(GBAS)四个城市的非对称TSP问题010.5110111.55011110ijDd基于图的蚁群系统（GBAS）设共有4只蚂蚁，都从城市A出发挥发因子初始信息素记忆矩阵为：1,1,2,32kk01121121121120112112011211201121121121120基于图的蚁群系统（GBAS）执行GBAS算法的步骤2，设蚂蚁的行走路线分别为：第一只w1：ABCDAf(w1)=4第二只w2：ACDBAf(w1)=3.5第三只w3：ADCBAf(w1)=8第四只w4：ABDCAf(w1)=4.5当前最优解为w2也是截止到当前的最优解。基于图的蚁群系统（GBAS）更新信息素矩阵─第一次外循环结束的状态11111,11,kkijijkijkijwwkkijw是上的一条弧不是上的一条弧0124161241601241241124112016124161240011211211211201121120112112011211211211201,1,2,32kk基于图的蚁群系统（GBAS）重复外循环，由于w2已经是全局最优解，因此按STEP3的信息素更新规则，无论蚂蚁如何行走，都只是对w2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵01485241480196114819652401481481148019619623148148052419619601148148524148019611481960