摘要模仿自然界生物进化而发展起来的进化算法是一种启发式优化算法，以其独特新颖的思路成功应用于多领域的优化处理.笔者对进化算法在定量构效关系研究中的应用进行了综述.

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.1Illustration 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)²等构成，每一个染色体代表一种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对多种适合函数作了比较，认为交叉检验