自适应蚁群算法及其应用

粒子群算法及其参数设置

摘要

本文对标准蚁群算法、MMAS蚁群算法、自适应蚁群算法做了较详细系统的总结，其中主要讨论了自适应蚁群算法在DNA序列比对中的应用，主要的过程是：首先，我们设一个计分函数和一个得分策略，在任意给出一对DNA序列，建立一个序列比对矩阵。现由4只蚂蚁从左上角向右下角移动，并且最终到达右下角，那么这4只蚂蚁随意走出4条路径，根据4条路径得出4对等长的比对，再依照计分函数分别计算出4条路径的比对得分，再由5.3式进一步验证4条路径的平均得分值，取其中得分最高（即最优路径）路径；进行第二次信息素增量的调整，方法是根据蚂蚁所走过的方向和该方向上得分比例计算出来的，信息素的变化量利用矩阵来存储，那么下一次蚂蚁所选的路径就要根据以前在各条路径上的信息素浓度总和的大小选择移动方向，最终经过有限次迭代，蚂蚁就会找到一条最优路径，也就是一条与原来DNA最相似的DNA链。

关键词：标准蚁群算法，MMAS算法，自适应蚁群算法，DNA序列比对

目录

1.引言 (1)

2.标准蚁群算法 (1)

2.1蚁群算法原理 (1)

2.2蚁群算法的实现 (2)

2.3 基本蚁群算法的优缺点 (4)

2.3.1 基本蚁群算法的优点 (4)

2.3.2 基本蚁群算法的缺点 (4)

3.标准蚁群算法和MMAS(Max-Min Ant System)蚁群算法 (5)

3.1 MMAS的概念 (5)

3.2 AS与MMAS的对比 (5)

3.3 MMAS和AS的区别 (6)

3.4 最好、最坏路径信息素全局更新策略 (7)

3.5 MMAS蚁群算法的特点 (7)

4.自适应蚁群算法 (7)

4.1 自适应蚁群算法的概述 (7)

4.2 自适应的信息更新策略 (8)

4.2.1 引题 (8)

4.2.2 改进的蚁群算法过程 (8)

4.2.3 自适应蚁群算法的稳定性和收敛性 (10)

5.自适应蚁群算法在DNA中的应用 (10)

5.1 序列比对 (10)

5.2 动态蚁群算法和DNA序列比对的联系 (12)

5.3 自适应调整信息素的改进算法 (18)

6.结束语 (18)

1.引言

在二十世纪九十年代初期，意大利M.Dorigo,V.Maniezzo,A.Colorni等人从蚂蚁觅食的自然现象中受到启发，经过大量的观察和实验发现,蚂蚁在觅食过程中留下了一种外激素，又叫信息激素，它是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物的时候会在经过的路上留下这种物质,以便在回巢时不至于迷路,而且方便找到回巢的最好路径。由此，M.Dorigo等人首先提出了一种新的启发式优化算法，又叫蚁群系统(Ant Colony System)，这种算法是目前国内外启发式算法中的研究热点和前沿课题，被成功地运用于旅行商问题的求解，蚁群算法在求解复杂优化问题方面具有很大的优越性和广阔的前景。但是,根据观察实验发现，蚁群中的多个蚂蚁的运动是随机的，在扩散范围较大时，在较短时间内很难找出一条较好的路径，在算法实现的过程中容易出现停滞现象和收敛速度慢现象。在这种弊端的情况下，学者们提出了一种自适应蚁群算法，通过自适应地调整运行过程中的挥发因子来改变路径中信息素浓度,从而有效地克服传统蚁群算法中容易陷入局部最优解和收敛速度慢的现象。

蚁群算法的主要特点是：正反馈、分布式计算，与某种启发式算法相结合，正反馈过程使得该方法能很快发现较好解；分布式易于并行实现，与启发式算法相结合，使得该方法易于发现较好解。初步的研究表明，蚁群算法是一种基于种群的鲁棒性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一种新思路。

2.标准蚁群算法

2.1蚁群算法原理

蚂蚁在外出觅食的过程中,不断地在经过的路径上释放信息激素以便和其他的蚂蚁进行联系，这种信息激素的浓度随着经过该路径的蚂蚁数量而增大，而蚂蚁在回巢或觅食时也会选择信息激素浓度较大的路径，这就会有更多的蚂蚁选择此路径，这就是一种正反馈现象。也就是说某一路径上经过的蚂蚁越多，则后来者选择该路径的概率就越大。

