□ 李愛平 □ 趙亞西

同濟(jì)大學(xué)機械與能源工程學(xué)院 上海 201804

1　研究背景

在企業(yè)實際生產(chǎn)中，改善裝配線的生產(chǎn)效益是研究重點。裝配是制造與信息控制相結(jié)合的過程，設(shè)計出優(yōu)良的裝配線平衡方案，能夠使裝配線高效且可靠地運行，進(jìn)而提高生產(chǎn)效率，增加企業(yè)效益，可見，研究裝配線平衡具有很大的實際意義。裝配線平衡問題按不同的優(yōu)化目標(biāo)主要分為三類［1-2］：① 生產(chǎn)節(jié)拍一定，求最優(yōu)工作站數(shù)；② 工作站數(shù)固定，求最優(yōu)生產(chǎn)節(jié)拍；③工作站數(shù)已知，求最優(yōu)平滑因子。裝配線平衡問題是典型的非確定多項式難題，對于求解算法有較高的要求，近年來主要以遺傳算法等啟發(fā)式算法為主，由于算法可行解過多，為了搜索出更優(yōu)的可行解，算法需要改進(jìn)。

張子凱等［3］針對大規(guī)?；炝鱑型裝配線平衡問題，提出了一種基于多級隨機分配編碼的改進(jìn)遺傳算法，算法在降低計算復(fù)雜度的同時能準(zhǔn)確求出問題較優(yōu)解。梁雨生等［4］針對裝配線平衡問題，提出了一種基于可行作業(yè)序列的多種群遺傳算法，擴(kuò)大了搜索的空間范圍，有效避免產(chǎn)生局部最優(yōu)的情況。扈靜等［5］針對傳統(tǒng)混合裝配生產(chǎn)線缺乏一工位多產(chǎn)品研究的現(xiàn)狀，設(shè)計了基于激素調(diào)節(jié)機制的改進(jìn)遺傳算法適應(yīng)度函數(shù)，以及選擇、交叉與變異算子，對一工位多產(chǎn)品的混合裝配生產(chǎn)線平衡問題模型進(jìn)行求解，提升了算法性能。董雙飛［6］結(jié)合遺傳算法與混流裝配線的特點，對遺傳算法中初始種群的產(chǎn)生、算法的可視化操作、交叉與變異操作的方式及概率的設(shè)置進(jìn)行改進(jìn)，并提出種群擴(kuò)張機制，提高了算法的全局搜索能力。李險峰［7］針對傳統(tǒng)遺傳算法在種群數(shù)目有限的情況下呈現(xiàn)早熟問題進(jìn)行分析，提出并實現(xiàn)了一種加入改進(jìn)遺傳算子策略，且結(jié)合模擬退火思路的混合遺傳算法。韓煜東、董雙飛等［8］設(shè)計了基于自然數(shù)序列和拓?fù)渑判虻母倪M(jìn)遺傳算法，對模型進(jìn)行求解時通過改進(jìn)交叉、變異操作來保護(hù)優(yōu)秀基因，同時提出了種群擴(kuò)張機制，在求解效率和求解質(zhì)量方面取得顯著成效。劉雪梅等［9］基于工位復(fù)雜性測度提出了一種隨機型裝配線平衡優(yōu)化方法，并將基于動態(tài)步長法的改進(jìn)遺傳算法用于優(yōu)化求解。陳星宇［10］提出一種雙種群遺傳算法，設(shè)計了基于優(yōu)先關(guān)聯(lián)矩陣的編碼、譯碼，以及適應(yīng)度設(shè)計、交叉選擇和變異算子，在求解裝配線平衡問題時有顯著成效。Hou Liang等［11］針對產(chǎn)品族裝配線提出了一種改進(jìn)的雙種群遺傳算法，同時為了彌補傳統(tǒng)解碼方法的不足，提出了一種新的解碼算法，加快了算法的搜索速度。

綜上所述，學(xué)者們從編碼、解碼、交叉、變異、選擇等各環(huán)節(jié)對遺傳算法做出改進(jìn)，但是尚未從近親不能繁衍后代的生物學(xué)角度考慮算法的改進(jìn)方式。筆者為了提高遺傳算法的搜索深度，考慮生物學(xué)角度近親不能交叉的規(guī)則，建立一種Bagging集成聚類方法用于分析種群個體間的親緣關(guān)系，并基于此方法改進(jìn)遺傳算法的交叉環(huán)節(jié)，在雙目標(biāo)裝配線平衡優(yōu)化問題中提高算法的搜索深度，得到更優(yōu)的可行解。

