基于蟻群聚類算法的板式定制家具訂單聚類分析?

陶 濤 王 潔 劉忠會 陳星艷 馮萬福

（1.中南林業(yè)科技大學(xué)，長沙 410004；2. 歐派家居集團(tuán)股份有限公司，廣州 510000； 3. 江蘇凱蒂家居用品有限公司，邳州 221300)

在現(xiàn)代家具企業(yè)中，傳統(tǒng)的大批量生產(chǎn)模式已不適用，取而代之的是家具企業(yè)的大規(guī)模定制生產(chǎn)模式。大規(guī)模定制的核心就是以大規(guī)模的生產(chǎn)模式滿足客戶個性化需求[1-3]。目前，定制家具企業(yè)的生產(chǎn)是以訂單為核心。定制化背景下家具訂單的差異性較大，導(dǎo)致設(shè)備調(diào)整時間和企業(yè)生產(chǎn)成本增加，交貨期延長[4-5]。因此，定制家具企業(yè)在排產(chǎn)前考慮訂單的相似性，做好訂單的管理工作，合理安排生產(chǎn)是企業(yè)降低生產(chǎn)成本的前提[6-8]。

蟻群算法是一種尋找最優(yōu)路徑的人工智能算法，有較強(qiáng)的魯棒性和自適應(yīng)性，目前，蟻群算法被大量運(yùn)用于數(shù)據(jù)挖掘、機(jī)器人、電力、通信、交通等多個領(lǐng)域[9-16]。本文針對定制家具訂單多品種小批量的情況，將蟻群算法應(yīng)用于定制家具訂單的聚類問題研究。通過模擬蟻群的覓食行為將算法應(yīng)用于定制家具訂單聚類問題分析中，以所有聚類類別中材料種類總和最小為聚類目標(biāo)對定制家具訂單進(jìn)行聚類分析。

1 模型構(gòu)建

1.1 問題描述

本文研究某定制家具企業(yè)在某一時間段內(nèi)到達(dá)的多個訂單，具有相同的交貨期。由于板式定制家具企業(yè)在開料環(huán)節(jié)需要對原料板進(jìn)行切割，不同的訂單所需原料板的種類及數(shù)量各不相同。若對單個訂單進(jìn)行單獨(dú)排產(chǎn)開料，會導(dǎo)致某些原料板的利用率較低，從而增加企業(yè)的生產(chǎn)成本。因此?，F(xiàn)代的定制家具企業(yè)將幾個相似訂單組合在一起進(jìn)行揉單生產(chǎn)。訂單的聚類問題描述為：在某一時間段內(nèi)有N個訂單{O1,O2,…ON}，每一個訂單有若干數(shù)量的板件，每個訂單的板件材料種類不定。假設(shè)第i個訂單Xi(i=1,2,3…N)中有t（t=1，2，3…n）種板件材料，每一種材料的總面積分別為{S1, S2…St}，則訂單i的總面積為Si=S1+S2+…St。對這N個訂單進(jìn)行聚類，使得聚類完成后所有類別中的材料種類總和最少。

1.2 訂單表示

由于定制家具訂單中某些信息是非結(jié)構(gòu)化信息，需將訂單中材料文本數(shù)據(jù)轉(zhuǎn)換成計(jì)算機(jī)能夠識別的語言以便進(jìn)行訂單的管理工作。本文選取定制家具訂單中訂單名稱，材料描述、訂單面積作為關(guān)鍵信息對訂單進(jìn)行預(yù)處理。定制家具訂單i可以表示為：

式中，tj表示材料j，Oij表示在訂單i中材料j的出現(xiàn)情況。Si為訂單i的板材總面積。由于板式家具開料工序是根據(jù)板件的材料種類進(jìn)行開料，影響訂單聚類的主要因素為材料種類。因此對于Oij值的表示為：若此材料在該訂單文本中出現(xiàn)，則該值為1，若訂單文本中該材料未出現(xiàn)，則該值為0。將定制家具訂單集合轉(zhuǎn)化為一個N×(n+1)的高維矩陣X，矩陣X表示: 總共有N個訂單，每一行代表一個訂單，該訂單集合總共有n種材料種類，每一列代表一個材料種類。

1.3 訂單相似度

為了對家具訂單進(jìn)行聚類，需要對各訂單的相似程度進(jìn)行描述。由于定制家具的生產(chǎn)特點(diǎn)，對于定制家具訂單間的相似度的計(jì)算只考慮材料的出現(xiàn)情況，訂單向量描述值為0 或1。Jaccard距離常用來處理僅包含非對稱的二元(0-1)屬性的對象，不考慮各屬性的實(shí)際值[17]。因此，本文通過Jaccard距離對訂單相似度進(jìn)行計(jì)算。公式如下：

