变邻域下降算法流程图

㈠ 最优化选择法数学原理

2.2.1 目标函数

设观测异常以ΔZ_k表示，k为观测点序号，k=1，2，…，m，m为观测点数。

设所选用的地质体模型的理论异常以 Z 表示，Z 是模型体参量和观测点坐标的函数，即

Z=f（x_k，y_k，z_k，b₁，b₂，…，b_n）

式中：x_k，y_k，z_k为观测点的坐标；b₁，b₂，…，b_n为模型体的参量，如空间位置、产状、物性等，参量的个数为n。

模型体的初始参量用

，

，

，…，

表示。

理论曲线与实测曲线之间的符合程度，是以各测点上理论异常与实测异常之差的平方和（即偏差平方和）来衡量的，用φ表示，即

地球物理数据处理教程

目的在于求得一组关于模型体参量的修改量δ₁，δ₂，…，δ_n，来修改模型体给定的初值参量，即

地球物理数据处理教程

于是求出关于模型体参量的一组新值，而由这组新参量形成的模型体的理论异常与实测异常之间的偏差平方和将取极小，即是

地球物理数据处理教程

代入式（2.2.1）中将使φ值获得极小，这时b_i即为我们的解释结果，这称为最小二乘意义下的最优化选择法。

我们称φ为目标函数，用它来衡量理论曲线与实测曲线的符合程度。最优化方法的关键在于求取使φ值获得极小参量的改正值δ_i，而f通常是b_i的非线性函数，因而该问题归结为非线性函数极小的问题。

2.2.2 求非线性函数极小的迭代过程

从上已知f为b_i的非线性函数，那么要求它与实测值之间的偏差平方和φ为极小的问题就称为非线性极小问题，或称为非线性参数的估计问题。如果是线性问题，参数估计比较简单，通常进行一次计算即可求出参数的真值，而对非线性问题，参数估计却要复杂得多，为了求解，通常将函数在参数初值邻域内展成线性（忽略高次项），即所谓的线性化，然后再求得改正量δ_i（i=1，2，…，n），由于这是一种近似方法，因而不可能使φ一次达到极小，而需要一个迭代过程，通过反复计算而逐步逼近函数φ的极小值。

图2.1 不同埋深时的重力异常

为了说明这个求极小的迭代过程，可以举一个单参量的例子，即假如我们要确定引起重力异常Δg_k的场源地质体的深度，假设场源为一个已知体积和密度的球体模型，如图2.1所示，那么φ就是球心埋深z的函数，如果球心埋深的真值为h，我们首先取初值为z^（0），这时函数

地球物理数据处理教程

式中：Δg_k为实测异常；g（z）是球心埋深为z的理论重力异常；φ随z的变化情况示于图2.2 中，要求使φ获极小的z，即要求使

地球物理数据处理教程

的根。由于z^（0）和φ（z^（0））不能一次求出φ的极小来，通常采用迭代的办法，如图2.3所示，例如用牛顿切线法迭代求根，根据下式

地球物理数据处理教程

得到一个更近似于根的值z^（1），但不等于h，因此需进一步再用上式，将z^（1）作为新的初值z^（0），可得到新的z^（1）更接近于h，如此反复下去可以使z值无限接近于h，当满足精度要求时，我们认为它近似等于h了，停止迭代，这时的z^（1）就作为h值。

图2.2 函数φ（z）随z变化示意图

图2.3 用牛顿切线法求φ′（z）=0的根示意图

2.2.3 单参量非线性函数的极小问题

单参量不仅是讨论多参量的基础，而且往往在求多参量极小时要直接用到单参量极小的方法，因此有必要作一介绍。

求单参量极小的方法很多，上面用到的牛顿切线法就是其中之一，在此我们介绍一种用得较多的函数拟合法，以及精度较高的DSC-Powell方法。

2.2.3.1 函数拟合法

2.2.3.1.1 二次函数拟合法

A.不计算导数的情况

设取三个参量值x₁、x₂、x₃，它们对应的φ 值就应为φ₁、φ₂、φ₃，过三个点（x₁，φ₁；x₂，φ₂；x₃，φ₃）作二次抛物线，应有下式

地球物理数据处理教程

联立φ₁、φ₂、φ₃的方程式，即可得出系数A、B、C来。

当A＞0时，应有极小点存在，我们设极小点为d，那么根据极小的必要条件有

地球物理数据处理教程

将A、B的表达式代入即得

地球物理数据处理教程

当x₁、x₂、x₃为等距的三点时，上式可简化为

地球物理数据处理教程

B.计算导数的情况

设已知两个点的参量值x₁和x₂对应的函数值φ₁、φ₂，并已求得x₁点的一阶导数值φ′（x₁），可用下列方法求极小点d：

地球物理数据处理教程

联立φ₁、φ₂、φ′（x₁）三个方程即可得A、B、C，代入极小点的表达式即可求得极小点。

为了简化起见，不妨设x₁为坐标原点（即x₁=0），设x₂=1，于是上面各式简化成：

φ′（x₁）=B

φ₁=C

φ₂=A+B+C