2　基于Bagging集成聚類的種群聚類分析

傳統(tǒng)遺傳算法在求解裝配線平衡等非確定多項式難題時，常常表現(xiàn)出搜索深度不足的問題，為了提高遺傳算法的搜索深度，筆者提出一種Bagging集成聚類算法，用Bagging對幾個K均值算法基學(xué)習(xí)器進(jìn)行集成學(xué)習(xí)，經(jīng)過投票機制后得出每個種群個體所屬的類別。

2.1　K均值聚類算法

K均值算法的原理是使聚類的所有樣本到聚類中心距離的平方和最小，是經(jīng)典的硬聚類算法。

K均值聚類算法使用的聚類準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則：

為了優(yōu)化聚類結(jié)果，應(yīng)使準(zhǔn)則最小化。

第一步，給出n個混合樣本，令I(lǐng)=1，表示迭代次數(shù)，選取 K 個初始聚合中心 Zj（I），j=1，2，...，K。

第二步，計算每個樣本與聚合中心的距離D（xk，Zj（I）），k=1，2，...，n，j=1，2，...，K。 若 D（xk，Zj（I））=min｛D（xk，Zj（I）），k=1，2，...，n｝，則 xk∈wi。

第三步，計算 K 個新聚合中心，Zj（I+1）=，j=1，2，...，K。

第四步，判斷若 Zj（I+1）≠Zj（I），j=1，2，...，K，則將I+1賦值給I，返回第二步；否則，算法結(jié)束。

筆者的K均值聚類算法采取成批處理法進(jìn)行初始分類的選取和調(diào)整，代表點就是聚類中心，選一批代表點后，計算其它樣本到聚類中心的距離，將所有樣本歸于最近的中心點，形成初始分類，再重新計算聚類中心。

2．2　K均值集成聚類

2.2.1集成學(xué)習(xí)

集成學(xué)習(xí)是利用幾個學(xué)習(xí)器進(jìn)行綜合學(xué)習(xí)。先選定幾個個體學(xué)習(xí)器，然后使用一些結(jié)合方法進(jìn)行結(jié)合。很多經(jīng)典的機器學(xué)習(xí)算法，如隨機森林法等都是采用集成學(xué)習(xí)建立的。隨機森林法由多個決策樹算法集成，這種個體學(xué)習(xí)器稱為基學(xué)習(xí)器。集成學(xué)習(xí)結(jié)構(gòu)圖如圖1所示。

▲圖1 集成學(xué)習(xí)結(jié)構(gòu)圖

2.2.2 Bootstrap

想要得到泛化性能強的集成，集成中的個體學(xué)習(xí)器應(yīng)當(dāng)盡可能相互獨立。雖然獨立在現(xiàn)實任務(wù)中無法做到，但可以設(shè)法使基學(xué)習(xí)器盡可能具有較大的差異。Bootstrap是統(tǒng)計學(xué)習(xí)中的一種重采樣技術(shù)，這種看似簡單的方法，對之后的很多技術(shù)都產(chǎn)生了深遠(yuǎn)影響。機器學(xué)習(xí)中的Bagging、AdaBoost等方法其實都蘊含了Bootstrap的思想。

在統(tǒng)計時，面臨的只有樣本，樣本具有明顯的不確定性。正因為不確定性的存在，才使統(tǒng)計能夠生生不息，統(tǒng)計的意義也就在于基于樣本推斷總體。Bootstrap方法最初由美國斯坦福大學(xué)統(tǒng)計學(xué)教授Efron在1977年提出，作為一種嶄新的增廣樣本統(tǒng)計方法，Bootstrap方法為集成學(xué)習(xí)的采樣提供了很好的思路。

2.2.3 Bagging

