Matlab与遗传算法 (2).ppt

《Matlab与遗传算法 (2).ppt》由会员分享，可在线阅读，更多相关《Matlab与遗传算法 (2).ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法理论遗传算法理论遗传算法的概要遗传算法的概要n问题的提出 对于一个求函数最大的优化问题一般可以描述为下述数学规划模型 式中，为决策变量，f(x)为目标函数，式(1-2),(1-3)为约束条件，U为基本空间，R是U的一个子集，称为可行集。总的来讲，求最优解或近似最优的方法主要有三种：枚举法，启发式算法和搜索算法，随着问题种类的不同和规模的扩大，上述方法都不理想，遗传算法遗传算法却提供了这类问题一个有效方法，开创了一种新的全局优化搜索算法。n遗传算法中，将N维决策向量 用n个记号Xi(i=1,2,.n)所组成的符号串X来表示：n把每个Xi看成一个遗传基因，它的所有可能取值称为等位基因，这样

2、，X就可看做是由n个遗传基因所组成的一个染色体。n 遗传算法中，决策变量X组成了问题的解空间。对问题最优的搜索是通过染色体X的搜索过程来进行的，从而由所有染色体X就组成了问题的搜索空间。遗传算法的基本概念和术语遗传算法的基本概念和术语n与生物界的进化过程相类比，遗传算法中有以下几个非常重要的概念和术语：n种群（种群（population）染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。有时个体的集合也称为个体群。n适应度（适应度（fitness）度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会。n选择（选择（selection）指决定以一定

3、的概率从种群中选择若干个体的操作。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。n交叉（交叉（crossover）将群体内的各个个体随机搭配成对，对每个个体以某个概率（交叉概率，交换它们之间的部分染色体，n变异（变异（mutation）对群体中的每个个体以某一概率（变异概率）改变某一个或某些基因座上的基因值为其它的等位基因。n编码（编码（coding）DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。n解码（解码（decoding）从遗传子型到表现型的映射。遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例（1）个体编码 x1

4、,x2取07之间的整数，可分别用3为无符 号二进制整数来表示，将它们连接成一起所组成的6位无符号二进制整数就形成个体的基因型，表示一个可行解。如基因型X=101110所对应的表现型是X=5,6.个体表现型和基因型X之间可通过编码和解码程序相互转换。（2）初始群体的产生 规模取4，随机产生（3）适应度计算 本例目标函数总取非负值，可求函数最大值为最优目标，以此计算个体的适应度。（4）选择运算 选择方法适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc（5）交叉运算 方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色

5、体(子辈染色体).新的子辈染色体:A 11010001 B 01011110（6）变异运算 GAGA的流程的流程遗传算法的特点遗传算法的特点n遗传算法以决策变量的编码作为运算对象。遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，而遗传算法是一决策变量的某种形式的编码为运算对象。n遗传算法直接以目标函数值作为搜索信息遗传算法直接以目标函数值作为搜索信息。传统算法不仅需要利用目标函数值，而且往往还需要目标函数的到数值等其它辅助信息。因而遗传算法避开了求导的障碍。n遗传算法同时使用多个搜索点的搜索信息。遗传算法同时使用多个搜索点的搜索信息。传统的优

6、化算法往往从解空间中的一个初始点开始迭代搜索过程。n遗传算法使用了概率搜索技术遗传算法使用了概率搜索技术 这优于传统算法的确定性搜索，因为从一个点到另一个点的确定性有可能使搜索永远达不到最优点遗传算法的基本实现技术遗传算法的基本实现技术BY朱诗颖朱诗颖1.1.编码方法编码方法2.2.适应度函数适应度函数3.3.选择算子选择算子4.4.交叉算子交叉算子5.5.变异算子变异算子6.6.遗传算法的运行参数遗传算法的运行参数编码方法编码方法 在遗传算法中，把一个问题的可行解从其解空间转换到遗传算在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。法所能处理的搜

7、索空间的转换方法称为编码。编码是遗传算法在首要解决的问题，它会影响到交叉算子，变异算子等运算方法，决定了运算的效率。DeJong提出了两条操作性较强的实用编码原则：一：应使用能易于产生与所求问题相关的且低阶，短定义长度模式的编码方案。二：应使用能使问题得到自然表示或描述的具体有最少编码字符集的编码方案。n目前主要的编码方法：n1.二进制编码方法n2.浮点数编码方法n3.符号编码方法二进制编码二进制编码n 遗传算法中最常用的一种编码方法，符号集是由二进制符号0和1所组成。符号串长度与问题所要求的解精度有关。取值范围是 ,假设用长度为二进制编码符号来表示，则能产生 种不同的的编码。若使编码对应关系

8、如下：格雷编码格雷编码n 格雷码的连续两个整数所对应的编码之间仅仅只有一个码位是不相同的。假设有一个二进制编码为B=，其对应的格雷码为G=，由二进制到格雷码的转换公式：n遗传算法的局部搜索能力差，变异操作一个基因座的差异，对应的参数值却很大，格雷码则克服了这个弱点。例如：对于区间0,1023中的两个邻近的整数x1=175和x2=176,若使用长度为10位的二进制编码为：x1=0010101111,x2=0010110000 而使用相同长度的格雷码：x1=0011111000,x2=0011101000;可见在进行变异操作后格雷码能保持稳定行，差异较小，相对提高了局部搜索能力，便于进行连续空间的

