基于改進遺傳算法的無刷電機裝配線平衡優化

許曉偉，于海武，劉 超，張海峰

（1.合肥工業大學 電氣與自動化工程學院，合肥 230000；2.中國科學院合肥物質科學研究院先進制造技術研究所，常州213164；3.中國科學技術大學 工程科學學院，合肥 230000；4.中國科學技術大學 信息科學技術學院，合肥 230000）

基于改進遺傳算法的無刷電機裝配線平衡優化

許曉偉1,2，于海武2，劉 超3，張海峰4

（1.合肥工業大學 電氣與自動化工程學院，合肥 230000；2.中國科學院合肥物質科學研究院先進制造技術研究所，常州213164；3.中國科學技術大學 工程科學學院，合肥 230000；4.中國科學技術大學 信息科學技術學院，合肥 230000）

為提高無刷電機裝配線的生產效率，減少在制品積壓，提出了一種改進遺傳算法對其進行優化。建立了以工位和平滑指數相結合的多目標優化數學模型，應用雙種群自適應遺傳算法在MATLAB中編程，對無刷電機裝配線平衡問題進行仿真和優化。結果表明，優化后的裝配線提高了各個工位的生產效率，減少了在制品積壓，驗證了算法的有效性和可行性。

無刷電機；裝配線平衡；遺傳算法；多目標；雙種群

0 引言

在制造行業中，裝配線平衡[1～3]（Assembly Line Balance，ALB）問題無論是在規劃設計階段還是在生產管理中都是一個受到重視的問題，它關系到裝配線的生產效率和產品質量的穩定，是一個不斷發現、不斷改進、不斷完善的過程。ALB問題的實質是裝配線各工位的協調與配合，在滿足一定優先關系約束條件下，使各工位的作業時間總和盡可能相當，減少在制品積壓，提高生產效率。根據裝配線優化目標函數的不同，ALB問題可以分為三類：1）給定節拍時間（CT），求最小工位數m。2）給定工位數m，求最小節拍時間（CT）。3）工位數m和生產節拍CT已確定，求最小平滑指數SI（Smooth Index）。針對ALB問題，國內外學者做進行了較多此方面的研究[4～11]。文獻[6]運用遺傳算法和工業工程方法對某發動機公司缸蓋裝配線進行了研究分析；文獻[7]運用啟發式算法對空調電路板組裝線進行平衡計算和改善，取得了滿意的效果；文獻[8]運用蟻群算法對第一類裝配線平衡問題進行了研究；文獻[9]運用一種縮放適應度的遺傳算法對第二類裝配線平衡問題進行了研究，提出了一種較好的解決方案；文獻[10]運用自適應遺傳算法，對服裝生產的縫制流水線的平衡問題進行了研究；文獻[11]受鰻魚效應的啟發提出了一種針對裝配線平衡問題改進的遺傳算法。無刷電機裝配線同樣存在平衡問題，將平衡優化算法應用于無刷電機裝配線，還少有報道。

本文將對無刷電機裝配線平衡問題進行研究，通過建立以工位數和平滑指數相結合的多目標優化數學模型，采用雙種群自適應的遺傳算法進行優化，以期達到工位數最少，負荷均衡，從而提高裝配線生產效率，減少在制品積壓。

1 問題的提出

某公司太陽能用無刷電機[12]裝配線由定子、轉子和總裝配三部分組成，是典型的離散型流水線裝配線。該無刷電機裝配線的具體情況如下：

1）生產綱領：年產20萬套；

2）工作條件：8小時/班，2班/日，250日/年；

3）根據工藝流程，通過調研、論證，時間測定，確定的無刷電機裝配工藝如表1所示；

4）生產節拍和生產效率計算如表2所示；

5）無刷電機裝配線優先關系圖如圖1所示。

圖1 無刷電機裝配線優先關系圖

表1 無刷電機裝配工藝

表2 裝配線計算

圖中的節點（圓圈）表示工序任務及其序號，節點上面的數字表示該工序的作業時間，箭頭表示工序之間先后約束關系。

一般情況下，裝配線生產效率在50%～60%是一種沒有人和科學管理意識的粗放式生產，60%～70%存在人為平衡的因素，70%～85%是在科學管理的原則下進行的，大于85%時生產過程就是按照“一個流”的方式進行的, 由表二可知該裝配線生產效率為61.69%，說明各工序間存在不平衡現象，本文正是在此背景下，對無刷電機裝配線第一類平衡問題進行了研究。

