机器学习研究生特色精品课程-智能计算与商空间--主页.PPT

第六章 遗传算法 遗传算法的仿生学基础 ? 构成生物的基本结构和功能的单位是细胞。 ? 细胞中含有的一种微小的丝状化合物称为染色体(Chromosome)，生物的所有遗 传信息都包含在这个复杂而又微小的染色体中。 ? 基因 经过生物学家的研究，控制并决定生物遗传性状的染色体主要是由一种叫做脱 氧核糖核酸(deoxyribonucleic acid 简称DNA)物质所构成。 DNA在染色体中有 规则地排列着，它是个大分子的有机聚合物，其基本结构单位是核苷酸，许多核苷 酸通过磷酸二酯键相结合形成一个长长的链状结构，两个链状结构再通过碱基间的氢键有 规律地扭合在一起，相互卷曲起来形成一种双螺旋结构。基因就是DNA长链结构中占有一 定位置的基本遗传单位。 ? 遗传信息是由基因(Gene)组成的，生物的各种性状由其相应的基因所控制。 ? 基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。遗传基因在染色体中所占据的位置称为基因座(Locus)； ? 同一基因座可能有的全部基因称为等位基因(Allele)； ? 某种生物所特有的基因及其构成形式称为该生物的基因型(Genotype)； ? 而该生物在环境中呈现出的相应的性状称为该生物的表现型(Phenotype)； ? 一个细胞核中所有染色体所携带的遗传信息的全体称为一个基因 组(Genome)。 遗传算法简介 (1) 萌芽期 (50年代后期至70年代初期) ? 50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。 ? 1965年，德国的L.Rechenberg等人正式提出进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有变异一种。 ? 1965年，美国的L.j.Fogel正式提出进化规划，在计算中采用多个个体组成的群 体，而且只运用变异操作。 ? 60年代期间，美国J.H.Holland在研究自适应系统时，提出系统本身与外部环境 相互协调的遗传算法。1968年，J.H.Holland教授又提出模式理论，它成为遗传算法的主要理论基础。 ? 1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（ Genetic Algorithm）”一词。 (2) 成长期 (70年代中期至80年代末期) ? 1975年，J.H.Holland教授的专著《自然界和人工系统的适应性(Adaptation in Natural and Artificial System)》正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志， Holland也被视作遗传算法的创始人。 ? 1987年，美国D.Lawrence总结人们长期从事遗传算法的经验，公开出版《遗传算法和模拟退火(Genetic Algorithm and Simulated Annealing)》一书，以论文集形式用大量实例介绍遗传算法。 ? 1985年，作为Holland的学生，D.E.Goldberg博士出版专著《遗传算法——搜索、优化及机器学习(Genetic Algorithms——in Search，Optimization and Machine Learning)》，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。 ? 1985年，在美国举行第一届遗传算法国际学术会议(International Conference on Genetic Algorithms，简称ICGA），与会者交流运用遗传算法的经验。随后，1987，1989，1991，1993，l 995及l 997年，每2年左右都举行一次这种会议。 (3) 发展期(90年代以后) ? 1991年，D.Lawrence出版《遗传算法手册(Handbook of Genetic Algorithms )一书，详尽地介绍遗传算法的工作细节。 ? 1996年 Z.Michalewicz的专著《遗传算法 + 数据结构 = 进化程序》深入讨论了遗传算法的各种专门问题。同年，T.Back的专著《进化算法的理论与实践：进化策略、进化规划、遗传算法》深入阐明进化算法的许多理论问题。 ? 1992年，Koza出版专著《遗传规划——应用自然选择法则的计算机程