1、最优化方法最优化方法Optimization Methods1第1页，共28页。最优化问题概述最优化问题概述Minimizes.t.nRx)(xFmixci,.,2,1,0)(mmixci,.,1,0)(Variable x:coordinatesObjective function F(x):energy,conformation,combination,etcConstraint ci(x):atom fixed,force field,etc目标函数目标函数变量变量/参数参数约束条件约束条件 最优化问题的一般形式为在一组限制最优化问题的一般形式为在一组限制性条件（性条件（等式等式/不等式
2、不等式、线性线性/非线性非线性）约）约束下寻找目标函数的束下寻找目标函数的极小值极小值/极大值极大值。2第2页，共28页。最优化问题概述最优化问题概述最优化问题的分类通常从最优化问题的分类通常从目标函数目标函数以及以及约束条件约束条件的特的特点入手。点入手。目标函数包括单变量函数、线性函数、线性函数平方目标函数包括单变量函数、线性函数、线性函数平方和、二次函数、非线性函数平方和、非光滑非线性函和、二次函数、非线性函数平方和、非光滑非线性函数等类型。数等类型。约束条件包括无约束、简单有界、线性函数、光滑非线约束条件包括无约束、简单有界、线性函数、光滑非线性函数等类型。性函数等类型。3第3页，共2
3、8页。最优化条件最优化条件对于任何满足上述所有约束条件 的点 称为可行点(feasible point)，而所有可行点的集合称为可行区域(feasible region)。全局极小Vs.局部极小通常得到的是局部极小约束条件下没有极值极限条件才有极值如，当 ，Minimizes.t.nRx)(xFmixci,.,2,1,0)(mmixci,.,1,0)(xF(x)强局部极小全局极小弱局部极小()ic x xx ()0 xF xe4第4页，共28页。最优化方法最优化方法Optimization Methods 数值最优化方法 Numerical Optimization 最陡下降法 Steepes
4、t Descent 共轭梯度法 Conjugated Gradient 牛顿法 Newtons Methods 非数值最优化方法 Non-numerical Optimization 模拟退火 Simulated Annealing 遗传算法 Genetic Algorithm 神经网络 Artificial Neural Network5第5页，共28页。最优化方法最优化方法Optimization Methods 数值最优化方法 Numerical Optimization 最陡下降法 Steepest Descent 共轭梯度法 Conjugated Gradient 牛顿法 Newto
5、ns Methods 非数值最优化方法 Non-numerical Optimization 模拟退火 Simulated Annealing 遗传算法 Genetic Algorithm 神经网络 Artificial Neural Network6第6页，共28页。数值最优化方法数值最优化方法算法结构算法结构迭代方法迭代方法 给定一个初始点 ，按照某一迭代规则生成一个有限/无限的点序列 来估计最优解 ，当给定的某个终止条件满足时停止迭代。有限序列的最后一个点为模型最优解的最佳估计无限序列的极限点为模型最优解的最佳估计非线性最优化算法非线性最优化算法基于步长的方法 step-length-b
6、ased methods信赖域方法 trust region methodsnRx 0 x kx7第7页，共28页。数值最优化方法数值最优化方法基于步长的方法基于步长的方法 Step-length-based Methods 步长因子 搜索方向，一般选择为F(x)在点 处的下降方向1kkkkxxpkkpkx算 法给定初始点如果 满足终止条件，则跳至步骤7，否则按照某种规则构造目标函数 F(x)在 点的搜索方向确定步长因子计算下一轮的迭代点重复步骤21.算法终止0 xkxkxkpk1kkkkxxp8第8页，共28页。数值最优化方法数值最优化方法线搜索方法线搜索方法 Line Search确定步长
7、因子线搜索方法的基本结构线搜索方法的基本结构沿搜索方向 确定函数 最优值的搜索区间；通过分割或插值技术迭代的缩小该区间，直至搜索到符合给定判据的可接受值根据判断结果是否可以被接受的判据类型，线搜索方法可分为两大类：根据判断结果是否可以被接受的判据类型，线搜索方法可分为两大类：精确线搜索 Exact line search不精确的线搜索 Accurate line search kkkF xpF xkp()kkF xp0()min()kkkkF xpF xp()()0kkkF xF xp 9第9页，共28页。数值最优化方法数值最优化方法信赖域方法信赖域方法 在确保算法总体收敛的情况下，作为线搜索
8、方法的替代技术。在确保算法总体收敛的情况下，作为线搜索方法的替代技术。与基于步长的方法的最大区别：与基于步长的方法的最大区别：在迭代计算过程中，步长因子在迭代计算过程中，步长因子 几乎不变几乎不变()由于步长因子基本不变，需要按照某种规则尝试不同的方向矢量，由于步长因子基本不变，需要按照某种规则尝试不同的方向矢量，以找到合适的搜索方向以找到合适的搜索方向 ，以确保在迭代过程中目标函数值，以确保在迭代过程中目标函数值F(x)有足够多的下降。有足够多的下降。kkkpxx1k1kkp10第10页，共28页。最陡下降法最陡下降法Steepest Descent Methods最陡下降法以目标函数的最陡
9、下降法以目标函数的导数负方向导数负方向为极小化方向，又称梯度法。为极小化方向，又称梯度法。迭代公式迭代公式1kkkkxxgThe method of Steepest Descent approaches the minimum in a zig-zag manner,where the new search direction is orthogonal to the previous.11第11页，共28页。最陡下降法最陡下降法Steepest Descent is Slow线搜索线搜索 line search依赖于初始搜索方向的选择依赖于初始搜索方向的选择梯度是进行搜索的方向梯度是进行搜
10、索的方向远离最小点时收敛快，最小点附近收敛慢（梯度接近远离最小点时收敛快，最小点附近收敛慢（梯度接近0）整体收敛性好整体收敛性好适用于优化的最初阶段适用于优化的最初阶段与其它方法连用与其它方法连用12第12页，共28页。共轭梯度法共轭梯度法Conjugated Gradient Methods在每一步迭代中找到合适的搜索方向在每一步迭代中找到合适的搜索方向 ，使得该方向与所有先，使得该方向与所有先前迭代步中的搜索方向前迭代步中的搜索方向 具有具有G-共轭。（其中共轭。（其中G为目标为目标函数的正定函数的正定Hessian矩阵。）矩阵。）迭代公式迭代公式kp()jpjk111,111kkkkkk
11、kkTkkk kTkkxxppgpg ggg 13第13页，共28页。共轭梯度法共轭梯度法Conjugated Gradient Methods 特点：特点：不仅运用当前的梯度，而且采用先前的最小化不仅运用当前的梯度，而且采用先前的最小化历史来确定下一步历史来确定下一步 收敛速度快。最多经过收敛速度快。最多经过n次精确线搜索即可收次精确线搜索即可收敛敛14第14页，共28页。牛顿法牛顿法Newtons Methods直接计算直接计算Hessian矩阵矩阵收敛速度快（对正定二次函数，算法是二阶收敛，迭代一次得收敛速度快（对正定二次函数，算法是二阶收敛，迭代一次得到极小点）到极小点）局部收敛局部收
12、敛不一定收敛到极小点不一定收敛到极小点 拟牛顿法拟牛顿法 Quasi-Newton Method 牛顿牛顿-拉弗森法拉弗森法 Newton-Raphson Method BUT 不适用于大体系不适用于大体系15第15页，共28页。数值最优化方法应用数值最优化方法应用 计算能量最小化计算能量最小化 选用何种方法，具体情况具体分析选用何种方法，具体情况具体分析16第16页，共28页。最优化方法最优化方法Optimization Methods 数值最优化方法 Numerical Optimization 最陡下降法 Steepest Descent 共轭梯度法 Conjugated Gradien
13、t 牛顿法 Newtons Methods 非数值最优化方法 Non-numerical Optimization 模拟退火 Simulated Annealing 遗传算法 Genetic Algorithm 神经网络 Artificial Neural Network17第17页，共28页。非数值最优化方法非数值最优化方法 Non-numerical Optimization货郎担问题货郎担问题 Traveling Salesman Problem给定n个城市和每个城市之间的距离dij。问某货郎如何选择路线，使得不重复地遍历所有城市的路线最短。计算复杂性计算复杂性时间复杂性时间复杂性/空间
14、复杂性空间复杂性货郎担问题穷举法货郎担问题穷举法 比较次数比较次数:(n-1)!/2最近邻法最近邻法 比较次数比较次数:(n-1)(n-2)/2算 法任意选择一个城市x1作为起始点。令k=1如果k=n，则算法停止根据最近邻原则，在xk以外的n-k个城市中选取一个城市xk+11.令k=k+1，转第2步18第18页，共28页。非数值最优化方法非数值最优化方法 Non-numerical Optimization局部搜索算法局部搜索算法在问题邻近解中进行迭代运算，直到某个给定目标函数的优化过程收敛至在问题邻近解中进行迭代运算，直到某个给定目标函数的优化过程收敛至不能进一步优化为止。不能进一步优化为止
15、。两个重要概念：邻域、局部最优两个重要概念：邻域、局部最优优点：优点：通用性强对于给定的组合优化问题，通过使用不同机制的解生成器，可以控制领域结构的复杂程度。局限：局限：由于多数情况下不能使用恰当的邻域结构，算法得到的最终解仅是某个解邻域内的局部最优解最终解的质量严重依赖 于初始解的选择19第19页，共28页。模拟退火模拟退火Simulated AnnealingMetropolis准则准则组合优化问题中效用函数的最小化过程与固体逐渐冷却到较低能量基态的过组合优化问题中效用函数的最小化过程与固体逐渐冷却到较低能量基态的过程相类似。程相类似。模拟退火算法的思路是使用模拟退火算法的思路是使用Met
16、ropolis准则来产生组合优化问题解准则来产生组合优化问题解的序列。的序列。初始解初始解大量解的变换给定控制参数给定控制参数t下组合优化问题的近似解下组合优化问题的近似解逐步减小t值判断接受接受/拒绝拒绝0t 得到问题的全局最优解冷却进度表冷却进度表20第20页，共28页。模拟退火模拟退火Simulated Annealing优点：优点：前期处理非常简单，对初始解没有特殊要求（随机选择）就可以得到较好的近前期处理非常简单，对初始解没有特殊要求（随机选择）就可以得到较好的近似解似解使用合适的冷却进度表，时间复杂性较低使用合适的冷却进度表，时间复杂性较低通用性强通用性强通过调整控制参数通过调整控
17、制参数t的参数值，可以在运行时间与最终解质量之间进行折的参数值，可以在运行时间与最终解质量之间进行折中。中。在取舍构象时不仅接受能量下降的变化，同时也接受部分能量上升的变化。在取舍构象时不仅接受能量下降的变化，同时也接受部分能量上升的变化。跳出局部势肼跳出局部势肼缺点：耗时缺点：耗时效率取决于参数的设置：初始温度、降温因子、随机数种子解效率取决于参数的设置：初始温度、降温因子、随机数种子解应用：应用：结合二维核磁数据确定蛋白质三维结构结合二维核磁数据确定蛋白质三维结构确定受体分子和配体分子对接的结构确定受体分子和配体分子对接的结构21第21页，共28页。遗传算法遗传算法Genetic Algo
18、rithms遗传算法是一种优化仿生算法。它吸收了达尔文的自然选择学说和孟遗传算法是一种优化仿生算法。它吸收了达尔文的自然选择学说和孟德尔的遗传变异理论中的基本思想：德尔的遗传变异理论中的基本思想：遗传变异理论遗传变异理论迭代过程中保留父代已有的模式，同时寻找更好的迭代过程中保留父代已有的模式，同时寻找更好的模式模式优胜劣汰，适者生存优胜劣汰，适者生存好的模式具有更多的机会在子代中出现好的模式具有更多的机会在子代中出现22第22页，共28页。遗传算法遗传算法Genetic Algorithms染色体编码一组相关特征；基因编码一个特征染色体编码一组相关特征；基因编码一个特征举例：染色体编码举例：染
19、色体编码Basilosaurus的身长的身长 四个基因分别编码四个基因分别编码“脚脚”和和“手指手指”理想的基因组（脚变短手指变长）是理想的基因组（脚变短手指变长）是遗传重组遗传重组种群：种群：Subject Genome Fitness P(Reproduction)A 1 1/7=0.143 B 1 1/7=0.143 C 2 2/7=0.286 D 3 3/7=0.428 Total 7 7/7=1 23第23页，共28页。遗传算法遗传算法Genetic AlgorithmsD:D:C:Subject Received genes Genome FitnessReproduction p
20、robability A A:D:2 2/10=0.2 B B:D:2 2/10=0.2 C D:C:3 3/10=0.3 D C:D:3 3/10=0.3 Total 10 10/10=1 D:+C:=24第24页，共28页。遗传算法遗传算法Genetic Algorithms主要用于全局优化主要用于全局优化具有随机性：初始种群的确立、交叉互换点的选取、变异的随具有随机性：初始种群的确立、交叉互换点的选取、变异的随机操作机操作特殊参数：种群大小、变异、互换操作的相对几率特殊参数：种群大小、变异、互换操作的相对几率应用：应用：构象搜索构象搜索QSAR(Quantitative Structur
21、e-Activity Relationships)Docking蛋白质及核酸的结构预测蛋白质及核酸的结构预测全新设计全新设计指导组合化学合成高活性化合物指导组合化学合成高活性化合物免疫系统、生态系统的进化免疫系统、生态系统的进化25第25页，共28页。神经网络神经网络Artificial Neural Network人工神经网络是模仿人脑神经网络结构和功能建立的一种信息处人工神经网络是模仿人脑神经网络结构和功能建立的一种信息处理系统。它是由数目众多的、功能相对简单的功能单元（神经元）理系统。它是由数目众多的、功能相对简单的功能单元（神经元）相互连接而成的复杂非线性网络。相互连接而成的复杂非线性
22、网络。26第26页，共28页。神经网络神经网络Artificial Neural Network优点：优点：并行性。由大量相同的简单处理单元并联组合而成，对信息的处并行性。由大量相同的简单处理单元并联组合而成，对信息的处理能力惊人理能力惊人非线性全局作用。每个神经元接受大量其他神经元的输入，并通过并非线性全局作用。每个神经元接受大量其他神经元的输入，并通过并行网络产生输出，影响其她神经元。相互制约。行网络产生输出，影响其她神经元。相互制约。容错性与联想记忆功能容错性与联想记忆功能自适应及自学习功能自适应及自学习功能应用：应用：能量计算，寻找全局极小能量计算，寻找全局极小QSAR27第27页，共28页。数值最优化方法应用数值最优化方法应用 应用于组合优化问题应用于组合优化问题 寻找分子优势构象寻找分子优势构象 定量构效关系定量构效关系 能量最小化能量最小化 28第28页，共28页。