A=φ₂-φ′（x₁）-φ₁

则

地球物理数据处理教程

2.2.3.1.2 三次函数拟合法

取两个点的参量值x₁和x₂，及相应的φ₁和φ₂值，并已得到该两点的一阶导数值φ′（x₁）和φ′（x₂），我们选用一个三次多项式

φ=Ax³+Bx²+Cx+D

代入上面给出的4个条件，同样，为了简化起见，不妨设x₁为坐标原点（即x₁=0），设x₂=1，则有

φ₁=D

φ₂=A+B+C+D

φ′（x₁）=C

φ′（x₂）=3A+2B+C

联立求解，可定出4个系数A、B、C、D，按照求极小的必要条件

φ′=3Ax²+2Bx+C=0

当二阶导数

φ″=6Ax+2B＞0

时有极小存在，极小点d就为

地球物理数据处理教程

为了计算方便，令

v=φ′（x₁）

u=φ′（x₂）

S=-3（φ₁-φ₂）=3（A+B+C）

Z=s-u-v=B+C

W²=Z²-vu=B²-3AC

于是极小点d就可用下列形式表示：

地球物理数据处理教程

2.2.3.2 DSC-Powell 法

该法为比较细致的单参量探测法，精度比较高，计算工作量较大，大致可分为两部分来完成，其探测（迭代）过程如图2.4所示。

2.2.3.2.1 确定极小值所在的区间

采用的是一种直接探测法，做法可归纳如下。

第一步：给定探测方向x、初值点x₀和初始步长Δx，计算φ（x₀）和φ（x₀+Δx），若φ（x₀+Δx）≤φ（x₀），转向第二步；若φ（x₀+Δx）＞φ（x₀），则取-Δx为步长Δx，转向第二步。

第二步：计算x_k+1=x_k+Δx，计算φ（x_k+1）。

第三步：如果φ（x_k+1）≤φ（x_k），以2Δx为新步长代替Δx，且用k代表k+1，转向第二步。

如果φ（x_k+1）＞φ（x_k），则以x_m表示x_k+1，以x_m-1表示x_k，将上步的x_k作为x_m-2，并计算

地球物理数据处理教程

第四步：在4个等距点（x_m-2、x_m-1、x_m+1、x_m）中，去掉四点中离φ（x）最小点最远的那一点，即或是x_m，或是x_m-2，剩下的三点按顺序以x_α、x_b、x_c表示，其中x_b为中点，那么（x_α，x_c）区间即为极小值所在的区间。

2.2.3.2.2 用二次函数拟合法求极小点

将上面已确定的等距的 x_α、x_b、x_c三点及 φ 值，用二次函数拟合法即用公式（2.2.3）求得极小点，令为x^*点。再将x_α、x_b、x_c、x^*四点中舍去φ值最大的点，剩下的点重新令为α、b、c，则又得三点和它们相应的φ值，用公式（2.2.2）求其极小点x^*，如此反复使用公式（2.2.2），逐步缩小极小值的区间，一直到两次求得的极小点位置差小于事先给定的精度为止，x^*点即为极小点。

图2.4 DSC-Powell法示意图

2.2.4 广义最小二乘法（Gauss 法）

重磁反问题中的最优化方法，一般是指多参量的非线性最优估计问题，理论模型异常z=f（

，b₁，b₂，…，b_n）是参数b_i（i=1，2，3，…，n）的非线性函数，其中

=（x，y，z）为测点的坐标。由前已知ΔZ_k（k=1，2，…，m）表示在第k个观测点

上的实测异常，现在要寻求与观测异常相对应的理论模型的参量值b_i（i=1，2，…，n），使理论异常与实测异常的偏差平方和

地球物理数据处理教程

为极小。

设b_i的初值为

，则上述问题，即是要求修正量δ_i，使

地球物理数据处理教程

代入φ中，使φ获得极小。

高斯提出了首先将f函数线性化的近似迭代方法，即将f在

处按台劳级数展开取其线性项。

地球物理数据处理教程

式中

，

地球物理数据处理教程

当

和

给出后，

和

均可直接计算出来。将台劳展开式代入式（2.2.6）中，目标函数φ为

地球物理数据处理教程

要求

使φ取得极小，根据极小的必要条件

地球物理数据处理教程

将上式化为

地球物理数据处理教程

写成方程组形式

地球物理数据处理教程

式中：

，

（i，j=1，2，…，n）

再写成矩阵形式，有

地球物理数据处理教程

即

地球物理数据处理教程

其中

A=P^TP

地球物理数据处理教程

式中：P称为雅可比（Jacobi）矩阵，是理论模型函数对参量的一阶导数矩阵。A为正定对称矩阵，实际计算时，当实测异常值已给出，模型体的初值

已选定后，A和

即可计算出，求解方程（2.2.7）即可求出

，从而可得

。

上面推导出的方程（2.2.7）是将f线性化所得，因而只有当f为真正的线性函数时，

才是真正的极小点

，即一步到达极小；当f为非线性函数时，台劳式线性化仅为近似式，近似程序视

