遗传算法概述第一讲幻灯片.ppt

遗传算法概述第一讲第1页，共22页，编辑于2022年，星期三信息系统与管理学院 为什么要学习遗传算法？课堂讨论第2页，共22页，编辑于2022年，星期三信息系统与管理学院 1、遗传算法概述2、如何提高初始种群质量3、程序实现第一讲第3页，共22页，编辑于2022年，星期三信息系统与管理学院 1、遗传算法概述2、如何提高初始种群质量3、程序实现第一讲第4页，共22页，编辑于2022年，星期三5信息系统与管理学院（1）遗传算法的产生与发展 上世纪上世纪50年代，一些生物学家开始运用数字计年代，一些生物学家开始运用数字计算机模拟生物的自然遗传与自然进化过程；算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的年，德国柏林技术大学的Rechenberg等做风等做风洞实验时，产生了进化策略的初步思想；洞实验时，产生了进化策略的初步思想；上世纪上世纪60年代，年代，Fogel在设计有限态自动机时提出在设计有限态自动机时提出进化规划的思想。进化规划的思想。1966年年Fogel等出版了等出版了基于模基于模拟进化的人工智能拟进化的人工智能，系统阐述了进化规划的思，系统阐述了进化规划的思想。想。第5页，共22页，编辑于2022年，星期三6信息系统与管理学院 60年代中期，美国年代中期，美国Michigan大学大学Holland教授提出借鉴生物自然遗教授提出借鉴生物自然遗传的基本原理用于自然和人工系统传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；的自适应行为研究和串编码技术；1967年，他的学生年，他的学生Bagley在博士论文中首次提在博士论文中首次提出出“Genetic Algorithms”一词；一词；1975年，年，Holland出版了著名的出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法，标志遗传算法的诞生。的诞生。（1）遗传算法的产生与发展 第6页，共22页，编辑于2022年，星期三7信息系统与管理学院 70年代初，年代初，Holland提出了提出了“模式定理模式定理”（Schema Theorem），是），是“遗传算法的基本定理遗传算法的基本定理”，奠定了遗传算法研究的理论基础；，奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；（1）遗传算法的产生与发展 第7页，共22页，编辑于2022年，星期三8信息系统与管理学院 1989年，年，Holland的学生的学生Goldherg出版了出版了“Genetic Algorithms in Search,Optimization,and Machine Learning”，对遗传算法及其应用作，对遗传算法及其应用作了全面而系统的论述；了全面而系统的论述；1991年，年，Davis编辑出版了编辑出版了遗传算法手册遗传算法手册，其中包括了遗传算法在工程技术和社会生活中其中包括了遗传算法在工程技术和社会生活中大量的应用实例。大量的应用实例。（1）遗传算法的产生与发展 第8页，共22页，编辑于2022年，星期三9信息系统与管理学院 遗传（遗传（Heredity）：子代和父代具有相同或相似）：子代和父代具有相同或相似的性状，保证物种的稳定性；的性状，保证物种的稳定性；变异（变异（Mutation）：子代与父代，子代不同个体）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然被保留，不具适应性变异的个体被淘汰。自然选择过程是长期、缓慢、连续的过程。选择过程是长期、缓慢、连续的过程。（2）生物进化理论和遗传学的基本知识 第9页，共22页，编辑于2022年，星期三10信息系统与管理学院 染色体（染色体（chromosome）：遗传物质的载体；）：遗传物质的载体；脱氧核糖核酸（脱氧核糖核酸（DNA）：大分子有机聚合物，）：大分子有机聚合物，双螺旋结构；双螺旋结构；基因（基因（gene）：）：DNA或或RNA长链结构中具有遗传效长链结构中具有遗传效应的应的DNA片段；片段；（2）生物进化理论和遗传学的基本知识 第10页，共22页，编辑于2022年，星期三11信息系统与管理学院 基因型（基因型（genotype）：遗传因子组合的模型；）：遗传因子组合的模型；表现型（表现型（phenotype）：由染色体决定性状的）：由染色体决定性状的外部表现。外部表现。1 1 1 1 1 1 1 1 1 1 0 1 1 1 基因型表现型（2）生物进化理论和遗传学的基本知识 第11页，共22页，编辑于2022年，星期三12信息系统与管理学院 个体（个体（individual）：指染色体带有特征的实体；）：指染色体带有特征的实体；种群（种群（population）：个体的集合，该集合内）：个体的集合，该集合内个体数称为种群的大小；个体数称为种群的大小；（2）生物进化理论和遗传学的基本知识 第12页，共22页，编辑于2022年，星期三13信息系统与管理学院 进化（进化（evolution）：生物在其延续生存的过程中，）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；这种生命现象称为进化；适应度（适应度（fitness）：度量某个物种对于生存环境的适）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。繁殖机会就会相对较少，甚至逐渐灭绝。（2）生物进化理论和遗传学的基本知识 第13页，共22页，编辑于2022年，星期三14信息系统与管理学院 选择（选择（selection）：指决定以一定的概率从种群）：指决定以一定的概率从种群中选择若干个体的操作中选择若干个体的操作；复制（复制（reproduction）：细胞在分裂时，遗传物质）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因胞就继承了旧细胞的基因;交叉（交叉（crossover）：在两个染色体的某一相同位置处）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的被切断，其前后两串分别交叉组合形成两个新的染色体。染色体。（2）生物进化理论和遗传学的基本知识 第14页，共22页，编辑于2022年，星期三15信息系统与管理学院 变异（变异（mutation）：在细胞进行复制时可能以很小）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使的概率产生某些复制差错，从而使DNA发生某种变发生某种变异，产生出新的染色体，这些新的染色体表现出新异，产生出新的染色体，这些新的染色体表现出新的性状的性状;编码（编码（coding）：表现型到基因型的映射；）：表现型到基因型的映射；解码（解码（decoding）：从基因型到表现型的映射。）：从基因型到表现型的映射。（2）生物进化理论和遗传学的基本知识 第15页，共22页，编辑于2022年，星期三16信息系统与管理学院（2）生物进化理论和遗传学的基本知识 第16页，共22页，编辑于2022年，星期三17信息系统与管理学院 1 产生初始种群2 适应值函数计算3 复制4 交叉5 变异（3）遗传算法的思路及特点 第17页，共22页，编辑于2022年，星期三信息系统与管理学院（3）遗传算法的思路及特点 种群操作种群操作邻域搜索邻域搜索随机性随机性第18页，共22页，编辑于2022年，星期三自组织、自适应和自学习性自组织、自适应和自学习性 在编码方案、适应度函数及遗传算子确定后，算法将利用进化过在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。程中获得的信息自行组织搜索。本质并行性本质并行性 内在并行性与内含并行性内在并行性与内含并行性不需求导不需求导 只需目标函数和适应度函数只需目标函数和适应度函数概率转换规则概率转换规则 强调概率转换规则，而不是确定的转换规则强调概率转换规则，而不是确定的转换规则（3）遗传算法的思路及特点 信息系统与管理学院 第19页，共22页，编辑于2022年，星期三信息系统与管理学院 1、遗传算法概述2、如何提高初始种群质量3、程序实现第一讲第20页，共22页，编辑于2022年，星期三信息系统与管理学院 1、遗传算法概述2、如何提高初始种群质量3、程序实现第一讲第21页，共22页，编辑于2022年，星期三结结 束束22信息系统与管理学院 第22页，共22页，编辑于2022年，星期三