遗传算法实现及应用举例.pptx

《遗传算法实现及应用举例.pptx》由会员分享，可在线阅读，更多相关《遗传算法实现及应用举例.pptx（158页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、SGA实现实现个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是负数。第1页/共158页为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：方法一：对于目标函数是求极大化，方法为：第2页/共158页式中，为一个适当地相对比较小的数它可用下面几种方法

2、之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。第3页/共158页比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette Wheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。第4页/共158页单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群

3、体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。第5页/共158页基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。第6页/共158页简单演示问题：求问题：求（1）编码：）编码：编码长度为编码长度为5（2）初始群体生成：群体大小设置为）初始群体生成：群体大小设置为4，随机产，随机产生四个个体：生四个个体：编码：编

4、码：01101，11000，01000，10011 解码：解码：13 24 8 19 适应度：适应度：169 576 64 361（3）适应度函数：）适应度函数：第7页/共158页（4）轮盘赌轮盘赌选择：选择概率选择：选择概率 个体：个体：01101，11000，01000，10011 适应度：适应度：169 576 64 361 选择概率：选择概率：0.14 0.49 0.06 0.31选择选择 11000 和和 01101交配产生下一代交配产生下一代第8页/共158页（5）交叉操作：发生交叉的概率取大）交叉操作：发生交叉的概率取大交叉点位置的选取是随机的（单点交叉）交叉点位置的选取是随机的

5、（单点交叉）0110 1 0110 0 1100 0 1100 1第9页/共158页（6）变异：发生变异的概率取小）变异：发生变异的概率取小改变某个字节改变某个字节 11001 11101（7）新群体的产生：）新群体的产生：保留上一代最优个体，保留上一代最优个体，1个新个体取代旧个体个新个体取代旧个体 11101，11000，01000，10011（8）重复上述操作）重复上述操作20次，次，或许就能够得到最优解或许就能够得到最优解！第10页/共158页应用实例：TSP问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学

6、描述给定图G=(V,E),V 为顶点集,E为边集，确定一条长度最短的Hamilton回路第11页/共158页TSP问题问题复杂度:指数增长的！(NP完全问题)12个城市，具有39916800条不同的路径。一条路径对应一个排列！交叉算子传统的交叉算子可能产生无效路径。第12页/共158页交叉算子（1）基于位置的交叉 把一个父代在向量上的被选元的位置强加到另一个父代。父代1：1 2 3 4 5 6 7 8 9 10父代2：5 9 2 4 6 1 10 7 3 8所选位置：*子代1：1 9 2 3 6 4 5 7 8 10子代2：9 2 3 4 5 6 1 8 10 7第13页/共158页交叉算子（

7、2）部分映射交叉利用父代所选段内元的对应定义子代。父代1：2 6 4 3 8 1 5 10 7 9父代2：8 5 1 10 7 6 2 4 3 9子代1：5 1 4 3 7 6 2 10 8 9子代2：7 2 6 10 8 1 5 4 3 9第14页/共158页变异算子起双重作用：1、提供和保持群体的多样性；2、搜索算子的作用。(1)基于位置的变异：随机选择两个元，然后把第二个元放在第一个元之前；(2)基于次序的变异：随机选择两个元，然后交换他们的位置；(3)打乱变异：随机选择一段，然后打乱这段内的次序。第15页/共158页编码方案路径表达：对一个旅行最自然的表达一个旅行 517894623

8、的编码就是（5 1 7 8 9 4 6 2 3）编码空间和解空间一一对应，总量为n!个？其实一些解是相同的，因为（5 1 7 8 9|4 6 2 3）=（4 6 2 3|5 1 7 8 9）二者是同一个解(n-1)!/2应用实例1：TSP第16页/共158页适应度函数就取为目标函数的倒数，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定第17页/共158页.p1p2pir选择操作算子:轮盘式选择首先计算每个个体 i 被选中的概率然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为 。选择时转动轮盘，参考点r落到扇形i则选择个体i。第18页/共158页交叉操作算子

9、Davis提出OX算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代例如：p1=（1 2 3|4 5 6 7|8 9）p2=（4 5 2|1 8 7 6|9 3）首先保持中间部分 o1=（X X X|4 5 6 7|X X）o2=（X X X|1 8 7 6|X X）第19页/共158页交叉操作算子然后移走p2中已在o1中的城市4、5、6和7后，得到21893该序列顺次放在o1中：o1=（2 1 8|4 5 6 7|9 3）类似地，可以得到另一个后代：o2=（2 3 4|1 8 7 6|5 9）第20页/共158页变异操作算子采用倒置变异：在染色体上随机地选择两点

