現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:基於MapReduce的基因演算法於旅遊行程規劃之研究 [以論文名稱查詢館藏系統]
論文英文名稱:The Study of MapReduce based Genetic Algorithm on Tour Planning [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:資訊管理研究所
畢業學年度:102
出版年度:103
中文姓名:楊浩
英文姓名:Hao Yang
研究生學號:101938003
學位類別:碩士
語文別:中文
口試日期:2014-07-01
論文頁數:56
指導教授中文名:翁頌舜
口試委員中文名:吳瑞堯;楊欣哲;蕭瑞祥
中文關鍵詞:旅遊規劃旅行推銷員問題基因演算法MapReduce
英文關鍵詞:Travel PlanningTraveling Salesman ProblemGenetic AlgorithmsMapReduce
論文中文摘要:近年來,行動網路以及手持行動裝置快速的發展與普及,資料快速的流通,人們在旅遊時採用自助旅行的方式占了八成以上。自助旅行從規劃到執行都必須自行處理,如何在各種限制下規劃出最節省交通時間的旅遊行程最為關鍵,這往往決定整趟旅遊的成敗。在眾多的旅遊服務中大多著重於熱門景點的推薦,缺乏旅遊行程規劃之研究,規劃時間不但長且規劃結果不佳,故本研究提供一套系統,提供旅遊行程規劃服務,並改善進行規劃的基因演算法,在較短時間內提供使用者較佳的行程規劃建議。
本研究以行動裝置為主要溝通介面,提供使用者在任何時空環境下皆可以進行旅遊資訊查詢與旅遊路線規劃。旅遊規劃利用基於主從式架構的MapReduce基因演算法來求解,並結合最近鄰居法以及特殊的交配模式的基因演算法來提升運算效能與結果,以這樣的架構在短時間內來滿足使用者行程規劃的需求。
從本研究的實驗結果發現,提出的基因演算法用於解決行程規劃提升結果品質達44.89%,且將演算法架構於MapReduce方法中也提升了執行效率27.45%,從這些結果中可以發現本研究提出的架構有良好的效果。
論文英文摘要:In recent years, mobile networks and mobile devices are rapidly developed and popularized. Information is in circulation rapidly. In tourist industry, the type of independent travel has occurred more than eighty percent. Independent travelers must handle their own trips from planning to implementation. How to plan the most time-saving transportation during the travel period is the most critical concern, which often determines the success or failure of the trip. Most traveling services focus on the attractions recommendation, lack of research regarding travel planning. This study proposes a system that users can plan their own trips. This study also tries to improve the planning algorithm so that in such a structure to meet the needs of users in shorter time.
In this study, a mobile device is used as the primary communication interface. It provides the user for searching information and planning the trip in any environment. Travel planning is helped based on Genetic Algorithm with MapReduce mechanism, the master-slave architecture on a Hadoop cloud platform. This study also proposes an enhanced Genetic Algorithm. It combines the Nearest Neighbor method and uses the unusual crossover approach to improve the performance and results. As the result shows, the system proposed in this study satisfies users’ needs.
As the result shows, the proposed genetic algorithm for solving travel planning enhances the quality of the planning results of 44.89%. The algorithms based on MapReduce method also improves the efficiency of 27.45%. From the results of this study, it shows that the proposed framework has a good effect.
論文目次:摘 要 i
英文摘要 ii
誌 謝 iv
目 錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 背景與動機 1
1.2 研究目的 4
1.3 研究架構 5
第二章 文獻探討 6
2.1 巨量資料(Big Data) 6
2.2 旅遊行程規劃 7
2.3 旅行推銷員問題(Traveling Salesman Problem) 8
2.4 基因演算法(Genetic Algorithm) 10
2.5 用於旅行推銷員問題的基因演算法 16
2.6 平行基因演算法(Parallel Genetic Algorithm) 17
2.7 MapReduce 20
2.8 基於MapReduce基因演算法相關應用與研究 21
第三章 研究方法 23
3.1 研究架構 23
3.2 使用者情境 26
3.3 數學模型 28
3.4 基因演算法設計 29
3.5 基於MapReduce的基因演算法 33
第四章 實驗設計與結果 35
4.1 實驗環境 35
4.2 實驗資料 35
4.3 基因演算法參數設定 36
4.4 執行效率探討 42
4.5 規劃結果比較 42
4.6 使用者介面 46
第五章 結論與未來展望 51
5.1 結論 51
5.2 研究限制與未來展望 53
參考文獻 54
論文參考文獻:1. 中華民國交通部觀光局,觀光市場調查。http://admin.taiwan.net.tw/statistics/market.aspx?no=133
2. 張偉振,「應用群蟻演算法於旅遊路線規劃之研究」,碩士論文,朝陽科技大學建築及都市設計研究所,2009。
3. 王裕廷,「基因演算法應用於具時窗限制之多天旅遊行程規劃」,碩士論文,長榮大學資訊管理學系,2010。
4. 楊郁樓,「旅遊行程規劃模式與系統之建置-以台北市為起點之旅遊為例」,碩士論文,國立台灣大學地理環境資源學系,2010。
5. 蔡碧展,「基於Hadoop平台的雲端基因架構」,碩士論文,國立高雄應用科技大學資訊管理系,2010。
6. Carter, A. E. and Ragsdale C. T., “A new approach to solving the multiple traveling salesperson problem using genetic algorithms,” European Journal of Operational Research, vol. 175, no. 1, 2006, pp. 246-257.
7. Dao, T. H., Jeong, S. R. and Ahn, H., “A novel recommendation Model of Location-based Advertising: Context-aware Collaborative Filtering using GA Approach,” Expert Systems with Applications, vol. 39, no. 3, 2012, pp. 3731-3739.
8. Dean, J. and Ghemawat, S., “MapReduce: Simplified data processing on large clusters,” Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, San Francisco, CA, 2004, pp. 137-150.
9. Fajardo, J. T. B. and Oppus, C. M., “A mobile disaster management system using the android technology,” WSEAS Transactions on Communications, vol. 9, no. 6, 2010, pp. 343-353.
10. Geronimo, L. D., Ferrucci, F., Murolo, A. and Sarro, F., “A Parallel Genetic Algorithm Based on Hadoop MapReduce for the Automatic Generation of JUnit Test Suites,” Proceedings of IEEE Fifth International Conference on Software Testing, Verification and Validation, Montreal, 2012, pp. 785-793.
11. Hameed, M. A., Malik, M. A., Sayeedunnisa, S. F. and Imroze, H., “An Effective Hybrid Algorithm in Recommender Systems Based on Fast Genetic k-means and Information Gain,” Proceedings of Fourth International Conference on Computational Intelligence and Communication Networks, Uttar Pradesh, 2012, pp. 860-865.
12. Holland, J. H., Adaptation in Natural and Artificial Systems, USA: University of Michigan Press, 1975.
13. Jin, C., Vecchiola, C. and Buyya, R., “MRPGA: An Extension of MapReduce for Parallelizing Genetic Algorithms,” Proceedings of IEEE Fourth International Conference on eScience, Indianapolis, 2008, pp. 214- 221.
14. Kaur, D. and Murugappan, M. M., “Performance enhancement in solving Traveling Salesman Problem using hybrid genetic algorithm,” North American Fuzzy Information Processing Society, New York, 2008, pp. 1-6.
15. Keast, S. L., A Simple Representation Technique to Improve GA Performance, Department of Computer Science and Software Engineering, Auburn University, Auburn, Alabama, 2003.
16. Kinoshita, T., Nagata, M., Shibata, N., Murata, Y., Yasumoto, K. and Ito, M., ”A Personal Navigation System for Sightseeing across Multiple days,” Proceedings of the 3rd International Conference on Mobile Computing and Ubiquitous Networking, London, 2006, pp. 254-259.
17. Negnevitsky M., Artificial Intelligence: A Guide to Intelligent Systems (2nd Edition), USA: Addison Wesley, 2005.
18. Singh, A. and Baghel, A. S., ”A new grouping genetic algorithm approach to the multiple traveling salesperson problem,” Soft Computing, vol. 13, no. 1, 2009, pp. 95-101.
19. Vansteenwegen, P., Souffriau, W. and Van Oudheusden, D., “The city trip planner: An expert system for tourists,” Expert System with Application, vol. 38, no. 6, 2011, pp. 6540-6546.
20. Yuan, S., Skinner, B., Huang, S. and Liu, D., “A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms,” European Journal of Operational Research, vol. 228, no. 1, 2013, pp. 72-82.
21. Zec, A., Konjicija, S. and Nosović, N., “Hybrid approach in design of GA implementation for MapReduce,” Proceedings of IEEE Ninth International Symposium on Telecommunications, Bucharest, 2012, pp. 1-6.
論文全文使用權限:同意授權於2019-08-11起公開