臺灣博碩士論文加值系統

質群演算法（PSO）發展至今，許多由原始型改善而得之變化型亦有學者陸續發表。PSO的整體概念既簡單易懂，又能夠以較快速又較節省成本的方式獲得結果，便成為研究的初步動機；再加上原始型PSO於多組解最佳化問題的求解效率與收斂速度不佳，更促使本論文針對多組解最佳化問題展開研究，並且提出一適用於求解大型多組解最佳化問題的PSO方法。
在研究初期，使用實驗設計（DOE）的技術用以探討PSO的主要參數對整體演算法效果與效率之影響，由實驗設計的全因子分析所得之參數效果圖表與數據結果，提出一改善方案，稱為DW-PSO（Decreasing Weight Particle Swarm Optimization）。演算法的成功率和運算次數作為衡量指標，實驗結果顯示DW-PSO能夠解決多組解方程最佳化問題，除此之外，更進一步地將各式多組解最佳化方程同樣地套用於DW-PSO與其他學者所提出的PSO方法，由其比較結果可知，DW-PSO對大型多組解最佳化問題的求解表現與其他PSO方法相較之下，成功尋找總體最佳解之效果尤其顯著。

The development of the Particle Swarm Optimization (PSO) has been almost ten years since 1995. From that time on, a variety of modifications of the original PSO has been proposed by many PSO researchers. The evolutionary concept of PSO, simple in concept, easy to implement and computational efficient, is partly the motivation of this thesis. The performance of the original PSO on the solution quality and convergence speed becomes much aggravated while optimizing multimodal functions with higher dimension. This is the main objective of this research such that we would like to develop a modified PSO suitable for solving large-scale multimodal optimization problems.
In this study, design of experiments (DOE) has been conducted to investigate the influences of each parameter in PSO. Based the computation results in the DOE stage, a modified PSO, termed Decreasing Weight Particle Swarm Optimization (DW-PSO), has been addressed. The success rate and number of function evaluation are considered performance measures. The experimental results show that the DW-PSO shows great promise in solving multimodal functions. The computational comparisons with PSO variants further reveal that DW-PSO has significant advantages, especially when it is performed to solve high dimension problems.

TABLE OF CONTENTS
ABSTRACT i
摘要 ii
LIST OF TABLES v
LIST OF FIGURES vi
Chapter 1: INTRODUCTION 1
1.1 Background 1
1.2 Motivation 2
1.3 Research Goals and Objectives 3
1.4 Organization of the Thesis 4
Chapter 2: LITERATURE REVIEW 6
2.1 Evolutionary Computation 6
2.1.1 Genetic Algorithms 8
2.1.2 Evolutionary Programming 10
2.1.3 Evolution Strategies 11
2.2 Particle Swarm Optimization 13
2.2.1 Basic Particle Swarm Optimization 13
2.2.2 Development of Particle Swarm Optimization 16
2.2.3 Parameters of Particle Swarm Optimization 21
2.3 Methodologies of Multimodal Functions 23
Chapter 3: RESEARCH METHOD AND DOE RESULTS 28
3.1 Preliminaries 28
3.2 Parameter Selection by Using Design of Experiments (DOE) 31
3.3 Analysis of Experimental Results 34
3.4 Recommendation and Comments 38
Chapter 4: COMPUTATIONAL EXPERIMENTS 43
4.1 Modified Particle Swarm Optimization Focusing on Inertia Weight 43
4.2 The Computational Results of DW-PSO and PSO Variants 45
Chapter 5: CONCLUSION 50
REFERENCES 53
APPENDIX 59

