智能检测技术-第六章 遗传算法.pdf

北京化工大学 智能检测技术智能检测技术 第六章 遗传算法 信息科学与技术学院何泉 概述概述 • 遗传算法（Genetic Algorithm ）是模拟达尔文生物进化论的自然选择 和和遗传学遗传学机理的生物进化过程的计算机理的生物进化过程的计算模型模型，，是是一种通过模拟自然进化种通过模拟自然进化 过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一 个种群 （population ）开始的，而一个种群则由经过基因 （gene ）编 码的码的一定数目的个体定数目的个体(individual)(individual)组成组成。每个个体实际上是每个个体实际上是染色体染色体 (chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即 多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定 了个体的形状的外部表现了个体的形状的外部表现，如黑头发的特征是由染色体中控制这如黑头发的特征是由染色体中控制这一特特 征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因 型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进 行简化行简化，如如二进制进制编码编码，初代种群产生之后初代种群产生之后，按照适者生存和优胜劣按照适者生存和优胜劣 汰的原理，逐代（generation ）演化产生出越来越好的近似解，在每 一代，根据问题域中个体的适应度 （fitness ）大小选择（selection ） 个体，并借助于自然遗传学的遗传算子 （genetic operators ）进行组 合交叉（crossover ）和变异（mutation ），产生出代表新的解集的种 群群。。这个过程将导致种群像自然进化这个过程将导致种群像自然进化一样的后生代种群比前代更加适样的后生代种群比前代更加适 应于环境，末代种群中的最优个体经过解码 （decoding ），可以作为 问题近似最优解。 遗传算法的产生遗传算法的产生 • 60年代中期年代中期，美国美国Michigan大学的大学的J. H. Holland 教授提出借鉴生物自然遗传的基本原理用于自然 和人和人工系统的自适应行为研究和串编系统的自适应行为研究和串编码技术技术； • 1967年，他的学生J. D. Baggleyy在博士论文中首次 提出“遗传算法(Genetic Algorithms)”一词； • 年，，HollandHolland 出版了著名的出版了著名的 “AdaptationAdaptation inin Natural and Artificial Systems”，标志遗传算法的 诞生诞生。。 遗传算法的发展遗传算法的发展 •• 7070年代初年代初，HollandHolland提出了提出了 “模式定理模式定理” （（ Schema Theorem ），一般认为是“遗传算 法的基本定理法的基本定理””，从而奠定了遗传算法研从而奠定了遗传算法研 究的理论基础； • 1985年，在美国召开了第一届遗传算法国 际会议际会议，并且成立了国际遗传算法学会并且成立了国际遗传算法学会 (ISGA，International Society of Genetic AlAlgorithithms)) ； ••年，HollandHolland 的学生的学生DD. JJ. GoldhergGoldherg出版出版 了“Genetic Algorithms in Search, Optimization, and Machine Learning”，对对 遗传算法及其应用作了全面而系统的论述 ； ••年，LL. DavisDavis编辑出版了编辑出版了 《《遗传算法手遗传算法手 册》，其中包括了遗传算法在工程技术和 社会生活中大量的应用实例社会生活中大量的应用实例。 70年代 5050，6060年代