智能优化算法综述

NanjingUniversityofScienceandTechnology智能优化算法的统一框架指导老师：叶晓东教授姓名：李进阳学号：110040692班级：电磁场与微波技术5班2011年6月20日NanjingUniversityofScienceandTechnology2目录1概述..............................................................32群体智能优化算法..................................错误!未定义书签。2.1人工鱼群算法................................................42.2蚁群算法....................................................52.3混合蛙跳算法................................................93神经网络算法.....................................................103.1神经网络知识点概述.........................................103.2神经网络在计算机中的应用...................................114模拟退火算法.....................................................155遗传算法..........................................错误!未定义书签。5.1遗传算法知识简介...........................................175.2遗传算法现状...............................................185.3遗传算法定义...............................................195.4遗传算法特点和应用.........................................205.5遗传算法的一般算法.........................................215.6遗传算法的基本框架.........................................266总结.............................................................287感谢.............................................................29NanjingUniversityofScienceandTechnology31概述近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。智能优化算法就是在这种背景下产生并经实践证明特别有效的算法。2群体智能优化算法自然界中群体生活的昆虫、动物,大都表现出惊人的完成复杂行为的能力。人们从中得到启发,参考群体生活的昆虫、动物的社会行为,提出了模拟生物系统中群体生活习性的群体智能优化算法。在群体智能优化算法中每一个个体都是具有经验和智慧的智能体(Agent),个体之间存在互相作用机制,通过相互作用形成强大的群体智慧来解决复杂的问题。自20世纪90年代模拟蚂蚁行为的蚁群算法(ACO)提出以来,又产生了模拟鸟类行为的微粒群算法(PSO)、模拟鱼类生存习性的人工鱼群算法、模拟青蛙觅食的混合蛙跳算法(SFLA)等。这些群体智能优化算法的出现,使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点:①群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性;②每个个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、方便;③系统用于通信的开销较少,易于扩充;④自NanjingUniversityofScienceandTechnology4组织性,即群体表现出来的复杂行为是通过简单个体的交互表现出高度的智能。本文部分内容，在群体智能优化算法范围内分别详细讨论了人工鱼群算法、蚁群算法、混合蛙跳算法等三种智能优化方法。2.1人工鱼群算法在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。在这种群体活动中,没有统一的协调者,而是通过鱼类每个个体的自适应行为而达到目的。模拟鱼类生活觅食的特性,李晓磊等人于2002年提出人工鱼群算法(AFSA)。在此算法中,人工鱼的活动被描述为三种典型行为:①觅食行为:这是鱼的基本行为,当发现附近有食物时,会向该方向游动;②追尾行为:当某条鱼发现该处食物丰富时,其它鱼会快速尾随而至:③聚群行为:它们往往能形成非常庞大的群。人工鱼所处的状态可以用矢量描述:X=(x1,x2,…,xn),xi(i=1,2,…,n)是所要优化问题的变量。Y=f(X)为人工鱼的食物密度,表示所要优化的目标函数。di,j=‖Xi-Xj‖为两条人工鱼之间的距离,人工鱼的感知距离定义为Visual距离。在人工鱼群算法中定义拥挤因子表示人工鱼所处环境的拥挤程度,人工鱼在食物较多而又不拥挤的环境下捕食,当环境过分拥挤时它就会离开这个环境,游往别处。人工鱼群算法觅食行为如下:Step1:设置最大尝试次数;Step2:人工鱼从一个状态转移到另一个状态:Xj=Xi+Random(Visual);Step3:如果适应值YiYj,则Xi|next=Xi+Random(Step)Xj-Xi‖Xj-Xi‖;否则,Xi|next=Xi+Random(Step);Step4:检查终止条件,如果条件满足结束迭带,否则转Step2。对于人工鱼的追尾行为:由状态Xi转移到状态Xj能获得更好的适应值Yj,人工鱼就向状态Xj移动一步。否则,就转入觅食行为。人工鱼的聚群行为,当人工鱼探测到所感知的范围内具有较多食物又不拥挤时,人工鱼就向伙伴的中心移动,否则,转向觅食行为。在人工鱼群算法中设置一个公告板,用于记录最优人工鱼个体的状态,当人工鱼自身状态优于最优状态就替代之。算法具有良好的求取NanjingUniversityofScienceandTechnology5全局极值能力,并具有对初值、参数选择不敏感、鲁棒性强、简单易实现等诸多优点,但是当问题规模过大时求解困难并且求解初期收敛较快,后期较慢。人工鱼群算法的改进研究,如在算法中增加鱼群的协调行为,将人工鱼群算法与模拟退火算法相融和的混合智能算法等。人工鱼群算法目前已用于组合优化、参数估计、PID控制器的参数整定、神经网络优化等。2.2蚁群算法蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚂蚁是一类社会性很强的生物,它们群体生活、共同觅食。在觅食过程中每只蚂蚁单独行动,蚂蚁之间通过信息素的释放来对觅食的轨迹进行“记忆”,一旦某一条轨迹发现了食物,那么其它蚂蚁就会向这条道路进行聚集,这条道路上的信息素的量就会增多。如果在觅食的过程中,蚂蚁发现不同路径的距离有远、近的区别,则蚂蚁就会选择最近的路径进行觅食,并把这一情况通过路径上信息素量的大小通知给其它蚂蚁。受到蚂蚁觅食现象的启发,Colorni、Dorigo等于1991年首次提出了蚁群算法,并用这一算法解决了一系列组合优化问题。基本蚁群算法的求解过程:Step1:设置参数,初始化信息素轨迹;Step2:生成m个可行解(蚂蚁);Step3:对每一个蚂蚁个体,计算其适应度;Step4:确定每一只蚂蚁的最优位置(最优解);Step5:确定全局的最优位置(最优解);Step6:更新信息素轨迹;Step7:判断终止条件是否满足,若满足则终止迭代,否则返回Step3。在蚁群算法中,蚂蚁通过行走在不同的地点(状态)之间转移,t时刻蚂蚁kNanjingUniversityofScienceandTechnology6在点i向点j的转移概率Pkij(t)为:式中:ηij—边(i,j)的能见度,反映由点i转移到点j的启发程度,这个量在蚂蚁系统的运行中不改变;τij—边(i,j)上的信息素轨迹强度;Pkij—蚂蚁k的转移概率,j是尚未访问的点;allowedk—蚂蚁k下一步允许选择的点,allowed={0,1,…,n-1};r—蚂蚁可以到达的位置。由式(1)可知,转移概率Pij(t)与τij·ηij成正比。α和β为两个参数,分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。经过n时刻,蚂蚁完成一次循环,各路径上信息素量根据下式调整:式中:Δτij(t,t+1)———第k只蚂蚁在时刻(t,t+1)留在路径(i,j)上的信息素量,其值大小视蚂蚁表现的优劣而定。路径越短信息素释放就越多;Δτij(t,t+1)———本次循环中路径(i,j)的信息素的增量;ρ———信息素挥发系数,通常设置ρ1来避免路径上轨迹量的无限累加。通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：1、多样性2、正反馈多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就NanjingUniversityofScienceandTechnology7是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是