遗传算法应用实例

2020/1/201遗传算法应用举例利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。y=x231XY2020/1/202分析原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。2020/1/203(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x22020/1/204(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。2020/1/205首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=3612020/1/206再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.312020/1/207赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法2020/1/208在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为ijjixPq1)(2020/1/209选择-复制设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色体适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0012020/1/2010于是，经复制得群体：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）2020/1/2011交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）2020/1/2012变异设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。2020/1/2013于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）2020/1/2014第二代种群S2中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.0012020/1/2015假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：s1’=11001（25）,s2’=01100（12）s3’=11011（27）,s4’=10000（16）做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因，得s1’’=11100（28）,s2’’=01001（9）s3’’=11000（24）,s4’’=10011（19）这一轮仍然不会发生变异。2020/1/2016于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）2020/1/2017第三代种群S3中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0012020/1/2018设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）s3’’=11000（24）,s4’’=10000（16）这一轮仍然不会发生变异。2020/1/2019于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）2020/1/2020显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。2020/1/2021YYy=x28131924X第一代种群及其适应度y=x212162527XY第二代种群及其适应度y=x29192428XY第三代种群及其适应度y=x216242831X第四代种群及其适应度