智能优化算法综述(共29页).doc

《智能优化算法综述(共29页).doc》由会员分享，可在线阅读，更多相关《智能优化算法综述(共29页).doc（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上智能优化算法的统一框架指导老师：叶晓东教授姓名：李进阳学号：班级：电磁场与微波技术5班 2011年6月20日目录4模拟退火算法15 1概述 近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜

2、索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。智能优化算法就是在这种背景下产生并经实践证明特别有效的算法。2群体智能优化算法 自然界中群体生活的昆虫、动物,大都表现出惊人的完成复杂行为的能力。人们从中得到启发,参考群体生活的昆虫、 动物的社会行为,提出了模拟生物系统中群体生活习性的群体智能优化算法。在群体智能优化算法中每一个个体都是具有经验和智慧的智能体 (Agent) ,个体之间存在互相作用机制,通过相互作用形成强大的群体智慧来解决复杂的问题。自 20世纪 90年代模拟蚂蚁行为的蚁群

3、算法(ACO)提出以来,又产生了模拟鸟类行为的微粒群算法 ( PSO)、 模拟鱼类生存习性的人工鱼群算法、 模拟青蛙觅食的混合蛙跳算法 ( SFLA)等。这些群体智能优化算法的出现,使原来一些复杂的、难于用常规的优化算法进行处理的问题可以得到解决,大大增强了人们解决和处理优化问题的能力,这些算法不断地用于解决工程实际中的问题,使得人们投入更大的精力对其理论和实际应用进行研究。群体智能优化算法本质上是一种概率搜索,它不需要问题的梯度信息具有以下不同于传统优化算法的特点: 群体中相互作用的个体是分布式的,不存在直接的中心控制,不会因为个别个体出现故障而影响群体对问题的求解,具有较强的鲁棒性; 每个

4、个体只能感知局部信息,个体的能力或遵循规则非常简单,所以群体智能的实现简单、 方便; 系统用于通信的开销较少,易于扩充; 自组织性,即群体表现出来的复杂行为是通过简单个体的交互表现出高度的智能。 本文部分内容，在群体智能优化算法范围内分别详细讨论了人工鱼群算法、蚁群算法、混合蛙跳算法等三种智能优化方法。2.1人工鱼群算法 在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。在这种群体活动中,没有统一的协调者,而是通过鱼类每个个体的自适应行为而达到目的。模拟鱼类生活觅食的特性,李晓磊等人于2002年提出人工鱼群算法 (AFSA)。在此算法中,人工鱼的活动被描述为三种典型行为: 觅食行为:

5、这是鱼的基本行为,当发现附近有食物时,会向该方向游动; 追尾行为:当某条鱼发现该处食物丰富时,其它鱼会快速尾随而至: 聚群行为:它们往往能形成非常庞大的群。 人工鱼所处的状态可以用矢量描述: X = ( x1 ,x2 , , xn ) , xi( i = 1, 2, , n) 是所要优化问题的变量。Y = f (X) 为人工鱼的食物密度,表示所要优化的目标函数。di , j= Xi- Xj为两条人工鱼之间的距离,人工鱼的感知距离定义为 V isua l距离。在人工鱼群算法中定义拥挤因子表示人工鱼所处环境的拥挤程度,人工鱼在食物较多而又不拥挤的环境下捕食,当环境过分拥挤时它就会离开这个环境,游往

6、别处。 人工鱼群算法觅食行为如下:Step1:设置最大尝试次数;Step2:人工鱼从一个状态转移到另一个状态:Xj= Xi+ Random (V isua l) ;Step3:如果适应值 Yi Yj,则 Xi| nex t= Xi+Random ( S tep)Xj- XiXj- Xi; 否则, Xi| nex t= Xi+Random ( S tep) ;Step4:检查终止条件,如果条件满足结束迭带,否则转 Step2。 对于人工鱼的追尾行为:由状态 Xi转移到状态Xj能获得更好的适应值 Yj,人工鱼就向状态 Xj移动一步。否则,就转入觅食行为。人工鱼的聚群行为,当人工鱼探测到所感知的范围