式中，Jij為杰卡德系數(shù)，表示訂單向量Xi與訂單向量Xj的交集元素的個數(shù)與訂單向量Xi與訂單向量Xj并集的元素個數(shù)的比例。Dij為杰卡德距離。Dij的取值范圍為[0,1]，當(dāng)值為1 時表示兩個訂單所需材料種類完全不相同;當(dāng)值為0 時表示兩個訂單所需材料種類一致。

1.4 目標(biāo)函數(shù)

本文以聚類完成后所有類別中的材料種類總和最少為目標(biāo)函數(shù)。求解公式如下：

式中，Zj為第j類中訂單包含的材料種類數(shù)，j為類別編號，K為聚類類別數(shù)目。

2 蟻群算法

2.1 蟻群算法原理

蟻群算法(ACA, Ant Colony Algorithm)是模擬螞蟻覓食過程形成的搜尋算法。最早由Marco Dorigo提出[18]。算法的主要思想是螞蟻在尋找路徑的途中會釋放一種信息素，信息素濃度與路徑長度有關(guān)，路徑越長，信息素濃度越低。每一只螞蟻搜尋路徑都會留下信息素，當(dāng)下一個螞蟻搜尋路徑時選擇信息素濃度較高的路徑的概率較大。

基于蟻群算法覓食原理的聚類算法思路如下：將數(shù)據(jù)視為具有不同屬性的螞蟻，聚類中心則是螞蟻搜尋的“食物源”，因此，數(shù)據(jù)的聚類過程就是螞蟻尋找食物源的過程,通過模擬螞蟻覓食行為將數(shù)據(jù)進(jìn)行聚類分析的算法即為蟻群聚類算法（ACCA，Ant Colony Clustering Algorithm）[19]。

1）螞蟻信息素矩陣表示為：τij（t）是t時刻ωi到ωj路徑上殘留的信息素量，路徑（i，j）上的信息素定義為：

其中，r為聚類半徑，本文選取r=1。

2)計(jì)算類別ωj合并到類別ωi的概率：

其中，τij為信息素濃度，ηij為啟發(fā)式函數(shù), ηij=1/Dij。α表示信息素啟發(fā)因子的相對重要性; β表示啟發(fā)式信息的相對重要性。

2.2 基于螞蟻覓食的蟻群聚類算法

本文所運(yùn)用的基于螞蟻覓食的蟻群聚類算法是聚類數(shù)目未知的聚類算法。由于定制家具板材種類眾多，對定制家具訂單進(jìn)行聚類時，無法在初始時設(shè)置聚類數(shù)目。該算法的目標(biāo)是通過螞蟻遍歷所有的訂單數(shù)據(jù)點(diǎn)，建立一條使目標(biāo)函數(shù)值最小的路徑，提高聚類的準(zhǔn)確性。聚類過程描述如下：

假設(shè)第i個訂單Xi(i=1,2,3…n)中有t（t=1，2，3…）種板件材料：

1）初始化算法參數(shù)，包括：螞蟻個數(shù)，聚類半徑r,直接轉(zhuǎn)移閾值p0。

2）初始分配N個樣品各自為一類（ω1, ω2, ω3…ωN）。

3）根據(jù)公式（3）計(jì)算類ωi與類ωj之間的杰卡德距離Dij。

4）根據(jù)公式（5）計(jì)算路徑上的信息素量， 再根據(jù)公式（6）求解類i與類j之間的轉(zhuǎn)移概率。

5）判斷若Pij＞p0，則將類ωj歸為類ωi，記下參加合并的訂單序號，類別數(shù)減1。p0 為轉(zhuǎn)移閾值。

6）當(dāng)所有螞蟻完成一次聚類之后，更新聚類中心和路徑上的信息素。

7）判斷各聚類中心之間的信息素值是否都為0，若否，轉(zhuǎn)至步驟3）循環(huán)；若是，則表示聚類類別無法歸并，計(jì)算各類別中訂單的板材總面積。

8）判斷是否存在各類別的板材總面積小于工廠規(guī)定的一個批次的板件生產(chǎn)的最小面積數(shù)，若否，則表示聚類完成。若是，將總面積數(shù)較少的類別兩兩歸并。

由于各訂單板件的材料種類不同及各訂單的總面積數(shù)不同，對于同一個聚類，總面積數(shù)過小不利于后期的排產(chǎn)時原材料的優(yōu)化，總面積數(shù)過大后續(xù)排產(chǎn)還需進(jìn)行再分批，且若同一類別中材料種類過多，后期排產(chǎn)時會增加機(jī)器調(diào)整時間從而導(dǎo)致生產(chǎn)成本升高。因此為使聚類結(jié)果更符合實(shí)際生產(chǎn)，在算法中需設(shè)定一個類別的總面積數(shù)的范圍。本文將其設(shè)定為工廠規(guī)定的一個批次的板件生產(chǎn)的最小面積數(shù)。

3 算法應(yīng)用

