智能控制(第三版)chap10-智能算法及其应用2

1、随着优化理论的发展，一些智能算法成为解决传随着优化理论的发展，一些智能算法成为解决传统系统辨识问题的新方法，如统系统辨识问题的新方法，如遗传算法、遗传算法、 蚁群蚁群算法、算法、 粒子群算法、差分进化算法粒子群算法、差分进化算法等。等。都是通过都是通过模拟揭示自然现象模拟揭示自然现象来实现来实现的的。本章介绍本章介绍遗传算法遗传算法的基本概念和方法。的基本概念和方法。2 遗传算法简称遗传算法简称GAGA（Genetic AlgorithmsGenetic Algorithms）是）是19621962年年由由美国美国HollandHolland教授提出的教授提出的模拟自然界生物进化机制模拟自然界

2、生物进化机制的一种并行的一种并行随机搜索随机搜索最优化方法。最优化方法。 遗传算法是以达尔文的遗传算法是以达尔文的自然选择学说自然选择学说为基础为基础, ,包括包括以下三个方面：以下三个方面：3（1 1）遗传遗传：亲代把生物信息交给子代，子代总是和亲：亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。才能稳定存在。（2 2）变异变异：亲代和子代之间以及子代的不同个体之间：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是的差异，称为变异。变异是随机随机发生的，变异的选择发生的，变异的选择和积累

3、是生命多样性的根源。和积累是生命多样性的根源。（3 3）生存斗争和适者生存生存斗争和适者生存：具有适应性变异的个体被：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐与祖先有所不代代的生存环境的选择作用，性状逐渐与祖先有所不同，演变为新的物种。同，演变为新的物种。4 遗传算法引入遗传算法引入“优胜劣汰，适者生存优胜劣汰，适者生存”的生物进的生物进化机制，按所选择的适应度函数对个体进行筛选。化机制，按所选择的适应度函数对个体进行筛选。 适应度高适应度高的个体被保留下来，组成新的群体，新的个体被保留

4、下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。的群体既继承了上一代的信息，又优于上一代。 周而复始，使群体中个体适应度不断提高，直到周而复始，使群体中个体适应度不断提高，直到满足一定的条件。满足一定的条件。 遗传算法可并行处理，得到全局最优解。遗传算法可并行处理，得到全局最优解。5遗传算法的基本操作为：遗传算法的基本操作为：（1）复制（）复制（Reproduction Operator）从旧种群中选择从旧种群中选择生命力强生命力强的个体产生新种群。的个体产生新种群。 通过通过随机随机方法实现。若设定复制概率阈值为方法实现。若设定复制概率阈值为40%，当产生的随机数在当产生的随

5、机数在0.41之间时，该个体被复制到子之间时，该个体被复制到子代，否则该个体被淘汰。代，否则该个体被淘汰。6（2 2）交叉（）交叉（Crossover OperatorCrossover Operator） 通过两个染色体的通过两个染色体的交换组合交换组合产生新的优良个体。产生新的优良个体。 任选任选两个染色体，随机选择一点或多点交换点位置；两个染色体，随机选择一点或多点交换点位置；交换双亲染色体在交换点右边的部分，即可得到两交换双亲染色体在交换点右边的部分，即可得到两个新的染色体数字串。个新的染色体数字串。有一点交叉、多点交叉等。有一点交叉、多点交叉等。一点交叉：染色体断点仅有一处，例：一点

6、交叉：染色体断点仅有一处，例：7: 101100 1110101100 0101: 001010 0101001010 1110AB一点交叉示意图一点交叉示意图8（3 3）变异）变异(Mutation Operator)(Mutation Operator) 模拟基因突变现象，以模拟基因突变现象，以小概率随机改变遗传基因小概率随机改变遗传基因的值。的值。 在染色体以在染色体以二进制编码二进制编码的系统中，它随机地将染的系统中，它随机地将染色体的某一个基因位由色体的某一个基因位由1 1变为变为0 0，或由，或由0 0变为变为1 1。优点：可使进化过程逃离局部最优解。优点：可使进化过程逃离局部最优

