基于改進(jìn)遺傳算法的無(wú)刷電機(jī)裝配線平衡優(yōu)化

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

（1.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，合肥 230000；2.中國(guó)科學(xué)院合肥物質(zhì)科學(xué)研究院先進(jìn)制造技術(shù)研究所，常州213164；3.中國(guó)科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院，合肥 230000；4.中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，合肥 230000）

基于改進(jìn)遺傳算法的無(wú)刷電機(jī)裝配線平衡優(yōu)化

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

（1.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，合肥 230000；2.中國(guó)科學(xué)院合肥物質(zhì)科學(xué)研究院先進(jìn)制造技術(shù)研究所，常州213164；3.中國(guó)科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院，合肥 230000；4.中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，合肥 230000）

為提高無(wú)刷電機(jī)裝配線的生產(chǎn)效率，減少在制品積壓，提出了一種改進(jìn)遺傳算法對(duì)其進(jìn)行優(yōu)化。建立了以工位和平滑指數(shù)相結(jié)合的多目標(biāo)優(yōu)化數(shù)學(xué)模型，應(yīng)用雙種群自適應(yīng)遺傳算法在MATLAB中編程，對(duì)無(wú)刷電機(jī)裝配線平衡問(wèn)題進(jìn)行仿真和優(yōu)化。結(jié)果表明，優(yōu)化后的裝配線提高了各個(gè)工位的生產(chǎn)效率，減少了在制品積壓，驗(yàn)證了算法的有效性和可行性。

無(wú)刷電機(jī)；裝配線平衡；遺傳算法；多目標(biāo)；雙種群

0 引言

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

本文將對(duì)無(wú)刷電機(jī)裝配線平衡問(wèn)題進(jìn)行研究，通過(guò)建立以工位數(shù)和平滑指數(shù)相結(jié)合的多目標(biāo)優(yōu)化數(shù)學(xué)模型，采用雙種群自適應(yīng)的遺傳算法進(jìn)行優(yōu)化，以期達(dá)到工位數(shù)最少，負(fù)荷均衡，從而提高裝配線生產(chǎn)效率，減少在制品積壓。

1 問(wèn)題的提出

某公司太陽(yáng)能用無(wú)刷電機(jī)[12]裝配線由定子、轉(zhuǎn)子和總裝配三部分組成，是典型的離散型流水線裝配線。該無(wú)刷電機(jī)裝配線的具體情況如下：

1）生產(chǎn)綱領(lǐng)：年產(chǎn)20萬(wàn)套；

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

3）根據(jù)工藝流程，通過(guò)調(diào)研、論證，時(shí)間測(cè)定，確定的無(wú)刷電機(jī)裝配工藝如表1所示；

4）生產(chǎn)節(jié)拍和生產(chǎn)效率計(jì)算如表2所示；

5）無(wú)刷電機(jī)裝配線優(yōu)先關(guān)系圖如圖1所示。

圖1 無(wú)刷電機(jī)裝配線優(yōu)先關(guān)系圖

表1 無(wú)刷電機(jī)裝配工藝

表2 裝配線計(jì)算

圖中的節(jié)點(diǎn)（圓圈）表示工序任務(wù)及其序號(hào)，節(jié)點(diǎn)上面的數(shù)字表示該工序的作業(yè)時(shí)間，箭頭表示工序之間先后約束關(guān)系。

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

2 建立數(shù)學(xué)模型

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

其中，STj為分配到第j個(gè)工位的所有任務(wù)的加工時(shí)間和，CT為生產(chǎn)節(jié)拍，m為工位數(shù)。

本文將綜合考慮工位數(shù)和平滑指數(shù)問(wèn)題，采用線性加權(quán)和法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題進(jìn)行求解。轉(zhuǎn)化后的目標(biāo)函數(shù)如式(2)所示。

其中，α、β為目標(biāo)函數(shù)的權(quán)重，一般取α+β=1。若α＞β，則表示工位數(shù)目標(biāo)比平滑指數(shù)目標(biāo)更重要，由于本文側(cè)重于第一類平衡問(wèn)題，所以取α=0.6，β=0.4。

約束條件為：

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

3 改進(jìn)遺傳算法設(shè)計(jì)

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

圖2 雙種群自適應(yīng)遺傳算法流程圖

3.1 編碼

按照工序優(yōu)先關(guān)系，采用實(shí)數(shù)編碼。染色體的長(zhǎng)度等于工序數(shù)，每個(gè)經(jīng)過(guò)編號(hào)的工序?qū)?yīng)于一個(gè)基因位，按工序優(yōu)先關(guān)系圖進(jìn)行排列，以經(jīng)典的Jackson生產(chǎn)線平衡模型為例（如圖3所示），給出了兩個(gè)染色體的編碼如圖4所示。

圖3 Jackson生產(chǎn)線平衡模型

圖4 染色體編碼

3.2 初始化種群

在保證工序優(yōu)先關(guān)系條件下，通過(guò)隨機(jī)的方式生成初始種群，同時(shí)要保證初始化種群的多樣性和差異性。

3.3 譯碼

根據(jù)編碼的順序，依次計(jì)算工序的累積作業(yè)時(shí)間Ti，并與生產(chǎn)節(jié)拍CT進(jìn)行比較，當(dāng)計(jì)算到第i個(gè)工序時(shí)，累積作業(yè)時(shí)間Ti大于生產(chǎn)節(jié)拍CT，則以前面i-1個(gè)編碼對(duì)應(yīng)的工序分配給第1個(gè)工位，依次進(jìn)行計(jì)算、分配，直到把對(duì)應(yīng)的編碼中的工序分配完畢。以Jackson生產(chǎn)線平衡編碼為例，假設(shè)生產(chǎn)節(jié)拍為10s，譯碼后的結(jié)果如圖5所示。

