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

第10章智能算法及其应用随着优化理论的发展，一些智能算法成为解决传统系统辨识问题的新方法，如遗传算法、蚁群算法、粒子群算法、差分进化算法等。都是通过模拟揭示自然现象来实现的。本章介绍遗传算法的基本概念和方法。2

10.1遗传算法的基本原理

遗传算法简称GA（GeneticAlgorithms）是1962年由美国Holland教授提出的模拟自然界生物进化机制的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础,包括以下三个方面：3（1）遗传：亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐与祖先有所不同，演变为新的物种。4遗传算法引入“优胜劣汰，适者生存”的生物进化机制，按所选择的适应度函数对个体进行筛选。适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。周而复始，使群体中个体适应度不断提高，直到满足一定的条件。遗传算法可并行处理，得到全局最优解。5遗传算法的基本操作为：（1）复制（ReproductionOperator）从旧种群中选择生命力强的个体产生新种群。通过随机方法实现。若设定复制概率阈值为40%，当产生的随机数在0.4~1之间时，该个体被复制到子代，否则该个体被淘汰。6（2）交叉（CrossoverOperator）通过两个染色体的交换组合产生新的优良个体。任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体在交换点右边的部分，即可得到两个新的染色体数字串。有一点交叉、多点交叉等。一点交叉：染色体断点仅有一处，例：7一点交叉示意图8（3）变异(MutationOperator)模拟基因突变现象，以小概率随机改变遗传基因的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因位由1变为0，或由0变为1。优点：可使进化过程逃离局部最优解。1011001110111011910.2遗传算法的特点

（1）对参数编码进行操作，而非对参数本身。因此，在参数优化过程中可借鉴生物学中染色体和基因等概念，模仿生物进化等机理；（2）同时使用多个搜索点的搜索信息。传统方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，效率不高，有时甚至会陷入局部最优解而停滞不前。以群体为基础进行搜索，效率高。10（3）遗传算法直接以目标函数作为搜索信息，无需目标函数的导数值等其他一些辅助信息。适用于目标函数无法求导数或导数不存在的优化问题，或者组合优化问题等。（4）遗传算法使用概率搜索技术。各种操作：选择、交叉、变异等都是以概率的方式进行的。（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；11（6）遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。

1210.3遗传算法的发展及应用自学。1310.4.1遗传算法的构成要素（1）染色体编码方法基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集{0,1}所组成。初始个体基因值可用均匀分布的随机值生成，如表示一个个体，该个体的染色体长度是18。10.4遗传算法的设计14（2）个体适应度评价：每个个体的适应度代表了其遗传到下一代的概率。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值J到个体适应度f之间的转换规则。15（3）遗传算子：三种基本遗传算子包括①选择运算：使用比例选择算子；②交叉运算：使用单点交叉算子；③变异运算：使用基本位变异算子或均匀变异算子。16（4）基本遗传算法的运行参数有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20~100；G：遗传算法的终止进化代数，一般取为100~500；Pc：交叉概率，一般取为0.4~0.99；Pm：变异概率，一般取为0.0001~0.1。17构造遗传算法解决优化问题的步骤：S1：确定决策变量及各种约束条件，即确定个体的表现形式和问题的解空间；S2：建立优化模型，即确定目标函数的描述形式或量化方法；S3：确定表示可行解的染色体编码方法，即确定个体的基因形式及遗传算法的搜索空间；10.4.2遗传算法的应用步骤18S4：确定个体适应度的量化评价方法，即确定由目标函数值J(x)到个体适应度函数F(x)的转换规则；S5：设计遗传算子，即确定选择、交叉、变异运算等遗传算子的具体操作方法；S6：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数；S7：确定解码方法，即确定出由个体表现形式到个体基因的对应关系或转换方法。19遗传算法流程图

