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

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

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

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

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

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

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

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

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

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

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

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

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

（待續）