粒子群最佳化演算法改良之研究

Research on a Modified Particle Swarm Optimization Algorithm

王雅賢(Ya-shyan Wang)

指導教授 ： 李維平

中原大學/商學院/資訊管理學系/碩士(2006年)

https://doi.org/10.6840/cycu200600614

摘要

粒子群最佳化演算法為一具有群體智慧概念的最佳化方法，也是演化式計算中的新分支，其具有較少參數設定、快速收斂等優點，但在粒子移動時僅跟隨個體最佳適應值記憶 與群體最佳適應值記憶 ，而使得粒子群演算法有容易落入區域最佳解的弱點。標準PSO演算法與各種改進之PSO演算法，大部份著眼於如何更有效地利用一個粒子群在解空間中搜尋最佳解，仍舊無法有效避免粒子落入區域最佳解中。
　　本研究提出一個以分群式粒子群演算法的架構，將初始產生的粒子用K-means演算法分群劃分搜尋領域後，以實驗法得到較小的 設定以加強粒子的區域搜尋能力，再經由比較分群各自找到的分群近似最佳解 ，得到全域近似最佳解，此為分群式粒子群演算法(KPSO)；另外，為確保演算法的收斂性，本研究將文化演算法「知識空間」的概念帶入了KPSO中，由知識空間中的粒子來引導主群體粒子前往具良好解答區搜尋，此為文化分群式粒子群演算法(CKPSO)。藉由此兩個粒子群的改良演算法，以期提高粒子搜尋到之全域近似最佳解的準確度。
　　研究結果得知分群後的KPSO與CKPSO均需比較小的 以加強區域搜尋能力，分群搜尋的效果使得平均最佳適應值的準度得以提升。然而，KPSO在粒子數目較少，而需處理的問題為較複雜的高維度問題時，會有無法收斂的可能性；加入了「知識空間」概念的CKPSO，其搜尋效能與KPSO相較之下雖無絕對優勢，但CKPSO有足夠能力處理複雜的高維問題，較KPSO更能確保演算法的收斂。KPSO與CKPSO在測試函數中的表現，整體來說均能優於過去學者提出之標準PSO、HPSO、FPSO。

關鍵字

群體智慧 ； 粒子群最佳化演算法 ； 文化演算法 ； 演化式計算 ； K-means演算法

並列摘要

Particle Swarm Optimization (PSO), an algorithm with the concept of swarm intelligence, also a new branch in evolutionary computing, possesses the merits of fast converging, as well as the simplification in parameter setting. Nevertheless, PSO has the demerit of the inclination to trap into local optima because when particles move, they merely follow pbest and gbest .Although the standard PSO algorithm and other modified algorithms has attempted to enhance the efficiency in utilizing a swarm to search global best, they still fail in avoiding particles falling into local optima.
This research has proposed a framework based on clustered Particle Swarm Optimization algorithm. This proposal firstly divides initially generated particles into different search clusters with K-means algorithm, and improves the local search ability by getting smaller Vmax settings with experimental methods. Then, the proposal gets global optima through the compare of gkbest obtained in different clusters. This is so called KPSO. Additionally, in order to ensure the convergence of the algorithm, this research has brought the concept of Belief Space in Culture Algorithm into KPSO, leading particles in population to search in good solution areas. This is the CKPSO. In short, this proposal purposes to increase the accuracy of mean best fitness by these two modified algorithms.
The result of this research shows that KPSO and CKPSO need smaller Vmax to increase local searching capability, and clustered search has enhanced mean best fitness value. When the number of particles is small, however, KPSO might be unable to converge in handing complicated dimension problems. After adding the concept of Belief Space, CKPSO is capable of dealing with intricate dimension problems even though it has no absolute advantage compared with KPSO in terms of searching ability. Generally speaking, the performance of KPSO and CKPSO in test functions outshines that of standard PSO, HPSO and FPSO.

並列關鍵字

K-means algorithm ； evolutionary computing ； particle swarm optimization ； swarm intelligence ； culture algorithm

參考文獻

[1] Angeline, P. J., “Evolutionary Optimization Versus Particle Swarm Optimization: Philosophy and Performance Differences,” Evolutionary Programming, 1998, pp.601-610

[3] Clerc, M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proceedings of the IEEE Congress on Evolutionary Compution, Seoul, Korea, 1999.

[5] Eberhart, R. C., and Shi, Y., “Particle Swarm Optimization: Developments, Application and Resources,” Proceedings of the 2001 Congress on Evolutionary Computation, vol.1, 2001, pp. 81-86.

[6] Eberhart, R.C., and Kennedy, J., “A new optimizer using particle swarm theory,” Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp.39-43.

[7] Eberhart, R.C., and Shi. Y., “Comparison between genetic algorithms and particle swarm optimization,” 1998 Annual Conference on Evolutionary Programming, San Diego, 1998.