GA2-遗传算法实例

1、by 谢广明 ， 20052006学年度第一学期,1,Genetic Algorithm，GA,遗传算法 (II),by 谢广明 ， 20052006学年度第一学期,2,内 容,应用实例1： TSP 应用实例2：函数优化 策略设计 算法改进,by 谢广明 ， 20052006学年度第一学期,3,应用实例1：TSP,问题回顾 给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。 数学描述 给定图G=(V,E), V为顶点集, E为边集，确定一条长度最短的Hamilton回路,by 谢广明 ， 20052006学年度第一学期,4,应用

2、实例1：TSP,编码方案 路径表达：对一个旅行最自然的表达 一个旅行 517894623 的编码就是（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 谢广明 ， 20052006学年度第一学期,5,应用实例1：TSP,适应度函数 就取为目标函数的倒数，即路径总长度的倒数 初始种群 随机生成40个 终止条件 2000次迭代 参数设置 自定,by 谢广明 ， 20052006学年度第一学期,6,应用实例1：T

3、SP,选择操作算子: 轮盘式选择 首先计算每个个体 i 被选中的概率 然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为 。选择时转动轮盘，参考点r落到扇形i则选择个体i 。,by 谢广明 ， 20052006学年度第一学期,7,应用实例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

4、 | X X ）,by 谢广明 ， 20052006学年度第一学期,8,应用实例1：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）,by 谢广明 ， 20052006学年度第一学期,9,应用实例1：TSP,变异操作算子 采用倒置变异：在染色体上随机地选择两点，将两点间的子串反转 例如 原个体：（1 2 3 4 5 6 7 8 9） 随机选择两点：（1 2 | 3 4 5 6 | 7 8 9） 倒

5、置后的个体：（1 2 | 6 5 4 3 | 7 8 9）,by 谢广明 ， 20052006学年度第一学期,10,应用实例1：TSP,by 谢广明 ， 20052006学年度第一学期,11,应用实例1：TSP,中国城市TSP的一个参考解,by 谢广明 ， 20052006学年度第一学期,12,应用实例2：函数优化,函数优化 编码方案采用二进制编码 对子变量定义域根据计算精度进行离散化处理， 然后根据离散化后待定解的个数选择合适长度的 二进制字符串进行编码 例如；0，1，计算精度0.001, 则0，0.001,0.002,0.998,0.999,1.000， 个数为1001 则用长度为10的二

6、进制字符串一次表征所有离散点 0000000000，0000000001，,1111110001.,by 谢广明 ， 20052006学年度第一学期,13,应用实例2：函数优化,适应度函数 例如，f(x)=x2 - x5 ，取Cmax=2, 即可得到满足要求的F(x),by 谢广明 ， 20052006学年度第一学期,14,应用实例2：函数优化,其它的就类似于TSP的求解了,by 谢广明 ， 20052006学年度第一学期,15,策略调整,针对不同实际问题需要调整相应策略 同一个实际问题不同的人也有不同的做法 编码方案 适应度函数设计 选择算子 交叉算子 变异算子 初始种群,by 谢广明 ，

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

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

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

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

11、处理完所有城市以后,将每个城市的遗传因子表示连接起来,就是一条旅程的基因表示. 例如,顺序表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),by 谢广明 ， 20052006学年度第一学期,25,求解TSP的策略调整,编码方案 路径表示：最自然、直接的表示方法 布尔矩阵表示：将一个旅程定义为一个优先权布尔矩阵M ,当且仅当城市 i 排在城市j 之前时矩阵元素mij = 1. 这种方法用n n 矩阵M 代表一条旅

12、程, M具有如下三个性质: 1) 矩阵中1 的数目为n ( n - 1) / 2 ; 2) mii = 0 , i= 1 ,2 , ., n ; 3) 若mij = 1 ,且mjk = 1 ,那么mik = 1.,by 谢广明 ， 20052006学年度第一学期,26,求解TSP的策略调整,选择算子 轮盘赌选择(roulette wheel selection), 最佳个体保存(elitist model) , 期望值模型(expected value model) , 排序模型(rank - based model), 联赛选择模型(tournament selection model) 排

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

14、调整,变异算子 全局意义 点位变异：变异仅以一定的概率(通常很小) 对串的某些位做值的变异; 逆转变异：在串中,随机选择两点,再将这两点内的子串按反序插入到原来的位置中; 对换变异：随机选择串中的两点,交换其值(码) ; 插入变异：从串中随机选择1 个码,将此码插入随机选择的插入点中间.,by 谢广明 ， 20052006学年度第一学期,29,求解TSP的策略调整,变异算子 贪心对换变异：从一个染色体中随机的选择两个城市(即两个码值) ,然后交换它们,得到新的染色体,以旅程长度为依据比较交换后的染色体与原来的染色体的大小,保留旅程长度值小的染色体. 倒位变异算子：在个体编码串中随机选择两个城市, 第一个城市的右城市与第二个城市之间的编码倒序排列,从而产生一个新个体. 如