臺灣博碩士論文加值系統

設施佈置問題是想在一些限制下找到經濟效益最高的設施佈置方式，這類問題已在工廠、倉庫、辦公室等地方可看見。設施佈置問題有許多不同的面相，例如：設施的大小形狀在擺放過程中能不能改變、設施需不需要被擺放在固定的位置、廠區內的限制等。對於不同的設施佈置問題有許多人使用了不同的演算法來解決，已有人使用了演化演算法來解設施佈置問題並得到不錯的解。本論文使用了演化演算法來解決設施佈置問題，並採用在解決數值最佳化問題表現優異的L-SHADE演算法。本論文將各個設施所放置的地方座標化，使用實數集合的方式來表示各個設施的位置及旋轉與否。針對所要解決的設施佈置問題，本研究設計了適應值評估函式，並以此來評估演算法產生出來的候選解的品質。由於在演化的過程中，候選解的設施佈置方式造成設施之間經常有重疊的現象發生，我們提出了一種修復方法來解決此問題，使得候選解的設施佈置方式不會有重疊現象的發生。在許多問題上，演算法會使用區域搜尋的方式來加速找到品質較佳的解，本論文也使用了區域搜尋。第一個實驗單純使用修復方法，所提出的演算法可以在演化前期找到較好的解，但在演化中後期因候選解的設施佈置方式已無重疊的現象，所以效果不彰。第二個實驗則單純使用區域搜尋的方式，演算法可以透過設施交換的方式找到更好的解，但若將演化代數增加，最後的結果差異不大，因為單純的做設施交換很可能造成候選解有重疊現象的發生，使得解較差。第三個實驗將區域搜尋與修復方法結合，不僅可以讓演化演算法在演化的前期找到較佳的解，在後期也可以透過設施交換及修復方法找到更好的解。

1 緒論7
1.1 背景. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 挑戰與動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 文獻探討11
2.1 方法用於解各式設施佈置問題. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 L-SHADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 問題定義15
4 研究方法18
4.1 L-SHADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.2 適應值評估函式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 修復方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.1 決定優先順序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.2 向外解開重疊. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4 區域搜尋. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 實驗結果與討論30
5.1 對於修復方法的比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.2 對於區域搜尋的比較. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.3 對於區域搜尋加修復方式的比較. . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 結論與未來展望48

[1] G. C. Armour and E. S. Buffa. A heuristic algorithm and simulation approach to relative
location of facilities. Management Science, 9:294–309, 1963.
[2] R. E. Burkard and K.‐H. Stratmann. Numerical investigations on quadratic assignment
problems. Naval Research Logistics Quarterly, 25:129–148, 1978.
[3] A. Drira, H. Pierreval, and S. Hajri-Gabouj. Facility layout problems: A literature analysis.
IFAC Proceedings Volumes, 39:389–400, 2006.
[4] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman & Co., 1979.
[5] M. H. Imam and M. Mir. Nonlinear programming approach to automated topology optimization.
Computer-Aided Design, 21:107–115, 1989.
[6] M. H. Imam and M. Mir. Automated layout of facilities of unequal areas. Computers &
Industrial Engineering, 24:355–366, 1993.
[7] K. Komarudin and K. Y. Wong. Applying ant system for solving unequal area facility
layout problems. European Journal of Operational Research, 202:730–746, 2010.
[8] T. C. Koopmans and M. Beckmann. Assignment problems and the location of economic
activities. Econometrica, 25:53–76, 1957.
[9] K. Y. Lee, S. Han, and M.-I. Roh. An improved genetic algorithm for facility layout
problems having inner structure walls and passages. Computers & Operations Research,
30:117–138, 2003.
[10] Y. H. Lee and M. H. Lee. A shape-based block layout approach to facility layout problems
using hybrid genetic algorithm. Computers & Industrial Engineering, 42:237–248, 2002.
[11] M. Mir and M.H. Imam. A hybrid optimization approach for layout design of unequal-area
facilities. Computers & Industrial Engineering, 39:49–63, 2001.
[12] M. A. Mohammed and R. A. Hasan. Particle swarm optimization for facility layout problems
flp 2014; a comprehensive study. In 2017 13th IEEE International Conference on
Intelligent Computer Communication and Processing (ICCP), 2017.
[13] M. Rajasekharan, B.A. Peters, and T. Yang. A genetic algorithm for facility layout design
in flexible manufacturing systems. International Journal of Production Research, 36:95–
110, 1998.
[14] S. Sahni and T. Gonzalez. P-complete approximation problems. J. ACM, 23:555–565,
1976.
[15] K. Y. Tam. Genetic algorithms, function optimization, and facility layout design. European
Journal of Operational Research, 63:322–346, 1992.
[16] R. Tanabe and A. Fukunaga. Success-history based parameter adaptation for differential
evolution. In 2013 IEEE Congress on Evolutionary Computation, 2013.
[17] R. Tanabe and A. S. Fukunaga. Improving the search performance of shade using linear
population size reduction. In 2014 IEEE Congress on Evolutionary Computation (CEC),
2014.
[18] M.-J. Wang, M. H. Hu, and M.-Y. Ku. A solution to the unequal area facilities layout
problem by genetic algorithm. Computers in Industry, 56:207–220, 2005.
[19] D. Zhao, C. Aranha, and H. Kanoh. Solving facility layout problems using evolutionary
strategy based on levy flight. In 2016 IEEE 9th International Workshop on Computational
Intelligence and Applications (IWCIA), 2016.
[20] D. Zhao, C. Aranha, and H. Kanoh. Solving real-world facility layout problems using
ga with levy flights and multi-decoding. In 2017 18th IEEE/ACIS International Conference
on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed
Computing (SNPD), 2017.
52