By 谢广明 ， 2005~2006 学年度第一学期 1 Genetic Algorithm ， GA 第二章 遗传算法 (II)

Presentation on theme: "By 谢广明 ， 2005~2006 学年度第一学期 1 Genetic Algorithm ， GA 第二章 遗传算法 (II)"— Presentation transcript:

1 by 谢广明 ， 2005~2006 学年度第一学期 1 Genetic Algorithm ， GA 第二章 遗传算法 (II)

2 by 谢广明 ， 2005~2006 学年度第一学期 2 内 容  简单演示  应用实例 1 ： TSP  应用实例 2 ：函数优化  策略设计  算法改进

3 by 谢广明 ， 2005~2006 学年度第一学期 3 简单演示 问题：求 （ 1 ）编码： 编码长度为 5 （ 2 ）初始群体生成：群体大小设置为 4 ，随机产生四 个个体： 编码： 01101 ， 11000 ， 01000 ， 10011 解码： 13 24 8 19 适应度： 169 576 64 361 （ 3 ）适应度函数：

4 by 谢广明 ， 2005~2006 学年度第一学期 4 （ 4 ）轮盘赌选择：选择概率 个体： 01101 ， 11000 ， 01000 ， 10011 适应度： 169 576 64 361 选择概率： 0.14 0.49 0.06 0.31 选择 11000 和 01101 交配产生下一代 简单演示

5 by 谢广明 ， 2005~2006 学年度第一学期 5 （ 5 ）交叉操作：发生交叉的概率取大 交叉点位置的选取是随机的（单点交叉） 0110 1 0110 0 1100 0 1100 1 简单演示

6 by 谢广明 ， 2005~2006 学年度第一学期 6 （ 6 ）变异：发生变异的概率取小 改变某个字节 11001  11101 （ 7 ）新群体的产生： 保留上一代最优个体， 1 个新个体取代旧个体 11101 ， 11000 ， 01000 ， 10011 （ 8 ）重复上述操作 20 次, 或许就能够得到最优解！ 简单演示

7 by 谢广明 ， 2005~2006 学年度第一学期 7 应用实例 1 ： TSP  问题回顾 – 给定 n 个城市以及两两城市之间的距离，求解 一条从某个城市出发、不重复地遍历所有其它 城市并最终又回到起始城市的最短路径。  数学描述 – 给定图 G=(V,E), V 为顶点集, E 为边集，确定 一条长度最短的 Hamilton 回路

8 by 谢广明 ， 2005~2006 学年度第一学期 8 应用实例 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

9 by 谢广明 ， 2005~2006 学年度第一学期 9 应用实例 1 ： TSP  适应度函数 – 就取为目标函数的倒数，即路径总长度的倒数  初始种群 – 随机生成 40 个  终止条件 –2000 次迭代  参数设置 – 自定

10 by 谢广明 ， 2005~2006 学年度第一学期 10 应用实例 1 ： TSP  选择操作算子 : 轮盘式选择  首先计算每个个体 i 被选中 的概率  然后根据概率的大小将将圆 盘分为 n 个扇形，每个扇形 的大小为 。选择时转 动轮盘，参考点 r 落到扇形 i 则 选择个体 i 。...... p1p1 p2p2 pipi r

11 by 谢广明 ， 2005~2006 学年度第一学期 11 应用实例 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 ）

12 by 谢广明 ， 2005~2006 学年度第一学期 12 应用实例 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 ）

13 by 谢广明 ， 2005~2006 学年度第一学期 13 应用实例 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 ）

14 by 谢广明 ， 2005~2006 学年度第一学期 14 应用实例1：TSP应用实例1：TSP

15 by 谢广明 ， 2005~2006 学年度第一学期 15 应用实例 1 ： TSP  中国城市 TSP 的一个参考解

16 by 谢广明 ， 2005~2006 学年度第一学期 16 应用实例 2 ：函数优化  函数优化 – 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理， 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如； [0 ， 1] ，计算精度 0.001, 则 0 ， 0.001,0.002, …,0.998,0.999,1.000 ， 个数为 1001 则用长度为 10 的二进制字符串一次表征所有离散点 0000000000 ， 0000000001 ， …,1111110001.

17 by 谢广明 ， 2005~2006 学年度第一学期 17 应用实例 2 ：函数优化  适应度函数 – 例如， f(x)=x 2 - x 5 ，取 C max =2, 即可得到满足要 求的 F(x)

18 by 谢广明 ， 2005~2006 学年度第一学期 18 应用实例 2 ：函数优化  其它的就类似于 TSP 的求解了

19 by 谢广明 ， 2005~2006 学年度第一学期 19 策略调整  针对不同实际问题需要调整相应策略  同一个实际问题不同的人也有不同的做法  编码方案  适应度函数设计  选择算子  交叉算子  变异算子  初始种群

20 by 谢广明 ， 2005~2006 学年度第一学期 20 策略调整  编码方案 – 本质：如何表示解 – 二进制：  自变量高维、大范围连续、高精度的时候很难处理  冗余问题，离散化后解的个数介于 2 (n-1) 和 2 n 之间 –D 进制, D=3,8,16, … – 实数编码：无需编码和解码 – 序列编码：例如 TSP 的路径表达 – 树编码：非定长 – 自适应编码 - 长度可调节

21 by 谢广明 ， 2005~2006 学年度第一学期 21 策略调整  适应度函数 – 是进行自然选择的定量标准 – 直接采用目标函数 – 引入适应值调节  线性变换  乘幂变换  指数变换  自适应变换

