免疫演算法於IC 載版鑽孔路徑問題之研究

Application of Immune Algorithm on IC Substrate Drilling Path Optimization

劉昱德(Yu-De Liu) ； 黃士滔(Shih-Tao Huang)

《品質學報》 19卷4期 (2012/08) Pp. 339-348

https://doi.org/10.6220/joq.2012.19(4).03

摘要

鑽孔路徑規劃對於減少鑽孔加工時間、提升生產效率有著顯著影響，鑽孔路徑規劃問題為組合優化問題，在探討如何事先規劃出刀具的最短運行路徑。此一問題以傳統的數學模型難以求解，常被侷限在局部最佳解中，本研究以啟發式演算法中的免疫演算法求解鑽孔路徑以求跳脫局部最佳解。本研究以IC（Integrated Circuit）載板鑽孔路徑為例，在鑽孔位置已知，孔群尺寸、深度相同，且不更換刀具的狀態下一次加工，從而事先規劃出刀具的最短運行路徑。在求解過程中使用MATLAB 7.0的軟體編寫模擬程式，建立此問題的免疫演算法數學模式，求解之後再與基因演算法、傳統批次加工鑽孔做比較。研究結果顯示免疫演算法優於其他兩種方法，且有效取得較短鑽孔路徑，因而減少加工時間。

關鍵字

免疫演算法 ； 鑽孔路徑 ； 基因演算法

並列摘要

In IC substrate industry, the drilling operation requires the longest processing time, before drilling operation. Drilling path planning can reduce drilling time and increase production efficiency. Drilling path planning is a kind of combinatorial optimization problem. It is difficult to solve the problem by traditional model. Traditional model leading to the local optima, immune algorithm can take large steps through the local optima, reaching the global optimum.The purpose of this study was used immune algorithm for IC substrate drilling path optimization, position of the hole, hole group size, and the depth of the hole have been known, one take for IC substrate drilling without tool change, finding the shortest distance of drilling path. This simulation results showed that model can find a short path of drilling path optimization than the tradition method and GA (Genetic Algorithms) algorithm.

並列關鍵字

immune algorithm ； drilling path optimization ； GA (Genetic Algorithms) algorithm

參考文獻

Dasgupta, D., 1997, Artificial neural networks and artificial immune systems: similarities and differences, Proceedings of 1997 Institute of Electrical and Electronics Engineers (IEEE) International Conference on Systems, Man, and Cybernetics, 1, 873-878.

Hunt, J. E. and Cooke, D. E., 1996, Learning using an artificial immune system, Journal of Network and Computer Applications, 19(2), 189-212.

Yang, J.-H., Sun, L., Lee, H. P., Qian, Y., and Liang, Y.-C., 2008, Clonal selection based memetic algorithm for job shop scheduling problems, Journal of Bionic Engineering, 5(2), 111-119.

王恒，2002，二維多孔數控鑽床加工路徑的生成及優化，機械科學與技術，21(3)，463-464。

肖人彬、陶振武，2005，孔群加工路徑規劃問題的進化求解，計算機集成製造系統，11(5)，682-689。