臺灣博碩士論文加值系統

本篇論文針對飯店訂房的配置問題，提出一個混合型和弦搜尋演算法 (Hybrid Harmony Search Algorithm， HHSA)，其目的是要在有限的計算時間內找出一組最佳配置解，使得飯店訂房問題獲得最大利潤。混合型和弦搜尋演算法結合了 改良型和弦搜尋演算法 (IHS)與新型 和弦搜尋衍生演算法(NDHS)的優點主要核心參數為和弦記憶大小 (HMS)、和弦記憶考量率(HMCR)、節距調整率(PAR)與距離帶寬(BW)，以此為母體進行新可行解之搜尋與組合。接著將所提出的混合型和弦搜尋演算法，應用在飯店訂房限制收益最佳化問題以測試效能，飯店訂房限制收益最佳化問題是屬於困難的隨機模擬最佳化問題，具有很大的解空間。最後將所提出的演算法與粒子群演算法(PSO)、演化式策略(ES)、基因演算法(GA)、模擬退火法(SA)、人工蜂群演算法(ABC)以及傳統的和弦搜尋演算法(HS)等六種演算法進行比較，由模擬數據顯示所提出的混合型和弦搜尋演算法，不論在解的品質和計算效率上，都能獲得很好的測試結果。

In this thesis, a hybrid of harmony search algorithm, abbreviated as HHSA, is proposed to solve the hotel booking limits problem. The goal is to search for a good enough solution with the objective of maximizing the expected revenue using limited computation time. The proposed HHSA utilizes the advantage of improved harmony search algorithm and novel derivative harmony search algorithm. The core parameters contain the harmony memory size, harmony memory considering rate, pitch adjustment rate and distance bandwidth, which are used to search for the optimal solution from entire solution space. Then the proposed HHSA is applied to a hotel booking limits problem, which is formulated as a hard stochastic simulation optimization problem that consists of a huge solution space comprised by the vector of booking limits. Finally, the proposed HHSA is compared with the particle swarm optimization algorithm, evolutionary strategies, genetic algorithm, simulated annealing, artificial bee colony and traditional harmony search algorithm. The vector of good enough booking limits obtained by the proposed HHSA is promising in the aspects of solution quality and computational efficiency.

中文摘要...........................................................I
Abstract.........................................................II
誌 謝........................................................... III
目 錄.............................................................IV
圖目錄...........................................................VII
表目錄...........................................................VIII
第一章、緒 論......................................................1
1.1背景...........................................................1
1.2研究動機與目的..................................................4
1.3研究方法與論文架構...............................................6
第二章、進化式演算法群體智能演算法....................................8
2.1粒子群演算法(Particle Swarm Optimization, PSO)...................8
2.2演化式策略(Evolution Strategy, ES)..............................10
2.3基因演算法(Genetic Algorithm, GA)...............................12
2.4 模擬退火法(Simulated Annealing, SA).............................15
2.5 人工蜂群演算法(Artificial Bee Colony algorithm, ABC).............17
2.6 和弦搜尋演算法(Harmony Search Algorithm, HSA)...................19
2.6.1和弦搜尋演算法(HSA)............................................19
2.6.2改良型和弦搜尋演算法(IHSA).......................................22
2.6.3全域最佳和弦搜尋演算法(GHSA).....................................23
2.6.4自適應和弦搜尋全域最佳演算法(SGHSA)..............................24
2.6.5新型和弦全域搜尋演算法(NGHSA)...................................25
2.6.6新型和弦搜尋衍生演算法(NDHSA)...................................26
2.6.7智能型全域和弦搜尋演算法(IGHSA).................................27
第三章、混合型和弦搜尋演算法........................................28
3.1架構...........................................................28
3.2程式範例.......................................................32
第四章、飯店訂房配置問題與實驗結果比較................................40
4.1　飯店之起源、定義...............................................40
4.2　飯店訂房之意義.................................................45
4.3　飯店訂房之形式.................................................46
4.4　問題定義及數學式................................................47
4.5實驗說明.........................................................52
4.6 演算法步驟與參數設定.............................................53
4.7實驗結果.........................................................60
第五章、結論........................................................68
參考文獻............................................................69