REFERENCES
[ 1 ] Abido, M. A. (2002) Optimal Power Flow Using Particle Swarm Optimization, Electrical Power and Energy Systems, 24, 563-571.
[ 2 ] Bilbro, G. L. and Snyder W. E. (1991) Optimization of Functions with Many Minima, IEEE Transactions on Systems, Man and Cybernetics, 21, No. 4, 840-849.
[ 3 ] Bagley, J.D. (1967) The Behavior of Adaptive Systems Which Employ Genetic and Correlation Algorithms, Ph. D. dissertation, University of Michigan, Ann Arbor.
[ 4 ] Clerc, M. (1999) The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization. Proceedings of the Congress on Evolutionary Computation, Washington D.C., USA, 3, 1951-1957.
[ 5 ] Carlisle, A. J. (2002) Applying the Particle Swarm Optimizer to Non-stationary Environments, Auburn University, Auburn, Alabama.
[ 6 ] Chelouah, R. and P. Siarry (2000) A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions, Journal of Heuristics, 6, 191-213.
[ 7 ] Chelouah, R. and P. Siarry (2000) Tabu Search Applied to Global Optimization, European Journal of Operational Research, 123, 256-270.
[ 8 ] Chelouah, R. and P. Siarry (2003) Genetic and Nelder-Mead Algorithms Hybridized for a More Accurate Global Optimization of Continuous Multiminima Functions, European Journal of Operational Research, 148, 335-348.
[ 9 ] Chelouah, R. and P. Siarry (2004) An Hybrid Method Combining Continuous Tabu Search and Nelder-Mead Simplex Algorithms for the Global Optimization of Multiminima Functions, European Journal of Operational Research (to appear).
[ 10 ] De Jong, K. A. (1975) An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Doctoral Dissertation, University of Michigan, Ann Arbor.
[ 11 ] Eshelman, L. J. and J. D. Schaffer (1991) Preventing Premature Convergence in Genetic Algorithms by Preventing Incest, Proceedings of the Fourth International Conference on Genetic Algorithms, La Jolla, CA: Morgan Kaufmann, 115-122.
[ 12 ] Eberhart, R. C. and J. Kennedy (1995) A New Optimizer Using Particle Swarm Theory, Sixth International Symposium on Micro Machine and Human Science, IEEE Service Center, Nagoya, Japan, 39-43.
[ 13 ] Eberhart, R. C. and Y. Shi (2000) Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization. Proceedings of the Congress on Evolutionary Computing, San Diego, CA, USA, 84-89.
[ 14 ] Fogel, L. J., A. J. Owens and M. J. Walsh (1966) Artificial Intelligence through Simulated Evolution, New York: John Wiley and Sons.
[ 15 ] Fogel, L. J. (1994) Evolutionary Programming in Perspective: the Top-down View, Computational Intelligence: Imitating Life, 135-146.
[ 16 ] Fan, H. (2002) A Modification to Particle Swarm Optimization Algorithm, Engineering Computations, 19, No. 8, 970-989.
[ 17 ] Fan, S. K., Y. C. Liang and E. Zahara (2004) Hybrid Simplex Search and Particle Swarm Optimization for the Global Optimization of Multimodal Functions, Engineering Optimization, 36, 401-418.
[ 18 ] Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA: Addision-Wesley.
[ 19 ] Goldberg, D. E., K. Deb and B. Korb (1991) Don’t Worry, Be Messy, Proceeding of the Fourth International Conference on Genetic Algorithms, La Jolla, CA: Morgan Kaufmann, 24-30.
[ 20 ] Holland, J. (1975) Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI.
[ 21 ] Holland, J. (1986) Escaping Brittleness: the Possibilities of General-purpose Learning Algorithms Applied to Parallel Rule-based Systems, Machine Learning: an Artificial Intelligence Approach, Los Altos: Morgan Kaufmann.
[ 22 ] Kennedy, J. and R. C. Eberhart (1995) Particle Swarm Optimization, Proceeding of the IEEE International Conference on Neural Networks, IEEE Service Center, Piscataway, NJ, 1942-1948.
[ 23 ] Kennedy, J. and W. M. Spears (1998) Matching Algorithms to Problems: An Experimental Test of the Particle Swarm and Some Genetic Algorithms on the Multimodal Problem Generator, Proceedings of the International Conference on Evolutionary Computation, Anchorage, Alaska, 78-83.
[ 24 ] Kennedy, J., R. C. Eberhart and Y. Shi (2001) Swarm Intelligence, Morgan Kaufmann.
[ 25 ] Kannan, S., S. Mary Raja Slochanal, P. Subbaraj and N. Prasad Padhy (2004) Application of Particle Swarm Optimization Technique and Its Variants to Generation Expansion Planning Problem, Electric Power Systems Research, 70, 203-210.
[ 26 ] Lovbjerg, M. and T. Krink (2002) Extending Particle Swarm Optimizers with Self-Organized Criticality, Proceedings of Fourth Congress on Evolutionary Conference, 2, 1588-1593.
[ 27 ] Laguna, M. and R. Martí (2002) Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions (Submitted for Publication).
[ 28 ] Onwubolu, G. and M. Clerc (2004) Optimal Operating Path for Automated Drilling Operations by a New Heuristic Approach Using PSO, International Journal of Production Research, 42, No. 3, 473-491.
[ 29 ] Peer, E. S., F. van den Bergh and A. P. Engelbrecht (2003) Using Neighborhoods with the Guaranteed Convergence PSO, Proceedings of the 2003 IEEE Swarm Intelligence Symposium, Indiana, USA, 235-242.
[ 30 ] Rechenberg, I. (1965) Cybernetic Solution Path of an Experimental Problem, Library translation No 1122, Royal Aircraft Establishment, Farnborough, HK.
[ 31 ] Rechenberg, I. (1973) Evolutionsstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution, Stuttgart, Germany: Frommann-Holzboog Verlag.
[ 32 ] Schwefel, H. P. (1965) Kybernetische Evolution als Strategie der experimentellen Forschung in der StrØmungstechnik, Diplomarbeit, Techniche Universität, Berlin.
[ 33 ] Schwefel, H. P. (1981) Numerical Optimization of Computer Models, New York: John Wiley and Sons.
[ 34 ] Spears, W. M., K. A. De Jong, T. Baeck, D. B. Fogel and H. de Garis (1993) An Overview of Evolutionary Computation, Proceedings of the European Conference on Machine Learning, P. B. Brazdil, Ed., 667, Springer Verlag, 442-459.
[ 35 ] Shi, Y. and R. C. Eberhart (1998) A Modified Particle Swarm Optimizer, Proceedings of IEEE International Conference of Evolutionary Computation, Anchorage, Alaska, 69-73.
[ 36 ] Shi, Y. and R. C. Eberhart (1998) Parameter Selection in Particle Swarm Optimization, Evolutionary Programming VII: Proceedings of 7th Annual Conference on Evolutionary Programming, Springer, Berlin, 591-600.
[ 37 ] Shi, Y. and R. C. Eberhart (1999) Empirical Study of Particle Swarm Optimization, Proceedings of the Congress on Evolutionary Computation, Washington, D.C., USA, 1945-1949.
[ 38 ] Shi, Y. and R. C. Eberhart (2001) Fuzzy Adaptive Particle Swarm Optimization, Proceedings of the 2001 Congress on Evolutionary Computation, 1, 101-106.
[ 39 ] Siarry, P. and M. Bessaou (2001) A Genetic Algorithm with Real-code to Optimize Multimodal Continuous Functions, Structural Multidisciplinary Optimal, 23, 63-74.
[ 40 ] Siarry, P., A. Pétrowski and M. Bessaou (2002) A Multipopulation Genetic Algorithm Aimed at Multimodal Optimization, Advances in Engineering Software, vol. 33, 207-213.
[ 41 ] Salman, A., I. Ahmad and S. Al-Madani (2002) Particle Swarm Optimization for Task Assignment Problem, Microprocessors and Microsystems, 26, 363-371.
[ 42 ] Tandon, V., H. El-Mounayri and H. Kishawy (2002) NC End Milling Optimization Using Evolutionary Computation, International Journal of Machine Tools and Manufacture, 42, 595-605.
[ 43 ] Van den Bergh, F. and A. Engelbrecht (2002) A New Locally convergent particle swarm optimizer, Proceedings of IEEE Conference on systems, Man and Cybernetics, Hammamet, Tunisia, 96-101.
[ 44 ] Van den Bergh, F. (2002) An Analysis of Particle Swarm Optimizers, PhD thesis, Department of Computer Science, University of Pretoria, South Africa.
[ 45 ] Van den Bergh, F. and A. P. Engelbrecht (2004) A Cooperative Approach to Particle Swarm Optimization, IEEE Transactions on Evolutionary Computation, 8, 225- 239.
[ 46 ] Xie, X. F., W. J. Zhang and Z. L. Yang (2002) Hybrid Particle Swarm Optimizer with Mass Extinction, International Conference on Communication, Circuits and Systems (ICCCAS), Chengdu, China.
[ 47 ] Xie, X. F., W. J. Zhang and Z. L. Yang (2002) A Dissipative Particle Swarm Optimization, IEEE Congress on Evolutionary Computation, Honolulu, Hawaii, USA, 1456-1461.
[ 48 ] Yoshida, H., K. Kawata, Y. Fukuyama, S. and Y. Nakanishi (1999) A Particle Swarm Optimization for Reactive Power and Voltage Control Considering Voltage Stability, IEEE International Conference on Intelligent System Applications to Power Systems, Brazil, 117-121..
[ 49 ] Zhang, L., H. Yu and S. Hu (2003) A New approach to improve Particle Swarm Optimization, Proceedings of the Genetic and Evolutionary Computation Conference, 134-139.