基于改進(jìn)NSGA-II算法求解混流裝配線平衡問題*

羅利飛，吳永明,b,c，黃海松，徐艷霞，張 晗

(貴州大學(xué) a.現(xiàn)代制造技術(shù)教育部重點實驗室；b.貴州省公共大數(shù)據(jù)重點實驗室；c.機(jī)械工程學(xué)院，貴陽 550025)

0 引言

混流裝配線平衡是指在已有生產(chǎn)條件下，兩種或兩種以上的產(chǎn)品在同一條裝配線上生產(chǎn)，合理地利用現(xiàn)有資源，低成本、高效率、最大可能地滿足市場多個客戶的生產(chǎn)需求，混流裝配線具有復(fù)雜的生產(chǎn)工藝且生產(chǎn)批量小、高頻率地變換產(chǎn)品，換裝成本高。因此，混流裝配線的生產(chǎn)計劃組織柔性要求較高[1]。

當(dāng)前關(guān)于混流裝配線方面的研究成果較多，基本概括為兩類，一是考慮某些特定因素的建模研究，如李金霖等[2]建立裝配線人工成本和維護(hù)平衡所需加班成本的混流裝配線多目標(biāo)模型，龔軻等[3]考慮作業(yè)元素之間的兼容性，建立有相同作業(yè)工藝條件或者需要到相同設(shè)備作業(yè)的元素放在同一工作站的模型，吳永明等[4]考慮產(chǎn)品需求變化、裝配工藝及技術(shù)進(jìn)步、設(shè)備更新等動態(tài)變化，建立了實現(xiàn)混流裝配線演進(jìn)平衡模型。第二類為側(cè)重對模型的求解方式方法研究，分為仿真和算法求解，如蔣南云等[5]運(yùn)用Flexsim仿真軟件對混流裝配線進(jìn)行建模仿真求解，韓煜東等[6]設(shè)計了基于自然數(shù)序列和拓?fù)渑判虻母倪M(jìn)遺傳算法。張則強(qiáng)等[7]提出了已知基于優(yōu)先權(quán)的粒子群算法，設(shè)計一種基于模擬退火抽樣機(jī)制的混合粒子群算法。

從現(xiàn)有研究文獻(xiàn)看，雖然混流裝配線平衡問題的研究已趨于成熟，但混流裝配線平衡隨著設(shè)備、市場、技術(shù)的變化演進(jìn)，并不能對混流生產(chǎn)系統(tǒng)組織問題有完美的解決，必須考慮到混流裝配線平衡以外的其他因素，本文考慮如何在滿足客戶和市場要求的基礎(chǔ)上，兼顧裝配線平衡和物料平準(zhǔn)化的要求，合理制定車間生產(chǎn)計劃，建立混流裝配線平衡與物料配送雙問題優(yōu)化模型，設(shè)計了基于生態(tài)策略的NSGA-II算法，該算法提出了生態(tài)種群的捕獲競爭，定義了環(huán)境變化時種群采取生態(tài)策略對環(huán)境進(jìn)行突變，在進(jìn)化過程中有效地增加和控制種群的多樣性，最后通過實例驗證算法和模型的有效性。

1 模型構(gòu)建

問題描述：混流裝配線有S個工作站完成M種產(chǎn)品的裝配作業(yè)，這些產(chǎn)品裝配結(jié)構(gòu)類似、工藝相近，每種產(chǎn)品包含工序N，qa為第a種產(chǎn)品所占需求產(chǎn)品的比例，qb為第b種產(chǎn)品所占總需求產(chǎn)品的比例，tmk表示第m種產(chǎn)品k道工序的作業(yè)時間，Gia為第a種產(chǎn)品第i道工序的物料所需量，Tk表示第k個工作站的裝配時間。

數(shù)學(xué)模型為：

F=min(SI,D,P)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

其中，S表示工作站數(shù)，K表示配送物料的車輛數(shù)，li為配送中心到第i個工作站的距離，xij為決策變量，表示第j輛車配送第i個工作站的物料，若是，xij=1，否則，xij=0，Gi表示工作站i的所需物料，Q表示運(yùn)輸物料的小車最大裝載量，dij為工作站i到工作站j的距離，式(2)為第一個目標(biāo)函數(shù)，是使得各工作站中產(chǎn)品的平均單件作業(yè)時間的均方差最小，即各工作站的加權(quán)平均負(fù)荷均衡；式(3)表示車輛運(yùn)輸?shù)淖疃搪窂?，?4)表示最小車輛利用率最大，式(5)每個物料點都能得到配送且只能由一輛車完成，式(6)為每輛車配送路線上物料和不超載，式(7)表示每輛車都從配送中心出發(fā)，式(8)表示每輛車配送完后返回配送中心。約束條件(9)指出變量下標(biāo)i，j的取值范圍。

