群集智能算法研究现状及进展

群集智能算法研究现状及进展3王　果1,2,戴　冬1(1.中南民族大学计算机科学学院,湖北武汉430074;2.河南机电高等专科学校试验管理中心,河南新乡453002)摘要:基于群集智能的算法研究,近年来受到了广泛的关注。

文中重点讨论了群集智能的两种算法,蚁群智能与微粒群智能,并分别阐述了它们的原理、基本算法及其一些改进算法。

最后讨论了群集智能算法的一些应用实例以及它们的应用领域和未来的研究方向。

关键词:群集智能;蚁群算法;微粒群算法中图分类号:TP391.9 文献标识码:A 文章编号:100822093(2007)022*******1　引言自然界中,群居昆虫以集体的力量,进行觅食、御敌、筑巢,如蜜蜂采蜜、筑巢、蚂蚁觅食、筑巢等。

这些群居昆虫,它们单个的智能很低、能力微弱,可是一旦形成规模,却可以解决很多复杂的问题。

比如白蚁,单个白蚁的智能很低,可是,一旦形成群体,它们建造的蚁巢就是建筑学上的奇观,即使蚁巢不断扩大,也能够保持适宜的环境温度和适当的氧气及二氧化碳含量。

实际上,对群居昆虫来说,团队合作主要是通过群居成员之间个体的互动进行协调的。

尽管单次互动可能非常简单,但通过多次互动就能解决复杂的问题,我们把群居昆虫的这种智能行为称作“群集智能”。

从本质上说,群居昆虫之所以如此成功,主要是因为它们具备三个特性:灵活性、稳健型和自我组织能力。

群居昆虫可以适应随时变化的环境,即使个体失败,整个群体仍然能完成任务。

2　群集智能算法人们从群居昆虫相互之间协调合作的工作原理及合作规则中得到启示,提出了基于群集智能的新的算法来解决现实生活中的一些复杂问题。

目前,在计算智能领域有两种基于群集智能的算法:蚁群算法和微粒群算法[1]。

蚁群算法是由意大利学者Dorigo和Maniezzo 等人首先提出的,是一种新型的模拟进化算法,初步的研究已经表明该算法具有许多优良的性质。

目前国内对蚁群算法的研究主要针对离散优化问题,如基于蚁群算法进行动态路由表设计,求最短路径等。

对于连续空间优化问题的研究是近来研究的一个新方向。

微粒群算法是1995年由美国学者K ennedy和Ebrhart率先提出的,是一种有别于遗传算法的并行进化计算技术。

近几年的发展中,微粒群算法已广泛应用于函数优化、人工神经网络训练、模糊控制等领域,成为目前进化计算研究的一个新热点。

3　蚁群算法3.1　蚁群算法的基本原理蚁群算法是人们通过对自然界中蚁群群体行为的研究而提出的一种基于种群的模拟进化算法[2]。

该算法通过模拟蚂蚁搜索食物的过程来求解一些实际问题。

蚂蚁能够在没有任何可见提示下找出蚁穴到食物源的最短路径,并且能随着环境的变化而变化,然后搜索新的路径,产生新的选择。

但是,蚁群是如何完成这些复杂的任务的呢?人们发现蚂蚁在从食物源返回洞穴的途中会分泌一种信息素(Pheromone,也称外激素),这种物质会随着时间的变化而挥发。

蚂蚁在运动中倾向于朝着信息素浓度高的方向移动。

假设蚂蚁从洞穴出发搜寻食物,洞穴与食物之间有v条路经。

最初,所有路径上都没有信息素,蚂蚁选择每条路径的概率是相同的,当找到食物后蚂蚁返回洞穴并在回来的路上留下信息素。

由于越短的路径需要的时间越短,因此在短的路径上残留的信息素浓度就高,就会有更多的蚂蚁选择这条路径。

假设我们把信息素的寿命用时间尺度来测量,当使用适当的时间尺度时,信息素的挥发可以使蚁群避免陷于选择次优路径[3][4]。

3.2　基本蚁群算法我们以旅行商问题为例,给出基本蚁群算法。

旅601第15卷第2期　2007年03月河南机电高等专科学校学报Journal of Henan Mechanical and Electrical Engineering College Vol.15№.2Mar.20073收稿日期:2006212220作者简介:王果(19772),男,河南南阳人,硕士研究生,主要从事图形图像处理研究。

