ＡＣＯ算法及应用

【摘要】ACO算法是一种新型模拟进化算法，为求解复杂的组合优化问题提供了一种新的思路和方法。文章对ACO算法理论做简要的综述，并介绍其在实际问题中的应用。最后对ACO算法仍需要解决的问题和未来的发展方向进行了探讨。

【关键词】ACO算法；组合优化；人工蚁群

【中图分类号】TP301【文献标识】A

【文章编号】1671-5969（2007）02-0127-02

当今科学技术正处于多学科相互交叉和融合的时代。随着人们认识与改进世界范围的扩大，人们对科学技术提出了更高更新的要求，单一领域的研究已经无法满足人们改造世界的需求，人类面临的许多复杂课题都需要通过交叉学科研究才能够得到解决。随着科技和经济的高速发展，人们对高效的优化技术和智能计算的要求日益迫切。

优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一个重要的学科分支，一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、VLSI技术、多代理机器人之间的任务协调和计算机并行处理等。鉴于实际工程问题的复杂性、约束性、非线性、建模困难等特点，寻找一种适合于大规模并行且具有智能特征的优化算法已成为有关学科的一个主要研究目标和引人注目的研究方向。

目前，除了已得到公认的遗传算法、模拟退火算法、禁忌搜索法、人工神经网络等进化算法，近几年提出的蚁群算法正开始崭露头角，为复杂困难的系统优化问题提供了新的具有竞争力的求解算法，应用范围也开始遍及到许多科学技术及工程领域。

一、群集智能

仿生学是人类一直使用的方法，如模仿海豚皮而构造的“海豚皮游泳衣”、模仿人眼视网膜工作原理，制成的“生物电子位置传递器”，模拟活细胞生化过程及其调控机制，研制的人工模拟线粒体膜、叶绿体膜的人造能量转换膜等。群居昆虫以集体的力量，进行觅食、御敌、筑巢等。这种群体所表现出来的“智能”，就称之为群体智能。如蜜蜂采蜜、筑巢、蚂蚁觅食、筑巢等。从群居昆虫相互合作进行工作中，得到启迪，研究其中的原理，以此原理来设计新的求解问题的算法。这是仿生学的另一重要领域，它是受自然界规律的启迪，根据其原理，模仿设计求解问题的算法。如人工神经网络技术、遗传算法、进化规划、模拟退火技术和群集智能技术等。ACO蚁群优化算法亦属于这一领域，它是近几年发展起来的一种新型模拟进化算法，研究表明该算法具有并行性，鲁棒性等优良性质，为解决许多优化问题提供了新的方向。

二、ACO算法理论

对于蚂蚁这类群居昆虫，其单个蚂蚁的行为极其简单。但由这些简单的个体组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务。蚁群会很快找到蚁穴到食物处的最短路径。此外，蚁群还能够适应环境的变化，当蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。

仿生学家通过大量的观察研究发现，蚂蚁在寻找食物或回穴的路径中，会在它们经过的地方留下一些“信息素”，用以与群体中的其他蚂蚁进行信息的交流。蚂蚁在运动的过程中能感知这些物质，并以此来指导自己的运动方向。具体表现在蚂蚁以相对较高的概率选择信息素浓度较高的路径，而后到者留下的信息素会对原有的信息素进行加强。这样，蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，在该路径上留下的信息素浓度也越高，后来的蚂蚁选择该路径的概率就越大。蚂蚁个体间就是通过这种信息的交流达到搜索食物的目的。

20世纪90年代，意大利学者正是充分利用了蚂蚁搜索食物的过程与著名的旅行商问题之间的相似性，最早提出了蚁群算法。不同的蚁群算法模型的定义虽然在一定程度上受到问题结构化的影响，但就求解组合优化问题而言，所有的蚁群算法都是以Macro Dorigo针对TSP问题提出的基本蚁群算法为基础。因此，下面先简要地介绍用于TSP问题求解的蚁群算法。

为模拟实际蚂蚁的行为,首先引入如下记号,设m是蚁群中蚂蚁的数量。d_ij(i,j=1,2,…,n)表示城市i和j之间的距离，τ_ij(t)表示在t时刻城市i和j之间的路径上残留的信息量。来模拟实际蚂蚁的信息素浓度。

在初始化的时候,m个蚂蚁被放置在不同的城市上,赋予每条边上的信息量为τ_ij(0)。每个蚂蚁k的tabuk的第一个元素赋值为它所在的城市。

用pk_ij(t)表示在t时刻蚂蚁k由城市i转移到城市j的概率,则

其中allowed_k表示蚂蚁k下一步允许走过的城市的集合,它随蚂蚁k的行进过程而动态改变;信息量τ_ij(t)随时间的推移会逐步衰减,用1—ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用;η_ij(t)为由城市i转移到城市j的期望程度,可根据某种启发算法而定。

经过n个时刻,蚂蚁k走完所有的城市,完成一次循环。此时,要根据下式对各路径上的信息量作更新:

