文档介绍：遗传算法大连理工大学 金博达尔文进化理论的主要论点生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状;染色体是由基因及其有规律的排列所构成的,遗传和进化过程发生在染色体上;生物的繁殖过程是由其基因的复制过程来完成的;通过同源染色体之间的交叉或染色体的变异会产生新的物种,使生物呈现新的性状;对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。遗传算法思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的优化算法。遗传算法用概率搜索过程在状态空间中搜索,产生新的样本。遗传算法遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构遗传算法的特点特点:通用鲁棒次优解、满意解遗传算法能解决的问题:优化NP完全NP难高度复杂的非线性问题遗传算法与传统优化算法的主要不同遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。遗传算法的发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在20世纪40年代,就有学者开始研究如何利用计算机进行生物模拟的技术,他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入20世纪60年代,美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发,创造出一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术—遗传算法。(1),Holland教授提出了遗传算法的基本定理—模式定理,从而奠定了遗传算法的理论基础。模式定理揭示了群体中优良个体(较好的模式)的样本数将以指数级规律增长,从理论上保证了遗传算法用于寻求最优可行解的优化过程。1975年,Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性》。20世纪80年代,Holland教授实现了第一个基于遗传算法的机器学习系统—分类器系统,开创了基于遗传算法的机器学习的新概念。(2),Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词,并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子,在个体编码上使用了双倍体的编码方法。在遗传算法的不同阶段采用了不同的概率,从而创立了自适应遗传算法的概念。(3),DeJong博士在其博士论文中结合模式定理进行了大量纯数值函数优化计算实验,树立了遗传算法的工作框架。他推荐了在大多数优化问题中都较适用的遗传算法的参数,建立了著名的DeJong五函数测试平台,定义了评价遗传算法性能的在线指标和离线指标。(4),Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》,该书全面地论述了遗传算法的基本原理及其应用,奠定了现代遗传算法的科学基础。