臺灣博碩士論文加值系統

由於目前對於粒子群演算法改良的研究中所提出之擾動策略，都是作為演算法改良的附屬策略。為了驗證擾動策略成為改良粒子群演算法主要策略的可行性，本研究嘗試引用基因演算法中突變的概念，提出三種活化策略改良粒子群演算法。透過實驗證明，本文所提出的活化策略，有三項優點：首先可以作為改良演算法的主要策略，並且使得演算法的效能亦不遜於以往的演算法。其次在擾動判定上，也突破了以往「在固定迭代數未改善即擾動」的方式，改由演算法以粒子群的求解狀態自動判斷是否活化，使得擾動判定策略更加自動、靈活。最後在附屬策略方面，本研究所提出的活化策略在與其它改良的粒子群演算法進行搭配，作為其附屬策略時，亦能增進原本演算法的效能。

According to researches, activation was a minor strategy of improving Particle Swarm Algorithm. For proofing the possibility of activation strategy could be a main strategy for improving Particle Swarm Algorithm, this article adopt the concept of mutation in Genetic Algorithm to improve Particle Swarm Optimization. The experimental results show three advantages for the activation strategies. First, It’s workable for the algorithm and the performance are superior to former PSO algorithms. Second, the agitation strategy was more flexible. Third, when the activation strategies collocate with other PSO algorithms, the performance would be superior then the original algorithm.

目錄
論文摘要 I
Abstract II
誌謝辭 III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第三節 研究架構 3
第二章 文獻探討 5
第一節 粒子群演算法(Particle Swarm Optimization) 5
2.1.1 PSO演算法發展背景 5
2.1.2 PSO概念與演算法流程 6
第二節 基因演算法 9
2.2.1 基因演算法發展背景 9
2.2.2 基因演算法概念與流程 10
第三章 研究方法 13
第一節 方法一：活化策略一型(Activation Strategy 1) 14
3.1.1活化策略一型說明 14
3.1.2活化策略一型虛擬碼 14
第二節 方法二：活化策略二型(Activation Strategy 2) 15
3.2.1活化策略二型說明 15
3.2.2活化策略二型虛擬碼 15
第三節 方法三：活化策略三型(Activation Strategy 3) 16
3.3.1活化策略三型說明 16
3.3.2活化策略三型虛擬碼 16
第四章 實驗設計 17
第一節 實驗環境 19
第二節 實驗一：活化策略比較測試 20
4.2.1測試函數與參數設置 20
4.2.2活化策略比較實證說明 23
第三節 實驗二：作為改良PSO演算法主要策略之效能實證 26
4.3.1測試函數與參數設置 26
4.3.2求解能力實證說明 29
第四節 實驗三：作為改良PSO演算法附屬策略之效能實證 32
4.3.1測試函數與參數設置 32
4.2.2求解能力實證說明 37
第五節 實驗結果總結 44
第五章 結論與建議 45
第一節 研究結論 45
第二節 未來研究議題 45
參 考 文 獻 46