本文以板式家具企業(yè)實(shí)際接受的訂單數(shù)據(jù)為數(shù)據(jù)基礎(chǔ)，隨機(jī)選取50 個同一天交貨期的定制家具訂單，分別用編號1～50 表示家具訂單。通過MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)。對訂單的聚類要求是使所有聚類類別的材料種類總和最小，且各類別的總面積大于工廠規(guī)定的一個批次生產(chǎn)的最小面積數(shù)。

3.1 訂單預(yù)處理

對50 個家具訂單進(jìn)行預(yù)處理，這50 個家具訂單總共包括30 種板材種類。生成50×31 的訂單集合矩陣，其中，訂單矩陣的最后一列為訂單的面積，用于聚類的訂單面積歸并，在訂單相似度計(jì)算時忽略該列。如表1所示。

表 1 定制家具訂單向量矩陣示例 Tab.1 Example of vector matrix for customized furniture orders

3.2 相似距離確定

將每個訂單作為一類，構(gòu)成大小為50×50 的距離矩陣,通過距離矩陣計(jì)算信息素矩陣,繼而計(jì)算類別之間的轉(zhuǎn)移概率,根據(jù)轉(zhuǎn)移概率對訂單進(jìn)行聚類，根據(jù)公式（6）求得類間轉(zhuǎn)移概率矩陣。將類別之間的轉(zhuǎn)移概率與轉(zhuǎn)移閾值進(jìn)行比較，進(jìn)行類別歸并循環(huán)迭代，直至滿足聚類要求為止。

3.3 聚類算法結(jié)果

經(jīng)過多次試驗(yàn)比較，最終確定本文算法的參數(shù)值如表2 所示。

表2 參數(shù)設(shè)置 Tab.2 Parameter setting

針對以上的50 個訂單，運(yùn)用傳統(tǒng)的聚類數(shù)目已知的蟻群算法以及經(jīng)典的聚類算法K-means算法進(jìn)行聚類求解，與本文中的聚類數(shù)目未知的蟻群算法的結(jié)果進(jìn)行對比，其結(jié)果如表3 所示。

表3 不同算法的聚類結(jié)果 Tab.3 Clustering results of different algorithms

3.4 算例結(jié)果分析

由于材料種類數(shù)決定了定制家具生產(chǎn)時機(jī)器調(diào)整總時間，對訂單聚類要求是使所有類別中訂單材料種類總和最少，使得參與聚類的所有訂單的生產(chǎn)時機(jī)器調(diào)整總時間最少，從而提高企業(yè)的生產(chǎn)效率。假設(shè)板材材料更換導(dǎo)致機(jī)器的調(diào)整時間固定，用tm表示。

對比三種聚類算法的聚類結(jié)果可知，本文提出的未知聚類數(shù)目的蟻群聚類算法聚類完成后，所有聚類類別材料種類總和為30，聚類類目為7，算法計(jì)算時間為32.83 s。則對這50 個訂單生產(chǎn)時機(jī)器調(diào)整的總時間為30×tm。而已知聚類數(shù)目的蟻群聚類算法在聚類之前需要找到一個較合適的聚類類目值，才能得到較好的聚類效果，增加了算法計(jì)算時間。根據(jù)本文算法的結(jié)果得到最優(yōu)的聚類類別數(shù)為7，因此，預(yù)先設(shè)定聚類數(shù)目為7，通過聚類數(shù)目已知的蟻群聚類算法迭代得到所有聚類類別材料種類總和為42，大于原有訂單的材料種類總數(shù)30，說明存在著具有不同板材種類的訂單聚為一類的情況，使得所有類別中材料種類增多，機(jī)器調(diào)整的總時間為42×tm。經(jīng)典的K-means算法計(jì)算快速，通過K-means算法聚類完成后所有類別中的材料種類總數(shù)為84，遠(yuǎn)大于這50 個訂單的材料種類總數(shù)30，說明其不適用于定制家具訂單聚類分析。

綜上所述，對于定制家具訂單的聚類分析，本文根據(jù)定制家具生產(chǎn)特點(diǎn)提出的蟻群聚類算法的聚類效果較好，結(jié)果更符合實(shí)際生產(chǎn)。

4 結(jié)論

本文結(jié)合定制家具的生產(chǎn)特點(diǎn)，根據(jù)蟻群的覓食行為，將聚類數(shù)目未知的蟻群算法應(yīng)用于定制家具訂單的聚類問題研究中。根據(jù)蟻群算法的特點(diǎn)計(jì)算類間轉(zhuǎn)移概率，將類別進(jìn)行歸并，將本文提出的聚類數(shù)目未知的蟻群聚類算法，與聚類數(shù)目已知的蟻群聚類算法和經(jīng)典的k-means算法進(jìn)行比較，結(jié)果表明：本文算法能有效提高訂單聚類的準(zhǔn)確性，降低了定制家具訂單生產(chǎn)時機(jī)器調(diào)整總時間，提高企業(yè)生產(chǎn)效率。