2 建立數學模型

一個平衡的裝配線，不僅要求工位數最小，而且要考慮負荷是否均衡，而平滑指數SI越小，則表示裝配線各工位的負荷越均衡，如式(1)所示。

其中，STj為分配到第j個工位的所有任務的加工時間和，CT為生產節拍，m為工位數。

本文將綜合考慮工位數和平滑指數問題，采用線性加權和法將多目標優化問題轉化為單目標優化問題進行求解。轉化后的目標函數如式(2)所示。

其中，α、β為目標函數的權重，一般取α+β=1。若α＞β，則表示工位數目標比平滑指數目標更重要，由于本文側重于第一類平衡問題，所以取α=0.6，β=0.4。

約束條件為：

4）工序優先關系矩A=(aij)n×n，其中：

3 改進遺傳算法設計

常規的優化方法基于梯度尋優技術，計算速度快，但要求優化問題具有可微性，且通常只能求得局部最優解；遺傳算法適用于求解組合優化問題以及目標函數不可微或約束條件復雜的非線性優化問題。但常規遺傳算法存在過早收斂，容易陷入局部最優解等問題。鑒于此，本文采用雙種群自適應[13,14]的遺傳算法來求解無刷電機裝配線平衡問題，如圖2所示。

圖2 雙種群自適應遺傳算法流程圖

3.1 編碼

按照工序優先關系，采用實數編碼。染色體的長度等于工序數，每個經過編號的工序對應于一個基因位，按工序優先關系圖進行排列，以經典的Jackson生產線平衡模型為例（如圖3所示），給出了兩個染色體的編碼如圖4所示。

圖3 Jackson生產線平衡模型

圖4 染色體編碼

3.2 初始化種群

在保證工序優先關系條件下，通過隨機的方式生成初始種群，同時要保證初始化種群的多樣性和差異性。

3.3 譯碼

根據編碼的順序，依次計算工序的累積作業時間Ti，并與生產節拍CT進行比較，當計算到第i個工序時，累積作業時間Ti大于生產節拍CT，則以前面i-1個編碼對應的工序分配給第1個工位，依次進行計算、分配，直到把對應的編碼中的工序分配完畢。以Jackson生產線平衡編碼為例，假設生產節拍為10s，譯碼后的結果如圖5所示。

圖5 染色體譯碼

3.4 構造適應度函數

適應度函數也即評估函數，通常要滿足單值、連續、非負、最大化等條件，本文中的目標函數為最小化問題，將其轉化為最大化問題，可以構造適應度函數如式(3)所示。

3.5 選擇操作

采用最優染色體保留與輪盤賭相結合進行選擇。為了使進化過程中的最優解不被交叉或變異操作所破壞，種群中適應度最高的染色體不進行配對交叉而直接復制到下一代中，然后對剩余染色體進行輪盤賭選擇，適應度大的被選擇的概率越高。選擇概率pi如式(4)所示。

其中fi為染色體i的適應度值，為群內所有染色體的總適應度值。

3.6 交叉與變異操作

對于標準遺傳算法，交叉、變異概率為常數，不能很好的適應優化過程中參數變化問題。為此，本文采用了自適應交叉、變異概率，如式(5)、式(6)，以保證算法在進化初期有較強的全局搜索能力，而在進化后期則集中于局部擇優，保護優良染色體。

其中，pc為交叉概率，pm為變異概率，pcmax為最大交叉概率，pmmax為最大變異概率，fit'為要交叉的染色體中較大的適應度值，fitavg為種群平均適應度值。

交叉操作采用兩點交叉法，從種群中任選兩個染色體作為雙親，隨機產生兩個交叉點。假設染色體有M個基因，首先在[1，M-1]之間產生交叉點1，然后在[交叉點1，M]之間產生交叉點2。兩個交叉點把染色體分為頭部，身體，尾部3部分，交叉就是對兩個染色體身體部分進行交叉。根據圖6所示，父代染色體1需要交叉的基因為[3，5，7，9，6]，在染色體2中搜索[3，5，7，9，6]的排列方式為[5，3，7，6，9]，將其作為父代染色體1的身體部分，于是就產生了子代染色體1。父代染色體2采用同樣的方法產生子代染色體2。

