蚁群算法研究综述

蚁群算法综述

控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景

蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。

从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。

二、蚁群算法的研究发展现状

国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。提出一种基于蚁群算法的TSP问题分段求解算法。王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。

随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。ACO-MH为蚁群算法的理论研究和算法设计提供了技术上的保障。在蚁群优化的收敛性方面，W.J.Gutjahr做了开创性的工作，提出了基于图的蚂蚁系统元启发式(Graph-Based Ant System Metaheuristic)这一通用的蚁群优化

的模型，该模型在一定的条件下能以任意接近l的概率收敛到最优解。T.StBtzle 和M.Dorigo对一类ACO算法的收敛性进行了证明，其结论可以直接用到两类实验上，证明是最成功的蚁群算法——MMAs和ACS。N.Meuleau和M.Dorigo研究了

随机梯度下降(Stochastic Gradlent Descent，简称SGD)和蚁群优化之间的关系，将蚁群优化看成是一种近似的SGD算法，并根据SGD实现了理论上收敛的蚁群优化算法。蚁群算法的应用研究一直非常活跃。继M.Dorigo首先将AS算法用于TSP 问题之后，V.Maniezzo等人首先将AS算法应用于指派问题(QuadraticAssignment Problem，简称QAP)。最近几年Gambardella，Thailard和StUtzle等也发表了一些用蚁群算法求解QAP问题的文章。目前，蚁群算法是求解QAP问题最有效的算法之一。

蚁群算法在通讯网络领域(尤其是网络路由问题)的应用受到越来越多的学者的关注。由于网络中的信息分布性、动态性、随机性和异步性与蚁群算法相似，如利用局部信息发现解，间接的通讯方式和随机状态的转换。Di Caro和Dorigo 已经在相关的文献中将ACO应用于网络路由问题，并称这种算法为Antnet。

除了各种组合优化问题外，蚁群算法还在函数优化、系统辨识、机器人路径规划、数据挖掘、大规模集成电路的综合布线设计等领域取得了令人瞩目的成果。

三、蚁群算法的原理及数学模型

1.蚁群算法的基本原理

根据生物学家和仿生学家的长期观察和研究发现，没有视觉的蚂蚁在运动时会通在路径上释放出一种特殊的分泌物——信息素，并通过其来寻找路径。当它们碰到一个还没有走过的路口时，就随机挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的推移而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快地重新找到最优路径。信息素在蚁群寻找最优路径的过程中发挥了重要作用。

2.蚁群算法的机制原理

蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设：

(1)蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环

境做出反应，也只对其周围的局部环境产生影响。

(2)蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行

为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。

(3) 在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单

只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体

行为。

由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁

群算法不需要对所求的问题的每一方面都有非常深入的了解。

3． 蚁群算法的数学描述

组合优化(Combinatorial Optimization)是运筹学中最活跃的分支之一，在计算机科学、计算生物学、物流和供应链管理等新兴领域有大量的应用。组合优化主要通过研究数学方法寻找到离散事件的最优编排、分类、次序或筛选等。组合优化又称组合规划，是指在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划。从最广泛的意义上说，组合规划与整数规划这两者的领域是一致的，都是指在有限可供选择方案组成的集合中，选择使目标函数达到极值的最优子集。旅行商问题是运筹学的著名命题，也是目前研究最为广泛的组合优化问题之一。对TSP 的研究成果将对求解NP(Non ．deterministic Polynomial Time)类问题产生重要影响。

蚂蚁在运动过程中，根据各条路径上的信息量及路径的启发信息来计算状态转移概率。每个蚂蚁应用一个状态转移规则来建立一个问题的解决方案，直到所有蚂蚁都建立了完整的解决方案。完成一次循环后，各路径进行信息量调整，存储所找到的最短路径，直到满足条件为止，其中状态转移规则为：

