群智能蚁群算法及其改进策略研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇群智能蚁群算法及其改进策略研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文首先介绍了群智能理论的产生、蚁群的觅食行为以及蚂蚁的信息系统，其次介绍了蚁群算法的基本原理以及基本模型。最后对蚁群算法的改进策略和未来的发展方向进行了探讨。

关键词：蚁群算法；蚂蚁系统；信息素；改进算法

中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)15-20ppp-0c

Research on Ant Colony Algorithm Based on Swam Intelligence and its' Improve Algorithm

BAO Dan-dan,WANG Hong

(College of Computer Science,South-central University for Nationalities,Wuhan 430074,China)

Abstract:A survey of origin of swam intelligence are presented in this paper.At first ant colonies foraging behavior and their communication system are briefly introduced.then the basic principle and the basic model of artificial ant colony algorithm is presented.Finally the improve algorithm about ACA and the future works are discussed.

Key words:Ant Colony Algorithm;ant system;pheromone;Improve algorithm

1 引言

群智能(Swarm Intelligence,SI)的概念最早由Beni,Hack-wood和wang在分子自动机系统中提出。群智能的一种定义是：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。这里，Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。每只蚂蚁的智能并不高，但它们却能协同工作，依靠群体能力发挥出超出个体的智能，且这种能力不是多个个体之间的能力通过简单叠加所获得的，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息,而且群内个体还能处理信息，这样就使得群体涌现出一些单个个体所不具备的能力和特性尤其是对环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能，也就是说动物个体通过聚集成群而涌现出了智能。

生物学家和仿生学家观察研究发现，蚂蚁在觅食走过的路径上释放一种特有的分泌物―信息素(Pheromone)，蚂蚁个体之间正是通过这种信息素传递信息，从而相互协作，完成从蚁穴到食物源寻找最短路径的复杂任务。从蚂蚁群体寻找最短路径觅食行为受到启发，意大利学者Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法―人工蚁群算法，简称蚁群算法。蚁群算法(ant colony algorithm,ACA)是最新发展起来的模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算机制、易于与其它方法相结合等优点。

2 蚁群算法的基本原理

蚁群算法不需要任何先验知识，最初只是随机选择搜索路径，随着对解空间的“了解”，搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间的“了解”机制主要包括三个方面[1]：

⑴蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时候不会再被选择，由此在蚁群算法中建立tabu（禁忌）列表来进行模拟。

⑵蚂蚁利用信息素(pheromone)进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介。

⑶蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜索就完全不同，当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发，因此，模拟这种现象即可利用群体智能建立路径选择机制，使蚁群算法的搜索向最优解推进。

蚁群算法所利用的搜索机制呈现出一种自催化或正反馈的特征，因此，可将蚁群算法模型理解成增强型学习系统，图1说明了蚂蚁群体的路径搜索原理和机制。假定障碍物的周围有两条路可以从蚁巢到达食物，即（蚁巢-ABD-食物）和（蚁巢-ACD-食物），路径的长度分别为4和6 。每只蚂蚁在单位时间内移动一个单位长的距离，并在走过的路径上遗留一个单位的信息素。开始时所有道路上未留有任何信息素，假设在t=0时刻，有20只蚂蚁从蚁巢出发移动到A。它们以相同概率选择左侧或右侧的路径，因此有10只蚂蚁走左侧，10只走右侧。在t=4时刻，第一批找到食物的蚂蚁将返回，在t=5时刻，两批蚂蚁将在D点相遇，此时BD上的信息素数量与CD上的相同，因为各有10只蚂蚁选择了相应的道路。从而有5只返回的蚂蚁将选择DB而另5只选择DC。在t=9时刻，前5只蚂蚁又返回A并且再次进行往左还是往右的选择。这时，AB上的信息素数量是20而AC上是15，因此将有较多的蚂蚁选择往左，从而增加了该路径的信息素数量。随着这种过程的不断进行，两条路径上的信息素数量的差距将越来越大，直到绝大多数蚂蚁都选择了最短的路径，正是由于一条路要比另一条路短，因此，在相同的时间区间内，短的路线会有更多的机会被选中。

