臺灣博碩士論文加值系統

最佳化是一個被廣泛應用的科學技術，本論文基於粒子群最佳化演算法(Particle Swarm Optimization)提出一個稱為－協作與自適應式粒子群演算法(Collaborative and Adaptive Particle Swarm Optimization)，該機制包含了新的粒子群溝通與學習策略，透過分析菁英粒子群(elitist particles)位置的離散資訊進而影響全體粒子的速度向量。針對求解效能同時兼顧各粒子的多樣性，本研究利用動態機制以隨機的方式選擇使用自適應壓縮因子與三元吸引操作以建構一個新的協同搜尋溝通模式。此策略賦予並保證群種運動之差異同時達到快速收斂與精準搜尋。在實驗方面，本研究選擇了包括多峰標竿測試函數與旅行銷售員(traveling salesman problem)測試集進行比較與驗證。實驗結果顯示，相較於其他PSO演算法，本研究提出之CAPSO演算法在解多峰函數與組合最佳化問題上均有優異的效能表現。

This paper presents a modified of particle swarm optimizations (PSOs), the collaborative and adaptive particle swarm optimization (CAPSO), which uses a novel communication and learning strategy whereby elitist particles’ positional dispersive information is used to influence all particles’ velocity. In order to improve the performance of PSO and maintain particle’s diversity based on randomization, adaptive constriction factors and the triad-attractive operation were brought forward. This strategy enables the diversity of the swarm to be preserved to faster convergence and accuracy. Experiments were conducted on multimodal test functions and traveling salesman problem (TSP). The results demonstrate good performance of the CAPSO in solving multimodal problems and combinatorial optimization problem when compared with other PSOs.

Contents
ABSTRACT I
中文摘要 II
致謝 III
CONTENTS V
LIST OF TABLES VI
LIST OF FIGURES VII
1. INTRODUCTION 1
2. SOME PREVIOUS WORK 3
2.1 PARTICLE SWARM OPTIMIZATION 3
2.2 RECENT VARIANTS OF PSOS 6
2.3 SCHEMA THEORY AND ADAPTIVE ALGORITHM 10
3. COLLABORATIVE AND ADAPTIVE PSO 12
3.1 DISTRIBUTION OF PARTICLES IN THE SEARCH SPACE 13
3.2 FEATURES OF COLLABORATIVE PARTICLE SWARM 15
3.3 FEATURES OF ADAPTIVE CONSTRICTION FACTOR 16
3.4 ADAPTIVE CONSTRICTION FACTOR FOR LOCATION-RELATED PARTICLE SWARM…….. 17
3.5 A TRIAD-ATTRACTIVE OPERATION TO PARTICLE SWARM 23
3.6 HYBRID FROM ALPS AND TOPS IS NAMELY CAPSO 28
4. EXPERIMENTS 30
4.1 NUMERICAL OPTIMIZATION 30
4.1.1 Test Functions 31
4.1.2 Parameters Used for Experiments 35
4.1.3 Experimental Results and Discussions 37
4.2 DYNAMIC ENVIRONMENT 45
4.2.1 Generator Function 45
4.2.2 Experimental Results and Discussions 47
4.3 TRAVELING SALESMAN PROBLEM 49
4.3.1 Benchmark Problems 49
4.3.2 Parameters Used for Experiments 50
4.3.3 Experimental Results and Discussions 51
5. CONCLUSIONS 53
REFERENCES 54
簡 歷 59


List of Tables
TABLE I. COMPARISON CHARACTERISTIC OF TWO OPTIMIZATION ALGORITHM. 11
TABLE II. BENCHMARKS FOR SIMULATIONS 32
TABLE III. PARAMETERS, GLOBAL OPTIMUM AND CRITERIA FOR THE TEST FUNCTIONS 35
TABLE IV. PARAMETER VALUES USED IN EACH PSO 36
TABLE V. SPHERE FUNCTION EVALUATIONS 38
TABLE VI. AXIS PARALLEL HYPER-ELLIPSOID FUNCTION EVALUATIONS 38
TABLE VII. ROSENBROCK FUNCTION EVALUATIONS 38
TABLE VIII. STEP FUNCTION EVALUATIONS 39
TABLE IX. SCHAFFER’S F6 FUNCTION EVALUATIONS 39
TABLE X. GRIEWANK FUNCTION EVALUATIONS 39
TABLE XI. ACKLEY FUNCTION EVALUATIONS 40
TABLE XII. RASTRIGIN FUNCTION EVALUATIONS 40
TABLE XIII. ROBUSTNESS ANALYSIS 44
TABLE XIV. DYNAMIC ENVIRONMENT EVALUATIONS 48
TABLE VII. DESCRIPTION OF TWO BENCHMARK PROBLEMS FOR TSP. 50
TABLE VIII. RESULT COMPARISON OF CAPSO, MPSO AND SGA FOR TSP. 51


