臺灣博碩士論文加值系統

粒子群演算法（Particle Swarm Optimization Algorithm，PSO）[1]為演化式計算領域的一門新技術，其特色在於「較少的參數設定」、「收斂速度快」。其與蟻群演算法、基因演算法、摸擬退火法、類神經網路相同，皆是仿效大自然的行為, 來進行最佳化求解。粒子群演算法除了仿效鳥、魚的覓食行為，也加入了人類社會行為的觀念，粒子在飛行時會追隨兩個值，一是個體最佳適應值記憶pbest，一是群體最佳適應值記憶gbest，藉由這兩個值計算出下一代飛行的位置，如此透過疊代的運算尋找最佳解。粒子群演算法已被廣泛的運用於各種領域，如旅行家銷售問題、排程問題等。
雖然粒子群演算法有「收斂速度快」的特性，但隨之而來的問題，則是會落入「區域最佳解」，尤其在多峰函數問題的求解上。目前各種改進PSO演算法，大部份著眼於如何更有效利用一個粒子在解空間搜尋最佳解。本研究認為演算法本身應能針對不同的問題做自適應的分析，再以適合的探索方式進行飛行，較能有效的對空間進行探索。
本研究提出利用粒子一開始分成兩群，並且給予兩群不同的慣性權重，來找出適合目標問題的慣性權重，以期能提升粒子群的求解品質。
研究中與其它較常見的慣性權重相互比較，如線性遞減型、線性遞增型、指數型、開口向上拋物線型、曲線型、Fuzzy型、隨機型等進行比較。

Particle Swarm Optimization Algorithm (PSO) is a new technology in evolution computing. PSO has many advantages, such as fewer parameters needed to be adjusted and the rapid convergence speed. It is the same as Ant Colony Optimization Algorithm. PSO finds the best solution by studying the nature. In addition to study birds and fishes forage, PSO also join the human social science. Each particle is following personal best solution and global solution when moving. Each particle computes new flying location to find the best answer by searching pbest and gbest after generations.
Even though PSO can rapid converge, but it also has the problem such as local best solution especially in multi-model functions. At present, many PSO improved studies focus on that how to use each particle to find the best solution effective in the space. We consider that the algorithm should estimation which inertia weight is better for the problems.
In this paper, we propose a method that using two different inertia weight particle swarms to test which inertia weight is better for the target function for improving the precision.
In this study, we compared with other inertia weight methods such as, decrease linerly, increase linerly, exponent, parapola with open up, curve, Fuzzy and random.

