求解最佳化的問題-使用粒子群演算法,part3

接續前一篇討論…

粒子群演算法，在運算上非常的簡單，首先先初始撒下粒子之個數、粒子飛行速度。

演算法：

1.每一粒子飛行速度與方向遷就於粒子本身及群體，定義飛行速度：

Vi(k+1)=W*Vi(k)+C1*rand()*(P_best_i-Xi(k))+C2*rand()*(G_best-Xi(k))............(1)

其中:

W是權重常數，考慮前一刻飛行速度，對下一刻的飛行速度的影響程度

Vi(k+1)：第i個粒子，第k+1時刻的飛行速度

Vi(k)：第i個粒子，第k時刻的飛行速度

C1,C2：學習係數，當前位置與最佳位置，影響下一時刻飛行速度的權重

rand()：隨機函數，產生0~1之間的小數

P_best_i：第i個粒子，所走路徑中自始至今之最佳值

G_best：群體粒子之最佳值

Xi(k)：第i個粒子，當前所在位置

2.定義粒子下一時刻的位置：

Xi(k+1)=Xi(k)+Vi(k+1)...........................(2)

其中：

Xi(k+1)：第i個粒子，在第k+1時刻的位置

Xi(k)：第i個粒子，在第k時刻的位置

(2)式，速度‧時間＝Vi(k+1)△t=位置

3.第i粒子最佳位置取代原則：

需定義適應函數(fitness function)，若fit(Xi(k+1))優於fit(P_best_i)，則P_best_i=Xi(k+1)

4.群體最佳值的修正時機：

若fit(P_best_i)優於fit(G_best)，則取代當前G_best地位

求解最佳化的問題-使用粒子群演算法,part2

粒子群演算法仿效鳥類飛行追求卓越的生命歷程，很像「雁行理論」。

粒子群演算法(Particle Swarm Optimization, PSO)，其精神為「一群隨機粒子分佈於一個區域範圍，每一個體粒子搜尋鄰近範圍的最優，個體與個體之間相互比較（取適合度fitness function）並擇其優，經過反覆迭代的過程，找出總體的最佳值。」

以前述的例子來解釋，假設一個一維函數F(x)=x^2..............(1)

首先，先散佈一群(N個)隨機的粒子，每一個粒子都代表此函數的X,例如X1,X2,X3....,XN

每一個X帶入(1)都會有一個相對應的函數值，我們的目的是:

找出X等於多少時，函數有最小值？

在每一次迭代的過程，個體(particle)在一個環境探索(exploit) 的歷程中，反覆與舊有的經驗（個體自始至今的最佳）比較，如果當前的位置優於舊有的經驗，最佳位置則以新值取代。

簡單的說，一隻鳥覓食，假設一個環境，甲處有一隻蟲、乙處有兩隻蟲、丙處有五隻蟲，以鳥的觀點來說，這三處最好的位置，應該是丙處。而鳥在飛翔的過程，假設會先經過甲、再到乙，最終到達丙處，鳥在觀察的過程中會發現乙優於甲、丙又優於乙，所以最佳的位置會不斷被取代。

而一群個體，在一個環境探索的歷程，每一個個體都會找到當前最好的位置，但以一個群體來說，整體最優的位置在哪？

因此，在粒子群演算法中討論到，如果一群個體相互比較，發現某一個體找到的位置是群體中所有的最佳，那麼所有的個體，將追隨這個總體最佳的位置前進。

簡單地說，如果一群鳥在一個環境中，每一隻鳥都會找到不錯的覓食點，假設其中有一隻鳥挖到寶，發現在某一個地方有無限量供應的蟲（酷斃了！），那麼所有的鳥將追隨這個位置並往這個方向飛，而放棄他自己找到還不錯的覓食點。

所以，當你有空停下腳步觀看天上飛翔的鳥，你會發現：一群鳥會跟著其中一隻往某個方向飛…

（待續）

求解最佳化的問題-使用粒子群演算法,part1

研究所時，跟隨恩師學習各種控制技術，印象中最為深刻地莫過於探討最佳化的問題。

有關最佳化的研究，有許多相關文獻運用不同的技術或方法求解最佳化，而最終的目的無非是獲得最佳的結果。至於最佳化的目的，主要為克服人為的經驗誤差，因此求助於微電腦控制，找尋參數的最佳值。

在暴力搜尋法中，遺傳演算法(Genetic Algorithm) 是最經典的技術，另外，仿生物型態的，還包含有蟻行演算法（Ants Algorithm）、及粒子群演算法（Particle Swarm Optimization,仿鳥類生態）。

再談最佳化的問題前，我們先瞭解一個最簡單的問題：

已知一個一維變數的函數F(x)=X^2 (X平方)..............(1)

若X的範圍從-5到+5，我們如果用畫圖的方式，可得以下的圖形：

從圖可以看出，此函數為拋物線函數，且最小值為F(0)=0，即：當X=0時有最小值0

當然，如果用微分來計算，我們可知：

dF(x)/dx=2x....................(2)

令dF(x)/dx=0 可得極值，由（2）可知2x=0，所以x=0............(3)

把(3)的結果帶回(1)，所以F(x)=0