7、内具有较多食物又不拥挤时,人工鱼就向伙伴的中心移动,否则,转向觅食行为。在人工鱼群算法中设置一个公告板,用于记录最优人工鱼个体的状态,当人工鱼自身状态优于最优状态就替代之。算法具有良好的求取全局极值能力,并具有对初值、参数选择不敏感、鲁棒性强、简单易实现等诸多优点,但是当问题规模过大时求解困难并且求解初期收敛较快,后期较慢。 人工鱼群算法的改进研究,如在算法中增加鱼群的协调行为,将人工鱼群算法与模拟退火算法相融和的混合智能算法等。人工鱼群算法目前已用于组合优化、 参数估计、PI D控制器的参数整定、神经网络优化等。2.2蚁群算法 蚁群算法(ant colony optimization, AC

8、O)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚂蚁是一类社会性很强的生物,它们群体生活、共同觅食。在觅食过程中每只蚂蚁单独行动,蚂蚁之间通过信息素的释放来对觅食的轨迹进行“记忆” ,一旦某一条轨迹发现了食物,那么其它蚂蚁就会向这条道路进行聚集,这

9、条道路上的信息素的量就会增多。如果在觅食的过程中,蚂蚁发现不同路径的距离有远、 近的区别,则蚂蚁就会选择最近的路径进行觅食,并把这一情况通过路径上信息素量的大小通知给其它蚂蚁。受到蚂蚁觅食现象的启发,Colorni、 Dorigo等于 1991年首次提出了蚁群算法,并用这一算法解决了一系列组合优化问题。 基本蚁群算法的求解过程:Step1:设置参数,初始化信息素轨迹;Step2:生成 m个可行解 (蚂蚁) ;Step3:对每一个蚂蚁个体,计算其适应度;Step4:确定每一只蚂蚁的最优位置 (最优解) ;Step5:确定全局的最优位置 (最优解) ;Step6:更新信息素轨迹;Step7:判断终

10、止条件是否满足,若满足则终止迭代,否则返回 Step3。 在蚁群算法中,蚂蚁通过行走在不同的地点 (状态)之间转移, t时刻蚂蚁 k在点 i向点 j的转移概率Pkij( t) 为: 式中:ij 边 ( i, j ) 的能见度,反映由点 i转移到点 j的启发程度,这个量在蚂蚁系统的运行中不改变;ij 边 ( i , j) 上的信息素轨迹强度; Pkij 蚂蚁 k 的 转 移 概 率, j 是 尚 未 访 问 的 点;a llowedk 蚂蚁 k下一步允许选择的点, a llowed= 0, 1, , n - 1 ;r 蚂蚁可以到达的位置。由式 (1)可知,转移概率 Pij( t) 与ij ij成

11、正比。和为两个参数,分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。经过 n时刻,蚂蚁完成一次循环,各路径上信息素量根据下式调整:式中: ij( t, t +1) 第 k只蚂蚁在时刻 ( t, t +1)留在路径 ( i ,j) 上的信息素量,其值大小视蚂蚁表现的优劣而定。路径越短信息素释放就越多; ij( t , t + 1) 本次循环中路径 ( i, j ) 的信息素的增量; 信息素挥发系数,通常设置 1来避免路径上轨迹量的无限累加。通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面

12、的特点： 1、多样性 2、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强

13、，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！蚁群算法的实现下面的程序开始运行之后，蚂蚁们开始从

14、窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。 其中，F点表示食物，H表示窝，白色块表示障碍物，+就是蚂蚁了。下面给出了一段求最优路径的蚁群算法的C+程序用vc+6.0来运行，地点之间的距离用矩阵来输入。#includeusing namespace std;const int MAX=100; /最多结点数const int MAX_LENGTH=10000; /最大长度struct closedgeint adjvex;int lowcost;bool visited;class Graphprivate:int arcsMAXMAX;char nodeMAX;i