人工蚁群算法是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提的，是一种基于种群的模拟进化算法，属于随机搜索算法。由意大利学者M.Dorigo等人首先提出M.Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程(通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP。为了区别于真实蚂蚁群体系统，称这种算法为“人工蚁群算法”，蚂蚁这类群居昆虫，虽然单个蚂蚁的行为极简单。但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务，而且，蚂蚁还能够适应环境的变化，如：在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚁群是如何完成这些复杂的任务的呢?经过人们大量研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有秩序的行为，个体之间的信息交流与相互协作起着重要的作用蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质。而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动．蚁群算法往往在初期信息素匮乏，求解速度慢；而遗传算法具有快速随机的全局搜索能力，但对于系统中反馈信息的利用却无能为力。因此，人们尝试将蚁群算法与遗传算法融

合，采用遗传生成信息素分布，利用蚁群算法求精确解，从而实现优势互补。在蚁群算法中

采用逆转变异，能有效克服基本蚁群算法中计算时间较长的缺陷，在一定程度上提高算法的收敛速度。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。

2．2 蚁群算法的实现

大家都知道，蚁群算法最成功的就是运用在TSP 问题上，现在就对该问题简单的介绍一下，如何实现标准蚁群算法：

设将M 只蚂蚁放入到N 个随机选择的城市，每只蚂蚁每一步的行动是根据一定的依据选择下一个它还没有访问的城市或者一个循环，蚂蚁选择下一个城市的主要依据是：)(t ij τ（t 时刻连接城市i 和j 的路径上残留信息的浓度），由算法本身提供的信息,ij η（由城市i 转移到城市j 的起始信息），该起始信息是由要解决的问题给出的.ij ij d /1=η为城市i 到城

市j 的先验值，于是，t 时刻位于城市i 的蚂蚁k 选择城市j 为目标城市的概率是：

???????∈=∑

∈else allowed j t t t t P k allowed n in in ij ij k ij k

,0

,)()()