的大小而定，当|δ_i|较大时，二次以上项忽略的误差就大，反之就小，所以对于非线性函数

不能简单地作为极小点

，一般将

作为新的初值

再重复上述做法，再解方程（2.2.7）又得到新的

，反复迭代下去，直到满足精度要求为止（例如|δ_i|小到允许误差）。

在高斯法应用中常常出现一种困难，即迭代过程不稳定，当

过大时，台劳展开的高次项太大而不能忽略时，就可能发生这样的情况，即用方程（2.2.7）求得的解，得到的参量

所对应的φ值大于

所对应的φ值，那么它将不能稳定地收敛于φ的极小值，即是出现了发散的情况，一般说来当f非线性程度越明显时，越易出现发散的情况。

因此高斯法的一种改进形式如下，即不直接把

作为校正值，而将它作为校正方向，记为

，而在该方向上用单变量求极小的方法寻找在这个方向上的极小点，即寻找一个α，使目标函数φ（

）为极小，取

作为新的初值，再继续迭代（0＜α＜1）。

把这个改进的方法称为广义最小二乘法，它使迭代过程的稳定性有所改善，即使这样当初值取得不好时，也有可能出现不收敛。

2.2.5 最速下降法

从前述已知，我们的目的是要求目标函数的极小，高斯法是利用将f函数线性化，建立一个正规方程（2.2.7）来求取修正量的，最速下降法是另一类型方法，它直接寻找φ函数的下降方向来求取修正量，所以它又称为直接法，而高斯法又称为间接法。

从目标函数φ出发来寻找其下降方向

地球物理数据处理教程

始终是大于或等于0，因此它一定有极小存在，我们首先考虑初值点

的一个邻域内，将φ在

处台劳展开取至线性项，有

地球物理数据处理教程

希望寻找使Φ下降的方向，即要找新点

，使φ（

）＜φ（

）

即要求φ（

）-φ（

）＞0，

且越大越好，那么可得

地球物理数据处理教程

地球物理数据处理教程

式中

表示φ函数对

的各分量的导数所组成的向量，即梯度向量。

要使上式取极大，有

地球物理数据处理教程

上式说明了φ值下降最快的方向

，应该是与梯度方向

相反的方向，即负梯度方向，那么修正量就应在负梯度方向上来求取。下面讨论从

出发，沿负梯度方向上求取极小点的方法，除了用前面介绍过的方法外，在此再介绍一种近似计算方法。

要求从

出发，沿-

方向的极小点，即要求λ使φ

为-

方向上极小点。根据极小必要条件，有

地球物理数据处理教程

如果φ为二次函数时，λ可以直接解出，在重磁反问题中φ为非二次函数，且函数形式较复杂，一般无法直接解出λ，而采用近似法，先将φ（

）台劳展开，取至线性项，即

地球物理数据处理教程

假设粗略认为φ的极小值为零，则极小点的λ应有

地球物理数据处理教程

这个方法计算简单，但误差较大，特别是

远离真正极小点

时，φ值较大，上式的假设不适合，当接近真极小点

附近时，可以采用。但在重磁反问题中，由于实测值Z_k中含有干扰成分，所以即使到了

附近，φ值仍不会为零，因而上述计算λ的方法不能直接采用，可将上述计算的λ作为一个区间估计值，再用其他方法计算［0，λ］之间真正的λ值。

从上所述可将最速下降法叙述如下：从初值

出发，沿着φ（

）的负梯度方向-

（

）寻找极小点

，然后又从

出发，沿着φ（

）的负梯度方向-

（

）寻找极小点

，一直迭代下去，直到找到

为止。

由于这个方法是沿着初值点的最快下降方向，在该方向上如果采用单方向求极小的方法得到该方向上的极小点，那么又称“最优”、“最速”下降法。但需要指出的是，所谓“最速”是就初值点的邻域而言，所谓“最优”是指在初值点的负梯度方向上，所以它的着眼点是就局部而言，就初值点邻域而言，而对整体往往是既非“最优”，又非“最速”，而是一条曲折的弯路，难怪有人称它为“瞎子下山法”，如图2.5所示，当φ的等值面为拉长的椭球时更是如此。但它有一个十分可贵的优点，即在迭代的每一步都保证φ值下降，所以它是稳定收敛的，在φ函数复杂时，计算工作量较大些，对于大型计算机比较适用。

图2.5 最速下降法迭代过程示意图

图2.6 修正量的方向

2.2.6 阻尼最小二乘法（Marguardt）

比较上述两种方法可知，Gauss法修正量的步长大，当φ近于二次函数，可以很快收敛，但当φ为非二次函数，初值又给得不好时，常常引起发散。而最速下降法却能保证稳定的收敛，但修正量的步长小，计算工作量大。当φ的等值面为拉长的椭球时，Gauss法的修正量

和最速下降法的修正量

之间的夹角γ可达80°～90°，如图2.6所示。

对于φ为二次函数的情况下，高斯法的修正量

方向是指向φ的极小点，而最速下降法修正量

的方向是垂直于通过

点的φ函数等值面的切平面。因而当φ为比较复杂的函数时，有可能使

