遗传算法案例分析

遗传算法案例分析利用遗传算法，求解区间0, 31上的二次函数y = X2的最大值。分析：原问题可转化为在区间0, 31中搜索能使y取最小值的点x的问题。那么，0, 31中的点x就是个体，函数值f(x)恰好就可以作为x的适应度,区间0, 31就是一个(解)空间。这样，只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。二次函数的图像如图所示。二次函数y = X2的图像(1) 设定种群规模，编码染色体，产生初始种群。将种群规模设定为4用5位二进制数编码染色体；取下列个体组成初始种S = 13 (01101)，iS = 24 (11000)2s = 19 (10011)4s =8(01000),3(2) 定义适应度函数。取适应度函数：f (x) = x2。(3) 计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适 应度最高的个体(即31 (11111)出现为止。首先计算种群S中各个体的适应度f (s )。容易求得，2f (s ) = f(13) = 13 = 16912f (s ) = f(24) = 24 = 57622f (s ) = f(8) = 8 = 6432f (s ) = f(19) = 19 = 3614再计算种群S1中各个体的选择概率。选择概率的计算公式为f ( X )I兰 f ( X ) j由此求得,j = 1P(s ) = P(13) = 0.141P(s ) = P(24) = 0.492P(s ) = P(8) = 0.063P(s ) = P(19) = 0.314用赌轮选择法可得,0.490.06赌轮选择法示意图设从区间0,1中产生4个随机数如下:r = 0.450126,1r = 0.1103472r = 0.572496,3与s 配对,2染色体适应 度选择概 率积累概 率选中次 数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.3111表1r = 0.985034第一代选中次数表于是，经复制得群体:s =11000 (24),s =01101 (13)12s =11000 (24), s =10011 (19)34设交叉率p =100%,即S中的全体染色体都参加交叉运算。设sc11s 与s 配对。分别交换后两位基因，得新染色体：34s =11001 (25),s =01100 (12)1 2s 丄 11011 （27）,s 丄 10000 （16）34设变异率p =0.001。这样，群体S中共有5X4X0.001=0.02位基因可以变异。m10.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S :2s =11001 （25）， s =01100 （12）1 2s =11011 （27）， s =10000 （16）34表2第二代选中次数表染色体适应 度选择概 率积累概 率估计的选中次 数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.1511假设这一轮选择-复制操作中，种群中的4个染色体都被选中，则得到群体:s =11001（25）， s = 01100（12）12s =11011（27），s = 10000（16）34做交叉运算，让s 与s ，s 与s 分别交换后三位基因，得1234s =11100（28），1s =11000（24），3s = 01001（9）2s = 10011（19）4这一轮仍然不会发生变异。于是，得第三代种群S3：s1=11100（28），s2=01001（9）s3=11000（24）， s4=10011（19）表3第三代选中次数染色体适应度选择概率积累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.81s4=100113610.211设这一轮的选择-复制结果为:s =11100 (28),s =11100 (28)12s =11000 (24),s =10011 (19)34做交叉运算，让s 与s ，s142s =11111 (31),1s =11000 (24),3与s 分别交换后两位基因，得3s 丄111002s 丄100004(28)(16)这一轮仍然不会发生变异。于是，得第四代种群s4：s1=11111 (31)s2=11100(28)s3=11000(24)s4=10000(16)显然，在这一代种群中已经出现了适应度最高的染色体s1=11111o于是，遗传操作终止，将 染色体“liiir作为最终结果输出。然后，将染色体“liiir解码为表现型，即得所求的最优 解: 31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。