圖目錄
圖1- 1 研究架構與流程 4
圖2- 1 粒子速度與位置搜尋示意圖 6
圖2- 2 粒子群演算法流程圖 7
圖2- 3 基因演算法示意圖 10
圖2- 4 基因演算法運作流程圖 11
圖2- 5 基因演算法突變示意圖 12
圖3- 1 活化策略一型示意圖 14
圖3- 2 活化策略二型示意圖 15
圖3- 3 活化策略三型示意圖 16
圖4- 1 活化策略比較測試示意圖 17
圖4- 2 作為改良演算法主要策略之效能實驗示意圖 18
圖4- 3 作為改良演算法附屬策略之效能實驗示意圖 18
圖4- 4 系統畫面 19
圖4- 5 Rosenbrock函數 21
圖4- 6 Rosenbrock函數 21
圖4- 7 Rastrigin函數 22
圖4- 8 Griewank函數 22
圖4- 9 Griewank函數 23
圖4- 10 活化策略比較分析(Sphere函數) 24
圖4- 11 活化策略比較分析(Rosenbrock函數) 24
圖4- 12 活化策略比較分析(Rastrigrin函數) 25
圖4- 13 活化策略比較分析(Griewank函數) 25
圖4- 14 Rosenbrock函數 26
圖4- 15 Rosenbrock函數 27
圖4- 16 Rastrigin函數 27
圖4- 17 Griewank函數 28
圖4- 18 Griewank函數 28
圖4- 19 主要策略比較測試(Rosenbrock函數) 30
圖4- 20 主要策略比較測試(Rastrigrin函數) 30
圖4- 21 主要策略比較測試(Griewank函數) 31
圖4- 22 Rosenbrock函數 33
圖4- 23 Rosenbrock函數 33
圖4- 24 Rastrigin函數 34
圖4- 25 Griewank函數 34
圖4- 26 Griewank函數 35
圖4- 27 作為PSCO附屬策略比較測試(Rosenbrock函數) 38
圖4- 28 作為PSCO附屬策略比較測試(Rastrigrin函數) 38
圖4- 29 作為PSCO附屬策略比較測試(Griewank函數) 38
圖4- 30 作為Group1附屬策略比較測試(Sphere函數) 39
圖4- 31 作為Group1附屬策略比較測試(Rosenbrock函數) 40
圖4- 32 作為Group1附屬策略比較測試(Rastrigrin函數) 40
圖4- 33 作為Group1附屬策略比較測試(Griewank函數) 40
圖4- 34 作為Group2附屬策略比較測試(Sphere函數) 41
圖4- 35 作為Group2附屬策略比較測試(Rosenbrock函數) 41
圖4- 36 作為Group2附屬策略比較測試(Rastrigrin函數) 41
圖4- 37 作為Group2附屬策略比較測試(Griewank函數) 42
圖4- 38 作為 -PSO附屬策略比較測試(Sphere函數) 43
圖4- 39 作為 -PSO附屬策略比較測試(Rosenbrock函數) 43
圖4- 40 作為 -PSO附屬策略比較測試(Rastrigrin函數) 43
圖4- 41 作為 -PSO附屬策略比較測試(Griewank函數) 43


表目錄
表4- 1實驗一之測試函數的搜尋空間與最大速度 23
表4- 2 實驗二之測試函數的搜尋空間與最大速度 29
表4- 3 學習因子參數設定表 29
表4- 4 粒子個數、維度、演化代數、求解精度與測試次數 29
表4- 5 作為改良PSO演算法主要策略之效能實證綜合比較 31
表4- 6 PCSO所用測試函數的搜尋空間與最大速度 35
表4- 7 壓縮係數(K)所用測試函數的搜尋空間與最大速度 35
表4- 8 -PSO所用測試函數的搜尋空間與最大速度 36
表4- 9 慣性權重 採用策略彙總表 36
表4- 10 學習因子參數設定表 36
表4- 11 粒子個數、維度、演化代數、求解精度與測試次數 37
表4- 12 實驗結果總結 44