圖目錄
圖 1. 近十年來臺旅客及國民出國人次變化........................................................4
圖 2. 近十年觀光外匯收入、國人國內旅遊收入及觀光總收入..........................................5
圖 3. 論文架構..............................................................................7
圖 4. 粒子群演算法(PSO)計算流程..............................................................9
圖 5. 演化式策略(ES)計算流程................................................................11
圖 6. 基因演算法(GA)計算流程................................................................12
圖 7. 基因演算法的交配圖例..................................................................13
圖 8. 基因演算法的突變例子..................................................................14
圖 9. 人工蜂群演算法(ABC)計算流程...........................................................17
圖 10.和弦搜尋演算法流程圖..................................................................19
圖 11. 混合型和弦搜尋演算法流程圖............................................................29
圖 12. 混合型和弦搜尋演算法程式流程圖........................................................32
圖 13. 飯店訂房問題輸入、輸出關係............................................................51
圖 14. 演算法的利潤值比較...................................................................67

表目錄
表 1. 初始化問題與參數設定..................................................................20
表 2. 參數設定.............................................................................33
表 3. 迭代次數NI=1之和弦記憶更新.............................................................35
表 4. 迭代次數NI=2之和弦記憶更新.............................................................37
表 5. 迭代次數NI=3之和弦記憶更新.............................................................39
表 6. 更新訂房限制的三種產品.................................................................49
表 7. 矩陣A保留現場入宿的資源................................................................52
表 8. 粒子群演算法(PSO)之參數設定............................................................54
表 9. 演化式策略(ES)之參數設定...............................................................55
表 10. 基因演算法(GA)之參數設定..............................................................56
表 11. 模擬退火法(SA)之參數設定..............................................................57
表 12. 人工蜂群演算法(ABC)之參數設定..........................................................59
表 13. 實驗環境.............................................................................60
表 14. 和弦記憶考量率(HMCR)之比較............................................................61
表 15. 和弦記憶大小(HMS)之比較...............................................................62
表 16. 最小與最大節距調整率( 與 )之比較.......................................................62
表 17. 最小與最大距離帶寬( 與 )之比較.........................................................63
表 18. 迭代次數.............................................................................65
表 19. 迭代次數.............................................................................65
表 20. 迭代次數.............................................................................66
表 21. 迭代次數.............................................................................66

