第10章遗传算法详解.ppt

运行结果： 2 遗传算法应用实例 运行结果： 2 遗传算法应用实例 * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 遗传算法简介 （5）变异概率 变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率Pm也是针对基因而言，即： Pm = B M · l 式中：B——每代中变异的基因数目； M——每代中群体拥有的个体数目 λ——个体中基因串长度。 1 遗传算法简介 自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织有哪些信誉好的足球投注网站。 本质并行性 内在并行性与内含并行性 不需求导 只需目标函数和适应度函数 概率转换规则 强调概率转换规则，而不是确定的转换规则 1.8 遗传算法的特点 1、遗传算法适合数值求解那些有多参数、多变量、多目标、多区域的NP-hard问题; 2、遗传算法在求解很多优化问题时，不需要有很强的技巧和对问题有非常深入的了解; 3、遗传算法求解有较好的兼容性。 1 遗传算法简介 1.9 遗传算法的优越性 1、编码不规范及编码存在表示的不准确性; 2、单一的遗传编码不能全面地将优化问题的约束表示出来; 3、是否能保证收敛到最优解. 1 遗传算法简介 1.10 遗传算法的不足 例1：利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。　　 y=x2 31 X Y 2 遗传算法应用实例 2.1 简单函数优化的实例 产生初始种群 计算适应度 2 遗传算法应用实例 参数编码 将整数 x*? {0,1,…,31}作为参数，采用二进制进行编码： x=0—00000， … …x=31 —11111 本例取适应度函数 fitness(X)=x2 串 编 号 随机产生初始群体 X（无符号整数） 适应度 f(x)=x2 选择概率 适应度期望值 实际计算（来自赌轮） 复制后配对库 交叉位置（随机选择） 新一代群体 X值 适应度 f(x)=x2 1 01101 13 169 01101 4 01100 12 144 2 11000 24 576 11000 4 11001 25 625 3 01000 8 64 11000 2 11011 27 729 4 10011 19 361 10011 2 10000 16 256 总和 1754 平均 293 439 最大 576 729 169 169+576+64+361 0.14 0.49 0.06 0.31 1.00 0.25 0.49 169 169+576+64+361 4 1.97 0.22 1.23 4.00 1.00 1.97 1 2 0 1 4 1 2 0.58 2 遗传算法应用实例 s4 0.31 s2 0.49 s1 0.14 S3 0.06 比例选择法（赌轮选择法）在算法 中赌轮选择法可用下面的子过程来 模拟: 　 ① 在［0, 1］区间内产生一个均匀分布的随机数r。 ② 若r≤q1,则染色体x1被选中。 ③ 若qk-1r≤qk(2≤k≤N), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为 2 遗传算法应用实例 设从区间［0, 1］中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503 染色体 适应度 选择概率 积累概率 选中次数 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.00 1 淘汰 2 遗传算法应用实例 例2：求一元函数f(x)的最大值： 2 遗传算法应用实例 用微分法求取f(x)的最大值： 解有多个： 2 遗传算法应用实例 当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内的最大值点： 此时，函数最大值f(x19)比f(1.85)=