變異操作如圖7所示。從種群中任選一個染色體，選擇染色體中的一點進行變異，將變異點前的基因片段保留到子代染色體中，變異點后的基因片段根據工序優先關系重新排列。

圖6 交叉操作

圖7 變異操作

3.7 算法終止條件

當滿足式(7)時，算法終止。

其中，fmax為最優染色體適應度值，favg為染色體適應度值的平均值，為極小值，這里取=0.001。

4 結果與討論

在MATLAB環境中編程，采用雙種群自適應遺傳算法對無刷電機裝配線進行優化，雙種群大小各為100，α=0.6，β=0.4，pcmax=0.4，pmmax=0.08，改進后的遺傳算法運行結束后，得出的最優工序分配方案如表3所示。

表3 工序分配方案

表4 優化結果

圖8 標準遺傳算法與改進遺傳算法迭代曲線

標準遺傳算法和雙種群自適應遺傳算法迭代曲線如圖8所示，可以看出標準遺傳算法迭代曲線的適應度值在經過約90代進化后才趨于穩定，達到最優值，而雙種群自適應遺傳算法迭代曲線的適應度值隨著進化代數的增加而迅速收斂，經過約40代進化后趨于穩定，達到了最優值，說明了改進后的遺傳算法能夠快速收斂找到最優解，驗證了算法的有效性和可行性。

通過表4，我們可以看出優化后，無刷電機裝配線的生產效率由61.69%提高到了84.12%，工位數由30個減少到了22個，裝配線的平滑指數由25.13下降到了8.258，有效的提高了各個工位的作業效率。優化前、后的直方圖如圖9所示，可以看出各工位的作業時間更加均衡。

5 結論

圖9 無刷電機裝配線優化前后直方圖

本文對無刷電機裝配線平衡問題進行了分析研究，提出了運用雙種群自適應遺傳算法對其進行優化。結果表明，改進后的遺傳算法保證了種群的多樣性，加快了算法的收斂速度，保護了優良個體，優化后的無刷電機裝配線減少了在制品積壓，提高了生產效率，驗證了算法的有效性和可行性。

[1] 陳星宇.基于改進遺傳算法的裝配生產線平衡技術研究[D].上海交通大學,2011.

[2] 肖中華.基于改進遺傳算法的汽車裝配線平衡問題研究[D].武漢科技大學,2010.

[3] 趙云飛.基于遺傳算法的生產線平衡改善研究[D].南昌大學,2014.

[4] Amen M.Heuristic methods for cost-oriented assembly line balancing:A comparison on solution quality and computing

【】【】time[J].International Journal of Production Economics, 2001,69(3):255-264.

[5] Bowman E H. Assembly-Line Balancing by Linear Programming[J].Operations Research,1960,8(3):385-389.

[6] 林秀木.汽車發動機裝配線平衡優化研究[D].沈陽工業大學,2016.

[7] 唐海波,吳斌,王正蘭.啟發式算法的裝配線的平衡改善應用[J].上海電機學院學報,2014(5):306-310.

[8] 毛凌翔,鄭永前.蟻群算法求解裝配線平衡第一類問題[J].計算機系統應用,2010,19(1):140-143.

[9] 張瑞軍,陳定方,楊琴.用改進的遺傳算法解決ALB問題[J].計算機工程與設計,2006,27(20):3731-3733.

[10] 梁會芹,費樹岷.自適應遺傳算法在服裝生產流水線平衡問題中的應用[J].工業控制計算機,2009,22(11):57-59.

[11] 陳曉峰,肖田元,郝新,等.應用遺傳算法解決裝配線平衡問題[J].計算機工程與應用,2001,37(23):81-83.

[12] 張濤.無刷直流電機的設計與性能研究[D].河南理工大學,2012.

[13] 秦偉娜.基于多種群的遺傳算法研究[D].山東師范大學,2009.

[14] 陳超.自適應遺傳算法的改進研究及其應用[D].華南理工大學,2011.

An optimization for brushless motor assembly line balancing based on improved genetic algorithm

XU Xiao-wei1,2, YU Hai-wu2, LIU Chao3, ZHANG Hai-feng4

TP29

：A

1009-0134(2017)06-0055-05

2017-03-24

中國科學院青年創新促進會資助（2016387）

許曉偉（1982 -），男，河南平頂山人，碩士研究生，研究方向為電機及其控制。