参数解码计算适应度复制交叉变异满足要求?遗传操作新种群寻优结束是否种群编码20利用遗传算法求Rosenbrock函数的极大值10.5遗传算法求函数极大值21函数f(x1,x2)的三维图如图10-2所示，可以发现该函数在指定的定义域上有两个靠近的极值点，即一个全局极大值和一个局部极大值。因此，采用寻优算法求极大值时，需要避免陷入局部最优解。22函数f(x1,x2)的三维图23采用遗传算法求解该问题的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法。10.5.1二进制编码遗传算法求函数极大值24用长度为10位的二进制编码来分别表示两个决策变量x1,x2。将x1,

x2的定义域离散化为1023个均等的区域，共获得1024个离散点。离散点分别与取值区间的二进制编码相对应。0000000000(0)1111111111(1023)-2.0482.04825将x1,x2的编码串接在一起，得到20位长的参数编码。这就是该函数优化问题的染色体编码。解空间和搜索空间具有一一对应关系。例如：某个体的基因型如下其中前10位表示x1，后10位表示x2。26（4）解码时，将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据前面的方法，将代码yi转换为变量xi的解码公式为：例如，对染色体x：00001101111101110001，切断后得到y1=55，y2=881。解码后，得到x1=-1.828，x2=1.476。27（5）确定个体评价方法：由于优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即选择个体适应度的倒数作为目标函数28（6）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（7）确定遗传算法的运行参数：群体大小M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。29即当x1=-2.0480，x2=-2.0480时，Rosenbrock函数具有极大值，极大值为3905.9。仿真程序：chap10_1.m

采用上述方法进行仿真，经过100步迭代，最佳样本为书中程序出错！%GenericAlgorithmforfunctionf(x1,x2)optimumclearall;closeall;%ParametersSize=80;%种群大小G=100;%遗传代数CodeL=10;%每个变量的染色体长度（2进制编码）umax=2.048;%两个变量的取值范围是相同的umin=-2.048;%初始种群的染色体E=round(rand(Size,2*CodeL));fork=1:1:G

time(k)=k;fors=1:1:Sizem=E(s,:);y1=0;y2=0;m1=m(1:1:CodeL);%取第1个变量x1的染色体

fori=1:1:CodeLy1=y1+m1(i)*2^(i-1);%求对应的十进制数

endx1=(umax-umin)*y1/1023+umin;%解码，求变量x1的值

m2=m(CodeL+1:1:2*CodeL);%取第2个变量x2的染色体

fori=1:1:CodeLy2=y2+m2(i)*2^(i-1);endx2=(umax-umin)*y2/1023+umin;

F(s)=100*(x1^2-x2)^2+(1-x1)^2;%目标函数值

end34

遗传算法的优化过程是目标函数J和适应度函数F的变化过程。由仿真结果可知，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多，并且它们都集中在所求问题的最优点附近，从而搜索到问题的最优解。3510.5.2实数编码遗传算法求函数极大值求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法：用2个实数分别表示两个决策变量x1,x2，分别将x1,x2的定义域离散化为从离散点-2.048到离散点2.048的Size个实数。36（4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即选个体适应度的倒数作为目标函数37（5）设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。（6）确定遗传算法的运行参数：群体大小M=500，终止进化代数G=200，交叉概率Pc=0.90，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。38上述六个步骤构成了用于求函数Rosenbrock极大值的实数编码遗传算法，仿真程序见chap10_2.m。

%************Step3:交叉操作************Pc=0.90;%交叉概率fori=1:2:(Size-1)temp=rand;ifPc>temp

alfa=rand;

TempE(i,:)=alfa*E(i+1,:)+(1-alfa)*E(i,:);%交叉操作TempE(i+1,:)=alfa*E(i,:)+(1-alfa)*E(i+1,:);endend第i+1个个体与第i个个体进行交叉

%************Step4:变异操作**************Pm=0.10-[1:1:Size]*(0.01)/Size;%自适应变异概率

Pm_rand=rand(Size,CodeL);Dif=(MaxX-MinX);

fori=1:1:Sizeforj=1:1:CodeLifPm(i)>Pm_rand(i,j)%MutationCondition

TempE(i,j)=MinX(j)+Dif(j)*rand;

