822第二章 遗传算法 (II).ppt

《822第二章 遗传算法 (II).ppt》由会员分享，可在线阅读，更多相关《822第二章 遗传算法 (II).ppt（34页珍藏版）》请在三一文库上搜索。

1、Genetic Algorithm，GA 第二章 遗传算法 (II) 1 by 谢广明 ， 20052006学年度第一学期 内 容 简单演示 应用实例1： TSP 应用实例2：函数优化 策略设计 算法改进 2 by 谢广明 ， 20052006学年度第一学期 简单演示 问题：求 （1）编码： 编码长度为5 （2）初始群体生成：群体大小设置为4，随机产生四 个个体： 编码： 01101，11000，01000，10011 解码： 13 24 8 19 适应度： 169 576 64 361 （3）适应度函数： 3 by 谢广明 ， 20052006学年度第一学期 （4）轮盘赌选择：选择概率 个体

2、： 01101，11000，01000，10011 适应度： 169 576 64 361 选择概率：0.14 0.49 0.06 0.31 选择 11000 和 01101交配产生下一代 简单演示 4 by 谢广明 ， 20052006学年度第一学期 （5）交叉操作：发生交叉的概率取大 交叉点位置的选取是随机的（单点交叉） 0110 1 0110 0 1100 0 1100 1 简单演示 5 by 谢广明 ， 20052006学年度第一学期 （6）变异：发生变异的概率取小 改变某个字节 11001 11101 （7）新群体的产生： 保留上一代最优个体，1个新个体取代旧个体 11101，110

3、00，01000，10011 （8）重复上述操作20次 ,或许就能够得到最优解！ 简单演示 6 by 谢广明 ， 20052006学年度第一学期 应用实例1：TSP 问题回顾 给定n个城市以及两两城市之间的距离，求解 一条从某个城市出发、不重复地遍历所有其它 城市并最终又回到起始城市的最短路径。 数学描述 给定图G=(V,E), V为顶点集, E为边集，确定 一条长度最短的Hamilton回路 7 by 谢广明 ， 20052006学年度第一学期 应用实例1：TSP 编码方案 路径表达：对一个旅行最自然的表达 一个旅行 517894623 的编码就是（5 1 7 8 9 4 6 2 3） 编码

4、空间和解空间一一对应，总量为n! 个？ 其实一些解是相同的，因为 （5 1 7 8 9 | 4 6 2 3）= （4 6 2 3 | 5 1 7 8 9） 二者是同一个解 (n -1)!/2 8 by 谢广明 ， 20052006学年度第一学期 应用实例1：TSP 适应度函数 就取为目标函数的倒数，即路径总长度的倒数 初始种群 随机生成40个 终止条件 2000次迭代 参数设置 自定 9 by 谢广明 ， 20052006学年度第一学期 应用实例1：TSP 选择操作算子: 轮盘式选择 首先计算每个个体 i 被选中 的概率 然后根据概率的大小将将圆 盘分为 n个扇形，每个扇形 的大小为 。选择时

5、转 动轮盘，参考点r落到扇形i则 选择个体i 。 . . . . . . p1 p2 pi r 10 by 谢广明 ， 20052006学年度第一学期 应用实例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 ） 11 by 谢广明 ， 20052006学年度第一学期 应用实例1

6、：TSP 交叉操作算子 然后移走p2中已在o1中的城市4、5、6和7后，得到 21893 该序列顺次放在o1中： o1=（2 1 8 | 4 5 6 7 | 9 3） 类似地，可以得到另一个后代： o2=（2 3 4 | 1 8 7 6 | 5 9） 12 by 谢广明 ， 20052006学年度第一学期 应用实例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） 13 by 谢广明

7、 ， 20052006学年度第一学期 应 用 实 例 1 ： T S P 14 by 谢广明 ， 20052006学年度第一学期 应用实例1：TSP 中国城市TSP的一个参考解 15 by 谢广明 ， 20052006学年度第一学期 应用实例2：函数优化 函数优化 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理， 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如；0，1，计算精度0.001, 则0，0.001,0.002,0.998,0.999,1.000， 个数为1001 则用长度为10的二进制字符串一次表征所有离散点 0000000000，00000

8、00001，,1111110001. 16 by 谢广明 ， 20052006学年度第一学期 应用实例2：函数优化 适应度函数 例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要 求的F(x) 17 by 谢广明 ， 20052006学年度第一学期 应用实例2：函数优化 其它的就类似于TSP的求解了 18 by 谢广明 ， 20052006学年度第一学期 策略调整 针对不同实际问题需要调整相应策略 同一个实际问题不同的人也有不同的做法 编码方案 适应度函数设计 选择算子 交叉算子 变异算子 初始种群 19 by 谢广明 ， 20052006学年度第一学期 策略调整 编码方案 本

9、质：如何表示解 二进制： 自变量高维、大范围连续、高精度的时候很难处理 冗余问题，离散化后解的个数介于2(n-1)和2n之间 D进制, D=3,8,16, 实数编码：无需编码和解码 序列编码：例如TSP的路径表达 树编码：非定长 自适应编码-长度可调节 20 by 谢广明 ， 20052006学年度第一学期 策略调整 适应度函数 是进行自然选择的定量标准 直接采用目标函数 引入适应值调节 线性变换 乘幂变换 指数变换 自适应变换 21 by 谢广明 ， 20052006学年度第一学期 策略调整 选择算子 轮盘赌选择(roulette wheel selection) 最基本、最常用的方式，又叫

