《蚂蚁算法》PPT课件.ppt

《《蚂蚁算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《蚂蚁算法》PPT课件.ppt（47页珍藏版）》请在三一办公上搜索。

1、蚂蚁算法Ant Colony Optimization,丁建立中国民航大学计算机学院,蚂蚁算法,蚂蚁算法的原理、特点蚂蚁算法的模型蚂蚁算法的研究进展蚂蚁算法求解TSP问题,蚂蚁的生物特征,用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的某些显著特征:（1）察觉小范围区域内状况并判断出是否有食物 或其他同类的信息素轨迹；（2）释放自己的信息素；（3）所遗留的信息素数量会随时间而逐步减少。,图2-1 蚂蚁从蚁穴（Nest）移至食物源(Food),图2-2 在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程,蚂蚁算法的原理,蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌

2、物信息素(随着时间的推移该物质会逐渐挥发),后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制,通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。,蚂蚁算法的特点,（1）其原理是一种正反馈机制或称增强型学习系统；它通过信息素的不断更新达到最终收敛于最优路

3、径上；（2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；（3）它是一种分布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机；（4）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（5）它是一种启发式算法；计算复杂性为，其中NC 是迭代次数，m 是蚂蚁数目，n 是目的节点数目。,蚂蚁算法符号的定义,蚂蚁算法（Ant Algorithm,AA）或统称蚁群优化（Ant Colony Optimization,ACO）一些符号的含义：m 蚂蚁个数;n 结点（顶点）个数;边弧 的能见度（visibility

4、）,或称局部启发因子，一般取，表示路径 之间的长度;边弧 的信息素轨迹强度（intensity）;蚂蚁k 于弧上 留下的单位长度轨迹信息素数量;蚂蚁k 在结点的转移概率，j 是尚未访问结点;信息素轨迹的相对重要性（）;边弧能见度的相对重要性（）;,蚂蚁算法符号的定义,信息素轨迹的持久性（），可理解为轨迹衰减度（evaporation）；体现蚂蚁所留轨迹数量的一个常数；可行结点集合；为第k 只蚂蚁在第结点i 出发下一步的可行结点集；一个列表，用于记录第k只蚂蚁到目前为止已经访问的城市。,蚂蚁算法求解的一般步骤,第1步：初始化，NC=0,将m只蚂蚁置于n个顶点上；第2步：将各蚂蚁的初始出发点置于当

5、前解集中；对每一个蚂蚁k，按概率P选择移至下一顶点j上；将顶点j置于当前解集；第3步：计算各蚂蚁的目标函数值；记录当前的最好解；第4步：按更新方程修改信息素轨迹强度；第5步：对各边弧,，NC=NC+1；第6步：若搜索次数NC预定迭代次数且无退化行为（即找到的都是相同解），则转第二步；第7步：输出目前的最好解。,AS模型（Ant System 简称AS）,蚂蚁系统（AS）是第一个蚁群优化算法（ACO），它是意大利科学家Dorigo 在1991年最先提出，并成功地用于求解著名的组合爆炸问题TSP问题，后经他本人（1992,1996,2000）及学者Colorni，Maniezzo(1997,199

6、9)等进一步研究，将其系统化。其主要参数变量表达如下：选择概率：信息素更新方程为：,按 的不同取法,可形成三种类型的蚂蚁算法模型:(1)蚂蚁密度模型（Ant Density）：(2)蚂蚁数量模型（Ant Quantity）：(3)蚂蚁圈模型（Ant Cycle）：其中:可行结点集合，具体应用中经常用 表示，为第k只蚂蚁在第i 结点出发下一步的可行结点集（TSP问题应去掉第k只蚂蚁已经过的结点），为第k只蚂蚁在本次循环中所走的路径的长度。上述三种模型中，蚂蚁密度模型和蚂蚁数量模型利用的是局部信息，而蚂蚁圈模型利用的是全局信息，对全局优化较好。,ACS（Ant Colony System）模型,D

7、origo与Gambardella等学者在1997年在Ant-Q算法的基础上进行修改，为了平衡寻找更好结果和寻找更大的搜索空间，Pseudo-Random-Proportional rule下状态转移如下：V按照下面概率选择 这里是将Ant-Q模型中，更重要地是给出了局部在线和全局离线的两种信息素轨迹更新方式：,Local Updating(online updating):Global Updating(offline updating):这里的 可以是，0。仅对最短路径的信息素增加量。局部更新用于每一时刻每一蚂蚁的每一步移动之中，而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果

8、进行信息素轨迹更新。,MMAS(Max-Min Ant System)模型,为避免停滞和陷入局部，Stutzle和Hoos 提出了MAX-MIN Ant System（简称MMAS）模型，它对AS进行了三点改进:(1)为了更加充分地寻优，各路径信息素初值设为最大值；(2)一圈中只有最短路径的蚂蚁才进行信息素修改增加，这与AS蚂蚁圈模型调整方法相似；(3)为了避免算法过早收敛非全局最优解，将各路经的信息素浓度限制在于 之间，即。超出这个范围的值被强制设为 或者。从实验结果看，MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进。,几种模型的评价,随着蚂蚁算法发展，蚂蚁算法的模型越来越