%变异操作endendend变异操作：随机变成另一个数了4010.6基于遗传算法优化的RBF网络逼近10.6.1遗传算法优化原理在7.3节的RBF网络逼近算法中，网络权值W、高斯函数的中心矢量C和基宽向量B的初值难以确定，如果这些参数选择不当，会造成逼近精度的下降甚至RBF网络的发散。采用遗传算法可实现RBF网络参数初始值的优化。41

为获取满意的逼近精度，采用误差绝对值指标作为参数选择的最小目标函数。

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

在RBF网络中，网络输入信号为2个，即u(k)和y(k)，网络初始权值及高斯函数参数初始值通过遗传算法优化而得。43

遗传算法优化程序为chap10_3a.m，取逼近总步骤为N=500，每一步的逼近误差及目标函数由chap10_3b.m求得。采用二进制编码方式，用长度为10位的二进制编码串来分别表示向量B、C和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]。取则共有12个参数需要优化。45

经过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网络高斯基函数参数的优化值及权值的优化值为:46RBF网络遗传算法优化程序包括三部分，即遗传算法优化程序chap10_3a.m、RBF网络逼近函数程序chap10_3b.m和RBF网络逼近测试程序chap10_3c.m。4710.7基于遗传算法的TSP问题优化旅行商问题（TravelingSalesmanProblem，TSP）：有N个城市，已知任意两个间的距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线总长度最短。旅行商问题是一个典型的组合优化问题，其可能的路径数目与城市数目N呈指数型增长的，一般很难精确的求出最优解，因而寻找其有效的近似求解算法具有重要的理论意义。很多实际应用问题经过简化处理后可转化为旅行商问题，因而对旅行商问题求解方法的研究具有重要的应用价值4910.7.1TSP问题的编码在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两种：（1）巡回旅行路线经过的连接两个城市的路线的顺序排列；（2）巡回旅行路线所经过的各个城市的顺序排列。大多数求解旅行商问题的遗传算法是以后者为描述方法的，它们大多采用所遍历城市的顺序来表示各个个体的编码串，其等位基因为N个整数值或N个记号。以城市的遍历顺序作为遗传算法的编码，目标函数取路径长度。在群体初始化、交叉操作和变异操作中考虑TSP问题的合法性约束条件（即对所有的城市做到不重不漏）。5110.7.2TSP问题的遗传算法设计采用遗传算法进行路径优化，分为以下几步：第一步：参数编码和初始群体设定对于TSP一类排序问题，采用对访问城市序列进行排列组合的方法编码，即染色体个体表示按顺序经过的城市序列。52N为城市总数，染色体长度为N+1，最后一位表示该路径总长度。参数编码和初始群体程序段为：pop=zeros(s,N+1);fori=1:spop(i,1:N)=randperm(N);%随机排列end

第二步：计算路径长度的函数设计以距离的总长度为适应度函数来衡量求解结果是否最优。设D={dij}是由城市i和城市j之间的距离组成的距离矩阵。计算路径长度的程序为chap10_1dis.m。目标函数：自适应度函数：54

第三步：计算选择算子群体中适应度最大的c个个体直接替换适应度最小的c个个体。选择算子函数为chap10_4select.m。num=1;%m11为当前种群中各个体的路径总长度whilenum<c+1%取距离大的c个个体

[a,mmax(num)]=max(m11);%选择当前种群中距离总长度最大值，并记录样本编号给mmax(num)m11(mmax(num))=0;%清除，防止再次被选中

%取距离小的c个个体

[~,mmin(num)]=min(m12);%chenyagm12(mmin(num))=a;%修改为很大的一个数，防止再次被选中

num=num+1;end%用距离大的c个个体替换距离小的c个个体pop(mmax,:)=pop(mmin,:);

第四步：计算交叉算子——有序交叉法步骤1：随机选取两个交叉点。步骤2：复制两交叉点之间的基因串A1和B1。56步骤3：在对应位置交换X1和X2双亲匹配段A1和B1以外的城市。57X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（1）将8复制到子代中，并检查是否与A1中的基因重复。58X1:98|45671|320A1X2:87|14032|965B183|45671|902A198|14032|756有序交叉算子（2）7在子串A1中存在，处于第4个位子。只好去B1的第4个基因位