臺灣博碩士論文加值系統

本篇論文提出粒子行為分析之多族群演算法(Behavior Analyzed Multi-modal Particle Swarm Optimization，BAMPSO)嘗試解決陷入局部解的問題。BAMPSO不僅可以運用在單目標最佳化問題，對於多目標最佳化問題也可獲得不錯的成效。BAMPSO主要是經由分析粒子移動時的特性及其適應值(Fitness Value)相對應之變化，尋找問題空間中所有的空間解，若已獲得大部份的空間解，只需要經過空間解的適應值之比較，即可得到全域最佳解(Global Solution)。BAMPSO可以避免粒子落入局部解及過早收斂(Convergence)之困擾，同時也可提高處理多目標最佳化問題的能力。基於粒子行為分析之多族群演算法之經驗，引入線上參數調適的概念結合粒子行為分析之多族群演算法之方式，提出了粒子行為線上分析之多族群演算法(Behavior Analyzed Adaptive Particle Swarm Optimization，BAAPSO)，可以線上處理多目標最佳化的問題，使其具有線上更新參數以及針對全域最佳解處提高精確度之搜尋功能，提升整體之搜尋效能。最後以四種不同複雜程度之測試函數(Test Function)為範例，針對本論文所提出的BAMPSO及BAAPSO與其它已提出的改良式粒子群演算法進行比較。

In this thesis, a new behavior analyzed multimodal particle swarm optimization (BAMPSO) algorithm is proposed for not only unimodal problems but multi-modal problems. The main idea is to find the local minima by analyzing the variation of the fitness value when the particles are moving. Since almost all the local minima are found, the global minimum can be obviously obtained. That is, the BAMPSO can avoid converging to local solution and efficiently find the global solution. Moreover, the behavior analyzed adaptive particle swarm optimization (BAAPSO) algorithm based on the same idea to on-line search the global minimum is also provided. BAAPSO algorithm can on-line to adjust parameters and improve the accuracy on searching for multi-objection problem. Experiment results and comparisons with other PSO algorithms are included to indicate the effectiveness of the proposed BAMPSO and BAAPSO algorithms.

誌謝 Ⅰ
摘要 Ⅱ
Abstract Ⅲ
目錄 Ⅵ
圖目錄 Ⅶ
表目錄 Ⅸ
1. 緒論 1
1.1. 前言 1
1.2. 研究動機 2
1.3. 研究目的 4
1.4. 文獻探討 5
1.5. 論文架構 9
2. 啟發式演算法 11
2.1. 模擬退火法 11
2.2. 禁忌搜尋法 11
2.3. 基因演算法 12
2.4. 螞蟻最佳化演算法 13
2.5. 粒子群最佳化演算法 13
2.5.1. 粒子群演算法發展 14
2.5.2. 粒子群演算法概念 15
2.5.3. 粒子群演算法應用 20
3. 粒子群演算法之改善 22
3.1. 慣性權重之粒子群演算法 22
3.2. 時變慣性權重參數之粒子群演算法 23
3.3. 收縮係數之粒子群演算法 23
3.4. 最大速度之粒子群演算法 24
3.5. 時變加速係數之粒子群演算法 25
3.6. 多族群粒子群演算法 25
4. 改良型自多族群粒子群演算法 27
4.1. 粒子行為分析之多族群最佳化演算法 27
4.1.1. 定義參數及執行PSO三次迭代 28
4.1.2. 選取區域代表之粒子 28
4.1.3. 在區域代表粒子間產生虛擬點 31
4.1.4. RP粒子分群準則 32
4.1.5. RP粒子分類成多個族群 33
4.1.6. 建立適當的族群數 37
4.1.7. RP族群搜尋空間解 38
4.1.8. 空間角落當成準局部最小值 40
4.1.9. 檢查NLM之間的區域解 41
4.1.10. 區分TLM與精鍊局部最小值 42
4.2. 粒子行為線上分析之多族群最佳化演算法 44
4.2.1. 定義參數及執行PSO三次迭代 45
4.2.2. 選取區域代表之粒子 45
4.2.3. 在區域代表之粒子之間產生虛擬點 45
4.2.4. RP粒子分類準則 45
4.2.5. RP粒子分類成多個族群 45
4.2.6. 建立適當的族群數 45
4.2.7. RP族群搜尋空間解 45
4.2.8. 確認誤差標準 45
4.2.9. 精鍊全域最小值 45
5. 測試函數之驗證 47
5.1. BAMPSO應用於二維度之測試函數 52
5.2. BAMPSO與BAAPSO應用於三十維度之測試函數 56
6. 結論與未來展望 61
6.1. 結論 61
6.2. 未來展望 61
參考文獻 63