9、丰富，人们针对不同的问题设计不同的参数，如求解TSP问题时,表示两个城市之间的距离；在求解QAP问题时，表示流程与距离的关系；在求解SMTT时，是可以得到的启发数据。如 等参数的选择也要根据不同问题做出不同选择。同时，基于问题进行轨迹更新方程的修改及概率选择的定义也是必要的。在蚂蚁算法的几种模型中，AS,ACS,MMAS三种具有重要的作用。,AS(Ant System)模型的优点,AS(Ant System)是最早的伴随蚁群这个概念提出来的算法，它首先被成功地运用于TSP问题。虽然与目前已经发展完备的一些算法(如GA等)比较起来，基本蚁群算法计算量比较大，而且效果也并不一定更好，但是它的成功运

10、用激起了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。AS的优点在于:（1）正反馈，从而能迅速找到好的解决方法；（2）分布式计算可以避免过早地收敛；（3）强启发能在早期的寻优中迅速找到合适的解决方案。（4）AS算法被成功地运用于许多能被表达为在图表上寻找最佳路径的问题。,ACS与AS的主要区别,（1）ACS算法中，蚂蚁在寻找最佳路径的过程中使用局部信息，即采用局部信息对信息素浓度进行调整；（2）在所有进行寻优的蚂蚁结束路径寻找后，信息素的浓度会再一次调整，这次采用的是全局信息，而且只对过程中发现的最好路径上的信息素浓度进行加强；（3）有一个状态传递机制，用于指导蚂蚁最初的寻

11、优过程，并通过信息素的积累反映问题的目前状态。,MMAS模型特点,MMAS(MAX-MIN Ant System)是到目前为止解决TSP，QAP等问题最好的ACO类算法。和其他寻优算法比较起来，它仍然属于最好的解决方案之一。其特点在于:（1）只对最佳路径增加信息素的浓度，从而更好地利用了历史信息(这与ACS算法的调整方案有点类似)；（2）为了避免算法过早收敛于并非全局最优的解，将各条路径可能的信息素浓度限制于，超出这个范围的值被强制设为 或者是，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；（3）将各条路径上信息素的起始浓度设为，这样便

12、可以更加充分地进行寻优。,表2 蚂蚁算法及其应用,表2 蚂蚁算法及其应用（续）,蚂蚁算法可研究问题,蚂蚁算法的研究与发展历史毕竟较短，还存在诸多问题：（1）它的发展远没有形成完整的理论体系；（2）模型对问题具有依赖性，研究者必须根据问题的特点选择和修正模型；（3）算法的参数选择更多的是依靠实验和经验，没有定理或公认的确定方法；（4）由于初始信息素匮乏，计算时间偏长，对实时应用不利。这些都表明其理论和实践方面有许多问题尚需更深入的研究。,举例1：遗传算法与蚂蚁算法的融合,遗传算法具有快速随机的全局搜索能力，但不能很好地利用系统的反馈信息,当求解到一定范围时往往作大量无为的冗余迭代，求精确解效率低

13、。蚂蚁系统是一种并行的分布式正反馈系统，它是通过信息素的累积和更新收敛于最优路径上，但初期信息素匮乏，初始求解速度慢。遗传算法与蚂蚁算法的融合模型，采用遗传算法生成初始信息素分布，利用蚂蚁算法反复迭代求精确解，以期达到优势互补。,遗传算法的基本原理,图3-1 简单遗传算法进化过程示例,种群#位串 适应值 排序1011011011 38.3 31100011100 43.7 20111010101 54.5 10110010010 34.6 4,交叉位11000111000111010101,变异位11000101010111011100,新后代11000101010111001100,选择,交

14、叉,变异,新后代,遗传算法的特点,遗传算法具有进化计算的所有特征，其优点是：（1）具有大范围全局搜索的能力，与问题领域无关；（2）搜索从群体出发，具有潜在的并行性；（3）可进行多值比较，鲁棒性强；（4）搜索使用评价函数启发，过程简单；（5）使用概率机制进行迭代，具有随机性；（6）具有可扩展性，容易与其它算法结合。但遗传算法在编码表示、适应度函数、选择策略、控制参数等方面还存在诸多问题。特别是，对于系统中的反馈信息利用不够，当求解到一定范围时往往作大量无为的冗余迭代，求精确解效率低。,遗传算法与蚂蚁算法的融合思想,遗传算法与蚂蚁算法的融合（Genetic AlgorithmAnt Algorit

15、hm 简称GAAA）,其基本思想是汲取两种算法的优点，克服各自的缺陷，优势互补。在时间效率上优于蚂蚁算法，在求精解效率上优于遗传算法，是时间效率和求解效率都比较好的一种新的启发式方法。其基本思路是算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布。算法后过程采用蚂蚁算法，在有一定初始信息素分布的情况下，充分利用蚂蚁算法并行性、正反馈性、求精解效率高等特点。,GAAA算法总体框架与流程,图3-2 GAAA算法总体框架,定义目标函数 生成若干组优化解 定义适应值函数 转化为初始信息素分布,问题,遗传 算法,蚂蚁 算法,最好解,图3-3 GAA