List of Figures
FIG. 1: ESSENTIAL OF PARTICLE SWARM OPTIMIZATION. 5
FIG. 2: FLOWCHART OF THE ORIGINAL PSO ALGORITHM. 6
FIG. 3: ESSENTIAL OF PARTICLE SWARM OPTIMIZATION WITH 8
FIG. 4: DIAGRAM ILLUSTRATING THE COMMUNICATION TOPOLOGIES. 9
FIG. 5: THE DISTRIBUTION OF PARTICLES: (A) AT THE 1ST ITERATION; (B) AT THE 10TH ITERATION; (C) AT THE 40TH ITERATION; (D) AT THE 60TH ITERATION; (E) AT THE 80TH ITERATION; (F) AT THE 100TH ITERATION. 14
FIG. 6: REPRESENTATION OF THE SPATIAL KNOWLEDGE AND SCHEMATA OF THE CAPSO ALGORITHM 15
FIG. 7: EXAMPLE OF CONSTRICTION FACTOR (K) RELATIVE TO THE DISTANCE FROM LOCATION TO CORE WITH THE AVERAGE DISTANCE FROM CORE TO EACH ELITE PARTICLE’S POSITION. 16
FIG. 8: PSEUDOCODE FOR THE ALPS ALGORITHM. 20
FIG. 9: THERE ARE USING THE PROCESS TO MAKE THE CORE POSITION, (A) PBEST POSITION (BLACK); (B) OUTSTANDING EXPERIENCE (RED); (C) CORE POSITION (BLUE). 20
FIG.11: PSEUDOCODE FOR THE TOPS ALGORITHM 25
FIG.12: PSEUDOCODE FOR THE CAPSO ALGORITHM 29
FIG. 13: THE DATA FLOW DIAGRAM THE FUNCTION SIMULATION MODEL 31
FIG. 14: THE MESH PLOTTING RETRANSMISSIONS OF THE TEST FUNCTIONS. 34
FIG.15: SPHERE MEAN BEST FUNCTION VALUE PROFILE. 41
FIG.16: AXIS PARALLEL HYPER-ELLIPSOID MEAN BEST FUNCTION VALUE PROFILE. 41
FIG.17: ROSENBROCK MEAN BEST FUNCTION VALUE PROFILE. 42
FIG.18: SCHAFFER’S F6 MEAN BEST FUNCTION VALUE PROFILE. 42
FIG.19: GRIEWANK MEAN BEST FUNCTION VALUE PROFILE. 42
FIG.20: ACKLEY MEAN BEST FUNCTION VALUE PROFILE. 43
FIG.21: RASTRIGIN MEAN BEST FUNCTION VALUE PROFILE. 43
FIG. 22: THE DATA FLOW DIAGRAM THE DYNAMIC ENVIRONMENT SIMULATION MODEL. 45
FIG. 23: THE SHIFT OF DYNAMIC SIMULATION FOR THE GRIEWANK 47
FIG. 24: LENGTH OF THE BEST TOUR VERSUS THE NUMBER OF FITNESS FUNCTION EVALUATIONS PERFORMED BY CAPSO, MPSO AND SGA ALGORITHMS ON TSP 51

