使用基因演算法求解旅行銷售員問題於自走車路徑規劃之應用實現

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：18.226.166.214

姓名

林勇(Yung Lin) 查詢紙本館藏

畢業系所

電機工程學系在職專班

論文名稱

使用基因演算法求解旅行銷售員問題於自走車路徑規劃之應用實現
(Solving traveling salesman problem for route planning realization of an autonomous line-tracking car by means of genetic algorithm)

相關論文

★ 使用梳狀濾波器於相位編碼之穩態視覺誘發電位腦波人機介面	★ 應用電激發光元件於穩態視覺誘發電位之腦波人機介面判斷
★ 智慧型手機之即時生理顯示裝置研製	★ 多頻相位編碼之閃光視覺誘發電位驅動大腦人機介面
★ 以經驗模態分解法分析穩態視覺誘發電位之大腦人機界面	★ 利用經驗模態分解法萃取聽覺誘發腦磁波訊號
★ 明暗閃爍視覺誘發電位於遙控器之應用	★ 使用整體經驗模態分解法進行穩態視覺誘發電位腦波遙控車即時控制
★ 使用模糊理論於穩態視覺誘發之腦波人機介面判斷	★ 利用正向模型設計空間濾波器應用於視覺誘發電位之大腦人機介面之雜訊消除
★ 智慧型心電圖遠端監控系統	★ 使用隱馬可夫模型於穩態視覺誘發之腦波人機介面判斷與其腦波控制遙控車應用
★ 使用類神經網路於肢體肌電訊號進行人體關節角度預測	★ 使用等階集合法與影像不均勻度修正於手指靜脈血管影像切割
★ 應用小波編碼於多通道生理訊號傳輸	★ 結合高斯混合模型與最大期望值方法於相位編碼視覺腦波人機介面之目標偵測

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本論文研究如何透過基因演算法來有效率的搜尋循線自走車的路徑規劃。藉由將循線自走車的路徑規劃組成旅行銷售員的求解問題，並以基因演算法取得旅行銷售員的最佳解(Optimal solution)。本方法用於多目標點的旅行家問題求解，所完成的路徑，要求每一目標點只能通過一次，且必須回到原點。目前研究成果已經可以準確的完成目標點為10以上的路徑規劃問題。
本系統使用個人電腦求解循線自走車的路徑最佳解，而計算結果則經由無線模組傳輸到循線自走車。本論文所提基因演算法包含隨機初始化、交配、突變、菁英政策、基因毀滅等主要程序，當完成最佳路徑規劃，由電腦端的無線模組傳送引導循線自走車行進。每行經一個目標點時，即由車體端無線射頻辨識(RFID)模組讀取目標點的射頻辨識標籤，判斷目標點資料後，車體進行轉向，續朝下一目標點循線前進。當目標數為10時，設定染色體數為200，最大演化代數為5000，突變率及交配率分別為0.3及0.85，求得全域最佳解機率為100%。
本論文成功以基因演算法求解旅行銷售員問題之最短路徑，並以循線自走車驗證路徑規劃結果，本結果未來可應用於無人搬運車進行生產自動化配送作業。

摘要(英)

This thesis aims to search the optimized route planning for an autonomous line-tracking car using Genetic Algorithm (GA). By formulating the route planning question as a Travelling Salesman Problem (TSP), the GA has proved its effectiveness with high accuracy in achieving the multi-target route planning of the autonomous line-tracking car, in which the route planning requested each target should be passed through only one time and the line-tracking car should return to the initial target. Our study results have successfully implemented the route planning of the line-tracking car for 10 or more targets. The optimized route planning of the autonomous line-tracking car was computed on a PC platform. The optimized solutions obtained from GA were transmitted through a wireless transmission module to the autonomous line-tracking car. The utilized GA algorithm was designed to contain several steps, including the random initialization, crossover, mutation, elite policy, gene destruction, etc. Once the optimized route has been obtained, the optimized TSP solution is transferred to guide the autonomous line-tracking car. When the autonomous link-tracking car reached each designated target, the ID tag attached on the target was sensed by a RFID module, equipped on the autonomous line-tracking car and direct the line-tracking car toward next target. It has been shown that the present system can achieve 100% accuracy for 10 targets, with chromosome number of 200, maximum evolution of 5000, mutation and the crossover rates of 0.3 and 0.85, respectively.
In this thesis, the genetic algorithm successfully solved the traveling salesman problem and used it for planning the shortest path length of an autonomous line-tracking car. The study results may be helpful to the logistic transportation of automated guided vehicle in future applications.

