阿米巴原蟲找窩 - 如何找最小值?

這次我們用 Nelder Mead algorithm 來求得最小值。

Nelder Mead algorithm 又稱為下降單純形法(Downhill simplex method)。其背後的想法是先構造一個初始單純形(Simplex)，然後對此單純形進行反射(Reflection)、擴展(extension)、緊縮(contraction)，逐步趨近最小值。

所謂單純形(Simplex) 是在 R (n) 空間中以線相連的 n+1 個點集合。 如在二維空間 R(2) 中的三角形( 2+1 個點)。[正規單純形( regular simplex) 是指這些點彼此等距。] 

所以 Nelder Mead algorithm，在二維空間中 Nelder Mead algorithm 直覺上的過程如下:

                                                             上面有沒有像阿米巴原蟲

                                                                      滾到最低點

 Nelder Mead algorithm 的作法如下:  給定 n+1 個點 xi, i=1… n+1  與 f(xi) 的值 ; 給定 Reflection 係數 R = 1、Expansion 係數 E = 2、Contraction 係數 K = 0.2、Shrinkage 係數 S = 0.2。

1. 排列函數值 f1 < f2 < … < fn+1，其對應點為  x1,x2,...,xn+1

2. 計算  xm = average( x1,x2,...,xn)

3. 計算 xn+1 的反射點 xr = xm + R(xm-xn+1) 與 fr = f(xr)。假如  f1 < fr < fn， 此時反射點對應的值介於最佳與次差值之間， 則接受 xr 終止反覆。

4. 假如 fr < f1 此時反射點對應的值比目前最佳還好，故再往此方向在邁一小步看看，計算 xe = xm+ E (xr - xm) 並求 f(xe) 值 。 假如 fe < fr 此時擴展點的方向是好的, 故接受 xe ; 否則接受 xr 終止反覆。

5. 假如 fr > fn 此時反射點對應的值比目前次差值還差, 故執行緊縮

向外嘗試(如4): 假如 fn < fr < fn+1 此時反射點對應的值比目前最差還好，故小心往外擴一點，計算  xoc= xm+ K (xr - xm) 與求 f(xoc) 值. 假如 foc< fr 有點進步 , 接受 xoc 終止反覆；否則進行一伸縮。

向內嘗試: 假如 fr > fn+1 此時反射點對應的值比目前最差還好，則最好往反方向計算 xic = xm – K (xm- xn+1) 與求 f(xic)  值.  假如 fic< fn+1 有點進步故接受 xic 終止反覆；否則進行一伸縮。

6. 伸縮: 求 n 個點 vi = xi + S (xi-x1), i = 2,….,n+1 的 f 值。下一個反覆的單純形點為 x1, v2, …, vn+1。

想像自己是一隻阿米巴原蟲在找窩 。