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

第六节 算法实现及应用 一、算法实现 遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造： 确定问题编码方案 确定适配值函数 设计遗传算子（选择、交叉、变异） 确定算法参数 确定算法终止条件 生成初始种群 SGA实现 ①个体适应度评价 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或0，不能是负数。 为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值变换为个体的适应度。 方法一：对于目标函数是求极大化，方法为： 式中， 为一个适当地相对比较小的数它可用下面几种方法之一来选取: 预先指定的一个较小的数； 进化到当前代为止的最小目标函数值； 当前代或最近几代群体中的最小目标值。 ②比例选择算子 比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette Wheel)选择，因为这种选择方式与赌博中的赌盘操作原理非常相似。 比例选择算子的具体执行过程是：先计算出群体中所有个体的适应度之和；其次计算出每个个体的相对适应度的大小，此值即为各个个体被遗传到下一代群体中的概率；最后再使用模拟赌盘操作（即0到1之间的随机数）来确定各个个体被选中的次数。 ③单点交叉算子 单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执行过程如下：对群体中的个体进行两两随机配对；对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点；对每一对相互配对的个体，依设定的交叉概率 在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新个体。 ④基本位变异算子 基本位变异算子的具体执行过程为：对个体的每一个基因座，依变异概率 指定其为变异点；对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的个体。 简单演示 应用实例：TSP 问题回顾 给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。 数学描述 给定图G=(V,E), V为顶点集, E为边集，确定一条长度最短的Hamilton回路 应用实例1：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：函数优化 函数优化 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理， 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如；[0，1]，计算精度0.001, 则0，0.001,0.002,…,0.998,0.999,1.000， 个数为1001 则用长度为10的二进制字符串一次表征所有离散 点0000000000，000000001，…，1111110001。 适应度函数 例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要求的F(x) 其它的就类似于