相同的任务、随机选择策略；另一方面，它们还具有以下三种特性： (1)人工蚂蚁具有记忆能力。
(2)人工蚂蚁生活在离散时间的环境中。
(3)人工蚂蚁选择路径时并不是完全盲目的，受到问题空间特征的启发，按一定算法规律有意识地寻找最短路径。
基本蚁群算法是采用人工蚂蚁的行走路线来表示待求解问题可行解的一种方法。每只人工蚂蚁在解空间中独立地搜索可行解，当它们碰到一个还没走过的路口时，就随机挑选一条路径前行，同时释放出与路径长度有关的信息素。路径长度越短信息素的浓度就越大。当后继的人工蚂蚁再次碰到这个路口的时候，以相对较大的概率选择信息素浓度较高的路径，并在“行走路线”上留下更多的信息素，影响后来的蚂蚁，形成正反馈机制。随着算法的推进，代表最优解路线上的信息素逐渐增多，选择它的蚂蚁也逐渐增多，其他路径上的信息素却会随着时间的流逝而逐渐消减，最终整个蚁群在正反馈的作用下集中到代表最优解的路线上，也就找到了最优解。在整个寻优过程中，单只蚂蚁的选择能力有限，但蚁群具有高度的自组织性，通过信息素交换路径信息，形成集体自催化行为，找到最优路径。
2.2蚁群算法的模型
为了更好的理解蚁群算法的模型和实现过程，我们以求解平面上n个城市(1,2,L,n为城市编号)的TSP问题为例，说明蚁群算法模型。首先引入如下记号： m——蚁群中蚂蚁的总数。
nij（i，j）——路径的能见度,用某种启发式算法算出，在TSP问题中，一般取
nij?1d，dij表示城市i与城市j之间的距离，i,j∈{1,2,L,n}。
ij?ij(t)——在t时刻路径（i，j）上残留的信息素。
??ij——一次循环中路径（i，j）上的信息素增量。
（i，j）上的信息素 ??ij——第k只蚂蚁在一次循环中留在路径
(k)pij(k)(t)——在t时刻蚂蚁k由位置i转移到位置j的概率。
?——启发因子，轨迹的相对重要性，亦即蚁群在运动过程中所残留的信息素的
相对重要程度。
?——期望启发因子，能见度的相对重要性。
?——信息素挥发度(0≤ρ<1),1?ρ可理解为信息素的残留系数。
Q——蚂蚁循环一次在经过的路径上所释放的信息素总量。
TSP求解中，蚁群算法中的每只人工蚂蚁具有以下特征：
(1)根据以城市距离和连接边上信息素的数量为变量的概率函数选择下一个城市。
(2)规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市，由禁忌表控
6
制。
(3)完成周游后，蚂蚁在它每一条访问的边上留下信息素。
于是，基本蚁群算法可以理解为：初始时刻，各条路径上的信息素相等，设
?ij(0)=常数。蚂蚁k(k=1,2,L,m)在运动过程中根据各条路径上信息素决定转移方
向。在t时刻，蚂蚁k在城市i选择城市j的转移概率为如下：
pij(k)(t)，其计算公式
其中，allowedk?{1,2，L,n}?tabuk表示蚂蚁k下一步允许选择的城市，
tabu用以记录蚂蚁k当前所走过的城市，tabu集合随着进化过程做动态调
kk(t)与?ij??ij成正比，蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向。为了避免残留信息素过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息素进行更新处理。(t+n)时刻，所有的蚂蚁完成了周游,路径(i,j)上信息素可根据以下公式做调整： 整。上式表明：转移概率
pij(k)??
根据信息素更新策略的不同，Dorigo M提出了三种基本蚁群算法模型，分别称之为蚁周模型(Ant-Cycle Model)，蚁量模型(Ant-Quantity Model)及蚁密模型(Ant-Density Model)。 蚁周模型：
L
k表示第k只蚂蚁在本次循环中所走路径的总长度。
蚁量模型：
7
蚁密模型：
上述三种模型的区别在于：蚁周模型利用的是蚁群的整体信息，即走完一个循环后才进行残留信息素的全局调整；而在蚁量、蚁密这两种模型中，蚂蚁每走一步都要更新残留的信息素，利用的是局部信息。本文的研究都是基于蚁周模型基础之上。
解TSP的蚁群算法的基本步骤如下：
第1步：初始化参数m、α、β、ρ、Q。令t=0,循环次数nc=0,设置最大循环次数NC,路径(i,j)的初化信息量?ij(0)=常数，初始时刻??ij(0)?0。
第2步：将各蚂蚁的初始出发点置于当解集中；对每只蚂蚁k(k=1,2,3,L,m),按概率
pijk（公式2.1）移至下一顶点j；将顶点j置于当前解集。
第3步：计算各蚂蚁搜索的路径长度Lk(k=1,2,L,m)；记录当前的最好解。 第4步：按更新方程(2.2)、（2.3）修改路径上的信息素。 第5步：对各条路径(i,j)，置??ij?0；nc?nc?1。 第6步：若nc 算法流程如图2.2所示。 8 图2.2 基本蚁群算法流程图 2.3蚁群算法的参数分析 从蚁群算法的模型中可以看出，蚁群算法的参数空间庞大。合适的参数组合能够有全局搜索能力和较快的收敛速度，不合适的参数组合则会使得算法收敛较慢或达到局部最优解。然而，目前对各参数该如何选择也没有严格的理论依据，只是根据经验和试验来选取合适的参数值。基于此，国内外许多研究人员在蚁群算法的参数分析和优化组合方面做了大量工作。Dorigo M等最早对α、β、ρ、m等参数的选择进行了初步研究；国内的段海滨、叶志伟、蒋玲艳、涂亚平等也对参数的选择进行了研究。研究表明：对于TSP问题，基本蚁群算法的初始参数的选择也有一般规律。 (1)蚂蚁数量m 蚁群算法是通过多个候选解组成的群体进化过程来搜索最优解，所以蚂蚁的数目m对蚁群算法有一定的影响。m大(相对处理问题的规模)，会提高蚁群算法 9 的全局搜索能力和稳定性，但数量过大会导致大量曾被搜索过的路径上的信息素变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度减慢。反之，m小，会使从来未被搜索到的解上的信息素减小到接近于0，全局搜索的随机性减弱，虽然收敛速度加快，但是会使算法的全局性能降低，稳定性变差，出现过早停滞现象。经大量的仿真试验获得：当m∈[0.6 n,0.9 n]时（n为城市规模），蚁群算法的全局收敛性和收敛速度都比较好。 (2)启发因子α 启发因子α是表示蚂蚁在运动过程中所积累的信息素在指导蚁群搜索中的相对重要程度，其大小反映了蚂蚁在路径搜索过程中随机因素作用的强弱。α越大，蚂蚁选择以前走过路径可能性就越大，实现自催化过程，但搜索的随机性减弱；α越小，易使蚁群算法过早陷入局部最优。文献研究表明：对于小规模的TSP问题，在蚁群算法的三种模型中，α=1时，解的质量和稳定性都是最好的。 (3)期望启发因子β 期望启发因子β是表示能见度相对重要程度的参数。β的大小反映了蚂蚁在路径搜索过程中确定性因素作用的强弱。文献研究表明：β过小，将导致蚂蚁群体陷入纯粹的随机搜索，在此情况下很难找到最优解；β过大，蚂蚁在局部点上选择局部最短路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易陷入局部最优。对于TSP问题，不同城市规模，β的具体取值各有不同。对于Oliver 30TSP来说：β∈[2,8.5]时，算法的综合性能比较好。 (4)信息素挥发度ρ 在蚁群算法中，人工蚂蚁是具有人类记忆功能的，随着时间的推移，以前留下的信息将要逐渐消逝。如前所述，在算法模型中，参数ρ表示信息素挥发度，其大小直接关系到蚁群算法的全局搜索能力及其收敛速度；1?ρ信息素残留因子，反映了蚂蚁个体之间相互影响的强弱。研究表明：在其它参数相同的情况下，信息素挥发度ρ的大小对蚁群算法的收敛性影响非常大，ρ与循环次数近似成反比关系。当ρ极小时，路径上残留信息占主导地位，信息正反馈作用相对较弱，搜索的随机性增强，因而蚁群算法的收敛速度很慢。若ρ较大时，正反馈作用占主导地位，搜索的随机性减弱，导致收敛速度快，但易陷入局部最优状态。对于TSP问题，不同的问题规模，ρ的取值也不尽相同。对于Oliver 30TSP来说：ρ∈[0.1,0.5]时，算法的性能较好。 (5)总信息量Q 总信息量Q为蚂蚁循环一周时释放在所经路径上的信息素总量，在基本蚁群算法中它为一常量。一般的理解是：总信息量Q越大，则在蚂蚁已经走过的路径上信息素的累积越快，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。Q值过小，则信息素浓度增长太慢，正反馈信息太少，使算法难以收敛。研究表明：在蚁周模型中，由于TSP的规模不同，路径长度各不相同，如果对不同的TSP使用相同的Q值，则信息素总量更新尺度是不同的，最终修改信息素的程度存在很大不稳定性。Q的取值应与所处理的TSP的规模相对应，确保信息素总量更新在可控制范围内。在小规模TSP问题中，Q=100是大多数论文所公认的较好的值。 2.4蚁群算法的优缺点 2.4.1蚁群算法的优点 蚁群算法的成功运用激起了人们的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。研究表明，蚁群算法是一种有效的随机搜索算法，具有如下优点： 10