整合遺傳演算法和粒子群最佳化演算法於分群分析之研究

Integration of Genetic Algorithm and Particle Swarm Optimization for Clustering Analysis

林如梅(Lu-Mei Lin)

指導教授 ： 郭人介

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2008年)

https://doi.org/10.6841/NTUT.2008.00161

摘要

本研究主要提出一種新的群集分析方法－Hybrid particle swarm optimization(Hybrid PSO)演算法，其主要整合粒子群演算法、遺傳演算法和K-means，並透過IRIS、Glass、Vowel 以及Wine等基準資料集與genetic algorithm (GA)、genetic K-means algorithm (GKA)、PSO clustering、particle swarm K-means optimization (PSKO)、genetic algorithm- particle swarm optimization (GA-PSO) 和genetic algorithm- particle swarm K-means optimization (GA-PSKO)演算法比較群集效益。Hybrid PSO為本研究評估出最佳的群集分析方法。
在個案研究中，本研究以研華科技新店單板廠為例。由於少量多樣的產品需求型態，使得SMT生產系統在換線時，備料作業時常未完成，導致昂貴的機台發生閒置的情形。因此本研究應用群集分析方法，將所有機種的BOM表根據其特徵進行兩階段分群，在第一階段中先以自適應共振理論2神經網路（ART2）自動找出群數，接著第二階段中再以GA、GKA、PSO clustering、PSKO、GA-PSO、GA-PSKO和Hybrid PSO各演算法找出最佳的分群結果，結果顯示ART2+Hybrid PSO為最佳兩階段分群法。得知分群結果後，生管工程師可將同一群集的機種排在一起生產，便能簡化備料作業，達到縮短SMT換線時間之目的。因此本研究以FCFS和SPT兩種生產排程之方法進行換線效益之評估，結果顯示確實能夠縮短綁料時間、生產時間以及有效的降低機台閒置時間，達到本研究縮短換線作業時間之目的。

關鍵字

群集分析 ； 自適應共振理論2神經網路 ； 粒子群最佳化 ； 遺傳演算法

並列摘要

This study intends to propose a novel clustering analysis technique, Hybrid particle swarm optimization algorithm (Hybrid PSO), which integrates the particle swarm optimization algorithm, genetic algorithm and K-means method together. In order to evaluate its computational performance, some clustering analysis methods including genetic algorithm (GA), genetic K-means algorithm (GKA), PSO clustering, particle swarm K-means optimization (PSKO), genetic algorithm- particle swarm optimization (GA-PSO) and genetic algorithm- particle swarm K-means optimization (GA-PSKO) method are employed for comparison via IRIS, Glass, Vowel and Wine benchmark data sets. The simulation results indicate that Hybrid PSO outperforms these six methods in accuracy.
For further assessing Hybrid PSO’s capability, a world-class industrial computer manufacturer, Advantech company, which belongs to the high mix low volume production system, provides the related evaluation information. Its production characteristic is that the material preparation process often has not completed during setup in SMT system. This results in expensive machine idleness. Thus, we apply a two-stage method, which first uses the adaptive resonance theory 2 (ART2) network to determine the number of clusters and then employs GA, GKA, PSO clustering, PSKO, GA-PSO, GA-PSKO and Hybrid PSO algorithms to find the final solution. The results show that the best two-stage method is ART2+ Hybrid PSO. Through order clustering, the production planners can manufacture products together in the same cluster in order to save the material preparation time and also achieve reducing SMT setup time. We use two scheduling rules, first-come first-served (FCFS) and shortest processing time (SPT), will be applied for production scheduling in order to evaluate the proposed ART2+ Hybrid PSO algorithm’s performance. Thus, no matter what kind of scheduling rules is employed, using clustering analysis to arrange the similar orders together really can save the production time and idle time as well.

並列關鍵字

Clustering analysis ； ART2 ； PSO ； GA

參考文獻

[1] 林芳君，「應用粒子群最佳化於群集分析以縮短SMT換線時間－以研華科技為例」，國立台北科技大學工業工程與管理研究所，碩士論文，2007。

[3] 黃庭瑋，「應用群集分析方法縮短SMT換線時間－以研華科技為例」，國立台北科技大學工業工程與管理研究所，碩士論文，2006。

[7] 葉俊吾，「運用類神經網路建構SMT錫膏印刷製程品質管制系統」，國立成功大學製造工程研究所碩博士班，碩士論文，2002。

[8] Al-Sultan, K., “A Tabu search approach to the clustering problem,” Pattern Recognition, Vol. 28, No. 9, pp.1443-1451, 1995.

[9] Alsultan, K. and Selim, S., “A simulated annealing algorithm for the clustering problems,” Pattern Recognition, Vol. 24, No. 10, pp.1003-1008, 1991.