[1]Ashraf M. Abdelbar, Suzan Abdelshahid, Donald C. Wunsch II, “Fuzzy PSO: A Generalization of Particle Swarm Optimization,” Proceedings of International Joint Conference on Neural Networks, Volume 2, July 31 - August 4, 2005, pp.1086 – 1091.
[2]Boyd, R., and Richerson, P.J., Culture and Evolutionary Process, University Of Chicago Press, 1988.
[3]Carlisle A, Dozier G., “Adapting particle swarm optimization to dynamic environment,” [A].Inc: Arabnia H. R.,eds. Proc of Int’l Conf on Artificial Intelligence [C]. Las Vegas:CSREA Press, 2000, pp.429-434.
[4]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]Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
[8]Holland, J.H., “Adaptation in Natural and Artificial System,” Ann Arbor: The University of Michigan Press, 1975.
[9]Hongbo Liu, Ajith Abraham, “Fuzzy adaptive turbulent particle swarm optimization,” Fifth International Conference on Hybrid Intelligent Systems, November 6-9, 2005, pp.6.
[10]Hu. X., Shi, Y., and Eberhart, R. C., “Recent advances in particle swarm,” Proceedings of IEEE International Conference on Evolutionary Computation, 2004, pp. 90-97.
[11]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. 1942-1948
[12]Kennedy, J., and Eberhart, R.C., Swarm Intelligence, Morgan Kaufmann Press, 2001.
[13]Lovbjerg M., Rasmussen T. K., Krink T., Hybrid particle swarm optimiser with breeding and subpopulations ,” In：Spector L, eds. Proc of Genetic and Evolutionary Computation Conference [C]. San Fransisco: Morgan Kaufmann Publishers Inc, 2001, pp.469-476.
[14]Qian-Li Zhang, Xing Li, Quang-Ahn Tran, “A modified particle swarm optimization Algorithm,” Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, Guangzhou, 18-21 August 2005, pp.2993 – 2995.
[15]R. C. Eberhart, Y. Shi, “Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization,” The IEEE Congress on Evolutionary Computation. San Francisco, USA: IEEE, Volume 1, 16-19 July 2000 , vol.1, pp. 84 - 88.
[16]R. C. Eberhart, Y. Shi, “Tracking and optimizing dynamic systems with particle swarms,” The IEEE Congress on Evolutionary Computation. San Francisco, USA: IEEE, 2001, pp.94-100.
[17]R. C. Eberhart, Yuhui Shi, “Comparison between genetic algorithms and particle swarm optimizations,” In: Proc. The 7th Annual Conf. Evolutionary Programming. New York:Springer-Verlag, 1998. pp. 611-618
[18]Reynolds, C.W., “Flock, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics, Vol.21, No.4, 1987, pp.25-34.
[19]Shi, Y., and Eberhart, R. C., “A modified particle swarm optimizer,” Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. Piscataway. 1998b, pp. 69-73.
[20]Shi, Y., and Eberhart, R. C., “Parameter selection in particle swarm optimization,” Proceedings of the 1998 Annual Conference on Evolutionary Computation, 1998a.
[21]Yuhui Shi, Russell C. Eberhart, “Empirical study of particle swarm optimization,” International Conference on Evolutionary Computation, Washington, USA: IEEE, 1999, pp. 1945-1950.
[22]Yuhui Shi, Russell C. Eberhart, “Fuzzy adaptive particle swarm optimization,” The IEEE Congress on Evolutionary Computation, San Francisco, USA: IEEE, 2001, pp. 101 – 106.
[23]王俊偉與汪定偉(2004)：一種帶有梯度加速的的粒子群演算法，控制與決策，第19卷，第11期，pp. 1298-1301。
[24]李愛國(2004)：多粒子群協同優化算法，復旦學報(自然科學版)，第43卷，第5期，pp. 923-925。
[25]俞歡軍、張麗平與陳德劍等(2005)：複合粒子群優化算法在模型參數估計中的應用，高校化學工程學報，第19卷，第5期，pp. 675-680。
[26]孫木楠、史志俊(2004)：基於粒子群優化算法的結構模型修改，震動工程學報，第17卷，第3期，pp. 350-353。
[27]陳貴敏、賈建援與韓琪(2006)：粒子群優化算法的慣性權值遞減策略研究，西安交通大學學報，第40卷，第一期，pp. 53-57。
[28]陸琳、譚清美(2006)：一類隨機需求VRP的混合粒子群算法研究，系統工程與電子技術，第28卷，第2期，pp. 244-247。
[29]黃承龍、王良吉、董吉雄，粒子群最佳化演算法之文獻回顧與研究議題分析，2005數位內容管理與應用研討會，2005。
[30]黃芳、樊曉平(2006)：基於島嶼群體模型的並行粒子群優化算法，控制與決策，第21卷第2期，pp. 175-180。