關鍵字(中)

★ 基因演算法
★ 旅行銷售員問題旅行銷售員問題
★ 循線自走車

關鍵字(英)

★ Genetic Algorithm (GA)
★ Traveling salesman Problem (TSP)
★ autonomous line-tracking car

論文目次

摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 IX
第一章緒論 1
1.1 前言 1
1.2 研究動機與目的 1
1.3 研究背景 2
1.4 論文架構 3
第二章文獻回顧 4
2.1 旅行銷售員問題 4
2.2 泛用啟發式演算法 5
2.3 基因演算法簡介 6
2.4 基因演算法求解旅行銷售員問題 7
2.5 輪型自走車控制 8
第三章研究方法與流程 11
3.1 硬體架構與軟體程式流程 11
3.1.1 GUI介面求解旅行銷售員問題流程 11
3.1.2 路徑應用探討 13
3.1.3 自走車控制程式流程 17
3.2 軟體介紹 21
3.2.1 MATLAB軟體 21
3.2.2 LabVIEW軟體 23
3.2.3 MPLAB IDE軟體 24
3.3 硬體介紹 25
3.3.1 dsPIC控制器 25
3.3.2 伺服馬達 28
3.3.3 循線模組 33
3.3.4 無線傳輸模組 35
3.3.5 RFID無線射頻辨識模組 36
3.4 基因演算法求解旅行銷售員問題流程 39
3.4.1 染色體基因編碼與解碼 42
3.4.2 初始化染色體 44
3.4.3 性能指標及適應函數計算 45
3.4.4 染色體排序 46
3.4.5 終止條件 50
3.4.6 菁英政策 50
3.4.7 交配策略 52
3.4.8 突變策略 54
3.4.9 基因毀滅 55
3.5 硬體與軟體介面 56
第四章實驗結果 58
4.1 旅行銷售員問題路徑規劃結果 58
4.1.1 求解旅行銷售員問題路徑規劃結果 58
4.1.2 路徑權重影響路徑規劃結果 66
4.1.3 油量消耗影響路徑規劃結果 67
4.1.4 貨物運送影響路徑規劃結果 71
4.1.5 不同目標點數影響路徑規劃之效能 75
4.1.6 不同目標點數與染色體數關係探討 82
4.2 循線自走車最短路徑驗證 83
第五章結論與未來展望 90
5.1 結論 90
5.2 未來展望 91
參考文獻 93
附錄A: 自走車實現最佳路徑規劃 94

參考文獻