??∈??=∑?else allowed j t t t t t k allowed s is is ik ij k k ,0,)]([)]([)]([)]([)(P ij 若βαβαητητ （1）

),...,2,1(m k tabu k =用以记录蚂蚁k 当前过的城市为记忆列表，其中允许

)(k tabu n k -=集合k tabu 随着进化过程动态调整，

ij η为先验知识能见度在TSP 问题中为城市转移到城市的启发信息，一般取ij ij /d 1=η，

α为路径上ij 残留信息的重要程度，β为启发信息的重要程度。

信息素更新规则采用如下公式：

),1,()()1(+?+?=+t t t t ij ij ij ττρτ （2）

,)1,()1,(1∑=+?=+?m

k k ij ij t t t t ττ （3）

???=+?否则在本次循环中经过路径如果蚂蚁,0);,(,/),(j i k L Q n t t k k ij

τ （4）

其中：k L 为第k 只蚂蚁在本次循环中所走的路径长度，Q 是信息素强度，)1,(+?t t k

ij τ表示第k 只蚂蚁在时刻)1,(+t t 留在路径),(j i 上的信息素量，)1,(+?t t ij τ表示本次循环中路径),(j i 的信息素的增量；)1(ρ-为信息素轨迹的衰减系数）（,10∈ρ。

根据具体算法的不同，ij τ?，k ij τ?及)(P t k

ij 的表达形式可以不同，Dorigo 曾给出3种不同模型，分别称为蚁周系统、蚁量系统和蚁密系统，在蚁量系统和蚁密系统中，蚂蚁在建立方案的同时释放信息素，利用的是局部信息；而蚁周系统是在蚂蚁已经建立了完整的轨迹后再释放信息素，利用的是整体信息。在一系列的标准测试问题上的运行试验表明，蚁周算法的性能优于其他两种算法。 四、 蚁群算法的实现步骤和程序流程图

以TSP 为例，基本蚁群算法的具体实现步骤如下：

(1)参数初始化。令时间0=t 和循环次数0=c N ，设置最大循环次数m ax c N ，将

m 只蚂蚁置于n 个城市上)(n m <，令有向图上每条边),(j i 的初始化信息量const ij =τ，其中const 表示常数，且初始时刻0)0(=?ij τ。

(2)循环次数1+←c c N N 。

(3)蚂蚁数目1+←k k 。

(4)蚂蚁个体根据状态转移概率公式(1)计算的概率选择城市j 并前进，

{}k tabu C j -∈。

(5)修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中。

(6)若集合C 中城市未遍历完，即m k <，则跳转到第(3)步，否则执行第(7)步。

(7)根据公式(2)和式(3)更新每条路径上的信息量。

(8)若满足结束条件，即如果循环次数cmac c N N ≥，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。

蚁群算法的程序流程图如下图所示：

图1 基本蚁群算法的程序结构流程

五、蚁群算法与其它智能算法的比较

当前研究的很多算法都是人们受到大自然现象的启发，通过模拟大自然一些物种的行为提出的，如蚁群算法是模拟自然界蚁群行为，遗传算法是基于生物进化理论原理发展起来的，人工神经网络算法是模拟人脑组织结构和运行机制，模拟退火算法来源于固体退火原理等。这些仿生优化算法通过模拟生物系统中生物体本能特性和无意识的寻优活动优化自身状态，以达到获得求解问题的最优解。作为同一类的智能算法，它们有许多相同的特点。

(1)都是不确定性的算法

生物体在自然界中并不是确定性变化的，正是由于本身一些不确定性因素的影响，导致生物体个体之间的差异，也保证生物种群的多样。仿生优化算法利用了这种不确定性的特性，它们借助随机特性，保证算法在求解过程中存在一定的不确定性因素，从而实现算法个体求解的多样性。也正是这种多样性，使得算法在求解某些问题的过程中，能够避免陷入局部解，保证整个求解过程朝着最优解的方向不断进行。实践证明，仿生优化算法中的随机特性有助于问题的求解，在求解性能上优于一些确定性的算法。

(2)没有严格的数学特性

这些算法在优化过程中都不依赖于优化问题本身的数学性质(如连续性、可导性)以及目标函数和约束条件的精确数学描述。同时算法本身由于存在一定的