研究生: |
連立川 Li-Chuan Lien |
---|---|
論文名稱: |
粒子蜂群演算法於營建場址配置最佳化之研究 Particle Bee Algorithm for Construction Site Layout Optimization |
指導教授: |
鄭明淵
Min-Yuan Cheng |
口試委員: |
張陸滿
Luh-Maan Chang 姚乃嘉 Nie-Jia Yau 曾仁杰 Ren-Jye Dzeng 晁立中 Li-Chung Chao 楊亦東 I-Tung Yang |
學位類別: |
博士 Doctor |
系所名稱: |
工程學院 - 營建工程系 Department of Civil and Construction Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 英文 |
論文頁數: | 231 |
中文關鍵詞: | 營建場址配置 、群智慧演算法 、蜂群演算法 、粒子(鳥群)演算法 、粒子蜂群演算法 |
外文關鍵詞: | construction site layout, swarm intelligence, bee algorithm, particle swarm optimization, particle bee algorithm |
相關次數: | 點閱:417 下載:7 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
好的營建場址配置(Construction Site Layout, CSL)除了可使工程成本與進度節省更為明顯,也因其可能牽涉相對高水準的美學和實用性的特質,成為一個特別有趣的研究領域。然而對工程師而言,執行營建場址配置是一種相對複雜的組合排列問題。群智慧演算法(Swarm Intelligence, SI),諸如蜂群演算法(Bee Algorithm, BA)與粒子(鳥群)演算法(Particle Swarm Optimization, PSO),皆是靈感來自於群體行為模式的最佳化方法,至今這些方法已越來越多的被用在處理各種複雜的優化問題上。為了整合蜂群演算法全域搜索與鳥群演算法局部搜索的能力,本研究提出了混合蜂群和鳥群行為的群智慧演算法–粒子蜂群演算法(Particle Bee Algorithm, PBA);另外為提高搜索效率及防止陷入局部解的問題,本研究提出鄰近視窗(neighborhood-windows, NW)搜尋及自參數更新(self-parameter-updating, SPU)技術。本研究以多維度的基準函數(multi-dimensional benchmark functions)來比較粒子蜂群演算法與著名最佳化演算法,諸如遺傳演算法(Genetic Algorithm, GA)、差分進化法(Differential Evolution, DE)、蜂群演算法與鳥群演算法的性能;此外,本研究另以樓面層級(Floor Level, FL)與工址層級(Site Level, SL)的營建場址配置假設問題,來進行粒子蜂群演算法、蜂群演算法與鳥群演算法的性能驗證。研究結果顯示,在多維度基準函數的性能比較及假設的營建場址配置最佳化問題驗證,粒子蜂群演算法皆有較其它演算法不錯的表現。
The construction site layout (CSL) design presents a particularly interesting area of study because of its relatively high level of attention to aesthetics and usability qualities, in addition to common engineering objectives such as cost and performance. However, they present a difficult combinatorial optimization problem for engineers. Swarm intelligence (SI), an approach to decision making that integrates collective social behavior models such as the bee algorithm (BA) and particle swarm optimization (PSO), is being increasingly used to resolve various complex optimization problems. In order to integrate BA global search ability with the local search advantages of PSO, this study proposes a new optimization hybrid swarm algorithm – the particle bee algorithm (PBA) which imitates the intelligent swarming behavior of honeybees and birds. This study also proposes a neighborhood-windows (NW) technique for improving searching efficiency as well as a self-parameter-updating (SPU) technique for preventing trapping into a local optimum in high dimensional problems. This study compares the performance of PBA with that of genetic algorithm (GA), evolutionary algorithms (EA), differential evolution (DE), bee algorithm (BA) and particle swarm optimization (PSO) for multi-dimensional benchmark function problems. Besides, this study compares PBA performance against bee algorithm (BA) and particle swarm optimization (PSO) performance in those hypothetical floor level (FL) and site level (SL) CSL problems. Results show PBA performance is comparable to those of the mentioned algorithms in the benchmark functions and can be efficiently employed to solve those hypothetical floor level and site level CSL problems with high dimensionality.
[1] Michalek, J. J., Choudhary, R. and Papalambros, P. Y., “Architectural layout design optimization,” Engineering Optimization, Vol.34, No.5, pp.461-484 (2002).
[2] Anjos, M. F. and Vannelli, A., A new mathematical programming framework for facility layout design, http://www.optimization-online.org/DB_HTML/2002/03/454.html (2002).
[3] Yeh, I. C., “Architectural layout optimization using annealed neural network,” Automation in Construction, Vol.15, No.4, pp.531-539 (2006).
[4] Bonabeau, E., Dorigo, M., and Theraulaz, G., “Swarm Intelligence: From Natural to Artificial Intelligence,” Oxford University Press, New York (1999).
[5] Dorigo, M., “Optimization, Learning and Natural Algorithms,” Ph.D Thesis, Politecnico di Milano, Italy (1992).
[6] Li, X. L., “A new intelligent optimization-artificial fish swarm algorithm,” Ph.D Thesis, Zhejiang University of Zhejiang, China (2003).
[7] Kennedy, J. and Eberhart, R.C., “Particle swarm optimization,” In Proceedings of the 1995 IEEE International Conference on Neural Networks, Vol.4, pp.1942-1948 (1995).
[8] Pham, D. T., Koc, E., Ghanbarzadeh, A., Otri, S., Rahim, S. and Zaidi, M., “The bees algorithm-a novel tool for complex optimization problems,” In Proceedings of the Second International Virtual Conference on Intelligent Production Machines and Systems, pp.454-461 (2006).
[9] Sirinaovakul, B. and Thajchayapong, P., “An analysis of computer-aided facility layout techniques,” Journal of Computer-Integrated Manufacturing, Vol.9, No.4, pp260-264 (1996).
[10] Moore, J. M., “Facilities design with graph theory and strings,” Omega, Vol.4, No.2, pp.193-203 (1976).
[11] Hassan, M. M. D. and Hogg, G. L., “On constructing a block layout by graph theory,” Journal of Production Research, Vo.29, No.6, pp.1263-1278 (1991).
[12] Cheng, M. Y., “Automated site layout of temporary construction facilities using geographic information systems (GIS),” PhD thesis, University of Texas at Austin, USA (1992).
[13] Tommelein, I. D., Levitt, R. E. and Confrey, T., “SightPlan experiments: alternate strategies for site layout design,” Journal of Computing in Civil Engineering, Vol.5, No.1, pp.42-63 (1991).
[14] Elbeltagi, E. and Hegazy, T., “A hybrid AI-based system for site layout planning in construction,” Computer-Aided Civil and Infrastructure Engineering, Vol.16, No.2, pp.79-93 (2001).
[15] Abdinnour-Helm, S. and Hadley, S.W., “Tabu search based heuristics for multi-floor facility layout,” International Journal of Production Research, Vol.38, No.2, pp.365-83 (2000).
[16] Suresh, G. and Sahu, S., “Multiobjective facility layout using simulated annealing,” International Journal of Production Economics, Vol.32, No.2, pp.239-54 (1993).
[17] Gero, J. S. and Kazakov, V., “Learning and reusing information in space layout planning problems using genetic engineering,” Artificial Intelligence in Engineering, Vol.11, No.3, pp.329-334 (1997).
[18] Li, H. and Love, P.E.D., “Genetic search for solving construction site-level unequal-area facility layout problems,” Automation in Construction, Vol.9, No.2, pp.217-226 (2000).
[19] Osman, H. M., Georgy, M. E. and Ibrahim, M.E., “A hybrid CAD-based construction site layout planning system using genetic algorithms,” Automation in Construction, Vol.12, No.6, pp.749-764 (2003).
[20] Hegazy, T. and Elbeltagi, E., “EvoSite: evolution-based model for site layout planning,” Journal of Computing in Civil Engineering, Vol.13, No.3, pp.198-206 (1999).
[21] Elbeltagi, E., Hegazy, T., Hosny, A.H. and Eldosouky, A., “Schedule-dependent evolution of site layout planning,” Construction Management and Economics, Vol.19, No.7, pp.689-697 (2001).
[22] Yang, X.S., “Engineering Optimizations via Nature-Inspired Virtual Bee Algorithms,” Lecture Notes in Computer Science, Vol.3562, pp.317-323 (2005).
[23] Karaboga, D. and Akay, B., “A comparative study of Artificial Bee Colony algorithm,” Applied Mathematics and Computation, Vol.214, pp.108-132 (2009).
[24] Basturk, B. and Karaboga, D., “An Artificial Bee Colony (ABC) Algorithm for Numeric Function Optimization,” IEEE Swarm Intelligence Symposium 2006, Indianapolis, Indiana, USA (2006).
[25] Ozbakir, L., Baykasog, A. and Tapkan, P., “Bees algorithm for generalized assignment problem,” Applied Mathematics and Computation, Vol.215, pp. 3782-3795 (2010).
[26] Tsai, H. C., “Predicting strengths of concrete-type specimens using hybrid multilayer perceptions with center-unified particle swarm optimization,” Expert Systems with Applications, Vol.37, pp.1104-1112 (2010).
[27] Parsopoulos, K. E., and Vrahatis, M. N., “Parameter selection and adaptation in unified particle swarm optimization,” Mathematical and Computer Modeling, Vol.46, No.1, pp.198-213 (2007).
[28] Korenaga, T., Hatanaka, T. and Uosaki, K., “Improvement of Particle Swarm Optimization for High-Dimensional Space,” 2006 SICE-ICASE International Joint Conference (2006).
[29] Eberhart, R., Shi Y., and Kennedy J., “Swarm Intelligence,” Morgan Kaufmann, San Francisco (2001).
[30] Karaboga, D., “An Idea Based on Honey Bee Swarm for Numerical Optimization,” Technical Report-TR06 (2005).
[31] Seeley, T. D., “The wisdom of the hive,” Harvard University Press, Cambridge, MA (1995).
[32] Tereshko, V. and Loengarov A., “Collective Decision-Making in Honey Bee Foraging Dynamics,” Computing and Information Systems Journal, Vol.9, No.3 (2005).
[33] Karaboga, D. and Basturk B., “On the performance of artificial bee colony (ABC) algorithm,” Applied Soft Computing, Vol.8, No.1, pp.687-697 (2008).
[34] Eberhart, R. C. and Kennedy, J. A., “New optimizer using particles swarm theory,” In The sixth international symposium on micro machine and human science (1995).
[35] Wooley, J., C. and Lin, H. S., “Catalyzing inquiry at the interface of computing and biology,” 2005 Report of the National Research Council of the National Academies (2005).
[36] Sharaf, A., M. and Adel, A. A., “A Novel Discrete Multi-Objective Particle Swarm Optimization (MOPSO) of Optimal Shunt Power Filter,” International Journal of Power and Energy Conversion, Vol.1, No.2-3, pp.157-177 (2009).
[37] Eberhart, R. C. and Shi, Y., “Comparing inertia weights and constriction factors in particle swarm optimization,” In Proceedings 2000 IEEE CEC, IEEE service center, Piscataway, NJ (2000).
[38] Zouein, P. P., and Harmanani, H., and Hajar, A., “Genetic Algorithm for Solving Site Layout Problem with Unequal-Size and Constrained Facilitiies,” Journal of Computing in Civiil Engineering, Vol.16, No.2, pp.143-151 (2002).
[39] Ning, X., Lam, K. C., Mike, and Lam, C. K., “Dynamic construction site layout planning using max-min ant system,” Automation in Construction, Vol.19, No.1, pp.55-65 (2010).
[40] Tam, C. M., Tong, K. L., Leung, W. T. and Chiu, W.C., “Site layout planning using nonstructural fuzzy decision support system,” Journal of construction engineering and management, Vol.128, No.3, pp.220-231 (2002).
[41] EI-rayes, K., and Khalafallah, A., “Trade-off between safety and cost in planning construction site layouts,” Journal of Construction Engineering and Management, Vol.131, No.11, pp.1186-1195 (2005).
[42] Jagielski, R. and Gero, J. S., “A genetic programming approach to the space layout problem in: R. Junge (Ed.),” CAAD Futures, Kluwer, Dordrecht, pp. 875–884 (1997).
[43] Hahn, P. M. and Jrarup, J., “A hospital facility layout problem finally solved,” Journal of Intelligent Manufacturing, Vol.15, No.5-6, pp.487-496 (2001).
[44] Yeh, I. C., “Construction site layout using annealed neutral network.” Journal of Computing in Civil Engineering, Vol.9, No.3, pp.201-208(1995).
[45] Holland, J. H., “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, MI (1975).
[46] Li, H. and Love, P. E. D., “Site-lever facilities layout using genetic algorithms,” Journal of Computing in Civil Engineering, Vol.12, No.4, pp.227-231(1998).
[47] Tam, C. M., Tong, Thomas K. L. and Wilson, K. W. Chan, “Genetic Algorithm for Optimizing Supply Locations around Tower Crane,” Journal of Construction Engineering and Management, Vol.127, No.4, pp.315-321 (2001).
[48] Tam, C. M. and Tong, Thomas K. L., “GA-ANN model for optimizing the locations of tower crane and supply points for high-rise public housing,” Construction Management & Economics, Vol.21, No.3, pp.257-266 (2003).
[49] Hegazy, T. and Elbeltagi, E., “EVOSITE: Evolution-based model for site layout planning,” Journal of computing in civil engineering, Vol.13, No.3, pp.198-206 (1999).
[50] Elbeltagi, E. and Hegazy, T., “A hybrid AI-based system for site layout planning in construction,” Computer-aided civil and infrastructural engineering, Vol.16, No.2, pp.79-93 (2001).
[51] Elbeltagi, E., Hegazy, T. and Eldosouky, A., “Dynamic Layout of Construction Temporary Facilities Considering Safety,” Journal of Construction Engineering and Management, Vol.130, No.4, pp.534-541 (2004).
[52] Mawdesley, M. J., AI-jibouri, S. H. and Yang, H. B., “Genetic algorithms for construction site layout in project planning,” Journal of construction engineering and management, Vol.128, No.5, pp.418-426 (2002).
[53] Samdani, S. A., Bhakal, L. and Singh, A. K., “Site layout of temporary construction facilities using ant colony optimization,” Los Angeles Section 526International Committee 4th International Engineering and Construction Conference, ASCE, California State University, USA (2006).
[54] Lam, K. C., Ning, X. and Ng, S. T., “Application of the ant colony optimization algorithm to the construction site layout planning problem,” Construction Management and Economics, Vol.25, No.4, pp.359-374 (2007).
[55] Engels, G. and Groenewegen, L., “Object-oriented modeling: a roadmap,” In Proceedings of the Conference on The Future of Software Engineering table of contents, Limerick, Ireland, pp.103-116 (2000).
[56] Satzinger, J. W., Jackson, R. B. and Burd, S. D., “System Analysis and Design in a Changing World,” Course Technology, Cambridge, Massachusetts (2000).
[57] Vadaparty, K., “UML & beyond- use cases–basics,” Journal of Object Oriented Programming, Vol.12, No.9, pp.4-8 (2000).
[58] Booch, G., Maksimchuk, R. A., Engle, M.W., Young, B. J., Conallen, J. and Houston, K. A, Object-Oriented Analysis and Design with Applications (3rd edition), Addison-Wesley, Reading, Massachusetts (2007)
[59] Basili, V. R. and Turner, A. J., “Iterative Enhancement: A practical technique for software development,” IEEE Transactions on software engineering, Vol.1, No.4, pp.390-396 (1975).
[60] Caspers, J., “Object-oriented programming: Analysis, design and implementation methods (1st edition),” Computer Technology Research Corp., Charleston, South Carolina (1994).
[61] Ko, C. H., “Evolutionary Fuzzy Neural Inference Model (EFNIM) for Decision-Making in Construction Management,” Ph.D. Thesis, National Taiwan University of Science and Technology, Taiwan (2002).
[62] Smith, H. A. and McKeen, J. D., “Object-Oriented Technology: Getting Beyond the Hype,” The DATA BASE for Advances in Information Systems, Vol.27, No.2, pp.20-29 (1996).
[63] O’Docherty, M., “Object-Oriented Analysis and Design: Understanding System Development with UML 2.0,” John Wiley & Sons, England (2005).
[64] Fichman, R. G. and Kemerer, C. F., “Adoption of Software Engineering Process Innovations: The Case of Object Orientation,” Sloan Management Review, pp.7-22 (1993)
[65] Fichman, R. G. and Kemerer, C. F., “Object technology and reuse: Lessons from early adopters,” Computer, Vol.30, No.10, pp.47-59 (1997).
[66] Johnson, R. A., “The ups and downs of object-oriented systems development. Communications of the ACM, Vol.43, No.10, pp.68-73 (2000).
[67] Larman, C., “Applying UML and patterns: An introduction to object-oriented analysis and design,” Prentice Hall PTR, Upper Saddle River, New Jersey (1998).
[68] Fowler, M. and Scott, K., “UML distilled: A brief guide to the standard object modeling language (2nd edition),” Addison-Wesley, Reading, Massachusetts (2000).
[69] D’Souza, D. F. and Wills, A. C., “Objects, components, and frameworks with UML: The catalysis approach,” Addison-Wesley, Reading, Massachusetts (1999).
[70] Barclay, K. and Savage, J., “Object-Oriented Design with UML and Java,” Elseviers, Butterworth-Heinemann, Burlington, Massachusetts (2004).
[71] Booch, G., “Coming of age in an object-oriented world,” IEEE Software, Vol.11, No.6, pp.33-41 (1994).
[72] Jacobson, I., “The Road to the Unified Software Development Process,” Cambridge University Press, Cambridge, United Kingdom, pp.103-108 (2000).
[73] Krink, T., Filipic, B., Fogel, G.B. and Thomsen, R., “Noisy optimization problems-a particular challenge for differential evolution?,” Proceedings of 2004 Congress on Evolutionary Computation, IEEE Press, Piscataway, NJ, pp.332-339 (2004).
[74] Lam, K. C., Ning, X. and Ng, T., “The application of the ant colony optimization algorithm to the construction site layout planning problem,” Construction Management and Economics, Vol.25, pp.359-374 (2007).