()(βαβ

αητητ （2.1） 假如k

i N j ∈其中

α——残留信息的相对重要程度。

β

——期望值的相对重要程度。

k

i N 所有可能的目标城市，即还没有访问的城市，为了避免对同一城市的多次访问，每制蚂蚁都保存一个列表tabu(k),用于记录到目前为止已经访问的城市。k

ij P 为时刻蚂蚁k 由i 城市到j 城市的概率。

为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每个蚂蚁完成对所有n

个城市的访问后(即一个循环)，必须对残留信息进行更新处理，对旧的信息进行削弱，同时，必须将最新的蚂蚁访问路径的信息加入,i j τ

，

∑=+=+m

k k

ij

ij ij t n t 1

)()(τρττ （2.2）

ρ为残留信息的保留部分，ρ-1为残留信息被削弱的部分，为了防止信息的无限累积，

ρ必须小于1。k

ij τ?为蚂蚁k 在时间段t 到(t+n)时间内的访问过程中。在i 到j 的路径上留

下的残留信息浓度。ant-quantity 算法对于前一种算法：

k k

ij L Q /=?τ （2.3）

如果蚂蚁k 在t 到(t+n)时间中选择了路径(i,j)。Q 为常量,k L 表示蚂蚁k 在本次循环中

所选择路径的总长度.如果没有选择该路径。则

0=?k ij τ

而后两种算法与前一种算法的区别在于，后两种算法中每走一步(即从时间t 到(t+1))都

要更新残留信息的浓度，而非等到所有蚂蚁完成对所有n 个城市的访问以后,同时2.3式的取法也有所不同，在ant density 算法中，k ij

Q τ

?

=；而在ant —quantity 算法中，ij

ij

Q

d

τ

?=

(ij

d 表示i 和j 的距离);在ant —density 算法中，从城市i 到城市j 的蚂蚁在路径上残留的信息浓度为一个与路径无关的常量Q 。而在ant ．quantity 算法中，以ij d 为城市i 到城市j 的距离，残留信息浓度为ij d Q /,即残留信息浓度会因为城市距离的减小而增大。

M.Dorigo 曾给出3种不同模型，分别称之为ant cycle system,ant quantity system ，ant density system,它们的差别在于表达式△的不同。 在ant cycle system 模型中，

??

?+=?否则素

时间段之间留下的信息到只蚂蚁在第,0

1,/t t k L Q k ij τ （2.4） 在ant density system 和ant quantity system ，ij τ?分别为：

??

?+=???

?+=?否则

素时间段之间留下的信息到只蚂蚁在第否则素

时间段之间留下的信息到只蚂蚁在第,0

1,,01,/t t k Q

t t k L Q ij k ij ττ （2.5） 其区别在于式1.5两种模型中利用的是局部信息，而式2.4利用的是整体信息，在求解TSP 问题时ant cycle system 性能较好。因而我们采用式1.4作为基本模型。基本蚁群算法中参数

ρθβα，，，，可以用实验方法确定其最优组合。停止条件可以用固定进化代数或者当进化

趋势不明显时便停止计算。由算法复杂度分析理论可知，该算法复杂度为O(3n nc ?)，其中，nc 表示循环次数。

结果ant —cycle 算法的效果最好，这是因为它用的是全局信息——k L Q /；而其余两种算法用的是局部信息——ij d Q /和Q 。这种更新方法很好地保证了残留信息不至于无限累积。

给定一个有n 个城市的TSP 问题，人工蚂蚁的数量为m ，每个人工蚂蚁的行为符合下列规律：

(1)根据路径上的信息素浓度，以相应的概率来选取下一步路径。

(2)不再选取自己本次循环已经走过的路径为下一步路径，用一个数据结构(tabu list)来控

制这一点。

(3)当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息素浓度.t 表示在搜索周期的第t 代，连接弧(i,j)上的信息素大小。

与实际蚁群不同，搜索蚁群算法具有记忆功能，每个蚂蚁个体可以记忆自己所走过的城市.随着时间的推移，以前留下的信息素逐渐消逝，用参数1-ρ表示信息消逝程度，经过n 个城市的搜索，蚂蚁完成一次循环，各路径上信息量要作调整：

)()1()()1(,,,t t t j i j i j i ?ρρ???-+=+ （2.6）

?

?

?=?其他过只蚂蚁在本次循环中经

若第,0,/)(,j i k L Q t k j i ? （2.7） 式中Q----------常数。

k L --------第k 只蚂蚁在本次循环中所走路径的长度。

及启发因子在蚂蚁选择路径中所起的不同作用。

2.3 基本蚁群算法的优缺点

2.3.1 基本蚁群算法的优点

(1)较强的鲁棒性.对该算法模型稍加修改，便可以应用于其它问题；蚂蚁算法对初始路

线要求不高，即蚂蚁算法的求解结果依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚂蚁算法的参数数目少，设置简单，易于蚂蚁算法应用到其它组合优化问题的求解。

(2)分布式计算。该算法是一种基于种群的拟生态系统算法，具有本质并行性，易于并行实现。

(3)易于与其它方法结合。该算法很容易与多种启发式算法结合，以改善算法的性能。 (4)蚁群算法是一种本质上并行的算法.每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。 2.3.2 基本蚁群算法的缺点

(1)需要较长的计算时间，容易出现停滞现象。蚂蚁中各个体的运动是随机的，虽然通过信息激素交换能够向着最优路径进化，但是当群体规模较大时，很难在较短时间内从大量杂乱无章的路径中找到一条较好的路径。这是因为在进化的初期，各个路径上的信息激素差别不大，通过信息正反馈，使得较好路径上的信息激素逐渐增大，经过较长一段时间，才能

使得较好路径上的信息激素明显高于其它路径，随着这一过程的进行，差别越来越明显，从

而最终收敛,这一过程一般需要较长的时间。

(2)所有通过路段的搜索路径对应的候选解均会对该路段带来信息素的增量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引导信息，从而造成大量的无效搜索，使系统出现停滞现象。

(3)采用了信息素均匀分配策略，即对已搜索路径中的所有路段采用同样的信息素增量，与路段的重要性无关,没有考虑当连续空间优化问题转换到有向图搜索问题时，信息素分配给可行解带来的尺度变化对于连续解空间搜索效率的影响。

众多研究已经证明蚁群算法具有很强的发现较好解的能力，这是因为该算法不仅利用了正反馈原理，在一定程度上可加快进化过程，而且是一种本质并行的算法，不同个体之间不断进行信息交流和传递,从而能够相互协作，有利于发现较好解,蚁群算法可以解释为一种特殊的强化学习(UL: reinforcement learning)算法。蚁群算法与Q-学习算法之间的联系。其中,相当于学习中的Q 值，表示学习所得到的经验。由某种启发式算法确定，如何将这两者结合起来，是提高蚁群算法效率的关键。虽然蚁群算法有许多优点，但是，这种算法也存在一些缺陷，如：与其它方法相比，该算法一般需要较长的搜索时间，蚁群算法的复杂度可以反映这一点；而且该方法容易出现停滞现象(stagnation behaviour)。即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。

3.标准蚁群算法和MMAS(Max-Min Ant System)蚁群算法

3.1 MMAS 的概念

MMAS(MMX-MIN Ant System)是到目前为止解决TSP ，QAP 等问题最好的ACO 类算法和其它寻优算法比较起来，它仍然属于最好的解决方案之一。其特点在于：只对最佳路径增加外激素的浓度，从而更好地利用了历史信息；为了避免算法过早收敛于并非全局最优的解，将各条路径可能的外激素浓度限制于：[m in τ,m ax τ]，超出这个范围的值被强制设为m ax τ或者是m in τ可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散；将各条路径上外激素的起始浓度设为m ax τ，这样便可以更加充分地进行寻优。

3.2 AS 与MMAS 的对比

蚁群算法(AS)是由M.Dorigo 和Gambardela 提出一种新的启发式算法，首先被应用于TSP 问题.这一节也将以TSP 为例说明蚁群算法。在算法的开始，首先m 只蚂蚁基于某种规则(如

随机)置于i,j 个城市上，位于城市i 上的蚂蚁k 以(i,j)为概率函数选择的下一个城市，这个公式给出蚂蚁k 由城市r 转移到城市s 的概率:

???????∈=∑

∈否则,0

)(,)],([)],([)],([)],([),()(r J s s r s r s r s r s r p k r J u k k βαβ

αητητ （3.1）

)(r J k 是蚂蚁k 还未访问的城市列表;τ(r ，u)，边τ(r ，u)上的信息素浓度；i i d /1=η, α，

β为启发函数，这两个参数反映了信息素和启发函数的相对重要性。

第二步，当所有蚂蚁完成环游，并按式3.2进行信息素更新

ττρτ?+-=),()1(),(s r s r （3.2）

∑=?=

?m

k s r 1

),(ττ,ρ(o<ρ<1)是信息素挥发因子。

???=?其他

使用时被蚂蚁当边,0),(,/1),(k s r L s r k k τ （3.3）

k L 是第k 只蚂蚁的环游长度。这种信息素更新方式称为局部信息素更新。

最后看结束条件是否满足，如不满足则返回第一步。

3.3 MMAS 和AS 的区别

(1)当所有的蚂蚁完成环游，仅仅蚂蚁发现的最好路径上的信息素进行更新，这种信息更新方式称为全局信息素更新。

(2)每条边上的信息素被限制在区间[min

τ

,max τ]内。

(3)信息素初始化为max τ。

对每条边上的信息素浓度的限制有利于减少早熟现象。MMAS 中每条边的信息素被初始化为τ，经过几次迭代之后，每条路径上的信息素因挥发而减小，而仅有每次迭代过程中的最好路径上的信息素被允许增加，因而只有最好路径上的信息素保持一个较高水准.MMAS 性能优于AS 。MMAS 有一种改善性能的机制称之为pheromone trail

smoothing(PTS)，当MMAS 计算结果收敛至一个值停滞不变时，按如下公式调整信息素：

)),(),((),(),(m ax s r s r s r s r ττδττ-+← （3.4）

这种机制是在进化接近停滞的情况下总体上的信息素分布，其中参数δ决定了对以前信息素的保留的多少。δ=0，则是完全保留，PTS 不起作用；δ=1则完全去掉以前的信息素分布，重新开始计算.这种机制在长时间计算运算中有比较好的作用。MMAS 对信息素的强度

给予一定的限制，从而大大改善了算法的性能。

动态蚁群算法中挥发因子是动态变化，信息素浓度越高挥发因子越大，浓度越低挥发因

子越小，这样实际对信息素浓度也进行限制。使信息素不可能无限增大，也不可能为零。MMAS 中仅有最好蚂蚁所走路径上的信息素进行全局更新，如果能对更多路径上的信息素进行更新则有可能加快演化的速度,为了比较算法的全局收敛能力。

3.4 最好、最坏路径信息素全局更新策略

AS 和MMAS 仅对最好路径上的信息素进行全局更新，仅有一只蚂蚁对全局信息素的更新产生影响。如果有多只的蚂蚁对全局信息素的更新产生影响，则可加速演化过程.更新规则

如式3.4所示,对蚂蚁所走路上的信息素进行更新，即对最好路径及最差路径上的信息素进行全局更新，L(gb)是最好蚂蚁所走路径长度,L(gw)是最差蚂蚁所走路径长度,α(τ(r ，s))是全局信息素挥发因子。

3.5 MMAS 蚁群算法的特点

MAX-MIN ANT SYSTEM 蚁群算法总结了基本蚁群算法的不足之处提出的一种基于基本蚁群算法的算法，它避免了在基本蚁群算法中出现的停滞现象和收敛速度慢等现象,与ACS 算法的调整方案类似，有效地避免某条路径上的信息量远大于其它路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散，将各条路径上外激素的起始浓度设为

max τ

，

这样便可以更加充分地进行寻优解，它最好的是用在旅行商问题和SHOP-JOB 调度问题，都取得了很好的效果。

4.自适应蚁群算法

4.1 自适应蚁群算法的概述

通过我们对蚁群算法的分析和研究发现：蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解,却容易出现停滞现象。这是造成蚁群算法的不足之处的根本原因．因而我们从选择策略方面进行修改，我们采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态地调整作确定性选择的概率当进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态凋整。缩小最好和最差路径上的信息量的差距，并且适当加大随机选择的概率，以小于l 对解空间的更完全搜索，从而可 有效地克服基本蚁群算法的不足，此算法属于自适应算法。该算法按照下式4.1确定蚂蚁由所在转移到下一个城市S

{}

0,)],()][,([max arg q q j i j i <若βητ （4.1）

其中，P ∈(0，1)，r 是(0，1)中均匀分布的随机数。当进化方向基本确定后，简单的放大(或

缩小)方法调整每一路径上的信息量，该方法不仅能够加快收敛速度，节省搜索时间，而且

能够克服停滞行为的过早出现，有利于发现更好的解这对于求解大规模优化问题是有益的。通过标准蚁群算法的对比，学者就提出了一种自适应蚁群算法。

4.2 自适应的信息更新策略

4.2.1 引题

蚂蚁在行进过程中常常选择信息量较大的路径，但当许多蚂蚁选中同一条路径时，该路径中的信息量就会陡然增大，从而使得多只蚂蚁集中到某一条路径上，造成一种堵塞和停滞现象，表现在使用蚁群算法解决问题时就容易导致早熟和局部收敛。为了解决这一问题，提高蚁群算法的全局收敛能力和搜索速度，许多文献提出了各种不同的更新信息量的策略，如引言中所谈到的蚁群算法，它们在更新信息量时，1)只要蚂蚁遍历时选择此路径就更新其路径上的信息量；2)只让最优适应度的路径上的信息量增强，而其余路径上的信息量被削减；3)基于等级变化的算法，让适应度相对较好的蚂蚁固定在若干条路径上，根据其解的优劣程度决定信息量的增加幅度。这些算法虽然各不相同，但它们主要采用固定信息量增减的比例来进行信息量的更新，它们都忽视了解的分布特征，在一定程度上虽对蚁群算法的特性进行了一定的改进，但它们一般只适合于处理较小规模的问题，为了解决较大规模的问题，这里从解的分布状态入手，提出了一种新的自适应的信息量更新策略。

