全局搜索算法type
status
date
slug
summary
tags
category
icon
password
Property
前面讨论的一些迭代算法，包括梯度方法、牛顿法、共辄梯度法和拟牛顿法等，能够从初始点出发，产生一个迭代序列。在很多时候，这一迭代序列往往只能收敛到局部极小点。因此，为了保证算法能够收敛到全局极小点，有时需要在全局极小点附近选择初始点。此外，这些方法需要计算目标函数的一阶导数(牛顿法还需要计算二阶导数)。
这里讨论一些全局意义上的搜索方法，它们能够在整个可行集中开展搜索，以找到极小点。这些方法只需要计算目标函数值，不需要对目标函数求导。因此，它们的适用面更为广阔。在某些情况下，这些方法产生的解，可以作为如梯度方法、牛顿法等迭代方法的"较好"的初始点。某些方法(具体而言，就是随机搜索方法)还可用于求解组合优化问题。在组合优化问题中，可行集是有限的(离散的) ，但通常会非常大。
Nelder-Mead 单纯形法
该方法是由Spendley, Hext and Himsworth 于1962年提出的，Nelder and Mead 在 1965 年对其进行了完善，现在通常称为 Nelder-Mead 单纯形法。
Nelder-Mead 单纯形法引入了单纯形的概念，不需要计算目标函数的梯度。所谓单纯形，指的是由维空间中的 个点 构成的几何形状，且满足
这一条件的含义为：中的两个点不重合， 中的三个点不共线， 中的四个点不共面，以此类推。因此， 中单纯形是一条线段， 的单纯形是一个三角形， 的单纯形是一 个四面体。这说明，单纯形包围的维空间具有有限的体积。
针对函数 的最小化问题，首先选择 个点，使其构成一个初始单纯形。Jang, Sun and Mizutani 提出了一种构造单纯形的方式 。具体方式为选定初始点，按照下式产生其他点：
其中, 表示一组单位向量，是空间 的标准基；系数为正数，可以按照优化问题的规模确定其大小。按照这种方式产生的 个点，正好能够构成一个单纯形。初始单纯形确定之后，接下来就是一步步对其进行修改，使得 产生的单纯形能够朝着函数极小点收敛。在每次迭代中，都要针对单纯形的每个点计算目标函数值。对于函数 最小化的优化问题而言，目标函数值最大的点将被另外的点代替。 持续开展这一迭代过程，直到单纯形收玫到目标函数的极小点。
如果针对 维问题，首先选定初始的 个点，构造初始单纯形；然后，针对每个点计算目标函数值，并对单纯形的这个顶点按照目标函数值由小到大的顺序进行排序：
具体到二维问题，则令 和 表示单纯形的顶点，分别表示函数值最大、次大和最小的点。从求解函数 极小点的意义上来看，顶点 是最好的， 是最差的， 是次差的。按照如下方式计算最好的个点 (只扣除最差的点) 的重心 :
对于二维 问题，最好点和次好点的重心为
接下来开展反射操作，利用反射系数 在 方向上对最差点 进行反射，得到反射点 :
反射系数一般取 ，反射过程如图所示。
计算 下的目标函数值 ，如果 [ 即 位于 和 之间 ]，那么用反射点 代替 ，构成一个新的单纯形, 完成本次反射操作，判断是否得到极小点，以此决定是否开展新的迭代。如果开展新的迭代，则计算新的单纯形中最好点和次好点的重心 (对于 维问题，则是去除最差点后 个点的重心)，做好下一次迭代的准备工作。
接下来，如果 ，也就是说， 对应的目标函数值比单纯形所有顶点对应的目标函数值都要小。这意味着的方向是有利于函数值下降的方向。在这种情况下，需要 在这个方向进行延伸操作，得到延伸点 :
(可取 ) 表示延伸系数。延伸点 位于直线 上，超过了 ，如图所示。
计算 对应的目标函数值 ，如果 ，说明延伸操作是成功的，利用 取代 ，构造新的单纯形；否则，如果 ，说明延伸操作失败，利用 代替 。
最后，如果 ，利用反射点 代替最差点 构造新单纯形，那么可知反射点 是新单纯形中的最差点。此时在 方向上开展反射操作可能是毫无意义的。在这种情况下， 需要分情况开展两种不同类型的收缩操作。首先，如果 且 , 那么采用下式对 进行收缩，得到收缩点 :
其中, (可取 0.5) 为收缩系数。这种收缩称为外收缩，如图所示。其次，如果 且 , 那么利用 代替 , 完成收缩操作, 得到收缩点 :
这种收缩称为内收缩, 如图所示。
计算收缩点 对应的目标函数值 , 无论开展的是何种类型的收缩操作, 如果 , 说明收缩操作成功, 利用 代替 , 构造新的单纯形。但是, 如果 , 说明收缩操作失败, 此时应按照如下方式构造新的单纯形: 只保留 , 单纯形中的其他各点与 的距离减半, 由此产生新的点, 构造新的单纯形, 这称为压缩操作, 如图所示。
压缩操作的公式为
。这可以产生 个新顶点 , 因此, 新构成单纯形的顶点为 。
在迭代过程中，如果多个点对应的目标函数值相等, 则需要用到平分决胜规则。 Lagarias et al 给出的平分决胜规则为, 对于目标函数值相等的多个点, 新产生的点, 赋 予更高的下标索引, 即在下面的公式中, 在目标函数值相等的前提下, 新点排在“已有点” 之右。
下图演示了利用 Nelder-Mead 单纯形法搜索二元函数极小点时，最开始的几次迭代,
初始单纯形包括3个顶点： 和 。通过延伸操作得到顶点 和 。通过反射操作得到顶点 ，利用外收缩操作得到顶点 ， 利用内收缩操作得到顶点 。为了清晰起见，在得到了单纯形 之后，没有继续往下绘制。实际的搜索过程并没有结束，还可以继续进行迭代搜索。
模拟退火法、粒子群算法、遗传算法
详见