蚂蚁算法2015ppt课件

《蚂蚁算法2015ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制,通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。蚂蚁算法符号的定义——信息素轨迹的持久性（），可理解为轨迹衰减度（evaporation）；——体现蚂蚁所留轨迹数量的一个常数；——可行结点集合；——为第

3、k只蚂蚁在第结点i出发下一步的可行结点集；——一个列表，用于记录第k只蚂蚁到目前为止已经访问的城市。蚂蚁算法求解的一般步骤第1步：初始化，NC=0,将m只蚂蚁置于n个顶点上；第2步：将各蚂蚁的初始出发点置于当前解集中；对每一个蚂蚁k，按概率P选择移至下一顶点j上；将顶点j置于当前解集；第3步：计算各蚂蚁的目标函数值；记录当前的最好解；第4步：按更新方程修改信息素轨迹强度；第5步：对各边弧,，NC=NC+1；第6步：若搜索次数NC<预定迭代次数且无退化行为（即找到的都是相同解），则转第二步；第7步：输出目前的最好解。AS模型（AntSystem简称AS）蚂蚁系统（AS）是第一个蚁群优化算法（A

4、CO），它是意大利科学家Dorigo在1991年最先提出，并成功地用于求解著名的组合爆炸问题TSP问题，后经他本人（1992,1996,2000）及学者Colorni，Maniezzo(1997,1999)等进一步研究，将其系统化。其主要参数变量表达如下：选择概率：信息素更新方程为：按的不同取法,可形成三种类型的蚂蚁算法模型:(1)蚂蚁密度模型（AntDensity）：(2)蚂蚁数量模型（AntQuantity）：(3)蚂蚁圈模型（AntCycle）：其中:可行结点集合，具体应用中经常用表示，为第k只蚂蚁在第i结点出发下一步的可行结点集（TSP问题应去掉第k只蚂蚁已经过的结点），为第k只蚂蚁

5、在本次循环中所走的路径的长度。上述三种模型中，蚂蚁密度模型和蚂蚁数量模型利用的是局部信息，而蚂蚁圈模型利用的是全局信息，对全局优化较好。Ant-Q模型Gambardella与Dorigo等学者在1995年、1996年运用Q-leaning思想对AS算法进行了修改，其状态转移的规则如下：这里是均匀分布于[0,1]区间的一个随机变量，是个参数。V是按照下列三种规则决定的一个随机变量：(1)Pseudo-Random规则：V按照均匀分布选择。（2）Pseudo-Random-Proportional规则：V按照下面概率选择（3）Random-Proportional规则：设置为0,基于概率分布进行

6、所有的决策。信息素轨迹更新方程为：这里，在初始化或求解最好结果路径上信息素增量，下一状态增加信息素相对最大值的比例是。ACS（AntColonySystem）模型Dorigo与Gambardella等学者在1997年在Ant-Q算法的基础上进行修改，为了平衡寻找更好结果和寻找更大的搜索空间，Pseudo-Random-Proportionalrule下状态转移如下：V按照下面概率选择这里是将Ant-Q模型中，更重要地是给出了局部在线和全局离线的两种信息素轨迹更新方式：LocalUpdating(onlineupdating):GlobalUpdating(offlineupdating):这

7、里的可以是，，0。仅对最短路径的信息素增加量。局部更新用于每一时刻每一蚂蚁的每一步移动之中，而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果进行信息素轨迹更新。MMAS(Max-MinAntSystem)模型为避免停滞和陷入局部，Stutzle和Hoos提出了MAX-MINAntSystem（简称MMAS）模型，它对AS进行了三点改进:(1)为了更加充分地寻优，各路径信息素初值设为最大值；(2)一