10、，将两点间的子串反转例如原个体：（1 2 3 4 5 6 7 8 9）随机选择两点：（1 2|3 4 5 6|7 8 9）倒置后的个体：（1 2|6 5 4 3|7 8 9）第21页/共158页第22页/共158页中国城市TSP的一个参考解第23页/共158页应用实例2：函数优化函数优化编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处理，然后根据离散化后待定解的个数选择合适长度的二进制字符串进行编码例如；0，1，计算精度0.001,则0，0.001,0.002,0.998,0.999,1.000，个数为1001则用长度为10的二进制字符串一次表征所有离散点0000000000，00

11、0000001，1111110001。第24页/共158页适应度函数例如，f(x)=x2-x5，取Cmax=2,即可得到满足要求的F(x)其它的就类似于TSP的求解了第25页/共158页 已知函数 其中 ，用遗传算法求解y的最大值。例1 多元函数优化问题第26页/共158页运行步骤第27页/共158页运行步骤第28页/共158页运行步骤第29页/共158页运行步骤第30页/共158页运行步骤第31页/共158页运行步骤第32页/共158页运行步骤第33页/共158页第34页/共158页 例例2 一元函数优化问题一元函数优化问题问题的提出问题的提出 一元函数求最大值：一元函数求最大值：第35页/

12、共158页问题的提出问题的提出 用微分法求取用微分法求取 f(x)的最大值：的最大值：解有无穷多个：解有无穷多个：第36页/共158页问题的提出问题的提出 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对对应局部极小值。应局部极小值。x19即为区间即为区间-1,2内的最大值点内的最大值点 此时，函数最大值此时，函数最大值 f(x19)比比f(1.85)=3.85稍大。稍大。第37页/共158页编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）串长与精度之间的关系串长与精度之间的关系：若要求求解精度

13、到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为，即需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。第38页/共158页产生产生初始种群初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，1111010011100001011000 1100110011101010101110 1010100011110010000100 101111001001110011

14、1001 0001100101001100000011 0000011010010000000000 第39页/共158页计算适应度计算适应度 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数本例：直接用目标函数作为适应度函数 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数：s=x=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.586345第40页/共158页计算适应度计算适应度 二进制与十进制之间的转换二进制与十进制之间的转换：第一步，将一个二进制串（第一步，将一

15、个二进制串（b21b20b0）转化为）转化为10进制数：进制数：第二步，第二步，x对应的区间对应的区间-1,2内的实数：内的实数：(0000000000000000000000)-1(1111111111111111111111)2第41页/共158页遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法；交叉：单点交叉；交叉：单点交叉；变异：小概率变异变异：小概率变异第42页/共158页模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最；最大代数大代数200。得到的最佳个体得到的最佳个体：smax=;xmax=1.850

16、6;f(xmax)=3.8503;第43页/共158页模拟结果模拟结果 进化的过程进化的过程：世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503第44页/共158页主程序主程序%用遗传算法进行简单函数的优化用遗传算法进行简单函数的优化clearbn=22;%个体串长度个体串长度inn=50;%初始种群大小初始种群大小gnmax=200;%最大代数最大代数pc=0.75;%交叉概率交叉概率