Bagging是并行式集成學(xué)習(xí)方法中最著名的代表。給定樣本容量為n的數(shù)據(jù)集，先隨機取出一個樣本放入采樣集中，再將樣本放回初始數(shù)據(jù)集，使下次采樣時該樣本仍有可能被選中，這樣經(jīng)過v次隨機抽樣，得到含v個樣本的采樣集。初始訓(xùn)練集中有的樣本在采樣集中多次出現(xiàn)，有的則從未出現(xiàn)。重復(fù)抽樣過程T次，則得到T個樣本容量為v的Bootstrap樣本，記為Di=（x1，x2，...，xv），i=1，2，...，T。

采樣出T個含v個訓(xùn)練樣本的采樣集，然后基于每個采樣集訓(xùn)練出一個基學(xué)習(xí)器，再對這些基學(xué)習(xí)器進(jìn)行結(jié)合，這就是Bagging的基本流程。在對結(jié)果進(jìn)行輸出結(jié)合時，Bagging通常使用投票原則。

2.2.4 K均值集成聚類算法

K均值聚類算法在機器學(xué)習(xí)中屬于無監(jiān)督學(xué)習(xí)，即使用沒有標(biāo)簽的數(shù)據(jù)進(jìn)行學(xué)習(xí)。集成學(xué)習(xí)使用多個基學(xué)習(xí)器來降低模型泛化誤差中的偏差和方差。將以上兩個概念結(jié)合起來，就是無監(jiān)督集成學(xué)習(xí)，即對沒有標(biāo)簽的數(shù)據(jù)使用集成算法。

將K均值與Bagging結(jié)合，生成K均值集成聚類算法，算法具體流程如圖2所示。

▲圖2 K均值集成聚類算法流程

第一步，按Bootstrap方式，對初始訓(xùn)練集進(jìn)行v次有放回的隨機抽樣，重復(fù)T-1次抽樣過程，采樣出T-1個含v個訓(xùn)練樣本的Bootstrap采樣集，記為Di=（x1，x2，...，xv），i=1，2，...，T-1。

第二步，由于存在未被抽樣的樣本，因此當(dāng)每個樣本都需要歸類時，需要將剩余所有未被抽樣的w個樣本取出，組成最后一個采樣集，記為 DT=（x1，x2，...，xw），則總的采樣集記為：

第三步，將T個采樣集分別用K均值基學(xué)習(xí)器來單獨進(jìn)行聚類訓(xùn)練，設(shè)初始訓(xùn)練集樣本數(shù)為z，聚類類別數(shù)為K，建立一個z·K維矩陣，用于記錄每個個體學(xué)習(xí)器對每個樣本聚類類別的投票情況，第i行第j列的數(shù)字s表示有s個基學(xué)習(xí)器將第i個樣本歸類為第j類。

第四步，根據(jù)建立的z·K維矩陣，按照投票法則來決定每一個樣本的最終聚類類別。樣本的最終類別由票數(shù)最多的類別決定，若存在投票數(shù)相同的類別，則在其中隨機選擇一個類別作為該樣本最后的聚類類別。

3　雙目標(biāo)裝配線平衡優(yōu)化數(shù)學(xué)模型

筆者在工作站數(shù)固定和作業(yè)元素優(yōu)先關(guān)系的約束條件下，將裝配線生產(chǎn)節(jié)拍和平滑因子作為優(yōu)化目標(biāo)，建立雙目標(biāo)裝配線平衡優(yōu)化模型。

3.1　約束條件

C為生產(chǎn)節(jié)拍，I為作業(yè)元素集合，J為工作站集合，n為作業(yè)元素個數(shù)，mi為種群中第i個個體的實際工作站數(shù)目，M為確定的工作站數(shù)，Jk為第k個工作站的作業(yè)元素集合， k∈（1，M）。

x為一維向量，表征各裝配作業(yè)元素排序情況，若x=［x1，x2，...，xn］， 滿足所有約束條件的 xi即為可行解。X為n·M維矩陣，表征各裝配作業(yè)元素在工作站上的分配情況，對于 X（i，k）∈X，若 X（i，k）=1，則表示裝配作業(yè)元素 i分配在工作站 k；若 X（i，k）=0，則表示裝配作業(yè)元素i未分配在工作站k。PPred為n×2維優(yōu)先關(guān)系集合，PPred（i，1）是 PPred（i，2）的前序作業(yè)元素。 P 為 n·n維優(yōu)先關(guān)系矩陣，對于 P（k，i）∈P，若 P（k，i）=1，則表示 k 為 i的前序作業(yè)元素；若 P（k，i）=0，則表示 k 為 i的后序作業(yè)元素。ti為第i道作業(yè)元素的作業(yè)時間。

