研究生: |
黃國玉 Kuo-yu Huang |
---|---|
論文名稱: |
混沌啟發式演算法之動態導引與類聚分群模式 Dynamic Guiding and Clustering Approach in Chaos Heuristic Algorithms |
指導教授: |
鄭明淵
Min-Yuan Cheng |
口試委員: |
王維志
Wei-Chih Wang 曾惠斌 Hui-Ping Tserng 張行道 Shing-Tao Chang 余文德 Wen-Der Yu 陳鴻銘 Hung-Ming Chen |
學位類別: |
博士 Doctor |
系所名稱: |
工程學院 - 營建工程系 Department of Civil and Construction Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 中文 |
論文頁數: | 83 |
中文關鍵詞: | 混沌映射 、粒子群最佳化演算法 、基因演算法 、K-means演算法 |
外文關鍵詞: | Chaos Mapping, Particle Swarm Optimization, Genetic Algorithms, K-means Algorithms |
相關次數: | 點閱:319 下載:7 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本研究所提出以基因演算法為基礎的架構,係依混沌映射及類聚分群的模式,並承續基因演算法的特性所構成。混沌映射的遍歷、不重複的特性,可以有效的提昇尋獲最佳解的效率;而援引類聚分群演算法的群聚特性,可以增進系統的收斂效果。在結合上述混沌、類聚分群、基因演算法等各演算邏輯的新演算法中,將展現出優異的演化效果。
研究中所提出將粒子群最佳化演算法,結合混沌映射和動態導引機制後,即擁有遍歷、不重複和動態、難以預測的屬性;進一步將混沌映射轉化為搜尋機制後,並配合對全域最佳解動態導引的設計,可以促使系統同時具有快速搜尋,和從區域最佳解脫離的潛在優勢,因而有助於演算法尋獲最佳解的效率。
證諸實際驗證的結果,並與其他傳統的啟發式演算法比較,顯示本研究根據基因演算法、及粒子群最佳化演算法,所提出的「混沌類聚分群基因演算法」及「混沌動態導引粒子群最佳化演算法」,可以顯著的提高尋獲最佳解的效能;而在求解最佳化問題時,本研究所提出的演算法更具有相對的優勢。
The proposed approach brings up a manner of cognition that inherits the paradigm in Genetic Algorithms (GA) to implement a chaotic mapping and enhanced by K-means clustering approach. Chaotic mapping, enjoyed ergodicity, irregularity and the stochastic properties in heuristic optimization approach, contributes to global search evidently. In the meantime, K-means clustering approach with grouping property in the proposed algorithm could more easily lead to convergence.
Dynamic guiding approach coupled with Particle Swarm Optimization (PSO) often implied fluctuation movement during evolution. Chaos properties employed in PSO were to search for optimal solution. The proposed algorithm incorporated dynamic guiding approach and chaos attributions into PSO would inevitably bring to a desirable optimal solution.
As proven in multi-dimensional design space and compared with other conventional heuristic based algorithms, the proposed approaches could improve the search performance significantly, and show the superiority in solving optimization problems over other algorithms reported in this study.
參考文獻
英文部份
[1] Holland JH. Adaptation in Natural and Artificial System. Ann Arbor: The University of Michigan Press 1975.
[2] Wright AH, Rawlins GJ. Genetic algorithms for real parameter optimization. Foundations of Genetic Algorithms, Morgan Kaufmann, California, 1991;205-18.
[3] Lu J, Fang SC. Solving nonlinear optimization problems with fuzzy relation equation constraints. Fuzzy Set and Systems 2001;119:1-20.
[4] García S, Saad M, Akhrif O. Nonlinear tuning of aircraft controllers using genetic global optimization: A new periodic mutation operator. Canadian Journal of Electrical and Computer Engineering 2006;31(3):149-58.
[5] Eshelman LJ, Schaffer JD. Preventing premature convergence in genetic algorithms by preventing incest. In: Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, California, 1991;115-22.
[6] Eberhart RC, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995;39-43.
[7] Kennedy J, Eberhart RC. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. Piscataway, NJ, 1995;4:1942-8.
[8] Abido MA. Optimal design of power-system stabilizers using particle swarm optimization. IEEE Transactions on Energy Conversion 2002;17:406–13.
[9] Liu B, Wang L, Jin YH, Tang F, Huang DX. Improved particle swarm optimization combined with chaos. Chaos, Solitons and Fractals 2005;25(5):1261–71.
[10] Coelho LS. A quantum particle swarm optimizer with chaotic mutation operator. Chaos, Solitons and Fractals 2008;37:1409-18.
[11] Savic AD, Walters GA, Atkinson RM, Smith MR. Genetic Algorithm Optimization of Large Water Distribution System Expansion. Measurement and Control 1999;32:104-9.
[12] Nanayakkara SC, Srinivasan D, Lup LW, German X, Taylor E, Ong SH. Genetic algorithm based route planner for large urban street networks. 2007 IEEE Congress on Evolutionary Computation, CEC 2007, Article number 4425056, 2007;4469-74.
[13] May RM. Simple mathematical models with very complicated dynamics. Nature 1976;261:459–67.
[14] MacQueen JB. Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1967;1:281-97.
[15] Shi Y, Eberhart RC. A Modified Particle Swarm Optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation 1998;69−73.
[16] Shi Y, Eberhart RC. Parameter selection in particle swarm optimization. In: Proceedings of Evolutionary Programming, New York; 1998;591–600.
[17] Clerc M. The swarm and queen: towards a deterministic and adaptive particle swarm optimization. In: Proceedings of IEEE congress on evolutionary computation, Washington, DC, USA. 1999;1951–7.
[18] Clerc M, Kennedy JF. The particle swarm-explosion, stability, and conver- gence in a multi-dimensional complex space. IEEE Transactions on Evolutionary Computation 2002;6(1):58–73.
[19] Carlisle A, Dozier G. An off-the-shelf PSO. In: Proceedings of the Workshop on Particle Swarm Optimization. Indianapolis, IN: Purdue School of Engineering and Technology, IUPUI . 2001;1:1-6.
[20] Kennedy J, Eberhart RC, Swarm Intelligence, Morgan Kaufmann 2001.
[21] del Valle Y, Venayagamoorthy GK, Mohagheghi S, Hernandez JC, Harley RG. Particle swarm optimization: basic concepts, variants and applications in power systems. IEEE Transactions on Evolutionary Computation 2008;12(April (2)): 171–95.
[22] Lorenz EN. Deterministic nonperiodic flow. Journal of the Atmospheric Sciences 1963;20:130–41.
[23] Hartigan J. Clustering algorithms. JohnWiley and Sons Inc. 1975.
[24] Huang Z. Clustering large data sets with mixed numeric and categorical values. In: Proceedings of the First Pacific-Asia conference on knowledge discovery and data mining 1997.
[25] Yang Xueming, Yuan Jinsha, Yuan Jiangye, Mao Huina. A modified particle swarm optimizer with dynamic adaptation. Applied Mathematics and Computation 2007;189:1205–13.
[26] Arumugam M, Senthil Rao MVC, Tan Alan WC. A novel and effective particle swarm optimization like algorithm with extrapolation technique. Applied Soft Computing 2009;9:308–20.
[27] Lu Z, Shieh LS, Chen G, Coleman NP. Adaptive feedback linearization control of chaotic systems via recurrent high-order neural networks. Information Sciences 2006;176(16):2337-54.
[28] Alatas B, Akin E, Bedri OA. Chaos embedded particle swarm optimization algorithms. Chaos, Solitons and Fractals 2009;40:1715–34.
[29] Angeline PJ. Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Proceedings of the 7th International Conference on Evolutionary Programming VII, Springer, 1998;601–10.
[30] Coelho LS, Mariani VC. A novel chaotic particle swarm optimization approach using He´non map and implicit filtering local search for economic load dispatch. Chaos, Solitons and Fractals 2009;39:510–8.
[31] Coelho LS, Coelho AR. Model-free adaptive control optimization using a chaotic particle swarm approach. Chaos, Solitons and Fractals 2009;41:2001–9.
[32] Heidari-Bateni G, McGillem CD. Chaotic direct-sequence spread-spectrum communication system. IEEE Transactions on Communications 1994;42(2-4/3):1524–7.
[33] “NIOSH Safety and Health Topic: Construction.” <http://www.cdc.gov/niosh/topics/construction/> (Dec. 10, 2008).
[34] Huang Y, Liang C, Yang Y. The optimum route problem by genetic algorithm for loading/unloading of yard crane. Computers and Industrial Engineering 2009;56(3):993-1001.
[35] Sun M, Zhao L, Yan C, Yao QX. Wavelet Chaotic Neural Network with Nonlinear Self-feedback and Its Application to Traveling Salesman Problem. In: Proceedings of the World Congress on Intelligent Control and Automation (WCICA), 2008;4537-41.
[36] Pongcharoen P, Chalnate W, Thapatsuwan P. Exploration of Genetic Parameters and Operators through Travelling Salesman Problem. Science Asia 2007;33(2): 215-22.
[37] David L. Applegate, Robert E. Bixby, Vasek Chvatal, William J. Cook. The traveling salesman problem. Princeton University Press, New Jersey, USA, 2006
[38] Gomory RE. Solving linear programming problems in integers. In: Proceedings of Symposia in Applied Mathematics 1963;10:211-5.
[39] Jellouli O, Chatelet E. Dynamic programming approach for the generalized traveling salesman problem. International Workshop, Minsk, Belarus. 2000.
[40] Hansen M, Karp R. A dynamic programming approach to sequencing problems. SLAM Review 1962;10:196-210.
[41] Volgenant T, Jonker R. A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation. European Journal of Operational Research 1982;9:83-9.
[42] Fishetti M, Salazar JJ, Toth P. A branch and cut algorithm for the symmetric generalised travelling salesman. Problem, Working paper, University of Bologna. 1993.
[43] Garey MR, Johnson DS. Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco, 1979.
[44] Molga M, Smutnicki C. Test functions for optimization needs. <http://www.zsd.ict.pwr.wroc.pl/files/docs/functions.pdf> (Jan. 11, 2010).
[45] Srinivasan D, Seow TH. Particle swarm inspired evolutionary algorithm (PS-EA) for multi-criteria optimization problems. Evolutionary Multi-objective Optimization, Springer, Berlin, Heidelberg; 2006;147–65.
[46] Montiel O, Castillo O, Melin P, Antonio RD, Roberto S. Human evolutionary model: A new approach to optimization. Inform Sciences 2007;177(10):2075–98.
[47] Watcharasitthiwat K, Wardkein P. Reliability optimization of topology communication network design using an improved ant colony optimization. Computers and Electrical Engineering 2009;35(5):730–47.
[48] Shelokar PS, Siarry P, Jayaraman VK, Kulkarni BD. Particle swarm and ant colony algorithms hybridized for improved continuous optimization. Applied Mathematics and Computation 2007;188:129–42.
[49] Mahamed GH, Omran Mehrdad Mahdavi. Global-best harmony search. Applied Mathematics and Computation 2008;198:643–56.
[50] Jin Yaochu, Olhofer Markus, Sendhoff Bernhard. A Framework for Evolutionary Optimization With Approximate Fitness Functions. IEEE Transactions on Evolutionary Computation 2002;6(5):481-94.
[51] Lu Z, Shieh LS, Chen GR. On robust control of uncertain chaotic systems: a sliding-mode synthesis via chaotic optimization. Chaos, Solitons and Fractals 2003;18:819–27.
[52] Chen MR, Li X, Zhang X, Lu YZ. A novel particle swarm optimizer hybridized with extremal optimization. Applied Soft Computing 2010;10(2):367-73.
[53] Chen DB, Zhao CX. Particle swarm optimization with adaptive population size and its application. Applied Soft Computing 2009;9(1):39-48.
[54] Huang RY, Halpin DW. Visual construction operation simulation: the DISCO approach. Computer-Aided Civil and Infrastructure Engineering 1994;9:175-184.
[55] Halpin DW, Riggs LS. Planning and Analysis of Construction Operation. John Wiley and Sons, Inc., New York, N.Y. 1992.
[56] Cheng MY, Huang KY, Chen HM, Cao PC. Genetic Algorithm-based Chaos Clustering Approach for Optimizing Construction Time-cost Tradeoff Problems. In: Proceedings of the 28th International Symposium on Automation and Robotics in Construction, Seoul, Korea, 2011;147-55.
[57] Begambre O, Laier JE. A hybrid Particle Swarm Optimization – Simplex algorithm (PSOS) for structural damage identification. Advances in Engineering Software 2009;40:883–91.
[58] Chen JH, Yang LR, Su MC. Comparison of SOM-based optimization and particle swarm optimization for minimizing the construction time of a secant pile wall. Automation in Construction 2009;18:844–8.
[59] Ammar W. Mohemmed, Nirod Chandra Sahoo, Tan Kim Geok. Solving shortest path problem using particle swarm optimization. Applied Soft Computing 2008;8:1643–53.
[60] Goldberg DE. Genetic Algorithm in Search, Optimization, and Machine Learning. Addison-Wesley Professional, U.S.A. 1989.
[61] Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Third Edition, Springer-Verlag, London, UK 1996.
[62] Gen M, Cheng R. Genetic algorithms and engineering design. John Wiley & Sons, New York, U.S.A. 1997.
中文部份
[63] 劉東官,即時動態生產排程問題與解決教材,國立高雄第一科技大學,民國99年12月(http://www.aich.nkfust.edu.tw/ees/neter/page5-1/emp/chap2.pdf )
[64] 江正文、李維平,「以學習因子分群策略改良粒子群演算法」,北商學術論壇-資訊管理與實務研討會,民國95年。
[65] 曾建潮,微粒群算法,科学出版社,民國93年5月。
[66] 「歷年來營造業勞工職業傷害人次及千人率」,行政院勞工委員會98年勞動檢查年報,民國99年7月。
[67] 周義翔,「遺傳演算法應用於營建物料供應鏈規劃之研究—以預鑄廠鋼筋材料為例」,國立台灣大學土木工程學研究所未出版碩士論文,民國91年6月。
[68] 林昭凱,「考慮多模式專案排程下資源撫平之研究」,國立中央大學工業管理研究所未出版碩士論文,民國93年6月。
[69] 吳獻堂,「動態營建資源即時配送最佳化模式之開發-以混凝土配送為例」,國立成功大學土木工程研究所未出版博士論文,民國95年6月。
[70] 林伯勳、胡光復、沈哲緯、辜炳寰、鄭錦桐,「最佳化方法於大地工程上之應用」,中興工程季刊,第103期,第13-24頁,民國98年4月。