論文摘要 I
Abstract II
誌謝辭 III
目錄 IV
圖目錄 VI
表目錄 IX
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究架構 3
第二章 文獻探討 4
2.1 粒子群演算法(Particle Swarm Optimization) 4
2.2 PSO 概念與演算法流程 5
2.3 線性遞減慣性權重粒子群演算法 9
2.4 其它粒子群演算法 9
2.4.1 多粒子群協同優化算法(PSCO) 9
2.4.2 Fuzzy Adaptive Particle Swarm Optimization(FPSO) 10
2.4.3 隨機型慣性權重PSO 13
2.4.4 曲線型慣性權重PSO 13
2.4.5 線性遞增慣性權重PSO 13
2.4.6 開口向上拋物線型慣性權重PSO及指數型遞減慣性權重PSO 14
2.5 慣性權重比較 15
第三章 研究方法 16
3.1 模擬線性遞減慣性權重粒子群演算法(PSO-TVIW) 17
3.2 慣性權重特性實驗 17
3.3 自適應調整慣性權重之粒子群演算法 21
第四章 實驗結果 26
4.1 模擬慣性權重線性遞減粒子群演算法實驗 26
4.2 慣性權重特性實證 28
4.2.1 實驗一：兩種慣性權重在四個函數上平均發生收斂時間 30
4.2.2 實驗二：兩種慣性權重在四個函數上的表現 34
4.3 自適應慣性權重之粒子群演算法實證 54
4.3.1 適應值收斂比較 55
4.3.2 精確度比較 75
結論與未來研究方向 78
參 考 文 獻 79
圖 1- 1 研究流程 3
圖 2- 1 解空間示意圖 6
圖 2- 2 粒子速度計算示意圖 6
圖 2- 3 粒子訊息傳遞模式 7
圖 2- 4 粒子群演算法流程圖 7
圖 3- 1 Sphere三維圖 18
圖 3- 2 Rosenbrock三維圖 18
圖 3- 3 Rosenbrock三維放大圖 18
圖 3- 4 Rastrigrin三維圖 19
圖 3- 5 Griewank三維圖 19
圖 3- 6 Griewank三維放大圖 19
圖 3- 7時間運用策略 21
圖 3- 8 1/4代數時，判斷出較適合0.4 22
圖 3- 9 1/4代數時，判斷出較適合0.9 23
圖 3- 10 1/4代數時，發現0.4、0.9表現相同 23
圖 3- 11自適應調整慣性權重之粒子群演算法流程圖 25
圖 4- 1a Sphere慣性權重適應值比較圖（10顆粒子、10維、1000代） 34
圖 4- 1b Sphere慣性權重適應值比較圖（10顆粒子、20維、1500代） 34
圖 4- 1c Sphere慣性權重適應值比較圖（10顆粒子、30維、2000代） 35
圖 4- 1d Sphere慣性權重適應值比較圖（20顆粒子、10維、1000代） 35
圖 4- 1e Sphere慣性權重適應值比較圖（20顆粒子、20維、1500代） 36
圖 4- 1f Sphere慣性權重適應值比較圖（20顆粒子、30維、2000代） 36
圖 4- 1g Sphere慣性權重適應值比較圖（40顆粒子、10維、1000代） 37
圖 4- 1h Sphere慣性權重適應值比較圖（40顆粒子、20維、1500代） 37
圖 4- 1i Sphere慣性權重適應值比較圖（40顆粒子、30維、2000代） 38
圖 4- 2a Griewank慣性權重適應值比較圖（10顆粒子、10維、1000代） 39
圖 4- 2b Griewank慣性權重適應值比較圖（10顆粒子、20維、1500代） 39
圖 4- 2c Griewank慣性權重適應值比較圖（10顆粒子、30維、2000代） 40
圖 4- 2d Griewank慣性權重適應值比較圖（20顆粒子、10維、1000代） 40
圖 4- 2e Griewank慣性權重適應值比較圖（20顆粒子、20維、1500代） 41
圖 4- 2f Griewank慣性權重適應值比較圖（20顆粒子、30維、2000代） 41
圖 4- 2g Griewank慣性權重適應值比較圖（40顆粒子、10維、1000代） 42
圖 4- 2h Griewank慣性權重適應值比較圖（40顆粒子、20維、1500代） 42
圖 4- 2i Griewank慣性權重適應值比較圖（40顆粒子、30維、2000代） 43
圖 4- 3a Rosenbrock慣性權重適應值比較圖（10顆粒子、10維、1000代） 44
圖 4- 3b Rosenbrock慣性權重適應值比較圖（10顆粒子、20維、1500代） 44
圖 4- 3c Rosenbrock慣性權重適應值比較圖（10顆粒子、30維、2000代） 45
圖 4- 3d Rosenbrock慣性權重適應值比較圖（20顆粒子、10維、1000代） 45
圖 4- 3e Rosenbrock慣性權重適應值比較圖（20顆粒子、20維、1500代） 46
圖 4- 3f Rosenbrock慣性權重適應值比較圖（20顆粒子、30維、2000代） 46
圖 4- 3g Rosenbrock慣性權重適應值比較圖（40顆粒子、10維、1000代） 47
圖 4- 3h Rosenbrock慣性權重適應值比較圖（40顆粒子、20維、1500代） 47
圖 4- 3i Rosenbrock慣性權重適應值比較圖（40顆粒子、30維、2000代） 48
圖 4- 4a Rastrigrin慣性權重適應值比較圖（10顆粒子、10維、1000代） 49
圖 4- 4b Rastrigrin慣性權重適應值比較圖（10顆粒子、20維、1500代） 49
圖 4- 4c Rastrigrin慣性權重適應值比較圖（10顆粒子、30維、2000代） 50
圖 4- 4d Rastrigrin慣性權重適應值比較圖（20顆粒子、10維、1000代） 50
圖 4- 4e Rosenbrock慣性權重適應值比較圖（20顆粒子、20維、1500代） 51
圖 4- 4f Rosenbrock慣性權重適應值比較圖（20顆粒子、30維、2000代） 51
圖 4- 4g Rastrigrin慣性權重適應值比較圖（40顆粒子、10維、1000代） 52
圖 4- 4h Rastrigrin慣性權重適應值比較圖（40顆粒子、20維、1500代） 52
圖 4- 4i Rastrigrin慣性權重適應值比較圖（40顆粒子、30維、2000代） 53
圖 4- 5a Sphere各模式適應值比較圖（20顆粒子、10維、1000代） 55
圖 4- 5b Sphere各模式適應值比較圖（20顆粒子、20維、1500代） 56
圖 4- 5c Sphere各模式適應值比較圖（20顆粒子、30維、2000代） 56
圖 4- 5d Sphere各模式適應值比較圖（40顆粒子、10維、1000代） 57
圖 4- 5e Sphere各模式適應值比較圖（40顆粒子、20維、1500代） 57
圖 4- 5f Sphere各模式適應值比較圖（40顆粒子、30維、2000代） 58
圖 4- 5g Sphere各模式適應值比較圖（80顆粒子、10維、1000代） 58
圖 4- 5h Sphere各模式適應值比較圖（80顆粒子、20維、1500代） 59
圖 4- 5i Sphere各模式適應值比較圖（80顆粒子、30維、2000代） 59
圖 4- 6a Griewank各模式適應值比較圖（20顆粒子、10維、1000代） 60
圖 4- 6b Griewank各模式適應值比較圖（20顆粒子、20維、1500代） 61
圖 4- 6c Griewank各模式適應值比較圖（20顆粒子、30維、2000代） 61
圖 4- 6d Griewank各模式適應值比較圖（40顆粒子、10維、1000代） 62
圖 4- 6e Griewank各模式適應值比較圖（40顆粒子、20維、1500代） 62
圖 4- 6f Griewank各模式適應值比較圖（40顆粒子、30維、2000代） 63
圖 4- 6g Griewank各模式適應值比較圖（80顆粒子、10維、1000代） 63
圖 4- 6h Griewank各模式適應值比較圖（80顆粒子、20維、1500代） 64
圖 4- 6i Griewank各模式適應值比較圖（80顆粒子、30維、2000代） 64
圖 4- 7a Rosenbrock各模式適應值比較圖（20顆粒子、10維、1000代） 65
圖 4- 7b Rosenbrock各模式適應值比較圖（20顆粒子、20維、1500代） 66
圖 4- 7c Rosenbrock各模式適應值比較圖（20顆粒子、30維、2000代） 66
圖 4- 7d Rosenbrock各模式適應值比較圖（40顆粒子、10維、1000代） 67
圖 4- 7e Rosenbrock各模式適應值比較圖（40顆粒子、20維、1500代） 67
圖 4- 7f Rosenbrock各模式適應值比較圖（40顆粒子、30維、2000代） 68
圖 4- 7g Rosenbrock各模式適應值比較圖（80顆粒子、10維、1000代） 68
圖 4- 7h Rosenbrock各模式適應值比較圖（80顆粒子、20維、1500代） 69
圖 4- 7i Rosenbrock各模式適應值比較圖（80顆粒子、30維、2000代） 69
圖 4- 8a Rastrigrin各模式適應值比較圖（20顆粒子、10維、1000代） 70
圖 4- 8b Rastrigrin各模式適應值比較圖（20顆粒子、20維、1500代） 71
圖 4- 8c Rastrigrin各模式適應值比較圖（20顆粒子、30維、2000代） 71
圖 4- 8d Rastrigrin各模式適應值比較圖（40顆粒子、10維、1000代） 72
圖 4- 8e Rastrigrin各模式適應值比較圖（40顆粒子、20維、1500代） 72
圖 4- 8f Rastrigrin各模式適應值比較圖（40顆粒子、30維、2000代） 73
圖 4- 8g Rastrigrin各模式適應值比較圖（80顆粒子、10維、1000代） 73
圖 4- 8h Rastrigrin各模式適應值比較圖（80顆粒子、20維、1500代） 74
圖 4- 8i Rastrigrin各模式適應值比較圖（80顆粒子、30維、2000代） 74