3蚁群算法

3.1基本蚁群算法模型

为模拟实际蚂蚁的行为，首先引进如下记号[2]：

设：m――蚁群中蚂蚁的数量；

ηij――边弧（i,j）的能见度；

τij――t时刻在ij之间路径上的信息量；

Δτkij――蚂蚁本次遍历中信息素浓度的增量;

Pkij(t)――表示在t时刻蚂蚁k从城市i移动到城市j的概率,j是此次遍历中还未访问的城市;

α――轨迹的相对重要性（α≥0）；

β――能见度的相对重要性（β≥0）；

ρ――轨迹的持久性（0≤ρ≤1），1－ρ理解为轨迹衰减度；

Q――体现蚂蚁所留轨迹数量的一个常数。

现以求解n个城市的TSP问题为例，说明蚁群系统模型。

旅行商问题是指，给定n个城市和每个城市之间的距离，要求确定一条经过每个城市一次且只有一次的最短路径。初始时刻，各条路径上信息量相等，设τij（0）=C（C为常数），蚂蚁k（k=1,2,3…,m）在运动过程中，根据各条路径上的信息量决定转移方向，移动概率为

bdd02.tif

其中，allowedk ={0,1,…,n-1}－tabuk表示蚂蚁k下一步允许选择的城市，与实际蚁群不同，人工蚁群系统具有记忆功能，tabuk(k=0,1,…,m)用以记录蚂蚁K当前所走过的城市，集合tabuk 随着进化过程做动态调整。随着时间的推移，以前留下的信息逐渐消逝，用参数1-ρ表示信息消逝程度，经过n个时刻，蚂蚁完成一次循环，各路径上信息量要根据下式进行调整：

τij（t+n）=ρ?τij（t）+（1-ρ）?Δτij

Δτij=∑Δτkij

其中，Δτkij 表示第k只蚂蚁在本次循环中留在路径（i,j）上的信息量，Δτij表示本次循环中路径（i,j）上的信息量的增量。在初始时刻，τij（0）=C（C为常数），Δτij=0

（i ,j =0,1,…,n-1）。ηij 表示从城市i转移到城市j的期望程度，可根据某种启发式算法具体确定。根据具体算法的不同，τij（t），Δτij 及Pkij的表达式可以不同，要视具体问题而定。

基本蚁群算法的主要步骤叙述如下：

步骤1：nc=0（nc为迭代步数或搜索次数），各τij 和Δτij 的初始化，将m个蚂蚁置于n个顶点上；

步骤2：将各蚂蚁的初始出发点置于当前解集中，对蚂蚁k(k=1,…,m),按概率Pkij 移至下一顶点j，将顶点j置于当前解集；

步骤3：计算各蚂蚁的目标函数值Zk (k=1,…,m),记录当前的最好解；

步骤4：按更新方程修改轨迹强度；

步骤5：对各边弧（i , j）,置Δτij =0，nc = nc＋1；

步骤6：若nc

3.2 对基本蚁群算法的改进策略

3.2.1 对选择策略的改进

在蚁群算法中，在蚂蚁搜索过程的起始阶段，有的路径上有蚂蚁走过，有的路径还未来的及被走过，而蚂蚁选路的策略是一旦有路径上的信息素，即信息量多于其他路径，它就以较大的概率选择该路径，这使得蚂蚁从搜索的一开始就以较大的概率集中在几条当前局部长度较短的路径上。为了避免蚂蚁一开始就失去解的多样性，在路径上信息量的刺激量未达到蚂蚁的绝对感觉阈限时，让蚂蚁忽视该刺激物的存在，只有当信息量的刺激趋于阈限为ρ0

时，蚂蚁才在信息量的刺激下趋于信息量较大的路径。这样蚂蚁在初始阶段可选择较多不同路径，以获得多样性的解。

3.2.2 蚁群信息量的全局修正

信息量的全局修正规则如下

τij（t+n）=ρ?τij（t）＋（1-ρ）?Δτij

其中Δτij=Δτkij ，第K只蚂蚁是发现本次循环中最短路径的蚂蚁。