17、pm=0.05;%变异概率变异概率Continue 算法的设计与实现算法的设计与实现 第45页/共158页主程序主程序%产生初始种群，产生初始种群，0,1向量向量s=round(rand(inn,bn);%计算适应度计算适应度,返回适应度返回适应度f和累积概率和累积概率pf,p=objf(s);Continue第46页/共158页主程序主程序 gn=1;while gngnmax+1 for j=1:2:inn%选择操作选择操作 seln=sel(s,p);%交叉操作交叉操作 scro=cro(s,seln,pc);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(

18、2,:);%变异操作变异操作 smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue第47页/共158页主程序主程序 s=smnew;%产生了新的种群产生了新的种群%计算新种群的适应度计算新种群的适应度 f,p=objf(s);%记录当前代最好和平均的适应度记录当前代最好和平均的适应度 fmax,nmax=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue第48页/共158页主程序主程序%记录当前代的最佳个体记录当前代的最佳个体 x

19、=n2to10(s(nmax,:);xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;gn=gn+1endgn=gn-1;Continue第49页/共158页主程序主程序%绘制曲线绘制曲线subplot(2,1,1);plot(1:gn,ymax;ymean);title(历代适应度变化历代适应度变化,fonts,10);legend(最大适应度最大适应度,平均适应度平均适应度);string1=最终适应度最终适应度,num2str(ymax(gn);gtext(string1);subplot(2,1,2);plot(1:gn,xmax,r-);legend(自

20、变量自变量);string2=最终自变量最终自变量,num2str(xmax(gn);gtext(string2);End第50页/共158页计算适应度和累计概率函数计算适应度和累计概率函数%计算适应度函数计算适应度函数function f,p=objf(s);r=size(s);%读取种群大小读取种群大小inn=r(1);%有有inn个个体个个体bn=r(2);%个体长度为个体长度为bnContinue第51页/共158页计算适应度和累计概率函数计算适应度和累计概率函数 for i=1:inn x=n2to10(s(i,:);%将将二进制转换为十进制二进制转换为十进制 xx=-1.0+x*3

21、/(power(2,bn)-1);%转化为转化为-1,2区间的实数区间的实数 f(i)=ft(xx);%计算函数值，即适应度计算函数值，即适应度endf=f;%行向量转列向量行向量转列向量Continue第52页/共158页计算适应度和累计概率函数计算适应度和累计概率函数%计算选择概率计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i)*f(i);endfor i=1:inn ps(i)=f(i)*f(i)/fsum;endContinue第53页/共158页计算适应度和累计概率函数计算适应度和累计概率函数%计算累积概率计算累积概率p(1)=ps(1);for i=2

22、:inn p(i)=p(i-1)+ps(i);endp=p;Back to main.m第54页/共158页计算目标函数值函数计算目标函数值函数%目标函数目标函数function y=ft(x);y=x.*sin(10*pi*x)+2;Back to objf.m第55页/共158页函数函数n2to10()Continue function x=n2to10(s)x=0;for j=1:22 x=x+s(j)*2(22-j);end function x=n2to10(s)x=s(1);for j=1:21 x=x*2+s(j+1);end 第56页/共158页选择操作函数选择操作函数%“选择

23、选择”操作操作function seln=sel(s,p);inn=size(p,1);%从种群中选择两个个体从种群中选择两个个体for i=1:2 r=rand;%产生一个随机数产生一个随机数 prand=p-r;j=1;while prand(j)d）；）；遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 第147页/共158页用遗传算法进行特征提取用遗传算法进行特征提取 个体的表示方法：一个长度为个体的表示方法：一个长度为L的个体对应于一的个体对应于一个个L维的二进制特征矢量，它的每一位就表示包维的二进制特征矢量，它的每一位就

24、表示包括或排除一个相应的特征。一个个体即是一个括或排除一个相应的特征。一个个体即是一个可能的最优特征子集；可能的最优特征子集；适应度函数的设计：个体所代表的特征子集进适应度函数的设计：个体所代表的特征子集进行分类时的识别率；行分类时的识别率；遗传算子：可采用各种方法；遗传算子：可采用各种方法；遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 第148页/共158页用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 将图像分为将图像分为mn格，对每一个格格，对每一个格 进行数据分析，得到进行数据分析，得到L个特征，

25、个特征，从从L中选出中选出l个（个（Ll）特征送入）特征送入 分类器进行识别。分类器进行识别。遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 第149页/共158页用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 个体的表示：个体的表示：l位长，每位代表一个特征的序号，位长，每位代表一个特征的序号，不可重复；不可重复；适应度函数的设计：识别率的函数；适应度函数的设计：识别率的函数；遗传算子：符合个体编码要求的算子。遗传算子：符合个体编码要求的算子。遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式

26、识别中的应用在模式识别中的应用在模式识别中的应用 第150页/共158页遗传算法今后研究的主要课题1、优化搜索方法的研究2、学习系统的遗传算法研究3、生物进化与遗传算法的研究4、遗传算法的并行分布处理5、人工生命与遗传算法的研究第151页/共158页GA 研究内容与方向算法性能研究混合算法研究并行算法研究算法应用研究第152页/共158页与GA相关的重要学术期刊与国际会议重要学术期刊Evolutionary ComputationIEEE Transactions on Evolutionary Computation重要国际会议International Conference on Gene

27、tic AlgorithmACM Genetic and Evolutionary Computation ConferenceWorkshop on Foundations of Genetic Algorithms and Classifier SystemsGenetic Programming ConferenceInternational Workshop on Artificial Life第153页/共158页混合遗传算法爬山法模拟退火算法最速下降法其它局部搜索算法遗传算法第154页/共158页并行组合模拟退火算法并行模拟退火遗传算法贪婪遗传算法遗传比率切割算法遗传爬山法引入局部改善操作的混合遗传算法免疫遗传算法混合遗传算法第155页/共158页 练习题练习题 用遗传算法解决下面函数的极小值问题：用遗传算法解决下面函数的极小值问题：第156页/共158页要求要求 1.遗传算法的具体实施策略不限；遗传算法的具体实施策略不限；2.用用MATLAB；3.上交内容包括：源程序和运行结果（图、表上交内容包括：源程序和运行结果（图、表等，等，WORD文档），发送至文档），发送至第157页/共158页感谢您的观看！第158页/共158页