一個新的全域最佳化演算法：禁制搜尋加強式粒子群最佳化

A new global optimizer: tabu-search enhanced particle swarm optimization

朱家賢(Jia-Xian Zhu)

指導教授 ： 尹邦嚴

國立暨南國際大學/管理學院/資訊管理學系/碩士(2008年)

摘要

本研究提出了一個新的全域最佳化演算法「禁制搜尋加強式粒子群最佳化」，用於解決無限制式連續最佳化問題，其核心概念主要是加強粒子群最佳化的引導功能，並利用禁制搜尋法動態禁制串列及釋放禁制串列等進階的排斥功能，來避免粒子重覆搜尋同一解答空間，以達到粒子分散搜尋的效果，而方法中根據粒子群最佳化的個體最佳經驗值及群體最佳經驗值所設計的粒子重新起始及粒子群重新起始，則是利用亂數解及路徑重新連結的重新起始策略來幫助搜尋跳脫停滯狀態。最後則透過求解知名且困難的23個標竿函數，來分析方法中各性質的重要性，並擴大求解110個測試函數，與求解無限制式連續最佳化問題有不錯效果的PSwarm及粒子群最佳化領域中最常被應用的壓縮因子粒子群最佳化演算法(CFPSO)做比較。實驗數據顯示，所提方法能獲得比PSwarm及CFPSO有更好的效能。

關鍵字

粒子群最佳化 ； 禁制搜尋法 ； 無限制式連續最佳化問題

並列摘要

This thesis proposes a new global optimizer named, tabu-search enhanced particle swarm optimization, which involves three novel features: (1) employing three-point guiding approach to navigate the trajectory of particles, (2) constraining the particle trajectories by marking the incumbent personal bests of all particles as tabu-active, and (3) avoiding search stagnation by embedding particle restarting and swarm restarting techniques. The restarting techniques are implemented by relinkng the paths from current particles or the globle best particle to random particles. The properties of the proposed algorithm are tested on 23 benchmark functions to identify its best setting. Then the performance of our algorithm is compared with two competing algorithms, namely the PSwarm and CFPSO, respectively, on a large set of 110 unconstrained continuous optimization functions. The experimental results manifest that our method outperforms PSwarm and CFPSO.

並列關鍵字

particle swarm optimization ； tabu search ； unconstrained continuous optimization problem

參考文獻

[1] Angeline, P. J., “Using selection to improve particle swarm optimization,” in Proc. IEEE Int. Conf. Evol. Computation, AK, 1998.

[2] Chelouah, R., and Siarry P., “A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions,” European Journal of Operational Research, Vol. 161, pp. 636-654, 2005.

[3] Coello, C. A. C., Puido, G. T., and Lechuga, M. S., “Handling multiple objectives with particle swarm optimization,” IEEE Transactions on Evolutionary Computation, Vol. 8(3), pp. 254-279, 2004.

[4] Clerc, M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proc. of 1999 Congress on Evolutionary Computation, Washington, pp. 1951-1957, 1999.

[5] Costamagna, E., Fanni, A. and Giacinto, G., “A tabu search algorithm for the optimization of telecommunication networks,” European Journal of Operational Research, Vol. 6(2–3), pp. 357–372, 1998.