[1] Eberhart, R.C., and Kennedy, J., new optimizer using particle swarm theory, Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp.39-43.
[2] Reynolds, R.G. and Sverdlik, W., problem sloving using cultural algorithms, Evolutionary computation. IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference, Vol. 2, 1994, pp.645-650.
[3] Eberhart, R.C., and Shi. Y., comparison between genetic algorithms and particle swarm optimization, 1998 Annual Conference on Evolutionary Programming, San Diego, 1998.
[4] Kennedy, J., and Eberhart, R.C., Particle swarm optimization, Proc. IEEE International Conference on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995, pp. IV: 1942-1948.
[5] Kennedy, J., and Eberhart, R.C., Mpirical study of particle swarm optimization, Proceedings of the 1999 Congress on Evolutionary Computation, Vol. 3, 1999.
[6] 艾景波、滕宏飛，文化粒子群優化算法，中國科技論文在線，www.paper.deu.cn
[7] Shi, Y. and Eberhart, R. C. Fuzzy Adaptive Particle Swarm Optimization, Proc Congress on Evolutionary Computation. Piscataway: IEEE Press, 2001, pp.101-106.
[8] Dorigo, M., Maniezzo, V., and Colorni, A., The ant system: Optiization by a colony of cooperating agents, IEEE Transactions on Systems and Cybernetics – Part B, Vol, 26, No.1, 1996, pp.21-41.
[9] 胡曉輝，粒子群優化算法介紹，http://icdweb.cc.purdue.edu/~hux，2002。
[10] Reynolds, C.W., Flock, Herds, and Schools: A Distributed Behavioral Model, Computer Graphics, Vol. 21, No. 4, 1987, pp.25-34.
[11] R Boyd and PJ Richerson, Culture and the Evolutionary Process, http://books.google.com/books?hl=zh-TW&lr=&id=JFxj3Vq-MMAC&oi=fnd&pg=PP9&dq=Boyd+Richerson&ots=kTMttAOx4h&sig=n1awzqkixN_-2k0ck0AVC8_UPts#PPA21,M1, 1998.
[12] PSO Tutorial, Online Available at: http://www.swarmintelligence.org/index.php
[13] 黃承龍、黃良吉、董吉雄，粒子群最佳化演算法之文獻回顧與研究議題分析，2005 數位內容管理與應用研討會，2005。
[14] 李愛國，多粒子群協同優化算法，复旦學報，第四十三卷，第一期：923-925頁，2004。
[15] Shi, Y., and Eberhart, R. C., Tracking and optimizing dynamic systems with particle swarms, Proceedings of the 2001 Congress on Evolutionary Computation, 2001, Vol. 1, pp 94-100.
[16] 潭立靜、樂麗君、牛奔、虛並寧，一種求解函數優化的新型混合優化算法，中國科技論文在線，www.paper.deu.cn
[17] Zheng, Y., Ma, L., Zhang, L., and Qian, J., Empirical study of particle swarm optimizer with an increasing inertia weight. Proceedings of IEEE Congress on Evolutionary Computation 2003 (CEC 2003), Canbella, Australia, 2003. pp 221-226.
[18] 陳貴敏、賈建，粒子群優化算法的慣性權重遞減策略研究，西安交通大學學報，第四十卷，第一期，2006。