15、nt count;public:void init_graph();void dijkstra();void Graph:init_graph()int i;coutcount;cout请依次输入各结点名称：;for( i=0;inodei;cout请输入邻接矩阵:endl;for( i=0;icount;i+)for(int j=0;jarcsij;void Graph:dijkstra()int temp_index;int min;int sor; /起始结点序号int des; /终点序号coutsordes蚁群算法中参加觅食的每一只蚂蚁都是一个单独计算的单元,由于大量的蚂蚁参与了运算

16、,算法具有很强的并行性。蚂蚁之间通过信息素进行合作,而不是直接通信,因此随着个体的增加系统的通信开销增加的也较小。因此,蚁群算法是一种结合了分布式计算、 正反馈机制和贪婪式搜索的算法,具有很强的搜索较优解的能力。但是蚁群算法也有搜索速度慢、陷入局部最优及搜索停滞等缺点。针对这些问题,人们对蚁群算法的机理进行了深入研究并提出许多改进措施。2.3混合蛙跳算法在一片湿地中生活着一群青蛙,湿地内离散地分布着许多石头,青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。每个青蛙通过寻找不同的石头提高自己寻找食物的能力,而青蛙个体之间通过思想的交流实现信息的交换。模拟群体青蛙的觅食特性,文献于2003年提

17、出混合蛙跳算法( SFLA)。每只青蛙都具有自己的文化,为了达到自己的目标努力,并被定义为问题的一个解。湿地的整个青蛙群体被分为不同的子群体,每个子群体有着自己文化,执行局部搜索策略。在子群体中的每个个体有着自己的文化,并且影响着其它个体,并随着子群体的进化而进化。当子群体进化到一定阶段以后,各个子群体之间再进行思想的交流实现子群体间的混合运算,一直到所设置的条件满足为止。 对于 D维函数优化问题,第 i只青蛙可表示为U ( i) = (U1i, U2i, , UDi) ,根据每只青蛙适应值 (位置)的大小按下降顺序排列。这样,整个青蛙群体被分为 m个子群体,每个子群体包含 n只青蛙,即池塘中

18、的青蛙数目为 F = mn。在进化计算过程中,第一只青蛙进入第一个子群体,第二只青蛙进入第二个子群体,一直分配下去,直到第 m 只青蛙进入到第 m个子群体。然后,第 m + 1只青蛙又进入到第一个子群体,第 m + 2只青蛙进入到第二个子群体等,这样循环分配下去,直到所有青蛙分配完毕。在每一个子群体中,适应值最好的个体和最差的个体记为 Ub和 Uw ,整个青蛙群体的最优值记为 Ug 。在每次循环中,只提高最差个体的适应值。 混合蛙跳中最差适应值 (位置 )青蛙的计算过程为:蛙跳步长更新: 位置更新为： Smax Si- Smax ,其中 rand ( ) 0, 1 ( k =1, 2, , n

19、) , Smax是最大步长。如果计算后新的解较优,则用其替代最差个体。并且通过式 ( 6)、( 7)求全局最优解 Ug 。如果得到的解没有改进,那么随机生成新解取代所求个体的解,算法继续迭代直至迭代次数完毕。 混合蛙跳算法的算法流程如下:Step1:针对 F只青蛙 (解) ,随机产生种群;Step2:对每只青蛙个体,计算其适应值;Step3:将 F只青蛙按适应值降序排列分为 m个子群体;Step4:对每一个子群体中的青蛙个体找出其中的最优个体和最差个体,在指定迭代次数内提高最差个体的适应值;Step5:针对各个子群体,按适应值降序排列个体,进行重新分配和混合运算;Step6:终止条件是否满足?

20、 如果满足,结束迭代,否则转向 Step2。混合蛙跳算法具有全局优化与局部细致搜索的优点,可以用来优化连续问题和离散问题,并且具有较强的鲁棒性,可用于地下水管网优化设计、非线性函数优化、旅行商问题、下料问题、齿轮问题等。3神经网络算法3.1神经网络知识点概述神经网络是新技术领域中的一个时尚词汇。很多人听过这个词，但很少人真正明白它是什么。本文的目的是介绍所有关于神经网络的基本包括它的功能、一般结构、相关术语、类型及其应用。“神经网络”这个词实际是来自于生物学，而我们所指的神经网络正确的名称应该是“人工神经网络（ANNs）”。在本文，我会同时使用这两个互换的术语。一个真正的神经网络是由数个至数十

21、亿个被称为神经元的细胞（组成我们大脑的微小细胞）所组成，它们以不同方式连接而型成网络。人工神经网络就是尝试模拟这种生物学上的体系结构及其操作。在这里有一个难题：我们对生物学上的神经网络知道的不多！因此，不同类型之间的神经网络体系结构有很大的不同，我们所知道的只是神经元基本的结构。虽然已经确认在我们的大脑中有大约50至500种不同的神经元，但它们大部份都是基于基本神经元的特别细胞。基本神经元包含有synapses、soma、axon及dendrites。Synapses负责神经元之间的连接，它们不是直接物理上连接的，而是它们之间有一个很小的空隙允许电子讯号从一个神经元跳到另一个神经元。然后这些电

22、子讯号会交给soma处理及以其内部电子讯号将处理结果传递给axon。而axon会将这些讯号分发给dendrites。最后，dendrites带着这些讯号再交给其它的synapses，再继续下一个循环。如同生物学上的基本神经元，人工的神经网络也有基本的神经元。每个神经元有特定数量的输入，也会为每个神经元设定权重（weight）。权重是对所输入的资料的重要性的一个指标。然后，神经元会计算出权重合计值（net value），而权重合计值就是将所有输入乘以它们的权重的合计。每个神经元都有它们各自的临界值（threshold），而当权重合计值大于临界值时，神经元会输出1。相反，则输出0。最后，输出会被传

23、送给与该神经元连接的其它神经元继续剩余的计算。 正如上述所写，问题的核心是权重及临界值是该如何设定的呢？世界上有很多不同的训练方式，就如网络类型一样多。但有些比较出名的包括back-propagation, delta rule及Kohonen训练模式。由于结构体系的不同，训练的规则也不相同，但大部份的规则可以被分为二大类别 - 监管的及非监管的。监管方式的训练规则需要“教师”告诉他们特定的输入应该作出怎样的输出。然后训练规则会调整所有需要的权重值（这是网络中是非常复杂的），而整个过程会重头开始直至数据可以被网络正确的分析出来。监管方式的训练模式包括有back-propagation及delt

24、a rule。非监管方式的规则无需教师，因为他们所产生的输出会被进一步评估。在神经网络中，遵守明确的规则一词是最“模糊不清”的。因为有太多不同种类的网络，由简单的布尔网络（Perceptrons），至复杂的自我调整网络（Kohonen），至热动态性网络模型（Boltzmann machines）！而这些，都遵守一个网络体系结构的标准。一个网络包括有多个神经元“层”，输入层、隐蔽层及输出层。输入层负责接收输入及分发到隐蔽层（因为用户看不见这些层，所以见做隐蔽层）。这些隐蔽层负责所需的计算及输出结果给输出层，而用户则可以看到最终结果。现在，为免混淆，不会在这里更深入的探讨体系结构这一话题。对于不同

25、神经网络的更多详细资料可以看Generation5 essays尽管我们讨论过神经元、训练及体系结构，但我们还不清楚神经网络实际做些什么。神经网络被设计为与图案一起工作 - 它们可以被分为分类式或联想式。分类式网络可以接受一组数，然后将其分类。例如ONR程序接受一个数字的影象而输出这个数字。或者PPDA32程序接受一个坐标而将它分类成A类或B类（类别是由所提供的训练决定的）。更多实际用途可以看Applications in the Military中的军事雷达，该雷达可以分别出车辆或树。联想模式接受一组数而输出另一组。例如HIR程序接受一个脏图像而输出一个它所学过而最接近的一个图像。联想模式更

26、可应用于复杂的应用程序，如签名、面部、指纹识别等。3.2神经网络在计算机中的应用很多神经网络都是模仿生物神经网络的，即是他们仿照大脑的运作方式工作。神经网络也得助于神经系统科学的发展，使它可以像人类一样准确地辨别物件而有电脑的速度！前途是光明的，但现在.是的，神经网络也有些不好的地方。这通常都是因为缺乏足够强大的硬件。神经网络的力量源自于以并行方式处理资讯，即是同时处理多项数据。因此，要一个串行的机器模拟并行处理是非常耗时的。神经网络的另一个问题是对某一个问题构建网络所定义的条件不足 - 有太多因素需要考虑：训练的算法、体系结构、每层的神经元个数、有多少层、数据的表现等，还有其它更多因素。因此

27、，随着时间越来越重要，大部份公司不可能负担重复的开发神经网络去有效地解决问题。神经网络算法是指模拟生物的神经结构以及其处理信息的方式来进行计算一种算法。网格计算是网格并行计算的一种，另一种是机群计算，其目标是将广域网上一些计算资源、数据源和其他设备等互联，形成一个大的可相互利用、合作的高性能计算网，用户可以像登陆一台超级巨型机一样使用它。下面是一个基因算法在人工神经元网络中的应用的matlab程序：clearPopsize=40;P_mutation=0.1;P_cross=0.6;real chrom;real currentbest_value;m=25; %权值和阈值的初始化范围chro

28、m=2*m.*rand(Popsize,21)-m; % 产生初始种群temchrom=zeros(size(chrom);p=0 0 0 0 1 1 1 1;0 0 1 1 0 0 1 1;1 0 1 0 1 0 1 0; %输入值aim=0 1 1 0 1 0 0 1; % 输出值ecope=100;currentbest=zeros(ecope,21);currentbest_value=zeros(ecope,1);fitness_gene=fitness(chrom,p,aim); %计算的染色体均方误差 fitness=8/sum(error.2) c_value c_order=

29、max(fitness_gene); for k=1:ecope %保留当前最好染色体 c_value c_order=max(fitness_gene); currentbest(k,:)=chrom(c_order,:); currentbest_value(k)=c_value; % 选择过程 fit=cumsum(fitness_gene)/sum(fitness_gene); N=Popsize; s=select(fit,N); temchrom=chrom(s,:); %交叉 P=rand(1,N); prob=find(PP_cross); crosschrom=temchro

30、m(prob,:); crosschrom=cross_over(crosschrom); temchrom(prob,:)=crosschrom; %变异 temchrom=mutation(temchrom,P_mutation,Popsize,ecope); chrom=temchrom; % 计算交叉变异之后的染色体的适应度 fitness_gene=fitness(chrom,p,aim); fit=cumsum(fitness_gene)/sum(fitness_gene); N=Popsize; s=select(fit,N-1); s_value s_order=max(fit

31、ness_gene); if s_valuecurrentbest_value(k) %基因选择 chrom=chrom(s,:);currentbest(k,:); fitness_gene=fitness_gene(s);currentbest_value(k); else s=s s_order(1); chrom=chrom(s,:); fitness_gene=fitness_gene(s); end% if currentbest_value(k)=1% break% endend%图表显示i=1:k;y=1./currentbest_value(1:k,:);plot(i,y,r

32、:);title( sum root mean square error);% tocy(k) 总之，神经网络在这个领域中有很多优点，使得它越来越流行。它在类型分类/识别方面非常出色。神经网络可以处理例外及不正常的输入数据，这对于很多系统都很重要（例如雷达及声波定位系统）。4模拟退火算法 模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳

33、特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Me

34、tropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。下面介绍一简单的模拟

35、退火算法原理。我们假设算法用以解决如下的组合最优化问题： min s.t. 其中为目标函数，为约束方程，D为定义域。简单的模拟退火算法为： Step1 任选一个初始解；;(初始尺度) Step2 若在该温度达到内循环停止条件，则到Step3；否则，从邻域中随机选一，计算；若，则，否则若时，则；重复Step2； Step3 ；若满足停止条件，终止计算；否则，返回Step2。在上述的模拟退火算法中，包含一个内循环和一个外循环。内循环是Step2，他表示在同一个温度时，在一些状态随机搜索。外循环包括Step3的温度下降变化，迭代步数的增加和停止条件。模拟退火的直观理解是：在一个给定温度，搜索从一个状

36、态随机地变化到另一个状态。每一个状态到达的次数服从一个概率分布。当温度很低时，以概率1停留在最优解。5遗传算法（Genetic Algorithm）5.1遗传算法知识简介遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算

37、法（SGA）。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、和人工生命等领域。它是现代有关中的。遗传算法的基本运算过程如下:a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗

38、传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。5.2遗传算法的现状随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空

39、间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evol

40、ution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（Stoch

41、astic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体

42、用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传

43、算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。5.3遗传算法的定义遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合

44、，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过

45、程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。5.4遗传算法的特点和应用 遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：首先组成一组候选解；依据某些适应性条件测算这些候选解的适应度；根据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法还具有以下几方面的特点：(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其它，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