第八讲遗传算法ppt课件.ppt
第8讲：遗传算法,1. 遗传算法概述2. 遗传算法的生物学背景3. 基本遗传算法的构成要素4. 基本遗传算法举例5. 遗传算子6. 遗传算法的高级实现技术7. 遗传算法的应用8. 应用遗传算法的即兴解决方案9. 文化基因,1. 遗传算法概述,1.1 遗传算法的地位1.2 遗传算法的特点,1.1 遗传算法的地位,爱因斯坦的相对论伽罗华的群论歌德尔的不完备定理John Holland的遗传算法用于优化问题,1.2 遗传算法的特点,遗传算法是一个随机搜索算法，特别适用于具有多参数、多变量、多目标的复杂优化问题遗传算法对于待求解问题的指标没有特殊要求，比如连续性、导数存在、单峰假设等，甚至显式指标函数也可以没有一旦编码完成，遗传算法几乎不需要任何与问题有关的知识，唯一需要的信息是适应值计算遗传算法具有天然的并行性，适用于并行求解,2. 遗传算法的生物学背景,2.1 达尔文的困惑2.2 进化之河中的高山鱼2.3 自然选择对两性分工的安排2.4 自然选择对群体进化的安排2.5 无性生殖两性生殖(普遍规律)2.6 两性生殖的不得已和优越性,3. 基本遗传算法的构成要素,3.1 染色体编码方法3.2 适应度函数3.3 遗传算子3.4 运行参数,3.1 染色体编码方法,二进制编码非二进制编码,3.2 适应度函数,模拟自然选择的过程用来评估一个染色体优劣的绝对值，或者一个染色体相对于整个群体的相对值的大小,3.3 遗传算子,选择算子交叉算子变异算子,3.4 运行参数,N: 群体大小，即群体中所含个体的数量，一般为20100T: 遗传算法的终止进化代数，一般取100500pc: 交叉概率，一般取0.40.9pm: 变异概率，一般取0.00010.1,4. 基本遗传算法举例,4.1 问题描述4.2 问题转换和参数设定4.3 第0代情况4.4 第0代交配情况4.5 第1代情况4.6 第1代交配情况4.7 第1代变异情况4.8 第2代情况4.9 第2代交配情况,4.1 问题描述,问题：求函数f(x) = x2的最大值，其中x为区间0,31间的整数,直接求解这个问题很简单，因为在区间0,31间函数是单调上升的，因此，最大值在x=31处取得。,但这里要利用遗传算法解决这一问题。,4.2 问题转换和参数设定,用5位二进制数表示x的定义域0,31。例如00000表示x=0；11111表示x=31。用函数本身作为适应度函数：F(x) = f(x)假设群体规模为4，交配概率pc=100%，变异概率pm=1%随机生成初始群体为01101，11000，01000，10011,4.3 第0代情况,经选择，得到第0代的种群为：01101，11000，11000，10011,4.4 第0代交配情况,经过选择，得到新的群体11011，11001，10000，但第3位基因均为0，所以通过交配不能得到最优解，已经过早地陷入局部最优解早熟,4.5 第1代情况,第1代选择了个体11001（1次），11011（2次），10000（1次）,4.6 第1代交配情况,交配完成后，最大适应值并没有发生变化。但由于变异概率较小，假设在这一代中恰好发生变异，而前面的操作过程中没有发生变异。,4.7 第1代变异情况,变异使得种群的基因具有多样性，从而使种群具有多样性，克服了可能发生早熟的问题。,4.8 第2代情况,第2代把第1代经过变异之后的个体全部保存了下来。,4.9 第2代交配情况,第2代交配完成后，已经找到最优解，以后无论采取什么操作，适应值不会超过961，遗传算法已经收敛。,5. 遗传算子,5.1 编码问题5.2 选择算子5.3 交叉算子5.4 变异算子,5.1 编码问题,5.1.1 二进制编码的精度5.1.2 整数编码（符号编码）的优点和缺陷5.1.3 实数编码的实现方法,5.1.1 二进制编码的精度,区间a,b上的实数，当用n位二进制表示时，其分辨率，即最大误差为：,如果允许的最大误差为：则,即：,例：如果区间为0,31，最大误差为1/8，则,5.1.2 整数编码（符号编码）的优点和缺陷,二进制编码可以使得编码长度最小，而符号编码一般要存在冗余经过交叉和变异操作，二进制数仍然会在定义域之内，但符号编码则有可能得到一个不成活的个体整数编码能够按照问题本身直接编码,5.1.3 实数编码的实现方法,算术平均：取两个对应的亲本的基因所取的算术平均值几何平均：取两个对应的亲本的基因所取的几何平均值扩展：取两个值的差，然后将这个差值加到较大的一个值上面，或从较小的一个值中减去,随机取代：将相应的值替换成随机的一个值漂移：加上或渐去一个随机产生的值几何漂移：乘以一个接近1的随机值,交叉算子：,变异算子：,5.1.3 实数编码的实现方法(续),适合于精度要求较高的问题便于较大空间的遗传搜索改善了遗传算法的计算复杂性，提高了效率便于遗传算法与经典优化算法混合使用便于设计针对问题的专门知识型算子便于处理复杂的决策约束条件,5.2 选择算子,5.2.1 概率选择算子5.2.2 适应值变换选择算子5.2.3 排序选择算子5.2.4 最优保存策略,5.2.1 概率选择算子,设群体的规模为N，F(xi)是第i个染色体的适应值，则第i个染色体被选中的概率为：,x1,x2,x3,x4,x5,x6,随机性选择,确定性选择,然后在随机选择,个个体于有尾数的群体中,5.2.2 适应值变换选择算子,若适应值总体上偏离0点，则要进行转换，使得某个个体不会被大量重复选中，从而降低群体的多样性。变换的方式可以是线性变换，也可以是非线性变换,5.2.3 排序选择算子,对所有个体按照适应值的大小排序，排序之后选择个体的概率只与排序后的位置有关，而和适应值的大小无关。这也可以减少早熟的可能性。,5.2.4 最优保存策略,每一代中的最佳个体（一个或多个）要保存下来已经证明，这种最优保存策略可以保证遗传算法收敛；否则不能保证其收敛这与人工选择、保留物种的做法是一致的,5.3 交叉算子,5.3.1 双亲双子法5.3.2 变化交配法5.3.3 多交配位法5.3.4 双亲单子法,5.3.5 常规整数交配法5.3.6 基于次序的整数交配5.3.7 基于位置的整数交配,5.3.1 双亲双子法,a1 a2 ai ai+1 anb1 b2 bi bi+1 bn,a1 a2 ai bi+1 bnb1 b2 bi ai+1 an,交配前,交配后,交叉位置,5.3.2 变化交配法,有些情况下，采用双亲双子交叉算子得到的两个子染色体与其双亲完全一致，这样的交配没有任何作用。变化交配法就是在随机产生交配位置时，排除掉这样的交配位置,1 1 0 1 0 0 11 1 0 0 0 1 0,5.3.3 多交配位法,单交配位方法只能交换一个片段的基因序列，但多交配位方法能够交换多个片段的基因序列,1 1 0 1 0 0 11 1 0 0 0 1 0,1 1 0 0 0 0 01 1 0 1 0 1 1,交配前,交配后,5.3.4 双亲单子法,两个染色体交配后，只产生一个子染色体。通常是从一般的交配法得到的两个子染色体中随机地选择一个，或者选择适应值较大的那一个子染色体,5.3.5 常规整数交配法,随机产生交配位，子代中首先保留一个父代中的一个片段，另外的片断从第二个父代中按照出现的先后顺序选取,1 2 3 4 5 6 7 85 2 1 7 3 8 4 6,1 2 3 4 5 7 8 65 2 1 7 3 4 6 8,5.3.6 基于次序的整数交配,随机产生若干个位置，把这些位置中的基因在另外的父染色体中删除并重新按照原来顺序置换,父代1：1 2 3 4 5 6 7 8 9 10父代2：5 9 2 4 6 1 10 7 3 8位置： * * * *,子代2：2 9 3 4 6 1 10 7 5 8,5.3.7 基于位置的整数交配,与常规的整数交配规则类似，只是在位置的选取方面是随机的，而不是切块的,父代1：1 2 3 4 5 6 7 8 9 父代2：5 9 2 4 6 1 7 3 8位置： * * * *,子代1：? 9 2 ? 6 ? ? 3 ?,子代1：1 9 2 4 6 5 7 3 8,5.4 变异算子,二进制的翻转变异基于位置的变异基于置换的变异基于乱序的变异,5.4.1 二进制的翻转变异,随机产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”,1 1 0 1 1 0 1,1 1 0 1 0 0 1,变异前,变异后,5.4.2 基于位置的变异,随机产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前,2 1 3 6 4 5 7 * *,2 4 1 3 6 5 7,变异前,变异后,5.4.3 基于置换的变异,随机产生两个变异位，然后将这两个位置上的基因互换,2 1 3 6 4 5 7 * *,2 4 3 6 1 5 7,变异前,变异后,5.4.4 基于乱序的变异,随机选择染色体上的一段，然后搭乱在这一段上的基因次序,2 1 3 6 4 5 7 * * * *,2 4 3 1 6 5 7,变异前,变异后,6. 遗传算法的高级实现技术,6.1 小生境遗传算法6.2 混合遗传算法6.3 与其他优化技术结合的遗传算法,6.1 小生境遗传算法,6.1.1 小生境遗传算法的生物学背景6.1.2 基于选择的小生境实现方法6.1.3 基于排挤的小生境实现方法6.1.4 基于共享函数的小生境实现方法,6.1.1 小生境遗传算法的生物学背景,小生境是特定环境下的生存环境相同的物种生活在一起，共同繁衍后代在某一特定的地理区域内，但也能进化出优秀的个体能够帮助寻找全部全局最优解和局部最优解（峰顶）,6.1.2 基于选择的小生境实现方法,只有当新产生的子代适应度超过其父代个体的适应度时，才进行替换，否则父代保存在群体中这种选择方式有利于保持群体的多样性这种方法有利于使得某些个体成为它所在区域中的最优个体,6.1.3 基于排挤的小生境实现方法,设置一个排挤成员的规模N，随机地在群体中选取N个个体，这些个体用来排挤哪些新产生的、与它们相似的个体相似形可以用海明距离定义这种方法同样也可以增加群体的多样性,6.1.4 基于共享函数的小生境实现方法,相似的个体共享同一个适应度函数，在适应值方面不再有区别定义为相似的个体具有相同的被选择的概率，从而不会因某个个体适应值过大而造成群体多样性的损失,6.2 混合遗传算法,嵌套使用遗传算法。局部遗传算法用来寻找局部最优解，而全局遗传算法利用局部遗传算法的结果寻找全局最优解全局算法和局部算法是交互的全局算法和局部算法应该使用相同的编码机制,6.3 与其他优化技术结合的遗传算法,6.3.1 与梯度法的结合6.3.2 与其它离散优化技术的结合6.3.3 与其它方法结合时的注意事项,6.3.1 与梯度法的结合,遗传算法虽然能避免陷入局部最优解，但也很难搜索到全局最优解，而只能搜索到全局次优解与梯度法结合就是在主峰所在的区域上继续爬坡其综合代价是比较小的，但比较容易搜索到全局最优,6.3.2 与其它离散优化技术的结合,与梯度法对应的离散优化技术没有固定的形式，其优化策略都是因问题而定的与梯度法对应的离散优化技术通常也需要沿最速上升（或下降）的方向，使用穷举（或近似穷举）法寻找方向，使用贪心法前进,6.3.3 与其它方法结合时的注意事项,一般不要仅对遗传算法结束时的最优个体进行继续优化，而要对遗传算法结束时的一系列最优个体继续优化，从中选择最终的最优解结合的遗传算法更能体现群体多样性的中重要性,7. 遗传算法的应用,搜索隐马尔科夫模型的参数集解决神经元网络的过早收敛和过慢收敛的问题多参数的系统优化问题,8. 应用遗传算法的即兴解决方案,提出优化问题讨论使用遗传算法的解决方案补充解决方案,9. 文化基因,9.1 文化与自然选择的对抗9.2 自然选择作用的弱化和文化选择的强化9.3 自然进化对文化进化的启示9.4 全球一体化过程中的文化基因的生存和淘汰,9.1 文化与自然选择的对抗,糖尿病遗传性高度近视猴子洗食物世袭制,9.2 自然选择作用的弱化和文化选择的强化,在人种选择过程中消失的尼安德特人英联邦国家的民主和法律宗教的作用,9.3 自然进化对文化进化的启示,生物的全面发展与高度异化被军备竞赛拖垮的前苏联综合国力问题生物多样性与文化的包容性我们的机遇和挑战,9.4 全球一体化过程中的文化基因的生存和淘汰,全球一体化是不可避免的趋势我们的责任,