圖5 染色體譯碼

3.4 構(gòu)造適應(yīng)度函數(shù)

適應(yīng)度函數(shù)也即評(píng)估函數(shù)，通常要滿足單值、連續(xù)、非負(fù)、最大化等條件，本文中的目標(biāo)函數(shù)為最小化問(wèn)題，將其轉(zhuǎn)化為最大化問(wèn)題，可以構(gòu)造適應(yīng)度函數(shù)如式(3)所示。

3.5 選擇操作

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

其中fi為染色體i的適應(yīng)度值，為群內(nèi)所有染色體的總適應(yīng)度值。

3.6 交叉與變異操作

對(duì)于標(biāo)準(zhǔn)遺傳算法，交叉、變異概率為常數(shù)，不能很好的適應(yīng)優(yōu)化過(guò)程中參數(shù)變化問(wèn)題。為此，本文采用了自適應(yīng)交叉、變異概率，如式(5)、式(6)，以保證算法在進(jìn)化初期有較強(qiáng)的全局搜索能力，而在進(jìn)化后期則集中于局部擇優(yōu)，保護(hù)優(yōu)良染色體。

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

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

變異操作如圖7所示。從種群中任選一個(gè)染色體，選擇染色體中的一點(diǎn)進(jìn)行變異，將變異點(diǎn)前的基因片段保留到子代染色體中，變異點(diǎn)后的基因片段根據(jù)工序優(yōu)先關(guān)系重新排列。

圖6 交叉操作

圖7 變異操作

3.7 算法終止條件

當(dāng)滿足式(7)時(shí)，算法終止。

其中，fmax為最優(yōu)染色體適應(yīng)度值，favg為染色體適應(yīng)度值的平均值，為極小值，這里取=0.001。

4 結(jié)果與討論

在MATLAB環(huán)境中編程，采用雙種群自適應(yīng)遺傳算法對(duì)無(wú)刷電機(jī)裝配線進(jìn)行優(yōu)化，雙種群大小各為100，α=0.6，β=0.4，pcmax=0.4，pmmax=0.08，改進(jìn)后的遺傳算法運(yùn)行結(jié)束后，得出的最優(yōu)工序分配方案如表3所示。

表3 工序分配方案

表4 優(yōu)化結(jié)果

圖8 標(biāo)準(zhǔn)遺傳算法與改進(jìn)遺傳算法迭代曲線

標(biāo)準(zhǔn)遺傳算法和雙種群自適應(yīng)遺傳算法迭代曲線如圖8所示，可以看出標(biāo)準(zhǔn)遺傳算法迭代曲線的適應(yīng)度值在經(jīng)過(guò)約90代進(jìn)化后才趨于穩(wěn)定，達(dá)到最優(yōu)值，而雙種群自適應(yīng)遺傳算法迭代曲線的適應(yīng)度值隨著進(jìn)化代數(shù)的增加而迅速收斂，經(jīng)過(guò)約40代進(jìn)化后趨于穩(wěn)定，達(dá)到了最優(yōu)值，說(shuō)明了改進(jìn)后的遺傳算法能夠快速收斂找到最優(yōu)解，驗(yàn)證了算法的有效性和可行性。

通過(guò)表4，我們可以看出優(yōu)化后，無(wú)刷電機(jī)裝配線的生產(chǎn)效率由61.69%提高到了84.12%，工位數(shù)由30個(gè)減少到了22個(gè)，裝配線的平滑指數(shù)由25.13下降到了8.258，有效的提高了各個(gè)工位的作業(yè)效率。優(yōu)化前、后的直方圖如圖9所示，可以看出各工位的作業(yè)時(shí)間更加均衡。

5 結(jié)論

圖9 無(wú)刷電機(jī)裝配線優(yōu)化前后直方圖

本文對(duì)無(wú)刷電機(jī)裝配線平衡問(wèn)題進(jìn)行了分析研究，提出了運(yùn)用雙種群自適應(yīng)遺傳算法對(duì)其進(jìn)行優(yōu)化。結(jié)果表明，改進(jìn)后的遺傳算法保證了種群的多樣性，加快了算法的收斂速度，保護(hù)了優(yōu)良個(gè)體，優(yōu)化后的無(wú)刷電機(jī)裝配線減少了在制品積壓，提高了生產(chǎn)效率，驗(yàn)證了算法的有效性和可行性。

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

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

[3] 趙云飛.基于遺傳算法的生產(chǎn)線平衡改善研究[D].南昌大學(xué),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] 林秀木.汽車發(fā)動(dòng)機(jī)裝配線平衡優(yōu)化研究[D].沈陽(yáng)工業(yè)大學(xué),2016.

[7] 唐海波,吳斌,王正蘭.啟發(fā)式算法的裝配線的平衡改善應(yīng)用[J].上海電機(jī)學(xué)院學(xué)報(bào),2014(5):306-310.

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

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

[10] 梁會(huì)芹,費(fèi)樹岷.自適應(yīng)遺傳算法在服裝生產(chǎn)流水線平衡問(wèn)題中的應(yīng)用[J].工業(yè)控制計(jì)算機(jī),2009,22(11):57-59.

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

[12] 張濤.無(wú)刷直流電機(jī)的設(shè)計(jì)與性能研究[D].河南理工大學(xué),2012.

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

[14] 陳超.自適應(yīng)遺傳算法的改進(jìn)研究及其應(yīng)用[D].華南理工大學(xué),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

中國(guó)科學(xué)院青年創(chuàng)新促進(jìn)會(huì)資助（2016387）

許曉偉（1982 -），男，河南平頂山人，碩士研究生，研究方向?yàn)殡姍C(jī)及其控制。