第八讲遗传算法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.14.基本遗传算法举例基本遗传算法举例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，100114.3 第第0代情况代情况序号群体适应值选择概率期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.851.231经选择，得到第0代的种群为：01101，11000，11000，100114.4 第第0代交配情况代交配情况序号群体交配对象交配位子代适应值1011012401100144211000141100162531100042110117294100113210000256经过选择，得到新的群体11011，11001，10000，但第3位基因均为0，所以通过交配不能得到最优解，已经过早地陷入局部最优解早熟4.5 第第1代情况代情况序号群体适应值选择概率期望次数选中次数1011001448.210.33021100162535.621.42131100172941.561.66241000025614.600.581第1代选择了个体11001（1次），11011（2次），10000（1次）4.6 第第1代交配情况代交配情况序号群体交配对象交配位子代适应值1110012311011729211011131100162531101141100002564100003111011729交配完成后，最大适应值并没有发生变化。但由于变异概率较小，假设在这一代中恰好发生变异，而前面的操作过程中没有发生变异。4.7 第第1代变异情况代变异情况序号群体是否变异变异位新群体适应值111011否11011729211001是311101841310000否10000256411011否11011729变异使得种群的基因具有多样性，从而使种群具有多样性，克服了可能发生早熟的问题。4.8 第第2代情况代情况序号群体适应值选择概率期望次数选中次数11101172928.531.14121110184132.921.31131000025610.020.40141101172928.531.141第2代把第1代经过变异之后的个体全部保存了下来。4.9 第第2代交配情况代交配情况序号群体交配对象交配位子代适应值1110112311001625211101131111196131000042100012894110113211010676第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个染色体被选中的概率为：x1x2x3x4x5x6随机性选择随机性选择确定性选择确定性选择然后在随机选择个个体于有尾数的群体中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 bna1 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 05.3.3 多交配位法多交配位法单交配位方法只能交换一个片段的基因序列，但多交配位方法能够交换多个片段的基因序列1 1 0 1 0 0 11 1 0 0 0 1 01 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 61 2 3 4 5 7 8 65 2 1 7 3 4 6 85.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 85.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 85.4 变异算子变异算子二进制的翻转变异基于位置的变异基于置换的变异基于乱序的变异5.4.1 二进制的翻转变异二进制的翻转变异随机产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”1 1 0 1 1 0 11 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 全球一体化过程中的文化全球一体化过程中的文化基因的生存和淘汰基因的生存和淘汰全球一体化是不可避免的趋势我们的责任