簡易檢索 / 詳目顯示

回結果列表
研究生： Maurice Glenn T. Go
Maurice - Glenn T. Go
論文名稱： Clustering-Based Chaotic Search Genetic Algorithm for Facility Layout Optimization
Clustering-Based Chaotic Search Genetic Algorithm for Facility Layout Optimization
指導教授： 鄭明淵
Min-Yuan Cheng
口試委員: 楊亦東
I-Tung Yang
郭斯傑
Sy-Jye Guo
學位類別： 碩士
Master
系所名稱： 工程學院 - 營建工程系
Department of Civil and Construction Engineering
論文出版年： 2012
畢業學年度： 100
語文別： 英文
論文頁數： 91
中文關鍵詞： Facility layout 、Genetic algorithm 、chaos 、k-means clustering 、optimization
外文關鍵詞： Facility layout, Genetic algorithm, chaos, k-means clustering, optimization
相關次數： 點閱：298  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • Finding the most efficient arrangement for a set of facilities in a system is an important and challenging task. Commonly known as facility layout problem (FLP), the objective is to assign each facility to a location such that an objective function (i.e. cost or distance) is minimized. This study proposes an improved optimization technique, namely k-means chaos genetic algorithm (KCGA), in solving the facility layout problem. The proposed model integrates two contrasting algorithm, chaos and k-means clustering, to effectively minimize the drawbacks of genetic algorithm. The former searches the solution space providing the necessary diversity in the population while the latter provides the general search direction of the algorithm, thus a faster convergence is achieved. To evaluate the model’s performance, two case studies: construction site layout (11 facilities) and architectural layout (28 facilities) are adopted. Experiment results on both problems demonstrate the superior performance of KCGA model in obtaining optimal solutions to the layout problem. The results show the potential of the proposed model as a search and optimization tool to assist planners and decision makers in facility layout planning.

    Finding the most efficient arrangement for a set of facilities in a system is an important and challenging task. Commonly known as facility layout problem (FLP), the objective is to assign each facility to a location such that an objective function (i.e. cost or distance) is minimized. This study proposes an improved optimization technique, namely k-means chaos genetic algorithm (KCGA), in solving the facility layout problem. The proposed model integrates two contrasting algorithm, chaos and k-means clustering, to effectively minimize the drawbacks of genetic algorithm. The former searches the solution space providing the necessary diversity in the population while the latter provides the general search direction of the algorithm, thus a faster convergence is achieved. To evaluate the model’s performance, two case studies: construction site layout (11 facilities) and architectural layout (28 facilities) are adopted. Experiment results on both problems demonstrate the superior performance of KCGA model in obtaining optimal solutions to the layout problem. The results show the potential of the proposed model as a search and optimization tool to assist planners and decision makers in facility layout planning.

    ABSTRACT ................................................................................................................... I ACKNOWLEDGEMENTS .......................................................................................... II TABLE OF CONTENTS ............................................................................................. III ABBREVIATION......................................................................................................... V LIST OF FIGURES ..................................................................................................... VI LIST OF TABLES ..................................................................................................... VII LIST OF APPENDIX ............................................................................................... VIII CHAPTER 1 INTRODUCTION 1.1. Introduction .................................................................................................. 1 1.2. Research Objective ....................................................................................... 4 1.3. Research Scope ............................................................................................. 5 1.4. Research Methodology ................................................................................. 6 CHAPTER 2 LITERATURE REVIEW 2.1. Facility layout problem ................................................................................. 8 2.2. Genetic Algorithm ...................................................................................... 11 2.3. K-means clustering ..................................................................................... 15 2.4. Chaos Theory .............................................................................................. 20 CHAPTER 3 MODEL CONSTRUCTION 3.1. Integrating K-means with GA (KGA) ........................................................ 24 3.2. Integrating Chaos with GA (CGA) ............................................................. 24 3.3. Integrating K-means and Chaos with GA (KCGA) .................................... 25 CHAPTER 4 MODEL IMPLEMENTATION 4.1. Case study 1: Construction site-level facility layout .................................. 30 4.1.1. Problem Definition .............................................................................. 30 4.1.2. Fitness Function .................................................................................. 31 4.1.3. KCGA Operators and Parameters ....................................................... 33 4.1.4. Experiment Results ............................................................................. 36 iv 4.2. Case study 2: Architectural layout problem ............................................... 38 4.2.1. Problem Definition .............................................................................. 38 4.2.2. Fitness Function .................................................................................. 39 4.2.3. KCGA Operators and Parameters ....................................................... 42 4.2.4. Experiment Results ............................................................................. 43 CHAPTER 5 CONCLUSION AND RECOMMENDATION 5.1. Conclusions ................................................................................................ 48 5.2. Recommendations ...................................................................................... 48 REFERENCES ............................................................................................................ 50 APPENDIX 1 Matlab Code for Case Study 1 ............................................................. 54 APPENDIX 2 Matlab Code for Case Study 2 ............................................................. 65 BIOGRAPHY .............................................................................................................. 78

    Alligood, K. T., Sauer, T. T. and Yorke, J. A. (1996). Chaos: An Introduction to Dynamical Systems. Springer-Verlag. New York
    Chan, C. M., Zhang, L. M. and Ng, J. Y. M. (2009). "Optimization of pile groups using hybrid genetic algorithms." Journal of Geotechnical & Geoenvironmental Engineering, vol. 135, no. 4, pp. 497-505.
    Chan, K. C. and Tansri, H. (1994). "A study of genetic crossover operations on the facilities layout problem." Computers and Industrial Engineering, vol. 26, no. 3, pp. 537-550.
    Cheng, M. Y. and Huang, K. Y. (2010). "Genetic algorithm-based chaos clustering approach for nonlinear optimization." Journal of Marine Science and Technology, vol. 18, no. 3, pp. 435-441.
    DeJong, K. A. (1975). Analysis of the behavior of a class of genetic adaptive systems. Ann Arbor, Michigan, University of Michigan.
    Devaney, R. L. (1992). A first course in chaotic dynamical systems: theory and experiment. Addison-Wesley Publishing Company,
    Dorigo, M. and Caro, G. D. (1999). Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionaty Computation. 2: 3.
    Fiechter, C. N. (1994). "A parallel tabu search algorithm for large traveling salesman problem." Discrete Applied Mathematics, vol. 51, no. 3, pp. 243-267.
    Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley Publishing Co. Massachusetts
    Han, J. and Kamber, M. (2001). Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers. San Francisco, CA, USA
    Hasselblatt, B. and Katok, A. (2003). A first course in dynamics: with a panorama of recent developments. Cambridge University Press. Cambridge, UK
    51
    Haupt, R. L. and Haupt, S. E. (2004). Practical Genetic Algorithms. John Wiley & Sons, Inc. Hoboken, New Jersey
    Hegazy, T. (1999). "Optimization of resource allocation and leveling using genetic algorithms." Journal of Construction Engineering and Management, vol. 125, no. 3, pp. 167-175.
    Heragu, S. (1997). Facilities Design. PWS Publishing Company. Boston, MA
    Hillborn, R. C. (2000). Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers. Oxford, New York, Oxford University Press.
    Holland, J. (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press. Ann Arbor, Michigan
    Kusiak, A. and Heragu, S. S. (1987). "The facility layout problem." European Journal of Operational Research, pp. 229-251.
    Lam, K. C., Ning, X. and Ng, T. (2007). "The 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.
    Lam, K. C., Tang, C. M. and Lee, W. C. (2005). "Application of entropy techniques and genetic algorithms to construction site layout planning of medium-size projects." Construction Management and Economics, vol. 23, no. 2, pp. 127-145.
    Larose, D. T. (2005). Discovering Knowledge in Data: An Introduction to Data Mining. John Wiley & Sons, Inc. Hoboken, New Jersey
    Leu, S.-S., Yang, C.-H. and Huan, J.-C. (2000). "Resource leveling in construction by genetic algorithm-based optimization and its decision support system application." Automation in Construction, vol. 10, no. 1.
    Li, H. and Love, P. E. D. (1998). "Site-level facilities layout using genetic algorithm." Journal of Computing in Civil Engineering, vol. 12, no. 4, pp. 227-231.
    52
    Li, H. and Love, P. E. D. (2000). "Genetic search for solving construction site-level unequal-area facility layout problems." Automation in Construction, vol. 9, pp. 217-226.
    Liang, L. Y. and Chao, W. C. (2008). "The strategies of tabu search technique for facility layout optimization." Automation in Construction, vol. 17, no. 6, pp. 657-669.
    Liu, B., Wang, L., Jin, Y.-H., Tang, F. and Huang, D.-X. (2005). "Improved particle swarm optimization combined with chaos." Chaos, Solitons and Fractals, vol. 25.
    Liu, J., Cai, Z. and Liu, J. (2000). "Premature convergence in genetic algorithm: analysis and prevention based on chaos operator". Proceedings of the 3rd World Congress on Intelligent Control and Automation, Hefei, P.R. China.
    Long, L. D. and Ohsato, A. (2009). "A genetic algorithm-based method for scheduling repetitive construction projects." Automation in Construction, vol. 18, no. 4, pp. 499-511.
    MacQueen, J. B. (1967). "Some methods for classification and analysis of multivariate observations". Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, CA, University of California Press.
    Mak, K. L., Wong, Y. S. and Chan, F. T. S. (1998). "A genetic algorithm for facility layout problems." Computer Integrated Manufacturing Systems, vol. 11, no. 1-2, pp. 113-127.
    Mawdesley, M. J., Al-jibouri, S. H. and Yang, H. (2002). "Genetic algortihms for construction site layout in project planning." Journal of Construction Engineering and Management, vol. 128, no. 5, pp. 418-426.
    May, R. M. (1976). "Simple mathematical models with very complicated dynamics." Nature, vol. 261, pp. 459-467.
    Reeves, C. R. and Rowe, J. E. (2003). Genetic Algorithms - Principles and Perspectives: A guide to GA theory. Kluwer Academic Publishers. Massachusetts, USA
    Sastry, K., Goldberg, D. and Kendall, G. (2005). Genetic Algorithms Search Methodologies. E. K. Burke and G. Kendall. Springer US: 97-125.
    53
    Singh, S. P. and Sharma, R. R. K. (2006). "A review of different approaches to the facility layout problems." International Journal of Advance Manufacturing Technology, no. 30, pp. 425-433.
    Tompkins, J. A., White, J. A., Bozer, Y. A. and Tanchoco, J. M. A. (2010). Facilitie Planning. John Wiley & Sons Inc. Hoboken, NJ
    Yeh, I.-C. (1995). "Construction site layout using annealed neural network." Journal of Computing in Civil Engineering, vol. 9, no. 3, pp. 201-208.
    Yeh, I.-C. (2006). "Architectural layout optimization using annealed neural network." Automation in Construction, vol. 15, no. 4, pp. 531-539.
    Yuan, X., Yuan, Y. and Zhang, Y. (2002). "A hybrid chaotic genetic algorithm for short-term hydro system scheduling." Mathematics and Computers in Simulation, vol. 59, pp. 319-327.

    QR CODE