进化算法在定量构效关系研究中的应用
作者：朱 杰1 季海涛 张万年
单位：第二军医大学药学院，上海 200433
关键词：定量构效关系；进化算法；遗传算法；进化规划；进化策略
摘 要 模仿自然界生物进化而发展起来的进化算法是一种启发式优化算法摘 要 模仿自然界生物进化而发展起来的进化算法是一种启发式优化算法，以其独特新颖的思路成功应用于多领域的优化处理.笔者对进化算法在定量构效关系研究中的应用进行了综述.
Hansch于本世纪60年代初提出的QSAR对药物化学及药物设计的发展起了巨大的推动作用.经数十年的发展，QSAR在数学模型、描述参数及数据处理方法等方面都取得了很大的进步.70年代在数学模型的应用方面，Kubinyi由Hansch提出的抛物线模型发展出新的双线性模型，Martin,Hackbarth提出了非线性模型，此外还有Lien提出的包括药效和药动两方面的QSAR模型等.到了90年代新的描述参数如差异性立体参数、正交化描述符、分子相似性指数等不断出现，而且传统理化参数与量化参数、拓扑指数的联合应用已成为当今的发展趋势.引人注目的是随着计算机科学及分子图形技术的进步，现已出现了以分子的空间结构信息为参数的3D-QSAR研究，其中以比较分子力场分析法(CoMFA)应用最多.此外针对Hansch提出的经典数据处理法——多元线性回归(MLR)的不足，学者们也发展了多种新的数据处理方法，如适应性最小二乘法(ALS)，主成分分析法(PCA)，非线性映射法，偏最小二乘法(PLS)和神经网络(NN)方法等.尽管QSAR研究发展迅速，但仍有一些基本难点没有解决，如描述参数(变量)的选择问题.而借鉴生物界自然选择和自然遗传机制发展起来的进化算法(EA)是一种新颖有效且非常稳健的随机搜索算法，已在最优化、机器学习及并行处理等领域得到了广泛的应用.目前EA已进入QSAR研究领域，用于对选择描述变量进行优化处理且获得了极大的成功.
, 百拇医药
1 进化算法简介
进化算法(EA)是受自然界中进化过程的启发，模仿达尔文进化论的一些主要原则建立起来的.人们只要将求解问题的可能解决方法转译成计算机可处理的数据结构(称为个体，亦可特称为染色体，常由多个个体组成一个种群)，就可以通过EA在计算机上对其实施进化，得到较满意的解决.自1957年Box对这种想法做了首次尝试以来，至今已主要发展出三种典型的算法〔1〕：遗传算法(genetic algorithms，GA)、进化规划(evolutionary programming，EP)和进化策略(evolution strategies，ES).
1.1 遗传算法
遗传算法(GA)是EA中应用最多且最为广泛的一种方法，Holland〔2〕对其发展作出过重大贡献.最简单的GA只有一个种群(population)，其个体多用变量串的形式(如一组由0/1组成的二进制编码)表示，或是用真值实数串的形式表示.GA主要使用选择、杂交、变异这三种算子对种群进行进化操作.选择主要是按适合函数计算出的得分从种群中挑选优秀的个体以作为父代进行繁殖，目前常用的是通过轮盘(roulette-wheel)算法〔3〕进行选择.杂交方法有单点交叉和多点交叉(包括两点交叉、均匀交叉等)多种，最简单的单点交叉操作见图1；通过交叉互换，父代的遗传物质传给了下一代，并生成了重组的新结构.变异即通过随机翻转二进制字串的字节或给真值串添加个高斯随机数来扰乱染色体.与自然界相似，变异操作是小概率的，但它因增加了种群的多样性而有可能打破局部优化的僵局，因而是必要的.典型的GA操作分以下七步：随机设置一个n维向量组成的初始种群，用适合函数给种群中每个成员打分，根据适合得分选择父代个体，通过交叉和(或)变异产生子代个体，用适合函数给子代打分，如果子代个体更优秀则取代父代个体，再从第3步开始循环操作直到满足结束条件.GA具体操作可参考文献〔2，4～6〕.
, 百拇医药
Fig.1 Illustration of one-point crossover in a GA
1.2 进化规划
进化规划(EP)最早由美国的L.J.Fogel等人在60年代中期提出.其区别于GA和ES的地方是它完全不用杂交算子，而只使用变异算子繁衍后代：通常是给字串中的每个元素加上个高斯随机数.EP方法中每个父代个体可产生一至数个子代，常用锦标赛(tournaments)方法对父子两代进行选择：每个个体都要与许多随机选择出来的对手进行比较，适合得分超过一个对手，即算获胜一次，所有个体(父代+子代)按获胜次数排序，从高到低选取一定数量组成新的父代以继续进化.EP中可以通过变动参加锦标赛的个体数目n来改变选择压力：n增大则压力增大，进化速度加快，进化代数减少，但很可能得到局部最优结果；n降低则压力降低，进化速度降低，进化代数增加，但可提高算法的搜寻质量.因此在实际应用中如何选择n以达到最佳平衡至关重要.简单的EP操作亦分七步：随机设置一个n维向量组成的初始种群，用适合函数给种群中的每个成员打分，每个父代个体通过变异产生一个后代，用适合函数给n个后代打分，对2n个个体(父代+子代)实行锦标赛制，获胜次数最多的n个个体组成新种群，再从第3步开始循环操作直到满足结束条件.此外对EP还有多种改进之处，如允许每个父代个体可产生多个后代及使用自适应变异参数〔7〕都是十分有效的.EP详情可参考文献〔1，8，9〕.
, 百拇医药
1.3 进化策略
进化策略(ES)是Rechenberg和Schwefel于60年代初在德国合作研究时创立的.它与EP十分相似，主要有两点区别：ES除了主要使用变异算子外还使用多种重组算子(如互换)，ES在选择中不是采用EP那种概率性的锦标赛制而是使用一种确定性的排序程序.ES的简单操作如下：随机设置一个n维向量组成的初始种群，用适合函数给种群中的每个成员打分，n个父代个体经变异和重组产生m个子代子体，用适合函数给m个子代打分，按适合函数对m+n个个体(父代+子代)进行排序，选择最高得分的n个个体组成新种群，再从第3步开始循环操作直到满足结束条件.对ES的发展人们也作出了多种尝试，目前多应用的是多父母产生多子女的方法.ES详情可参考文献〔1，9〕.
综上可见，在应用EA处理实际问题时，需解决好以下问题：确定求解问题的表示方案，即如何将需处理的问题恰当地转译成EA可操作的染色体；确定恰当的适合函数以确保种群向理想方向进化，选择合适的算法参数，如种群规模(种群内个体数目)、杂交和变异发生的几率及EP中参加锦标赛的个体数目n等，确定合适的结束条件以保证种群进化到理想的地步.
, 百拇医药
2 进化算法在定量构效关系研究中的应用
Rogers和Hopfinger将Holland的GA与Friedman的MARS(multivariate adaptive regression splines)算法〔10〕结合发展出一种GFA(genetic function approximation)算法〔11〕，并将其用于QSAR和QSPR研究.GFA的染色体由一系列基本描述变量组成的简单函数如(logP-10.1)2等构成，每一个染色体代表一种QSAR模型，其得分由Friedman的LOF(lack of fit)值〔10〕来衡量，既可避免过拟合现象又能使用户自己控制拟合的平滑度.操作时首先随机选择一定数量的函数串组成初始种群，用最小二乘法得出个体中各函数项的系数，依其LOF得分成反比地选出父代，进行进化操作.其中杂交只使用单点交叉法，而变异则包括添加一新的随机基本函数或移动Spline型函数的结点两种，各占50%的几率.种群中不允许有重复模型出现.GFA算法一次可得到多个较佳的QSAR模型，并可通过对模型进化过程的研究获得许多标准回归分析得不到的信息.GFA可以使用Splines、高斯或者高阶多项式等各种函数来进行建模，并以全面的模式检测来自动选择函数及确定染色体(QSAR模型)中的基本函数项数，而不是通过逐渐增减手段(前进、后退法)建立模型.测试结果表明GFA产生的模型相当于或超过回归分析和NN方法，且发现将几个高得分模型均化处理可产生更强的预测力〔11〕.GFA软件现已经商业化〔12〕.
, 百拇医药
Luke运用EP进行了QSAR模型的构建〔13〕，其个体亦是用与Rogers〔11〕相似的函数串表示.Luke认为EP较适合于含有许多描述变量但又要求在最后预测中仅保留少数几个的情况，而此时GA则因杂交算子的存在无法保证种群的总体适合度会一代代地增高.Luke以COST作为适合函数，1/COST的值作为适合得分.COST包含两项：一项是根均方误(RMSE)，一项是设计用来使EP有利于产生含预定理想项数的模型.变异父代模型中的项数或是改变适合函数第2项的权重都可用来产生子代.选择是将父代和子代合并后按适合得分排序来进行.而非实行锦标赛制.对Rogers和Hopfinger使用的数据资料〔11〕的测试表明EP是一个十分迅速、有效的QSAR/QSPR建模方法：EP可产生与GFA同样高质量的QSAR方程，并且对Selwood数据组(QSAR测试的标准数据组)的处理时还发现了一些GFA未发现的较佳模型.最近，国内的王亭、周家驹也将EP用于了QSAR研究〔14〕。其不同处在于他们对个体采用了直接强制进化手段：变异得到的个体必须优于父代，否则重新变异直至更优或超过规定次数.对杀幼虫剂和磺酰脲除草剂两个系列的应用表明：EP是一种有效的变量选择方法，可获得多个高质量QSAR方程.并且经研究表明若以增加计算时间为代价，则交互检验得到的相关系数是避免过拟合现象的理想适合函数.
, 百拇医药
So和Karplus将EA和NN联合对Selwood数据组进行了QSAR研究〔15〕.鉴于以往对Selwood数据组研究〔11，13，16，17〕多得到仅含3个变量的较佳模型，且为了便于直接比较，So和Karplus将变量数定为3，采用上述两种进化算法：GFA(略作两点调整)和EP来挑选变量，而使用了一个3-3-1型SD-NN(steepest descent back propagation)进行建模.So对多种适合函数作了比较，认为交叉检验程序得到的相关系数Rcv值能较好的反应预测能力，但颇费时.研究发现GFA-NN和EP-NN在相近的进化时间里可得到同样的最佳模型，但剩余模式中GFA-NN明显低于EP-NN.检查发现，那些EP中高得分的模型在GFA-NN中都曾出现过，但随后就被杂交、变异操作所破坏.因此So只选择了EP进行继续的研究.同3变量回归模型的全枚举标准检测程序相比，EP-NN的有效性和完备性都是理想的，其得出的优秀模型具有极佳的拟合和预测能力，优于任何已发表的模型.鉴于Rogers的工作，So等人也将几个高得分的模型均化，组合成新模型.原则上这种组合模型因包含了更多的信息，预测能力会有提高，但在Selwood数据组中，还没有发现可明显优于最佳单模型的组合模型.尽管如此So和Karplus仍然认为这不失为一种提高预测能力的好方法.其后So和Karplus又用EP-NN对系列苯并二氮(艹)/(卓)化合物进行了研究〔18〕.此前Maddalena等人已对该系列化合物采用后退删除策略选择变量，用10-3-1型SD-NN建立了较好的模型〔19〕.针对SD-NN的不足，So等人选用在速度和稳定性上都有所提高的SCG-NN，以交叉检验得到的相关系数Rcv为适合函数进行了QSAR建模，发现了许多优于Maddalena等人结果的模型.So和Karplus为提高速度，还对简化网络结构和改进评判标准作了研究.
, 百拇医药
Kyngas也将GA与NN联合对DHFA抑制剂作了QSAR研究〔20〕.与So等人的将GA与NN的辅助性结合不同的是：Kyngas将GA与NN进行合作式结合，利用GA优选NN的结构，寻找可产生最佳预测结果的NN.首先随机确立250个用各参数表示的NN组成初始种群.将各NN进行5次训练后对实验组进行预测，删去效果最差的50个NN.对余下的200个NN进行均匀杂交得到50个新NN，再对其进行概率为0.05的改变参数的变异操作.然后对这50个后代补训5n次，以便和前200个父代的受训次数相同.再对这250个NN进行5次训练、预测、删除最差的50个……如此重复至满足结束条件.结果显示该法优于Silipo的回归分析，且得到的NN较Andrea使用的NN〔21〕有更好的预测能力.
Kubinyi发展了一种MUSEUM算法〔22〕，因为没有杂交算子所以较倾向于EP，且仅使用变异的策略使得该算法更为迅速.但其种群内个体数仅为1，区别于其它的EA.MUSEUM首先随机选择一个由若干变量组成的模型，然后进行对一个或少数几个变量添加、删除的变异操作，适合得分如能在20次变异中有所提高则保留作下一代进化；如不能提高就需对较多数量的变量同时进行随机的增、删和(或)改变，5次操作内如有提高则保留备用，如仍无提高则对每个变量进行系统增删，以寻求进化.如果还是失败则以当前模型为最佳模型，然后对其所有变量作显著性检验，删除显著性低于95%的变量.在运用MUSEUM对Selwood数据组进行PLS分析中，Kubinyi采用了简单的FIT值(F值的函数)作为适合函数，得到了与以交叉检验得出的SPRESS为适合函数相当的结果.与其它方法(经典回归分析〔16〕、显著性聚类分析〔23〕、NN〔17〕、GFA〔11〕)的比较发现，MUSEUM可得到更为合适的QSAR模型.其后的研究〔24〕中，Kubinyi将MUMSEUM和一个用于产生2或3变量模型的系统搜寻程序联合，速度可较MUSEUM提高一个数量级.近来Kubinyi又发现MUSEUM算法在回归和PLS分析中对变量选择也是有效的〔25〕.
, 百拇医药
3 评述与展望
进化算法本质上是一种启发式优化算法，群体搜索策略及种群中个体间的信息交换是它的两个主要特点.它通过对种群进行进化操作从而引入竞争机制，在解空间中能以很大的概率找到全局最优解而不易陷入局部最优，且其固有的并行性特征使其非常适用于大规模并行搜索，因而优于传统的优化算法，在高维搜索和多局部极值优化问题中得到了越来越多的应用.进化算法以其新颖而简单直观的思路与常规QSAR研究中的MLR，PLS，NN等方法结合，指导它们获得具最优变量组合的QSAR方程.可以看出正是其所模仿的自然进化中适者生存的机制迫使种群中的个体向着更优的方向进化.尤为难得的是EA的并行性使其可同时对一组个体实施进化操作，最终获得一组较优的QSAR方程，这点是别的QSAR研究方法所无法达到的.而且在QSAR应用中，EA所面对的如何确定求解问题的表示方案的难题几乎不存在.可以说QSAR是EA应用较为成功的一个领域.至于如何选择最佳的适合函数及确定最优的种群规模、变异和杂交操作的相对比例等EA在各个应用领域都面临的问题，在QSAR研究中仍有进一步探讨的必要.
, 百拇医药
参 考 文 献
1.B a¨ck T,Schwefel HP.An overview of evolutionary algorithms for parameter optimization.Evol Compout,1993，1(1)：1～24
2.(a)Holland JH,Adaption in natural and artifical systems.University of Michigan Press,Ann Arbor,MI,1975
(b)Holland JH,Adaption in natural and artificial system.2nd ed.MIT Press，Cambridge,MA，1992
3.Goldberg DE.Genetic algorithms in search,optimization and machine learing.Reading,MA:Addison-Wesley,1989
, http://www.100md.com
4.Davis L Ed.Handbook of genetic algorithms.New York,NY:Van Nostrand Reinhold,1991
5.Holland JH.Genetic algothms.computer programs that“evolve” in ways that resemble natural selection can solve complex problems even their creators do not fully understand.Scientific American,1992，267(1)：44～50
6.Forrest S.Genetic algotithms:principles of natural selection applied to computation.Science,1993,261(5123)：872～878
, 百拇医药
7.Saravanan N,Fogel DB,Nelson KM.A comparison of methods for self-adaptation in evolutionary algorithms.BioSystems,1995，36(2)：157～166
8.Fogel DB.An introduction to simulated evolutionary optimization.IEEE Trans Neur Netw,1994，5(1)：3～14
9.Ba¨ck T.Evolutionary algirithms in theory and practice.Oxford University Press,Oxford,UK,1995
10.Friedman J.Multivariate adaptive regression splines.Technical Report No.102,Laboratory for Computationtal Statistics,Department of Statistics,Stanford University,Stanford,CA,Nov 1988(revised Ang 1990)
, 百拇医药
11.Rogers D,Hopfinger AJ.Application of genetic function approximation to quantitative structure-activity relationships and quantitative structure-property relationships.J Chem Inf Comput Sci,1994，34(4)：854～866
12.C2GA，Molecular Simulations Inc,9685 Scranton Road,San Diego,CA,92121,USA
13.Luke BT.Evclationary progamming applied to the development of QSAR and QSPR.J Chem Inf Comput Sci，1994，34(6)：1279～1287
, 百拇医药
14.王亭，周家驹.定量结构-活性关系研究中变量挑选的进化算法.计算机与应用化学，1997，14(2)：95～100
15.So SS,Karplus M.Evolutionary optimization in QSAR:an application of genetic neural networks.J Med Chem，1996，39(7)：1521～1530
16.Selwood DL,Livingstone DJ,Comley JC，et al.SAR of antifilarial antimycin analogues:a multivariate pattern recognition Study.J Med Chem,1990，33(1)：136～142
17.Wikel JH,Dow ER.The use of neural networks for variable selection in QSAR.Bioorg Med Chem Lett,1993，3(4)：645～651
, http://www.100md.com
18.So SS,Karplus M.Genetic neural networks for QSARs:improvements and application of benzodiazepine affinity for benzodiazpine/GABAA receptors.J Med Chem,1996，36(26)：5246～5256
19.Maddalena DJ,Jonston GAR.Prediction of receptor properties and binding affinity of ligands to benzodiazepine/GABAA receptors using artifical neural networks.J Med Chem,1995，38(4)：715～724
20.Kyngas J,Valjakka J.Evolutionary neural networks in QSAR of dihydrofolate reductase inhibitors.Quand Struct-Act Relat,1996，15(4)：296～301
, 百拇医药
21.Audrea TA,Kalayeh H.Application of neural networks in quantitative structure-activity relationships of dihydrofolate reductase inhibitors.J Med Chem,1991，34(9)：2824～2836
22.Kubinyi H.Variable selection in QSAR studies.I.An evolutionary algorithm.Quant Struct-Act Relat,1994，13(3)：285～294
23.McFarland JW,Gans DJ.On identifying likely determinants of biological activity in high dimensional QSAR problems.Quant Struct-Act Relat,1994，13(1)：11～17
24.Kubinyi H.Variable selection in QSAR studies.Ⅱ.A high efficient combination of systemic search and evolution.Quant Struct-Act Relat,1994，13(4)：393～401
25.Kubinyi H.Evolutionary variables selection in regression and PLS analysis.J Chemometr,1996，10(2)：119～133
收稿日期:1999-01-13, 百拇医药(朱 杰1 季海涛 张万年)
单位：第二军医大学药学院，上海 200433
关键词：定量构效关系；进化算法；遗传算法；进化规划；进化策略
摘 要 模仿自然界生物进化而发展起来的进化算法是一种启发式优化算法摘 要 模仿自然界生物进化而发展起来的进化算法是一种启发式优化算法，以其独特新颖的思路成功应用于多领域的优化处理.笔者对进化算法在定量构效关系研究中的应用进行了综述.
Hansch于本世纪60年代初提出的QSAR对药物化学及药物设计的发展起了巨大的推动作用.经数十年的发展，QSAR在数学模型、描述参数及数据处理方法等方面都取得了很大的进步.70年代在数学模型的应用方面，Kubinyi由Hansch提出的抛物线模型发展出新的双线性模型，Martin,Hackbarth提出了非线性模型，此外还有Lien提出的包括药效和药动两方面的QSAR模型等.到了90年代新的描述参数如差异性立体参数、正交化描述符、分子相似性指数等不断出现，而且传统理化参数与量化参数、拓扑指数的联合应用已成为当今的发展趋势.引人注目的是随着计算机科学及分子图形技术的进步，现已出现了以分子的空间结构信息为参数的3D-QSAR研究，其中以比较分子力场分析法(CoMFA)应用最多.此外针对Hansch提出的经典数据处理法——多元线性回归(MLR)的不足，学者们也发展了多种新的数据处理方法，如适应性最小二乘法(ALS)，主成分分析法(PCA)，非线性映射法，偏最小二乘法(PLS)和神经网络(NN)方法等.尽管QSAR研究发展迅速，但仍有一些基本难点没有解决，如描述参数(变量)的选择问题.而借鉴生物界自然选择和自然遗传机制发展起来的进化算法(EA)是一种新颖有效且非常稳健的随机搜索算法，已在最优化、机器学习及并行处理等领域得到了广泛的应用.目前EA已进入QSAR研究领域，用于对选择描述变量进行优化处理且获得了极大的成功.
, 百拇医药
1 进化算法简介
进化算法(EA)是受自然界中进化过程的启发，模仿达尔文进化论的一些主要原则建立起来的.人们只要将求解问题的可能解决方法转译成计算机可处理的数据结构(称为个体，亦可特称为染色体，常由多个个体组成一个种群)，就可以通过EA在计算机上对其实施进化，得到较满意的解决.自1957年Box对这种想法做了首次尝试以来，至今已主要发展出三种典型的算法〔1〕：遗传算法(genetic algorithms，GA)、进化规划(evolutionary programming，EP)和进化策略(evolution strategies，ES).
1.1 遗传算法
遗传算法(GA)是EA中应用最多且最为广泛的一种方法，Holland〔2〕对其发展作出过重大贡献.最简单的GA只有一个种群(population)，其个体多用变量串的形式(如一组由0/1组成的二进制编码)表示，或是用真值实数串的形式表示.GA主要使用选择、杂交、变异这三种算子对种群进行进化操作.选择主要是按适合函数计算出的得分从种群中挑选优秀的个体以作为父代进行繁殖，目前常用的是通过轮盘(roulette-wheel)算法〔3〕进行选择.杂交方法有单点交叉和多点交叉(包括两点交叉、均匀交叉等)多种，最简单的单点交叉操作见图1；通过交叉互换，父代的遗传物质传给了下一代，并生成了重组的新结构.变异即通过随机翻转二进制字串的字节或给真值串添加个高斯随机数来扰乱染色体.与自然界相似，变异操作是小概率的，但它因增加了种群的多样性而有可能打破局部优化的僵局，因而是必要的.典型的GA操作分以下七步：随机设置一个n维向量组成的初始种群，用适合函数给种群中每个成员打分，根据适合得分选择父代个体，通过交叉和(或)变异产生子代个体，用适合函数给子代打分，如果子代个体更优秀则取代父代个体，再从第3步开始循环操作直到满足结束条件.GA具体操作可参考文献〔2，4～6〕.
, 百拇医药
Fig.1 Illustration of one-point crossover in a GA
1.2 进化规划
进化规划(EP)最早由美国的L.J.Fogel等人在60年代中期提出.其区别于GA和ES的地方是它完全不用杂交算子，而只使用变异算子繁衍后代：通常是给字串中的每个元素加上个高斯随机数.EP方法中每个父代个体可产生一至数个子代，常用锦标赛(tournaments)方法对父子两代进行选择：每个个体都要与许多随机选择出来的对手进行比较，适合得分超过一个对手，即算获胜一次，所有个体(父代+子代)按获胜次数排序，从高到低选取一定数量组成新的父代以继续进化.EP中可以通过变动参加锦标赛的个体数目n来改变选择压力：n增大则压力增大，进化速度加快，进化代数减少，但很可能得到局部最优结果；n降低则压力降低，进化速度降低，进化代数增加，但可提高算法的搜寻质量.因此在实际应用中如何选择n以达到最佳平衡至关重要.简单的EP操作亦分七步：随机设置一个n维向量组成的初始种群，用适合函数给种群中的每个成员打分，每个父代个体通过变异产生一个后代，用适合函数给n个后代打分，对2n个个体(父代+子代)实行锦标赛制，获胜次数最多的n个个体组成新种群，再从第3步开始循环操作直到满足结束条件.此外对EP还有多种改进之处，如允许每个父代个体可产生多个后代及使用自适应变异参数〔7〕都是十分有效的.EP详情可参考文献〔1，8，9〕.
, 百拇医药
1.3 进化策略
进化策略(ES)是Rechenberg和Schwefel于60年代初在德国合作研究时创立的.它与EP十分相似，主要有两点区别：ES除了主要使用变异算子外还使用多种重组算子(如互换)，ES在选择中不是采用EP那种概率性的锦标赛制而是使用一种确定性的排序程序.ES的简单操作如下：随机设置一个n维向量组成的初始种群，用适合函数给种群中的每个成员打分，n个父代个体经变异和重组产生m个子代子体，用适合函数给m个子代打分，按适合函数对m+n个个体(父代+子代)进行排序，选择最高得分的n个个体组成新种群，再从第3步开始循环操作直到满足结束条件.对ES的发展人们也作出了多种尝试，目前多应用的是多父母产生多子女的方法.ES详情可参考文献〔1，9〕.
综上可见，在应用EA处理实际问题时，需解决好以下问题：确定求解问题的表示方案，即如何将需处理的问题恰当地转译成EA可操作的染色体；确定恰当的适合函数以确保种群向理想方向进化，选择合适的算法参数，如种群规模(种群内个体数目)、杂交和变异发生的几率及EP中参加锦标赛的个体数目n等，确定合适的结束条件以保证种群进化到理想的地步.
, 百拇医药
2 进化算法在定量构效关系研究中的应用
Rogers和Hopfinger将Holland的GA与Friedman的MARS(multivariate adaptive regression splines)算法〔10〕结合发展出一种GFA(genetic function approximation)算法〔11〕，并将其用于QSAR和QSPR研究.GFA的染色体由一系列基本描述变量组成的简单函数如(logP-10.1)2等构成，每一个染色体代表一种QSAR模型，其得分由Friedman的LOF(lack of fit)值〔10〕来衡量，既可避免过拟合现象又能使用户自己控制拟合的平滑度.操作时首先随机选择一定数量的函数串组成初始种群，用最小二乘法得出个体中各函数项的系数，依其LOF得分成反比地选出父代，进行进化操作.其中杂交只使用单点交叉法，而变异则包括添加一新的随机基本函数或移动Spline型函数的结点两种，各占50%的几率.种群中不允许有重复模型出现.GFA算法一次可得到多个较佳的QSAR模型，并可通过对模型进化过程的研究获得许多标准回归分析得不到的信息.GFA可以使用Splines、高斯或者高阶多项式等各种函数来进行建模，并以全面的模式检测来自动选择函数及确定染色体(QSAR模型)中的基本函数项数，而不是通过逐渐增减手段(前进、后退法)建立模型.测试结果表明GFA产生的模型相当于或超过回归分析和NN方法，且发现将几个高得分模型均化处理可产生更强的预测力〔11〕.GFA软件现已经商业化〔12〕.
, 百拇医药
Luke运用EP进行了QSAR模型的构建〔13〕，其个体亦是用与Rogers〔11〕相似的函数串表示.Luke认为EP较适合于含有许多描述变量但又要求在最后预测中仅保留少数几个的情况，而此时GA则因杂交算子的存在无法保证种群的总体适合度会一代代地增高.Luke以COST作为适合函数，1/COST的值作为适合得分.COST包含两项：一项是根均方误(RMSE)，一项是设计用来使EP有利于产生含预定理想项数的模型.变异父代模型中的项数或是改变适合函数第2项的权重都可用来产生子代.选择是将父代和子代合并后按适合得分排序来进行.而非实行锦标赛制.对Rogers和Hopfinger使用的数据资料〔11〕的测试表明EP是一个十分迅速、有效的QSAR/QSPR建模方法：EP可产生与GFA同样高质量的QSAR方程，并且对Selwood数据组(QSAR测试的标准数据组)的处理时还发现了一些GFA未发现的较佳模型.最近，国内的王亭、周家驹也将EP用于了QSAR研究〔14〕。其不同处在于他们对个体采用了直接强制进化手段：变异得到的个体必须优于父代，否则重新变异直至更优或超过规定次数.对杀幼虫剂和磺酰脲除草剂两个系列的应用表明：EP是一种有效的变量选择方法，可获得多个高质量QSAR方程.并且经研究表明若以增加计算时间为代价，则交互检验得到的相关系数是避免过拟合现象的理想适合函数.
, 百拇医药
So和Karplus将EA和NN联合对Selwood数据组进行了QSAR研究〔15〕.鉴于以往对Selwood数据组研究〔11，13，16，17〕多得到仅含3个变量的较佳模型，且为了便于直接比较，So和Karplus将变量数定为3，采用上述两种进化算法：GFA(略作两点调整)和EP来挑选变量，而使用了一个3-3-1型SD-NN(steepest descent back propagation)进行建模.So对多种适合函数作了比较，认为交叉检验程序得到的相关系数Rcv值能较好的反应预测能力，但颇费时.研究发现GFA-NN和EP-NN在相近的进化时间里可得到同样的最佳模型，但剩余模式中GFA-NN明显低于EP-NN.检查发现，那些EP中高得分的模型在GFA-NN中都曾出现过，但随后就被杂交、变异操作所破坏.因此So只选择了EP进行继续的研究.同3变量回归模型的全枚举标准检测程序相比，EP-NN的有效性和完备性都是理想的，其得出的优秀模型具有极佳的拟合和预测能力，优于任何已发表的模型.鉴于Rogers的工作，So等人也将几个高得分的模型均化，组合成新模型.原则上这种组合模型因包含了更多的信息，预测能力会有提高，但在Selwood数据组中，还没有发现可明显优于最佳单模型的组合模型.尽管如此So和Karplus仍然认为这不失为一种提高预测能力的好方法.其后So和Karplus又用EP-NN对系列苯并二氮(艹)/(卓)化合物进行了研究〔18〕.此前Maddalena等人已对该系列化合物采用后退删除策略选择变量，用10-3-1型SD-NN建立了较好的模型〔19〕.针对SD-NN的不足，So等人选用在速度和稳定性上都有所提高的SCG-NN，以交叉检验得到的相关系数Rcv为适合函数进行了QSAR建模，发现了许多优于Maddalena等人结果的模型.So和Karplus为提高速度，还对简化网络结构和改进评判标准作了研究.
, 百拇医药
Kyngas也将GA与NN联合对DHFA抑制剂作了QSAR研究〔20〕.与So等人的将GA与NN的辅助性结合不同的是：Kyngas将GA与NN进行合作式结合，利用GA优选NN的结构，寻找可产生最佳预测结果的NN.首先随机确立250个用各参数表示的NN组成初始种群.将各NN进行5次训练后对实验组进行预测，删去效果最差的50个NN.对余下的200个NN进行均匀杂交得到50个新NN，再对其进行概率为0.05的改变参数的变异操作.然后对这50个后代补训5n次，以便和前200个父代的受训次数相同.再对这250个NN进行5次训练、预测、删除最差的50个……如此重复至满足结束条件.结果显示该法优于Silipo的回归分析，且得到的NN较Andrea使用的NN〔21〕有更好的预测能力.
Kubinyi发展了一种MUSEUM算法〔22〕，因为没有杂交算子所以较倾向于EP，且仅使用变异的策略使得该算法更为迅速.但其种群内个体数仅为1，区别于其它的EA.MUSEUM首先随机选择一个由若干变量组成的模型，然后进行对一个或少数几个变量添加、删除的变异操作，适合得分如能在20次变异中有所提高则保留作下一代进化；如不能提高就需对较多数量的变量同时进行随机的增、删和(或)改变，5次操作内如有提高则保留备用，如仍无提高则对每个变量进行系统增删，以寻求进化.如果还是失败则以当前模型为最佳模型，然后对其所有变量作显著性检验，删除显著性低于95%的变量.在运用MUSEUM对Selwood数据组进行PLS分析中，Kubinyi采用了简单的FIT值(F值的函数)作为适合函数，得到了与以交叉检验得出的SPRESS为适合函数相当的结果.与其它方法(经典回归分析〔16〕、显著性聚类分析〔23〕、NN〔17〕、GFA〔11〕)的比较发现，MUSEUM可得到更为合适的QSAR模型.其后的研究〔24〕中，Kubinyi将MUMSEUM和一个用于产生2或3变量模型的系统搜寻程序联合，速度可较MUSEUM提高一个数量级.近来Kubinyi又发现MUSEUM算法在回归和PLS分析中对变量选择也是有效的〔25〕.
, 百拇医药
3 评述与展望
进化算法本质上是一种启发式优化算法，群体搜索策略及种群中个体间的信息交换是它的两个主要特点.它通过对种群进行进化操作从而引入竞争机制，在解空间中能以很大的概率找到全局最优解而不易陷入局部最优，且其固有的并行性特征使其非常适用于大规模并行搜索，因而优于传统的优化算法，在高维搜索和多局部极值优化问题中得到了越来越多的应用.进化算法以其新颖而简单直观的思路与常规QSAR研究中的MLR，PLS，NN等方法结合，指导它们获得具最优变量组合的QSAR方程.可以看出正是其所模仿的自然进化中适者生存的机制迫使种群中的个体向着更优的方向进化.尤为难得的是EA的并行性使其可同时对一组个体实施进化操作，最终获得一组较优的QSAR方程，这点是别的QSAR研究方法所无法达到的.而且在QSAR应用中，EA所面对的如何确定求解问题的表示方案的难题几乎不存在.可以说QSAR是EA应用较为成功的一个领域.至于如何选择最佳的适合函数及确定最优的种群规模、变异和杂交操作的相对比例等EA在各个应用领域都面临的问题，在QSAR研究中仍有进一步探讨的必要.
, 百拇医药
参 考 文 献
1.B a¨ck T,Schwefel HP.An overview of evolutionary algorithms for parameter optimization.Evol Compout,1993，1(1)：1～24
2.(a)Holland JH,Adaption in natural and artifical systems.University of Michigan Press,Ann Arbor,MI,1975
(b)Holland JH,Adaption in natural and artificial system.2nd ed.MIT Press，Cambridge,MA，1992
3.Goldberg DE.Genetic algorithms in search,optimization and machine learing.Reading,MA:Addison-Wesley,1989
, http://www.100md.com
4.Davis L Ed.Handbook of genetic algorithms.New York,NY:Van Nostrand Reinhold,1991
5.Holland JH.Genetic algothms.computer programs that“evolve” in ways that resemble natural selection can solve complex problems even their creators do not fully understand.Scientific American,1992，267(1)：44～50
6.Forrest S.Genetic algotithms:principles of natural selection applied to computation.Science,1993,261(5123)：872～878
, 百拇医药
7.Saravanan N,Fogel DB,Nelson KM.A comparison of methods for self-adaptation in evolutionary algorithms.BioSystems,1995，36(2)：157～166
8.Fogel DB.An introduction to simulated evolutionary optimization.IEEE Trans Neur Netw,1994，5(1)：3～14
9.Ba¨ck T.Evolutionary algirithms in theory and practice.Oxford University Press,Oxford,UK,1995
10.Friedman J.Multivariate adaptive regression splines.Technical Report No.102,Laboratory for Computationtal Statistics,Department of Statistics,Stanford University,Stanford,CA,Nov 1988(revised Ang 1990)
, 百拇医药
11.Rogers D,Hopfinger AJ.Application of genetic function approximation to quantitative structure-activity relationships and quantitative structure-property relationships.J Chem Inf Comput Sci,1994，34(4)：854～866
12.C2GA，Molecular Simulations Inc,9685 Scranton Road,San Diego,CA,92121,USA
13.Luke BT.Evclationary progamming applied to the development of QSAR and QSPR.J Chem Inf Comput Sci，1994，34(6)：1279～1287
, 百拇医药
14.王亭，周家驹.定量结构-活性关系研究中变量挑选的进化算法.计算机与应用化学，1997，14(2)：95～100
15.So SS,Karplus M.Evolutionary optimization in QSAR:an application of genetic neural networks.J Med Chem，1996，39(7)：1521～1530
16.Selwood DL,Livingstone DJ,Comley JC，et al.SAR of antifilarial antimycin analogues:a multivariate pattern recognition Study.J Med Chem,1990，33(1)：136～142
17.Wikel JH,Dow ER.The use of neural networks for variable selection in QSAR.Bioorg Med Chem Lett,1993，3(4)：645～651
, http://www.100md.com
18.So SS,Karplus M.Genetic neural networks for QSARs:improvements and application of benzodiazepine affinity for benzodiazpine/GABAA receptors.J Med Chem,1996，36(26)：5246～5256
19.Maddalena DJ,Jonston GAR.Prediction of receptor properties and binding affinity of ligands to benzodiazepine/GABAA receptors using artifical neural networks.J Med Chem,1995，38(4)：715～724
20.Kyngas J,Valjakka J.Evolutionary neural networks in QSAR of dihydrofolate reductase inhibitors.Quand Struct-Act Relat,1996，15(4)：296～301
, 百拇医药
21.Audrea TA,Kalayeh H.Application of neural networks in quantitative structure-activity relationships of dihydrofolate reductase inhibitors.J Med Chem,1991，34(9)：2824～2836
22.Kubinyi H.Variable selection in QSAR studies.I.An evolutionary algorithm.Quant Struct-Act Relat,1994，13(3)：285～294
23.McFarland JW,Gans DJ.On identifying likely determinants of biological activity in high dimensional QSAR problems.Quant Struct-Act Relat,1994，13(1)：11～17
24.Kubinyi H.Variable selection in QSAR studies.Ⅱ.A high efficient combination of systemic search and evolution.Quant Struct-Act Relat,1994，13(4)：393～401
25.Kubinyi H.Evolutionary variables selection in regression and PLS analysis.J Chemometr,1996，10(2)：119～133
收稿日期:1999-01-13, 百拇医药(朱 杰1 季海涛 张万年)