《遗传算法的实现及应用举例课件》由会员分享，可在线阅读，更多相关《遗传算法的实现及应用举例课件（158页珍藏版）》请在金锄头文库上搜索。
1、第六节 算法实现及应用一、算法实现遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述来构造：确定问题编码方案确定适配值函数设计遗传算子（选择、交叉、变异）确定算法参数确定算法终止条件生成初始种群遗传算法的实现及应用举例SGA实现个体适应度评价在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是
2、负数。遗传算法的实现及应用举例为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。方法一：方法一：对于目标函数是求极大化，方法为：遗传算法的实现及应用举例式中， 为一个适当地相对比较小的数它可用下面几种方法之一来选取:预先指定的一个较小的数；进化到当前代为止的最小目标函数值；当前代或最近几代群体中的最小目标值。 遗传算法的实现及应用举例比例选择算子比例选择实际上是一种有退还随机选择，也叫做赌盘(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 适应
5、度：适应度： 169 576 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个新个体
6、取代旧个体个新个体取代旧个体 11101，11000，01000，10011（8）重复上述操作）重复上述操作20次，次，或许就能够得到最优解！或许就能够得到最优解！ 遗传算法的实现及应用举例应用实例：应用实例：TSP问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学描述给定图G=(V,E), V为顶点集, E为边集，确定一条长度最短的Hamilton回路遗传算法的实现及应用举例TSP问题问题复杂度:指数增长的！(NP完全问题)12个城市，具有条不同的路径。一条路径对应一个排列！交叉算子传统的交叉算子可能产生无效路径。
7、遗传算法的实现及应用举例交叉算子（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）部分映射交叉利用父代所选段内元的对应定义子代。父代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
8、 5 4 3 9遗传算法的实现及应用举例变异算子起双重作用：1、提供和保持群体的多样性； 2、搜索算子的作用。(1) 基于位置的变异：随机选择两个元，然后把第二个元放在第一个元之前；(2) 基于次序的变异：随机选择两个元，然后交换他们的位置；(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）二者是同
9、一个解(n -1)!/2应用实例应用实例1 1：TSPTSP遗传算法的实现及应用举例适应度函数就取为目标函数的倒数，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定遗传算法的实现及应用举例.p1p2pir选择操作算子选择操作算子: 轮盘式选择轮盘式选择首先计算每个个体首先计算每个个体 i 被选中被选中的概率的概率然后根据概率的大小将将圆然后根据概率的大小将将圆盘分为盘分为 n个扇形，每个扇形个扇形，每个扇形的大小为的大小为 。选择时转。选择时转动轮盘，参考点动轮盘，参考点r落到扇形落到扇形i则选择个体则选择个体i 。遗传算法的实现及应用举例交叉操作算子Davis提出O
10、X算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代例如：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）遗传算法的实现及应用举例变异
11、操作算子采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转例如原个体：（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：函数优化函数优化编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处理，然后根据离散化后待定解的个数选择合适长度的二进制字符串进行编码例如；0，1，计算精度0.001,则0，0.001,0.002,0.998,0.999,1.000， 个数为10
12、01则用长度为10的二进制字符串一次表征所有离散点0000000000，000000001，1111110001。遗传算法的实现及应用举例适应度函数例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要求的F(x)其它的就类似于TSP的求解了遗传算法的实现及应用举例 已知函数 其中 ，用遗传算法求解y的最大值。 例1 多元函数优化问题遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例运行步骤遗传算法的实现及应用举例 例
13、例2 一元函数优化问题一元函数优化问题问题的提出问题的提出 一元函数求最大一元函数求最大值：遗传算法的实现及应用举例问题的提出问题的提出 用微分法求取用微分法求取 f(x) 的最大的最大值值： 解有无解有无穷穷多个：多个：遗传算法的实现及应用举例问题的提出问题的提出 当当i为为奇数奇数时时xi对应对应局部极大局部极大值值点，点，i为为偶数偶数时时xi对对应应局部极小局部极小值值。x19即即为为区区间间-1,2内的最大内的最大值值点点 此此时时，函数最大，函数最大值值 f(x19) 比比f(1.85)=3.85稍大。稍大。遗传算法的实现及应用举例编码编码 表表现现型：型：x 基因型：二基因型：二
14、进进制制编码编码（串（串长长取决于求解精度）取决于求解精度） 串串长长与精度之与精度之间间的关系的关系： 若要求求解精度到若要求求解精度到6位小数，区位小数，区间长间长度度为为2-(-1)3，即需将区，即需将区间间分分为为3/0.000001=3106等份。等份。 所以所以编码编码的二的二进进制串制串长应为长应为22位。位。遗传算法的实现及应用举例产生产生初始种群初始种群 产产生的方式：随机生的方式：随机 产产生的生的结结果：果：长长度度为为22的二的二进进制串制串 产产生的数量：种群的大小（生的数量：种群的大小（规规模），如模），如30，50，111110110001101010111010
15、0100001001110011100110000000000遗传算法的实现及应用举例计算适应度计算适应度 不同的不同的问题问题有不同的适有不同的适应应度度计计算方法算方法 本例：直接用目本例：直接用目标标函数作函数作为为适适应应度函数度函数 将某个体将某个体转转化化为为-1,2区区间间的的实实数：数： s= x=0.637197 计计算算x的函数的函数值值（适（适应应度）：度）： f(x)=xsin(10x)+2.0=2.586345遗传算法的实现及应用举例计算适应度计算适应度 二二进进制与十制与十进进制之制之间间的的转换转换： 第一步，将一个二第一步，将一个二进进制串（制串（b21b20b
16、0）转转化化为为10进进制数：制数： 第二步，第二步，x对应对应的区的区间间-1,2内的内的实实数：数：)-1(1111111111111111111111)2遗传算法的实现及应用举例遗传操作遗传操作 选择：轮盘赌选择法；法； 交叉：交叉：单点交叉；点交叉； 变异：小概率异：小概率变异异遗传算法的实现及应用举例模拟结果模拟结果 设设置的参数置的参数： 种群大小种群大小50；交叉概率；交叉概率0.75；变变异概率异概率0.05；最；最大代数大代数200。 得到的最佳个体得到的最佳个体： smax=; xmax=1.8506; f(xmax)=3.8503;遗传算法的实现及应用举例模拟结果模拟结果
17、 进化的化的过程程：遗传算法的实现及应用举例主程序主程序 %用用遗传遗传算法算法进进行行简单简单函数的函数的优优化化clearbn=22; %个体串个体串长长度度inn=50; %初始种群大小初始种群大小gnmax=200; %最大代数最大代数pc=0.75; %交叉概率交叉概率pm=0.05; %变变异概率异概率Continue 算法的设计与实现算法的设计与实现 遗传算法的实现及应用举例主程序主程序 %产产生初始种群，生初始种群，0,1向量向量s=round(rand(inn,bn);%计计算适算适应应度度,返回适返回适应应度度f和累和累积积概率概率pf,p=objf(s); Continu
18、e遗传算法的实现及应用举例主程序主程序 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,:)=mut(scnew(j+1,:),pm); endContinue遗传算法的实现及应用举例主程序主程序 s=smnew; %产产生了新的种群生了新的种群 %计计算新种群的适算新种
19、群的适应应度度 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;Continue遗传算法的实现及应用举例主程序主程序 %绘绘制曲制曲线线subplot(2,1,1);plot(
20、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遗传算法的实现及应用举例计算适应度和累计概率函数计算适应度和累计概率函数 %计计算适算适应应度函数度函数function f,p=obj
21、f(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(1
23、0*pi*x)+2;Back to objf.m遗传算法的实现及应用举例函数函数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 遗传算法的实现及应用举例选择操作函数选择操作函数 %“选择选择”操作操作function seln=sel(s,p);inn=size(p,1);%从种群中从种群中选择选择两个个体两个个体for i=1
24、:2 r=rand; %产产生一个随机数生一个随机数 prand=p-r; j=1; while prand(j)d）；）；遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用遗传算法的实现及应用举例用遗传算法进行特征提取用遗传算法进行特征提取 个体的表示方法：一个个体的表示方法：一个长长度度为为L的个体的个体对应对应于一于一个个L维维的二的二进进制特征矢量，它的每一位就表示包制特征矢量，它的每一位就表示包括或排除一个相括或排除一个相应应的特征。一个个体即是一个的特征。一个个体即是一个可能的最可能的最优优特征子集；特征子集； 适适应应度
25、函数的度函数的设计设计：个体所代表的特征子集：个体所代表的特征子集进进行分行分类时类时的的识别识别率；率； 遗传遗传算子：可采用各种方法；算子：可采用各种方法；遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用遗传算法的实现及应用举例用遗传算法进行特征提取用遗传算法进行特征提取 例：作品例：作品鉴别鉴别 将将图图像分像分为为mn格，格，对对每一个格每一个格 进进行数据分析，得到行数据分析，得到L个特征，个特征， 从从L中中选选出出l个（个（Ll）特征送入）特征送入 分分类类器器进进行行识别识别。 遗传算法的应用遗传算法的应用 5 5
26、在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用遗传算法的实现及应用举例用遗传算法进行特征提取用遗传算法进行特征提取 例：作品例：作品鉴别鉴别 个体的表示：个体的表示：l位位长长，每位代表一个特征的序号，每位代表一个特征的序号，不可重复；不可重复； 适适应应度函数的度函数的设计设计：识别识别率的函数；率的函数； 遗传遗传算子：符合个体算子：符合个体编码编码要求的算子。要求的算子。遗传算法的应用遗传算法的应用 5 5 在模式识别中的应用在模式识别中的应用在模式识别中的应用在模式识别中的应用遗传算法的实现及应用举例遗传算法今后研究的主要课题遗传算法今后研究的主要课题1、优化
27、搜索方法的研究2、学习系统的遗传算法研究3、生物进化与遗传算法的研究4、遗传算法的并行分布处理5、人工生命与遗传算法的研究遗传算法的实现及应用举例GA 研究内容与方向算法性能研究混合算法研究并行算法研究算法应用研究遗传算法的实现及应用举例与GA相关的重要学术期刊与国际会议重要学术期刊Evolutionary ComputationIEEE Transactions on Evolutionary Computation重要国际会议International Conference on Genetic AlgorithmACM Genetic and Evolutionary Computati
28、on ConferenceWorkshop on Foundations of Genetic Algorithms and Classifier SystemsGenetic Programming ConferenceInternational Workshop on Artificial Life遗传算法的实现及应用举例混合遗传算法爬山法模拟退火算法最速下降法其它局部搜索算法遗传算法遗传算法的实现及应用举例并行组合模拟退火算法并行模拟退火遗传算法贪婪遗传算法遗传比率切割算法遗传爬山法引入局部改善操作的混合遗传算法免疫遗传算法混合遗传算法遗传算法的实现及应用举例 练习题练习题用用遗传算法解决下面函数的极小算法解决下面函数的极小值问题：遗传算法的实现及应用举例要求要求 1. 遗传遗传算法的具体算法的具体实实施策略不限；施策略不限； 2. 用用MATLAB； 3. 上交内容包括：源程序和运行上交内容包括：源程序和运行结结果（果（图图、表、表等，等，WORD文档），文档），遗传算法的实现及应用举例此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！遗传算法的实现及应用举例