当问题规模较大时，由于信息量挥发系数的存在，使那些从未被搜索过的路径上的信息量减小到接近于0，从而降低了算法在这些路径上的搜索能力，反之，当某条路径中信息量较大时，这些路径中的信息量增大，搜索过的路径再次被选择的机会就会变得较大，这也影响了算法的全局搜索能力，此时通过固定地变化挥发系数虽然可以提高全局搜索能力，但却使算法的收敛速度降低，因而提出一种自适应的改变τ值的方法，将信息素更新公式：

ij

ij m ij ij ij m ij ij

ij ij t t t t t ττρτττττρτττττρτ???+-=+?+-=+-+)()1()1(,)()1()1(,)1()1()(1m in )(1m ax 时当时当 （4.2） 其中m ?是一个与收敛次数m 成正比的函数，收敛次数m 越多m ?的取值越大，如：

m ?=连续收敛次数m c

，

这里c 为常数，根据解的分布情况自适应地进行信息量的更新，从而动态地调整各路径

上的信息量强度，使蚂蚁既不过分集中也不过分分散，从而避免了早熟和局部收敛，提高全局搜索能力。

4.2.2 改进的蚁群算法过程 {初始化c ，，，ρβα等参数；

for(i=0;i

{

//*设ik0为蚂蚁k 的开始城市*// Table(k)={0,1,2,…,m -1}-ik0; ik=ik0; }

While(not 结束条件) {

for(k=0;p

if(p

for(k=0;k

//*按照公式2.1选择下一个城市jk*// Table(k)=Table(k)-jk Tourk(p)=(ik,jk); } else

for(k=0;k

jk=jk0;

Tourk(p)=(ik,jk);

}

for(k=0;k

计算Length(k)并求出最优长度的平均值Avel.

If(平均值Avel 与前一次Avel 计算值相同)m=m+1;else m=1;

()m m c ?=;

for(每条边edge(i,j)) {

ij

ij m ij ij ij m ij ij

ij ij t t t t t ττρτττττρτττττρτ???+-=+?+-=+-+)()1()1(,)()1()1(,)1()1()(1m in )

(1m ax 时当时当 }

输出最佳结果：}

上述算法根据解的分布情况自适应地进行信息量的更新，从而动态地调整了各路径上的信息量强度,增加了解空间的多样性，提高了全局搜索能力，避免了局部收敛和早熟现象，实验证明改进后的蚁群算法比传统蚁群算法和传统的MMAS 算法具有更好的搜索最优解的能力。

4.2.3 自适应蚁群算法的稳定性和收敛性

改进后的蚁群算法具有比传统蚁群算法和MMAS 蚁群算法更强的搜索全局最优解的能

力，并具有更好的稳定性和收敛性。对传统蚁群算法容易出现早熟和停滞现象的缺陷，提出了一种动态更新信息素的蚁群算法。实验表明，改进的蚁群算法具有比传统蚁群算法和MMAS 蚁群算法更强的搜索全局最优解的能力，并具有更好的稳定性和收敛性。蚁群算法作为一种新的生物进化算法，目前还没有和遗传算法、模拟退火等那样形成较系统的分析方法和坚实的数学基础，各种参数的确定也没有一定的理论指导，相信随着蚁群算法研究的不断深入，蚁群算法也将会同其他生物进化算法一样获得越来越广泛的应用和坚实的理论根据。

5.自适应蚁群算法在DNA 中的应用

5.1 序列比对

随着生物的不断进化，科学家对生物的基因产生了极大的兴趣，科学家首先对生物的遗传物质DNA 进行研究，对于DNA 是双螺旋结构的模型，美国的生物学家沃森和英国的生物物理学家克里克进行深入的探讨和研究.沃森、克里克和英国物理学家威尔金斯因发现生命的双螺旋而荣获1962年诺贝尔医学生理学奖.在此，DNA 是由四种由4种核糖核酸(A,G,C,T)组成的：A ：腺嘌呤脱氧核苷酸,G ：鸟嘌呤脱氧核苷酸，C ：胞嘧啶脱氧核苷酸，T ：胸腺嘧啶脱氧核苷酸.基因序列在突变中的变化包括替代、插入和删除，我们用“一”来表示插入和删除所产生的空位.对于,X,Y ∈ωU{—}，定义?(x,y)为计分函数，表示x,y 比较时的得分，以下是最简单的一种：

2()

(,)2

()1('_''_')

x y x y x y x y σ=∈Ω??

=-≠∈Ω??-==?

或 (5.1)

S 和T 的一个比对A 用序列和中字符的一一对应表示。其中①|S?|=|T?|，②|S?|，|T?|去掉空格就是S 和T.G 的得分为:

'

||

()1('[],'[])A i S S i T j Score σ==∑ (5.2)

取得最大值的比对就是最优比对。

下面我们举一个实例来进行说明：

现在有一对序列S=TCCAGG 和S=TGCTAG 并且建立初态矩阵如图5.1所示：

图5.1

假设有4只蚂蚁从矩阵左上角出发各选择一条路线到达右下角，就形成一个比对，规定在水平或者垂直方向上移动一格，表示在相应的序列中插入一个空位（…_?），沿对角线移动一格表示到达新位置对应的核糖核酸的匹配。现在第一只蚂蚁从左上角最终到达右下角，如图5.2所示：

图5.2

则S?=TCC_ _AGG,T?=T_GCTA_G,由式5.1和式5.2可得Score(A)=0。

现在第二只蚂蚁从左上角最终到达右下角，路径如图5.3所示：

图5.3

S?=TCC_AGG_,T?=T_GCT_AG,由式5.1和式5.2可得：Score(A)=-8。

现在第三只蚂蚁从左上角最终到达右下角，路径如图5.4所示：

图5.4

S?=T_CCAGG,T?=TGGTA_G, 由式5.1和式5.2可得：Score(A)=4。

现在第四只蚂蚁从左上角最终到达右下角，路径如图5.5所示：

图5.5

S?=TC_ _ _CAGG,T?=T_GCT_A_G, 由式5.1和式5.2可得：Score(A)=0。

在找到的所有路径中得分最高的比对就是最优比对，比较可得第三只蚂蚁所走路径为最优路径。

同样，已知S?和T?也可找到蚂蚁所走路径。

5.2 动态蚁群算法和DNA序列比对的联系

序列比对的结果表明其实质是在序列的不同位置分别插入空位，使两序列间具有最小的差异也就是最大的相似性，并从中推断其生物学意义。这里，所插入的空位即表示了序列中残基的插入、缺失、替换等操作，当然，它不同于序列中原有的“空缺”。在计算生物学中，序列比对是最基本的操作。如在序列的同源性及相似性判别，基因区域的预测等领域，序列比对都有广泛的应用。

在上述的最优比对中，我们进一步验证，当Score(A)=4时，是否为最优比对，因为规定在 (x,y)记分函数中，得分越高则越接近最优比对，即最大值就是最优比对。

用)(t ijk τ表示t 时刻图1中(i,j)位置上第k 个方向的路径ijk R 上的信息素浓度。其中i=0,1,2,3,4,5，j=0,1,2,3,4,5，而k=0，1，2分别表示向右，向下，即向右下方向。初始时刻，设定

ijk

τ

(0)=10(

τ

为常数)。

蚂蚁：Z(Z=1,2,3,4)从矩阵左上角出发，每走一步，根据当前位置上各条路径上的信息

素浓度决定向某一路径转移。为(i,j)位置上蚂蚁z 选择第k 个方向的路径定义一个得分：

()

z

ijk ijk t Score d

M α

γ

βτ= (5.3)

其中，M 为启发信息，可以根据式5.1来确定M 的值。当k=2时，即向右下方移动，所到达的新位置上，序列s ，T 对应位置上的核糖核酸如果相同，M 的值取匹配得分，式5.1中为2，不相同则M 值取不匹配罚分的绝对值的倒数为12

。k=0或1时，即向右或向下移动，必然在序

列中产生空位，M 的值取空位罚分的绝对值的倒数，为1。d 是用来调整蚂蚁的选择概率，在此，d=5,当然计分方式不同，M 的取值方法会不同。

,,αβγ是分配给信息素，启发信息和d 的权值，体现了它们对决策的影响力大小，在实验中可以进行合理地调整。设1αβγ===。

我们分别算出4只蚂蚁所走路径的总长度并求出)(总z

ijk Score 的平均值。 第一只蚂蚁所走路径为：

12002

002(0)1025100Score d M τ==??=

11101

002(0)101550Score d M τ==??=

1

2212002

1

(0)105252

Score d M τ==??= 1

0220002

(0)101550Score d M τ==??= 10230

002(0)101550Score d M τ==??=

12342

002(0)1025100Score d M τ==??= 11441

002(0)101550Score d M τ==??= 12552

002(0)1025100Score

d M τ==??=

5,5

1ijk

0,0

(0)/865.625Score

i j k ijk

i j d M τ

=====

=∑

同理，我们计算第二只蚂蚁所走的路径的平均值：

2

2002002(0)10251

00S c o r e d M τ==??= 21101002

(0)101550Score d M τ==??=

22212002

1

(0)105252

Score d M τ==??= 20220

002

(0)101550Score d M τ

==??=

2

2

3320021

(0)105252

Score d M τ==??= 2

1

431

002

(0)101550Score d M τ==??=

2

2

5420021(0)105252

Score d M τ==??= 2

0550

002(0)101550Score

d M τ==??=

5,5

2ijk

0,0

(0)/846.875Score

i j k ijk

i j d M τ

=====

=∑

计算第三只蚂蚁所走的路径的平均值：

32002002(0)1025100Score d M τ==??= 30010002(0)101550Score d M τ==??=

3

2132

002(0)1025100Score d M τ==??=

3

2232002

1(0)105252

Score d M τ

==??= 3

2342002

(0)1025100Score d M τ==??= 31441002(0)101550Score d M τ==??= 32552

002(0)1025100Score

d M τ==??=

5,5

3ijk

0,0

(0)/775Score i j k ijk

i j d M τ

=====

=∑

计算第四只蚂蚁所走的路径的平均值：

4

2002002(0)1025100Score

d M τ==??= 41101

002(0)101550Score d M τ==??= 40110002(0)101550Score d M τ==??= 40120002(0)101550Score d M τ==??= 40130

002(0)101550Score d M τ==??= 40230002(0)101550Score d M τ==??= 42342002(0)1025100Score d M τ==??= 41441002(0)101550Score d M τ==??= 42552

002(0)1025100Score

d M τ==??=

5,5

4ijk

0,0

(0)/866.667Score

i j k ijk

i j d M τ

=====

=∑

由计算可总结出)(总z

ijk Score 的平均值的公式：

z

ijk /0,1,2

(0)Score k ijk k d

M α

γ

τ=

∈∑（）蚂蚁所走的方格总数 (5.4)

由四只蚂蚁所走路径的平均值可得，第三只蚂蚁的平均值最高，那么我们就选择第三只

蚂蚁进行优化，实行第二次更新，在此之前我们遵循以前的规定，即蚂蚁只有三个方向可供选择，右边，下边，右下角方向，并结合式5.1和式5.2的罚分策略，我们只选择得分最高的方向为蚂蚁下一步路径(注意：罚分策略一定要慎重考虑）。 因此，在选择下一步时应该先计算三个方向的Score(A)的值：

30020002(0)101550Score

d M τ==??=

3

1101002

(0)101550

S c o r e d M τ

==??= 3

2112

002(0)1025100Score

d M τ==??=

所以蚂蚁选择得分为3

112Score 的这条路径，即这条路径也就是沿对角线方向最相似的路径，依照同样的方法计算并选择，蚂蚁走的就是最优路径，也就是DNA 链最优的比对。

上一种算法假设我们设置一个参数是0(0,1)q ∈,蚂蚁在选择路径时产生一个（0，1）之间的随机数P ，那么上面的算法设置为00.8,0.3P q ==第三只蚂蚁选择)

2,1,0(=k Score z

ijk 之中分值最大的方向。

当0q p >时，我们设P=0.7，0

q =0.5，第三只蚂蚁按式5.5决定三个方向的概率：

20

()z

z ijk

ijk

z ijk

k t Score

P

Score

==

∑ (5.5)

经过一代进化，当所有的蚂蚁通过不同的路径达到矩阵右下角，得到一组比对结果。就完成了寻找最优路线的一次循环，我们对路径上的信息素浓度进行更新如下：

(1)()ijk

ijk ijk t t τ

ττ+=+? (5.6)

1

m

z ijk

ijk

z τ

τ=?=

?∑

其中ijk τ

?为本次循环中路径ijk R 中的信息素增量，设初始值时刻0ijk

τ?=，z ijk

τ

?

为第Z 只蚂蚁在路径ijk R 上留下的信息素，那么z ijk

τ

?计算公式如下：

1

,(210)z

m

ijk ijk ijk

z Q

Q Score Score

τ=?=

?=∑其中 (5.7)

在每只蚂蚁所选的下一步有三个方向，在三个方向上的信息素浓度的增加量不尽相同，

而这三个方向与相邻的路径（相邻表格）和路径方向的得分值有关。

由计算可知第三只蚂蚁所走的路径得分最高，说明该路径在已知路径中是最好的路径选择，那么我们就选择此路径进行信息量的调整。

由于手工计算量有限，选一个三行三列的矩阵进行计算，图如下：

图5.6

比如蚂蚁从①开始移动，可供选择的方向右、向下、右下角，也就是方格②、④、⑤，那么我们就计算在这三个方向的信息素增量。

已知ijk Score ∑=525，Q=210；z

ijk Score 的值计算可得：

3

010010210

2510525

ijk

Q

Score Score

τ?=

?=

?=∑ 3

112112210

5020525

ijk

Q

Score Score

τ?=

?=

?=∑ 3

101101

210

5020525

ijk

Q

Score

Score

τ?=?=?=∑ 3

010010

2102510525ijk

Q

Score

Score

τ?=?=?=∑ 3

122122

2102520525

ijk

Q

Score

Score

τ?=?=?=∑ 3

111111

2105020525ijk

Q

Score

Score

τ?=?=?=∑ 3

121121

2105020525ijk

Q

Score

Score

τ?=?=?=∑ 3

110110

2105020525ijk

Q

Score

Score

τ?=?=?=∑ 3212

212

2102510525

ijk

Q

Score

Score

τ?=?=?=∑

3

201201

210

2510525ijk

Q

Score

Score

τ?=?=?=∑ 3

120120

2105020525ijk

Q

Score

Score

τ?=?=?=∑ 3

211211

2102510525

ijk

Q

Score

Score

τ?=?=?=∑ 3

222222

21010040525

ijk

Q

Score

Score

τ?=?=?=∑ 3

2102102102510525

ijk

Q

Score

Score

τ?=?=?=∑ 3

220

220

21010040525

ijk

Q

Score

Score

τ?=?=?=∑ 计算了每一条可能路径的信息素得增量，根据罚分策略和式5.7可以得出，得分值越高，说明信息素浓度越强。我们对新的信息素浓度进行更新（在这里不考虑旧信息素浓度的挥发），更新公式是

(1)()ijk

ijk ijk t t τ

ττ+=+?。在每一代进化完以后又进行新一轮的信息

素调整，得出一组最优解，直到算法达到最大进化代数或者最优解连续10代不再变化时信息素调整结束。那么得出的一组解就可能是最好解，也就是对应的序列越接近最优序列比对（即 最终由动态蚁群算法得出得最优路径也就是最相似得两条DNA 链，这两条DNA 链的相似性就越强）。

当然，以上只是取了三行三列的矩阵进行计算，如果手工计算是相当繁琐的工作，但是原理都是一样的。

为了简单直观，我们建立一个9*9的矩阵如下：

1

2345678

91010020200000200100202000030000020000400002001010050000020010406000000004070000000100800000000409

000000000??

??????

??

??????

??

??????

????

??

????

由矩阵可知信息素浓度越高对应的序列越接近最优解。那么以后的信息素增量把以前的