臺灣博碩士論文加值系統

本研究提出一不需要花費時間於試誤並試圖求得最佳參數組合之粒子群最佳化演算法(Particle Swarm Optimization; PSO)的變化型。粒子群最佳化演算法被提出後，就因為其架構簡單且求解品質與效率皆不錯的多項優點，廣受學者討論，並提出多種粒子群最佳化演算法之變化型，使其求解品質更佳；但是這些演算法共同的難處是，須耗費相當多的時間與成本，調整最適於該演算法於該問題的參數組合。本研究利用自適應(Self-adaptive)之調整參數的概念，將絕對收斂粒子群最佳化演算法(Guarantee Convergence Particle Swarm Optimization; GCPSO)之策略參數，併入粒子之解編碼當中，令GCPSO之慣性權重、自我認之參數、社交參數與比例因子等四個策略參數，於演算過程中自我調整。本研究所提出之自適應絕對收斂粒子群最佳化演算法測試於低中高三種不同維度的各基準函數(Benchmark Function)，並與其他文獻比較後，結果顯示，本研究所提出之演算法，省去了大量的實驗設計與試誤最佳參數組合的時間，即可達到部分同等，甚至優於文獻之結果，故本研究提出的並非純粹犧牲求解品質以成就求解效率之演算法，而是可大幅縮短整體研究之時間與成本的演算法。

This paper proposes a variant of particle swarm optimization (PSO) with no need of time-consuming fine-parameter adjustment. PSO is considered as an efficient and effective algorithm with simple structure which has been widely discussed and a lot of PSO variants have been suggested to improve PSO performance. However, for almost all these PSO variants, one major mystery is to find out the most appropriate setting of parameters. Since parameter-tuning is inevitable and takes lots of computational time and analysis work, it always becomes a bottleneck of conducting research using metaheuristics. This study uses the concept of self-adaptive parameter control to embed the strategy parameters of guarantee convergence particle swarm optimization (GCPSO) in particle encodings. Therefore, during the process of a run, the proposed algorithm is able to adaptively alter the values of strategy parameters of GCPSO, such as inertia weight, cognition parameter, social parameter, and scaling factor. The results of testing in low, medium, and high dimensional benchmark functions show that the proposed SaGCPSO saves a lot of time of experimental design and parameter-tuning and reaches comparable or even greater level of solution quality comparing with other methods in the literatures. Consequently, the proposed algorithm is not the tradeoff between solution quality and efficiency, but is rather an efficient technique which can reduce the computational effort or cost of the research.

摘 要 I
ABSTRACT II
致謝 III
表目錄 VII
圖目錄 IX
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究架構 4
第二章 文獻探討 7
2.1 參數設定的分類 7
2.1.1 依照參數設定之方法分類 8
2.1.2 依照參數設定之影響階層分類 14
2.1.3 依照參數設定之對象分類 17
2.2 粒子群最佳化演算法 28
2.2.1 發展背景 28
2.2.2 演算方法 29
2.3 粒子群最佳化演算法之參數控制的相關文獻 34
第三章 研究方法 36
3.1 自適應絕對收斂粒子群最佳化演算法之架構 36
3.2 SAGCPSO與GCPSO之比較 43
第四章 結果分析 45
4.1 測試例題介紹 45
4.2 參數設定 54
4.2.1 低中高維度三種結果分析法之介紹與通用之參數設定 55
4.2.2 SaGCPSO與GCPSO之參數設定 58
4.3 SAGCPSO的自適應參數於各維度及各基準函數之收斂情形 59
4.3.1 SaGCPSO的自適應參數於低維度各基準函數之收斂情形 60
4.3.2 SaGCPSO的自適應參數於中維度各基準函數之收斂情形 65
4.3.3 SaGCPSO的自適應參數於高維度各基準函數之收斂情形 70
4.3.4 小結 73
4.4 低維度基準函數演算結果比較 75
4.5 中維度基準函數演算結果比較 81
4.6 高維度基準函數演算結果比較 88
4.7 小結 93
第五章 結論與未來研究方向 95
5.1 結論 95
5.2 未來研究方向 96
參考文獻 97

