和聲搜尋演算法應用於不等面積設施佈置問題

Applying Harmony Search Algorithm to Unequal-Area Block Facility Layout Problem

顧庭禎(Ting-Chen Ku)

指導教授 ： 張美香

中原大學/工學院/土木工程研究所/碩士(2011年)

https://doi.org/10.6840/cycu201100125

摘要

設施佈置問題(Facility Layout Problem)是一典型組合最佳化問題。本研究利用切割樹結構搭配自我適應式和聲搜尋法求解不等面積設施佈置問題。SGHS與和聲搜尋法(Harmony Search Algorithm, HS)最大的差別在於利用學習週期(Learning Mechanisms, LP)，讓和聲記憶考量(Harmony Memory Consideration Rate, HMCR)與調音機率(Pitch Adjustment Rate, PAR)經由常態分配(Normal Distribution)方式自我產生。此外，新發展的調音機制是由子樹間的調音與子樹內的調音所組成。
為了評估此方法的有效性，本研究針對具代表性的問題做了一系列的測詴，並與文獻上的求解結果比較，問題如：O7、O8、O9與Ba12。而較大的例子如Du62也曾在合理的時間內求解到答案。

關鍵字

不等面積設施佈置 ； 自我適應式和聲搜尋法 ； 切割樹結構

並列摘要

The Facility Layout Problem (FLP) is a typical combinational optimization problem. In this research, a slicing tree and self-adaptive harmony search (SGHS) based heuristic is proposed for solving unequal-area block layout problem. The major difference between SGHS and harmony search (HS) is the harmony memory consideration rate and pitch adjustment rate of SGHS are dynamically adapted by the learning mechanisms. Furthermore, the newly developed pitch adjustment is composed of two schemes, intra-subtrees and inner-subtrees.
To evaluate the effectiveness of this approach, a series of computational experiments are performed and testing results are compared to those found in the literature. Datasets of well known problems, O7, O8, O9, and Ba12 are used for demonstration. Additionally, a large problem instance comprised of 62 facilities has been solved in reasonable time.

並列關鍵字

unequal-area block layout problem ； self-adaptive harmony search algorithm ； slicing tree structure

參考文獻

3. 楊偉智（2009），和聲搜尋法於巨大廢棄物回收網路設計之探討，中原大學土木工程學系，碩士論文。

4. 劉向邦（2008），以和諧搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究，中央大學土木工程學系，碩士論文。

5. 羅冠君（2008），基於和聲搜尋法與離散拉格郎日法之混合演算法於結構最佳化設計的研究，中央大學土木工程學系，碩士論文。

2. 徐開評（2009），應用和聲演算法探討溫室氣體排放限制下之電力系統容量擴增計畫，中原大學土木工程學系，碩士論文。

1. 王明展（2003），基因演算法應用於設施佈置問題之研究，元智大學工業工程學系，博士論文。