22 by 谢广明 ， 2005~2006 学年度第一学期 22 策略调整  选择算子 – 轮盘赌选择 (roulette wheel selection)  最基本、最常用的方式，又叫适应度比例选择算子 – 最佳个体保存 (elitist model)  把适应度最高的个体保留到下一代，又叫精英保留 – 排序模型 (rank - based model)  按适应度函数大小排序，根据事先设定的概率表分配选择概率 – 联赛选择模型 (tournament selection model)  随机选择几个进行比较，高的被选，又叫锦标赛模型

23 by 谢广明 ， 2005~2006 学年度第一学期 23 策略调整  选择算子 – 期望值模型 (expected value model) – 排挤模型 (crowding model) – 浓度控制策略 – 共享机制 – 截断选择

24 by 谢广明 ， 2005~2006 学年度第一学期 24 策略调整  交叉算子 – 简单交叉  最基本、最常用的方式，双亲互换子串 – 平坦交叉  二者之间均匀随机产生 – 算术交叉  双亲的凸组合 – 线性交叉  1 ： 1 ， 3 ： 1 ， 1 ： 3 比较最好的两个留下

25 by 谢广明 ， 2005~2006 学年度第一学期 25 策略调整  交叉算子 – 混合交叉 – 离散交叉 – 启发式交叉 – 模拟二进制交叉 – 单峰正态分布交叉 – 单纯形交叉 – 父体中心交叉 – 几何交叉 – 均匀交叉 – 基于模糊联接的交叉

26 by 谢广明 ， 2005~2006 学年度第一学期 26 策略调整  变异算子 – 随机变异  区间内均匀随机取 – 非一致变异  某个区间内随机扰动 – 边界变异  取边界值 – 多项式变异 – 高斯变异 –Cauthy 变异 – 自适应变异 –Muhlenbein 变异

27 by 谢广明 ， 2005~2006 学年度第一学期 27 策略调整  初始种群 – 对计算结果和计算效率有影响 – 全局性要求初始解尽量分散 – 设计一些生成方法

28 by 谢广明 ， 2005~2006 学年度第一学期 28 求解 TSP 的策略调整  编码方案 – 二进制编码：交叉和变异很难处理 – 顺序表示： 1985 年 Grefenstette 提出，序表示是指所有 城市依次排列构成一个顺序表 (order list), 对于一条旅程, 可以依旅行经过顺序处理每个城市, 每个城市在顺序表 中的顺序就是一个遗传因子的表示, 每处理完一个城市, 从顺序表中去掉该城市. 处理完所有城市以后, 将每个城 市的遗传因子表示连接起来, 就是一条旅程的基因表示. 例如, 顺序表 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)

29 by 谢广明 ， 2005~2006 学年度第一学期 29 求解 TSP 的策略调整  编码方案 – 路径表示：最自然、直接的表示方法 – 布尔矩阵表示：将一个旅程定义为一个优先权 布尔矩阵 M, 当且仅当城市 i 排在城市 j 之前时 矩阵元素 m ij = 1. 这种方法用 n × n 矩阵 M 代表一 条旅程, M 具有如下三个性质 :  1) 矩阵中 1 的数目为 n ( n - 1) / 2 ;  2) m ii = 0, i= 1,2,., n ;  3) 若 m ij = 1, 且 m jk = 1, 那么 m ik = 1.

30 by 谢广明 ， 2005~2006 学年度第一学期 30 求解 TSP 的策略调整  选择算子 – 轮盘赌选择 (roulette wheel selection), – 最佳个体保存 (elitist model), – 期望值模型 (expected value model), – 排序模型 (rank - based model), – 联赛选择模型 (tournament selection model) – 排挤模型 (crowding model) – 浓度控制策略 – 上述机制混合

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

32 by 谢广明 ， 2005~2006 学年度第一学期 32 求解 TSP 的策略调整  变异算子 – 全局意义 – 点位变异：变异仅以一定的概率 ( 通常很小 ) 对 串的某些位做值的变异 ; – 逆转变异：在串中, 随机选择两点, 再将这两点内 的子串按反序插入到原来的位置中 ; – 对换变异：随机选择串中的两点, 交换其值 ( 码 ) ; – 插入变异：从串中随机选择 1 个码, 将此码插入 随机选择的插入点中间.

33 by 谢广明 ， 2005~2006 学年度第一学期 33 求解 TSP 的策略调整  变异算子 – 贪心对换变异：从一个染色体中随机的选择两 个城市 ( 即两个码值 ), 然后交换它们, 得到新的染 色体, 以旅程长度为依据比较交换后的染色体与 原来的染色体的大小, 保留旅程长度值小的染色 体. – 倒位变异算子：在个体编码串中随机选择两个 城市, 第一个城市的右城市与第二个城市之间的 编码倒序排列, 从而产生一个新个体. 如, 若有父 个体 P ( 1 4 5 2 3 6 ), 假设随机选择的城市是 4,3, 那么产生的新个体为 Offspring (1 4 3 2 5 6).

34 by 谢广明 ， 2005~2006 学年度第一学期 34 算法改进  遗传算法本质上依赖于问题的编码以及遗 传操作算子. 要发展遗传算法也要以这几个 方面作为突破口  解决实际问题，经验往往要起到决定性作 用，不要期望能很快很好的解决问题  多亲和单亲遗传算法  多目标优化问题  和其他优化算法整合，取长补短