臺灣博碩士論文加值系統

參觀博物館為國內常見的課外活動與校外學習，亦是國外旅遊團來台參訪的重要行程之一。對於有事先預約的團體，博物館通常會安排領隊帶領團體參觀展覽品並講解展覽品的由來，參觀路徑是根據參觀團體的參觀時間來安排，以避免路線雍塞或排隊而造成時間的浪費。

本研究探討博物館路徑問題，此問題需同時規劃多個團體參觀展覽室的路徑，其中各團體有必須觀看的展覽室和選擇觀看的展覽室，問題目標為最小化完成參觀時間。本研究探討博物館路徑問題為NP-hard問題，我們嘗試以基因演算法(Genetic Algorithm)、免疫演算法(Immune Algorithm)、粒子群演算法(Particle Swarm Optimization，PSO)三種演算法對此博物館路徑問題進行求解。本研究針對團體數量大於展覽室數量的情況下，對於不同的參觀率組合條件，分別求解團體參觀展覽室的最小完成時間。除此之外，我們亦將三種演算法做比較，實驗數值結果顯示，基因演算法與免疫演算法的差異性不大，均優於粒子群演算法，且皆能有效地解決此問題。

Museum visit is a common domestic extracurricular and fieldtrip learning activity; and it is also one of the important stops for foreign tour groups to visit Taiwan. For groups that make an appointment in advance, the museum usually arranges tour guides to show visitors around exhibits or explain the origin of the exhibits. The visit route is usually arranged depending on the groups’ time of visit, so as to avoid congestion or queuing that wastes time.
This thesis explored the museum routing problem. This problem involves planning of routes for a number of groups that visit several exhibition rooms at the same time. In particular, there are must-visit exhibition rooms and select-exhibition rooms for operational viewing. The goal of this museum routing problem is to minimize the visit times (makespans) of groups. This study investigated the museum routing problem, which is an NP-hard problem. In this thesis, we attempt to solve the museum routing problem by three algorithms, namely, genetic algorithm, immune algorithm, and particle swarm optimization. Targeting the situation where the number of groups is higher than the number of exhibition rooms available, the test problems of combinations of various visit rates were solved with the objective of minimizing visit times (makespans) of groups. In addition, numerical results of three algorithms were provided and compared. The experimental results show that genetic algorithm and immune algorithm showed no significant differences and they are both better than swarm optimization method. Furthermore, as shown, the test problems were all effectively resolved.

摘要......................................................i
ABSTRACT................................................ii
誌謝....................................................iii
表目錄...................................................vi
圖目錄..................................................vii
第一章 緒論..............................................1
1.1研究背景與動機..........................................1
1.2研究目的...............................................1
1.3研究方法與步驟..........................................2
1.4論文架構...............................................2
第二章 文獻探討..........................................4
2.1博物館遊客路徑問........................................4
2.2相關的排程問題..........................................5
2.3開放式排程問題..........................................6
第三章 研究問題與方法.....................................7
3.1研究方法...............................................7
3.1.1基因演算法...........................................7
3.1.2免疫演算法...........................................11
3.1.3粒子群演算法.........................................13
3.1.4田口實驗設計.........................................15
3.2研究問題..............................................18
3.2.1問題描述............................................18
3.2.2假設................................................19
3.2.3編碼方式............................................19
3.2.4參數設定............................................22
第四章 測試問題、測試結果與討論...........................27
4.1設備環境及演算法參數設定................................27
4.2測試問題..............................................27
4.3測試結果..............................................36
4.3.1雲林布袋戲館數據結果分析(團體數=5，展覽室數=4)...........36
4.3.2國立臺灣歷史博物館數據結果分析(團體數=10，展覽室數=6).....40
4.3.3中台山博物館數據結果分析(團體數=15，展覽室數=8)..........45
4.3.4科學博物館數據結果分析(團體數=20，展覽室數=10)...........51
4.3.5各演算法測試結果之比較................................54
4.4統計檢定..............................................56
第五章 結論..............................................62
5.1結論.................................................62
5.2未來研究方向..........................................62
參考文獻.................................................64
附錄A...................................................66
附錄B...................................................68
附錄C...................................................70
附錄D...................................................72
Extended Abstract......................................74
簡歷....................................................77