16、A算法详细流图,GAAA中遗传算法的模型选择定义,GAAA中的遗传算法是基于优胜选择遗传算法的原理与定义。编码与适应值函数：如TSP问题，以城市的遍历次序作为遗传算法的编码，适应度函数取为哈密顿圈的长度的倒数。种群生成与染色体选择：利用随机函数生成一定数量的十进制实数编码种群，根据适应值函数选择准备进行交配的一对染色体父串。交叉算子：采用Davis提出的顺序交叉方法。变异算子：采用逆转变异方法。,交叉算子：采用Davis提出的顺序交叉方法，先进行常规的双点交叉，在进行维持原有相对访问顺序的巡回路线修改。具体交叉如下：（1）随机在父串上选择一个交配区域，如两父串选定为：old1=1 2|3 4

17、5 6|7 8 9,old2=9 8|7 6 5 4|3 2 1（2）将old2的交配区域加到old1前面，将old1的交配区域加到old2的前面：old1=7 6 5 4|1 2 3 4 5 6 7 8 9,old2=3 4 5 6|9 8 7 6 5 4 3 2 1（3）依次删除old1，old2中与交配区相同的数码，得到最终的两子串：new1=7 6 5 4 1 2 3 8 9,new2=3 4 5 6 9 8 7 2 1变异算子：采用逆转变异方法，所谓“逆转”，如染色体(123456)在区间23和区间56处发生断裂，断裂片段又以反向顺序插入，于是逆转后的染色体变为(125436)。这里

18、的“进化”，是指逆转算子的单方向性，只有经逆转后，适应值有提高的才接受下来，否则逆转无效。,GAAA中蚂蚁算法模型选择,GAAA中蚂蚁算法选择基于蚂蚁圈模型（Ant-Cycle）和MMAS(MAX-MIN Ant System)算法，在吸取其各自优点的基础上并进行改进，具体来说：信息素更新方程：选择概率：每一蚂蚁圈信息素增加：各路径设置信息素初值。,GAAA中遗传算法与蚂蚁算法对接,两种算法对接的关键是如何把遗传算法的结果转化为蚂蚁算法的信息素。信息素的初值设置：MMAS是把各路径信息素初值设为最大值max，这里我们通过遗传算法得到了一定的路径信息素，所以把信息素的初值设置为:S=C+G 这里

19、，C是一个根据具体求解问题规模给定的一个信息素常数，相当于MMAS算法中的min，G是遗传算法求解结果转换的信息素值。信息素更新模型：采用蚂蚁圈模型进行信息素更新，即一圈中只有最短路径的蚂蚁才进行信息素修改增加。,仿真实验分析,我们采用GAAA算法分别对典型的NP-hard问题30城市TSP问题和中国CHN144城市问题进行了实验,GAAA中遗传算法迭代次数分别选定为30代和144代，蚂蚁算法中各路径信息素初值C分别设为60和600,遗传算法求解结果转换的信息素值是经过路径加2和20,轨迹更新分别取=0.8，Q=1000和=0.9，Q=100000。表3-1、表3-2、表3-3、表3-4、图3

20、-4、图3-5、图3-6、图3-7、图3-8、图3-9、图3-10、图3-11、图3-12、图3-13是仿真实验结果。,表3-1 GAAA算法优化解数据逼近过程,表3-2 GAAA算法随机求解的30个 优化解值分布,图3-4 GAAA算法一次随机遗传变异后产生的信息素分布(TSP30),图3-5 GAAA算法找到的最优路径（TSP30,d=423.74）,图3-6 GAAA算法一次随机迭代求得最好结果（TSP30,d=424.46）,图3-7 GAAA算法一次随机迭代求得最好结果（TSP30,d=424.67）,图3-8 GAAA算法一次随机迭代求得最好结果（TSP30,d=424.69）,图

21、3-9 GAAA算法一次随机迭代求得最好结果（TSP30,d=424.90）,图3-10 GAAA算法找到的最优路径(CHN144,d=30351),图3-11 GAAA算法一次随机迭代求得最好结果(CHN144,d=30354),表3-3:GAAA算法的实验结果 表3-4:基本蚂蚁算法的实验结果,图3-12 GAAA一次随机求解过程（TSP30）,图3-13 GAAA一次随机求解过程（CHN144）,算法及实例仿真结论：,（1）算法无论是优化性能还是时间性能，都取得了非常好的效果；（2）算法由于在遗传算法中使用随机生成种群，不仅加快了蚂蚁算法的速度而且避免求精确解阶段陷入局部最优；（3）遗传算法与蚂蚁算法的融合，对于蚂蚁算法中的参数调整大大减低，减少了大量盲目的试验次数；（4）算法对TSP问题进行了仿真应用，对于其它NP问题同样具有借鉴作用。,