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

NCUIR > Engineering College > Graduate Institute of opto-Mechatronics > Electronic Thesis & Dissertation > Item 987654321/92245

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/92245

Title:	無性生殖基因演算法於自動出入料裝置路徑規劃應用之研究
Authors:	何宗揚;Ho, Tsung-Yang
Contributors:	光機電工程研究所
Keywords:	路徑規劃;無性生殖;基因演算法;突變;routing problem;asexual;genetic algorithm;mutation
Date:	2023-01-16
Issue Date:	2024-09-19 15:27:14 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究探討具有彈匣機構、可儲存多個零件的自動出入料裝置機械手臂路徑規劃。此類裝置能自材料補充點抓取多個材料，儲存在彈匣機構內，再依規畫路徑放置到多個需求點，節省機械手臂往返儲料點與需求點的時間與成本，提高出入料與加工效率。因為此類問題的計算時間複雜度隨需求點數量指數級增加，故本研究提出一種修改無性生殖基因演算法（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.
Appears in Collections:	[Graduate Institute of opto-Mechatronics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	17	View/Open

社群 sharing

Loading...