在企業(yè)實際生產(chǎn)中，裝配線常常已經(jīng)建立完畢，若改建或擴(kuò)建，則成本高昂，所以工作站數(shù)是一定的。

每個作業(yè)元素只能分配到一個工作站上，即：

要在滿足優(yōu)先關(guān)系的條件下分配作業(yè)元素，即：

各工作站的作業(yè)總時間小于等于生產(chǎn)節(jié)拍，即：

工作站數(shù)是一定的，即：

3.2　優(yōu)化目標(biāo)

筆者選擇優(yōu)化目標(biāo)為生產(chǎn)節(jié)拍C和平滑因子SI，因為減小生產(chǎn)節(jié)拍C能起到縮短總空閑時間的作用，而平滑因子SI是評價裝配線負(fù)荷平衡的指標(biāo)，負(fù)荷平衡的作用是提高人員和設(shè)備利用率。優(yōu)化目標(biāo)定義為min C ，min SI。

其中，生產(chǎn)節(jié)拍C的定義是工作站作業(yè)時間的最大值，T（k）為第k個工作站的作業(yè)時間，則有：

平滑因子SI為：

3.3　數(shù)學(xué)模型

綜合約束條件和優(yōu)化目標(biāo)，定義如下數(shù)學(xué)模型：

4　基于Bagging集成聚類的改進(jìn)遺傳算法

為提高遺傳算法的搜索深度，筆者基于Bagging集成聚類算法的種群聚類分析方法，對遺傳算法的交叉部分進(jìn)行改進(jìn)，判斷隨機配對的兩個體是否是屬于同一族群的近親，避免近親個體交叉。

4.1　算法流程

記Spop為種群數(shù)目，要求是2的倍數(shù)，Ppop（t）為第t代種群，G為遺傳代數(shù)，Pc為交叉概率，Pm為變異概率，其余參數(shù)定義同前，則改進(jìn)遺傳算法流程如下。

第一步，初始值設(shè)定。 輸入 Spop、G、C、M、Pc、Pm、T、v、K 的值。

第二步，初始化種群。令t=0，隨機產(chǎn)生滿足約束、數(shù)量為 Spop的初始種群 Ppop（0）。

第三步，適應(yīng)度計算。對第t代種群Ppop（t）中每個個體計算適應(yīng)度參考值，即染色體的生產(chǎn)節(jié)拍C和平滑因子SI。

第四步，懲罰策略。檢查種群中的個體是否滿足約束條件，若不滿足工作站數(shù)固定為M的約束，則給此個體適應(yīng)度一個懲罰項，將兩個適應(yīng)度參考值變?yōu)槟硺O大值，如500。

第五步，雙目標(biāo)并列選擇操作。根據(jù)兩個適應(yīng)度參考值，分別選出兩個適應(yīng)度參考值最優(yōu)的s個個體，s=Spop/2，然后重組為新種群，作為第t+1代種群。

第六步，交叉操作。利用Bagging集成聚類算法對交叉規(guī)則進(jìn)行改進(jìn)，交叉形式采用單點交叉。

第七步，變異操作。變異規(guī)則采用單點變異。

第八步，循環(huán)。將t+1賦值給t，如果滿足停止條件，結(jié)束；否則轉(zhuǎn)向第三步。

4.2　編碼與策略

在滿足作業(yè)元素優(yōu)先關(guān)系的約束條件下，對所有作業(yè)元素進(jìn)行排列。每個作業(yè)元素對應(yīng)染色體的一個基因位，排列好的個體記為一條編碼染色體。

在交叉變異后，對種群中的個體重新做約束檢查。若某個體不滿足工作站數(shù)固定的條件，則對該個體的兩個適應(yīng)度參考值生產(chǎn)節(jié)拍C和平滑因子SI給予一個懲罰項，如500。由于懲罰項較大，因此被懲罰的個體容易在選擇環(huán)節(jié)淘汰。

