遗传算法演示文稿修改.ppt

遗传算法遗传算法遗传算法发展历史遗传算法发展历史 遗传算法(Genetic Algorithm,简称GA)起源于对生物系统所进行的计算机模拟研究. 美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发,创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术—遗传算法. 1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本定理——模式定理(Schcma Theorem)，并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and Artificial Systems》 20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念1975年DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。

1989年Goldberg出版了专著，系统地总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及其应用 1991年，Davis出版了《Handbook of Genetic Algorithms》一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例 1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming ，简称GP)的概念 从遗传算法的整个发展过程来看，20世纪70年代是兴起阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视遗传算法的应用领域遗传算法的应用领域（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度问题 （5）图像处理 （6）机器人学 （7）人工生命 （8）数据挖掘 （9）机器学习遗传算法基本思路遗传算法基本思路基于模仿生物界遗传学的遗传过程把问题的参数用基因代表，问题的解用染色体代表，从而得到一个由具有不同染色体的个体组成的群体。

这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解遗传算法中的生物遗传学概念遗传算法中的生物遗传学概念序号遗传学概念遗传算法概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值, 一般为0.001~0.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解遗传算法的步骤和实现方法遗传算法的步骤和实现方法（1)选择编码策略，把参数集合（可行解集合）转换染色体结构空间；（2)定义适应函数，便于计算适应值；（3)确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；（4)随机产生初始化群体；（5)计算群体中的个体或染色体解码后的适应值；（6)按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；（7)判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步。

参数编码种群1计算适配值满足要求遗传操作种群2解码否是选择交叉变异倒位种群2>种群1寻优结束开始1.1.编码编码 浮点编码遗传算法的编码共三种 符号编码 二进制编码二进制编码既符合计算机处理信息的原理，也方便了对染色体进行遗传，变异和突变等操作 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤编码方法影响到交叉算子、变异算子等遗传算子的运算方法，很大程度上决定了遗传进化的效率2.2.解码解码3.3.适应值函数的确定适应值函数的确定遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必须对个体位串的适应性进行评价根据个体适应值可以决定它在此环境下的生存能力一般来说，好的染色体位串结构具有比较高的适应值，即可以取得较高的评价，具有较强的生存能力为了能够直接将适应值函数与群体中个体的优劣度量相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好4.4.遗传算子遗传算子（（1 1）选择）选择目标目标：把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代常用的选择算子有：常用的选择算子有：适应度比例算法，随机遍历抽样法，局部选择法。

比例选择算子比例选择算子(2)(2)交叉交叉 所谓交叉是指把两个父代个体的部分结构加以替换重组从而生成新个体的操作通过交叉，遗传算法的搜索能力得以飞跃提高单点交叉单点交叉 一点交叉又称单点交叉，是由Holland提出的最基本的一种交叉方式具体操作是：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并形成两个新个体 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 1两点两点交叉交叉 两点交叉与单点交叉操作类似，只是设定了两个交叉点（依然是随机设定的） 1 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 多点交叉 一致交叉变异变异 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动就基于字符集{O，1}的二值码串，变异操作就是把某些基因座上的基因值取反，即1-O或O-1。

S = 1 0 1 0 0 1 1 S'= 1 0 1 1 0 1 1倒位倒位 倒位是指一个染色体某区段正常排列顺序发生180̊ 的颠倒，造成染色体内的DNA序列重新排列 S = 1 1 0 1 0 0 1 0 S'= 1 1 0 0 1 0 1 0遗传算法的特点遗传算法的特点（（1 1））遗遗传传算算法法是是对对参参数数的的编编码码进进行行操操作作，，而而非非对对参数本身；参数本身； （（2 2））遗遗传传算算法法同同时时使使用用多多个个搜搜索索点点的的搜搜索索信信息息遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高；（（3 3））遗遗传传算算法法在在解解空空间间进进行行高高效效启启发发式式搜搜索索，，而非盲目地穷举或完全随机搜索； （（4 4））遗遗传传算算法法直直接接以以目目标标函函数数作作为为搜搜索索信信息息遗传算法使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。

遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等；（（5 5））遗遗传传算算法法具具有有并并行行计计算算的的特特点点，因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化；（（6 6））遗遗传传算算法法使使用用概概率率搜搜索索技技术术遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体；（（7 7））遗遗传传算算法法对对于于待待寻寻优优的的函函数数基基本本无无限限制制，它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广 遗传算法的拓展遗传算法的拓展谢谢谢谢。