整合粒子群最佳化演算法與遺傳演算法於動態分群之研究

Integration of Particle Swarm Optimization and Genetic Algorithm for Dynamic Clustering

徐儀蓁(Yi-Jhen Syu)

指導教授 ： 田方治 ； 郭人介

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

摘要

隨著科技日新月異，新的群集分析方法不斷地被提出，但大多分群方法需先設定分群之群數，因此本研究主要提出一自動分群之方法－Dynamic Clustering using Particle Swarm Optimization and Genetic Algorithm (DCPG)演算法，不需事先決定欲分群的數目，可藉由資料的特性自行群聚成適合的群集。
本研究先分別採用四組基準資料集Iris、Wine、Glass以及Vowel來進行實驗，
並與Dynamic Clustering using Particle Swarm Optimization (DCPSO) 和Dynamic Clustering using Genetic Algorithm (DCGA)進行比較，以驗證該方法之準確性及有效性。驗證得知，本研究所提DCPG此一動態分群的方法在分群結果上表現較為穩定且優異。最後再將此方法應用於研華科技新店單板廠所有機種與用料之Bill of Material (BOM)表中，利用DCPG自動分群法找出群數後，接著第二階段以林如梅(2008)所提出之Hybrid Particle Swarm Optimization (Hybrid PSO)找出最佳的分群結果。經過兩階段的群集分析後，找出相同群集的機種及其共用料，再透過產品族的概念將相同群集的機種安排一起生產，以其縮短SMT換線作業時間，以因應工業電腦產業多量少樣的生產模式。

關鍵字

群集分析 ； 自動分群 ； 粒子群最佳化演算法 ； 遺傳演算法

並列摘要

With the advancement of technology, the methods of clustering analysis are continually proposed. Even though, most of the clustering methods still need to set the number of cluters. This study intends to propose a novel dynamic clustering technique - Dynamic Clustering using Particle Swarm Optimization and Genetic Algorithm (DCPG), which does not need to set the number of cluters in advance. By the features of data, the method could auomatically cluster together into a suitable cluster number.
This study employees four benchmark datasets, Iris, Wine, Glass and Vowel, to evaluate the accuracy and validity by comparing DCPG and other two methods, Dynamic Clustering using Particle Swarm Optimization (DCPSO) and Dynamic Clustering using Genetic Algorithm (DCGA). The experimental results indicate that DCPG outperforms other three methods in validity and stability. Finally, we apply a two-stage method, which includes DCPG to determine the number of cluters, and Hybrid Particle Swarm Optimization (Hybrid PSO) to find the final solution. This method is applied to cluster the Bill of Material (BOM) for Advantech Company. The clustering results can be used to categorize products into clusters which share the same materials. Moreover, through the concept of product family, machines in the same cluster are arranged to be manufactured together to reduce SMT setup time in response to the high-mix and low-volumn production pattern of industrial personal computers.

並列關鍵字

Clustering Analysis ； Dynamic Clusterung ； Particle Swarm Optimization Algorithm ； Genetic Algorithm.

參考文獻

[3] 林如梅，整合遺傳演算法和粒子群最佳化演算法於分群分析之研究，台北科技大學工業工程與管理研究所，碩士論文，台北，2008。

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

[5] 黃振倫，印刷電路板小元件裝配排程問題之研究─以Fuji CP機器為例，元智大學，工業工程與管理學系，碩士論文，桃園，2002。

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

[8] 韓永祥，整合遺傳演算法與粒子群最佳化演算法於二階線性規劃問題之應用-以供應鍊之配銷模型為例，台北科技大學工業工程與管理研究所，碩士論文，台北，2008。