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

　　摘要：基于群集智能的算法研究，近年来受到了广泛的关注。本文讨论了群集智能的两种算法，蚁群智能与微粒群智能。分别阐述了它们的原理、基本算法及其一些改进算法。最后讨论了群集智能算法的一些应用实例以及它们的应用领域和未来的研究方向。
　　关键词：群集智能；蚁群算法；微粒群算法
　　中图分类号：TP311文献标识码：A 文章编号：1009-3044(2007)17-31415-01
　　Study of Algorithm Based on Swarm Intelligence
　　YANG Yuan-hua,SONG Zhong-shan
　　(School of Computer Science, Central South University of Nationalities, Wuhan 43074, China )
　　Abstract:Algorithm based swarm intelligence have gained considerable amount of attention in recent years. In this paper, we review ant colony algorithm and particle swarm optimization. The methodolog- ies of theses algorithm were reviewed and described systematically. Finally, we introduce some applica- tions in the developed areas and discuss the future research issues.
　　Key words:Swarm intelligence; Ant colony algorithm; Particle swarm optimization
　　
　　1 引言
　　
　　自然界中，群居昆虫以集体的力量，进行觅食、御敌、筑巢，如蜜蜂采蜜、筑巢、蚂蚁觅食、筑巢等。这些群居昆虫，它们单个的智能很低、能力微弱，可是一旦形成规模，却可以解决很多复杂的问题。比如白蚁，单个白蚁的智能很低，可是，一旦形成群体，它们建造的蚁巢就是建筑学上的奇观，即使蚁巢不断扩大，也能够保持适宜的环境温度和适当的氧气及二氧化碳含量。实际上，对群居昆虫来说，团队合作主要是通过群居成员之间个体的互动进行协调的。尽管单次互动可能非常简单，但通过多次互动就能解决复杂的问题，我们把群居昆虫的智能行为称作“群集智能”。
　　从本质上说，群居昆虫之所以如此成功，主要是因为它们具备三个特性：灵活性、稳健型和自我组织能力。群居昆虫可以适应随时变化的环境，即使个体失败，整个群体仍然能完成任务。
　　
　　2 群集智能算法
　　
　　人们从群居昆虫相互之间协调合作的工作原理及合作规则中得到启示，提出了基于群集智能的新的算法来解决现实生活中的一些复杂问题。目前，在计算智能领域有两种基于群集智能的算法：蚁群算法和微粒群算法。蚁群算法是由意大利学者M.Dorigo等人首先提出的，是一种新型的模拟进化算法,初步的研究已经表明该算法具有许多优良的性质。目前国内对蚁群算法的研究主要针对离散优化问题，如基于蚁群算法进行动态路由表设计，求最短路径等。对于连续空间优化问题的研究是近来研究的一个新方向。微粒群算法是1995年由Kennedy和Ebrhart 率先提出的，是一种有别于遗传算法的并行进化计算技术。近几年的发展中，微粒群算法已广泛应用于函数优化、人工神经网络训练、模糊控制等领域，成为目前进化计算研究的一个新热点。
　　
　　3 蚁群算法
　　
　　3.1 蚁群算法的基本原理
　　蚁群算法是人们通过对自然界中蚁群群体行为的研究而提出的一种基于种群的模拟进化算法。该算法通过模拟蚂蚁搜索食物的过程来求解一些实际问题。蚂蚁能够在没有任何可见的提示下找出蚁穴到食物源的最短路径，并且能随着环境的变化而变化的搜索新的路径，产生新的选择。
　　但是，蚁群是如何完成这些复杂的任务的呢？人们发现蚂蚁在从食物源返回洞穴的途中会分泌一种信息素（Pheromone，也称外激素）,这种物质会随着时间的变化而挥发。蚂蚁在运动中倾向于朝着信息素浓度高的方向移动。假设蚂蚁从洞穴出发搜寻食物，洞穴与食物之间有n条路经。最初，所有路径上都没有信息素，蚂蚁选择每条路径的概率是相同的，当找到食物后蚂蚁返回洞穴并在回来的路上留下信息素。由于越短的路径需要的时间越短，因此在短的路径上残留的信息素浓度就高，就会有越多的蚂蚁选择这条路径。假设我们把信息素的寿命用时间尺度来测量，当使用适当的时间尺度时，信息素的挥发可以使蚁群避免陷于选择次优路径。
　　3.2基本蚁群算法
　　我们以旅行商问题为例，给出基本蚁群算法。旅行商问题是指，给定n个城市和每两个城市之间的距离，要求确定一条经过每个城市一次且只有一次的最短路径。我们引入如下记号来描述蚁群算法。
　　设： ｍ――蚂蚁的规模；
　　 初始时刻，所有路径上的τij均为一个相同的常数。运动过程中，蚂蚁根据各条路径上信息素的浓度决定移动方向。蚂蚁k从城市i移动到城市j的概率用下式得出。
　　算公式也会不同。针对实际问题，研究者们在基本蚁群算法的基础上提出一些改进算法。如：M.Dorigo等人提出了称之为Ant-Q的蚁群算法,是蚁群系统（Ant System，AS）和Q学习机制的耦合算法；Bullnheimer等人提出了AS算法的另一个改进算法,采用类似于Max-Min 蚁群系统(MMAS)的信息素贡献机制,在新算法中蚂蚁是按比例在经过的路径上释放信息素,同样最佳路径上的信息素亦按照比例进行更新。在各种新的算法被不断提出的同时，针对算法本身的研究也取得了很大的进展。如：H.M.Botee等人对算法的参数选择进行研究后，用遗传算法求得了参数的最优组合；Amrbadr等人给出了蚁群算法收敛性的证明。
　　3.3蚁群算法的实际应用
　　蚁群算法在现实问题中的应用很广泛。目前，主要的应用集中在网络上，如路由器路由选择、网络传输中内容的组织、网络的协议优化等。实践表明，在网络方面使用蚁群算法，无论在数据流量最大化方面还是在延迟最小化方面，都优于目前其它的算法。
　　
　　4 微粒群算法（particle swarm optimization , PSO）
　　
　　4.1 PSO的基本原理
　　PSO起源于对简单社会系统的模拟，人们通过对鸟类的研究发现，鸟在运动过程中会通过参考同伴的运动信息来调整自己的运动状态。在运动中，每个个体的信息都是共享的，正是通过这种相互借鉴可以使个体运动达到最优状态。
　　在PSO算法中，我们把鸟群中的鸟称为微粒，鸟群飞行的空间可以看成是一个n维空间。每个微粒都有一个由目标函数决定的适应度和相应的位置与速度。所有的微粒在空间中以一定的速度飞行，通过追随当前搜索到的最优适应度来寻找全局的最优值。
　　4.2 基本PSO
　　Step 2：计算每个微粒的适应度。
　　Step 3：对每个微粒，把当前适应度与Pbest比较，如果优于Pbest，则将其记为Pbest。
　　Step 4：对每个微粒，把当前适应度与gbest 比较，如果优于gbest，则将其记为gbest。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　Step 5：根据式(1),(2)变化微粒的速度与位置。
　　Step 6：如果未达到结束条件（常为足够好的适应值或达到一个预设的值），则返回Step 2。
　　PSO在迭代早期性能优异，但在有些实际优化问题中当逼近最优解时性能较差。针对PSO的不足，研究者们提出了新的改进算法。如：杂交的PSO（HS），组合了进化计算与PSO的思想,此方法加入选择后具有更强的搜索能力；基于邻域算子的PSO，邻域算子能改进PSO性能，保持微粒群的多样性，避免过早收敛；基于不同收缩方向的PSO能进行多目标搜索，避免微粒陷入局部最优。
　　4.3 PSO的应用
　　PSO已得到了广泛的应用。它最直接的应用是关于多元函数的优化问题，包括带约束的优化问题。如果所讨论的函数受到严重的噪音干扰而呈现不规则的形状，同时所求得不一定是精确的最优值，PSO都能得到很好的应用。在演化人工神经网络中PSO也得到了更为广泛的应用。另外PSO还可用于动态问题中，如多目标优化、分类、模式识别、信号处理、机器人技术应用、决策制定、模拟和证明等。
　　
　　5 结论
　　
　　本文对群集智能的算法和基本概念进行了说明。群集智能算法，在实际问题的解决中为人们提供了新的思路，并已得到了广泛的应用。但是，有关群集智能的研究仍缺乏完整的理论，数学基础也相对薄弱，需要进行更进一步的深入研究。目前，我国对于群集智能算法的研究和应用都很少，我们还要加强这一领域的研究，以促进我国科技的进一步发展。
　　参考文献：
　　[1]Kennedy j, Eberhart R C, Shi Y. Swarm IntelligenceMarco Dorigo, Vittorio Maniezzo, Alberto Colorni. The ant system: Optimization by a colony of co- operating agents Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies李志伟. 基于群集智能的蚁群优化算法研究L. M. Gambardella and M. Dorigo. Ant-Q: A reinforcement learning approach to the traveling sales- man problemClerc M, Kennedy J. The Particle Swarm Explosion, Stability, and Convergence in a
　　Multidimensio- nal Complex Space谢晓峰，张文君，杨之廉. 微粒群算法综述[J].控制与决策，2003，18(2): 129.
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文