對第t代種群Ppop（t），根據(jù)計算好的每個個體適應(yīng)度參考值生產(chǎn)節(jié)拍C和平滑因子SI，獨立選出最優(yōu)的前1/2個體，然后組成新的第t+1代種群。

4.3　交叉操作

遺傳算法中，個體以編碼形式存在，可以將各編碼值看作個體的特征值，用聚類方法來判斷兩個體是否屬于近親。K均值屬于硬聚類，是一種弱學(xué)習(xí)器，學(xué)習(xí)效果有限。將多個K均值進(jìn)行結(jié)合，則得到超越個體學(xué)習(xí)器的優(yōu)越泛化性能。筆者通過之前建立的基于Bagging的K均值集成聚類方法改進(jìn)遺傳算法的交叉操作。

由交叉概率 Pm決定第t代種群 Ppop（t）發(fā)生交叉的概率，交叉具體規(guī)則為單點交叉，具體如下。

第一步，將排序打亂，隨機配對。

第二步，對第t代種群Ppop（t）中所有個體，采樣出T個含v個訓(xùn)練樣本的采樣集。將剩余所有未被抽樣的w個樣本作為最后一個采樣集，對采樣集進(jìn)行Bagging K均值集成聚類算法，聚類類別數(shù)為K，根據(jù)投票法則得到每個個體的聚類類別。

第三步，對比隨機配對的兩個體所屬的聚類類別，若兩者屬于同一類別，則當(dāng)前兩個體不交叉，跳過，進(jìn)行下一組；否則，兩個體進(jìn)行交叉，交叉采用單點交叉規(guī)則。

5　實例分析

為了驗證筆者算法的深度搜索能力，以某汽車變速箱裝配線為實例，對該條裝配線進(jìn)行平衡優(yōu)化。汽車變速箱裝配體由三個主要部分組成，作業(yè)元素數(shù)量n=27，優(yōu)先關(guān)系如圖3所示。裝配線的工作站已建立好，工作站數(shù)M=12，若改建或擴(kuò)建，則成本高昂。

對該裝配線進(jìn)行平衡優(yōu)化，在工作站數(shù)固定為M=12的約束下，以生產(chǎn)節(jié)拍C和平滑因子SI為優(yōu)化目標(biāo)，利用提出的改進(jìn)型遺傳算法進(jìn)行求解，提高搜索深度。

5.1　雙目標(biāo)優(yōu)化求解

利用MATLAB 2015b編程求解，數(shù)學(xué)模型的參數(shù)設(shè)定如下：固定工作站數(shù)M=12，交叉概率Pc=0.6，變異概率Pm=0.05，遺傳代數(shù) G=50，種群數(shù)量 S=200，生產(chǎn)節(jié)拍初始值C=130 s。

當(dāng)設(shè)定T=5、v=60、K=3時，生產(chǎn)節(jié)拍C和平滑因子SI的優(yōu)化過程分別如圖4和圖5所示。優(yōu)化過程記錄了每代種群中C和SI的最優(yōu)值。

由圖4和圖5可知，兩個目標(biāo)都得到了優(yōu)化。生產(chǎn)節(jié)拍優(yōu)化比較容易，在5代以內(nèi)得到最終優(yōu)化值。平滑因子在不斷優(yōu)化，在40代后收斂，沒有過早收斂。選取一些具有代表性的優(yōu)秀解，見表1、表2。

▲圖3 汽車變速箱裝配優(yōu)先關(guān)系

由表1、表2可見，生產(chǎn)節(jié)拍C和平滑因子SI兩個目標(biāo)均得到了優(yōu)化，提高了裝配效率，減少了總空閑時間，算法對可行解進(jìn)行了深度搜索，優(yōu)化出多個較優(yōu)解。

▲圖4 生產(chǎn)節(jié)拍優(yōu)化過程

▲圖5 平滑因子優(yōu)化過程

表1　作業(yè)元素分配方案1

5.2　方案對比

基于Bagging集成聚類的改進(jìn)遺傳算法在不同主要參數(shù)設(shè)置時，搜索深度會有差異，主要參數(shù)包括T、v和K。為證明改進(jìn)后的遺傳算法搜索深度確實有提升，對參數(shù)進(jìn)行不同設(shè)置，做對比試驗。一是給定不同的T、v、K進(jìn)行優(yōu)化，二是利用未改進(jìn)的遺傳算法進(jìn)行求解。進(jìn)行多組對比試驗，取兩個目標(biāo)數(shù)值之和最小的解為代表，對比結(jié)果見表3。

