以螞蟻識別系統進行零件分群

Ant colony recognition for part clustering problems

李岳倫(Yue-Lun Li)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2005年)

摘要

單元製造為群組技術最主要的應用，需要一個有效的零件分群法則，來進行初步製造單元設計。集群分析法為常用方法之一，搭配特殊設計的相似係數，能集群相似的零件成為零件家族。集群分析法可分為階層分群與非階層分群兩種，但階層法容易有鏈結效應，而非階層分群事先需給定零件家族數目。故在本研究中提出一個以人工螞蟻識別系統(AntClust)為基之零件分群演算法，來解決上述問題。本演算法利用人工螞蟻的非監督式學習方法，逐漸建立起完整零件識別能力，自然地形成成員相似度甚高的零件家族，並利用合併法則達到工廠規劃者理想群數。由於本演算法具有螞蟻分群特性：群體性與隨機性，使零件分群過程可將前期錯分的零件重新分配，降低例外零件對分群結果之影響。本演算法已經被開發成系統，並利用分群績效指標，對十七個文獻案例進行測試，都得到相當好的單元形成結果。同時以複雜度為構面進行實驗，顯現出本演算法在零件分群方面可處理複雜問題。最後與早期的螞蟻分群模式APCS系統進行比較，證實本演算法在求解速度上較優。

關鍵字

群組技術，零件家族形成，螞蟻演算法，群體智慧。

並列摘要

Cellular manufacturing, which requires an effective parts clustering method to start up the manufacturing cell design, is the premier application of group technology. Cluster analysis, clustering similar parts to be part families by working with similarity coefficients specially designed, is one of the methods in common use. Cluster analysis is divided into hierarchical clustering method and nonhierarchical clustering method, but chaining effect often appeared in hierarchical clustering method and setting requirement of part family numbers for nonhierarchical clustering method have limited the applications of cluster analysis. Therefore, based on the recognition system of artificial ants, a new parts clustering algorithm is proposed in our study to solve the clustering problem. The proposed algorithm is using the ability of unsupervised learning of artificial ants to gradually build up the comprehensive recognition and naturally form the part clusters with high similarities. Furthermore, this algorithm also uses merging rules to decrease the part clusters and fit the designated cluster numbers. Due to the features like collective behaviour and randomization from ant clustering model, this algorithm allows re-clustering of the mis-clustered parts and accordingly eliminates the effect of exceptional parts. This algorithm has been developed to be a machine cell formation system; moreover, 17 reported cases have been tested and evaluated by clustering performance measures. The results coming from those 17 cases, which contain various complications and sizes, all revealed effective cell formulation that indicates the performance of this algorithm at parts clustering.

並列關鍵字

ant algorithms ； Group technology ； part family formation ； swarm intelligence.

參考文獻

1. Askin, G. R., Cresswell, H. S., Goldberg, B. J. and Vakharia, J. A., 1991, A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing. International Journal of Production Research, 29, 1081-1100.

2. Bonabeau, E., Dorigo, M., and Theraulaz, G., 1999, Swarm intelligence：from natural to artificial systems. New York：Oxford University Press.

3. Burbidge, L. J., 1975, The introduction of group technology. New York：John and Sons.

4. Carrie, A. S., 1973, Numerical taxonomy applied to group technology and plant layout. International Journal of Production Research, 11, 399-416.

5. Chan, H. M. and Milner, D. A., 1982, Direct clustering algorithm for group formation in cellular manufacture. Journal of Manufacturing Systems, 1, 65-75.