2 算法設(shè)計

2.1 基本算法

對于多目標(biāo)優(yōu)化問題的求解，一般是將多目標(biāo)轉(zhuǎn)化為單目標(biāo)或者采用多目標(biāo)進(jìn)化算法進(jìn)行求解，但是多目標(biāo)轉(zhuǎn)化單目標(biāo)有一定的缺點：可能造成所求解為非可行解，NSGA-II[8]是目前優(yōu)化效果不錯的一種元啟發(fā)式多目標(biāo)智能算法，通過快速非支配排序，可以使算法復(fù)雜度降低，能加快算法的運(yùn)行，同時通過采用精英策略，在進(jìn)化過程中，父代的優(yōu)秀個體可以保留到子代中，不但能提升種群的多樣性，而且優(yōu)秀個體的遺傳使得算法結(jié)果的精確性得到優(yōu)化，最后擁擠度和擁擠度比較算子，對pareto曲面的均勻性大大提高。但NSGA-II存在側(cè)重于全局的廣域搜索，局域搜索深度較差的缺點，本文在保留原有精髓：精英保留策略、快速非支配排序合擁擠度比較算子情況下引進(jìn)生態(tài)策略對算法局域搜索進(jìn)行改進(jìn)。

2.2 編碼設(shè)計

傳統(tǒng)的二進(jìn)制編碼對連續(xù)裝配線問題的求解比較復(fù)雜，對運(yùn)算速度也有一定的影響，尤其在搜索空間較大時尤顯緩慢，本文采用由(0～1)的隨機(jī)數(shù)組成的編碼[9]，編碼及解碼過程：

Step1：每條染色體隨機(jī)生成(0～1)之間的隨機(jī)數(shù)；

Step2：對作業(yè)順序圖進(jìn)行遍歷，找到無緊前的裝配任務(wù)放入集合TS中；

Step3：集合中作業(yè)元素對應(yīng)染色體的隨機(jī)數(shù)，比較隨機(jī)數(shù)的大??；

Step4：排列對應(yīng)隨機(jī)數(shù)大的作業(yè)元素后，去掉已排列的作業(yè)元素，跳轉(zhuǎn)Step3。

某裝配線作業(yè)任務(wù)順序如圖1所示，對應(yīng)的染色體編碼及解碼見表1，排列順序見圖1。

圖1 某裝配線作業(yè)任務(wù)順序圖

編號(任務(wù))1234567對應(yīng)染色體(0～1)數(shù)0.78230.65420.84530.32580.69420.75320.6985解碼1、TS={1},解碼作業(yè)元素R={1};2、TS={2,3,6},解碼元素R={3};......7、TS={7},解碼元素R={7}。解碼任務(wù)排列1365247

2.3 擁擠度計算以及改進(jìn)

擁擠度是指在群體中的給定個體的周圍個體的密度[10]。結(jié)合裝配線模型，以及NSGA-II計算擁擠度的缺點，擁擠距離采用空間上的歐幾距離，即：

(10)

式中，f1,f2,f3分別為兩個子目標(biāo)函數(shù)。

擁擠度改進(jìn)后計算流程如圖2所示。

圖2 擁擠度計算過程

2.4 生態(tài)進(jìn)化策略

生態(tài)策略(ecological strategy)是自然界的生物在根據(jù)環(huán)境變化后對環(huán)境適應(yīng)時形成的一種進(jìn)化策略。

2.4.1 環(huán)境變化檢測算子

(11)

其中，t表示迭代數(shù)，‖‖表示歐式距離，若s(t,k)≥0.5，則認(rèn)為環(huán)境之間存在了變化，即環(huán)境t與k為非相似環(huán)境。

2.4.2 競爭算子

設(shè)有兩個染色體C1=(x1,x2,....xm)和C2=(x1,x2,...,xm)，如果滿足條件x屬于C1，存在x屬于C2，y>x,則表示染色體中y捕食掉x，否則x捕食掉y，然后混合后得到新的染色體中C3=(l1,l2,...,lm)。

將生態(tài)競爭算子引入后，種群所經(jīng)過的進(jìn)化過程為選擇、交叉、變異、競爭和再選擇，個體與個體之間有內(nèi)部競爭和種群間競爭，增加種群的有效多樣性，而且得到的子個體都是符合非支配的，加速子種群向Pareto前沿進(jìn)化，促進(jìn)整個種群收斂。

2.5 混合變異

混合變異是將高斯變異(gaussian Mutation,GM)、柯西變異(Cauchy Mutation,CM)、Lateral變異(Lateral Mutation，LM)三種變異因子相結(jié)合，根據(jù)各個變異的關(guān)聯(lián)性及多優(yōu)化目標(biāo)的影響程度來選擇變異因子。GM表達(dá)式如下：

