第四章__遗传算法2

1、 w问题的提出问题的提出 一元函数求最大值：一元函数求最大值： 2 , 1 0 . 2)10sin()(xxxxf w问题的提出问题的提出 用微分法求取用微分法求取f(x)的最大值：的最大值： 解有无穷多个：解有无穷多个： xxxxxxf10)10tan( 0)10cos(10)10sin()( 即的实数递减序列。一接近于是及，0), 2, 1, 2 , 1( , 2, 1 ,2012 0 , 2 , 1 ,20120iiiixxiixiiiii w问题的提出问题的提出 当当i为奇数时为奇数时xi对应局部极大值点，对应局部极大值点，i为偶数时为偶数时xi对应对应局部极小值。局部极小值。x19即

2、为区间即为区间-1,2内的最大值点：内的最大值点： 此时，函数最大值此时，函数最大值f(x19)比比f(1.85)=3.85稍大。稍大。 19191985. 12037x w编码编码 表现型：表现型：x 基因型：二进制编码（串长取决于求解精度）基因型：二进制编码（串长取决于求解精度） 串长与精度之间的关系串长与精度之间的关系： 若要求求解精度到若要求求解精度到6位小数，区间长度为位小数，区间长度为2-(-1)3，即需将区间分为即需将区间分为3/0.000001=3106等份。等份。 所以编码的二进制串长应为所以编码的二进制串长应为22位。位。 4194304230000002209715222

3、21 w产生初始种群产生初始种群 产生的方式：随机产生的方式：随机 产生的结果：长度为产生的结果：长度为22的二进制串的二进制串 产生的数量：种群的大小（规模），如产生的数量：种群的大小（规模），如30，50， 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 w计算适应度计算适应度 不同的问题有不同的适应度计算方法不同的问题有不同的适应度计算方法 本例：直接用目标函数作

4、为适应度函数本例：直接用目标函数作为适应度函数 将某个体转化为将某个体转化为-1,2区间的实数：区间的实数： s= x=0.637197 计算计算x的函数值（适应度）：的函数值（适应度）： f(x)=xsin(10 x)+2.0=2.586345 w计算适应度计算适应度 二进制与十进制之间的转换二进制与十进制之间的转换： 第一步，将一个二进制串（第一步，将一个二进制串（b21b20b0）转化为）转化为10进制进制数：数： 第二步，第二步，x对应的区间对应的区间-1,2内的实数：内的实数： )2()(10210202021xbbbbiii12) 1(20 . 122xx(000000000000

5、0000000000)-1(1111111111111111111111)2 w遗传操作遗传操作 选择：轮盘赌选择法；选择：轮盘赌选择法； 交叉：单点交叉；交叉：单点交叉； 变异：小概率变异变异：小概率变异 w模拟结果模拟结果 设置的参数设置的参数： 种群大小种群大小50；交叉概率；交叉概率0.75；变异概率；变异概率0.05；最大；最大代数代数200。 得到的最佳个体得到的最佳个体： smax=; xmax=1.8506; f(xmax)=3.8503; w模拟结果模拟结果 进化的过程进化的过程： 世代数世代数自变量自变量适应度适应度11.44953.449491.83953.7412171

6、.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503 w编码原则编码原则完备性（完备性（completeness）：问题空间的所有解都能）：问题空间的所有解都能表示为所设计的基因型；表示为所设计的基因型；健全性（健全性（soundness）：任何一个基因型都对应于）：任何一个基因型都对应于一个可能解；一个可能解；非冗余性（非冗余性（non-redundancy）：问题空间和表达空）：问题空间和表达空间一一对应。间一一对应。 w多种编码方式多种编码方式二进制编码；二进制编码；浮点数编

7、码；浮点数编码；格雷码编码；格雷码编码；符号编码；符号编码；复数编码；复数编码；DNA编码等。编码等。 w二进制编码与浮点数编码的比较二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数在变异操作时，二进制编码的种群稳定性比浮点数编码差。编码差。 w适应度函数的重要性适应度函数的重要性 适应度函数的选取直接影响遗传算法的收敛速度以适应度函数的选取直接影响遗传算法的收敛速

8、度以及能否找到最优解。及能否找到最优解。 一般而言，适应度函数是由目标函数变换而成的，一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的对目标函数值域的某种映射变换称为适应度的尺度尺度变换变换（fitness scaling）。）。 w几种常见的适应度函数几种常见的适应度函数直接转换直接转换 若目标函数为最大化问题：若目标函数为最大化问题：Fit ( f (x) )= f (x) 若目标函数为最小化问题：若目标函数为最小化问题：Fit ( f (x) )= - f (x) w几种常见的适应度函数几种常见的适应度函数界限构造法界限构造法1 若目标函数为最大化问题

9、：若目标函数为最大化问题： 若目标函数为最小化问题：若目标函数为最小化问题： 的最小估计值。为式中，其他)( , 0)( ,)()(minminminxfccxfcxfxfFit的最大估计值。为式中，其他)( , 0)( ),()(maxmaxmaxxfccxfxfcxfFit w几种常见的适应度函数几种常见的适应度函数界限构造法界限构造法2 若目标函数为最大化问题：若目标函数为最大化问题： 若目标函数为最小化问题：若目标函数为最小化问题： c为目标函数的保守估计值。为目标函数的保守估计值。 0)(, 0 )(11)(xfccxfcxfFit0)(, 0 )(11)(xfccxfcxfFit

10、w适应度函数的作用适应度函数的作用 适应度函数设计不当有可能出现欺骗问题：适应度函数设计不当有可能出现欺骗问题： （1）进化初期，个别超常个体控制选择过程；）进化初期，个别超常个体控制选择过程； （2）进化末期，个体差异太小导致陷入局部极值。）进化末期，个体差异太小导致陷入局部极值。 w适应度函数的设计适应度函数的设计单值、连续、非负、最大化单值、连续、非负、最大化合理、一致性合理、一致性计算量小计算量小通用性强通用性强 w适应度函数的线性变换法适应度函数的线性变换法 f=*f+ 系数的确定满足以下条件：系数的确定满足以下条件： favg= favg fmax= cmult favg cmul

11、t =1.02.0 w适应度函数的幂函数变换法适应度函数的幂函数变换法 f= f k k与所求优化相关与所求优化相关 0.10.20.30.40.50.60.70.80.900.10.20.30.40.50.60.70.80.91k w适应度函数的指数变换法适应度函数的指数变换法 f= e-af a决定了复制的强制性，其值越小，复制的强制性决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体。就越趋向于那些具有最大适应性的个体。 1234567891000.10.20.30.40.50.60.70.80.91ff w几个概念几个概念选择压力（选择压力（selection

12、 pressure）:最佳个体选中的概最佳个体选中的概率与平均个体选中概率的比值；率与平均个体选中概率的比值；偏差（偏差（bias）：个体正规化适应度与其期望再生概）：个体正规化适应度与其期望再生概率的绝对差值；率的绝对差值；个体扩展（个体扩展（spread）：单个个体子代个数的范围；）：单个个体子代个数的范围；多样化损失（多样化损失（loss of diversity）：在选择阶段未选）：在选择阶段未选中个体数目占种群的比例；中个体数目占种群的比例； w几个概念几个概念选择强度（选择强度（selection intensity）:将正规高斯分布应用于选择方法，将正规高斯分布应用于选择方法，期

13、望平均适应度；期望平均适应度；选择方差（选择方差（selection variance）：）：将正规高斯分布应用于选择方法，将正规高斯分布应用于选择方法，期望种群适应度的方差。期望种群适应度的方差。 w个体选择概率的常用分配方法个体选择概率的常用分配方法按比例的适应度分配（按比例的适应度分配（proportional fitness assignment） 某个体某个体i，其适应度为，其适应度为fi，则其被选取的概率，则其被选取的概率Pi为：为： MiiiiffP1个体个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410

14、.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09 w个体选择概率的常用分配方法个体选择概率的常用分配方法基于排序的适应度分配（基于排序的适应度分配（rank-based fitness assignment） 线性排序（线性排序（by Baker） 为种群大小，为种群大小，i为个体序号，为个体序号，max代表选择压力。代表选择压力。 maxminmaxminmaxmax2, 21,11)(1iPi w个体选择概率的常用分配方法个体选择概率的常用分配方法基于排序的适应度分配（基于排序的适应度分配（rank-based

15、 fitness assignment） 非线性排序（非线性排序（by Michalewicz） i为个体序号，为个体序号，c为排序第一的个体的选择概率。为排序第一的个体的选择概率。 1)1 (iiccP w常用选择方法常用选择方法轮盘赌选择法（轮盘赌选择法（roulette wheel selection） 个体个体1234567891011适应度适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率累计概率0.180.340.490.620.730.820.890

16、.950.981.001.00 w常用选择方法常用选择方法随机遍历抽样法（随机遍历抽样法（stochastic universal sampling） 个体个体1234567891011适应度适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率累计概率0.180.340.490.620.730.820.890.950.981.001.00设定n为需要选择的个体数目，等距离选择个体，选择指针的距离为1n。第一个指针的位置由0，ln区间的均匀随机数决定。如图所示，需要选

17、择6个个体，指针间的距离为l6o.167，第一个指针的随机位置为0.1，按这种选择方法被选中作为交配集个体为：12，34，6，8。 w常用选择方法常用选择方法局部选择法（局部选择法（local selection） (1)线形邻集线形邻集 在局部选择法中，每个个体处在局部选择法中，每个个体处于一个约束环境中，称为局部于一个约束环境中，称为局部邻域邻域( (而其他选择方法中视整个而其他选择方法中视整个种群为个体之邻域种群为个体之邻域) )，个体仅与，个体仅与其邻近个体产生交互，该邻域其邻近个体产生交互，该邻域的定义由种群的分布结构给出。的定义由种群的分布结构给出。邻域可被当作潜在的交配伙伴。邻域

18、可被当作潜在的交配伙伴。首先均匀随机地选择一半交配首先均匀随机地选择一半交配种群，选择方法可以是随机遍种群，选择方法可以是随机遍历方法也可以是截断选择方法，历方法也可以是截断选择方法，然后对每个被选个体定义其局然后对每个被选个体定义其局部邻域，在邻域内部选择交配部邻域，在邻域内部选择交配伙伴。伙伴。 w常用选择方法常用选择方法局部选择法（局部选择法（local selection） (2)两对角邻集两对角邻集 w常用选择方法常用选择方法局部选择法（局部选择法（local selection） (2)两对角邻集两对角邻集 w常用选择方法常用选择方法截断选择法（截断选择法（truncation s

19、election） 个体按适应度排列，只有优秀个体能够称为父个体，个体按适应度排列，只有优秀个体能够称为父个体，参数为截断阀值（被选作父个体的百分比）。参数为截断阀值（被选作父个体的百分比）。 截断阀值截断阀值11020405080选择强度选择强度2.661.761.20.970.80.34 w常用选择方法常用选择方法锦标赛选择法（锦标赛选择法（tournament selection） 随机从种群中挑选一定数目个体，其中最好的个体随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。作为父个体，此过程重复进行完成个体的选择。 竞赛规模竞赛规模12351030选

20、择强度选择强度00.560.851.151.532.04 w实值重组实值重组离散重组离散重组 子个体的每个变量可以按等概率随机地挑选父个体。子个体的每个变量可以按等概率随机地挑选父个体。 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1 123 4 5子个体子个体2 12 4 34 w实值重组实值重组中间重组中间重组 子个体父个体子个体父个体1（父个体（父个体2父个体父个体1） 是比例因子，由是比例因子，由-d,1+d上均匀分布地随机数产生。上均匀分布地随机数产生。 d=0时为中间重组，一般取时为中间重组，一般取d=0.25。 子代的每个变量均产生一个子代的每个变量

21、均产生一个 。 w实值重组实值重组中间重组中间重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5 1.1 -0.1值样本值样本2 0.1 0.8 0.5120.5（12312）=67.567.5251.1（425）=1.91.92.1120.1（12312）=23.123.18.219.5 w实值重组实值重组中间重组中间重组 w实值重组实值重组线性重组线性重组 父个体父个体1 12 25 5父个体父个体2 123 4 34子个体子个体1子个体子个体2值样本值样本1 0.5值样本值样本2 0.1120.5（12312）=67.5

22、67.5250.5（425）=14.514.519.5120.1（12312）=23.123.122.97.9 w实值重组实值重组线性重组线性重组 w二进制交叉二进制交叉单点交叉单点交叉 w二进制交叉二进制交叉多点交叉多点交叉 w二进制交叉二进制交叉均匀交叉均匀交叉 父个体父个体1 0 1 1 1 0 0 1 1 0 1 0 父个体父个体2 1 0 1 0 1 1 0 0 1 0 1子个体子个体1 1 1 1 0 1 1 1 1 1 1 1子个体子个体2 0 0 1 1 0 0 0 0 0 0 0 样本样本1 0 1 1 0 0 0 1 1 0 1 0 样本样本2 1 0 0 1 1 1 0

23、0 1 0 1 w实值变异实值变异 一般采用：一般采用： w二进制变异二进制变异 为变量的取值范围。；，通常取值，以概率取值以概率其中，LmmmiaiaLXXmii 2001111)( ,2)(5 . 00 w主程序主程序 %用遗传算法进行简单函数的优化用遗传算法进行简单函数的优化clearbn=22; %个体串长度个体串长度inn=50; %初始种群大小初始种群大小gnmax=200; %最大代数最大代数pc=0.75; %交叉概率交叉概率pm=0.05; %变异概率变异概率Continue w主程序主程序 %产生初始种群，产生初始种群，0,1向量向量s=round(rand(inn,bn)

24、;%计算适应度计算适应度,返回适应度返回适应度f和累积概率和累积概率pf,p=objf(s); Continue w主程序主程序 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 w主程序主程序 s=

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

26、ot(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 w计算适应度和累计概率函数计算适应度和累计概率函数 %计算适应度函数计算适应度函数function f,

27、p=objf(s);r=size(s); %读取种群大小读取种群大小inn=r(1); %有有inn个个体个个体bn=r(2); %个体长度为个体长度为bnContinue w计算适应度和累计概率函数计算适应度和累计概率函数 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 w函数函数n2to10() Conti

28、nue 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 w计算适应度和累计概率函数计算适应度和累计概率函数 %计算选择概率计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i)*f(i);endfor i=1:inn ps(i)=f(i)*f(i)/fsum;endContinue w计算适应度和累计概率函数计算适应度和累计概率函数 %计算

29、累积概率计算累积概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;Back to main.m w计算目标函数值函数计算目标函数值函数 %目标函数目标函数function y=ft(x);y=x.*sin(10*pi*x)+2;Back to objf.m2 , 1 0 . 2)10sin()(xxxxf w选择操作函数选择操作函数 %“选择选择”操作操作function seln=sel(s,p);inn=size(p,1);%从种群中选择两个个体从种群中选择两个个体for i=1:2 r=rand; %产生一个随机数产生一个随机数 pran

30、d=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号选中个体的序号endBack to main.m w交叉操作函数交叉操作函数 %“交叉交叉”操作操作function scro=cro(s,seln,pc);r=size(s);inn=r(1);bn=r(2);pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，根据交叉概率决定是否进行交叉操作，1则是，则是，0则否则否Continue w交叉操作函数交叉操作函数 if pcc=1 chb=round(rand*(bn-2)+1; %在在1,bn-1范围内随机产生范围内

31、随机产生一个交叉位一个交叉位 scro(1,:)=s(seln(1),1:chb) s(seln(2),chb+1:bn); scro(2,:)=s(seln(2),1:chb) s(seln(1),chb+1:bn);else scro(1,:)=s(seln(1),:); scro(2,:)=s(seln(2),:);end Back to main.m w变异操作函数变异操作函数 %“变异变异”操作操作function snnew=mut(snew,pm);r=size(snew);bn=r(2);snnew=snew;Continue w变异操作函数变异操作函数 pmm=pro(pm)

32、; %根据变异概率决定是否进行变异操根据变异概率决定是否进行变异操作，作，1则是，则是，0则否则否if pmm=1 chb=round(rand*(bn-1)+1; %在在1,bn范围内随机范围内随机产生一个变异位产生一个变异位 snnew(chb)=abs(snew(chb)-1);end Back to main.m w运行程序运行程序 w运行程序运行程序 w运行程序运行程序 w运行程序运行程序 w模式模式 将种群中的个体即基因串中的相似样板称为将种群中的个体即基因串中的相似样板称为模式模式。 在二进制编码的串中，模式是基于三个字符集（在二进制编码的串中，模式是基于三个字符集（0，1，*）

33、的字符串，符号）的字符串，符号*代表任意字符，即代表任意字符，即0或或1。 如模式如模式 *1* 描述了一个四个元的子集描述了一个四个元的子集010，011，110，111。 w模式阶和定义距模式阶和定义距 模式模式 H 中确定位置的个数称为模式中确定位置的个数称为模式 H 的的模式阶模式阶，记作记作 O(H)，如，如 O(0 1 1 * 1 *)=4。 模式阶用来反映不同模式间确定性的差异，模式阶模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越高，模式的确定性就越高，所匹配的样本个数就越少。越少。 w模式阶和定义距模式阶和定义距 模式模式 H 中第一

34、个确定位置和最后一个确定位置之中第一个确定位置和最后一个确定位置之间的距离称为模式的间的距离称为模式的定义距定义距，记作，记作 (H)，如，如 (0 1 1 * 1 * *)=4。 阶数相同的模式会有不同的性质，定义距就反映了阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。这种性质的差异。 w模式模式定理（定理（schema theorem） 在给定时间步在给定时间步 t ,一个特定模式一个特定模式 H 有有 m 个代表串包个代表串包含在种群含在种群 A(t) 中，记为中，记为 m=m(H,t)，在再生阶段，在再生阶段，每个串根据它的适应值进行复制，一个串每个串根据它的适应值进行复

35、制，一个串 Ai 的再的再生概率为生概率为 njjiiffp1 w模式模式定理（定理（schema theorem） 当采用非重叠的当采用非重叠的 n 个串的种群替代种群个串的种群替代种群 A(t)，可以，可以得到：得到： 其中其中 f(H) 是在时间是在时间 t 表示模式表示模式 H 的串的平均适应的串的平均适应度。度。 njjfHfntHmtHm1)(),() 1,(fHftHmtHm)(),() 1,(nffnjj1 为整个种群的平均适应度 )0 ,()1 (),()1 ()(),() 1,(HmctHmcffcftHmtHmtw模式模式定理（定理（schema theorem） 假设从假设从 t=0 开始，某一特定模式适应度值保持在种开始，某一特定模式适应度值保