药物分子设计第二讲.ppt

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