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

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

1、第六节 算法实现及应用一、算法实现遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定问题编码方案确定问题编码方案确定适配值函数确定适配值函数设计遗传算子（选择、交叉、变异）设计遗传算子（选择、交叉、变异）确定算法参数确定算法参数确定算法终止条件确定算法终止条件生成初始种群生成初始种群SGA实现个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。

2、为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是负数。为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：方法一：对于目标函数是求极大化，方法为：式中，为一个适当地相对比较小的数它可用下面几种方法之一来选取:预先指定的一个较小的数；预先指定的一个较小的数；进化到当前代为止的最小目标函数值；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。当前代或最近几代群体中的最小目标值。比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette Wheel)选择，因为这种选择方式与赌博

3、中的赌盘操作原理非常相似。比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。单点交叉算子单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。基本位变异算子基本位变异算子的具体执行过程为：对个体的每一个基因

4、座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。简单演示问题：求问题：求（1）编码：）编码：编码长度为编码长度为5（2）初始群体生成：群体大小设置为）初始群体生成：群体大小设置为4，随机产，随机产生四个个体：生四个个体：编码：编码：01101，11000，01000，10011 解码：解码：13 24 8 19 适应度：适应度：169 576 64 361（3）适应度函数：）适应度函数：（4）轮盘赌轮盘赌选择：选择概率选择：选择概率 个体：个体：01101，11000，01000，10011 适应度：适应度：169 5

5、76 64 361 选择概率：选择概率：0.14 0.49 0.06 0.31选择选择 11000 和和 01101交配产生下一代交配产生下一代（5）交叉操作：发生交叉的概率取大）交叉操作：发生交叉的概率取大交叉点位置的选取是随机的（单点交叉）交叉点位置的选取是随机的（单点交叉）0110 1 0110 0 1100 0 1100 1（6）变异：发生变异的概率取小）变异：发生变异的概率取小改变某个字节改变某个字节 11001 11101（7）新群体的产生：）新群体的产生：保留上一代最优个体，保留上一代最优个体，1个新个体取代旧个体个新个体取代旧个体 11101，11000，01000，10011

6、（8）重复上述操作）重复上述操作20次，次，或许就能够得到最优解！或许就能够得到最优解！应用实例：TSP问题回顾给定给定n个城市以及两两城市之间的距离，个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市历所有其它城市并最终又回到起始城市的最短路径。的最短路径。数学描述给定图给定图G=(V,E),V为顶点集为顶点集,E为边集，为边集，确定一条长度最短的确定一条长度最短的Hamilton回路回路TSP问题问题问题复杂度问题复杂度:指数增长的！指数增长的！(NP完全问题完全问题)12个城市，具有个城市，具有399168

7、00条不同的路径。条不同的路径。一条路径对应一个排列！一条路径对应一个排列！交叉算子交叉算子传统的交叉算子可能产生无效路径。传统的交叉算子可能产生无效路径。交叉算子交叉算子（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交叉算子交叉算子（2）部分映射交叉）部分映射交叉利用父代所选

8、段内元的对应定义子代。利用父代所选段内元的对应定义子代。父代父代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变异算子变异算子起双重作用：起双重作用：1、提供和保持群体的多样性；、提供和保持群体的多样性；2、搜索算子的作用。、搜索算子的作用。(1)基于位置的变异：基于位置的变异：随机选择两个元，随机选择两个元，然后把第二个元放在第一个元之前；然后把第二个元放在第一个元之前；(2)基于次序的变异：基于次序的变异：随机选择两个元，随机选择两个元，

9、然后交换他们的位置；然后交换他们的位置；(3)打乱变异：打乱变异：随机选择一段，然后打乱随机选择一段，然后打乱这段内的次序。这段内的次序。编码方案路径表达：路径表达：对一个旅行最自然的表达对一个旅行最自然的表达一个旅行一个旅行 517894623 的编码就是（的编码就是（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 1：TSPTSP适应度函数就取为目

10、标函数的倒数，即路径总长就取为目标函数的倒数，即路径总长度的倒数度的倒数初始种群随机生成随机生成40个个终止条件2000次迭代次迭代参数设置自定自定.p1p2pir选择操作算子选择操作算子:轮盘式选择轮盘式选择首先计算每个个体首先计算每个个体 i 被选中被选中的概率的概率然后根据概率的大小将将圆然后根据概率的大小将将圆盘分为盘分为 n个扇形，每个扇形个扇形，每个扇形的大小为的大小为 。选择时转。选择时转动轮盘，参考点动轮盘，参考点r落到扇形落到扇形i则选择个体则选择个体i。交叉操作算子Davis提出提出OX算子：通过从一个亲体中算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体挑选一个子