[1]Y. Takenaka and N. Funabiki, “An improved genetic algorithm using the convex hull for traveling salesman problem ”, IEEE International Conference on Systems, Man, and Cybernetics, Vol. 3, pp. 2279-2284, 1998.
[2]P. Larranaga, et al, “Genetic Algorithm for the Travelling Salesman Problem:A Review of Representations and Operators ”, Artificial Intelligence Review, Vol. 13, No. 2, pp. 129-170, 1999.
[3]S. S. Ray, S. Bandyopadhyay, and S. K. Pal, “New operators of genetic algorithms for traveling salesman problem ”, Proceedings of the 17th International Conference on Pattern Recognition, pp. 497-500, 2004.
[4]台灣大福(DAIFUKU)高科技設備股份有限公司，取自http://tw.taiwandaifuku.com/
[5]E. Horowitz, Fundamentals of Computer Algorithms, Misc, 1978.
[6]M. M. Flood, “The Travelling Salesman Problem ”, Operations Research, Vol. 4, No. 1, pp. 61-75, 1956.
[7]S. Tsubakitani and J. R. Evans, “Optimizing tabu list size for the traveling salesman problem ”, Computers & Operations Research, Vol. 25, No 2, pp. 91-97, 1998.
[8]S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, “Optimization by Simulated Annealing ”, Science, Vol. 220, No. 4598, pp. 671-680, 1983.
[9]M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem ”, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.
[10]J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press Cambridge, MA, USA 1992.
[11]J. Kennedy and R. Eberhart, “Particle Swarm Optimization ”, IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[12]J. H. Holland, Adaptation in Natural and Articial Systems, University of Michigan Press, Ann Arbor, MI, USA, 1975.
[13]林昇甫、徐永吉，遺傳演算法及其應用，初版，五南圖書，台北市，民國九十八年。
[14]王正元，基于狀態轉移的組合優化方法，西安交通大學出版社,，西元2010年8月。
[15]V. Dwivedi, T. Chauhan, S. Saxena and P. Agrawal, “Travelling Salesman Problem using Genetic Algorithm ” International Journal of Computer Applications, pp. 25-30, 2012.
[16]K. Deep and H. Mebrahtu, “Combined Mutation Operators of Genetic Algorithm for the Travelling Salesman problem ”, International Journal of Combinatorial Optimization Problems and Informatics, Vol. 2, No. 3, 2011.
[17] C. Chudasama, S. M. Shah and M. Panchal, “Comparison of Parents Selection Methods of Genetic Algorithm for TSP ”, International Journal of Computer Applications, 2011.
[18]余家華，「由較佳邊集合引導之基因區域搜尋法及其應用於解旅行推銷員問題」，國立中興大學，碩士論文，民國96年。
[19]李維平、江正文、賀嘉生和李佩玲，「以混合基因與粒子群演算法求解旅行銷售員問題」，先進工程學刊，第五卷第四期，377~383頁，2010年10月。
[20]邱以強，「結合基因演算法與螞蟻演算法求解旅行推銷員問題」，國立東華大學，碩士論文，民國101年。
[21]許哲源，「自走車之驅動控制與避障規劃」，國立成功大學，碩士論文，民國92年。
[22]鄭永順，「輪型行動機器人之自動航行與路徑規劃」，國立中央大學，碩士論文，民國94年。
[23] 陳俊嘉，「即時影像追蹤之自走車設計」，國立中央大學，碩士論文，民國96年。
[24] 吳至仁，「利用環場視覺作自動車應用之定位與影像分析新技術之研究」，國立交通大學，博士論文，民國98年。
[25]李孟軒，「輪型機器人之路徑追蹤與避障」，國立中央大學，碩士論文，民國100年。
[26]陳承杰，「藉由粒子群演算法求解旅行銷售員問題於最佳化後勤補給規劃」，國立中央大學，碩士論文，民國101年。
[27]NI網站，LabVIEW 系統設計軟體，取自http://www.ni.com/labview/zht/
[28]曾百由，數位訊號控制器原理與應用，宏友圖書，民國九十八年。
[29]普特企業有限公司網站，Parallax標準伺服機，取自http://www.playrobot.com/cart/shop.php?id=296&factory=&header=&sub=&Fno=&date_buy
[30]東莞世安集團網站，伺服馬達的工作原理與內部結構圖，取自 http://www.gdshian.com/html/yingyonganli/201205/19-291.html
[31]Toymaker Television. Parallax RC Servo part 1:PWM/Hookup Basics. 取自http://tymkrs.tumblr.com/post/16823262200/parallax-rc-servo-part-i-pwm-hookup-basics
[32]普特企業有限公司網站，QTI循線模組，取自http://www.playrobot.com/cart/shop.php?id=12&factory=&header=&sub=&ctype2=&typeid=&pagename=&Fno=&date_buy
[33]劉穎昌：預測未來台灣RFID技術暨產業發展趨勢。2007年12月，取自http://www.gs1tw.org/twct/gs1w/pubfile/2007-12-p26-33.pdf
[34]H. Braun, “On Solving travelling salesman problems by genetic algorithms ”, Lecture Notes in computer Science, Vol. 496, pp 129-133, 1991.
[35]王文俊，認識Fuzzy，第三版，全華圖書，民國九十七年。
[36] 陳智綱，「含菁英政策與基因毀滅之基因演算法於主動式振動控制器之設計」，國立中山大學，碩士論文，民國89年。
[37]N. Kumar, Karambir and R. Kumar, “A Comparative Analysis of PMX, CX and OX Crossover operators for solving Travelling Salesman Problem ”, International Journal of Latest Research in Science and Technology, Vol 1, No. 2, pp. 98-101, July –August 2012.
[38]華儲物流設備有限公司，產品介紹：無人搬運車AM-AGV( Automation Guided Vehicle)，取自http://www.axis-group.com.tw/ASHE/Index_AXIS.asp

指導教授

李柏磊

審核日期

2013-7-30

推文