[1].AlRashidi, M.R. and El-Hawary, M.E., “A survey of particle swarm optimization application in electric power systems,” IEEE Transactions on Evolutionary Computation: Accepted for future publication, 2006.
[2].Beasley, D., Bull, D.R. and Martin, R.R., “An overview of genetic algorithms,” University Computing, Vol.15, No.2, 1993, pp.58-69.
[3].Van den Bergh, F. and Engelbrecht, A.P., “A cooperative approach to particle swarm optimization,” IEEE Transactions on Evolutionary Computation, Vol.8, 2004, pp.225-239.
[4].Blackwell, T. and Branke, J., "Multiswarms, exclusion, and anti-convergence in dynamic environments," IEEE Transactions on Evolutionary Computation, Vol.10, No.4, Aug. 2006, pp.459-472.
[5].Chen, X. H., Lee, W. P., Liao, C. Y. and Huang, M. L., “Collaborative and Adaptive Particle Swarm Optimizer with Fitness and Position Condition,” IEEE International Conference on Machine Learning and Cybernetics 2007 (ICMLC2007), Hong Kong, August, 2007.
[6].Chen, X. H., Lee, W. P., Liao, C. Y. and Dai, J. T., “Adaptive Constriction Factor for Location-related Particle Swarm,” 8th WSEAS International Conference on Evolutionary Computing (EC '07), Vancouver, June, 2007, pp306-312.
[7].Clerc, M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proceedings of the IEEE Congress on Evolutionary Computation, 1999.
[8].Clerc, M., and Kennedy, J., “The particle swarm-explosion, stability and convergence in a multidimensional complex space,” IEEE Transactions on Evolutionary Computation, Vol.6, no.2, 2002, pp.58-73.
[9].Dorigo, M. and Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1.No.1, 1997.
[10].Dorigo, M., and Stützle, T., “The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” Handbook of Metaheuristics, 2002.
[11].Eberhart, R.C. and Shi, Y., “Comparison between genetic algorithms and particle swam optimization,” Proceedings of the 7th Annual Conference on Evolutionary Programming, Vol.1447, 1998, pp.611-616.
[12].Eberhart, R.C. and Shi, Y., “Comparing inertia weights and constriction factors in particle swarm optimization,” Proceedings of the 2000 Congress on Evolutionary Computation, Vol.1, La Jolla., 2000, pp.84-88.
[13].Eberhart, R.C. and Shi, Y., “Particle Swarm Optimization: Developments, Applications and Resources,” Proceedings of the Congress on Evolutionary Computation 2001, Piscataway, NJ., Seoul, Korea, 2001.
[14].Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA., 1989.
[15].Hatta, K., Wakabayashi, S. and Koide, T., “Adaptation of genetic operators and parameters of a genetic algorithm based on the elite degree of an individual,” System and Computers in Japan, Vol.32, No.1, 2001, pp29-37.
[16].Haupt, L. R. and Haupt, S. E., Practical Genetic Algorithms, John Wiley and Sons Publishers, New York. 2nd edition, 2004.
[17].Higashi, N. and Iba, H., Particle swarm optimization with Gaussian mutation, Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, IN, 2003, pp.72-79.
[18].Holland, J.H., Adaptation in Natural and Artificial systems, MIT Press, 1975.
[19].Hu, X., Shi, Y. and Eberhart, R., “Recent advances in particle swarm,” Proceedings of Congress Evolutionary Computation, Vol.1, 2004, pp.90-97.
[20].Janson, S. and Middendorf, M., “A hierarchical particle swarm optimizer and its adaptive variant,” IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, Vol.35, No.6, 2005, pp.1272-1282.
[21].Kang, Y., “A review of content and formal schemata in ESL reading,” In LORE., Vol.2.1, 2002, pp.39-42.
[22].Kennedy, J. and Eberhart, R.C., “Particle swarm optimization,” Proceedings of the Fourth IEEE International Conference on Neural Networks. Perth, Australia, 1995, pp.1942-1948.
[23].Kennedy, J. and Eberhart, R.C., “A discrete binary version of the particle swarm algorithm,” Proceedings Conference on Systems, Man, and Cybernetics, Piscataway, NJ, 1997, pp.4104-4108.
[24].Kennedy, J., “Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance,” Proceedings of the 1999 IEEE Congress Evolutionary Computation, Piscataway, 1999, pp.1931-1938.
[25].Kennedy, J. and Mendes, R., “Neighborhood topologies in fully informed and best-of-neighborhood particle swarms,” IEEE Transactions on System, Man, and Cybernetics-Part C: Applications and Reviews, Vol.36, No.4, 2006, pp.515-519.
[26].Liang, J.J., Qin, A.K., Suganthan, P.N., and Baskar, S., “Comprehensive learning particle swarm optimizer for global optimization of multimodal functions,” IEEE Transactions on Evolutionary Computation, vol.10, No.3, 2006, pp.281-295.
[27].Liu, J.C. and Hu, Y.Y., “Adaptive genetic algorithm with missed gene detection and reparation policy,” Computer Applications, Vol.26, No.6, 2006, pp.1401-1403. (in Chinese)
[28].Liu, Y., Qin, Z., Shi, Z. and Lu J., “Center Particle Swarm Optimization,” Neurocomputing, Vol.70, 2007, pp.672-679.
[29].Medin, D.L., Ross, B.H. and Markman, A.B., Cognitive Psychology, John Wiley and Sons Publishers, New York. 4th edition, 2004.
[30].Mendes, R., Kennedy, J. and Neves, J., “The fully informed particle swarm: simpler, maybe better,” IEEE Transactions on Evolutionary Computation, Vol.8, No.3, 2004, pp.204-210.
[31].Michalewicz, Z., Genetic Algorithms+ Data Structures = Evolution Programs, Springer-Verlag Berlin Heidelberg, New York, 4th edition, 1999.
[32].Pampara, G., Franken, N. and Engelbrecht, A.P., “Combining particle swarm optimization with angle modulation to solve binary problems,” The 2005 IEEE Congress on Evolutionary Computation, Vol.1, 2005, pp.89-96.
[33].Peram, T., Veeramachaneni, K., Mohan, C.K., “Fitness-distance-ratio based particle swarm optimization,” Proceedings of the 2003 IEEE Swarm Intelligence Symposium, April, 2003, pp.174-181.
[34].Parrott, D. and Li, X., “Locating and tracking multiple dynamic optima by a particle swarm model using speciation,” IEEE Transactions on Evolutionary Computation, Vol.10, No.4, 2006, pp.440-458.
[35].Pang, W., Wang, K.P., Zhou, C.G., Dong, L.J., Liu, M., Zhang, H.Y. and Wang, J.Y., “Modified particle swarm optimization based on space transformation for solving travelling salesman problem,” Proceedings of 2004 International Conference on Machine Learning and Cybernetics, Vol. 4, 26-29 Aug. 2004, pp.2342 – 2346.
[36].Ratnaweera, A., Halgamuge, S.K., and Watson, H.C., “Self-organizing hierarchical particle swarm optimizer with time varying accelerating coefficients,” IEEE Transactions on Evolutionary Computation, vol. 8, 2004, pp. 240–255.
[37].Rumelhart, D.E. and Ortony, A., “The representation of knowledge in memory,” Schooling and the Acquisition of Knowledge, Anderson, R.C., et al. (Eds.) Hillsdale, NJ. Erlbaum, 1977.
[38].Shi, Y. and Eberhart, R.C., “A modified particle swarm optimizer,” Proceedings of IEEE World Congress Computation Intelligence, 1998, pp.69–73.
[39].Shi, Y. and Eberhart, R.C., “Fuzzy adaptive particle swarm optimization,” Proceedings of the 2001 Congress on Evolutionary Computation, Vol.1, 2001, pp.101-106.
[40].Suganthan, P. N., Particle swarm optimizer with neighborhood operator, Proceedings of IEEE International Congress Evolutionary Computation, Vol.3, 1999, pp.1958–1962.
[41].Tawdross, P. and König, A., “Local Parameters Particle Swarm Optimization,” Proceedings of the 6th International Conference on Hybrid Intelligent Systems(HIS’06), Dec. 2006, pp.52-55.
[42].Wang, C., Zhang, J., Yang, J., Hu, C. and Liu, J., “A Modified Particle Swarm Optimization Algorithm and its Application For Solving Travelling Salesman Problem,” International Conference on Neural Networks and Brain, Vol. 2, 13-15 Oct. 2005, pp.689 – 694.
[43].Wang, K.P., Huang, L., Zhou, C.G. and Pang, W., “Particle swarm optimization for travelling salesman problem,” International Conference on Machine Learning and Cybernetics, Vol. 3, 2-5 Nov. 2003, pp.1583 - 1585.
[44].Wolpert, D.H.; Macready, W.G., “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, April 1997, pp.67 – 82.
[45].Zhi, X.H., Xing, X.L., Wang, Q.X., Zhang, L.H., Yang, X.W., Zhou, C.G. and Liang, Y.C., “A discrete PSO method for generalized TSP problem,” Proceedings of 2004 International Conference Machine Learning and Cybernetics, Vol. 4, 26-29 Aug. 2004, pp.2378 - 2383.