1.Garey, M.R. and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979: W. H. Freeman & Co.
2.Clarke, G. and J.W. Wright, Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. OPERATIONS RESEARCH, 1964. 12(4): p. 568-581.
3.Kruskal, J.B., On the shortest spanning subtree of a graph and the traveling salesman problem, in Proceedings of the American Mathematical Society. 1956, American Mathematical Society. p. 48.
4.Jarnik, V., O jistem problemu minimalnim [About a certain minimal problem]. Prace Moravske Přirodovědecke Společnosti, 1930. 6: p. 57-63.
5.Prim, R.C., Shortest connection networks and some generalizations. The Bell System technical journal, 1957. 36(6): p. 1389.
6.Osman, I., A Unified-Metaheuristic Framework, in Multiple Approaches to Intelligent Systems, I. Imam, et al., Editors. 1999, Springer Berlin / Heidelberg. p. 11-12.
7.Dorigo, M., Optimization, Learning and Natural Algorithms. 1992, Politecnico di Milano, Italy.
8.Kennedy, J. and R. Eberhart, Particle swarm optimization, in Proceedings of IEEE International Conference on Neural Networks. 1995: Perth, WA, Australia. p. 1942-1948.
9.Mladenović, N. and P. Hansen, Variable neighborhood search. Computers & Operations Research, 1997. 24(11): p. 1097-1100.
10.Van Den Bergh, F. and A.P. Engelbrecht, A new locally convergent particle swarm optimiser, in IEEE International Conference on Systems, Man and Cybernetics. 2002. p. 6.
11.Angeline, P.J., Adaptive and Self-adaptive Evolutionary Computations, in Computational Intelligence: A Dynamic Systems Perspective, M. Palaniswami, et al., Editors. 1995, IEEE Press: New York. p. 152-163.
12.Eiben, A.E., R. Hinterding, and Z. Michalewicz, Parameter Control in Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 1999. 3(2): p. 124-141.
13.Holland, J.H., Adaptation in Natural and Artificial Systems. 1992: MIT Press.
14.Fogarty, T.C., Varying the Probability of Mutation in the Genetic Algorithm, in Proceedings of the 3rd International Conference on Genetic Algorithms. 1989, Morgan Kaufmann Publishers Inc. p. 104-109.
15.Hesser, J. and R. Manner, Towards an Optimal Mutation Probability for Genetic Algorithms, in Proceedings of the 1st Workshop on Parallel Problem Solving from Nature. 1991, Springer-Verlag. p. 23-32.
16.Kirkpatrick, S., C.D. Gelatt, and M.P. Vecchi, Optimization by Simulated Annealing. Science, 1983. 220(4598): p. 671-680.
17.Rechenberg, I., Evolutionsstrategie: optimierung technischer systeme nach prinzipien der biologischen evolution. 1973: Frommann-Holzboog.
18.Spears, W.M., Adapting Crossover in Evolutionary Algorithms, in Proceedings of the 4th Annu. Conf. Evolutionary Programming, J.R. McDonnell, R.G. Reynolds, and D.B. Fogel, Editors. 1995. p. 367-384.
19.Dong, C., et al., A Method of Self-Adaptive Inertia Weight for PSO, in 2008 International Conference on Computer Science and Software Engineering, W. Gaofeng, C. Zhenyi, and Y. Zuqiang, Editors. 2008. p. 1195-1198.
20.Schwefel, H.-P., Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie. 1 ed. 1977, Stuttgart: Birkhauser Basel.
21.Fogel, D.B., L.J. Fogel, and J.W. Atmar, Meta-evolutionary programming, in Proceeding of the 25th Asilomar Conference on Signals, Systems and Computers, R.R. Chen, Editor. 1991, Pacific Grove, CA. p. 540-545.
22.Back, T., Evolutionary algorithms. SIGBIO newsletter, 1992. 12(2): p. 26-31.
23.Hinterding, R., Z. Michalewicz, and T. Peachey, Self-adaptive genetic algorithm for numeric functions, in Parallel Problem Solving from Nature — PPSN IV, H.-M. Voigt, et al., Editors. 1996, Springer Berlin / Heidelberg. p. 420-429.
24.Smith, J. and T. Fogarty, Self adaptation of mutation rates in a steady state genetic algorithm, in IEEE International Conference on Evolutionary Computation. 1996. p. 318-323.
25.Angeline, P.J., Two self-adaptive crossover operators for genetic programming, in Advances in genetic programming. 1996, MIT Press. p. 89-109.
26.Herrera, F. and Lozano, Adaptive Genetic Algorithms Based on Coevolution with Fuzzy Behaviors. 1998, Dept. of Computer Science and A. I., University of Granada, Spain.
27.Smith, J.E., Co-evolving memetic algorithms: A learning approach to robust scalable optimization, in Proceedings of the 2003 Congress on Evolutionary Computation. 2003, IEEE Press. p. 498-505.
28.Krasnogor, N. and S. Gustafson, A Study on the use of ``self-generation'' in memetic algorithms. Natural Computing, 2004. 3(1): p. 53-76.
29.Haupt, R.L. and D.H. Werner, Genetic Algorithms in Electromagnetics. 2007: Wiley-IEEE Press.
30.Al-Anzi, F.S. and A. Allahverdi, A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times. European Journal of Operational Research, 2007. 182(1): p. 80-94.
31.Mezura-Montes, E. and A.G. Palomeque-Ortiz, Parameter control in differential evolution for constrained optimization, in Proceedings of the Eleventh conference on Congress on Evolutionary Computation. 2009, IEEE Press: Trondheim, Norway. p. 1375-1382.
32.Gong, W., Z. Cai, and C. Ling, DE/BBO: a hybrid differential evolution with biogeography-based optimization for global numerical optimization. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 2010.
33.Montalvo, I., et al., Improved performance of PSO with self-adaptive parameters for computing the optimal design of Water Supply Systems. Engineering Applications of Artificial Intelligence, 2010. 23(5): p. 727-735.
34.Dickhaus, T., H. Finner, and V. Gontscharuk, Implicitly adaptive FDR control based on the asymptotically optimal rejection curve, in Department of Mathematics. 2011, Humboldt-University of Berlin: Berlin.
35.Eiben, A.E., R. Hinterding, and Z. Michalewicz, Adaptation in evolutionary computation: a survey, in IEEE International Conference on Evolutionary Computation. 1997. p. 65-69.
36.Darwen, P. and X. Yao, Every Niching Method has its Niche Fitness Sharing and Implicit Sharing Compared, in Parelle Problem Solving from Nature - PPSV IV, H.-M. Voigt, et al., Editors. 1996, Springer, Berlin. p. 398-407.
37.Teller, A., Evolving programmers: the co-evolution of intelligent recombination operators, in Advances in genetic programming. 1996, MIT Press. p. 45-68.
38.Lis, J., Parallel genetic algorithm with the dynamic control parameter, in Proceedings of the IEEE Conference on Evolutionary Computation. 1996, IEEE Press: Piscataway,NY. p. 324-329.
39.Schlierkamp-Voosen, D. and H. Muhlenbein, Adaptation of population sizes by competing subpopulations, in Proceedings of IEEE International Conference on Evolutionary Computation. 1996. p. 330-335.
40.Schaffer, J.D. and A. Morishima, An adaptive crossover distribution mechanism for genetic algorithms, in Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application. 1987, L. Erlbaum Associates Inc.: Cambridge, Massachusetts, United States. p. 36-40.
41.White, T. and F. Oppacher, Adaptive crossover using automata, in Parallel Problem Solving from Nature — PPSN III, Y. Davidor, H.-P. Schwefel, and R. Manner, Editors. 1994, Springer Berlin / Heidelberg. p. 229-238.
42.Rosenberg, R.S., Stimulation of genetic populations with biochemical properties: I. The model. Mathematical Biosciences, 1970. 7(3-4): p. 223-257.
43.Arabas, J., Z. Michalewicz, and J.J. Mulawka, GAVaPS - a Genetic Algorithm with Varying Population Size, in Proceedings of the First IEEE Conference on Evolutionary Computation. 1994, IEEE Press. p. 73-78.
44.Fogel, L.J., P.J. Angeline, and D.B. Fogel, An Evolutionary Programming Approach to Self-Adaptation on Finite State Machines, in Proceedings of the Forth Annual Conference on Evolutionary Programming, J.R. McDonnell, R.G. Reynolds, and D.B. Fogel, Editors. 1995, MIT Press: Massachusetts. p. 355-365.
45.Angeline, P.J. and J. Pollack, Evolutionary Module Acquisition, in Proceedings of the Second Annual Conference on Evolutionary Programming. 1993, MIT Press. p. 154-163.
46.Shaefer, C.G., The ARGOT strategy: adaptive representation genetic optimizer technique, in Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application. 1987, L. Erlbaum Associates Inc.: Cambridge, Massachusetts, United States. p. 50-58.
47.Whitley, D., K. Mathias, and P. Fitzhorn, Delta Coding: An Iterative Search Strategy for Genetic Algorithms, in Proceedings of the Fourth International Conference on Genetic Algorithms. 1991, Morgan Kaufmann. p. 77-84.
48.Schraudolph, N.N. and R.K. Belew, Dynamic Parameter Encoding for Genetic Algorithms. Mach Learn, 1992. 9(1): p. 9-21.
49.Bagley, J.D., The Behavior of Adaptive Systems which Employ Genetic and Correlation Algorithms. 1967, University of Michigan.
50.Greene, F., A method for utilizing diploid/dominance in genetic search, in Proceedings of the First IEEE Conference on Evolutionary Computation. 1994, IEEE Press. p. 439-444.
51.Greene, F., Performance of diploid dominance with genetically synthesized signal processing networks, in Proceedings of the Seventh International Conference on Genetic Algorithms. 1997, Morgan Kaufmann. p. 615-622.
52.Courant, R., Variational methods for the solution of problems of equilibrium and vibrations. Bulletin of American Mathematical Society, 1943. 49: p. 1-23.
53.Carroll, C.W., The Created Response Surface Technique for Optimizing Nonlinear, Restrained Systems. OPERATIONS RESEARCH, 1961. 9(2): p. 169-184.
54.Fiacco, A.V. and G.P. McCormick, Extensions of Sumt for Nonlinear Programming: Equality Constraints and Extrapolation. Management Science, 1966. 12(11): p. 816-828.
55.Dasgupta, D. and Z. Michalewicz, Evolutionary algorithms in engineering applications. 1997, Berlin New York: Springer.
56.Coello Coello, C.A., Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer Methods in Applied Mechanics and Engineering, 2002. 191(11-12): p. 1245-1287.
57.Homaifar, A., C.X. Qi, and S.H. Lai, Constrained Optimization Via Genetic Algorithms. SIMULATION, 1994. 62(4): p. 242-253.
58.Michalewicz, Z., Genetic algorithms + data structures = evolution programs (3rd ed.). 1996, London, UK: Springer-Verlag.
59.Michalewicz, Z., Genetic Algorithms, Numerical Optimization, and Constraints, in Proceedings of the Sixth International Conference on Genetic Algorithms, L.J. Eshelman, Editor. 1995, Morgan Kaufmann: University of Pittsburgh, Morgan Kaufmann, San Mateo, CA. p. 151-158.
60.Joines, J.A. and C.R. Houck, On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA''s, in Proceedings of the First IEEE Conference on Evolutionary Computation. 1994. p. 579-584.
61.Michalewicz, Z. and G. Nazhiyath, Genocop III: A Co-evolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints, in Proceedings of the Second IEEE International Conference on Evolutionary Computation, D.B. Fogel, Editor. 1995, IEEE Press: Piscataway, NJ. p. 647-651.
62.Michalewicz, Z. and M. Schoenauer, Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation, 1996. 4(1): p. 1-32.
63.Michalewic, Z. and N.F. Attia, Evolutionary optimization of constrained problems, in Proceedings of the 3rd Annual Conference on Evolutionary Programming. 1994, World Scientific: Singapore. p. 98-108.
64.Carlson, S.E. and R. Shonkwiler, Annealing a genetic algorithm over constraints, in IEEE International Conference on Systems, Man, and Cybernetics. 1998. p. 3931-3936.
65.Ben Hadj-Alouane, A. and J.C. Bean, A Genetic Algorithm for the Multiple-Choice Integer Program. OPERATIONS RESEARCH, 1997. 45(1): p. 92-101.
66.Smith, A.E. and D.M. Tate, Genetic Optimization Using A Penalty Function, in Proceedings of the 5th International Conference on Genetic Algorithms. 1993, Morgan Kaufmann Publishers Inc. p. 499-505.
67.Coit, D.W. and A.E. Smith, Penalty guided genetic search for reliability design optimization. Computers & Industrial Engineering, 1996. 30(4): p. 895-904.
68.Coit, D.W., A.E. Smith, and D.M. Tate, Adaptive Penalty Methods for Genetic Optimization of Constrained Combinatorial Problems. INFORMS JOURNAL ON COMPUTING, 1996. 8(2): p. 173-182.
69.Coello Coello, C.A., Use of a self-adaptive penalty approach for engineering optimization problems. Computers in Industry, 2000. 41(2): p. 113-127.
70.De Jong, K.A., An analysis of the behavior of a class of genetic adaptive systems. 1975, University of Michigan.
71.Grefenstette, J., Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 1986. 16(1): p. 122-128.
72.Karaboga, D. and B. Akay, A comparative study of Artificial Bee Colony algorithm. Applied Mathematics and Computation, 2009. 214(1): p. 108-132.
73.Shi, Y. and R. Eberhart, A modified particle swarm optimizer, in Proceedings of the IEEE International Conference on Evolutionary Computation 1998. p. 69-73.
74.Shi, Y. and R. Eberhart, Parameter selection in particle swarm optimization, in Evolutionary Programming VII, V. Porto, et al., Editors. 1998, Springer Berlin / Heidelberg. p. 591-600.
75.Fan, H.Y., A modification to particle swarm optimization algorithm. Engineering Computations, 2002. 19(7-8): p. 970-989.
76.Clerc, M. and J. Kennedy, The particle swarm - Explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002. 6(1): p. 58-73.
77.Jin, Y.-X., et al., New discrete method for particle swarm optimization and its application in transmission network expansion planning. Electric Power Systems Research, 2007. 77(3-4): p. 227-233.
78.Kennedy, J.F., R.C. Eberhart, and Y. Shi, Swarm intelligence. The Morgan Kaufmann series in evolutionary computation. 2001, San Francisco: Morgan Kaufmann Publishers.
79.Arumugam, M.S. and M.V.C. Rao, On the improved performances of the particle swarm optimization algorithms with adaptive parameters, cross-over operators and root mean square (RMS) variants for computing optimal control of a class of hybrid systems. Applied Soft Computing, 2008. 8(1): p. 324-336.
80.Ratnaweera, A., S.K. Halgamuge, and H.C. Watson, Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 2004. 8(3): p. 240-255.
81.Clerc, M. and J. Kennedy, The particle swarm - explosion, stability, and convergence in a multidimensional complex space. Evolutionary Computation, IEEE Transactions on, 2002. 6(1): p. 58-73.
82.Chelouah, R. and P. Siarry, A hybrid method combining continuous tabu search and Nelder-Mead simplex algorithms for the global optimization of multiminima functions. European Journal of Operational Research, 2005. 161(3): p. 636-654.
83.Liang, J.J., et al., Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006. 10(3): p. 281-295.
84.Fan, S.-K. and J.-M. Chang, Dynamic multi-swarm particle swarm optimizer using parallel PC cluster systems for global optimization of large-scale multimodal functions. Engineering Optimization, 2010. 42(5): p. 431-451.
85.Molga, M. and C. Smutnicki. Test functions for optimization needs. 2005; Available from: http://www.zsd.ict.pwr.wroc.pl/files/docs/functions.pdf.
86.Yang, X.-S. Test Problems in Optimization. Engineering Optimization: An Introduction with Metaheuristic Applications 2010; Available from: http://arxiv.org/abs/1008.0549v1.