10、适应度比例选择算子 最佳个体保存(elitist model) 把适应度最高的个体保留到下一代，又叫精英保留 排序模型(rank - based model) 按适应度函数大小排序，根据事先设定的概率表分配选择概率 联赛选择模型(tournament selection model) 随机选择几个进行比较，高的被选，又叫锦标赛模型 22 by 谢广明 ， 20052006学年度第一学期 策略调整 选择算子 期望值模型(expected value model) 排挤模型(crowding model) 浓度控制策略 共享机制 截断选择 23 by 谢广明 ， 20052006学年度第一学期 策

11、略调整 交叉算子 简单交叉 最基本、最常用的方式，双亲互换子串 平坦交叉 二者之间均匀随机产生 算术交叉 双亲的凸组合 线性交叉 1：1，3：1，1：3比较最好的两个留下 24 by 谢广明 ， 20052006学年度第一学期 策略调整 交叉算子 混合交叉 离散交叉 启发式交叉 模拟二进制交叉 单峰正态分布交叉 单纯形交叉 父体中心交叉 几何交叉 均匀交叉 基于模糊联接的交叉 25 by 谢广明 ， 20052006学年度第一学期 策略调整 变异算子 随机变异 区间内均匀随机取 非一致变异 某个区间内随机扰动 边界变异 取边界值 多项式变异 高斯变异 Cauthy变异 自适应变异 Muhlen

12、bein变异 26 by 谢广明 ， 20052006学年度第一学期 策略调整 初始种群 对计算结果和计算效率有影响 全局性要求初始解尽量分散 设计一些生成方法 27 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 编码方案 二进制编码：交叉和变异很难处理 顺序表示：1985 年 Grefenstette提出，序表示是指所有 城市依次排列构成一个顺序表(order list) ,对于一条旅程 ,可以依旅行经过顺序处理每个城市,每个城市在顺序表 中的顺序就是一个遗传因子的表示,每处理完一个城市, 从顺序表中去掉该城市. 处理完所有城市以后,将每个城 市的遗传因子表示连接起

13、来,就是一条旅程的基因表示. 例如,顺序表C = (1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9) ,一条旅程为5 - 1 - 7 - 8 - 9 - 4 - 6 - 3 - 2. 按照这种编码方法,这条旅程的编 码为表l = (5 1 5 5 5 3 3 3 2 1) 28 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 编码方案 路径表示：最自然、直接的表示方法 布尔矩阵表示：将一个旅程定义为一个优先权 布尔矩阵M ,当且仅当城市 i 排在城市j 之前时 矩阵元素mij = 1. 这种方法用n n 矩阵M 代表 一条旅程, M具有如下三个性质: 1) 矩阵中1

14、 的数目为n ( n - 1) / 2 ; 2) mii = 0 , i= 1 ,2 , ., n ; 3) 若mij = 1 ,且mjk = 1 ,那么mik = 1. 29 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 选择算子 轮盘赌选择(roulette wheel selection), 最佳个体保存(elitist model) , 期望值模型(expected value model) , 排序模型(rank - based model), 联赛选择模型(tournament selection model) 排挤模型(crowding model) 浓

15、度控制策略 上述机制混合 30 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 交叉算子 依赖于编码方式 基于路径表示的顺序交叉 基于路径表示的部分匹配交叉 贪心交叉法：在一个父个体中选择第一个城市作为子 个体的第一个城市,然后在两个父个体中进行比较并找 到与已经选择的那个城市相邻且距离较近的城市作为 下一个城市扩展到旅程中;如果与该城市相邻的两个城 市有一个已经在旅程中,那么选择另外一个,如果两个都 在旅程中,那么就选择其它没有被选择的城市. 循环交叉 边重组交叉 31 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 变异算子 全局意义 点位变

16、异：变异仅以一定的概率(通常很小) 对 串的某些位做值的变异; 逆转变异：在串中,随机选择两点,再将这两点 内的子串按反序插入到原来的位置中; 对换变异：随机选择串中的两点,交换其值(码) ; 插入变异：从串中随机选择1 个码,将此码插入 随机选择的插入点中间. 32 by 谢广明 ， 20052006学年度第一学期 求解TSP的策略调整 变异算子 贪心对换变异：从一个染色体中随机的选择两 个城市(即两个码值) ,然后交换它们,得到新的染 色体,以旅程长度为依据比较交换后的染色体与 原来的染色体的大小,保留旅程长度值小的染色 体. 倒位变异算子：在个体编码串中随机选择两个 城市, 第一个城市的右城市与第二个城市之间的 编码倒序排列,从而产生一个新个体. 如,若有父 个体P ( 1 4 5 2 3 6 ) ,假设随机选择的城市是4 ,3 ,那么产生的新个体为Offspring (1 4 3 2 5 6) . 33 by 谢广明 ， 20052006学年度第一学期 算法改进 遗传算法本质上依赖于问题的编码以及遗 传操作算子. 要发展遗传算法也要以这几个 方面作为突破口 解决实际问题，经验往往要起到决定性作 用，不要期望能很快很好的解决问题 多亲和单亲遗传算法 多目标优化问题 和其他优化算法整合，取长补短 34 by 谢广明 ， 20052006学年度第一学期