出现发散而失败。

阻尼最小二乘法是在Gauss法和最速下降法之间取某种插值，它力图能以最大步长前进，同时又能紧靠负梯度方向，这样既能保证收敛又能加快速度。它的基本思想是：在迭代过程的每一步，最好尽量使用Gauss法修正量方向

，以使修正步长尽可能地增大，如当这种情况下不能收敛时，再逐步改用接近最速下降的方向

，同时缩小步长，以保证收敛，下面以

表示由阻尼最小二乘法得出的修正量。

实现上述思想只要将方程

地球物理数据处理教程

改变为

地球物理数据处理教程

就能实现了。式中

为我们所要求的修正量，即称Marguardt修正向量，I为单位矩阵，λ是用来控制修正方向和步长的任意正数，又称阻尼因子，它起到阻止发散的作用，方程（2.2.9）中

显然是λ的函数，即

地球物理数据处理教程

通过这一改变后，即原来的正规方程（2.2.7）系数矩阵的主对角线上加一正数，从而使条件数得到了改善。如果原来A是奇异的，而A+λI可成为正定的，设原来A的最大特征值和最小特征值为μ_max和μ_min，则条件数就发生了如下变化：

地球物理数据处理教程

使病态条件数改善，对于计算来说，是十分有利的。

从方程（2.2.7）可看出，右端项为

地球物理数据处理教程

而φ的负梯度向量

的第i个分量

地球物理数据处理教程

所以

，即方程（2.2.7）、（2.2.9）的右端项

的方向即为负梯度方向，值为负梯度值的一半。

在方程（2.2.9）中，当λ=0时，即是（2.2.7）方程，这时

就是

；当λ→∞时，δ₀→

，而

是负梯度方向，这时

就是最速下降方向，所以阻尼最小二乘法的修正量

，是最速下降修正量

和Gauss法修正量

之间的某种插值，λ就是这种插值的权系数。

Marguardt向量

具有以下三个特性：

（1）当λ越来越大时，

的长度越来越小，且

地球物理数据处理教程

‖

‖表示

向量的范数，也即是它的长度。

（2）当λ由零逐渐增大时，

的方向逐渐由Gauss法的方向

转向最速下降法方向

，λ越大，

方向越接近

方向。

（3）对λ＞0的任意正数，

（满足方程（2.2.9））使φ在半径为‖

‖的球面上取得极小。

图2.7Δ₀（λ）随λ的变化情况示意图

以上三个性质说明，当λ逐渐增大时，

的方向由

向

靠近，它的大小‖

‖逐渐减小，λ→∞时，‖

‖→0，如图2.7所示。因此在迭代的任何一步，我们总可以找到充分大的λ，来保证稳定的收敛，因为当φ 不下降时，就加大λ向

靠，一直到使φ下降为止，从而保证收敛。性质（3）说明在跨出同样的步长时，以

（λ）方向最好，这就保证了该法的优越性。在实际计算时，总是在保证收敛的前提下，取较小的λ，以获得较大的步长前进。

下面介绍阻尼最小二乘法的迭代步骤，即实际计算过程。

（1）给出模型体参量初值

，计算φ（

）；给出实测场值ΔZ_k（k=1，2，…，m）；给出阻尼因子的初值λ^（0）及改变λ的比例系数v。

（2）开始迭代，λ=λ^（0）/v

（3）计算A，（A+λI）及右端项

在初值点

的值，得方程（2.2.9），（A+λI）

的系数矩阵及右端项。

（4）求解方程（2.2.9）得

。

（5）计算

及φ（

）。

（6）比较φ（

）和φ（

）。

若φ（

）＜φ（

），则该次迭代成功。判断

是否满足精度要求，若满足停止迭代，这时的

即为极小点

；若不满足精度要求，则将

作为新

，φ（

）作为新φ（

），减小λ作为新的λ^（0），转向第（2）步，继续迭代下去。

若φ（

）＞φ（

），则该次迭代失败，增大阻尼因子λ，将λ·v作为新的λ，转向第（4）步，即重新求解（A+λI）

方程，重新得到新的

。

该方法中阻尼因子λ的选择十分重要，上述选法是一种简单可行的方法，还有很多不同的选择方法，可参阅有关的书籍。

㈡ 非线性规划的深入解析

例1（投资决策问题）某企业有n个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A元，投资于第i个项目需花资金ai元，并预计可收益bi元。试选择最佳投资方案。
解:设投资决策变量为

则投资总额为∑aixi，投资总收益为∑bixi。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金 ，故有限制条件

另外，由于 xi只取值0或1，所以还有

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）。可概括为一般形式

