遗传算法案例分析.docx

遗传算法案例分析 利用遗传算法，求解区间［0,31］上的二次函数y=x2的最大值。 分析：原问题可转化为在区间［0,31］中搜索能使y取最小值的点x的问题。那么，［0,31］中的点x就是个体，函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样，只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。二次函数的图像如图所示。 二次函数y 二次函数y=x2的图像 设定种群规模，编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S: 1S= S=13(01101)， s=8(01000)， S=24(11000) s=19(10011) 定义适应度函数。 取适应度函数：f(x)=x2。 计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适应度最高的个体(即31(11111))出现为止。 首先计算种群S中各个体的适应度f(s)。容易求得，112f(s)=f(13)=13=16912f(s)=f(24)=24=57622 f(s)=f(8)=8=6432f(s)=f(19)=19=3614再计算种群S中各个体的选择概率。选择概率的计算公式为1P(x)=f(xi)kf(xJ)j=1 由此求得，P(s)=P(13)=0.141P(s)=P(24)=0.492P(s)=P(8)=0.063P(s)=P(19)=0.314用赌轮选择法可得，设从区间［0,1］中产生4个随机数如下:r=0.450126,1r=0.572496,3r=0.1103472r=0.985034第一代选中次数表染色体适应 设从区间［0,1］中产生4个随机数如下: r=0.450126, 1 r=0.572496, 3 r=0.110347 2 r=0.98503 4 第一代选中次数表 染色体 适应 度 选择概率 积累概率 选中次数 s1=01101 169 0.14 0.14 1 s2=11000 576 0.49 0.63 2 s3=01000 64 0.06 0.69 0 s4=10011 361 0.31 1 1 表1 于是，经复制得群体: s’=11000(24),s’=01101(13) TOC\o1-5\h\z12s’=11000(24),s’=10011(19) \o CurrentDocument 34设交叉率p=100%,即S中的全体染色体都参加交叉运算。设s’与s’配对，c112s’与s’配对。分别交换后两位基因，得新染色体： s’=11001(25),s’=01100(12) s’=11011(27),s’=10000(16)34设变异率p=0.001。这样，群体S中共有5X4X0.001=0.02位基因可以变异。m10.02位显然不足1位，所以本轮遗传操作不做变异。 于是，得到第二代种群S: 2s=11001(25),s=01100(12)TOC\o1-5\h\z12s=11011(27),s=10000(16)34表2第二代选中次数表 染色体 适应度 选择概率 积累概率 估计的选中次数 s1=11001 625 0.36 0.36 1 s2=01100 144 0.08 0.44 0 s3=11011 729 0.41 0.85 2 s4=10000 256 0.15 1 1 TOC\o1-5\h\z假设这一轮选择-复制操作中，种群s2中的4个染色体都被选中，则得到群体: s’=11001(25)，s’=01100(12)12s’=11011(27)，s’=10000(16) \o CurrentDocument 34做交叉运算，让s’与s’，s’与s’分别交换后三位基因，得1234s’’=11100(28)，s’’=01001(9)12s’’=11000(24)，s’’=10011(19)34这一轮仍然不会发生变异。于是，得第三代种群S3： s1=11100(28)，s2=01001(9)s3=11000(24)，s4=10011(19)表3第三代选中次数 染色体 适应度 选择概率积累概率估计的选中次数 s1=11100 784 0.44 0.44 2 s2=01001 81 0.04 0.48 0 s3=11000 576 0.32 0.8 1 s4=10011 361 0.2 1 1 设这一轮的选择-复制结果为: s=11100(28),s=11100(28)TOC\o1-5\h\z12s=11000(24),s=10011(19) \o CurrentDocument 34 与s分别交换后两位基因，得3s=11100（28）2s=10000（16）4做交叉运算，让s‘与s,s142s=11111（31），1s 与s分别交换后两位基因