研究生: |
陳柏志 Bo-jhih Chen |
---|---|
論文名稱: |
以礦工基因演算法求解旅行商問題 Using Miners Genetic Algorithm to Solve Travelling Salesman Problems |
指導教授: |
葉瑞徽
Ruey Huei Yeh |
口試委員: |
張文亮
none 吳建瑋 none |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2012 |
畢業學年度: | 100 |
語文別: | 中文 |
論文頁數: | 55 |
中文關鍵詞: | 基因演算法 、TSP 、MGA 、貪婪演算法 、通用啟發式演算法 |
外文關鍵詞: | TSP, MGA |
相關次數: | 點閱:185 下載:1 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本論文針對基因演算法的架構加以改良,提出改良後的新式演算法:礦工基因演算法(Miners Genetic Algorithms, MGA)。為了驗證礦工基因演算法的效率,本研究以旅行商問題(Travelling Salesman Problem, TSP)做為範例驗證。測試結果發現礦工基因演算法與基因演算法相比,不但較易於進行參數設置,其求解品質也有較佳的表現(即能在相同時間內獲取較佳的解)。 測試結果也發現,將礦工基因演算法加入些許改良方法,能使求解品質更為提高,在研究中也將上述的方法,簡稱為MGA_GM。最後將MGA_GM與國際學者們所提出之眾多通用啟發式演算法相比,發現MGA_GM的求解品質皆較佳,由此可知MGA_GM,是可行的新式演算法。
This thesis modifies the structure of Genetic Algorithms (GA) to develop a new algorithm to solve the Traveling Salesman Problem (TSP). The new algorithm is called Miners Genetic Algorithms (MGA). The MGA includes three phases as follows: (i) Mining, (ii) Exploration and (iii) Communication. The first phase (Mining) takes down all of the solutions on a mining location. The second phase (Exploration) searches new mining locations. The last phase (Communication) decides a mining location through the information of different mining. Since the MGA is a improve version of the GA, the MGA has the advantage of the GA. In addition, the MGA does not set the mutation and mating rates. In order to verify the efficiency of the MGA, the TSP examples are given to illustrate the efficiency of the MGA. Further, the efficiency of the MGA is compared with the GA for the TSP. In the TSP examples, we find that the initial value of MGA is produced using the Greed Algorithm and have more Explorations, which can find the better solution for TSP. Therefore, this method is called MGA_GM. In this thesis, the MGA_GM is compared with some heuristic algorithms for TSP. The comparison results show that the efficiency of MGA_GM is better than the other algorithms.
中文文獻:
[1]林昇甫、徐永吉(2009 年),遺傳演算法及其應用,第1~5頁,台北,五南圖書出版公司。
[2]謝新銘(2006年),「使用基因演算法提升影像解析度」,逢甲大學電機工程學系碩士班碩士論文。
[3]李宜修(2008年),「基因型模糊推論軟體品質評估系統」,國立成功大學資訊工程學系碩士論文。
[4]陳柏宏(2009年),「利用基因演算法探討無限感測連接支配集合問題」,義守大學資訊管理研究所碩士論文。
[5]余彥儒(2010年),「圖書館書籍通閱移送之車輛途程問題-巨集啟發式演算法之應用」,中央大學土木工程學系碩士論文。
[6]陳奕憲(2011年),「基因演算法在國民中學排課問題之最佳化研究」,南華大學資訊管理學系碩士論文。
[7]熊彥銘、毛凌、楊戰平(2012 年),「基於遺傳算法的時間決策系統標定優化方法」,電子科技大學學報,第41卷,第1期,80-84。
[8]吳泰熙、吳奕樺、張欽智(2006年),「以基因演算法求解單原片方形物件排列問題」,科學與工程技術期刊,第2卷,第3期,75-83。
[9]李佩玲(2006年),「以混合基因與粒子群演算法求解旅行銷售員問題」,中原大學資訊管理學系碩士論文。
[10]袁浩(2010年),「基于改進蜂群算法無線傳感器感知節點部屬優化」,計算機應用研究,第27卷,第7期,2704-2708。
[11]林鴻鈞(2011年),「運用電磁演算法於屬性篩選:理論與應用」,國立清華大學工業工程與工程管理學系博士論文。
[12]韓宇德(2007年),「貪婪演算法結合區域搜尋演算法求解TSP組合最佳化問題」,立德管理學院應用資訊研究所碩士論文。
[13]郭定(2009年),「基因演算法中不同選擇策略的替代性與互補性」,科學與工程技術期刊,第5卷,第2期,25-34。
[14]曾郁展(2005年),「DSP-Based之即時人臉辨識系統」,國立中 山大學電機系碩士論文。
[15]林家富、劉宏毅、蔡金橤、郭東義(2010年),「含菁英政策之基因演算法於模式最佳化近似的應用」,工程科技與教育學刊 第7卷,第3期,437- 444。
[16]藍曉玲、周永權、韋修喜(2009年),「求解TSP問題的社會演化算法」,計算機工程與應用,第45期,46-48。
英文文獻:
[17]A. Puris, R. Bello and F. Herrera, “Analysis of the efficacy of a Two-Stage methodology for ant colony optimization: Case of study with TSP and QAP,” Expert Systems with Applications, Vol. 37, 5443-5453(2010).
[18]H. Chen, S. Li and Z. Tang, “Hybrid Gravitational Search Algorithm with Random-key Encoding Scheme Combined with Simulated Annealing,” International Journal of Computer Science and Network Security Vol. 11, 208-217 (2011).
[19]N. Mohd Razali, and J. Geraghty, “Genetic algorithm performance with different selection strategies in solving TSP,” Proceedings of the World Congress On Engineering, Vol. 2, (2011).
[20] A. Philip, A. Adio Taofiki and O. Kehinde, “A Genetic Algorithm for Solving Travelling Salesman Problem,” International Journal of Advanced Computer Science and Applications Vol. 2, 26-29 (2011).
[21]A. Arab Asadi, A.Naserasadi, and Z. Arab Asadi, “A New HybridAlgorithm for Traveler Salesman Problem based on Genetic Algorithms and Artificial Neural Networks,” International Journal of Computer Applications Vol. 24, 6-9 (2011).
[22]M. Serpell, and J. Smith, “Self-Adaptation of Mutation Operator and Probability for Permutation Representations in Genetic Algorithms,” Evolutionary Computation Vol. 18, 491-514 (2010).
[23]M. Sevaux, and M. J. Geiger, “Inventory Routing and On-line Inventory Routing File Format,” Helmut-Schmidt-University at Logistics Management Department (2011).