表2　作業(yè)元素分配方案2

表3　方案對比

由表3分析可知，每組試驗得到的平衡方案中生產(chǎn)節(jié)拍C優(yōu)化解都相同，而平滑因子SI則不相同，這說明從單一的優(yōu)化目標(biāo)角度來看，生產(chǎn)節(jié)拍的優(yōu)化較為容易，平滑因子的優(yōu)化則較難，不同參數(shù)設(shè)置下得到的搜索深度不同。對比各組試驗結(jié)果，用改進(jìn)遺傳算法求出的優(yōu)化解在不同參數(shù)設(shè)置下的結(jié)果并不相同，搜索深度有差別；整體上，用改進(jìn)遺傳算法求出的優(yōu)化解明顯優(yōu)于未改進(jìn)遺傳算法。綜上所述，基于Bagging集成聚類的改進(jìn)遺傳算法，相比未改進(jìn)的遺傳算法，搜索深度更深，能得到更優(yōu)的解。

6　結(jié)束語

筆者從生物學(xué)中近親不能交叉的角度考慮，建立了一種基于Bagging集成聚類算法的種群聚類分析方法，利用這一方法判斷種群中的兩個體是否屬于近親，進(jìn)而改進(jìn)了遺傳算法的交叉規(guī)則。以生產(chǎn)節(jié)拍和平滑因子為優(yōu)化目標(biāo)，建立了雙目標(biāo)裝配線平衡模型，將改進(jìn)遺傳算法應(yīng)用于雙目標(biāo)裝配線平衡實例中。實例顯示，改進(jìn)遺傳算法相比未改進(jìn)遺傳算法，有效提升了算法的深度尋優(yōu)能力。

［1］ 竇建平，蘇春，李俊.求解第Ⅰ類裝配線平衡問題的離散粒子群優(yōu)化算法［J］.計算機集成制造系統(tǒng)， 2012， 18（5）：1021-1030.

［2］ 鄭巧仙，李元香，李明，等.面向第Ⅱ類裝配線平衡問題的蟻群算法［J］.計算機集成制造系統(tǒng)， 2012， 18（5）：999-1005.

［3］ 張子凱，唐秋華，張利平，等.改進(jìn)遺傳算法求解大規(guī)模混流 U型裝配線問題 ［J］.機械設(shè)計與制造，2016（1）：137-139.

［4］ 梁雨生，李向波.基于遺傳算法的裝配線平衡問題研究［J］.價值工程， 2013， 32（5）：123-125.

［5］ 扈靜，蔣增強，葛茂根，等.基于改進(jìn)遺傳算法的混合裝配生產(chǎn)線平衡問題研究［J］.合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2010， 33（7）：1006-1009.

［6］ 董雙飛.基于改進(jìn)遺傳算法的混流裝配線多目標(biāo)平衡優(yōu)化研究［D］.重慶：重慶交通大學(xué)，2015.

［7］ 李險峰.基于改進(jìn)遺傳算法的汽車裝配生產(chǎn)線平衡問題研究［D］.北京：北京科技大學(xué)，2017.

［8］ 韓煜東，董雙飛，譚柏川.基于改進(jìn)遺傳算法的混裝線多目標(biāo)優(yōu)化［J］.計算機集成制造系統(tǒng)， 2015， 21（6）：1476-1485.

［9］ 劉雪梅，蘭琳琳，顧佳巍，等.基于工位復(fù)雜性測度的隨機型裝配線平衡優(yōu)化方法 ［J/OL］.計算機集成制造系統(tǒng)，http：//kns.cnki.net/KCMS/detail/11.3619.TP.20170627.1615.006.html.

［10］陳星宇.基于改進(jìn)遺傳算法的裝配生產(chǎn)線平衡技術(shù)研究［D］.上海：上海交通大學(xué)，2011.

［11］ HOU L，WU Y M，LAI R S，et al.Product Family Assembly Line Balancing Based on an Improved Genetic Algorithm［J］.The International Journal of Advanced Manufacturing Technology， 2014，70（9-12）：1775-1786.