访问的城市 。
101 Q U k i N )(ktabu l第第1步：步：初始化 ， NC=0, 将m只蚂蚁置于n个顶点上； l第第2步：步：将各蚂蚁的初始出发点置于当前解集中；对每一个蚂 蚁k ， 按概率P选择移至下一顶点j上；将顶点j置于当前解集； l第第3步：步：计算各蚂蚁的目标函数值；记录当前的最好解； l第第4步：步：按更新方程修改信息素轨迹强度； l第第5步：步：对各边弧 ,， NC=NC+1； l第第6步：步：若搜索次数NC预定迭代次数且无退化行为（即找到 的都是相同解） ， 则转第二步； l第第7步：步：输出目前的最好解 。
),(ji 。

8、0 ij l蚂蚁系统（AS）是第一个蚁群优化算法（ACO） ， 它是意大 利科学家Dorigo 在1991年最先提出 ， 并成功地用于求解著名 的组合爆炸问题TSP问题 ， 后经他本人（1992,1996,2000）及 学者Colorni ， Maniezzo(1997,1999)等进一步研究 ， 将其系统 化 。
其主要参数变量表达如下： l选择概率： l信息素更新方程为： other Uj t t tp Ul ilil ijij k ij 0 )( )( )( m k k ijijij ttt 1 )()() 1( l按 的不同取法,可形成三种类型的蚂蚁算法模型: l(1) 蚂蚁密度模型（Ant Density） 。

9、： l(2) 蚂蚁数量模型（Ant Quantity）： l(3) 蚂蚁圈模型（Ant Cycle）： l其中: 可行结点集合 ， 具体应用中经常用 表示 ，为第k只蚂蚁在第i 结点出发下一步的可行结点集（TSP问 题应去掉第k只蚂蚁已经过的结点） ，为第k只蚂蚁在本 次循环中所走的路径的长度 。
l上述三种模型中 ， 蚂蚁密度模型和蚂蚁数量模型利用的是 局部信息 ， 而蚂蚁圈模型利用的是全局信息 ， 对全局优化 较好 。
k ij kk ij LQ ij k ij dQ Q k ij U k i N k i N k L lDorigo与与Gambardella等学者在1997年在Ant-Q算法的基础上 进行修改 。

10、 ， 为了平衡寻找更好结果和寻找更大的搜索空间 ，Pseudo-Random-Proportional rule下状态转移如下： lV按照下面概率选择 l这里是将Ant-Q模型中 ，更重要地是给出了局部在线和全 局离线的两种信息素轨迹更新方式： 0 0 )()(arg max qqV qq v ilil Nl k i k i Nl ilil ijij k ij p )()( )()( 1 lLocal Updating(online updating): lGlobal Updating(offline updating): l 这里的 可以是，， 0。
仅对最短路径的 信息素增加量 。
l局部 。

11、更新用于每一时刻每一蚂蚁的每一步移动之中 ， 而全局 更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结 果进行信息素轨迹更新 。
ijijij tt)1 ()() 1( e ijijij tt)1 ()() 1( j max e ij 0 ij l为避免停滞和陷入局部 ， Stutzle和Hoos 提出了MAX-MIN Ant System（简称MMAS）模型 ， 它对AS进行了三点改进: l(1)为了更加充分地寻优 ， 各路径信息素初值设为最大值 ； l(2)一圈中只有最短路径的蚂蚁才进行信息素修改增加 ， 这与AS 蚂蚁圈模型调整方法相似； l(3)为了避免算法过早收敛非全局最优解 ， 将各路经的信息素浓度 限 。

12、制在于 之间 ， 即。
超出这个范围的值 被强制设为 或者。
l从实验结果看 ， MMAS算法在防止算法过早停滞及有效性方面对 AS算法有较大的改进 。
max e ijijij tt)() 1( , maxmin maxmin ij max min l随着蚂蚁算法发展 ， 蚂蚁算法的模型越来越丰富 ， 人们针对 不同的问题设计不同的参数 ， 如求解TSP问题时, , 表示两个城市之间的距离；在求解QAP问题时 ，表示流程与距离的关系；在求解SMTT时 ，是可以得到的启发数据 。
如 等参数的选择也 要根据不同问题做出不同选择 。
同时 ， 基于问题进行轨迹更 新方程的修改及概率选择的定义也是必要的 。
l在蚂蚁算法的几种模型 。

13、中 ， 在蚂蚁算法的几种模型中 ， AS, ACS, MMAS三种具有重要三种具有重要 的作用的作用 。
ijij d1 ij dijij s1 jiij dfs ijij MDD1 ij MDD,Q lAS (Ant System) 是最早的伴随蚁群这个概念提出来的算法 ，它首先被成功地运用于TSP问题 。
虽然与目前已经发展完备的 一些算法(如GA等)比较起来 ， 基本蚁群算法计算量比较大 ， 而 且效果也并不一定更好 ， 但是它的成功运用激起了人们对蚁群 算法的极大兴趣 ， 并吸引了一批研究人员从事蚁群算法的研究 。
AS的优点在于: l（1）正反馈 ， 从而能迅速找到好的解决方法； l（2）分布式计算可以避免过早地收敛； 。

14、 l（3）强启发能在早期的寻优中迅速找到合适的解决方案 。
l（4）AS算法被成功地运用于许多能被表达为在图表上寻找最 佳路径的问题 。
l（1）ACS算法中 ， 蚂蚁在寻找最佳路径的过程中使用局部 信息 ， 即采用局部信息对信息素浓度进行调整； l（2）在所有进行寻优的蚂蚁结束路径寻找后 ， 信息素的浓 度会再一次调整 ， 这次采用的是全局信息 ， 而且只对过程中 发现的最好路径上的信息素浓度进行加强； l（3）有一个状态传递机制 ， 用于指导蚂蚁最初的寻优过程 ，并通过信息素的积累反映问题的目前状态 。

稿源：(未知)

【傻大方】网址：/a/2021/0819/0023818768.html

标题：蚂蚁|蚂蚁算法2010( 二 )