無性生殖基因演算法於自動出入料裝置路徑規劃應用之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：104

、訪客IP：18.119.102.149

姓名

何宗揚(Tsung-Yang Ho) 查詢紙本館藏

畢業系所

光機電工程研究所

論文名稱

無性生殖基因演算法於自動出入料裝置路徑規劃應用之研究

相關論文

★ 氣動馬達之單軸平台定位控制	★ 運用MRAC及模糊法則於氣動馬達FPGA控制器之研發
★ 球型變焦鏡頭之研究	★ 影像式多目標模擬器製作與平行光顯像系統設計
★ 連續式微電鍍之影像處理方法	★ 硬體迴路測試系統建構與驗證
★ 即時影像引導連續式微電鍍之立體微結構製作研究	★ 公共環境下人員追蹤影像方法研究
★ 燃料電池氫氣進料控制之研究	★ 形狀記憶合金對焦系統之基因演算法及模糊控制法則
★ 公共空間光源亮度模糊控制法則之研究	★ 立方衛星無線通訊系統開發
★ 多重訊號同步擷取裝置整合研究	★ 應用希爾伯特黃變換(HHT)之邊際譜分析於旋轉機械的元件鬆脫故障診斷
★ 總體經驗模態分解法(EEMD)結合自回歸(AR)模型在旋轉機械之元件鬆脫故障診斷之應用	★ 超音波聚焦噴墨之能量驅動與分析研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2028-1-1以後開放)

摘要(中)

本研究探討具有彈匣機構、可儲存多個零件的自動出入料裝置機械手臂路徑規劃。此類裝置能自材料補充點抓取多個材料，儲存在彈匣機構內，再依規畫路徑放置到多個需求點，節省機械手臂往返儲料點與需求點的時間與成本，提高出入料與加工效率。
因為此類問題的計算時間複雜度隨需求點數量指數級增加，故本研究提出一種修改無性生殖基因演算法（Modified asexual genetic algorithm, MAGA）來求解最短的路徑總長。本演算法著重使用無性生殖的突變機制來逃脫局部最優解陷阱，來快速求得接近全局最優解的解。由於此類問題與車輛旅途問題（Vehicle routing problem, VRP）相似，本研究與該問題常見的求解方法：工業界常用Z形排序法（Zigzag）以及Google AI團隊所開發的OR-Tools求解器以預設選項（Path cheapest arc guided local search, PCAGLS）做比較。
相對於隨需求點數量指數增加計算時間，本文提出之演算法在短時間內（10秒），即計算出優秀的計算結果，取得路徑總長較短的的路徑規劃，證明本文提出演算法的構想之有效性。本研究使用 C# .NET 實現演算法，與上述列出的演算法比較，在20 ~ 80個隨機需求點各30組，彈匣容量5~9的條件下測試。

摘要(英)

The proposed algorithm aims to solve the routing problem for automatic feeding and outgoing device by modified asexual genetic algorithm (MAGA). The device has a robotic arm with capacitated magazine end effector. The magazine end effector can catch multiple components and place those components to demand points at once. Since the magazine is capacitated, the robotic arm needs to move its end effector back to a certain depot to pick up required number of components.
The proposed algorithm is different from classical genetic algorithm. MAGA use only mutation to generate new route from exists route to escape from local minimum with adaptive mutation rate. Also, selection mechanism is adjusted to increase the genetic diversity.
In this study, we generated 20, 30 ... 80 random demand points and a real PCB punching processing demand points to test the proposed algorithm. Since the route planning problem of the robotics arm is similar to Vehicle routing problem (VRP). We compared the proposed algorithm to the control group. Including industrial common use algorithm, Zigzag algorithm and OR-Tools VRP solver develop by Google AI teams.
In the experiment, we used C# .NET to implement the algorithm. Compare to control group, the proposed MAGA gives a better result and takes shorter time in the range of 20 ~ 80 demand points and magazine size of 5~9.

關鍵字(中)

★ 路徑規劃
★ 無性生殖
★ 基因演算法
★ 突變

關鍵字(英)

★ routing problem
★ asexual
★ genetic algorithm
★ mutation

論文目次

摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
符號說明 ix
第一章緒論 1
1-1 研究動機 1
1-2 研究目的 3
1-3 研究架構 5
第二章文獻回顧 6
2-1 基因演算法 6
2-2 Zigzag 排序法 8
2-3 Google OR-Tools 8
第三章演算法設計 9
3-1 初始化設計 10
3-2 基因突變方法設計 10
3-3 基因選擇方法設計 14
3-4 終止條件 21
第四章實驗結果與討論 22
4-1 演算法特性觀察 23
4-2 與Zigzag排序演算法比較 24
4-3 與 Google OR-Tools比較 27
4-3-1 隨機數據測試 27
4-3-2 真實目標點測試 38
4-4 演算法效率比較 40
第五章結論與未來展望 42
5-1 結論 42
5-2 未來展望 42
參考文獻 43

參考文獻

[1] BMBF, "Zukunftsprojekt Industrie 4.0," [Online]. Available: https://web.archive.org/web/20140407091109/http://www.bmbf.de/de/19955.php. [Accessed 1 1 2013].
[2] H. Çebi Bal and Ç. Erkan, "Industry 4.0 and Competitiveness," Procedia Computer Science, vol. 158, pp. 625-631, 2019.
[3] J. D. ULLMAN, "NP-Complete Scheduling Problems," JOURNAL OF COMPUTER AND SYSTEM SCIENCES 10, pp. 384-393, 1975.
[4] D. S. Hochba, "Approximation Algorithms for NP-Hard Problems," ACM SIGACT News, vol. 28, no. 2, pp. 40-52, June 1997.
[5] A. Slowik and H. Kwasnicka, "Evolutionary algorithms and their applications to engineering problems," Neural Computing and Applications, pp. 12363-12379, 2022.
[6] M. A. Mohammed, M. S. Ahmad and S. A. Mostafa, "Using Genetic Algorithm in implementing Capacitated Vehicle Routing Problem," in ICCIS, Kuala Lumpur, 2012.
[7] C. Voudouris and E. Tsang, "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, vol. 113, no. 2, pp. 469-499, March 1999.
[8] Z. Beheshti and S. M. H. Shamsuddin, "A Review of Population-based Meta-Heuristic," International Journal of Advances in Soft Computing and its Applications, vol. 5, no. 1, March 2013.
[9] A. Van Breedam, "An analysis of the effect of local improvement operators in genetic algorithms and simulated annealing for the vehicle routing problem," in University of Antwerp, Belgium, 1996.
[10] B. M.Baker and M.A.Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research, vol. 30, no. 5, pp. 787-800, April 2003.
[11] 陳聖學, 「分群演算法應用於自動出入料裝置路徑規劃研究」, 碩士論文, 國立中央大學機械工程學系, 2021.
[12] 張家樵, 「三軸機械手臂雷射加工控制之研究」, 碩士論文, 國立中央大學光機電工程研究所, 2019.
[13] D. Goldberg and R. Lingle, "Alleles, loci and the traveling salesman problem," in In Proceedings of an International Conference on Genetic Algorithms , pp.10-19, Morgan Kauffman, 1985.
[14] J. H. Holland, "Adaptation in natural and artificial systems," in MA:MIT Press, Cambridge, 1975.
[15] L. M. Schmitt, "Theory of genetic algorithms," Theoretical Computer Science, vol. 259, no. 1-2, pp. 1-61, 28 May 2001.
[16] P. C. Chang, W. H. Huang and C. J. Ting, "Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems," Expert Systems with Applications, vol. 37, no. 3, pp. 1863-1878, March 2010.
[17] I. D. Falcoa, A. D. Cioppa and E. Tarantinoa, "Mutation-based genetic algorithm: performance evaluation," Applied Soft Computing, vol. 1, no. 4, pp. 285-299, May 2002.
[18] J. Cantó, S. Curiel 且 E. Martínez-Gómez, “A simple algorithm for optimization and model fitting: AGA (asexual genetic algorithm),” Astronomy & Astrophysics, 編號 501, p. 1259–1268, 2009.
[19] 黃萱軒, 「PCB 孔洞加工路徑之研究」, 碩士論文, 國立中央大學機械工程學系, 2022.
[20] T. G. Crainic and J. Roy, "OR tools for tactical freight transportation planning," European Journal of Operational Research, vol. 33, no. 3, pp. 290-297, 1988.

指導教授

黃衍任(Yean-Ren Hwang)

審核日期

2023-1-16

推文