研究生: |
英妲 Amalia - Utamima |
---|---|
論文名稱: |
運用人工粒子群演算法解決單列機台佈置問題 Artificial Particle Swarm Optimization for Solving Single Row Facility Layout Problem |
指導教授: |
歐陽超
Chao Ou-Yang |
口試委員: |
郭人介
Ren-Jieh Kuo 楊朝龍 Chao-Lung Yang |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2012 |
畢業學年度: | 100 |
語文別: | 英文 |
論文頁數: | 57 |
中文關鍵詞: | 單排設施規劃 、分佈估計演算法 、粒子群演算法 、禁忌搜尋法 |
外文關鍵詞: | single row facility layout, estimation distribution algorithm, particle swarm optimization, tabu search |
相關次數: | 點閱:268 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
直線單排設施規劃問題(Single Row Facility Layout Problem, SRFLP)為著名的直 線設施規劃問題。被歸類為NP-Complete問題的直線單排設施規劃問題,其目的為將兩 兩設施之間的距離的總和最小化。
分佈估計演算法(Estimation of Distribution Algorithm, EDA)能有效地改善初 期幾個世代的解的品質,但隨著世代的增加,多樣性的遺失也迅速擴大。為了保留多樣性,則需使用混合式的啟發式演算法(meta-heuristic algorithms)。本研究提出一人造 粒子群演算法Artificial Particle Swarm Optimization (APSO),其為由分佈估計演算法 (EDA)、粒子群演算法(PSO)及禁忌搜尋法(TS)組合而成的混合式演算法。其他混合式演算法將被用來與APSO進行比較。在本研究中,延伸的基因演算法extended Artificial Chromosomes Genetic Algorithm (eACGA)、分佈估計粒子群演算法Estimation Distribution Algorithm Particle Swarm Optimization (EDAPSO) ,以及分佈估計禁忌搜尋 演算法Estimation Distribution Algorithm Tabu Search (EDAtabu)這三個混合式演算 法將被用來與APSO進行比較。本研究使用SRFLP中的15個標竿問題進行性能測試,結果顯示APSO能成功地得到最佳解。此外,與另外三個混合式演算法相比,APSO能得到較小的平均誤差。
直線單排設施規劃問題(SRFLP)在考慮更多的限制下能成為增強的SRFLP (enhanced SRFLP)。計算結果顯示,APSO也能有效地處理enhanced SRFLP 。因此, 可推得APSO為一個有效的啟發式演算法,不僅能解決原有的直線單排設施規劃問題 (SRFLP),也能處理增強的直線單排設施規劃問題(enhanced SRFLP)。
The layout positioning problem of facilities on a straight line is known as Single Row Facility Layout Problem (SRFLP). The objective of SRFLP, categorized as NP-Complete problem, is to arrange the layout so that the sum of distances between all facilities’ pairs can be minimized.
Estimation Distribution Algorithm (EDA) improves the solution quality efficiently in first few runs, but the diversity lost grows rapidly as more iterations are run. To maintain the diversity, hybridization with meta-heuristic algorithms is needed. This research proposes Artificial Particle Swarm Optimization (APSO), an algorithm which consists of hybridization of EDA, Particle Swarm Optimization (PSO), and Tabu Search (TS). Other hybridization algorithms are also built as comparers. They are extended Artificial Chromosomes Genetic Algorithm (eACGA), Estimation Distribution Algorithm Particle Swarm Optimization (EDAPSO), and Estimation Distribution Algorithm Tabu Search (EDAtabu). APSO’s performance is tested in 15 benchmark problems of SRFLP and it successfully achieves optimum solution. Moreover, the mean error rates of APSO always get the lowest value compared to other algorithms.
SRFLP can be enhanced by considering more constraints and become enhanced SRFLP. Computational results show that APSO also can solve enhanced SRFLP effectively. Therefore, we can conclude that APSO is a promising meta-heuristic algorithm which could be used to overcome the basic and enhanced SRFLP.
Ackley, D.H., 1987. A connectionist machine for genetic hillclimbing, Norwell, MA, USA: Kluwer Academic Publishers.
Amaral, A.R.S., 2009. A new lower bound for the single row facility layout problem. Discrete Applied Mathematics, 157(1), pp.183-190.
Amaral, A.R.S., 2006. On the exact solution of a facility layout problem. European Journal of Operational Research, 173(2), pp.508-518.
Anjos, M.F., Kennings, A. & Vannelli, A., 2005. A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Discrete Optimization, 2(2), pp.113-122.
Anjos, M.F. & Vannelli, A., 2008. Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, 20(4), pp.611-617.
Baluja, S., 1995. An empirical comparison of seven iterative and evolutionary function optimization heuristics,
Baluja, S. & Davies, S., 1998. Fast probabilistic modeling for combinatorial optimization. In Proceedings of the fifteenth national/tenth conference on artificial intelligence/innovative applications of artificial intelligence. pp. 469-476.
Braglia, M., 1996. Optimization of a simulated-annealing-based heuristic for single row machine layout problem by genetic algorithm. International Transactions in Operational Research, 3(1), pp.37-49.
Bratton, D. & Kennedy, J., 2007. Defining a standard for particle swarm optimization. In Proceeding of the IEEE Swarm Intelligence Symposium, SIS’2007. Honolulu, Hawaii, New Jersey, pp. 120-127.
Ceberio, J. et al., 2012. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Progress in Artificial Intelligence, 1(1), pp.103-117.
Chang, P.-C. et al., 2009. Artificial chromosomes embedded in genetic algorithm for a chip resistor scheduling problem in minimizing the makespan. Expert Systems with Applications, 36(3), pp.7135-7141.
Chen, Y.-M. et al., 2012. Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems. Computers & Industrial Engineering, 62(2), pp.536-545.
Datta, D., Amaral, A.R.S. & Figueira, J.R., 2011. Single row facility layout problem using a permutation-based genetic algorithm. European Journal of Operational Research, 213(2), pp.388-394.
Dobslaw, F., 2010. A Parameter Tuning Framework for Metaheuristics Based on Design of Experiments and Artificial Neural Networks. In Proceeding of the International Conference on Computer Mathematics and Natural Computing. pp. 1-4.
Drira, A., Pierreval, H. & Hajri-Gabouj, S., 2007. Facility layout problems: A survey. Annual Reviews in Control, 31(2), pp.255-267.
Harik, G., Lobo, F. & Goldberg, D., 1999. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation, 3(4), pp.287-297.
Haupt, R.L. & Haupt, S.E., PRACTICAL GENETIC ALGORITHMS 2004th ed., Wiley Interscience.
Hauschild, M. & Pelikan, Martin, 2011. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation, 1(3), pp.111-128.
Heragu S, S., 2008. Facilities Design 3rd ed., CRC Press, Taylor & Francis Group.
Heragu, S.S. & Alfa, A.S., 1992. Experimental analysis of simulated annealing based algorithms for the layout problem. European Journal of Operational Research, 57(2), pp.190-202.
Heragu, S.S. & Kusiak, A., 1991. Efficient Models for the facility layout problem. European Journal of Operational Research, 53, pp.1-13.
Hu, X., Eberhart, R. & Shi, Y., 2003. Swarm Intelligence For Permutation Optimization, A Case Study On N-Queens Problem.pdf. In IEEE Swarm Intelligence Symposium. Indianapolis, USA, pp. 243-246.
Kennedy, J. & Eberhart, R.C., 1995. Particle Swarm Optimization. In Proceeding IEEE International Conference on Neural Networks IV. Nagoya, Japan: IEEE, pp. 1942–1948.
Kumar, K.R., Hadjinicola, G.C. & Lin, T.-li, 1995. A heuristic procedure for the single-row facility layout problem. European Journal of Operational Research, 87.
Lozano, J.A., 2006. Towards a new evolutionary computation: Advances in the Estimation of Distribution Algorithms,
Mawdesley, M.J. & Al-Jibouri, S.H., 2003. Proposed Genetic Algorithms For Construction Site Layout. Engineering Applications of Artificial Intelligence, 16(5-6), pp.501-509.
Navalertporn, T. & Afzulpurkar, N.V., 2011. Optimization of tile manufacturing process using particle swarm optimization. Swarm and Evolutionary Computation, 1(2), pp.97-109. Available at: http://linkinghub.elsevier.com/retrieve/pii/S2210650211000216 [Accessed June 20, 2012].
Neghabat, F., 1974. An efficient equipment layout algorithm. Operations Research, 22, pp.622-628.
Pelikan, M, Goldberg, D.E. & Lobo, F.G., 2002. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21, pp.5-20.
Peña, J. et al., 2004. Hybrid evolutionary algorithm using genetic and Estimation of Distribution Algorithms. In Innovations in applied artificial intelligence: 17th international conference on industrial and engineering applications of artificial intelligence and expert systems. Proceedings of IEA/AIE 2004. Ottawa, Canada.
Samarghandi, H. & Eshghi, K., 2010. An efficient tabu algorithm for the single row facility layout problem. European Journal of Operational Research, 205(1), pp.98-105.
Samarghandi, H., Taabayan, P. & Jahantigh, F.F., 2010. A particle swarm optimization for the single row facility layout problem. Computers & Industrial Engineering, 58(4), pp.529-534.
Santana, R., Larrañaga, P. & Lozano, J., 2008a. Combining variable neighborhood search and Estimation of Distribution Algorithms in the protein side chain placement problem. Journal of Heuristics, 14, pp.519-547.
Santana, R., Larrañaga, P. & Lozano, J., 2008b. Combining variable neighborhood search and Estimation of Distribution Algorithms in the protein side chain placement problem. Journal of Heuristics, 14, pp.519-547.
Solimanpur, M., Vrat, P. & Shankar, R., 2005. An ant algorithm for the single row layout problem in flexible manufacturing systems. Computers & Operations Research, 32(3), pp.583-598.
Sule R, D., 2009. Manufacturing Facilities Location, Planning, and Design 3rd ed., CRC Press, Taylor & Francis Group.
Syswerda, G., 1993. Simulated crossover in genetic algorithms. Foundations of Genetic Algorithms, 2, pp.239-255.
Yang, I.-T. (NTUST), 2009. Particle Swarm Optimization (2) A. Lazinica, ed.
Zhang, Q. & Muhlenbein, H., 2004. On the convergence of a class of Estimation of Distribution Algorithms. IEEE Transactions on Evolutionary Computation, 8(2), pp.127-136.
Zhang, Q., Sun, J. & Tsang, E., 2005. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation, 9(2), pp.192-200.