全局修正规则只是让实现最好环游的蚂蚁释放信息素。它和改进的状态转移规则结合的搜索，保证了蚂蚁在优秀父辈完成的环游领域内进行更多搜索，这使得求解速度大大提高。

4 蚁群算法改进的思路和应用前景

由于基本蚁群算法利用随机选择策略，使得进化速度较慢；同时蚁群算法旨在利用正反馈原理和分布式计算的模式，却未能较好地加快进化过程及避免过早收敛，反而容易出现停滞现象。针对蚁群算法加速收敛与早熟、停滞 现象等的矛盾和寻找最优解的时间过长等缺点，可以从以下方向改进蚁群算法。

（1）算法的自适应性。①从选择概率来看，可以采用不同的阶段使用不同的选择概率，在寻路的过程中动态地调整选择概率，并且可以使用选择概率的不同方法。②信息素更新策略的自适应，应该能对信息素进行动态更新和自适应调节。③如果把寻路过程优化为几个不同的阶段，并且在不同阶段采用不同的方法，则应该自适应地分析蚁群个体进行的程度已经到哪个阶段了，选择应该执行什么样的策略等。④蚁群算法的公式中各个参数的自适应选择。

（2）初始解的优化。由于各个路径上的初始信息素是相同的，初始解即第一次选择的路径很可能对整个蚁群的进化过程产生误导，必须提高初始解的质量，尽量扩大在初始阶段可以选择路径的数目，以增加解的多样性。

（3）信息素动态更新策略。信息素的浓度强弱直接关系到蚂蚁个体的寻优过程。如何让信息素动态、自适应地更新，如何通过信息素作用的扩散和信息素种类的增加等方法来达到蚂蚁间的协作，以及如何调整信息素的更新公式，都是非常重要的。

⑷路径选择概率的适应性调整。①应该实现选择概率的自适应；②按照不同的应用，不同的实际环境等合理设计和调整选择概率公式等。

（4）门槛值的设计。定义信息素、选择概率等发挥作用的区间或临界点，把蚁群算法分为不同的阶段，不同的策略来实施等，也辅助了自适应的实现。

（5）蚂蚁的协作。已经有较多研究提到了蚂蚁间的协作，并且有研究者提出要把蚂蚁分成多类，不同的类别实现不同的策略、完成不同的工作，然后再通过蚂蚁间的协作达到更优的策略。正如在真实的蚁群世界中，蚂蚁也是被分了类的，不同类别的蚂蚁完成不同的工作。蚂蚁的协作在一定程度上优化了算法，但也增加了算法的复杂性。

以上是蚁群算法中最重要的改进和优化的主要方向，当然还有蚁群算法中参数的优化，如信息素挥发系数的优化等。

5 结语

蚁群算法的理论研究和实际应用表明，它是一种很有前途的仿生优化算法。随着人类认识的进步和社会发展的加速，仿生智能及最优化系统理论将越来越成为科学认识和工程时间的有力工具，蚁群算法理论及其应用的研究必将是一个长期的研究课题。蚁群算法这一新兴的仿生优化算法必将展现出更加广阔、更加引人注目的发展前景。

参考文献：

[1] M Dorigo,V Maniezzo A, Colomi ColomiA, DorigoM, ManiezzoV. Distributed optimization by ant colonies [A] .proc 1 European conf art ificial Life[C] .Pans,Francer:Elsevier,1991.134- 142.

[2] 熊伟清,余舜杰,赵杰煜.具有分工的蚁群算法及应用[J].模式识别与人工智能,2003,16(3).

[3] M Dorigo,LMG ambardella. Ant Colonies for the Traverling Salesman Problem .BioSystems,1997(43):73-81.

[4] 陈永强,人工蚁群算法及其在组合优化中的应用[D].哈尔滨：哈尔滨工业大学,2003.

[5] 马良,项培军.蚂蚁算法在组合优化中的应用[J].管理科学学报,2001,4(2):32-36.

[6] 候立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用[J].上海交通大学学报,2001,35(6).

收稿日期：2008-03-12