行商问题是指,给定n个城市和每两个城市之间的距离,要求确定一条经过每个城市一次且只有一次的最短路径。

我们引入如下记号来描述蚁群算法。

设:m———蚂蚁的规模;　ηij———经验知识或能见度;　τij———城市i与城市j之间路径上的信息素浓度;　Δτij———蚂蚁本次遍历中信息素浓度的增量;　P k ij(t)———表示在t时刻蚂蚁k从城市i移动到城市j的概率,j是此次遍历中还未访问的城市。

初始时刻,所有路径上的τij均为一个相同的常数。

运动过程中,蚂蚁根据各条路径上信息素的浓度决定移动方向。

蚂蚁k从城市i移动到城市j的概率用下式得出。

P k ij(t)=Iτij(t)Iα(ηij)βΣj:allowed kIτij(t)Iα(ηij)β0α,β为蚂蚁在运动过程中所积累的τij和ηij在蚂蚁选择路径中的相对重要性,allow ed k为蚂蚁还未访问过的城市集合。

当蚂蚁遍历完所有城市以后,我们,接着进行下一次遍历,这时各路径上的信息素浓度将作如下调整。

τij(t+1)=(1-ρ)τij(t)+Δτij(1-ρ)为信息素的衰减系数,我们设置0<ρ<1来避免路径上信息素的无限增加。

在实际的应用中,根据具体的算法不同,Δτij(t,t +1),P k ij的计算公式也会不同。

针对实际问题,研究者们在基本蚁群算法的基础上提出一些改进算法。

如:Dorigo等人提出了被称为Ant-Q的蚁群算法[5],是蚁群系统(Ant System,AS)和Q学习机制的耦合算法;Bullnheimer等人提出了AS算法的另一个改进算法,采用类似于Max-Min蚁群系统(MMAS)的信息素贡献机制,在新算法中蚂蚁是按比例在经过的路径上释放信息素,同样最佳路径上的信息素亦按照比例进行更新。

在各种新的算法被不断提出的同时,针对算法本身的研究也取得了很大的进展。

如: H.M.Botee等人对算法的参数选择进行研究后,用遗传算法求得了参数的最优组合;Amrbadr等人给出了蚁群算法收敛性的证明。

4　微粒群算法4.1　PSO的基本原理PSO(particle swarm optimization,PSO)起源于对简单社会系统的模拟,人们通过对鸟类的研究发现,鸟在运动过程中会通过参考同伴的运动信息来调整自己的运动状态。

在运动中,每个个体的信息都是共享的,正是通过这种相互借鉴可以使个体运动达到最优状态。

在PSO算法中,我们把鸟群中的鸟称为微粒,鸟群飞行的空间可以看成是一个n维空间。

每个微粒都有一个由目标函数决定的适应度和相应的位置与速度。

所有的微粒在空间中以一定的速度飞行,通过追随当前搜索到的最优适应度来寻找全局的最优值。

4.2　基本PSO假设目标搜索空间是一个n维空间,空间中有m 个微粒。

微粒以一定的速度在空间中飞行,我们把每个微粒在空间中的位置看作是一个可能的解。

第i个微粒的位置我们表示为L i=(l i1,l i2,I i3,∧,l in),飞行速度用向量V i=(νi1,νi2,νi3,∧,νin)来表示。

微粒通过适应度函数f(x),x:L i(不同的问题,适应度函数不同)来评价当前位置,并将自己已经飞行过的有最优适应度的位置(最优位置)记为P i=(p i1,p i2,p i3,∧, p in),也称为个体极值P b est。

整个群体中所有微粒的最优位置用P g=(p g1,p g2,p g3,∧,p gn)来表示,称为g b est。

每一次迭代,第j维(1ΦjΦn)的速度及位置,根据下式变化: νij=wνij+c1r1(p ij-l ij)+c2r2(p gj-l ij)(1)l ij=l ij+νij(2)其中,w为惯性权重,它表示微粒保持运动惯性的程度。

c1,c2为两个加速常数,表示将微粒推向P b est 和g b est的加速权重。

r1,r2为范围在[0,1]之间的两个随机数。

为避免微粒飞出可行解的范围,微粒的速度V i被一个最大速度V max限制,当超出这个速度时,则把V max记作V i。

PSO的基本算法流程如下[6]:Step1:初始化一群微粒,即为每个微粒i初始化L i,V i,P b est,并初始化g b est。