（NP)
其中x=[x1 ... xn]称为模型（NP）的决策变量，f称为目标函数，gi和hj 称为约束函数。另外，gi(x)=0称为等式约束，hj(x)<=0称为不等式约束。 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：
（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。
（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。
（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。
（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般数学模型可表述为求未知量x1，x2，…，xn，使满足约束条件：
gi(x1，…，xn）≥0i=1，…，m
hj(x1，…，xn)=0j=1，…，p
并使目标函数f(x1，…，xn）达到最小值（或最大值）。其中f，诸gi和诸hj都是定义在n维向量空间Rn的某子集D（定义域）上的实值函数，且至少有一个是非线性函数。
上述模型可简记为：
min f(x)
s.t. gi(x）≥0i=1，…，m
hj(x)=0 j=1，…，p
其中x=(x1，…，xn）属于定义域D，符号min表示“求最小值”，符号s.t.表示“受约束于”。
定义域D 中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*，如果存在x*的一个邻域，使目标函数在x*处的值f(x*）优于 （指不大于或不小于）该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果f(x*）优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。 指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。
①黄金分割法又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。
②切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。
③插值法又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。
此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。 指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。
无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：①梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。②牛顿法：收敛速度快，但不稳定，计算也较困难。③共轭梯度法：收敛较快，效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。 这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸gi都是凹函数，诸hj都是一次函数，则称之为凸规划。所谓f是凸函数，是指f有如下性质：它的定义域是凸集，且对于定义域中任意两点x和y及任一小于1的正数α，下式都成立：
f(（1-α）x +αy）α≤（1-α）f(x)+αf(y)
将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。
对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。 几何规划一类特殊的非线性规划。它的目标函数和约束函数都是正定多项式（或称正项式）。几何规划本身一般不是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上。

㈢ 数字图像中最近邻域法是什么意思

顾名思义，邻域就是相邻的区域。
比如你家邻域就是你们楼上楼下左邻右舍。
由于像素是离散的，邻域也就有了具体的区域。
有八邻域，有四邻域，也有更多的区域，16,32的有的是。
[1
2
3;
4
x
5;
6
7
8]
1-8是八邻域，2
4
7是4邻域。
不同邻域反应像素周边信息，看你用到什么，选取不同邻域进行处理。

㈣ 图像增强和复原的原理是什么

图像增强的方法可分成两大类：频率域法和空间域法。
前者把图像看成一种二维信号，对其进行基于二维傅里叶变换的信号增强。采用低通滤波（即只让低频信号通过）法，可去掉图中的噪声；采用高通滤波法，则可增强边缘等高频信号，使模糊的图片变得清晰。

后者空间域法中具有代表性的算法有局部求平均值法和中值滤波（取局部邻域中的中间像素值）法等，它们可用于去除或减弱噪声。

㈤ 遗传算法的运算过程

遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。
遗传操作包括以下三个基本遗传算子(genetic operator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点：
个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。
遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子(reproction operator)。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。
其中轮盘赌选择法 （roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为遗传算法
显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。 在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：
a)实值重组（real valued recombination）
1)离散重组（discrete recombination）
2)中间重组（intermediate recombination）
3)线性重组（linear recombination）
4)扩展线性重组（extended linear recombination）。
b)二进制交叉（binary valued crossover）
1)单点交叉（single-point crossover）
2)多点交叉（multiple-point crossover）
3)均匀交叉（uniform crossover）
4)洗牌交叉（shuffle crossover）
5)缩小代理交叉（crossover with reced surrogate）。
最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：
个体A：1 0 0 1 ↑1 1 1 → 1 0 0 1 0 0 0 新个体
个体B：0 0 1 1 ↑0 0 0 → 0 0 1 1 1 1 1 新个体 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：
a)实值变异
b)二进制变异。
一般来说，变异算子操作的基本步骤如下：
a)对群中所有个体以事先设定的变异概率判断是否进行变异
b)对进行变异的个体随机选择变异位进行变异。
遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。
基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下：
基因位下方标有*号的基因发生变异。
变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小的值，一般取0.001－0.1。 当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

㈥ 各位大侠，请问什么是杂交算法啊是神经网络与遗传算法的结合谢谢

杂交？你指的是混合吗？神经网络与遗传算法相混合的例子很多，还有其他智能算法相混合的，比如说遗传算法和模拟退火算法，变邻域搜索算法和禁忌搜索算法的混合等。
如果你说的是遗传算法中的杂交，那么杂交算法应该指的就是遗传算法。

㈦ 求救，论文高手请不吝赐教

模拟退火是一种优化算法，它本身是不能独立存在的，需要有一个应用场合，其中温度就是模拟退火需要优化的参数，如果它应用到了聚类分析中，那么就是说聚类分析中有某个或者某几个参数需要优化，而这个参数，或者参数集就是温度所代表的。它可以是某项指标，某项关联度，某个距离等等

Simulate Anneal Arithmetic (SAA,模拟退火算法)
模拟退火算法
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schele)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
1 . 模拟退火算法的模型
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想:
(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L
(2) 对k=1，……，L做第(3)至第6步：
(3) 产生新解S′
(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少，且T->0，然后转第2步。
算法对应动态演示图：
模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
2 模拟退火算法的简单应用
作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j) i, j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。
求解TSP的模拟退火算法模型可描述如下：
解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2 ,……，wn)，并记wn+1= w1。初始解可选为(1，……，n)
目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数：
我们要求此代价函数的最小值。
新解的产生 随机产生1和n之间的两相异数k和m，若k (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
变为：
(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).
如果是k>m，则将
(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)
变为：
(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).
上述变换方法可简单说成是“逆转中间或者逆转两端”。
也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为：
根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procere TSPSA:
begin
init-of-T; { T为初始温度}
S={1，……，n}; {S为初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 从当前回路S产生新回路S′}
Δt:=f(S′))-f(S);{f(S)为路径总长}
IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′;
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheling Problem)等等。
3 模拟退火算法的参数控制问题
模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
(1) 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
(2) 退火速度问题。
模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
(3) 温度管理问题。
温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
T(t+1)＝k×T(t)
式中k为正的略小于1.00的常数，t为降温的次数

