第5章 遗传算法及应用.ppt

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

1、遗传算法及应用遗传算法是一种新发展起来的基于优胜劣汰、自然选择、适者生存和基因遗传思想的优化算法，60年代产生于美国的密执根大学。5.1遗传算法的原理与特点Darwin的进化论：优胜劣汰，适者生存。Mendel的基因遗传学：遗传是作为一种指令码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质，每个基因产生的个体对环境有一定的适应性，基因杂交和基因突变可能产生对环境适应性更强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。15.1.1遗传算法的基本原理遗传算法将问题的求解表示成“染色体”（用编码表示字符串）。该算法从一群“染色体”串出发

2、，将它们置于问题的“环境”中，根据适者生存的原则，从中选择出适应环境的“染色体”进行复制，通过交叉、变异两种基因操作产生出新的一代更适应环境的“染色体”种群。随着算法的运行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。25.1.1遗传算法的基本原理常规的寻优方法主要有三种类型：解析法：间接法是通过让目标函数的梯度为零，进而求解一组非线性方程来寻求局部极值。直接法是使梯度信息按最陡的方向逐次运动来寻求局部极值，它即为通常所称的爬山法。枚举法：可寻找到全局极值，不需要目标函数连续光滑。随机法：搜索空间中随机地漫游并随时记录下所取得的最好结果。35.1.2遗传算法的特点1)遗传算

3、法是对参数的编码进行操作，而不是对参数本身；2)遗传算法是从许多初始点开始并行操作，因而可以有效地防止搜索过程收敛于局部最优解，而且有较大的可能求得全部最优解；3)遗传算法通过目标函数来计算适配度，而不需要其它的推导和附属信息，从而对问题的依赖性较小；4)遗传算法使用概率的转变规则，而不是确定性的规则；5)遗传算法在解空间内不是盲目地穷举或完全随机测试，而是一种启发式搜索，其搜索效率往往优于其它方法；6)遗传算法对于待寻优的函数基本无限制，因而应用范围很广；7)遗传算法更适合大规模复杂问题的优化。45.2遗传算法的基本操作与模式理论设需要求解的优化问题为寻找当自变量x在0～31之间取整数

4、值时函数f(x)=x2的最大值。第一步：准备工作“染色体”串的编码采用二进制数来对其进行编码，可用5位数来表示。例如01010对应x=10，11111对应x=31。初始种群的产生设种群大小为4，即含有4个个体，则需按位随机生成4个5位二进制串：01101、11000、01000、1001155.2.1.1复制操作复制(Copy)亦称再生(Reproduction)或选择(Selection)，复制过程是个体串按照它们的适配度进行复制。本例中目标函数值即可用作适配度。按照适配度进行串复制的含义是适配度越大的串，在下一代中将有更多的机会提供一个或多个子孙。5.2.1遗传算法的基本操作6种群的

5、初始串及对应的适配度序号串X值适配度占整体的百分数%期望的复制数实际得到的复制数1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23总计1170100.04.00平均29325.01.00最大值57649.01.975.2.1.1复制操作5.2.1遗传算法的基本操作7经复制后的新的种群为01101110001100010011串1被复制了一次串2被复制了两次串3被淘汰串4也被复制了一次5.2.1.1复制操作5.2.1遗传算法的基本操作8种群的初始串及对应的适配度序号串X值适配度占整体的百分数%期

6、望的复制数实际得到的复制数1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231总计1170100.04.004平均29325.01.001最大值57649.01.9729交叉(Crossover)操作可分为两步：第一步—将新复制产生的匹配池中的成员随机两两匹配。第二步—进行交叉繁殖。设串的长度为l，则串的l个数字位之间的空隙标记为1，2，…，l-１。随机地从[1，l-1]中选取一整数位置k，则将两个父母串中从位置k到串末尾的子串互相交换，而形成两个新串。5.2.1.2交叉操作5.2.1遗

7、传算法的基本操作10本例中初始种群的两个个体假定从１到４间选取随机数，得到k＝４，那么经过交叉操作之后将得到如下两个新串5.2.1.2交叉操作5.2.1遗传算法的基本操作11新串号匹配池匹配对象交叉点新种群x值适配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256总计1754平均439最大值729交叉操作12变异(Mutation