運用人工粒子群演算法解決單列機台佈置問題｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	英妲 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
相關次數：	點閱：244 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

直線單排設施規劃問題(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.

Abstract	i
中文摘要	ii
Acknowledgements	iv
Table of Contents	v
List of Figures	vii
List of Tables	viii
Introduction	1
1.	Background	1
2.	Objective	2
3.	Scope and Assumptions	2
4.	Organization of Thesis	3
Literature Review	4
1.	Estimation Distribution Algorithm and Its Hybridizations	4
2.	Single Row Facility Layout Problem	5
3.	Enhanced Single Row Facility Layout Problem	6
4.	Particle Swarm Optimization	7
5.	Tabu Search Algorithm	8
6.	Meta-heuristic Algorithms for Solving Single Row Facility Layout Problem	9
Methodology	10
1.	Problem Description and Mathematical Model	10
1.1.	Single Row Facility Layout Problem	10
1.2.	Enhanced Single Row Facility Layout Problem	11
2.	Development of Algorithms	12
2.1.	Chromosome or Particle Representation	13
2.2.	General Procedure of eACGA	13
2.3.	General Procedure of EDAtabu	15
2.4.	General Procedure of EDAPSO	15
3.	Artificial Particle Swarm Optimization Procedure	17
3.1.	Estimation Distribution Algorithm Part	20
3.2.	Particle Swarm Optimization Part	22
3.3.	Local Search based on Tabu Search Algorithm Part	23
Experiments Analysis	25
1.	Parameters	25
2.	APSO for SRFLP	26
3.	Hypothesis Testing	31
4.	APSO for enhanced SRFLP	32
5.	Sensitivity Analysis for enhanced SRFLP	34
5.1.	Case 1 : Similar length of facilities	34
5.2.	Case 2 : Normal distribution for flow between facilities	35
Discussion and Conclusions	37
1.	Discussion	37
2.	Conclusions	37
3.	Contributions	38
4.	Future Research	39
REFERENCES	40
APPENDIX A	43
APPENDIX B	47

                                

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.

簡易檢索 / 詳目顯示

相關論文