1.吳淑華(2012)，「博物館展示配置與參觀行為關係之研究」，科技博物，16卷，3期，頁89-108。
2.吳獻堂(2009)，人工智慧在工程分析上之應用以簡單基因演算法為基礎，朝陽科技大學出版。
3.宋祚忠、楊劍東、蒲創城(2011)，「造船廠船段組合作業排程問題之研究」，中國造船暨輪機工程學刊，30卷，3期，頁139-156。
4.李金華、朱道立(2010)，「基於Multi-agent的大型會展活動的遊客協調控制方法」，系統工程學報，25卷，4期，頁499-505。
5.李騏華(2012)，人工智慧法於具時效性傳染病疫苗最佳施打問題的探討，國立虎尾科技大學工業工程與管理研究所，碩士論文。
6.林晉宏(2007)，基因演算法求解作業不同到達時間之open shop雙目標排程問題之研究，國立勤益科技大學工業工程與管理系碩士班，碩士論文。
7.林豐澤(2005)，「演化式計算下篇：基因演算法以及三種應用實例」，東北大學資訊科學與工程學院系統工程學報，3卷，2期，頁29-56。
8.洪士程、楊逢羿(2010)，「序的最佳化於隨機工程生產排程問題之應用」，資訊科技國際期刊；4卷，2期，頁22-34。
9.張鴻志(2005)，整合人工免疫系統與類神經網路於製程參數最佳化之研究以IC半導體封裝之銲線製程為例，國立雲林科技大學工業工程與管理研究所，碩士論文。
10.許正良(2013)，應用人工智慧法於居家照顧服務排程路徑規劃問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。
11.喻奉天(2012)，「以粒子群演算法求解開放式區域車輛途程問題」，中華民國運輸學會101年學術論文研討會。
12.黃柏輔(2010)，利用多重軌跡搜尋演算法解決開放式工廠排程問題，中興大學資訊網路多媒體研究所，碩士論文。
13.黃祥熙(2011)，排程理論，http://hhuang.ism.tw/Teach/Attach/99-2%20%E6%8E%92%E7%A8%8B%E7%90%86%E8%AB%96(%E7%A2%A9%E5%A3%AB%E7%8F%AD).pdf，引用日期：2014.05.08。
14.溫演福、蔡孟軒、何明建、張智隆、賴妤欣、周俊佑(2010)，「根基於RFID之個人化互動式導覽系統--動態路徑規劃及認養」，2010第六屆知識社群研討會。
15.鄧宗倫(2010)，應用人工智慧法於最佳消毒作業之時窗限制車輛途程問題，國立虎尾科技大學工業工程與管理研究所，碩士論文。
16.謝佩璇、舒仲璿、詹佩穎、陳俊穎、劉家伃(2010)，國立成功大學博物館導覽系統最短路徑規劃之研究。國科會計畫編號：NSC 99-2815-C-006-016-H。
17.顏上堯、郭俊志、蕭妃晏(2012)，「航機維護工廠年度停機排程調整最佳化模式之研究」，運輸計劃季刊，41卷，3期，頁311-344。
18.顏上晴(2002)，「博物館到館參觀導引研究－以國立科學工藝博物館為例」，科技博物，6卷，3期，頁47-61。
19.蘇昭銘、程培倫、郭旻鑫(2001)，「捷運系統列車排程決策支援系統」，運輸計劃季刊；30卷，2期，頁409-437。
20.蘇朝墩(2009)，品質工程，中華民國品質學會，台北。
21.Besbes, W., Loukil, T. & Teghem, J. (2006) “Using genetic algorithm in the multiprocessor flow shop to minimize the makespan”, Proceedings of the International Conference on Service Systems and Service Management, Vol. 2, pp. 1228–1233.
22.Fowler, J.W., & Rose, O. (2004). “Grand challenges in modeling and simulation of complex manufacturing systems”, Simulation, Vol. 80, pp.469-476.
23.Hu, X., Eberhart, R.C. & Shi Y. (2003). “Particle swarm with extended memory for multiobjective optimization”, Swarm Intelligence Symposium, pp.193-197.
24.Jurcik, K. (2009). “Open shop scheduling to minimize makespan”, Department of Mathematical Sciences Lakehead University Thunder Bay, Ontario.
25.Kennedy, J. & Eberhart, R.C. (1995). “A new optimizer using particle swarm theory”, Proceeding of the Sixth International Symposium on Micro machine and Human Science, pp.39-43.
26.Lin, H.H. (2010) “A multi-objective particle swarm optimization for openshop scheduling problems”, Sixth International Conference on Natural Computation, pp.3706-3710.
27.Lin, J.C., & Huang, Y.M. (2011). “A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems”, Expert Systems with Applications, Vol. 38 No. 5, pp.5438-5447.
28.Panahi, H. (2011) “Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization”, Expert Systems with Applications: An International Journal, Vol. 38, No. 3, pp.2817–2822.
29.Tsai, J.T., Liu, T.K., & Chou, J.H. (2004). “Hybrid taguchi-genetic algorithm for global numerical optimization”, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 4, pp.365-377.
30.Younes, M. & Rahli, M. (2006). “On the choice genetic parameters with taguchi method applied in economic power dispatch”, Leonardo Journal of Sciences, Issue 9 , pp.9-24.
31.Yu, V.F., Lin, S.W. & Chou, S.Y. (2010). “The museum visitor routing problem”, Applied Mathematics and Computation, Vol. 216, Issue3, pp.719-729.