Δτk_ij表示蚂蚁k在本次循环中在城市i和城市j之间留下的信息量,其计算方法根据计算模型而定,在最常用的antcyclesystem模型中:

其中Q为常数,L_k为蚂蚁k在本次循环中所走路径的长度。

三、ACO算法流程

步骤1nc=0(nc为迭代步数或搜索次数);每条边上的

τ_ij(0)=c(常数),并且Δτ_ij=0;放置m个蚂蚁到n个城市上。

步骤2将各蚂蚁的初始出发点置于当前解集tabu_k(s)中;对每个蚂蚁k(k=1,…,m),按概率p_ijk移至下一城市j;将城市j置于tabu_k(s)中。

步骤3经过n个时刻,蚂蚁k可走完所有的城市,完成一次循环。计算每个蚂蚁走过的总路径长度L_k,更新找到的最短路径。

步骤4更新每条边上的信息量τ_ij(t+n)

步骤5对每一条边置Δτ_ij=0;nc=nc+1。

步骤6若nc<预定的选代次数NCMAX,则转步骤2;否则,打印出最短路径,终止整个程序。

四、人工蚂蚁

人们利用蚁群优化算法解决实际问题的过程实际上是利用问题与真实蚂蚁觅食过程的相似性，把问题抽象为真实蚂蚁觅食的过程。这样，人们便抽象出许许多多的“人工蚂蚁”来帮助我们解决实际问题。

人工蚂蚁吸收了蚂蚁群体行为的典型特征：一是能觉察小范围区域内状况，并判断出是否有食物或其他同类的信息素轨迹；二是能释放自己的信息素；三是所遗留的信息素量会随时间而逐步减少。

蚂蚁算法通过候选解组织群体的进化过程来寻求最优解,这一过程包括适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息不断调整自身的结构;在协作阶段各候选解间通过信息交流,以便产生性能更好的解。在蚁群算法中,一个有限规模的人工蚁群体,通过相互协作搜索用于解决优化问题的较优解。每只蚂蚁根据问题依赖的准则,从被选的初始状态出发建立一个可行解或是解的一个组成部分。在建立蚂蚁自己的解决方案中,每只蚂蚁都搜集关于问题拓征和其自身行为的信息,并且使用这些信息来修改问题的表现形式,正如其它蚂蚁所看到的那样。蚂蚁既能共同的行动又能独立的工作,显示出了一种相互协作的行为,它们之间不使用直接通讯,而使用信息激素指导着蚂蚁间的信息交换。蚂蚁使用一种结构上的贪婪启发式搜索可行解。根据问题的约束条件列出了一个解,作为经过问题状态的最小代价(最短路径)。每只蚂蚁都能够找出一个解,但可能是较差解。蚁群中的个体同时建立了很多不同的解决方案,找出高质量的解是群体中的所有个体之间全局性的相互协作的结果。

只要我们擅于利用问题与蚁群算法之间的相似性，模拟出人工蚂蚁来帮助解决问题，那么蚁群算法的应用范围将是广阔的。

五、ACO算法在组合优化中的应用

ACO蚁群算法主要用于求解不同的组合优化问题，一类应用于静态组合优化问题，另一类用于动态组合优化问题。静态问题指一次性给出问题的特征,在解决问题过程中,问题的特征不再改变。这类问题的范例就是经典旅行商问题(TSP);动态问题被定义为一些量的函数,这些量的值由隐含系统动态设置。因此,问题在运行时间内是变化的,而优化算法须在线适应不断变化的环境。这类问题的典型例子是网络路由问题。

目前，在静态组合优化问题中，蚁群算法主要用于解决旅行商问题，二次分配问题，车间任务调度问题，车辆路线问题，图着色问题，有序排列问题等。

在动态组合优化问题中，主要应用于有向连接的网络路由和无向连接的网络路由等。研究表明，用蚁群算法研究解决包含带宽、延时、延时抖动、包丢失率和最小花费等约束条件在内的QoS组播路由问题，效果优于模拟退火算法及遗传算法。

另外，蚁群算法在其他领域也得到了应用，如在解决管线敷设问题，机构同构判定问题，开关合布线问题等都取得了令人满意的结果。

六、结语

ACO蚁群算法是一种新的仿生启发式优化算法，刚刚问世几年，其理论还十分不完善，存在着搜索时间较长，在算法模型、收敛性及理论依据方面还有许多工作有待进一步深入研究。但其在解决组合优化问题中的优越性也是显著的，它具有较强的鲁棒性、通用性、并行搜索等优点。

对ACO算法的研究才刚刚起步，需要解决的问题还有很多很多，但这是一种用途广泛且高效的算法，值得我们去深入地研究和优化其算法。相信日后会在更多的领域用到“人工蚂蚁”！

【参考文献】

[1]宋雪梅．蚁群算法及其应用[D]．河北理工学院学报，2006．

[2]李士勇．蚁群优化算法及其应用研究进展[D]．哈尔滨工业大学学报，2003．

推荐访问:算法 ACO