7、解。1011 0011 1011 1011910.2 10.2 遗传算法的特点遗传算法的特点 （1 1）对）对参数编码参数编码进行操作，而非对参数本身。因此，进行操作，而非对参数本身。因此，在参数优化过程中可借鉴生物学中染色体和基因等概在参数优化过程中可借鉴生物学中染色体和基因等概念，模仿生物进化等机理；念，模仿生物进化等机理；（2 2）同时使用）同时使用多个搜索点多个搜索点的搜索信息。传统方法往往的搜索信息。传统方法往往是从解空间的是从解空间的单个初始点单个初始点开始最优解的迭代搜索过程，开始最优解的迭代搜索过程，效率不高，有时甚至会陷入效率不高，有时甚至会陷入局部最优解局部最优解而停滞不前

8、。而停滞不前。以群体为基础进行搜索，效率高。以群体为基础进行搜索，效率高。10（3 3）遗传算法）遗传算法直接以目标函数直接以目标函数作为搜索信息，无需目作为搜索信息，无需目标函数的标函数的导数值导数值等其他一些辅助信息。适用于目标函等其他一些辅助信息。适用于目标函数数无法求导数或导数不存在无法求导数或导数不存在的优化问题，或者组合优的优化问题，或者组合优化问题等。化问题等。（4 4）遗传算法使用概率搜索技术。各种操作：选择、）遗传算法使用概率搜索技术。各种操作：选择、交叉、变异等都是以概率的方式进行的。交叉、变异等都是以概率的方式进行的。（5 5）遗传算法在解空间进行高效）遗传算法在解空间进

9、行高效启发式搜索启发式搜索，而非盲，而非盲目地穷举或完全随机搜索；目地穷举或完全随机搜索；11（6 6）遗传算法对于待寻优的函数基本无限制，它）遗传算法对于待寻优的函数基本无限制，它既不既不要求函数连续，也不要求函数可微要求函数连续，也不要求函数可微，既可以是数学解，既可以是数学解析式所表示的析式所表示的显函数显函数，又可以是映射矩阵甚至是神经，又可以是映射矩阵甚至是神经网络的网络的隐函数隐函数，因而应用范围较广；，因而应用范围较广；（7）遗传算法具有）遗传算法具有并行计算并行计算的特点，因而可通过大规的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的模并行计算来提高计算速度

10、，适合大规模复杂问题的优化。优化。 1210.3 遗传算法的发展及应用遗传算法的发展及应用 自学。自学。1310.4 10.4 遗传算法的设计遗传算法的设计10 0111 0010 0010 1101x 141516171819遗传算法流程图遗传算法流程图 参数解码计算适应度复制交叉变异满足要求?遗传操作新种群寻优结束是是否否种群编码2022212121( ,)100()(1)2.0482.048(1,2)if x xxxxxi21函数函数f(x1, x2)的三维图如图的三维图如图10-2所示，可以所示，可以发现该函数在指定的定义域上发现该函数在指定的定义域上有两个有两个靠靠近近的极的极值值点