㈧ hadoop的maprece常见算法案例有几种

基本MapRece模式

计数与求和
问题陈述:
有许多文档，每个文档都有一些字段组成。需要计算出每个字段在所有文档中的出现次数或者这些字段的其他什么统计值。例如，给定一个log文件，其中的每条记录都包含一个响应时间，需要计算出平均响应时间。
解决方案:
让我们先从简单的例子入手。在下面的代码片段里，Mapper每遇到指定词就把频次记1，Recer一个个遍历这些词的集合然后把他们的频次加和。

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Recer
7 method Rece(term t, counts [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)

这种方法的缺点显而易见，Mapper提交了太多无意义的计数。它完全可以通过先对每个文档中的词进行计数从而减少传递给Recer的数据量:

1 class Mapper
2 method Map(docid id, doc d)
3 H = new AssociativeArray
4 for all term t in doc d do
5 H{t} = H{t} + 1
6 for all term t in H do
7 Emit(term t, count H{t})

如果要累计计数的的不只是单个文档中的内容，还包括了一个Mapper节点处理的所有文档，那就要用到Combiner了:

1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Combiner
7 method Combine(term t, [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
12
13 class Recer
14 method Rece(term t, counts [c1, c2,...])
15 sum = 0
16 for all count c in [c1, c2,...] do
17 sum = sum + c
18 Emit(term t, count sum)

应用：Log 分析, 数据查询

整理归类

问题陈述:
有一系列条目，每个条目都有几个属性，要把具有同一属性值的条目都保存在一个文件里，或者把条目按照属性值分组。 最典型的应用是倒排索引。
解决方案：
解决方案很简单。 在 Mapper 中以每个条目的所需属性值作为 key，其本身作为值传递给 Recer。 Recer 取得按照属性值分组的条目，然后可以处理或者保存。如果是在构建倒排索引，那么 每个条目相当于一个词而属性值就是词所在的文档ID。
应用：倒排索引， ETL
过滤 (文本查找)，解析和校验
问题陈述:
假设有很多条记录，需要从其中找出满足某个条件的所有记录，或者将每条记录传换成另外一种形式（转换操作相对于各条记录独立，即对一条记录的操作与其他记录无关）。像文本解析、特定值抽取、格式转换等都属于后一种用例。
解决方案:
非常简单，在Mapper 里逐条进行操作，输出需要的值或转换后的形式。
应用：日志分析，数据查询，ETL，数据校验

分布式任务执行

问题陈述:
大型计算可以分解为多个部分分别进行然后合并各个计算的结果以获得最终结果。
解决方案: 将数据切分成多份作为每个 Mapper 的输入，每个Mapper处理一份数据，执行同样的运算，产生结果，Recer把多个Mapper的结果组合成一个。
案例研究： 数字通信系统模拟
像 WiMAX 这样的数字通信模拟软件通过系统模型来传输大量的随机数据，然后计算传输中的错误几率。 每个 Mapper 处理样本 1/N 的数据，计算出这部分数据的错误率，然后在 Recer 里计算平均错误率。
应用：工程模拟，数字分析，性能测试
排序
问题陈述:
有许多条记录，需要按照某种规则将所有记录排序或是按照顺序来处理记录。
解决方案: 简单排序很好办 – Mappers 将待排序的属性值为键，整条记录为值输出。 不过实际应用中的排序要更加巧妙一点， 这就是它之所以被称为MapRece 核心的原因（“核心”是说排序？因为证明Hadoop计算能力的实验是大数据排序？还是说Hadoop的处理过程中对key排序的环节？）。在实践中，常用组合键来实现二次排序和分组。
MapRece 最初只能够对键排序， 但是也有技术利用可以利用Hadoop 的特性来实现按值排序。想了解的话可以看这篇博客。
按照BigTable的概念，使用 MapRece来对最初数据而非中间数据排序，也即保持数据的有序状态更有好处，必须注意这一点。换句话说，在数据插入时排序一次要比在每次查询数据的时候排序更高效。
应用：ETL，数据分析

非基本 MapRece 模式

迭代消息传递 (图处理)

问题陈述：
假设一个实体网络，实体之间存在着关系。 需要按照与它比邻的其他实体的属性计算出一个状态。这个状态可以表现为它和其它节点之间的距离， 存在特定属性的邻接点的迹象， 邻域密度特征等等。
解决方案：
网络存储为系列节点的结合，每个节点包含有其所有邻接点ID的列表。按照这个概念，MapRece 迭代进行，每次迭代中每个节点都发消息给它的邻接点。邻接点根据接收到的信息更新自己的状态。当满足了某些条件的时候迭代停止，如达到了最大迭代次数（网络半径）或两次连续的迭代几乎没有状态改变。从技术上来看，Mapper 以每个邻接点的ID为键发出信息，所有的信息都会按照接受节点分组，recer 就能够重算各节点的状态然后更新那些状态改变了的节点。下面展示了这个算法：

1 class Mapper
2 method Map(id n, object N)
3 Emit(id n, object N)
4 for all id m in N.OutgoingRelations do
5 Emit(id m, message getMessage(N))
6
7 class Recer
8 method Rece(id m, [s1, s2,...])
9 M = null
10 messages = []
11 for all s in [s1, s2,...] do
12 if IsObject(s) then
13 M = s
14 else // s is a message
15 messages.add(s)
16 M.State = calculateState(messages)
17 Emit(id m, item M)

一个节点的状态可以迅速的沿着网络传全网，那些被感染了的节点又去感染它们的邻居，整个过程就像下面的图示一样：

案例研究： 沿分类树的有效性传递
问题陈述：
这个问题来自于真实的电子商务应用。将各种货物分类，这些类别可以组成一个树形结构，比较大的分类（像男人、女人、儿童）可以再分出小分类（像男裤或女装），直到不能再分为止（像男式蓝色牛仔裤）。这些不能再分的基层类别可以是有效（这个类别包含有货品）或者已无效的（没有属于这个分类的货品）。如果一个分类至少含有一个有效的子分类那么认为这个分类也是有效的。我们需要在已知一些基层分类有效的情况下找出分类树上所有有效的分类。
解决方案：
这个问题可以用上一节提到的框架来解决。我们咋下面定义了名为 getMessage和 calculateState 的方法：

1 class N
2 State in {True = 2, False = 1, null = 0},
3 initialized 1 or 2 for end-of-line categories, 0 otherwise
4 method getMessage(object N)
5 return N.State
6 method calculateState(state s, data [d1, d2,...])
7 return max( [d1, d2,...] )

案例研究：广度优先搜索
问题陈述：需要计算出一个图结构中某一个节点到其它所有节点的距离。
解决方案： Source源节点给所有邻接点发出值为0的信号，邻接点把收到的信号再转发给自己的邻接点，每转发一次就对信号值加1：

1 class N
2 State is distance,
3 initialized 0 for source node, INFINITY for all other nodes
4 method getMessage(N)
5 return N.State + 1
6 method calculateState(state s, data [d1, d2,...])
7 min( [d1, d2,...] )

案例研究：网页排名和 Mapper 端数据聚合
这个算法由Google提出，使用权威的PageRank算法，通过连接到一个网页的其他网页来计算网页的相关性。真实算法是相当复杂的，但是核心思想是权重可以传播，也即通过一个节点的各联接节点的权重的均值来计算节点自身的权重。

1 class N
2 State is PageRank
3 method getMessage(object N)
4 return N.State / N.OutgoingRelations.size()
5 method calculateState(state s, data [d1, d2,...])
6 return ( sum([d1, d2,...]) )

要指出的是上面用一个数值来作为评分实际上是一种简化，在实际情况下，我们需要在Mapper端来进行聚合计算得出这个值。下面的代码片段展示了这个改变后的逻辑 （针对于 PageRank 算法）：

1 class Mapper
2 method Initialize
3 H = new AssociativeArray
4 method Map(id n, object N)
5 p = N.PageRank / N.OutgoingRelations.size()
6 Emit(id n, object N)
7 for all id m in N.OutgoingRelations do
8 H{m} = H{m} + p
9 method Close
10 for all id n in H do
11 Emit(id n, value H{n})
12
13 class Recer
14 method Rece(id m, [s1, s2,...])
15 M = null
16 p = 0
17 for all s in [s1, s2,...] do
18 if IsObject(s) then
19 M = s
20 else
21 p = p + s
22 M.PageRank = p
23 Emit(id m, item M)

应用：图分析，网页索引

值去重 （对唯一项计数）
问题陈述: 记录包含值域F和值域 G，要分别统计相同G值的记录中不同的F值的数目 (相当于按照 G分组).
这个问题可以推而广之应用于分面搜索（某些电子商务网站称之为Narrow Search）
Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}

Result:
a -> 3 // F=1, F=2, F=3
b -> 2 // F=1, F=3
d -> 1 // F=2
e -> 1 // F=2

解决方案 I:
第一种方法是分两个阶段来解决这个问题。第一阶段在Mapper中使用F和G组成一个复合值对，然后在Recer中输出每个值对，目的是为了保证F值的唯一性。在第二阶段，再将值对按照G值来分组计算每组中的条目数。
第一阶段：

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...]])
3 for all category g in [g1, g2,...]
4 Emit(record [g, f], count 1)
5
6 class Recer
7 method Rece(record [g, f], counts [n1, n2, ...])
8 Emit(record [g, f], null )