群体的规模为m。

Step2:计算每个微粒的适应度。

Step3:对每个微粒,把当前适应度与P b est比较,如果优于P b est,则将其记为P b est。

再用P b est与g b est比较,如果优于g b est,则将其记为g b est。

Step4:根据式(1),(2)变化微粒的速度与位置。

Step5:如果未达到结束条件(常为足够好的适应值或达到一个预设的值),则返回Step2。

PSO在迭代早期性能优异,但在有些实际优化问题中当逼近最优解时性能较差。

针对PSO的不足,研究者们提出了新的改进算法。

如:杂交的PSO (HS),组合了进化计算与PSO的思想,此方法加入选701王果等:群集智能算法研究现状及进展择后具有更强的搜索能力;基于邻域算子的PSO,邻域算子能改进PSO性能,保持微粒群的多样性,避免过早收敛;基于不同收缩方向的PSO能进行多目标搜索,避免微粒陷入局部最优。

5　群集智能算法的特点及应用群体智能算法中相互合作的个体都是分布式的,没有中心控制,并且单个个体的智能很低,因此算法简单。

另外群集智能系统具有鲁棒性,因此不会因个体故障而影响整体求解,从而使系统具有良好的扩充性。

两种群集智能算法在现实中的应用都很广泛。

蚁群算法主要的应用集中在网络上,如路由器路由选择、网络传输中内容的组织、网络的协议优化等。

实践表明,在网络方面使用蚁群算法,无论在数据流量最大化方面还是在延迟最小化方面,都优于目前其他的算法。

对于PSO来说,它最直接的应用是关于多元函数的优化问题,包括带约束的优化问题。

在演化人工神经网络中PSO也得到了更为广泛的应用[7]。

另外PSO还可用于动态问题中,如多目标优化、分类、模式识别、信号处理、机器人技术应用、决策制定、模拟和证明等。

6　结论群集智能算法在实际问题的解决中为人们提供了新的思路,并已得到了广泛的应用。

群集智能的研究代表了今后计算机研究发展的一个重要方向,但是目前有关群集智能的研究仍缺乏完整的理论,数学基础也相对薄弱,需要进行更进一步的深入研究。

我国对于群集智能算法的研究和应用都很少,我们还要加强这一领域的研究,以促进我国科技的进一步发展。

(责任编辑　吕春红)参考文献:[1]Kennedy j,Eberhart R C,Shi Y.Swarm Intelligence[M].SanFrancisco:Morgan Kauf mann Publishers,2001.[2]Marco Dorigo,Vittorio Maniezzo,Alberto Colorni.The ant sys2tem:Optimization by a colony of co-operating agent s[J].IEEE Transaction on Systems,1996,26(1):1-2.[3]Colorni A,Dorigo M,Maniezzo V.Distributed Optimization byAnt Colonies[C].Proceeding Of The First European Conference Artificial Life[M].Paris:Elsevier Publishing,1991:134-142. [4]李志伟.基于群集智能的蚁群优化算法研究[J].计算机工程与设计,2003,24(8):27-29.[5]L.M.Gambardella,M.Dorigo.Ant-Q:A reinforcement learn2ing approach to t he traveling sales-man problem[J].In Proceed2 ings of t he Twelft h International Conference on Machine Learning, ML-95.Palo Alto,CA:Morgan Kauf mann,1995,252-260. [6]Clerc M,Kennedy J.The Particle Swarm Explosion,Stability,and Convergence in a Multidimensio-nal Complex Space[J].IEEE Trans.On Evolutionary Computation,2002,6(1):58. [7]谢晓峰,张文君,杨之廉.微粒群算法综述[J].控制与决策,2003,18(2):129.R esearch and Development ofAlgorithm B ased on Sw arm IntelligenceWAN G Guo,et al(Moden Technology Center,Henan Mechanical and Elect rical Engineering College,Xinxiang453002,China) Abstract:Algorit hm based swarm intelligence have gained considerable amount of attention in recent years.In t his paper,we review ant colony algorit hm and particle swarm optimization.The met hodologies of t heses algorit hm were reviewed and described systematically.Finally,we int roduce some applications in t he developed areas and discuss t he f ut ure research issues.K ey w ords:Swarm intelligence;Ant colony algorit hm;Particle swarm optimization801河南机电高等专科学校学报 2007年2期。