Matlab与遗传算法 (2).ppt

遗传算法理论,遗传算法的概要,问题的提出 对于一个求函数最大的优化问题一般可以描述为下述数学规划模型 式中，为决策变量，f(x)为目标函数，式(1-2),(1-3)为约束条件，U为基本空间，R是U的一个子集，称为可行集。总的来讲，求最优解或近似最优的方法主要有三种：枚举法，启发式算法和搜索算法，随着问题种类的不同和规模的扩大，上述方法都不理想，遗传算法却提供了这类问题一个有效方法，开创了一种新的全局优化搜索算法。,遗传算法中，将N维决策向量 用n个记号Xi(i=1,2,.n)所组成的符号串X来表示：把每个Xi看成一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。遗传算法中，决策变量X组成了问题的解空间。对问题最优的搜索是通过染色体X的搜索过程来进行的，从而由所有染色体X就组成了问题的搜索空间。,遗传算法的基本概念和术语,与生物界的进化过程相类比，遗传算法中有以下几个非常重要的概念和术语：种群（population）染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。适应度（fitness）度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会。选择（selection）指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。,交叉（crossover）将群体内的各个个体随机搭配成对，对每个个体以某个概率（交叉概率，交换它们之间的部分染色体，变异（mutation）对群体中的每个个体以某一概率（变异概率）改变某一个或某些基因座上的基因值为其它的等位基因。编码（coding）DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。解码（decoding）从遗传子型到表现型的映射。,遗传算法的手工模拟计算示例,（1）个体编码 x1,x2取07之间的整数，可分别用3为无符 号二进制整数来表示，将它们连接成一起所组成的6位无符号二进制整数就形成个体的基因型，表示一个可行解。如基因型X=101110所对应的表现型是X=5,6.个体表现型和基因型X之间可通过编码和解码程序相互转换。（2）初始群体的产生 规模取4，随机产生（3）适应度计算 本例目标函数总取非负值，可求函数最大值为最优目标，以此计算个体的适应度。,（4）选择运算,选择方法适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc,（5）交叉运算,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体:A 11010001 B 01011110（6）变异运算,GA的流程,遗传算法的特点,遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，而遗传算法是一决策变量的某种形式的编码为运算对象。遗传算法直接以目标函数值作为搜索信息。传统算法不仅需要利用目标函数值，而且往往还需要目标函数的到数值等其它辅助信息。因而遗传算法避开了求导的障碍。遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往从解空间中的一个初始点开始迭代搜索过程。遗传算法使用了概率搜索技术 这优于传统算法的确定性搜索，因为从一个点到另一个点的确定性有可能使搜索永远达不到最优点,遗传算法的基本实现技术BY朱诗颖,1.编码方法2.适应度函数3.选择算子4.交叉算子5.变异算子6.遗传算法的运行参数,编码方法,在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。编码是遗传算法在首要解决的问题，它会影响到交叉算子，变异算子等运算方法，决定了运算的效率。DeJong提出了两条操作性较强的实用编码原则：一：应使用能易于产生与所求问题相关的且低阶，短定义长度模式的编码方案。二：应使用能使问题得到自然表示或描述的具体有最少编码字符集的编码方案。目前主要的编码方法：1.二进制编码方法2.浮点数编码方法3.符号编码方法,二进制编码,遗传算法中最常用的一种编码方法，符号集是由二进制符号0和1所组成。符号串长度与问题所要求的解精度有关。取值范围是,假设用长度为二进制编码符号来表示，则能产生 种不同的的编码。若使编码对应关系如下：,格雷编码,格雷码的连续两个整数所对应的编码之间仅仅只有一个码位是不相同的。假设有一个二进制编码为B=，其对应的格雷码为G=，由二进制到格雷码的转换公式：遗传算法的局部搜索能力差，变异操作一个基因座的差异，对应的参数值却很大，格雷码则克服了这个弱点。例如：对于区间0,1023中的两个邻近的整数x1=175和x2=176,若使用长度为10位的二进制编码为：x1=0010101111,x2=0010110000 而使用相同长度的格雷码：x1=0011111000,x2=0011101000;可见在进行变异操作后格雷码能保持稳定行，差异较小，相对提高了局部搜索能力，便于进行连续空间的局部搜索。,其它常见的编码,浮点编码方法：个体的每个基因值用某一范围的一个浮点数表示，个体的编码长度等于其决策变量的个数。例如某个优化问题有5个变量Xi(i=1,2,.5),每个变量都有其对应上下限,则X：就是一个基因型，对应表现型X=5.80,6.90,3.50,3.80,5.00。注意每个字节的限制范围！符号编码方法：个体染色体编码串中的基因取自一个无数值含义，而只有代码含义的符号集。例如n个城市被访问顺序可构成一个旅行路线个体X：1,2,3,.n.多参数级联编码方法：针对多个变量的个体进行编码，每个参数可采用任何一种，有不同的上下界和编码长度和精度。多参数交叉编码方法：先对各个参数分组编码，再将各个参数编码串中的最高位连接在一起，再取次高位的连接一起以此类推。,适度函数,与自然界的优胜劣汰类似，在遗传算法里使用适应度来衡量群体中各个个体接近最优接的优良程度。度量适应度的函数称为适度函数。遗传算法中可以根据优化问题的类型，利用目标函数转化成适度函数。设目标函数为f(x),适度函数为F(x)最大值问题：最小值问题：,适应度尺度转换,主要的三种变换方法：线性尺度变换：F=aF+b a,b为系数 条件一，变换后新适应度平均值要不改变 条件二：变换后新的最大适应度要等于平均适应度指定的倍数乘幂尺度变换指数尺度变换,选择算子,选择操作建立在对个体适应度的评价基础之上最常用的选择算子是比例算子。一种回放式随机采样的方法。基本思想：各个个体被选中的概率与其适应度的大小成正比。设群体大小为M，个体i的适应度为Fi,则个体被选中的概率为Pi,用转轮方法进行选择,交叉算子,配对策略：随机配对，即将M个个体随机组成随机设置交叉点单点交叉 双点交叉与多点交叉,均匀交叉算术交叉 两个个体线性组合而产生两个新的个体,变异算子,基本位变异 均匀变异：依次指定个体编码中的每个基因座为变异点，并以变异概率Pi从对应基因的取值范围中取一随机数来代替原有基因值，例如：,遗传算法的运行参数,遗传算法中需要选择的运行参数主要有个体编码串长度L 与精度有关群体大小M 一般20100交叉概率Pi 一般取较大 0.40.99变异概率Pm 建议0.0001-0.1终止代数T 100-1000 代沟G 每一代群体中被替换掉的个体在全部个体中的所占百分率例如G=1.0表示群体全部个体都是新产生的,MATLAB遗传算法工具箱,1.GAOT工具箱2.gatbx工具箱 3.gads工具箱,Gaot主要函数列表,gatbx工具箱函数列表,Gads 工具箱,基于图形用户界面基于.M文件编写的函数文件,适应度函数,变量个数,约束条件,图形选项,运行状态显示区,尺度变换,选择函数,繁殖选项,变异选项,交叉选项,算法停止条件,迁移参数,运算参数设定,混合函数选项,遗传算法搜索函数最小值 x,fval,exitFlag,output,population,scores=ga(FUN,GenomeLength,Aineq,Bineq,Aeq,Beq,LB,UB,nonlcon,options)X:适应点值 fval:适应度函数在x点处的函数值 FUN：适应函数 GenomeLength：个体基因长度 Aineq,Bineq,Aeq,Beq，nonlcon：约束条件参数 LB,UB：x的下界、上界,Options：算法参数结构体常，通过gaoptimset函数来设定,实例演示 以Rastringrin函数为例演示matlab遗传算法工具箱的使用f=20+x.2-10*cos(2*pi*x)+y.2-10*cos(2*pi*y),-5.12=x,y=5.12,1.函数法直接在matlab命令行里输入rafitness,运行结果：x=1.0e-008*-0.1663 0.0263fval=0,2.用GUI图形界面直接在Fitness funtion框里输入rastriginsfcn；输入变量个数为2，设定繁殖代数为150代。在plot区里可以勾选希望看到的结果图像设置完参数之后点击start按钮就可以运行了,GUI演示图：,运行结果：,遗传算法实例示范,作者：张健,函数优化实例,求函数f(x)=10*sin(5x)+7*cos(4x)的最大值，其中x0,10 将 x 的值用一个10位的二值形式表示为二值问题，一个10位的二值数提供的分辨率是每为(10-0)/(210-1)0.01。将变量域 0,10 离散化为二值域 0,1023,x=10*b/1023,其中 b 是 0,1023 中的一个二值数。1.编码initpop.m函数的功能是实现群体的初始化，popsize表示群体的大小，chromlength表示染色体的长度(二值数的长度)，长度大小取决于变量的二进制编码的长度(在本例中取10,位)。遗传算法子程序 Name:initpop.m%初始化 function pop=initpop(popsize,chromlength)pop=round(rand(popsize,chromlength);%rand随机产生每个单元为0或1，行数为popsize，列数为chromlength的矩阵。这样产生的初始种群。2.计算目标函数值2.1将二进制数转化为十进制数 遗传算法子程序 Name:decodebinary.m%产生 2n 2(n-1).1 的行向量，然后求和，将二进制转化为十进制,function pop2=decodebinary(pop)px,py=size(pop);%求pop行和列数 for i=1:py pop1(:,i)=2.(py-i).*pop(:,i);end pop2=sum(pop1,2);%求pop1的每行之和2.2 将二进制编码转化为十进制数(2)decodechrom.m函数的功能是将染色体(或二进制编码)转换为十进制，参数spoint表示待解码的二进制串的起始位置(对于多个变量而言，如有两个变量，采用20位表示，每个变量10位，则第一个变量从1开始，另一个变量从11开始。本例为1)参数1ength表示所截取的长度（本例为10）。,遗传算法子程序 Name:decodechrom.m%将二进制编码转换成十进制 function pop2=decodechrom(pop,spoint,length)pop1=pop(:,spoint:spoint+length-1);pop2=decodebinary(pop1);2.3 计算目标函数值 calobjvalue.m函数的功能是实现目标函数的计算，其公式采用本文示例仿真，可根据不同优化问题予以修改。遗传算法子程序 Name:calobjvalue.m%实现目标函数的计算 function objvalue=calobjvalue(pop)temp1=decodechrom(pop,1,10);%将pop每行转化成十进制,x=temp1*10/1023;%将二值域 中的数转化为变量域 的数 objvalue=10*sin(5*x)+7*cos(4*x);%计算目标函数值 3 计算个体的适应值 遗传算法子程序 Name:calfitvalue.m%计算个体的适应值 function fitvalue=calfitvalue(objvalue)global Cmin;Cmin=0;px,py=size(objvalue);for i=1:px if objvalue(i)+Cmin0 temp=Cmin+objvalue(i);else,temp=0.0;end fitvalue(i)=temp;end fitvalue=fitvalue;%2.4 选择复制%选择或复制操作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择，这种方法较易实现。%根据方程 pi=fi/fi=fi/fsum，选择步骤：%1）在第 t 代，由（1）式计算 fsum 和 pi%2）产生 0,1 的随机数 rand(.)，求 s=rand(.)*fsum%3）求 fis 中最小的 k，则第 k 个个体被选中%4）进行 N 次2）、3）操作，得到 N 个个体，成为第 t=t+1 代种群,遗传算法子程序 Name:selection.m%选择复制 function newpop=selection(pop,fitvalue)totalfit=sum(fitvalue);%求适应值之和 fitvalue=fitvalue/totalfit;%单个个体被选择的概率 fitvalue=cumsum(fitvalue);%如 fitvalue=1 2 3 4，则 cumsum(fitvalue)=1 3 6 10 px,py=size(pop);ms=sort(rand(px,1);%从小到大排列 fitin=1;newin=1;while newin=px if(ms(newin)fitvalue(fitin)newpop(newin)=pop(fitin);,newpop(newin)=pop(fitin);newin=newin+1;else fitin=fitin+1;end end 5.交叉 交叉(crossover)，群体中的每个个体之间都以一定的概率 pc 交叉，即两个个体从各自字符串的某一位置（一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：x1=0100110 x2=1010001,这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。事实上交又是遗传算法区别于其它传统优化方法的主要特点之一。遗传算法子程序 Name:crossover.m%交叉 function newpop=crossover(pop,pc)px,py=size(pop);newpop=ones(size(pop);for i=1:2:px-1 if(randpc)cpoint=round(rand*py);newpop(i,:)=pop(i,1:cpoint),pop(i+1,cpoint+1:py);,newpop(i+1,:)=pop(i+1,1:cpoint),pop(i,cpoint+1:py);else newpop(i,:)=pop(i);newpop(i+1,:)=pop(i+1);end end 2.6 变异 变异(mutation)，基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率 pm 翻转，即由“1”变为“0”，或由“0”变为“1”。遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间，因此可以在一定程度上求得全局最优解。,遗传算法子程序 Name:mutation.m%变异 function newpop=mutation(pop,pm)px,py=size(pop);newpop=ones(size(pop);for i=1:px if(randpm)mpoint=round(rand*py);if mpoint=0 mpoint=1;end newpop(i)=pop(i);if any(newpop(i,mpoint)=0 newpop(i,mpoint)=1;,else newpop(i,mpoint)=0;end else newpop(i)=pop(i);end end 7.求出群体中最大的适应值及其个体 遗传算法子程序 Name:best.m%求出群体中适应值最大的值 function bestindividual,bestfit=best(pop,fitvalue)px,py=size(pop);bestindividual=pop(1,:);,bestfit=fitvalue(1);for i=2:px if fitvalue(i)bestfit bestindividual=pop(i,:);bestfit=fitvalue(i);end end 2.8 主程序 遗传算法主程序 Name:genmain05.m function genmain(popsize,n)chromlength=10;%字符串长度（个体长度）pc=0.6;%交叉概率,pm=0.001;%变异概率 pop=initpop(popsize,chromlength);%随机产生初始群体 for i=1:20%20为迭代次数 objvalue=calobjvalue(pop);%计算目标函数 fitvalue=calfitvalue(objvalue);%计算群体中每个个体的适应度 newpop=selection(pop,fitvalue);%复制 newpop=crossover(pop,pc);%交叉 newpop=mutation(pop,pc);%变异 bestindividual,bestfit=best(pop,fitvalue);%求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit);n(i)=i;,pop5=bestindividual;x(i)=decodechrom(pop5,1,chromlength)*10/1023;pop=newpop;end fplot(10*sin(5*x)+7*cos(4*x),0 10)hold on plot(x,y,r*)hold off z index=max(y);%计算最大值及其位置 x=x(index)%计算最大值对应的x值 y=z,在MATLAB命令串口输入genmain（20，20）,