确定性算法

数学术语

确定性算法是利用问题的解析性质，产生一确定的有限或无限点序列使其收敛于全局最优解。这类方法依据某一确定性策略搜索局部极小，并试图跳跃已获得的局部极小而达到某个全局最优点，能充分利用问题的解析性质，从而计算效率高。如填充函数法、打洞函数法、D.C.规划算法、区间法、单调规划、分支定界方法和积分水平集方法等，这些算法的构造都涉及到已知目标函数的某些局部性质或者全局性质。其中，函数的连续性、可微性认为是局部性质，而凸性、单调性、稠密性、等度连续性、李普希兹连续、水平集等通常称为全局性的解析性质。

全局优化问题

全局优化问题的一般形式是：

其中，是可行域，是目标函数。上述问题一般称为原问题，这里记为问题(1)。根据可行域X的不同情况，问题(1)又可分为多种类型。如果X= ，则得无约束全局优化问题，记为问题(2)；如果X={ | }为一个闭箱，则得闭箱约束全局优化问题，记为问题(3)；如果X是一个多面体，则得线性约束全局优化问题。

填充函数法

填充函数是由西安交通大学的R.Ge(葛仁溥)教授首先提出的，填充函数法充分地利用了函数在可行域上的局部性质。

填充函数的定义如下：

函数p(x， )称为f(x)在局部极小点处的填充函数，如果满足：

(1) 是p(x， )的一个严格局部极大点，f(x)在点处的盆谷成为p(x， )的峰的一部分；

(2) p(x， )在比高的盆谷里没有平稳点；

(3) 如果存在比低的盆谷，则存在x'∈ 主使得p(x， )在x'和的连线上存在极小点．

由填充函数的定义可以看出，如果当前极小点不是全局极小点的话，通过极小化填充函数则可以跳出原问题当前局部极小点，并到达一个原问题函数值比当前局部极小值还要小的点。因此，从该点出发极小化原问题目标函数，必将导致一个原问题目标函数值更小的局部极小点。

填充函数算法由两个阶段组成：极小化阶段和填充阶段。这两个阶段交替使用直到找不到更好的局部极小点。在第一阶段里，可以用经典的极小化算法寻找目标函数的一个局部极小值点。然后进入第二阶段，在当前极小点处定义一个填充函数，通过极小化填充函数，找到点，使得，而后以x'为初始点，重复第一步，一直到找不到更好的局部极小点。为此葛仁溥给出了一个两个参数的填充函数函数：

填充函数的优点是较多地利用了函数的性质，所以收敛速度比较快，算法的设计和执行也相对容易；缺点是填充函数过多依赖一些未知参数，这就增加了算法设计之前的工作量，要经大量的实验，来确定参数的取值范围，以确保能找到满意的全局最优解，而且填充函数利用的是线搜索，所以对寻找低盆谷的点也有很大的难度。

打洞函数法

打洞函数法是由Levy和Montalvo在1985年首先提出的，它由一系列循环组成，每个循环包括两个阶段：局部极小化阶段和打洞阶段。

首先是极小化阶段，由一个初始点出发，应用局部极小化算法，求得f(x)的一局部极小点。其次是打洞阶段，先定义处的打洞函数：

这里是的强度，然后寻找T(x， )≤0的点，即找到，使，由x'作为初始点开始下一轮循环，必将得到一个更好的极小点。

采用适当极小化打洞函数的方法找到一个局部极小点x'，并对其进行讨论：

(1) 如果x'= ，则增大，使得x'不再是T(x， )的局部极小点。

(2) 如果x'≠ ：并且，那么构造新的打洞函数：

这里，是的强度，目的是使x'不再是T(x， )的局部极小点，防止极小化T(x， )时又得到x'，然后重新极小化T(x， )。

(3) 如果f(x')≤f( )，则由x'为初始点开始下一轮循环。

打洞函数存在下述缺陷：

(1) 极的强度与问题有关，当增大到足够大时算法才会有效，而增加，算法必须重新开始，从而增加工作量。

(2) 打洞函数可能找到另一局部极小点x'，成立f(x')≥f( )。这样对于第二个局部极小点x'，必须加上另一个极，打洞过程又要重新开始，又增加了工作量。

(3) 极的增加会引起打洞函数成为平坦，这时候极小点很难求。

D.C.规划算法

通过引入变量t，下面的D.C.规划问题：

可以转化为等价的凹极小化问题（记为问题(4)）：

显然，目标函数是凹的，可行域是一个凸集，因此，如果(x‘，t‘)是问题(4)的一个全局最优解，则x’是D.C.规划问题的一个全局最优解，且t‘=f(x‘)。

因此，对于任一D.C.规划问题都可以通过凹极小化算法求解。对于凹极小化问题，人们已经提出了一些算法，这些算法多以分枝定界技巧、割平面方法、最优性条件和整数规划等方法为基础，且它们的有效性依赖于所要解决问题的结构特点。

区间方法

区间方法考虑的是问题(2)，其基本思想是以区间分析为基础，按照区间算术运算规则用区间变量代替点变量进行区间计算，并将分支定界法和Moore-Skelboe算法等方法相结合。对这类算法，Moore首次提出区间全局优化这一概念。在这一研究领域里，所有的算法都包含精确区间计算，以及算法的执行效率依赖于目标函数、梯度和约束区间扩张的构造方法。这类方法一般分为五个基本步骤：定界、分支、终止、删除和分裂。其中包括区间分裂规则、删除规则及区间选择规则，不同的区间算法在于这几种规则的不同处理手段上。

区间方法和其他方法(即以点搜索方式产生近似点序列)相比，它的突出优点是对于低维空间中全局优化问题，能在给定精度内求出问题的全部全局极小点。特别地，对于二维空间中的单变量目标函数，建立了计算效率很高的求一元函数全局极小的区间斜率算法。缺点是当用于高维全局优化问题时，算法的计算量很大，对于区间分裂规则、删除规则及区间选择规则以及它们的检验条件的确定，难度都很大。

分支定界方法

在分支定界算法中，可行域得到松弛，并且把原区域逐次分割成越来越多的小区域，这个过程称为分支；在这些小区域内，确定目标函数的下界和上界，这个过程称为定界。在算法的某个阶段，对于在其内下界大于当前最小的上界的小区域，将其删除，这个过程称为剪支，因为这些小区域中显然不包含最优解。随着分支越来越细，最小上界的不断下降，最大下界的不断上升，当最大下界和最小上界之差趋于零，同时细分的小区域收缩为一个点时，我们可以得到目标函数的全局极小值和全局极小点。

各种分支定界算法在求解连续变量的全局最优化问题时，有如下共同的特点：

(1) 对目标函数和可行域有较高的要求，以便于分支和定界。算法的效率与分支和定界方法的效率紧密相关。

(2) 在算法实施时，需要储存越来越多的细分的小区域和目标函数在其上的下界，这使得在编程时，对数据结构的选择、计算机内存的使用提出了更高的要求。

全国各地天气预报查询

上海市

云南省

云南省

云南省