第二阶段：

1 class Mapper
2 method Map(record [f, g], null)
3 Emit(value g, count 1)
4
5 class Recer
6 method Rece(value g, counts [n1, n2,...])
7 Emit(value g, sum( [n1, n2,...] ) )

解决方案 II:
第二种方法只需要一次MapRece 即可实现，但扩展性不强。算法很简单-Mapper 输出值和分类，在Recer里为每个值对应的分类去重然后给每个所属的分类计数加1，最后再在Recer结束后将所有计数加和。这种方法适用于只有有限个分类，而且拥有相同F值的记录不是很多的情况。例如网络日志处理和用户分类，用户的总数很多，但是每个用户的事件是有限的，以此分类得到的类别也是有限的。值得一提的是在这种模式下可以在数据传输到Recer之前使用Combiner来去除分类的重复值。

1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...] )
3 for all category g in [g1, g2,...]
4 Emit(value f, category g)
5
6 class Recer
7 method Initialize
8 H = new AssociativeArray : category -> count
9 method Rece(value f, categories [g1, g2,...])
10 [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
11 for all category g in [g1', g2',...]
12 H{g} = H{g} + 1
13 method Close
14 for all category g in H do
15 Emit(category g, count H{g})

应用：日志分析，用户计数
互相关
问题陈述：有多个各由若干项构成的组，计算项两两共同出现于一个组中的次数。假如项数是N，那么应该计算N*N。
这种情况常见于文本分析（条目是单词而元组是句子），市场分析（购买了此物的客户还可能购买什么）。如果N*N小到可以容纳于一台机器的内存，实现起来就比较简单了。
配对法
第一种方法是在Mapper中给所有条目配对，然后在Recer中将同一条目对的计数加和。但这种做法也有缺点：
使用 combiners 带来的的好处有限，因为很可能所有项对都是唯一的
不能有效利用内存

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 for all item j in [i1, i2,...]
5 Emit(pair [i j], count 1)
6
7 class Recer
8 method Rece(pair [i j], counts [c1, c2,...])
9 s = sum([c1, c2,...])
10 Emit(pair[i j], count s)

Stripes Approach（条方法？不知道这个名字怎么理解）
第二种方法是将数据按照pair中的第一项来分组，并维护一个关联数组，数组中存储的是所有关联项的计数。The second approach is to group data by the first item in pair and maintain an associative array (“stripe”) where counters for all adjacent items are accumulated. Recer receives all stripes for leading item i, merges them, and emits the same result as in the Pairs approach.
中间结果的键数量相对较少，因此减少了排序消耗。
可以有效利用 combiners。
可在内存中执行，不过如果没有正确执行的话也会带来问题。
实现起来比较复杂。
一般来说， “stripes” 比 “pairs” 更快

1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 H = new AssociativeArray : item -> counter
5 for all item j in [i1, i2,...]
6 H{j} = H{j} + 1
7 Emit(item i, stripe H)
8
9 class Recer
10 method Rece(item i, stripes [H1, H2,...])
11 H = new AssociativeArray : item -> counter
12 H = merge-sum( [H1, H2,...] )
13 for all item j in H.keys()
14 Emit(pair [i j], H{j})

应用：文本分析，市场分析
参考资料：Lin J. Dyer C. Hirst G. Data Intensive Processing MapRece
用MapRece 表达关系模式
在这部分我们会讨论一下怎么使用MapRece来进行主要的关系操作。
筛选（Selection）

1 class Mapper
2 method Map(rowkey key, tuple t)
3 if t satisfies the predicate
4 Emit(tuple t, null)

投影（Projection）
投影只比筛选稍微复杂一点，在这种情况下我们可以用Recer来消除可能的重复值。

1 class Mapper
2 method Map(rowkey key, tuple t)
3 tuple g = project(t) // extract required fields to tuple g
4 Emit(tuple g, null)
5
6 class Recer

㈨ 邻域的定义是唯一的吗邻域的定义与搜索效率及结 果有关联吗简要说明你的结

不是。有关联。
邻域：邻域是指集合上的一种基础的拓扑结构。在集合论中，它是以点a为中心的任何开区间，记作：U(a)。在拓扑学和相关的数学领域中，邻域是拓扑空间中的基本概念。有邻域公理（邻域公理是现代数学拓扑结构的基础概念）、开邻域和闭邻域、去心邻域等相关研究的着作。
广义邻域搜索算法的统一结构：
1.对优化过程作两方面分解处理：方面1、基于优化空间的分层（原问题分解为子问题求解，最后将各子问题的解逆向综合为原问题的解）方面2、基于优化进程的分层（进程层次分为若干阶段，各阶段采用不同的搜索算法或邻域函数进行优化）目前混合算法的结构类型主要可归纳为串行、镶嵌、并行及混合结构。
串行结构。
镶嵌结构。
并行结构（又分为同步式并行、异步式并行、网络结构）。
同步式：各子算法相对独立但与主过程的通讯必须同步。
异步式：子算法与主过程的通讯不受其他子算法的限制。
网络结构：各算法分别在独立的存储器上执行独立的搜索，算法间的通信是通过网络相互传递的。