GA2-遗传算法实例.ppt

by 谢广明 ， 2005~2006学年度第一学期 * Genetic Algorithm，GA 遗传算法 (II) by 谢广明 ， 2005~2006学年度第一学期 * 内 容 应用实例1： TSP 应用实例2：函数优化 策略设计 算法改进 by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 问题回顾 给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。 数学描述 给定图G=(V,E), V为顶点集, E为边集，确定一条长度最短的Hamilton回路 by 谢广明 ， 2005~2006学年度第一学期 * 应用实例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 by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 适应度函数 就取为目标函数的倒数，即路径总长度的倒数 初始种群 随机生成40个 终止条件 2000次迭代 参数设置 自定 by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 选择操作算子: 轮盘式选择 首先计算每个个体 i 被选中的概率 然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为 。选择时转动轮盘，参考点r落到扇形i则选择个体i 。 . . . . . . p1 p2 pi r by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 交叉操作算子 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 ） by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 交叉操作算子 然后移走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） by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 变异操作算子 采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转 例如 原个体：（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） by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP by 谢广明 ， 2005~2006学年度第一学期 * 应用实例1：TSP 中国城市TSP的一个参考解 by 谢广明 ， 2005~2006学年度第一学期 * 应用实例2：函数优化 函数优化 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理， 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如；[0，1]，计算精度0.001, 则0，0.001,0.002,…,0.998,0.999,1.000， 个数为1001 则用长度为10的二进制字符串一次表征所有离散点 0000000000，0000000001，…,1111110001.  by 谢广明 ， 2005~2006学年度第一学期 * 应用实例2：函数优化 适应度函数 例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要求的F(x) by 谢广明 ， 2005~2006学年度第一学期 * 应用实例2：函数优化 其它的就类似于TSP的求解了 by 谢广明 ， 2005~2006学年度第一学期 * 策略调整 针对不同实际问题需要调整相应策略 同一个实际问题不同的人也有不同的做法 编码方案 适应度函数设计 选择算子 交叉算子 变异算子 初始种群 by 谢广明 ， 2005~2006学年度第一学期 * 策略调整 编码方案 本质：如何表示解 二进制： 自变量高维、大范围