11、序列旅行并保存另一个亲体的城市相对次序来构造后代的城市相对次序来构造后代例如：例如：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）交叉操作算子然后移走然后移走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）变异操作算子采用

12、倒置变异：在染色体上随机地选择采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转两点，将两点间的子串反转例如例如原个体：（原个体：（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）中国城市TSP的一个参考解应用实例2：函数优化函数优化编码方案采用二进制编码编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处对子变量定义域根据计算精度进行离散化处理，理，然后根据离散化后待定解的个数选择合适长然后根据离散化后待定解的个数选择合适长度的度的二进制字符串进行编码二

13、进制字符串进行编码例如；例如；0，1，计算精度，计算精度0.001,则则0，0.001,0.002,0.998,0.999,1.000，个数为个数为1001则用长度为则用长度为10的二进制字符串一次表征所有的二进制字符串一次表征所有离散离散点点0000000000，000000001，1111110001。适应度函数例如，例如，f(x)=x2-x5，取，取Cmax=2,即可得到即可得到满足要求的满足要求的F(x)其它的就类似于TSP的求解了 已知函数已知函数 其中其中 ，用遗传算法求解，用遗传算法求解y的的最大值。最大值。例1 多元函数优化问题运行步骤运行步骤运行步骤运行步骤运行步骤运行步骤运

14、行步骤 例例2 一元函数优化问题一元函数优化问题问题的提出问题的提出 一元函数求最大值：一元函数求最大值：问题的提出问题的提出 用微分法求取用微分法求取 f(x)的最大值：的最大值：解有无穷多个：解有无穷多个：问题的提出问题的提出 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对对应局部极小值。应局部极小值。x19即为区间即为区间-1,2内的最大值点内的最大值点 此时，函数最大值此时，函数最大值 f(x19)比比f(1.85)=3.85稍大。稍大。编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度）

15、串长与精度之间的关系串长与精度之间的关系：若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为，即需将区间分为3/0.000001=3106等份。等份。所以编码的二进制串长应为所以编码的二进制串长应为22位。位。产生产生初始种群初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50，计算适应度计算适应度 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法 本例：直接用目标函数作为适应度函数本例：直接用目标

16、函数作为适应度函数 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数：sx=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.586345计算适应度计算适应度 二进制与十进制之间的转换二进制与十进制之间的转换：第一步，将一个二进制串（第一步，将一个二进制串（b21b20b0）转化为）转化为10进制数：进制数：第二步，第二步，x对应的区间对应的区间-1,2内的实数：内的实数：(0000000000000000000000)-1遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法；交叉：单点交叉；交叉：单点交叉；变异：小概

17、率变异变异：小概率变异模拟结果模拟结果 设置的参数设置的参数：种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最；最大代数大代数200。得到的最佳个体得到的最佳个体：smax xmax=1.8506;f(xmax)=3.8503;模拟结果模拟结果 进化的过程进化的过程：主程序主程序%用遗传算法进行简单函数的优化用遗传算法进行简单函数的优化clearbn=22;%个体串长度个体串长度inn=50;%初始种群大小初始种群大小gnmax=200;%最大代数最大代数pc=0.75;%交叉概率交叉概率pm=0.05;%变异概率变异概率Continue 算法的设计与实现算法的

18、设计与实现 主程序主程序%产生初始种群，产生初始种群，0,1向量向量s=round(rand(inn,bn);%计算适应度计算适应度,返回适应度返回适应度f和累积概率和累积概率pf,p=objf(s);Continue主程序主程序 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(2,:);%变异操作变异操作 smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)

