遗传算法的研究+文献综述(2)
时间:2018-04-06 22:03 来源:毕业论文 作者:毕业论文 点击:次
1.1 遗传算法的起源 要从系统论的角度与观念来看生物体与生物界，就必须进行对其的计算机模拟研究。学者们从生物学的角度出发，进行了生物物种进化过程和遗传过程等过程的模拟，从此就出现了遗传算法的相关研究。 研究早期的侧重点是对某些复杂操作的研究。最早认为自然遗传算法存在可能转化为人工智能算法的是J.Holland教授。J.Holland教授率先提出了人工智能操作这个概念的重要性，并尝试将其应用到人工系统与自然系统中。J.D.Bagley一名J.Holland教授的学生，在其博士论文中首次提出了“遗传算法”（Genetic Algorithm，GA）一词，并发表了第一篇关于遗传算法在实际应用方面的论文，这一论文的另一成果则是首次提出了自适应的概念。J.D.Bagley发展了变异、复制、显性、交叉等遗传算子，在单倍体编码上使用双倍体的编码方法。几年后，Cavicchio把遗传算法应用在模式的识别上。Holistien则是最早把遗传算法应用在函数优化方向上。1970年代初，Holland教授提出了遗传算法的理论基础，即遗传算法的基本定理-模式定理，该定理揭示了种群优良个体数的增长规律：将以指数级增长。所以在理论能够保证遗传算法是可以用来寻求最优可行解的优化算法。在1975年，Holland教授出版了《自然系统和人工系统的自适应性》。 20世纪80年代，Hntland教授第一个实现遗传算法基础下的机器学习系统，即分类器系统，分类器系统这一全新的概念为机器学习系统构造出了一个完整的框架。1989年，D.J.Goldberg出版的专著—《搜索、优化和机器学习中的遗传算法》，该书总结了关于遗传算法发展至今的主要研究成果，完整而全面地描述了遗传算法的基本原理及其应用。1991年，L.Davis出版著作《遗传算法手册》，书中描述了遗传算法的大量应用样本，在社会经济、科学计算、工程技术中起到重要作用。1992年，J.R.Koza将遗传算法应用在计算机程序中，使程序优化设计和自动生成，并提出了遗传规划(Genetic Programming,简称GP)的概念。 1.2 遗传算法的基本原理与特点 遗传算法是建立在自然界进化的规律下并一步步发展起来的搜索方法，不仅仅具有随机性，还能全局优化搜索。遗传算法本质是高效并行的全局搜索方法，在搜索过程中该算法能自动获取和积累关于搜索空间的知识，也会在搜索过程中自适应规则以求得最优解。算法操作利用达尔文的进化论中适者生存的原则来选择优化。在目标解决方案种群里逐步测试计算得出近似的最优解方案。再根据孟德尔的遗传学说利用再造方法进行选择产生新的近似解。遗传算法在过程中选择过程会使个体在种群中进化。新进化的个体能更好的适应环境，算法也会淘汰不能适应环境的落后个体，这一点就类似于达尔文进化论的优胜略汰。 1.2.1 遗传算法的基本原理 遗传算法中每个算出的最优解都被称为“个体”。个体不是一个固定值，而是一个变量的序列，它能够根据环境的变化而更新，进化成新环境下的最优解。遗传算法在一开始时会随机生成不定数量的个体，算法操作者也可以人为干预设置成不固定量的个体，以此来提高初始个体的品质。个体在进化时会产生一代代的个体，每一代个体都会被标记而且进行单独的计算，计算过程是计算其适应度。这类似于生物在自然环境下，通过优胜略汰竞争后，存活率就是这个个体的适应度。存活率高的个体就排在种群的前面。 接着，把每一代产生的个体组织成种群。组织的过程需要经过严格的选择和繁殖，其中繁殖包括交配和突变。选择的操作并不是完全根据适应度的高低作为唯一标准的。如果作为唯一的标准，那么算法很快就会被收敛到高适应度的局部，这并不是全局的最优解。所以我们必须设计一定的原则来进行选择。适应度高的个体，相应被选择的概率也高；适应度低的个体，相应被选择的概率也会降低。这样就能避免仅在适应度高的个体中做选择，保证了全局性。 (责任编辑：qin) |