基於多片圖形顯示器加速之粒子群優化法

Accelerating Particle Swarm Optimization via Multiple Graphic Processing Units

洪郁凱(Yu-Kai Hung)

指導教授 ： 王偉仲

國立臺灣大學/理學院/數學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.02725

摘要

粒子群優化法為基於大量隨機性試驗之無微分最佳化方法，藉由其簡單直覺性與良好的效率性，至今已被採用來解決各種形式的最佳化問題上，使用粒子群優化法來解決高維度或複雜的目標函數問題時，需要使用大量的粒子群來探索並搜尋可能區域來達到隨機性與正確性，因而造成大量的計算源於的需求以及傳統上執行過於緩慢的問題。
在本篇論文中，我們專注於藉由圖形顯示器計算環境下來平行加速粒子群優化法，藉此解決具有簡單的邊界限制與目標函數計算負載平衡的最佳化問題，並提出一種基於大量執行緒觀點下的改良演算法藉此達到最適合於圖形顯示器架構下之粒子群優化演算法。
藉由最後的數值結果可證明圖形顯示器硬體架構非常適合於加速粒子群優化法，可以大量減少計算所耗費的時間並達到高度的平行效能，更可以藉由大量的粒子來達到搜尋到更好的最佳解。舉例來說，本篇論文中使用65536個粒子來搜尋100維度之目標函數最佳化問題時，相對於CPU上單核心的未平行化程式可以達到280倍的速度。
使用基於圖形顯示器加速之粒子群優化法可以在相對於CPU上更短的時間內解決高維度與複雜之目標函數問題，或於相同時間上獲得更佳的最佳化解。

關鍵字

粒子群優化法

並列摘要

無資料

並列關鍵字

Particle Swarm Optimization

參考文獻

[5] J.F. Chang, S.C. Chu, and J.S. Pan, A Parallel Particle Swarm Optimization Algorithm with Com-

[28] J. Li, D. Wan, Z. Chi, and X. Hu, A Parallel Particle Swarm Optimization Algorithm Based on Fine-

[1] A. Banks, J. Vincent, and C. Anyakoha, A review of particle swarm optimization. Part I: background

[2] A. Banks, J. Vincent, and C. Anyakoha, A review of particle swarm optimization. Part II: hybridis-

ation, combinatorial, multicriteria and constrained optimization, and indicative applications, Natural