[1] J. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[2] Metropolis, N., Rosenbluth, A.W., and Teller, A.H., “Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 21, 1087-1092, (1953).
[3] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: optimization by acolony of cooperating agents,” IEEE Trans. on Systems, Man, and Cybernetics-Part B, pp. 29-41, 1996.
[4] Kennedy, J. and Eberhart, R.C. (1995). “Particle swarm optimization,” Proceedings of the IEEE International Conference on Neural Networks, Vol. 4, 1942-1948, Perth, Australia, IEEE, Piscataway, NJ, USA.
[5] Eberhart, R.C. and Kennedy, J. (1995). “A new optimizer using particle swarm theory,” Proceedings of the 6th International Symposium on MicroMachine and Human Science, 39-43, Nagoya, Japan, IEEE, Piscataway, NJ, USA.
[6] Eberhart, R. and Kennedy, J. (1997). “A discrete binary version of the particle swarm algorithm,” Proceedings of the IEEE International Conference on Systems, Vol 5, 4104-4108, Man and Cybernetics, IEEE, Piscataway, NJ, USA.
[7] Kennedy, J. (1997). “The particles swarm: Social adaptation of knowledge,” Proceedings of the 1997 International Conference on Evolutionary Computation, 303-308, Indianapolis, IN, USA, IEEE, Piscataway, NJ,USA.
[8] Shi, Y. and Eberhart, R. (1998). “A modified particle swarm optimizer,” Proceedings of the IEEE International Conference on Evolutionary Computation, 69-73, Anchorage, AK, USA, IEEE, Piscataway, NJ, USA.
[9] Shi, Y. and Eberhart, R., (1998). “Parameter selection in particle swarm optimization,” Lecture Notes in Computer Science, Vol. 1447, 591.
[10] Angeline, P. J. (1998). “Using selection to improve particle swarm optimization,” Proceedings of the 1998 International Conference on Evolutionary Computation, 84-89. Anchorage, AK, USA, IEEE, Piscataway, NJ, USA.
[11] Shi, Y. and R. Eberhart, “Empirical Study of Particle Swarm Optimization”, in Proc of the IEEE Int. Congr. Evolutionary Computation, Vol. 3, pp. 1958-1962, 1999.
[12] Clerc, M. (1999), “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proc. 1999 Congress on Evolutionary Computation, Washington, DC, pp. 1951-1957.
[13] Eberhart, R.C. and Shi, Y. (2000), “Comparing inertia weights and constriction factors in particle swarm optimization,” Proceeding of the 2000 Congress of Evolutionary Computation, Vol. 1, 84-88, California, CA, USA, IEEE, Piscataway, NJ, USA.
[14] Davis L. (Ed.). (1991). Handbook of genetic algorithms. New York: Van Nostrand Reinhold.
[15] Carlisle, A. and Dozier, G. (2001), “An Off-the-shelf PSO,” Proceedings of the Workshop on Particle Swarm Optimization, 1-6. Indianapolis, Indiana, USA.
[16] Z. Li-Ping, Y. Huan-Jun, and H. Shang-Xu, (2005), “Optimal choice of parameters for particle swarm optimization,” Journal of Zhejiang University: Science, Vol 6 A, 528-534, Zhejiang University, Hangzhou, 310027, China.
[17] R. C. Eberhart and Y. Shi, “Tracking and optimizing dynamic systems with particle swarms,” Proceedings of the 2001 Congress on Evolutionary Computation, 2001., pp. 94–97, May 2001.
[18] Fourie, P.C. and Groenwold, A.A. (2002), “The particle swarm optimization algorithm in size and shape optimization,” Structural and Multidisciplinary Optimization, Vol. 23, 259–267, Springer Verlag.
[19] YONG-LING Z., LONG-HUA M., LI-YAN Z. and JI-XIN Q. (2003), “On the convergence analysis and parameter selection in particle swarm optimization,” Proceedings of the 2nd International Conference on Machine Learning and Cybernetics, Vol. 3, 1802-1807, Xi'an, China, Institute of Electrical and Electronics Engineers Inc.
[20] R. Boyd and P. J. Richerson, “Culture and the Evolutionary Process”, Chicago, The University of Chicago Press, 1985
[21] C. W. Reynolds (1987), “Flocks, herds and schools: A distributed behavioral model”, Proc. of the 14th annual conference on Computer graphics and interactive techniques, ACM Press, pp. 25–34.
[22] Eberhart, R. and Kennedy, J. (1997), “A discrete binary version of the particle swarm algorithm”, Proceedings of the IEEE International Conference on Systems, Vol 5, 4104-4108, Man and Cybernetics, IEEE, Piscataway, NJ, USA.
[23] Fukuyama, Y. and Yoshida, H. (2001), “A particle swarm optimization for reactive power and voltage control in electric power systems”, Proceedings of the IEEE Conference on Evolutionary Computation 2001, 87-93, Soul.
[24] He, S.,Wen, J.Y., Prempain, E., Wu, Q.H., Fitch, J. and Mann, S., “An improved particle swarm optimization for optimal power flow”, Power System Technology. PowerCon. 2004 Internationa Conference.Vol.2, 21-24 Nov. pp.1633 - 1637 Vol.2
[25] Yoshida, H., Kawata, K., Fukuyama, Y., Takayama, S. and Nakanishi, Y., “A particle swarm optimization for reactive power and voltage control considering voltage security assessment”, IEEE Transactions on Power Systems,Vol.15, Issue 4, Nov. 2000.pp.1232 – 1239
[26] A.M. El-Zonkoly, A.A. Khalil and N.M. Ahmied, “Optimal tunning of lead-lag and fuzzy logic power system stabilizers using particle swarm optimization”, Expert Systems with Applications, Vol. 36, Issue 2, Part 1, March 2009, pp.2097-2106
[27] Chun-Chieh Tseng, Jer-Guang Hsieh and Jyh-Horng Jeng, “Fractal image compression using visual-based particle swarm optimization”, Image and Vision Computing, Vol. 26, Issue 8, 1 August 2008, pp.1154-1162
[28] Cheng-Jian Lin, Yong-Cheng Liu, “Image backlight compensation using neuro-fuzzy networks with immune particle swarm optimization”, Expert Systems with Applications, In Press, Corrected Proof, Available online 2 July 2008
[29] Zhang, Xueying, Sun, Ying, Zhang, Xiaomei, Wang and Peng, “A Fuzzy Neural Network Based on Particle Swarm Optimization Applied in the Speech Recognition System”, Intelligent Systems Design and Applications, 2008. ISDA '08. Eighth International Conference. Vol. 2, 26-28 Nov. pp.693 - 697
[30] Fu-yuan and Huang, “A Particle Swarm Optimized Fuzzy Neural Network for Credit Risk Evaluation”, Genetic and Evolutionary Computing, 2008. WGEC '08. Second International Conference. 25-26 Sep. pp.153 - 157
[31] Karim H., Youssef, Hasan A., Yousef, Omar A., Sebakhy, Manal A. and Wahba, “Adaptive fuzzy APSO based inverse tracking-controller with an application to DC motors”, Expert Systems with Applications, Vol. 36, Issue 2, Part 2, March 2009. pp. 3454-3458
[32] Hakim, E.A., Suprijanto, A., and Heri P, M., “PSS based on optimal fuzzy PID with Particle Swarm Optimization”, Power Engineering Conference, IPEC 2007. International3-6 Dec. pp.1396 – 1400
[33] V. Mukherjee, S.P. Ghoshal, “Intelligent particle swarm optimized fuzzy PID controller for AVR system”, Electric Power Systems Research, Volume 77, Issue 12, October 2007, pp. 1689-1698
[34] Clerc, M., and Kennedy, J. (2000). “The particle swarm: Explosion, stability, and convergence in a multimodal complex space,” Proceedings of the Congress of Evolutionary Computation, Vol. 6, 58-73, Washington DC, IEEE, Piscataway, NJ, USA.
[35] Eberhart, R.C. and Shi, Y., 2001, “Particle Swarm Optimization: Developments, Application and Resources”, Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, South Korea, Vol. 1, pp. 81-86.
[36] P. N. Suganthan, “Particle Swarm Optimiser with Neighbourhood Operator,” in Proceedings of the 1999 Congress on Evolutionary Computation, 1999. CEC 99., Vol.3, pp. 101-106, 1999.
[37] A. Ratnaweera, S. K. Halgamuge, and H. C. Watson, “Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients,” IEEE Trans. on Evol. Comput., Vol. 8, No. 3, pp. 240–255, Mar. 2004.
[38] Jang-Ho Seo, Chang-Hwan Im, Chang-Geun Heo, Jae-Kwang Kim, Hyun-Kyo Jung and Cheol-Gyun Lee, “Multimodal function optimization based on particle swarm optimization”, IEEE Transactions on Magnetics,Vol. 42, pp.1095 – 1098 April 2006.
[39] Ho, S.L.; Shiyou Yang; Guangzheng Ni; Lo, E.W.C.; Wong, H.C, “A particle swarm optimization-based method for multi-objective design optimizations”, IEEE Transactions on Magnetics, Vol. 41, issue 5, pp. 1756–1759, May 2005
[40] Tao Li; Chengjian Wei; Wenjang Pei, “PSO with sharing for multimodal function optimization”, Neural Networks and Signal Processing, 2003. International Conference on Proceedings, Vol.1, pp.450 – 453, Dec 2003
[41] P. Angeline, “Evolutionary optimization versus particle swarm optimization:
Philosophy and performance differences,” in Evolutionary Programming VII, Eds. Berlin, Germany, 1998, pp. 601–610.
[42] Ling, S.H., Iu, H.H.C., Chan, K.Y., Lam, H.K., Yeung, B.C.W. and Leung, F.H., “Hybrid Particle Swarm Optimization With Wavelet Mutation and Its Industrial Applications,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol. 38, No. 3, pp.743 – 763, June 2008.
[43] A. A. E. Ahmed, L. T. Germano, and Z. C. Antonio, “A hybrid particle swarm optimization applied to loss power minimization,” IEEE Trans. on Power Syst. Vol. 20, No. 2, pp. 859–866, May 2005.
[44] C. F. Juang, “A hybrid of genetic algorithm and particle swarm optimization for recurrent network design,” IEEE Trans. on Syst., Man, Cybern. B, Cybern. Vol. 34, no. 2, pp. 997–1006, Apr. 2004.
[45] M. M. Noel and T. C. Jannett, “Simulation of a new hybrid particle swarm optimization algorithm,” in Proc 36th Southeastern Symp. Syst. Theory, pp. 150–153, 2004.
[46] Kennedy, J., Eberhart, R.C. and Shi, Y. ( 2001). Swarm intelligence San Francisco: Morgan Kaufmann Publishers.
[47] F. Glover, “Tabu search, Part I,” ORSA Journal on Computing, Vol. 1, 1989, pp. 190–206
[48] De Jong, K. A., “An Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph. D. Dissertation, University of Michigan, Ann Arbor, 1975.
[49] 蘇昱豪，2006，具隨機粒子與微調機制式粒子群最佳化於多極值函數問題之研究，國立台灣科技大學，碩士論文。
[50] 吳文棋，2008，跳躍更新的多目標粒子群最佳化演算法，國立東華大學，碩士論文。