NM 单纯形搜索算法（NM算法）

对原始的NM单纯形搜索算法的步骤进行了总结

暗夜的幕布

4810人浏览 · 2020-05-06 12:40:29

暗夜的幕布 · 2020-05-06 12:40:29 发布

文章目录

The Nelder–Mead simplex search method

The Nelder–Mead simplex search method

简介

一种不使用梯度信息的无约束优化的局部下降算法。

单纯形是由D + 1个点(或顶点)在D维空间中构成的几何图形，什么意思呢？在二维空间中，是个三角形，三维空间中，是个四面体，不一定是正的。

如果以一个非退化的单纯形的任意点为原点，那么其他D点则定义了跨越D维向量空间的向量方向。这种方法的操作是通过reflection, expansion, contraction and shrinkage这四个基本过程，根据函数的局部行为对单纯形进行重新划分。通过这些步骤，单纯形可以成功地自我改进，接近最优。

Q1：如何理解contraction与shrinkage？

原始的NMSS过程概述如下：

1. 初始化

参数	符号
the reflection coefficient	$\alpha$
the expansion coefficient	$\gamma$
the contraction coefficient	$\beta$
the shrinkage coefficient	$\delta$

NM假设 $\alpha = 1,\gamma= 2,\beta=\delta=0.5$ 。通过在搜索范围内随机生成D + 1个顶点来初始化单纯形，并评估目标函数在每个顶点上的适应度。

2.确定顶点

确定 $x_h,x_s,x_l$ 分别代表最高、第二高、最低函数值的顶点。

$f_h,f_s,f_l$ 分别为对应的函数值，在极小化情况下计算除 $x_h$ 外的单纯形的质心 $\overline x$ 。

3. reflection

通过反射最坏的点生成一个新的顶点 $x_r$ ,计算公式：
$x_r = \overline x + \alpha (\overline x - x_h) \qquad \alpha >0 \tag{1}$
计算对应的适应度值 $f_r$ ，对比相应的值进行不同的操作：
$\begin {cases} go\ to\ 4 &if \ f_r<f_l\\ x_r代替x_h\ 并且go \ to \ 7 & if \ f_l \leq f_r \leq f_s \\ go \ to\ 5 & if \ f_r>f_s \end {cases} \tag{2}$

在这里插入图片描述

4. expansion

对反射进行扩展，使搜索空间向同一方向扩展，扩展点按下式计算:
$x_e = \overline x + \gamma (x_r - \overline x) \qquad \gamma > 1 \tag{3}$
同样计算对应的适应度值 $f_e$ ，判断依据：
$\begin {cases} 接受扩展，并用x_e代替x_h & if \ f_e<f_r \\ x_r 代替x_h ,go \ to \ 7 & otherwise \end {cases} \tag{4}$

在这里插入图片描述

5. contraction

当 $f_r>f_s \ and \ f_r \leq f_h$ ，用 $x_r$ 代替 $x_h$ 并尝试收缩。当 $f_r > f_h$ ，不直接用 $x_r$ 代替 $x_h$ 收缩，收缩顶点按下式计算：
$x_c = \overline x + \beta (x_h - \overline x) \qquad 0 < \beta < 1 \tag{5}$
判断：
$\begin {cases} 接受收缩，并用x_c代替x_h ,\ go \ to \ 7 & if \ f_c \leq f_h \\ go \ to \ 6 & otherwise \end {cases} \tag{6}$

在这里插入图片描述

6. shrinkage

若第5步失败，将继续尝试收缩。通过收缩单纯形除 $x_l$ 的所有点完成，然后进行第7步。收缩公式如下：
$x_i = \delta x_i + (1 - \delta) x_l \qquad i=1,2,....,D+1 \ and \ i \neq l \qquad 0 < \delta < 1 \tag{7}$