NM 单纯形 搜索算法 （NM算法）
文章目录
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假设 α = 1 , γ = 2 , β = δ = 0.5 \alpha = 1,\gamma= 2,\beta=\delta=0.5 α=1,γ=2,β=δ=0.5。通过在搜索范围内随机生成D + 1个顶点来初始化单纯形，并评估目标函数在每个顶点上的适应度。
2.确定顶点
确定 x h , x s , x l x_h,x_s,x_l xh,xs,xl分别代表最高、第二高、最低函数值的顶点。
f h , f s , f l f_h,f_s,f_l fh,fs,fl分别为对应的函数值，在极小化情况下计算除 x h x_h xh外的单纯形的质心 x ‾ \overline x x。
3. reflection
通过反射最坏的点生成一个新的顶点
x
r
x_r
xr,计算公式：
x
r
=
x
‾
+
α
(
x
‾
−
x
h
)
α
>
0
(1)
x_r = \overline x + \alpha (\overline x - x_h) \qquad \alpha >0 \tag{1}
xr=x+α(x−xh)α>0(1)
计算对应的适应度值
f
r
f_r
fr，对比相应的值进行不同的操作：
{
g
o
t
o
4
i
f
f
r
<
f
l
x
r
代替
x
h
并且
g
o
t
o
7
i
f
f
l
≤
f
r
≤
f
s
g
o
t
o
5
i
f
f
r
>
f
s
(2)
\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}
⎩
⎨
⎧go to 4xr代替xh 并且go to 7go to 5if fr<flif fl≤fr≤fsif fr>fs(2)
4. expansion
对反射进行扩展，使搜索空间向同一方向扩展，扩展点按下式计算:
x
e
=
x
‾
+
γ
(
x
r
−
x
‾
)
γ
>
1
(3)
x_e = \overline x + \gamma (x_r - \overline x) \qquad \gamma > 1 \tag{3}
xe=x+γ(xr−x)γ>1(3)
同样计算对应的适应度值
f
e
f_e
fe，判断依据：
{
接受扩展，并用
x
e
代替
x
h
i
f
f
e
<
f
r
x
r
代替
x
h
,
g
o
t
o
7
o
t
h
e
r
w
i
s
e
(4)
\begin {cases} 接受扩展，并用x_e代替x_h & if \ f_e<f_r \\ x_r 代替x_h ,go \ to \ 7 & otherwise \end {cases} \tag{4}
{接受扩展，并用xe代替xhxr代替xh,go to 7if fe<frotherwise(4)
5. contraction
当
f
r
>
f
s
a
n
d
f
r
≤
f
h
f_r>f_s \ and \ f_r \leq f_h
fr>fs and fr≤fh，用
x
r
x_r
xr代替
x
h
x_h
xh并尝试收缩。当
f
r
>
f
h
f_r > f_h
fr>fh，不直接用
x
r
x_r
xr代替
x
h
x_h
xh收缩，收缩顶点按下式计算：
x
c
=
x
‾
+
β
(
x
h
−
x
‾
)
0
<
β
<
1
(5)
x_c = \overline x + \beta (x_h - \overline x) \qquad 0 < \beta < 1 \tag{5}
xc=x+β(xh−x)0<β<1(5)
判断：
{
接受收缩，并用
x
c
代替
x
h
,
g
o
t
o
7
i
f
f
c
≤
f
h
g
o
t
o
6
o
t
h
e
r
w
i
s
e
(6)
\begin {cases} 接受收缩，并用x_c代替x_h ,\ go \ to \ 7 & if \ f_c \leq f_h \\ go \ to \ 6 & otherwise \end {cases} \tag{6}
{接受收缩，并用xc代替xh, go to 7go to 6if fc≤fhotherwise(6)
6. shrinkage
若第5步失败，将继续尝试收缩。通过收缩单纯形除
x
l
x_l
xl的所有点完成，然后进行第7步。收缩公式如下：
x
i
=
δ
x
i
+
(
1
−
δ
)
x
l
i
=
1
,
2
,
.
.
.
.
,
D
+
1
a
n
d
i
≠
l
0
<
δ
<
1
(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}
xi=δxi+(1−δ)xli=1,2,....,D+1 and i=l0<δ<1(7)
7. 终止
如果满足终止条件，则停止计算;否则，新的迭代将从步骤2开始
参考文献
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
4
0- 0
已为社区贡献1条内容
所有评论(0)