现代智能优化算法课程群智能优化算法综述学生姓名:学号:班级:2014年6月22日摘要工程技术与科学研究中的最优化求解问题十分普遍,在求解过程中,人们创造与发现了许多优秀实用的算法。
群智能算法是一种新兴的演化计算技术,已成为越来越多研究者的关注焦点,智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。
群智能优化是智能优化的一个重要分支,它与人工生命,特别是进化策略以及遗传算法有着极为特殊的联系。
群智能优化通过模拟社会性昆虫的各种群体行为,利用群体中个体之间的信息交互和合作实现寻优。
本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。
关键词:群智能;最优化;算法目录摘要 (1)1 概述 (3)2 定义及原理 (3)2.1 定义 (3)2.2 群集智能算法原理 (4)3 主要群智能算法 (4)3.1 蚁群算法 (4)3.2 粒子群算法 (5)3.3 其他算法 (6)4 应用研究 (7)5 发展前景 (7)6 总结 (8)参考文献 (9)1 概述优化是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。
很多实际优化问题往往存 在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。
因此设计高效的优化算法成为众多科研工作者的研究目标。
随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。
这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。
基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。
目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 和粒子群优化算法(ParticleSwarm Optimization, PSO)。
2 定义及原理2.1 定义群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。
它将搜索和优化过程模拟成个体的进化或觅食过程,用搜索空间中的点模拟自然界中的个体;将求解问题的目标函数度量成个体对环境的适应能力;将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。
从而,形成了一种以“生成+检验”特征的迭代搜索算法,是一种求解极值问题的自适应人工智能技术。
各类优化算法实质上都是建立问题的目标函数,求目标函数的最优解,因而实际工程优化问题均可转化为函数优化问题。
其表达形式如下:求:,,2,1,0)(..),(min ,,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤==。
Ω∈X其中,i X 为设计变量;)(X f 为被优化的目标函数;0)(≤X g j 为约束函数;Ω为设计变量的可行域。
2.2 群集智能算法原理自然界中一些生物的行为特征呈现群体的特征,可以用简单的几条规则将这种群体行为在计算机中建模,Reynolds认为动物以群落形式生存觅食时一般遵循三个规则1)分隔规则:尽量避免与临近伙伴过于拥挤;2)对准规则:尽量与临近伙伴的平均方向一致,向目的运动;3)内聚规则:尽量朝临近伙伴的中心移动。
以上规则可归纳为个体信息和群体信息两类信息,前者对应于分隔规则,即个体根据自身当前状态进行决策;后者对应于对准规则和内聚规则,即个体根据群体信息进行决策。
另外,由于动物行为一般具有适应性、盲目性、自治性、突现性以及并行性等特征。
因此自组织性、突现性成为群集智能优化算法的两大基本特征。
群集智能优化算法通过Reynolds模型模拟了整个群体的运动,使得算法的迭代搜索过程成为一个不断地利用个体极值和群体极值来修正自身进行寻优搜索的过程,实现了个体与群体的信息交互与相互协作。
个体极值具有一定的随机性,在一定的程度上保持了搜索方向的多样性,避免了过早地收敛而陷于局部最优;群体极值从整体上把握了寻优的方向,从而保证算法的收敛性。
3 主要群智能算法3.1 蚁群算法蚁群算法蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来寻找最优解决方案的机率型技术。
它由Marco Dorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。
其选择一条路径的概率与该路径上分泌物的强度成正比。
因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大。
蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。
蚁群算法就是根据这一特点,通过模仿蚂蚁的行为,从而实现寻优。
这种算法有别于传统编程模式,其优势在于,避免了冗长的编程和筹划,程序本身是基于一定规则的随机运行来寻找最佳配置。
也就是说,当程序最开始找到目标的时候,路径几乎不可能是最优的,甚至可能是包含了无数错误的选择而极度冗长的。
但是,程序可以通过蚂蚁寻找食物的时候的信息素原理,不断地去修正原来的路线,使整个路线越来越短,也就是说,程序执行的时间越长,所获得的路径就越可能接近最优路径。
这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。
实际上好似是程序的一个自我学习的过程。
自蚁群算法提出以来,引起了国内外研究人员的极大兴趣,对该算法进行了广泛的研究,取得了丰富的成果。
研究表明,蚁群算法是一种高效的启发式随机搜索算法,具有如下优点:1.正反馈性:由自然蚂蚁搜索食物原理可知,信息素的积累是一个正反馈的过程。
单个蚂蚁之间通过信息素进行交流,若某路径上的信息素浓度更高,将吸引更多的蚂蚁沿着这条路径运动,这又使得其信息素浓度增加。
2.自组织性强:算法初期,单个的人工蚂蚁无序地寻找解,经过一段时间的搜索,通过信息素的作用,蚂蚁自发地越来越趋向于寻找到接近最优解的一些解,是个从无序到有序的过程。
3.鲁棒性强:该算法具有很好的适应性,且不局限于具体问题,只要稍加修改就可以应用到其它领域。
4.并行性强:蚁群在问题的解空间中多点同时开始进行独立的搜索,具有本质并行性。
5.结合性强:蚁群算法易于与其他优化算法相结合,吸取其他算法得优点,以改善算法的性能。
但由于基本蚁群算法进化收敛速度慢,且易陷入局部最优或者出现停滞现象等缺陷,国内外学者开展了大量有意义的研究。
研究成果主要涉及路径搜索策略、信息素更新策略和最优解保留策略等方面;研究行为主要是进行算法改进或验证。
有些改进算法的性能相比基本蚁群算法而言有了较大水平的提高,如最大最小蚁群算法是目前求解TSP 问题的最好方法之一;有些已成为主流的蚁群算法。
3.2 粒子群算法粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。
CAS理论于1994年正式提出,CAS中的成员称为主体。
比如研究鸟群系统,每个鸟在这个系统中就称为主体。
主体有适应性,它能够与环境及其他的主体进行交流,并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。
整个系统的演变或进化包括:新层次的产生(小鸟的出生);分化和多样性的出现(鸟群中的鸟分成许多小的群);新的主题的出现(鸟寻找食物过程中,不断发现新的食物)。
所以CAS系统中的主体具有4个基本特点(这些特点是粒子群算法发展变化的依据):首先,主体是主动的、活动的。
主体与环境及其他主体是相互影响、相互作用的,这种影响是系统发展变化的主要动力。
环境的影响是宏观的,主体之间的影响是微观的,宏观与微观要有机结合。
最后,整个系统可能还要受一些随机因素的影响。
粒子群算法就是对一个CAS系统——鸟群社会系统的研究得出的。
粒子群算法(Particle Swarm Optimization, PSO)最早是由Eberhart和Kennedy于1995年提出,它的基本概念源于对鸟群觅食行为的研究。
设想这样一个场景:一群鸟在随机搜寻食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是它们知道当前的位置离食物还有多远。
那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。
在PSO中,每个优化问题的潜在解都可以想象成d维搜索空间上的一个点,我们称之为“粒子”(Particle),所有的粒子都有一个被目标函数决定的适应值(Fitness Value ),每个粒子还有一个速度决定他们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。
Reynolds对鸟群飞行的研究发现。
鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。
3.3 其他算法●人工鱼群算法(Artificial Fish Swarm Algorithm,简称AFSA)是受鱼群行为的启发,由国内李晓磊博士于2002 年提出的一种基于动物行为的群体智能优化算法,是行为主义人工智能的一个典型应用,这种算法源于鱼群的觅食行为。
●蛙跳算法(SFLA)是一种全新的后启发式群体进化算法,具有高效的计算性能和优良的全局搜索能力。
对混合蛙跳算法的基本原理进行了阐述,针对算法局部更新策略引起的更新操作前后个体空间位置变化较大,降低收敛速度这一问题,提出了一种基于阈值选择策略的改进蛙跳算法。
通过不满足阈值条件的个体分量不予更新的策略,减小了个体空间差异,从而改善了算法的性能。
数值实验证明了该改进算法的有效性,并对改进算法的阈值参数进行了率定。
4 应用研究随着群智能算法研究的不断发展,研究者已尝试着将其应用于各种工程优化问题,并取得了意想不到的收获。
多种研究表明,群智能算法在离散和连续求解空间中均表现出良好的搜索效果,更在组合优化问题中有突出表现。
蚁群算法最初用于解决旅行商问题。
自从在著名的旅行商问题(TSP)和工件排序问题上取得成效以来,已经陆续渗透到其它领域中,如图着色问题、二次分配问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题、数据聚类问题、武器攻击目标分配和优化问题、区域性无线电频率自动分配问题等。
粒子群算法最早应用于训练人工神经网络,Kennedy 和Eberhart 成功地将算法应用于分类XOR 问题的神经网络训练。
随后,微粒群算法被广泛地应用于函数优化、约束优化、模式分类、参数优化、组合优化、模糊系统控制、机器人路径规划、信号处理、模式识别、TSP、车间调度等工程领域。