（分析化学专业论文）改进的遗传算法及其在化学中的应用.pdf

中困l ： 挫人学坝i 学位论文 摘蛰 摘要 、遗传算法作为模仿自然进化的随机搜索方法，已在确：多领域中得到广泛 应用。其良好的全局搜索能力以及不需任何有关问题的先验知识的特性使得 它尤其适合于求解复杂问题。目前遗传算法已成为化学计量学研究的重要内 ；r 容之一。本文研究了一系列改进的遗传算法，并将其用于化学信号处理及结 构优化问题，得到了良好的结果。 首先，介绍了简单遗传算法的基本概念和模型，并概述了遗传算法的发 展，研究方向及其近年来在化学中的应刚。 ， 其次，介绍了简单遗传算法的算法基础和实现技术。从对简单遗传算法 的数学分析中看出，简单遗传算法虽然具有全局并行搜索的优点，但是未成 熟收敛和局部搜索能力差也是其明显的缺点。因此，本文对简单遗传算法进 行了一系列的改进，通过比较改进的遗传算法和简单遗传算法的性能，明显 看出改进的遗传算法提高了遗传算法的优化性能，加快了遗传算法的搜索速 度，加强了遗传算法的局部搜索性能，改善了未成熟收敛现象。 基于小波变换的线性和时频局部化的性质，我们将小波与遗传算法结合 ， 形成了小波遗传算法。另夕b 针对色谱峰的特点，我们又提出了基于指数修正 的商斯函数的遗传算法，并首次将这两种算法应用于重叠色谱峰的压缩、滤 噪及解析，获得了良好的结果。 最后，将改进的遗传算法用于结构优化，这一类问题由于在势能表面存 在很多局部最优而被认为是计算化学中非常难于解决的问题。髀法对于小的 原子簇和分子簇的结构优化结果表明，改进的遗传算法所得到的最低能量结 果可与在高性能并行计算机上得到的结果相媲美。卢，一， 中国科技大学烦i j 学位论艾 a b s t r a c t a b s t r a c t g e n e t i ca l g o r i t h m s ( g a s ) ，a ss t o c h a s t i cs e a r c h i n gm e t h o d ss i m u l a t i n gt h e f u n c t i o no fn a t u r a le v o l u t i o n ，h a v eb e e nu s e dw i d e l yi nm a n yr e s e a r c hf i e l d s t h e p r o p e r t i e si nl o c a t i n gt h eg l o b a lm i n i m u mw i t h o u tn e e do f a n ys p e c i f i ci n f o r m a t i o n f r o mt h ep r o b l e mm a k eg a s p a r t i c u l a r l ys u i t a b l ef o rs o l v i n gc o m p l i c a t e dp r o b l e m s n o wg a sh a v eb e c o m eo n eo ft h em o s ti m p o r t a n tf i e l d s i nc h e m o m e t r i c s i nt h i s d i s s e r t a t i o nas e r i e so fm o d i f i e dg e n e t i ca l g o r i t h m s ( m g a ) ，h a v eb e e ns t u d i e d a n da p p l i e dt oc h e m i c a ls i g n a lp r o c e s s i n ga n ds t r u c t u r a lo p t i m i z a t i o n ，s a t i s f a c t o r y r e s u l t sw e r eo b t a i n e d f i r s t ，t h eb a s i ct h e o r i e sa n dm o d e l so fs i m p l eg e n e t i ca l g o r i t h m s ( s g a ) w e r ei n t r o d u c e d ，a n dar e v i e wo np r o g r e s s i o na n da p p l i c a t i o n so fg a si nc h e m i s t r y d u r i n gr e c e n ty e a r sw e r ep r e s e n t e d s e c o n d l y ，t h eb r i e fa l g o r i t h m a n dr e a l i z a t i o nt e c l m i q u e so fs g aw e r e d e s c r i b e d f r o mt h ea r i t h m e t i c a la n a l y s i so ft h ep r e s e n ts g a ，i ti sf o u n dt h a t a l t h o u g hs g ah a st h ea d v a n t a g e so fg l o b a la n dp a r a l l e ls e a r c h ，i ta l s oh a st h e d i s a d v a n t a g e so fp r e m a t u r ec o n v e r g e n c ea n dw e a kl o c a ls e a r c h t h e r e f o r e ，m a n y m o d i f i c a t i o n so fs g aw e r ei n t r o d u c e d c o m p a r i n gt h ep e r f o r m a n c e so fs g aw i t h t h a to fm g a ，i tc a nb es e e nc l e a r l yt h a tm g ai m p r o v e st h es g a so p t i m i z i n g a b i l i t y ，s p e e d su ps g a ss e a r c h i n gp r o c e s s ，e n h a n c e st h es g a si n c a ls e a r c h i n g a b i l i t ya n dh e l p st oo v e r c o m et h ep r e m a t u r ec o n v e r g e n c e t a k i n ga c c o u n to ft h ei i n e a rt r a n s f o r ma n dt h el o c a l i z a t i o ni nt i m e f r e q u e n c y o ft h ew a v e l e t ，a n do nt h eb a s i so ft h ep r e v i o u sw o r ko fo u rg r o u p ，w ec r e a t ea w a v e l e tg e n e t i ca l g o r i t h m ( w g a ) i na d d i t i o n ，c o n s i d e r i n gt h ec h a r a c t e r i s t i c so f c h r o m a t o g r a p h i cp e a k s ，w ed e v e l o p e dag e n e t i ca l g o r i t h mb a s e do ne x p o n e n t i a l l y m o d i f i e dg a n s s i a nf u n c t i o n s ( e g a ) b o t hw g aa n de g aw e r ef i r s t l yu s e di nt h e c o m p r e s s i o n ，n o i s e - f i l t e r i n ga n dr e s o l u t i o no fh i g h l yo v e r l a p p e dc h r o m a t o g r a m s ， f i n er e s u l t sw e r eo b t a i n e d f i n a l l y ，m g aw a su s e dt os t r u c t u r a lo p t i m i z a t i o np r o b l e m sw h i c hh a v e b e e n c o n s i d e r e da sp r o h i b i t i v e l yd i f f i c u l tp r o b l e m si nc o m p u t a t i o n a lc h e m i s t r yd u et oa l a r g en u m b e ro fl o c a lm i n i m a s m a l la t o m i ca n dm o l e c u l a rc l u s t e r s w e r e i n v e s t i g a t e d t h eo p t i m i z e ds t r u c t u r e sw i mm i n i m u me n e r g i e sb ym g a w e r er i v a l s o ft h o s ec a l c u l a t e do nh i g hp e r f o r m a n c ep a r a l l e lc o m p u t e r 中团科技人学坝f 学位论史 致谢 本论文是在导师潘忠孝教授、蔡文生副教授、张懋森教授的悉心 关怀和指导下完成的。 潘老师三年来在学习和 作上严格要求学生，他严谨认真的治学 态度，对科学研究工作一丝不苟的精神令我十分钦佩。潘老师在工 作、学习、思想上给我的启迪和帮助，将令我终身难忘。 蔡老师在论文工作期间给予了我很多具体的指导，提供了有关遗 传算法的详细资料，并就算法程序中的一些细节的实现给予了帮助， 在论文写作方面也一直给予我严格的训练和热情的指导。 张懋森先生德高望重，为人随和。在学术上富于开拓精神。先生 渊博的知识、谦和的为人及乐观的生活态度给我留下了很深的印象， 使我受益非浅。 感谢召5 学广教授在程序调试、数据提供及处理方面所给予的具体 指导。 本实验室的印春生老师在论文的完成过程中，一直给作者予大量 的支持。寇红兵、吴孔导、任琴、王利亚、夏保云、赵巍、邹明选、 傅荣强、梁红波、李伟等同学也给了作者许多鼓励、合作和帮助。借 此机会向他们表示衷心的谢意。 谨以此论文献给一直关爱和鼓励我的家人。 中田科技人学坝l 学位论文 第一章遗传算法概述 第一章遗传算法概述 1 1 自然进化与遗传算法 生命自从在地球上诞生以来，就丌始了漫长的生物进化历程，低级、简 单的生物类型逐渐发展为高级、复杂的生物类型。这一过程已经由古生物学、 胚胎学和比较解剖学等方面的研究工作所证实。生物进化的原因自古至今有 着各种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。 自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争 包括种内斗争、种问斗争以及生物跟无机环境之侧的斗争三个方面。在生存 斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异 传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。 因此，凡是在生存斗争获胜的个体都是对环境适应性比较强的。达尔文把这 种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。达尔文的自然 选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子 代之间，在性状上存在的相似现象。变异是指父代与子代之间，以及子代的 个体之问，在性状上或多或少地存在的差异现象。在生物体内，遗传和变异 的关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有 的可以遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特 性，变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展。 生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。 根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体，染色 体主要足山d n a 和蛋白质组成，其中d n a 又是最主要的遗传物质。现代分 子水平的遗传学的研究又进一步证明，基因是有遗传效应的片段，它储存着 遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成 而控制生物的性状。生物体自身通过对基因的复制和交叉( 即基因分离、基 因自由组合和基因连锁互换) 操作使其性状的遗传得到选择和控制。同时， 通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变 中田科技大学颂士学位论文第一章遗传算法概述 异现缘。需要指出的是，根据达尔文进化论，多种多样的生物之所以能够适 应环境而得以生存进化，是和上述的遗传和变异生命现象分不开的。生物的 遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物 个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。 自然进化的这些特征早在6 0 年代就引起了美国m i c h i g a n 大学的j o h n 1 4 0 l | a n d 的极大兴趣，那时，他和他的学生们已在从事如何建立能学习的机 器的研究。h o l l a n d 注意到学习不仅可以通过单个生物体的适应而且通过一 个种群的许多代的进化适应也能发生。受达尔文进化论一一适者生存的启 发，他逐渐认识到，在机器学习的研究中，为获得一个好的学习算法，仅靠 单个策略的群体的建立和改进足不够的，还要依赖于一个包含许多候选策略 的群体的繁殖。他们的研究想法起源于遗传进化，h o l l a n d 就将这个研究领 域取名为遗传算法。一直到1 9 7 5 年h o l l a n d 出版了那本颇有影响的专著 a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s i “，遗传算法这个名称才逐渐为人 所知。 h o l l a n d 创建的遗传算法是一种概率搜索算法，它是利用某种编码技术 作用于被称为染色体的二进制数串，其基本思想是模拟由这些串组成的群体 的进化过程。遗传算法通过有组织地然而是随机地信息交换来重新结合那些 适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来生成 一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段 来替代原来的部分。遗传算法是一类随机算法，但它不是简单的随机走动， 它可以有效地利用已有的信息来搜寻那些有希望改善解质量的串，类似于自 然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体柬求解问题。 与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算 法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好 的染色体比适应性差的染色体有更多的繁殖机会。 遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决 非常困难的问题。特别是由于它不受搜索空间的限制性假设的约束，不必要 求诸如连续性、导数存在和单峰等假设，以及其固有的并行性，遗传算法目 的已经在最优化、机器学习和并行处理等领域得到了越来越广泛的应用刚。 2 中周科技大学硕士学位论文第一章遗传算法概述 1 2 遗传算法的描述 遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、 适于并行处理以及应用范围广等显著特点，奠定了它作为2 1 世纪关键智能 计算方法之一的地位。 由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算 方法，所以遗传算法中经常使用有关自然进化中的一些基础理论用语。 生物的遗传物质的主要载体是染色体，d n a 是其中最主要的遗传物质， 而基因又是控制生物性状的遗传物质的功能单位和结构单位。若干个基因组 成染色体，染色体中基因的位置称作基因座，而基因所取的值又叫做等位基 【划。基因和基因座决定了染色体的特征，也就决定了生物个体的性状。此外， 染色体有两种相应的表示模式，即基因型和表现型。所谓表现型是指生物个 体所表现出来的性状，而基因型是指与表现型密切相关的基因组成。同一种 撼因型的生物个体在不同的环境条件下可以有不同的表现型，因此表现型是 基因型与环境条件相互作用的结果。在遗传算法中，染色体对应的是数据或 数组，在标准的遗传算法中，这通常是由一维的串结构数据来表现的。串 备个位置对应l 述的基因座，而各位置上所取的值对应上述的等位基因。 遗传算法处理的足染色体，或者叫基因型个体。 定数量的个体组成了群体， 也叫集团。群体中个体的数目称为群体的大小，也叫群体规模。而各个体对 环境的适应程度叫做适应度。表1 - 1 所示为遗传算法中所用术语与遗传学名 i 司的对应关系。 表1 1 遗传学和遗传算法中基础术语对照表 中国科技大学硕士学位论文 第一章遗传算法概述 当然，遗传算法的计算过程只是对群体进化论过程的模拟，借助遗传学 的基本原理处理问题。所以遗传算法中的生物学概念不一定十分准确，只是 生物学概念的简单“借用”。 执行遗传算法时包含两个必需的数据转换操作，一个是表现型到基因型 的转换，另一个是基因型到表现型的转换。前者是把搜索空间中的参数或解 转换成遗传空间中的染色体或个体，此过程又叫做编码操作：后者是前者的 一个相反操作，叫做译码操作。 遗传算法包含了如下5 个基本要素：1 ) 参数编码；2 ) 初始群体的设定： 3 ) 适应度函数的设计；4 ) 遗传操作设计；5 ) 控制参数设定( 主要是指群 体大小和使用遗传操作的概率等) 。这5 个要素构成了遗传算法的核心内容。 遗传算法是具有“生成+ 检测”的迭代过程的搜索算法f 4 j 。它的基本处理流程 如图1 1 所示，l h 图可见，遗传算法是一种群体操作，该操作以群体中的所 有个体为对象。选择、交叉和变异是遗传算法的3 个主要操作钟子，它们构 成了所谓的遗传操作，使遗传算法具有了其它传统方法所没有的特性。 图1 1 遗传算法流程图 4 中国科技大学硕士学位论文 第一章遗传算法概述 1 3 遗传算法发展回顾、研究方向及其在化学中的应用 1 3 1 遗传算法发展回顾 遗传算法研究的兴起是在8 0 年代末和9 0 年代初期，但它的历史起源可 追朔到6 0 年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。 在遗传算法作为搜索方法用于人工智能系统中之前，已有不少生物学家 用计算机来模拟自然遗传系统。尤其是f r a s e r 的模拟研究，他于1 9 6 2 年提 出了和现在的遗传算法十分相似的概念和思想1 5 】。但是，f r a s e r 和其他一些学 者并未认识到自然遗传算法可以转化为人工遗传算法。而h o l l a n d 教授及其 学生不久就认识到这一转化的重要性”i 。h o l l a n d 认为比起寻找这种或那种具 体的求解问题的方法来说，开拓一种能模拟自然选择遗传机制的带有一般性 的理论和方法更有意义。在这一时期，h o l l a n d 不但发现了基于适应度的人 工遗传选择的基本作用，而且还对群体操作等进行r 认真的研究。1 9 6 5 年， 他苗次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统 中。 1 9 6 7 年，b a g l e y 在他的论文中首次提出了遗传算法( g e n e t i ca l g o r i t h m ) 这 一术语，并讨论了遗传算法在自动博弈中的应用。他所提出的包括选择、 交义和变异的操作已与目前遗传算法中的相应操作十分接近。尤其是他对选 择操作做了十分有意义的研究。他认识到，在遗传进化过程的前期和后期， 选择概率应适当地变动。为此，他引入了适应度定标概念，这是目前遗传算 法中常用的技术。同时，他也首次提出遗传算法自我调整概念，即把交叉和 变异的概率融于染色体本身的编码中，从而可实现算法自我调整优化。尽管 b a g l e y 没有对此进行计算机模拟实验，但这些思想对于后来遗传算法的发展 所起的作用是十分明显的。 第一个把遗传算法用于函数优化的是h o l l s t i e n 。1 9 7 1 年他在论文计算 机控制系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制 的方法【7 】。但实际上，他主要是讨论了对于二变量函数的优化问题。其中， 对于优势基因控制、交叉和变异以及各种编码技术进行了深入的研究。 1 9 7 5 年在遗传算法研究的历史上是十分重要的一年。这一年，h o l l a n d s 中国科技大学硕士学位论文第一章遗传算法概述 出版了他的著名专著自然系统和人工系统的适配该书系统地阐述了遗传 算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的 模式理论( s c h e m a t at h e o r y ) 。该理论首次确认了结构重组遗传操作对于获得 隐并行性的重要性。直到这时才知道遗传操作到底在干什么，为什么又于得 那么出色，这对于以后陆续开发出来的遗传操作具有不可估量的指导作用。 同年，d ej o n g 完成了他的重要论文遗传自适应系统的行为分析【8 l 。 他在该论文中所做的研究工作可看作是遗传算法发展进程中的一个里程碑， 这是因为他把h o l l a n d 的模式理论与他的计算实验结合起来。尽管d e3 0 n g 和h o l l s t i e n 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变 异操作进一步完善和系统化，同时又提出了诸如代沟( g e n e r m i o ng a p ) 等新的 遗传操作技术。可以认为，d ej o n g 的研究工作为遗传算法及其应用打下了 坚实的基础，他所得h 1 的许多结论迄今仍具有普遍的指导意义。 进入8 0 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用 研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不 但它的应用领域扩大，而且利用遗传算法进行优化平f 规则学习的能力也显著 提高，同时产业应川方面的研究也在摸索之中。此外一些新的理论和方法在 应用研究中亦得到了迅速的发展，这- - 当无疑均给遗传算法增添了新的活力。 遗传算法的应用研究已从初期的组合优化求解拓展到了许多更新、更工 程化的应用方面。 1 3 2 遗传算法的研究方向 对遗传算法的研究： 作主要集中在以下几个方面： 一、性能分析。遗传算法的性能分析一直都是遗传算法研究领域中最重 要的主题之一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参 数的选取是非常困难的，同时，它们又是必不可少的实验参数，这方面已有 一些具有指导性的实验结果。遗传算法还存在一个过早收敛问题，也就是说 遗传算法的最后结果并不总是达到最优解，怎样阻止过早收敛也是人们感兴 趣的问题之一。另外，为了拓广遗传算法的应用范围，人们在不断研究新的 遗传表示法和新的遗传算子。 6 中国科技大学硕士学位论文第一章遗传算法概述 二、并行遗传算法。遗传算法在操作上具有高度的并行性，许多研究人 员都正在探索在并行计算机上高效执行遗传算法的策略。最近几届的遗传算 法国际会议论文集上也收录了不少这方面的文章。对并行遗传算法的研究表 明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并行执行 过程，即使不使用并行计算机，也能提高算法的执行效率。 三、分类系统。分类系统属于基于遗传算法的机器学习中的一类，它包 括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子 系统。分类系统正被人们越来越多地应用在科学、工程和经济等领域，例如， 规则集的演化能预估公司的利润和对字母序列进行预测。目前，分类系统是 遗传算法研究中的一个非常活跃的领域。 近年来，遗传算法的研究领域中出现了一些新的动向。在遗传算法的模 型方面，人们为了提高遗传算法的搜索能力，提出了几个扩展的遗传算法模 型。关于遗传算子，s y s w e r d a 提出了致杂交算子， 它是随机地交换位序 列来保持群体的多样性1 9 】。e s h e l m a n 提出通过阻止类似的个体之间的杂交来 防止过早的收敛0 】。w h i t l e y 提出“编码”方法，通过对远离一些先前的局 部解的距离进行编码来找到更精确的解f 。至于处理遗传算法“骗问题”( 遗 传算法难以解决的问题) ，d a s 提出了一个超平面搜索方法，其中相互竞争的 超平而，是通过指定一个随机序列来统计地搜索，这种方法可处理某类骗函 数“。g o l d b e r g 提出了一个更有效的模型混乱遗传算法，它生成k 阶短 模式，并通过每次至少改变k 位来避免落入局部解 1 3 i 。 李通化等提出了一种动态遗传算法1 ，即在遗传算法的初始化阶段，利 用较短的时间使群体中的个体之间尽可能地具有较大的差异：在遗传算法的 中间阶段，控制参数变化使搜索空间尽量大，从而提高“开发”( 产生新型 基因) 的效率；而在遗传算法的最后阶段，控制参数变化适当降低“开发” 效率，使搜索局限于较小的空间范围，尽快地找到最优解。此后，丛培盛、 李通化等在经典遗传算法的基础上提出一种新的全局优化方法数值遗传算法 ( n g a ) 15 1 , 除新设计了交配和突变数值遗传操作并讨论了它们的特点外， 还加入了记忆遗传操作。所谓记忆遗传操作，是在若干次遗传操作之后，如 子代能够存活，记子代与祖先之差为6 ，并在子代的基础上加上b6 ( 0 b 1 ) 7 中国科技大学硕士学位论文 第一章遗传算法概述 产生一个新的个体，若仍能存活，则不断重复上述过程，直到个体不能再存 活，它在单调变化区域和多变量同时优化时特别有效。n g a 将广泛的搜索与 局部的精化相结合，能够越过局部较优找到全局最优解，特别适合于处理复 杂的非线性问题。对三个数学函数的模拟实验结果表明，在优化过程中，能 迅速有效地找到全局最优解。 针对特定的问题，为了改进算法搜索效率，人们提出了特别的遗传表示 法和遗传算子。s u g a t o 对任务排队问题的不合法解用相似的合法解来替代i “】。 v o nl a s z e w s k i 对图划分问题提出了一个混合遗传算法【1 7 1 。在每一代中，算法 采用k e r n i g h a n 和l i n 的图的分割算法来搜索局部解，结果表明混合遗传算 法可找到比启发式算法更好的解8 】。m a r u y a m a 出指出，对图划分问题，异 步并行遗传算法在解的质量和执行效果上都能够超过并行化的传统启发式算 法【”i 。 1 3 3 遗传算法在化学中的应用研究 遗传算法不仅可以处理组合优化问题，而儿可以处理多连续变量参数的 优化问题，特别适用于复杂f 线性问题的处理，在化学中有广泛的应用。 一、结构分析 结构解析是有机化学和药物化学领域中的个重要的研究课题，对于指 导合成新的有机化合物和药物，充分合理地利刖天然资源具有重要的意义。 在化学中许多问题都需要分子三维构象的信息，m c g a r r a h 等以环六甘氨 酸为例，用遗传算法全局寻优，寻找能量低的构象，并研究了群体数、遗传 代数等参数对遗传算法寻优的影响【2 0 】。v j v e l l i 等提出了个用于预测球 蛋白的二级结构的以局部遗传算法控制的自向神经网络并行系统。该法可在 神经网络的参数空间内广泛地搜索和确定最优拓扑结构。以最小均方误差为 评价指标，用遗传算法来选择神经网络的拓扑结构。当用以区分n 螺旋、b 线型和随机螺旋型二级结构时，达到的最大效率为0 6 2 ，相关系数分别为 0 3 5 、0 3 1 和0 3 7 。其准确度与以前用无隐含层人工神经网络以单个蛋白 质序列作为输入时获得的准确度相似】。b e n e d e t t i 等将遗传算法用于获得 r n a 的最优和较优二级结构，并用不同长度的r n a 序列对方法进行了检验别。 8 中国科技大学硕士学位论文第一章遗传算法概述 g u l t y a e v 等将遗传算法用于模拟r n a 的折叠途径，并能预测其亚稳结构和动 力学控制的向稳定结构的转移1 2 ”。c a r p i o 根据实验中已知的许多影响蛋白质 折叠过程的因素提出一种适值函数，并在此基础上使用一种并行遗传算法预 测了多肽的三维结构f 2 4 l 。j u d s o n 将遗传算法用于聚合物折叠结构的研究，提 出了一个描述二维模型聚合物如何折叠成为全局能量最小的聚合物形态的遗 传程序。该程序指明聚合物折叠的途径，并能找到满足特定终态要求的聚合 物折叠结构形态l 。 m a y 等用遗传算法搜索两个蛋白质结构刚性重叠的近似最优解，用通常 的动力学规划法定义最后结构的拓扑等价性，用最小二乘法来优化最后一组 拓扑等价性之间的拟合，将上述三种方法结合起来用于核糖核酸结构以及蛋 白质结构的比较研究1 2 6 】。j u d s o n 等将遗传算法用于有机小分子构象的探索， 根据对一组7 2 个分子的实验结果表明，它优于c s e a r c h 算法。当分子中有 八个以上可旋转键时，该法的效果更好，且随着分子中可旋转键数目的增多 而更有效【2 ”。b l o m m e r s 等将遗传算法用于二核苷酸光二聚物的结构分析，发 现糖和配糖体的构型分别是s 型和顺式构型，此外，还发现存在于平衡中的 其它构型i 。 用n m r 潜计算蛋白质的二二维结构的困难在于对谱图的正确解析，但由于 噪声、谱例分辨不够清晰或者不正常的图形，常常使谱图得不到正确的解析。 w e h r e n s 等成功地将遗传算法用于蛋白质二维核磁谱解析中，即使输入数据 有相当大的误差也能得到满意结果。 s h e r i d a n 等在有机合成中用遗传算法从已知数于种一胺和二胺中，根 据构效关系快速地选择和找到具有特殊活性的一胺和二胺，来生成n 取代的 甘氨酸的低聚物m i 。j o n e s 用遗传算法进行蛋白质分子的从头设计，使所合 成的氨基酸序列符合给定的三维结构j 。v e n k a t a s u b r a m a n i a n 将遗传算法用 于计算机辅助分子设计中，该法可以克服通常的计算机辅助分子设计方法在 处理大的非线性搜索空间方面存在的困难，在设计具有所需要性质的聚合物 分子时成功的概率大，这点在实验中得到了证明 3 2 , 3 3 j 。 二、拟合与校正 目前大多数仪器分析都是相对测量，通过分析信号的校正来计算被测组 9 中国科技大学硕士学位论文 第一章遗传算法概述 分的含量，在多组分同时测量时，数据拟合和分析信号的校正是一个很重要 的问题。h i b b e r t 用遗传算法拟合浓度一反应时间的动力学曲线，优化5 一三 磷酸腺苷速率常数f 3 4 l 。d eh a a n 等用遗传算法拟合中子反射实验数据，在没 有任何有关样本先验知识的情况下，能够得到模型的参数，使数据得到很好 的拟合i 。聚乙烯对苯二酸酯丝的x 一射线赤道衍射仪扫描，峰严重重叠，用 通常的方法进行拟合会产生病态，而用人工神经网络与遗传算法进行曲线拟 合，仍能得到好的结果【3 6 】。 蔡煜东将遗传算法用于分析化学中非线性多元函数的拟合，以铬天菁一s 与铝合物的一组吸光度数据为对象，比较了用遗传算法和最小二乘法进行二 次回归方程拟合的效果，发现遗传算法拟合精度优于最小二乘法【3 7 j ，蔡等在 此工作基础上改进了遗传算法，不对问题进行编码，将任意实数都看作个 体以扩大采样空问，将交叉重组推广到选取算术平均值和几何平均值， 将突变推广到任意微小的扰动( 相当小的随机数) 。用此法拟合离子选 择电极的工作曲线，拟合精度优于一般遗传算法和线性回归法，认为该方法 有望成为各类传感器非线性曲线拟合的有效手段i ”i 。 三、定量分析 p a r e z e w s k i 等将遗传算法用于滴定分析，根据光度模拟滴定数据用遗传 算法求溶液组分的浓度、条件1 i 衡常数和吸光系数m l 。 用人工神经网络模型计算x 射线荧光光谱定量分析结果有很好的准确 度，b o s 等对遗传算法与误差反传( b p ) 算法进行了比较，对f e n i c r 体系， 使用较少训练样本数( n = 1 3 ) 时，两种算法都取得了较好的结果m 】。 四、多组分成分分析波长选择 多组分同时测定是分析化学中常遇到的问题，l u c a s i u s 等将遗传算法用 于紫外光度法同时测定几种核苷酸时的波长选择中，以选择性、准确性和最 小平均方差为评价指标，并与模拟退火法和逐步消元法的结果进行了比较， 结果表明遗传算法的效果最佳”。h o r c h n e r 等对模拟退火和遗传算法在波长 选择中的应用进行了对比研究，提出了准确鉴定最优波长组合方法和优化判 据适用性的要求。 五、原子簇、分子簇的几何结构优化 1 0 中固科技大学硕士学位论文 第一章遗传算法概述 d e a v e n 等基于遗传算法提出一种确定原子簇最低能量结构算法，此算法 以驰豫能作为判据，以一部分候选的结构群为母体，通过交叉重组遗传操作， 产生具有较低能量的新的结构群。这一方法已用来优化碳原子簇，从小的简 单碳原子簇直到富勒烯c 。的几何结构，都能有效地找到能量最低结构【4 ”。 m e s t r e s 等发展了一个几何优化遗传算法的程序，用来搜索c 。簇线链异构体 全局能量最小结构，并对不同遗传算子进行了检验，所得到的一组优化遗传 算子随后用于获得最多含有1 3 个原子的稀有气体原子簇的最小结构f 4 4 】。 w i l l i a m s 提出了许多方法 4 5 - 4 7 l ，用于分子簇的几何结构优化，如基于对 称中心的牛顿一拉普桑局部优化法| 4 ”，从次优解进化到全局最优解的 o r e m w a ( o f f - r i d g ee i g e n v e c t o rm i m m i z a t i o nw i t ha n n e a l i n g ) 法4 ”，从而确 定含两到四个苯分子的苯分子簇的最低能量结构。他还提出了一种二进制编 码的遗传算法( g a m e ) 来求苯、蒽、菲的二聚体的全局能量最小点【4 7 1 。n i e s s e 运用遗传算法成功地对a r 原子簇和水分子簇进行了最低能量结构预测m 】。 最近，p u l l a n 提出了一种能预测苯分子簇结构的有效的并行遗传算法【4 9 】，它 可找到具有2 1 5 个苯分子的分子簇的最低能量结构。 六、化工过程优化 在制造多层式滤光器时，薄膜厚度与不同性质的介电材料叠放顺序都有 影响，e i s e n h a m m e r 等将遗传算法用于银基热反射镜研制工艺优化【5 0 l 。 c a r t w r i g h t 等用遗传算法同时优化工艺流程和设备布局5 “。 硼提取率与m 9 0 一b 。o 。一s i 0 。渣组成呈现复杂的非线性关系，用回归分析很 难实现最优化。用梯度法对复杂函数求导困难，有时会出现局部优化。张培 新等用人工神经网络一遗传算法找到了最佳硼提取率所对应的渣系组成，为 硼提取过程优化提供了新的途径1 5 2 i 。李兵等将模拟退火( s a a ) 和遗传算法 ( g a s ) 较强的全局搜索能力和趋化性算法( c a ) 较强的局部搜索能力结合 起来，提出了一种新的随机优化方法。将该法用于化工柔性工业过程优化， 可以较快地找到全局最优解【”l 。 七、异常值检啦 实验数据可能被异常值污染，基于最小中位值残差平方( l m s ) 的稳健 回归对异常值是稳健的，且可用来检验异常值。最初l m s 法只能用来处理线 中国科技大学硕士学位论文 第一章遗传算法概述 性模型，而遗传算法可以用来获得非线性模型的对数。v a n k e e r b e r g h e n 等成 功地分析校正了有异常值污染的药物动力学数据，这说明了将遗传算法用于 l m s 的灵活性m i ，l e a r d i 将遗传算法用于异常值的检出，即使在经典方法无 能为力的场合，遗传算法仍能将异常值检出陋1 。 八、其它 d ew e i j e r 等先用有关聚乙烯对苯酸酯( p e t ) 结构一眭质的复杂关系训 练人工神经网络，根据p e t 的机械和收缩性质，用遗传算法寻找其设想的物 理结构，再以实验数据来检验遗传算法所找到的优化结构【5 6 l 。h a n a g a n d i 等 将遗传算法用来解决聚合物表面吸附的自恰场模型问题，与传统的梯度搜索 法比较，遗传算法弓梯度搜索法结合可以改善收敛特性。而无需深入了解其 物理特性，对任何随机初始群体，该搜索算法都能保证收敛j 。w i s e 等将遗 传算法用于动力学模型识别，并与神经网络、非线性有偏回归法进行了比较。 使用直接线性传递项的人工神经网络法的预测精度较好，但在非线性模型 中，遗传算法能用更少时间获得与其相似甚至更好的结果嘲1 。 w ie n k e 等将遗传算法用于多变量多目标向量的优化中，与其它搜索法如 改进单纯形法、最速下降法、模拟退火法及最小二乘法等在计算费用和速度、 全局和局部的优化能力、对分析设备的在线适应性及实验工作量等进行了比 较，并：博其用来优化原子发射光谱法同时测定矾土中六种微量元素的光谱激 发条件l ”j 。 r o s s i 等将遗传算法用于n d d o 波函数的参数研究，和该法拟合用n d d o 分子轨道理论根据初始数据得到的一组能量差，产生一作用于c b c i l 。反应的 特殊反应参数，输入少数初始数据点，能很好地拟合势能面和进行有机反应 的直接动力学计算咖1 。s m i t h 用遗传算法设计二元合金计算晶胞每个原子的 化学物种，以使一个特定化学组成的样品其总能量最小，研究结果表明，遗 传算法优于传统的蒙特卡罗法1 。另一篇很有意思的文章是，c a r t w r i g h t 等 将遗传算法用于大气污染分析。通过分析污染物分布，用遗传算法处理多污 染源一多接收器问题，可研究污染源分布，结果优于现行的模型 6 2 l 。 遗传算法的发展历史并不长，在化学中的应用还不广泛，随着研究工作 的深化，它在化学领域中将会开拓出更多的应用，前景广阔。 中国科技大学硕士学位论文第一章遗传算法概述 参考文献 1 】h o l l a n djh ，a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m s u n i v e r s i t yo f m i c h i g a np r e s s ，19 7 5 ，m i tp r e s s ，19 9 2 【2 】d a v i sl ，s t e e n s t r u pm ，g e n e t i ca l g o r i t h m sa n ds i m u l a t e da n n e a l i n g ，p i t m a n ， l o n d o n ，1 9 8 7 ：1 【3 】w a n gq b i 0 1 c y b e m ，1 9 8 7 ，5 7 ：9 5 4 d ej o n gk ，i e e et r a n s s y s t m a nc y b e m ，19 8 0 ，1 0 ：5 6 5 】f r a s e r as ，s i m u l a t i o no f g e n e t i cs y s t e m s jo f t h e o r e t i c a lb i o l o g y , 1 9 6 2 ，2 ： 3 2 9 3 4 6 ( 6 lb a g l e yjd ，t h eb e h a v i o ro fa d a p t i v es y s t e mw h i c he m p l o yg e n e t i ca n d c o r e l a t i o na l g o r i t h m ： p hdd i s s e r t a t i o n u n i v e r s i t yo fm i c h i g a n ，n o 6 8 7 5 5 6 ，1 9 6 7 【7 1h o l l s t i e nrb ，a r t i f i c i a lg e n e t i ca d a p t a t i o ni nc o m p u t e rc o n t r o ls y s t e m s ： p 1 1dd i s s e r t a t i o n u n i v e r s i t yo f m i c h i g a n ，n o 7 1 2 3 7 7 3 ，1 9 7 1 8 】d ej o n gka ，a na n a l y s i so ft h eb e h a v i o u ro fac l a s so fg e n e t i ca d a p t i v e s ) s t e m s ： hdd i s s e r t a t i o n u n i v e r s i t yo f m i c h i g a n ，n o 7 6 9 3 8 1 ，1 9 7 5 【9 1s y s w e r d ag ，u n i f o r mi ng e n e t i ca l g o r i t h m s ，i c g a 8 9 ，m o r g a nk a u f m a n n ， 1 9 8 92 9 10 】e s h e l m e nl ，a n ds c h a f f f e rd ，p r e v e n t i n gp r e m a t u r ec o n v e r g e n c ei ng e n e t i c a l g o r i t