9、局部搜索。其它常见的编码其它常见的编码n浮点编码方法浮点编码方法：个体的每个基因值用某一范围的一个浮点数表示，个体的编码长度等于其决策变量的个数。例如某个优化问题有5个变量Xi(i=1,2,.5),每个变量都有其对应上下限 ,则X：就是一个基因型，对应表现型X=5.80,6.90,3.50,3.80,5.00。注意每个字节的限制范围！n符号编码方法符号编码方法：个体染色体编码串中的基因取自一个无数值含义，而只有代码含义的符号集。例如n个城市被访问顺序可构成一个旅行路线个体X：1,2,3,.n.n多参数级联编码方法多参数级联编码方法：针对多个变量的个体进行编码，每个参数可采用任何一种，有不同的上

10、下界和编码长度和精度。n多参数交叉编码方法多参数交叉编码方法：先对各个参数分组编码，再将各个参数编码串中的最高位连接在一起，再取次高位的连接一起以此类推。5.806.903.503.805.00适度函数适度函数n与自然界的优胜劣汰类似，在遗传算法里使用适应度来衡量群体中各个个体接近最优接的优良程度。度量适应度的函数称为适度函数。遗传算法中可以根据优化问题的类型，利用目标函数转化成适度函数。n设目标函数为f(x),适度函数为F(x)n最大值问题：n最小值问题：适应度尺度转换适应度尺度转换n主要的三种变换方法：n线性尺度变换：F=aF+b a,b为系数 条件一，变换后新适应度平均值要不改变 条件二

11、：变换后新的最大适应度要等于平均适应度指定的倍数n乘幂尺度变换n指数尺度变换选择算子选择算子n选择操作建立在对个体适应度的评价基础之上n最常用的选择算子是比例算子。一种回放式随机采样的方法。n基本思想：各个个体被选中的概率与其适应度的大小成正比。n 设群体大小为M，个体i的适应度为Fi,则个体被选中的概率为Pi用转轮方法进行选择交叉算子交叉算子n配对策略：随机配对，即将M个个体随机组成n随机设置交叉点n单点交叉 n双点交叉与多点交叉n均匀交叉n算术交叉 两个个体线性组合而产生两个新的个体变异算子变异算子n基本位变异 n均匀变异：依次指定个体编码中的每个基因座为变异点，并以变异概率Pi从对应基因

12、的取值范围中取一随机数来代替原有基因值，例如：遗传算法的运行参数遗传算法的运行参数n 遗传算法中需要选择的运行参数主要有n个体编码串长度L 与精度有关n群体大小M 一般20100n交叉概率Pi 一般取较大 0.40.99n变异概率Pm 建议0.0001-0.1n终止代数T 100-1000 n代沟G 每一代群体中被替换掉的个体在全部个体中的所占百分率例如G=1.0表示群体全部个体都是新产生的MATLAB遗传算法工具箱遗传算法工具箱1.GAOT工具箱2.gatbx工具箱 3.gads工具箱 Gaot主要函数列表主要函数列表gatbx工具箱函数列表工具箱函数列表Gads 工具箱工具箱n n基于图形

13、用户界面n n基于.M文件编写的函数文件适应度函数变量个数约束条件图形选项运行状态显示区尺度变换选择函数繁殖选项变异选项交叉选项算法停止条件迁移参数运算参数设定混合函数选项n遗传算法搜索函数最小值 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的

14、下界、上界nOptions：算法参数结构体常，通过：算法参数结构体常，通过gaoptimset函数来设定函数来设定实例演示实例演示 以以Rastringrin函数为例演示函数为例演示matlab遗传算法工具箱的使用遗传算法工具箱的使用f=20+x.2-10*cos(2*pi*x)+y.2-10*cos(2*pi*y),-5.12=x,y0 temp=Cmin+objvalue(i);else ntemp=0.0;end fitvalue(i)=temp;end fitvalue=fitvalue;n%2.4 选择复制%选择或复制操作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择，这种

15、方法较易实现。%根据方程 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 代种群 n遗传算法子程序 Name:selection.m%选择复制 function newpop=selection(pop,fitvalue)totalfit=sum(fitvalue);%求适应值之和 fitvalue=fitvalue/totalfit;%单个个

16、体被选择的概率 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);nnewpop(newin)=pop(fitin);newin=newin+1;else fitin=fitin+1;end end n 5.交叉 交叉(crossover)，群体中的

17、每个个体之间都以一定的概率 pc 交叉，即两个个体从各自字符串的某一位置（一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：x1=0100110 x2=1010001 n这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。事实上交又是遗传算法区别于其它传统优化方法的主要特点之一。遗传算法子程序 Name:crossover.m%交叉 function newpop=crossover(pop,pc)px,py=size(pop);newpop=ones(size(pop);for

18、 i=1:2:px-1 if(randpc)cpoint=round(rand*py);newpop(i,:)=pop(i,1:cpoint),pop(i+1,cpoint+1:py);nnewpop(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 n 2.6 变异 变异(mutation)，基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率 pm 翻转，即由“1”变为“0”，或由“0”变为“1”。遗传算法的变异特性可

19、以使求解过程随机地搜索到解可能存在的整个空间，因此可以在一定程度上求得全局最优解。n遗传算法子程序 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 mpointbestfit bestindividual=pop(i,:);bestfit=fitvalue(i);end end 2.8 主程序 遗传算法主程序 Name:genmain05.m function genmain

20、(popsize,n)chromlength=10;%字符串长度（个体长度）pc=0.6;%交叉概率 npm=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);%变异

21、 bestindividual,bestfit=best(pop,fitvalue);%求出群体中适应值最大的个体及其适应值 y(i)=max(bestfit);n(i)=i;npop5=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）