19、=mut(scnew(j+1,:),pm);endContinue主程序主程序 s=smnew;%产生了新的种群产生了新的种群%计算新种群的适应度计算新种群的适应度 f,p=objf(s);%记录当前代最好和平均的适应度记录当前代最好和平均的适应度 fmax,nmax=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue主程序主程序%记录当前代的最佳个体记录当前代的最佳个体 x=n2to10(s(nmax,:);xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;gn=gn+1endgn=gn-1;C

20、ontinue主程序主程序%绘制曲线绘制曲线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(自变量自变量);string2=最终自变量最终自变量,num2str(xmax(gn);gtext(string2);End计算适应度和累计概率函数计算适应度和累计概率函数%计

21、算适应度函数计算适应度函数function f,p=objf(s);r=size(s);%读取种群大小读取种群大小inn=r(1);%有有inn个个体个个体bn=r(2);%个体长度为个体长度为bnContinue计算适应度和累计概率函数计算适应度和累计概率函数 for i=1:inn x=n2to10(s(i,:);%将二进制转换为十进制将二进制转换为十进制 xx=-1.0+x*3/(power(2,bn)-1);%转化为转化为-1,2区间的实数区间的实数 f(i)=ft(xx);%计算函数值，即适应度计算函数值，即适应度endf=f;%行向量转列向量行向量转列向量Continue计算适应度

22、和累计概率函数计算适应度和累计概率函数%计算选择概率计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i)*f(i);endfor i=1:inn ps(i)=f(i)*f(i)/fsum;endContinue计算适应度和累计概率函数计算适应度和累计概率函数%计算累积概率计算累积概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;Back to main.m计算目标函数值函数计算目标函数值函数%目标函数目标函数function y=ft(x);y=x.*sin(10*pi*x)+2;Back to objf.m函数函数n

23、2to10()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 选择操作函数选择操作函数%“选择选择”操作操作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 在模式识别中的

24、应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 用遗传算法进行特征提取用遗传算法进行特征提取 个体的表示方法：一个长度为个体的表示方法：一个长度为L的个体对应于一的个体对应于一个个L维的二进制特征矢量，它的每一位就表示包维的二进制特征矢量，它的每一位就表示包括或排除一个相应的特征。一个个体即是一个括或排除一个相应的特征。一个个体即是一个可能的最优特征子集；可能的最优特征子集；适应度函数的设计：个体所代表的特征子集进适应度函数的设计：个体所代表的特征子集进行分类时的识别率；行分类时的识别率；遗传算子：可采用各种方法；遗传算子：可采用各种方法；遗传算法的应用遗传算法的应用 5 5 在模

25、式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 将图像分为将图像分为mn格，对每一个格格，对每一个格 进行数据分析，得到进行数据分析，得到L个特征，个特征，从从L中选出中选出l个（个（Ll）特征送入）特征送入 分类器进行识别。分类器进行识别。遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 用遗传算法进行特征提取用遗传算法进行特征提取 例：作品鉴别例：作品鉴别 个体的表示：个体的表示：l位长，每位代表一个特征的序号，位长，每位代表一个特征的

26、序号，不可重复；不可重复；适应度函数的设计：识别率的函数；适应度函数的设计：识别率的函数；遗传算子：符合个体编码要求的算子。遗传算子：符合个体编码要求的算子。遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用 遗传算法今后研究的主要课题1、优化搜索方法的研究2、学习系统的遗传算法研究3、生物进化与遗传算法的研究4、遗传算法的并行分布处理5、人工生命与遗传算法的研究GA 研究内容与方向研究内容与方向算法性能算法性能研究研究混合算法混合算法研究研究并行算法并行算法研究研究算法应用算法应用研究研究与GA相关的重要学术期刊与国际会议重要学术期

27、刊Evolutionary ComputationIEEE Transactions on Evolutionary Computation重要国际会议International Conference on Genetic AlgorithmACM Genetic and Evolutionary Computation ConferenceWorkshop on Foundations of Genetic Algorithms and Classifier SystemsGenetic Programming ConferenceInternational Workshop on Artificial Life混合遗传算法爬山法爬山法模拟退火算法模拟退火算法最速下降法最速下降法其它其它局部搜索算法局部搜索算法遗传算法遗传算法并行组合模拟退火算法并行模拟退火遗传算法贪婪遗传算法遗传比率切割算法遗传爬山法引入局部改善操作的混合遗传算法免疫遗传算法混合遗传算法 练习题练习题 用遗传算法解决下面函数的极小值问题：用遗传算法解决下面函数的极小值问题：要求要求 1.遗传算法的具体实施策略不限；遗传算法的具体实施策略不限；2.用用MATLAB；3.上交内容包括：源程序和运行结果（图、表上交内容包括：源程序和运行结果（图、表等，等，WORD