遗传算法的实现及应用举例.pptVIP

第六节 算法实现及应用;SGA实现;为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。 方法一：对于目标函数是求极大化，方法为：;式中， 为一个适当地相对比较小的数它可用下面几种方法之一来选取: 预先指定的一个较小的数； 进化到当前代为止的最小目标函数值； 当前代或最近几代群体中的最小目标值。 ;②比例选择算子 比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette Wheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。 比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。 ;③单点交叉算子 单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。 ;④基本位变异算子 基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。 ;简单演示;（4）轮盘赌选择：选择概率 个体： 01101，11000，01000，10011 适应度： 169 576 64 361 选择概率：0.14 0.49 0.06 0.31 选择 11000 和 01101交配产生下一代;（5）交叉操作：发生交叉的概率取大 交叉点位置的选取是随机的（单点交叉） 0110 1 0110 0 1100 0 1100 1;（6）变异：发生变异的概率取小 改变某个字节 11001 ?11101 （7）新群体的产生： 保留上一代最优个体，1个新个体取代旧个体 11101，11000，01000，10011 （8）重复上述操作20次，或许就能够得到最优解！ ;应用实例：TSP;TSP问题;交叉算子;交叉算子;变异算子;编码方案 路径表达：对一个旅行最自然的表达 一个旅行 5—1—7—8—9—4—6—2—3 的编码就是（5 1 7 8 9 4 6 2 3） 编码空间和解空间一一对应，总量为n! 个？ 其实一些解是相同的，因为 （5 1 7 8 9 | 4 6 2 3）= （4 6 2 3 | 5 1 7 8 9） 二者是同一个解 (n -1)!/2;适应度函数 就取为目标函数的倒数，即路径总长度的倒数 初始种群 随机生成40个 终止条件 2000次迭代 参数设置 自定;.;交叉操作算子 Davis提出OX算子：通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代 例如： p1=（1 2 3 | 4 5 6 7 | 8 9） p2=（4 5 2 | 1 8 7 6 | 9 3） 首先保持中间部分 o1=（X X X | 4 5 6 7 | X X ） o2=（X X X | 1 8 7 6 | X X ）;交叉操作算子 然后移走p2中已在o1中的城市4、5、6和7后，得到 2—1—8—9—3 该序列顺次放在o1中： o1=（2 1 8 | 4 5 6 7 | 9 3） 类似地，可以得到另一个后代： o2=（2 3 4 | 1 8 7 6 | 5 9）;变异操作算子 采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转 例如 原个体：（1 2 3 4 5 6 7 8 9） 随机选择两点：（1 2 | 3 4 5 6 | 7 8 9） 倒置后的个体：（1 2 | 6 5 4 3 | 7 8 9）;;中国城市TSP的一个参考解 ;应用实例2：函数优化;适应度函数 例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要求的F(x) 其它的就类似于TSP的求解了; 已知函数 其中 ，用遗传算法求解y的最大值。;运行步骤;运行步骤;运行步骤;运行步骤;运行步骤;运行步骤;运行步骤;; 例2 一元函数优化问题;问题的提出 用微分法求取 f(x) 的最大值： 解有无穷多个：;问题的提出 当i为奇数时xi对