11、点，即一个全局极大值和一个局部，即一个全局极大值和一个局部极大值。极大值。因此，采用寻优算法求极大值时，需要避因此，采用寻优算法求极大值时，需要避免陷入局部最优解。免陷入局部最优解。22函数函数f(x1, x2)的三维图的三维图2324251101110001 0000110111:x26)2 , 1(048. 21023096. 4iyxii27),()(21xxfxF1min( )( )J xF x28290 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Best S书中程序出错！%Generic Algorithm for function f(x1,x2)

12、 optimumclear all;close all;%ParametersSize=80; %种群大小G=100; %遗传代数CodeL=10; %每个变量的染色体长度（2进制编码）umax=2.048; %两个变量的取值范围是相同的umin=-2.048;%初始种群的染色体E=round(rand(Size, 2*CodeL); for k=1:1:G time(k)=k; for s=1:1:Size m=E(s,:); y1=0; y2=0; m1=m(1:1:CodeL); %取第1个变量x1的染色体 for i=1:1:CodeL y1=y1+m1(i)*2(i-1); %求对应

13、的十进制数 end x1=(umax-umin)*y1/1023+umin; %解码，求变量x1的值 m2=m(CodeL+1:1:2*CodeL); %取第2个变量x2的染色体 for i=1:1:CodeL y2=y2+m2(i)*2(i-1); end x2=(umax-umin)*y2/1023+umin; F(s)=100*(x12-x2)2+(1-x1)2; %目标函数值 end0204060801002.93.43.5x 10-4TimesBest J0204060801002900300031003200330034003500360037

14、0038003900timesBest F343510.5.2 10.5.2 实数编码遗传算法求函数极大值实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件；）确定决策变量和约束条件；（2 2）建立优化模型；）建立优化模型；（3 3）确定编码方法：用）确定编码方法：用2 2个实数分别表示两个个实数分别表示两个决策变量决策变量x1, x2，分别将，分别将x1, x2的定义域离散化的定义域离散化为从离散点为从离散点-2.0482.048到离散点到离散点2.048的的SizeSize个实个实数。数。36（4 4）确定个体评价方法：

15、）确定个体评价方法： 个体的适应度直接取为对应的目标函数值，个体的适应度直接取为对应的目标函数值，即即),()(21xxfxF)(1)(xFxJ选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数37（5 5）设计遗传算子：）设计遗传算子：选择运算使用选择运算使用比例选择比例选择算子，算子，交叉运算使用交叉运算使用单点交叉单点交叉算子，变异运算使用算子，变异运算使用基本位变基本位变异异算子。算子。（6）确定遗传算法的运行参数：群体大小）确定遗传算法的运行参数：群体大小M=500M=500，终，终止进化代数止进化代数G=200G=200，交叉概率，交叉概率P Pc c=0.90=0.90

16、，采用自适应变，采用自适应变异概率异概率m0.1011:1:Size/SizePfit即变异概率与适应度有关，即变异概率与适应度有关，适应度越小，变异概率越适应度越小，变异概率越大大。38上述六个步骤构成了用于求函数上述六个步骤构成了用于求函数Rosenbrock极大值极大值的实数编码遗传算法，仿真程序见的实数编码遗传算法，仿真程序见chap10_2.m。 %* Step 3 : 交叉操作交叉操作 * Pc=0.90; %交叉概率交叉概率 for i=1:2:(Size-1) temp=rand; if Pctemp alfa=rand; TempE(i,:)=alfa*E(i+1,:)+(1

17、-alfa)*E(i,:); %交叉操作交叉操作 TempE(i+1,:)=alfa*E(i,:)+(1-alfa)*E(i+1,:); end end第i+1个个体与第i个个体进行交叉 %* Step 4: 变异操作变异操作 * Pm=0.10-1:1:Size*(0.01)/Size; %自适应变异概率自适应变异概率 Pm_rand=rand(Size, CodeL); Dif=(MaxX - MinX); for i=1:1:Size for j=1:1:CodeL if Pm(i)Pm_rand(i,j) %Mutation Condition TempE(i,j)=MinX(j)+D

18、if(j)*rand; %变异操作变异操作 end end end变异操作：随机变成另一个数了4010.6.1 遗传算法优化原理遗传算法优化原理 在在7.3节的节的RBF网络逼近算法中，网络权网络逼近算法中，网络权值值W、高斯函数的中心矢量、高斯函数的中心矢量C和基宽向量和基宽向量B的的初值初值难以确定，如果这些参数选择不当，会难以确定，如果这些参数选择不当，会造成逼近精度的下降甚至造成逼近精度的下降甚至RBF网络的发散。网络的发散。采用遗传算法可实现采用遗传算法可实现RBF网络参数初始值的网络参数初始值的优化。优化。41 为获取满意的逼近精度，采用误差绝对值指标作为为获取满意的逼近精度，采用

19、误差绝对值指标作为参数选择的最小目标函数。参数选择的最小目标函数。 式中，式中， 为逼近的总步骤，为逼近的总步骤， 为第为第 步步RBF网络的逼近误网络的逼近误差。差。 在应用遗传算法时，为了避免参数选取范围过大，在应用遗传算法时，为了避免参数选取范围过大，可以先按经验选取一组参数，然后再在这组参数的周可以先按经验选取一组参数，然后再在这组参数的周围利用遗传算法进行设计，从而大大减少初始寻优的围利用遗传算法进行设计，从而大大减少初始寻优的盲目性，节约计算量。盲目性，节约计算量。 1100|NiJe iN iei4210.6.2 仿真实例仿真实例 使用使用RBF网络逼近下列对象：网络逼近下列对象

20、：32(1)( )( )1(1)y ky kukyk 在在RBF网络中，网络中，网络输入信号为网络输入信号为2个，即个，即u(k)和和y(k)，网络初始权值及高斯函数参数初始值，网络初始权值及高斯函数参数初始值通过遗传算法优化而得。通过遗传算法优化而得。43 遗传算法优化程序为遗传算法优化程序为chap10_3a.m，取逼近，取逼近总步骤为总步骤为N=500N=500，每一步的逼近误差及目标函，每一步的逼近误差及目标函数由数由chap10_3b.m求得。采用二进制编码方式，求得。采用二进制编码方式，用长度为用长度为10位的二进制编码串来分别表示向量位的二进制编码串来分别表示向量B B、C C和

21、和W W中的每个值。中的每个值。 44 遗传算法优化中，取样本个数为遗传算法优化中，取样本个数为Size=30，交叉概，交叉概率为率为Pc=0.60，采用自适应变异概率，采用自适应变异概率，即适应度越小，即适应度越小，变异概率越大，取变异概率越大，取变异概率为变异概率为 取用于优化的取用于优化的RBF网络结构为网络结构为2-3-1，i=1,2,j=1,2,3。网络权值网络权值wj的取值范围为的取值范围为-1,+1，高斯函数基宽向量，高斯函数基宽向量元素元素bj的取值范围为的取值范围为0.1,+3，高斯函数中心矢量元素，高斯函数中心矢量元素cij的取值范围为的取值范围为-3,+3。取。取则共有则

22、共有12个参数需要优化。个参数需要优化。0.001/SizeSize:1:10.001mP321232221131211321wwwccccccbbbp45 经过经过150代遗传算法进化，优化后的结果为：代遗传算法进化，优化后的结果为：p=2.7732，2.6343，2.2630，1.8680，-0.0616，-0.7126，-0.3959，2.2669， -1.4047，-0.3099，0.7478，-0.3353。 则则RBF网络高斯基函数参数的优化值及权值网络高斯基函数参数的优化值及权值的优化值为的优化值为:2.7732,2.6343,2.26301.86800.06160.71260.

23、39592.26691.40470.3099,0.7478,0.3353TTBCW 46 RBF网络遗传算法优化程序包括三部分，网络遗传算法优化程序包括三部分，即遗传算法优化程序即遗传算法优化程序chap10_3a.m、RBF网络网络逼近函数程序逼近函数程序chap10_3b.m和和RBF网络逼近测网络逼近测试程序试程序chap10_3c.m。4710.7 基于遗传算法的基于遗传算法的TSP问题优化问题优化 旅行商问题（旅行商问题（Traveling Salesman Problem，TSP）：）： 有有N个城市，已知任意两个间的距离，现个城市，已知任意两个间的距离，现有一推销员必须遍访这有一

24、推销员必须遍访这N个城市，并且每个城市只个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线总长排他对这些城市的访问次序，使其旅行路线总长度最短。度最短。 旅行商问题是一个典型的旅行商问题是一个典型的组合组合优化问题优化问题，其可能的路径数目，其可能的路径数目与城市数目与城市数目N呈指数型增长的，呈指数型增长的，一般很难精确的求出最优解，一般很难精确的求出最优解，因而寻找其有效的因而寻找其有效的近似求解算近似求解算法法具有重要的理论意义。具有重要的理论意义。 很多实际应用问题经过简化处很多实际应用问题经

25、过简化处理后可转化为旅行商问题，因理后可转化为旅行商问题，因而对旅行商问而对旅行商问题求解方法的研题求解方法的研究具有重要的应用价值究具有重要的应用价值4910.7.1 TSP问题的编码问题的编码 在旅行商问题的各种求解方法中，描述旅行路线在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两种：（的方法主要有如下两种：（1）巡回旅行路线经过的）巡回旅行路线经过的连接两个城市的连接两个城市的路线的顺序排列路线的顺序排列；（；（2）巡回旅行路）巡回旅行路线所经过的各个线所经过的各个城市的顺序排列城市的顺序排列。大多数求解旅行商。大多数求解旅行商问题的遗传算法是以后者为描述方法的，它们大多采

26、问题的遗传算法是以后者为描述方法的，它们大多采用所遍历城市的顺序来表示各个个体的编码串，其等用所遍历城市的顺序来表示各个个体的编码串，其等位基因为位基因为N个整数值或个整数值或N个记号。个记号。 以以城市的遍历顺序城市的遍历顺序作为遗传算法的编码，目标函数作为遗传算法的编码，目标函数取路径长度。取路径长度。在群体初始化、交叉操作和变异操作中考虑在群体初始化、交叉操作和变异操作中考虑TSP问题问题的合法性约束条件（即对所有的城市做到不重不的合法性约束条件（即对所有的城市做到不重不漏）。漏）。5110.7.2 TSP问题的遗传算法设计问题的遗传算法设计 采用遗传算法进行路径优化，分为以下几步：采用

27、遗传算法进行路径优化，分为以下几步： 第一步：参数编码和初始群体设定第一步：参数编码和初始群体设定对于对于TSP一类排序问题，采用一类排序问题，采用对访问城市序列进行排对访问城市序列进行排列组合的方法编码列组合的方法编码，即染色体个体表示按顺序经过的，即染色体个体表示按顺序经过的城市序列。城市序列。52N为城市总数，染色体长度为N+1，最后一位表示该路径总长度。参数编码和初始群体程序段为：pop=zeros(s,N+1);for i=1:s pop(i,1:N)=randperm(N); %随机排列随机排列end 第二步：计算路径长度的函数设计第二步：计算路径长度的函数设计 以距离的总长度为以

28、距离的总长度为适应度函数适应度函数来衡量求解结果是否来衡量求解结果是否最优。设最优。设D=dij是由城市是由城市i和城市和城市j之间的距离组成的之间的距离组成的距离矩阵距离矩阵。计算路径长度的程序为计算路径长度的程序为chap10_1dis.m。 1NjJ td j目标函数：目标函数： 1f tJ t自适应度函数：自适应度函数：54 第三步：计算选择算子第三步：计算选择算子群体中适应度最大的群体中适应度最大的c个个体直接替换适应度最小个个体直接替换适应度最小的的c个个体。选择算子函数为个个体。选择算子函数为chap10_4select.m。num=1; %m11为当前种群中各个体的路径总长度为

29、当前种群中各个体的路径总长度while numc+1 %取距离大的取距离大的c个个体个个体 a,mmax(num)=max(m11); %选择当前种群中距离总长度最大值，并记选择当前种群中距离总长度最大值，并记录样本编号给录样本编号给mmax(num) m11(mmax(num)=0; %清除，防止再次被选中清除，防止再次被选中 %取距离小的取距离小的c个个体个个体 ,mmin(num)=min(m12); %chenyag m12(mmin(num)=a; %修改为很大的一个数，防止再次被选中修改为很大的一个数，防止再次被选中 num=num+1;end%用距离大的用距离大的c个个体替换距离小的个个体替换距离小的c个个体个个体pop(mmax,:) = pop(mmin,:); 第四步：计算交叉算子第四步：计算交叉算子有序交叉法有序交叉法步骤1： 随机选取两个交叉点。步骤2：复制两交叉点之间的基因串A1和B1。56步骤步骤3：在对应位置：在对应位置交换交换X1和和X2双亲匹配段双亲匹配段A1和和B1以外的城市。以外的城市。57X1: 9 8|45671|320A1X2:87|14032|965B