第八讲遗传算法ppt课件.ppt

《第八讲遗传算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8讲：遗传算法1.遗传算法概述2.遗传算法的生物学背景3.基本遗传算法的构成要素4.基本遗传算法举例5.遗传算子6.遗传算法的高级实现技术7.遗传算法的应用8.应用遗传算法的即兴解决方案9.文化基因1.遗传算法概述1.1遗传算法的地位1.2遗传算法的特点1.1遗传算法的地位爱因斯坦的相对论伽罗华的群论歌德尔的不完备定理JohnHolland的遗传算法—用于优化问题1.2遗传算法的特点遗传算法是一个随机搜索算法，特别适用于具有多参数、多变量、多目标的复杂优化问题遗传算法对于待求解问题的指标没有特殊要求，比如连续性

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遗传算子选择算子交叉算子变异算子3.4运行参数N:群体大小，即群体中所含个体的数量，一般为20—100T:遗传算法的终止进化代数，一般取100—500pc:交叉概率，一般取0.4—0.9pm:变异概率，一般取0.0001—0.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问题描

4、述问题：求函数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代情况经选择，得到第0代

5、的种群为：01101，11000，11000，100114.4第0代交配情况经过选择，得到新的群体11011，11001，10000，但第3位基因均为0，所以通过交配不能得到最优解，已经过早地陷入局部最优解—早熟4.5第1代情况第1代选择了个体11001（1次），11011（2次），10000（1次）4.6第1代交配情况交配完成后，最大适应值并没有发生变化。但由于变异概率较小，假设在这一代中恰好发生变异，而前面的操作过程中没有发生变异。4.7第1代变异情况变异使得种群的基因具有多样性，从而使种群具有多样性，克服了

6、可能发生早熟的问题。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位二进制表示时，其分辨率，即最大误差为：如果允许的最大误差为ε：则即：例：如果区间为

7、[0,31]，最大误差ε为1/8，则5.1.2整数编码（符号编码）的优点和缺陷二进制编码可以使得编码长度最小，而符号编码一般要存在冗余经过交叉和变异操作，二进制数仍然会在定义域之内，但符号编码则有可能得到一个不成活的个体整数编码能够按照问题本身直接编码5.1.3实数编码的实现方法算术平均：取两个对应的亲本的基因所取的算术平均值几何平均：取两个对应的亲本的基因所取的几何平均值扩展：取两个值的差，然后将这个差值加到较大的一个值上面，或从较小的一个值中减去随机取代：将相应的值替换成随机的一个值漂移：加上或渐去一个随机产

8、生的值几何漂移：乘以一个接近1的随机值交叉算子：变异算子：5.1.3实数编码的实现方法(续)适合于精度要求较高的问题便于较大空间的遗传搜索改善了遗传算法的计算复杂性，提高了效率便于遗传算法与经典优化算法混合使用便于设计针对问题的专门知识型算子便于处理复杂的决策约束条件5.2选择算子5.2.1概率选择算子5.2.2适应值变换选择算子5.2.3排序选择算子5.2.4最优保存策