能量优化算法与过渡态求解

4.6.1 能量最优算法

优化从本质上讲是数学问题，对于自变量x（或者向量X）的函数f（x）[或者f（X）]，求解其极值的过程就是优化的过程。能量优化中常用的算法有最速下降法（steepest descents method）、共轭梯度法（conjugate gradients method）、牛顿-拉夫逊方法（Newton-Raphson方法）、模拟退火（simulated annealing）和遗传算法（genetic algorithm）。

最速下降法历史悠久，是1847年Cauchy提出的，其基本思想是，从任意起始点开始，沿着目标函数在该点的负梯度方向，也即目标函数的最速下降方向，多次迭代即可找到局域的极小值。这种方法算法简单、计算量小但是收敛性不够好，其收敛速度正比于目标函数的条件数（最大本征值与最小本征值的比），因此如果条件数太大的话，其收敛将会变得很慢。

共轭梯度法对最速下降法的优化方向做了改进，优化方向不再仅仅依赖目标函数的负梯度方向，而是取决于本次迭代时的负梯度方向与上次迭代的负梯度方向的线性组合。这样共轭梯度法就能更准确地确定优化方向而减小计算量。共轭梯度法在复杂问题的表现上优于最速下降法。两者经常结合起来使用，先用最速下降法处理，然后用共轭梯度法做进一步的优化。

牛顿-拉夫逊方法又称为牛顿法（Newton’smethod），它是一种利用二阶导数求解极值的方法。对于具有二次型的函数均可用这种方法求解极值，例如能量函数。但是当能量函数远离二次时，这种方法很容易失稳，并且在能量优化过程中，牛顿法每次都要对Hessian矩阵求逆计算代价相当高。因此，这种方法一般作为最速下降法优化之后使之收敛的手段。

前面介绍的最速下降法、共轭梯度法和牛顿-拉夫逊方法在寻找局域极小值中表现很好，但是在解决全局最优问题时却很难实现。模拟退火和遗传算法是解决全局最优问题时常用的两种方法，下面简单介绍一下这两种方法。

模拟退火来源于冶金学的专有名词退火。退火是将材料加热后再经特定的速率缓慢冷却，这样做的目的是增大晶粒的体积，减少晶格中的缺陷。材料中原有的原子可能会停留在使内能局部最小的位置，加热升温之后能量变大，原子离开原来的位置，随机地在其他位置中移动；以适当速率缓慢冷却时，原子有更多的可能找到比原来内能更低的位置。模拟退火的原理与金属退火的原理近似，它以解空间里任意一点为起始搜索新的解，如果新解优于原有解则肯定会被接受，否则只有很小的概率被接受，当新解被接受时则用新解代替原有解开始下一轮的搜索，如果新解被拒绝时则在原有解的基础上继续搜索。

模拟退火算法与初始值无关，并且具有固有的并行性和渐进收敛性是一种不错的求全局最优解的方法。

遗传算法是借鉴了生物进化现象而发展起来的一种算法。在遗传算法中，优化问题的解称为“个体”，它由一系列“染色体”组成，“染色体”一般是简单的字符串或者数字串。一开始，算法随机产生一定数量的“个体”（或者人为确定生成），就是“种群”。然后“种群”中的每个“个体”都被评价，通过适应度函数（也叫目标函数）获得一个适应度数值，再根据适应度排序。接下来是产生下一代种群的过程。算法会根据“种群”中“个体”适应度高低选择进行“繁殖”的个体，适应度越高的“个体”被选择的概率越大，被选中的“个体”按照一定的概率进行“交配”，“交配”的过程就是将“父母”“染色体”中某部分随机交换产生两个新的“个体”代替原来的“个体”，这个过程中新产生的“个体”的“染色体”又有一定的概率发生“突变”，通常是其中的某个字节由0变为1，或者由1变为0。这样就得到了一个新的“种群”，然后进入下一轮的评价—选择—“繁殖”。整个过程与自然界的进化类似，最好的“个体”总是最多地被选择产生下一代，而适应度低的“个体”则逐渐被淘汰。

遗传算法最擅长的就是求解全局最优化问题，如果参数设置得恰当它能够跳出局部最优而找到全局最优点，因此在许多领域得到了广泛的应用。

4.6.2 过渡态求解

过渡态是基元反应中能量最高点所对应的分子构型，表现在反应的势能面上，过渡态结构的能量对坐标的一阶导数为零，二阶导数为负，是势能面上的一阶鞍点。确定过渡态有助于了解反应机理、计算反应速率。搜索过渡态结构的算法主要有基于初猜结构的算法、基于反应物结构的算法、基于反应物与产物结构的算法和全势能面扫描。

基于初猜结构的算法。过渡态是势能面上的一阶鞍点，与能量极小点和高阶鞍点一样一阶导数为零，因此可以用与能量优化类似的方法来寻找，例如牛顿-拉夫逊方法。牛顿法对初猜的Hessian矩阵十分敏感并且计算量也非常大，许多人在此基础上发展了不同的改进方法，如BFGS（Broyden Fletcher Goldfarb Shan-no），DFP（Davidon Fletcher Powell），SR1（Symmetric Rank1）、PSB（Powell Sym-metric Broyden），AH（Augmented Hessian）、QA（Quadratic Approximation）， TRIM（Trust Region Image Minimization）以及RFO（Rational Function Optimiza-tion）和P-RFO（Partitioned-RFO）等方法。

基于反应物结构的算法。这类方法从反应物的结构出发沿着势能面上反应可能经过的途径追踪反应的过程搜索过渡态。如最缓上升法（leaststeepascent）、EF（Eigenvector/Eigenvalue Following、ARTn（Activation Relaxation Technique nouveau）、GE（Gradient Extremal）、RGF（Reduced Gradient Following）、IS（Isopo-tenial Searching）和SO（Sphere Optimization）等方法。

基于反应物与产物结构的算法。合理的初猜结构往往不容易得到，完全从结构出发搜索势能面又太过盲目，有时甚至不能找到合理的过渡态，如果同时知道反应物和产物的结构再寻找过渡态结构就相对容易些了。这类方法主要有LST （Linear Synchronous Transit），QST（Quadratic Synchronous Transit），STQN （Combined Synchronous Transitand Quasi-Newton Methods）赝坐标法（Pseudo Reaction Coordinate），DHS方法（Dewar Healy Stewart），LTP方法（Line Then Plane），Ridge方法、Step-and-Slide方法等。

全势能面扫描是最可靠的方法，得到整个势能面后就可以很容易找到过渡态的一阶鞍点。但是，全势能面扫描的计算量非常大，一般仅限于反应中少数几个自由度的势能面扫描。即使如此，很多时候也不得不考虑半经验或者分子力学等更低级的方法。另外，全势能面扫描除了可以提供过渡态位置的信息以外还可用于研究反应路径、构象搜索等。

关于过渡态求解的方法还有很多，这里就不一一列举了，有兴趣的读者可以查阅相关专著。