822第二章遗传算法 (II).ppt
by 谢广明，20052006学年度第一学期,1,Genetic Algorithm，GA,第二章 遗传算法(II),by 谢广明，20052006学年度第一学期,2,内 容,简单演示应用实例1：TSP应用实例2：函数优化策略设计算法改进,by 谢广明，20052006学年度第一学期,3,简单演示,问题：求（1）编码：编码长度为5（2）初始群体生成：群体大小设置为4，随机产生四个个体：编码：01101，11000，01000，10011 解码：13 24 8 19 适应度：169 576 64 361（3）适应度函数：,by 谢广明，20052006学年度第一学期,4,（4）轮盘赌选择：选择概率 个体：01101，11000，01000，10011 适应度：169 576 64 361 选择概率：0.14 0.49 0.06 0.31选择 11000 和 01101交配产生下一代,简单演示,by 谢广明，20052006学年度第一学期,5,（5）交叉操作：发生交叉的概率取大交叉点位置的选取是随机的（单点交叉）0110 1 0110 0 1100 0 1100 1,简单演示,by 谢广明，20052006学年度第一学期,6,（6）变异：发生变异的概率取小改变某个字节 11001 11101（7）新群体的产生：保留上一代最优个体，1个新个体取代旧个体 11101，11000，01000，10011（8）重复上述操作20次,或许就能够得到最优解！,简单演示,by 谢广明，20052006学年度第一学期,7,应用实例1：TSP,问题回顾给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。数学描述给定图G=(V,E),V为顶点集,E为边集，确定一条长度最短的Hamilton回路,by 谢广明，20052006学年度第一学期,8,应用实例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学年度第一学期,9,应用实例1：TSP,适应度函数就取为目标函数的倒数，即路径总长度的倒数初始种群随机生成40个终止条件2000次迭代参数设置自定,by 谢广明，20052006学年度第一学期,10,应用实例1：TSP,选择操作算子:轮盘式选择首先计算每个个体 i 被选中的概率然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i。,by 谢广明，20052006学年度第一学期,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）,by 谢广明，20052006学年度第一学期,12,应用实例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学年度第一学期,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）,by 谢广明，20052006学年度第一学期,14,应用实例1：TSP,by 谢广明，20052006学年度第一学期,15,应用实例1：TSP,中国城市TSP的一个参考解,by 谢广明，20052006学年度第一学期,16,应用实例2：函数优化,函数优化编码方案采用二进制编码对子变量定义域根据计算精度进行离散化处理，然后根据离散化后待定解的个数选择合适长度的二进制字符串进行编码例如；0，1，计算精度0.001,则0，0.001,0.002,0.998,0.999,1.000，个数为1001则用长度为10的二进制字符串一次表征所有离散点0000000000，0000000001，,1111110001.,by 谢广明，20052006学年度第一学期,17,应用实例2：函数优化,适应度函数例如，f(x)=x2-x5，取Cmax=2,即可得到满足要求的F(x),by 谢广明，20052006学年度第一学期,18,应用实例2：函数优化,其它的就类似于TSP的求解了,by 谢广明，20052006学年度第一学期,19,策略调整,针对不同实际问题需要调整相应策略同一个实际问题不同的人也有不同的做法编码方案适应度函数设计选择算子交叉算子变异算子初始种群,by 谢广明，20052006学年度第一学期,20,策略调整,编码方案本质：如何表示解二进制：自变量高维、大范围连续、高精度的时候很难处理冗余问题，离散化后解的个数介于2(n-1)和2n之间D进制,D=3,8,16,实数编码：无需编码和解码序列编码：例如TSP的路径表达树编码：非定长自适应编码-长度可调节,by 谢广明，20052006学年度第一学期,21,策略调整,适应度函数是进行自然选择的定量标准直接采用目标函数引入适应值调节线性变换乘幂变换指数变换自适应变换,by 谢广明，20052006学年度第一学期,22,策略调整,选择算子轮盘赌选择(roulette wheel selection)最基本、最常用的方式，又叫适应度比例选择算子最佳个体保存(elitist model)把适应度最高的个体保留到下一代，又叫精英保留排序模型(rank-based model)按适应度函数大小排序，根据事先设定的概率表分配选择概率联赛选择模型(tournament selection model)随机选择几个进行比较，高的被选，又叫锦标赛模型,by 谢广明，20052006学年度第一学期,23,策略调整,选择算子期望值模型(expected value model)排挤模型(crowding model)浓度控制策略共享机制截断选择,by 谢广明，20052006学年度第一学期,24,策略调整,交叉算子简单交叉最基本、最常用的方式，双亲互换子串平坦交叉二者之间均匀随机产生算术交叉双亲的凸组合线性交叉1：1，3：1，1：3比较最好的两个留下,by 谢广明，20052006学年度第一学期,25,策略调整,交叉算子混合交叉离散交叉启发式交叉模拟二进制交叉单峰正态分布交叉单纯形交叉父体中心交叉几何交叉均匀交叉基于模糊联接的交叉,by 谢广明，20052006学年度第一学期,26,策略调整,变异算子随机变异区间内均匀随机取非一致变异某个区间内随机扰动边界变异取边界值多项式变异高斯变异Cauthy变异自适应变异Muhlenbein变异,by 谢广明，20052006学年度第一学期,27,策略调整,初始种群对计算结果和计算效率有影响全局性要求初始解尽量分散设计一些生成方法,by 谢广明，20052006学年度第一学期,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),by 谢广明，20052006学年度第一学期,29,求解TSP的策略调整,编码方案路径表示：最自然、直接的表示方法布尔矩阵表示：将一个旅程定义为一个优先权布尔矩阵M,当且仅当城市 i 排在城市j 之前时矩阵元素mij=1.这种方法用n n 矩阵M 代表一条旅程,M具有如下三个性质:1)矩阵中1 的数目为n(n-1)/2;2)mii=0,i=1,2,.,n;3)若mij=1,且mjk=1,那么mik=1.,by 谢广明，20052006学年度第一学期,30,求解TSP的策略调整,选择算子轮盘赌选择(roulette wheel selection),最佳个体保存(elitist model),期望值模型(expected value model),排序模型(rank-based model),联赛选择模型(tournament selection model)排挤模型(crowding model)浓度控制策略上述机制混合,by 谢广明，20052006学年度第一学期,31,求解TSP的策略调整,交叉算子依赖于编码方式基于路径表示的顺序交叉基于路径表示的部分匹配交叉贪心交叉法：在一个父个体中选择第一个城市作为子个体的第一个城市,然后在两个父个体中进行比较并找到与已经选择的那个城市相邻且距离较近的城市作为下一个城市扩展到旅程中;如果与该城市相邻的两个城市有一个已经在旅程中,那么选择另外一个,如果两个都在旅程中,那么就选择其它没有被选择的城市.循环交叉边重组交叉,by 谢广明，20052006学年度第一学期,32,求解TSP的策略调整,变异算子全局意义点位变异：变异仅以一定的概率(通常很小)对串的某些位做值的变异;逆转变异：在串中,随机选择两点,再将这两点内的子串按反序插入到原来的位置中;对换变异：随机选择串中的两点,交换其值(码);插入变异：从串中随机选择1 个码,将此码插入随机选择的插入点中间.,by 谢广明，20052006学年度第一学期,33,求解TSP的策略调整,变异算子贪心对换变异：从一个染色体中随机的选择两个城市(即两个码值),然后交换它们,得到新的染色体,以旅程长度为依据比较交换后的染色体与原来的染色体的大小,保留旅程长度值小的染色体.倒位变异算子：在个体编码串中随机选择两个城市,第一个城市的右城市与第二个城市之间的编码倒序排列,从而产生一个新个体.如,若有父个体P(1 4 5 2 3 6),假设随机选择的城市是4,3,那么产生的新个体为Offspring(1 4 3 2 5 6).,by 谢广明，20052006学年度第一学期,34,算法改进,遗传算法本质上依赖于问题的编码以及遗传操作算子.要发展遗传算法也要以这几个方面作为突破口解决实际问题，经验往往要起到决定性作用，不要期望能很快很好的解决问题多亲和单亲遗传算法多目标优化问题和其他优化算法整合，取长补短,