[1] 賴詩婷，結合序優化與人工蜂群演算法求解飯店訂房問題， 碩士論文，
朝陽科技大學資訊工程系 ， 臺中， 2013。
[2] Lars Junghans, Nicholas Darde, “Hybrid single objective genetic algorithm
coupled with the simulated annealing optimization method for building
optimization”, Energy and Buildings, Vol 86, 2015, pp. 651 -662.
[3] Nicoletta Kessaris, Lorenza Magno, Anna Noren Rubin, Marcio Guiomar
Oliveira “Genetic programs controlling cortical interneuron fate”, Current
Opinion in Neurobiology, Vol 26, 2014, pp. 79-87.
[4] N. Moreira, T. Miranda, M. Pinheiro, P. Fernandes, D. Dias, L. Costa, J.
Sena-Cruz “Back analysis of geomechanical parameters in underground
works using an Evolution Strategy algorithm”, Tunnelling and Underground
Space Technology, Vol 33, 2013, pp. 143-158.
[5] Saúl Domínguez-Isidro, Efrén Mezura-Montes, Luis-Guillermo OsorioHernández, “Evolutionary programming for the length minimization of
addition chains”, Engineering Applications of Artificial Intelligence, Vol
37, 2015, pp. 125-134.
[6] D.Karaboga, B. Basturk, “A powerful and efficient algorithm for numerical
function optimization: artificial bee colony (ABC) algorithm”, Journal of
Global Optimization, November 2007, Vol 39, Issue 3, pp. 459-471 .
[7] J.Kennedy, R.C. Eberhart, “Particle Swarm Optimization”, IEEE International
Conference on Neural Networks, Vol 4, 1995, pp. 1942-1948.
[8] Xu Zhou, Yanheng Liu, Jindong Zhang, Tuming Liu, Di Zhang “An ant
colony based algorithm for overlapping community detection in complex
networks”, Physica A: Statistical Mechanics and its Applications, Vol 427,
2015, pp. 289-301 .
[9] Hanning Chen, Ben Niu, Lianbo Ma, Weixing Su, Yunlong Zhu “Bacterial
colony foraging optimization”, Neurocomputing, Vol 137, 2014, pp. 268-
284.
[1 0] Md. Abul Kalam Azad, Ana Maria A.C. Rocha, Edite M.G.P. Fernandes,
“Improved binary artificial fish swarm algorithm for the 0–1
multidimensional knapsack problems”, Swam and Evolutionary
Computation, Vol 14, 2014, pp. 66-75.
[11 ] Erik Cuevas, Miguel Cienfuegos, Daniel Zaldívar, Marco Pérez-Cisneros “A
swarm optimization algorithm inspired in the behavior of the social-spider”,
Expert Systems with Applications, Vol 40, Issue 16, 2013, pp. 6374-6384.
70
[1 2] Wen-Tsao Pan, “A new Fruit Fly Optimization Algorithm: Taking the
financial distress model as an example”, Knowledge-Based Systems, Vol 26,
2012, pp. 69-74.
[1 3] Ayad Mashaan Turky, Salwani Abdullah, Nasser R. Sabar, “A Hybrid
Harmony Search Algorithm for Solving Dynamic Optimisation
Problems”, Procedia Computer Science, Vol 29, 2014, pp. 1926-1936.
[1 4] Jing.Chen, Quan-ke Pan, Jun-qing Li, “Harmony search algorithm with
dynamic control parameters”, Applied Mathematics and Computation, Vol
219, Issue 2, 2012, pp. 592-604.
[1 5] Ehsan Valian, Saeed Tavakoli, Shahram Mohanna, “An intelligent global
harmony search approach to continuous optimization problems”, Applied
Mathematics and Computation, Vol 232, 2014, pp. 670-684.
[1 6] M. Mahdavi, M. Fesanghary, E. Damangir, “An improved harmony search
algorithm for solving optimization problems”, Applied Mathematics and
Computation, Vol 188, Issue 2, 2007, pp. 1567-1579.
[1 7] Mahamed G.H. Omran, Mehrdad Mahdavi, “Global-best harmony search”,
Applied Mathematics and Computation, Vol 198, 2008, pp. 643-656.
[1 8] Quan-Ke Pan, P.N. Suganthan, M. Fatih Tasgetiren, J.J. Liang, “A selfadaptive global best harmony search algorithm for continuous optimization
problems”, Applied Mathematics and Computation, Vol 216, Issue 3, 2010,
pp. 830-848.
[19] Dexuan Zou, Liqun Gao, Jianhua Wu, Steven Li, “Novel global harmony
search algorithm for unconstrained problems”, 10th Brazilian Symposium on
Neural Networks, Vol 73, Issue 16-18, 2010, pp. 3308-3318.
[20] Jing.Chen, Quan-ke Pan, Jun-qing Li, “Harmony search algorithm with
dynamic control parameters”, Applied Mathematics and Computation, Vol
219, Issue 2, 2012, pp. 592-604.
[21 ] Ehsan Valian, Saeed Tavakoli, Shahram Mohanna, “An intelligent global
harmony search approach to continuous optimization problems”, Applied
Mathematics and Computation, Vol 232, 2014, pp. 670-684.
[22] 交通部 觀光局行政資訊系統 , 觀光統計圖表 . [Online]. Available:
http://admin.taiwan.net.tw/public/public.aspx?no=315.
[23] 李欽明，旅館客房管理實務(精華版)， 揚智文化事業股份有限公司， 2010
第 96-97 頁。
[24] 李欽明，旅館客房管理實務， 揚智文化事業股份有限公司 ， 1998。
[25] SimOpt.org, Booking limits at a hotel: Baby. [Online]. Available:
http://www.simopt.org, 2011 .