(12)

其中，N(0,1)為均值為0，方差為1的正態(tài)分布，sg為變異長度，ωg為[0,fgau(0)]中隨機(jī)數(shù)。

CM基于柯西密度函數(shù)：

(13)

其執(zhí)行過程為：

(14)

其中，εk是柯西隨機(jī)變量，sc為柯西變異步長，ωc為[0,fcau(0)]中隨機(jī)數(shù)。

LM定義為：

(15)

其中,l屬于(1,m)之間,且l≠k,α是(0,1)之間的隨機(jī)數(shù)。

LM可以加快收斂速度，但是易使所有的個體最終收斂局部最優(yōu)解，而GM和CM可以克服這個缺點，避免算法出現(xiàn)局部最優(yōu)。變異過程如圖3所示。

圖3 變異過程

2.6 改進(jìn)算法的求解步驟

基于生態(tài)策略的改進(jìn)NSGA-II具體過程如下：

(1)種群初始化及參數(shù)設(shè)置：設(shè)定種群數(shù)pop，迭代次數(shù)Gen。

(2) 0～1編碼對應(yīng)非支配排序并計算擁擠度。

(3)選擇算子，根據(jù)正態(tài)隨機(jī)數(shù)決定交叉還是混合變異，進(jìn)行環(huán)境檢測判斷是否進(jìn)行競爭，若需競爭根據(jù)捕食原則替換染色體，合并種群非支配排序后得到N個體，并與上一代進(jìn)行環(huán)境檢測進(jìn)行競爭。

(4)重新選取擁擠度大的個體。編解碼對應(yīng)具體作業(yè)任務(wù)。

(5)判斷父代種群是否滿足終止條件，若是，結(jié)束，否則，跳轉(zhuǎn)到(3)。

流程圖如圖4所示。

圖4 基于生態(tài)策略的NSGA-II算法流程圖

3 實例分析

某混流裝配車間有1個物料配送中心，載重為Q=11的物料車輛若干，現(xiàn)已知物料配送中心與各工作站的距離見表和各工序的作業(yè)時間及物料需求量見表2和表3，兩種產(chǎn)品的比例為qa=0.42，qb=0.58，設(shè)計節(jié)拍為CT=94。

圖5 裝配線作業(yè)任務(wù)順序圖

工序號ta /stb /s工序號ta /stb /s1020141302777715555537373161920490821737058888189497662019131373602009080202120209666622474710252523928211555524413712777125500135959

表4 工作站距離(m)

算法參數(shù)如下：種群規(guī)模pop=100,交叉概率Pc=0.9,變異概率Pm=0.1，進(jìn)化100代最后得到若干非劣解，求解結(jié)果如圖6所示。

圖6 Pareto解

算法工作站數(shù)站間均衡系數(shù)物料配送路徑和最小車輛裝載率車輛平均裝載率NSGA-II方案11413.14246550.33%79.46%方案21511.58647942.87%65.253%改進(jìn)NSGA-II方案11411.16941640.18%88.32%方案21412.499842162.18%89.54%

圖7 方案1工序條形圖

圖6灰色星型點為迭代100次后都能得到Pareto最優(yōu)解，表5為選取NSGA-II改進(jìn)與沒改進(jìn)時選取的兩個解，從表看出相對原算法有一定的優(yōu)勢且改進(jìn)后收斂性更好，從Pareto解可以看出解對站間均衡系數(shù)、物料配送路徑及車輛裝載率的選擇要基于具體實際生產(chǎn)在某目標(biāo)的選取，對企業(yè)生產(chǎn)具有一定的參考意義。

4 結(jié)論

在分析混流裝配線平衡問題和物料路徑配送問題后，本文提出混流裝配線平衡和物料配送綜合模型，該模型對混流裝配線的第一類問題進(jìn)行優(yōu)化的同時，使配送物料路徑得到優(yōu)化，克服制造系統(tǒng)裝配與物料配送出現(xiàn)不配套等問題。根據(jù)生態(tài)策略設(shè)計了一種基于生態(tài)策略的改進(jìn)NSGA-II，算法重點采用生態(tài)策略去應(yīng)對環(huán)境的變化，對個體進(jìn)行競爭防止陷入“早熟”，通過實例求解表明，改進(jìn)后的算法相對標(biāo)準(zhǔn)算法具有更佳的收斂能力及保持多樣性能力，全局尋優(yōu)能力也有所提高，效率與可靠性進(jìn)一步提升，對于裝配線平衡問題具有較好的求解效果.如何更好地評價該算法的性能，這將是下一步要做的工作。