張 瑋，李艷軍 ，江天玥

(1.南京航空航天大學(xué)民航學(xué)院，江蘇 南京 211100)(2.南京理工大學(xué)經(jīng)濟管理學(xué)院，江蘇 南京 210094)

近年來，我國民機裝配技術(shù)水平逐步提高[1]?，F(xiàn)代飛機裝配管控過程都具有周期長、不確定性高、組織協(xié)調(diào)難度大的特點[2]，而民機相較于軍機裝配過程更加復(fù)雜，數(shù)字化技術(shù)的進步帶動了民機裝配方式的進步。在優(yōu)化方法方面，遺傳算法具有良好的局部搜索尋優(yōu)能力和較強的魯棒性，但也有容易陷入局部最優(yōu)的缺點；模擬退火算法以一定的概率接受較差值，從而跳出局部最優(yōu)，但其效率低，對初值有較強的依賴性。目前針對民機裝配現(xiàn)場調(diào)度問題的研究比較少，且多為單目標優(yōu)化，針對民機裝配現(xiàn)場管控的編碼方式和染色體交叉變異方式不夠完善。本文針對民機數(shù)字化裝配現(xiàn)場管控的實際需求，將標準的遺傳算法進行改進，并加入退火過程，設(shè)計出改進的遺傳與模擬退火混合算法，并對多目標民機裝配生產(chǎn)調(diào)度模型進行優(yōu)化計算。

1 需求分析

民機數(shù)字化裝配生產(chǎn)計劃的制定需要考慮以下幾個特點：多項目并行、多約束條件[3]、多調(diào)度目標[4]、高度離散性[5]。

2 模型建立

2.1 問題描述

2.2 約束條件

假設(shè)：1)不同的工件之間不存在緊前約束，同一工件的工序之間存在緊前約束；2)一架工裝在同一時刻僅可裝配一道工序；3)不可打斷一道工序的裝配；4)忽略工件在工裝上的裝卸時間；5)物料資源充足。約束條件量化如下：

Sjk+xijk×tijk≤Cjk,i=1,2,…,m;j=1,2,…,n;k=1,2,…,kj

(1)

Cjk≤Sj(k+1),j=1,2,…,n;k=1,2,…,kj-1

(2)

Cjk≤Cmax,j=1,2,…,n

(3)

Sjk+tjk≤Shl+W(1-yijkhl),i=1,2,…,m;j,h=1,2,…,n;k=1,2,…,kj;l=1,2,…,kh

(4)

rj≤Sijk≤dj-tijk,i=1,2,…,m;j=1,2,…,n;k=1,2,…,kj

(5)

2.3 目標函數(shù)

1)工裝最大作業(yè)負荷f1最小,即：

(6)

2)最大完工時間f2最小,即：

(7)

對上述目標函數(shù)加權(quán)得到目標函數(shù)gx，即：

gx=w1f1+w2f2

(8)

式中：w1,w2>0,w1+w2=1。

3 混合算法的設(shè)計與實現(xiàn)

3.1 改進遺傳算法

1)編碼與解碼。根據(jù)民機數(shù)字化裝配現(xiàn)場的實際情況，采用雙層編碼方法。一層編碼代表工序的排序，另一層編碼代表選擇的工裝編號，且上下兩層編碼長度相等。編碼方式如圖1所示。

圖1 編碼圖示

以某民機裝配企業(yè)的生產(chǎn)現(xiàn)場為例，其裝配作業(yè)時間表見表1。

表1 裝配作業(yè)時間表

由此得到工裝與工序的關(guān)聯(lián)矩陣J0和時間矩陣T0：

(9)

(10)

解碼過程是，按編碼規(guī)則將基因轉(zhuǎn)換為工序Ojk，根據(jù)J0和T0求出該工序?qū)?yīng)的工裝和裝配時長，按模型約束條件規(guī)則將工序工裝組合排序，形成生產(chǎn)計劃。

2)適應(yīng)度函數(shù)設(shè)計。本文選擇下界構(gòu)造法[7]構(gòu)造適應(yīng)度函數(shù)，適應(yīng)度函數(shù)Fit(x)為：

(11)

式中：c為目標函數(shù)界限保守估計值。

3)改進交叉算子。工序之間存在工藝約束，為保證交叉后種群不出現(xiàn)非法個體以及計算過程的可控性，交叉方式如下：隨機選擇第n個工件，保持該工件所有工序的基因不變，其他工序的基因按順序交叉。例如：隨機產(chǎn)生一個不大于工裝總數(shù)的整數(shù)，假設(shè)是1，工件1的所有工序基因保留，工件2和3的工序基因依次交換，得到子代染色體，如圖2所示。由于工序和工裝存在對應(yīng)關(guān)系，為保證工裝交叉后不出現(xiàn)非法解，工裝交叉操作跟隨工序交叉同時進行。

圖2 工序染色體交叉操作示例

4)改進變異算子。根據(jù)編碼解碼規(guī)則，為避免種群中存在大量重復(fù)個體，工序變異時選取一個基因，將其插入該基因位置與前一個相同編碼之間的任意位置，后移其他基因。例如：隨機生成一個不大于染色體長度的整數(shù)5，父代基因位置5代表工序O22，將其變異到O21后面的任意位置3，得到子代染色體，如圖3所示。

圖3 工序染色體變異操作示例

工裝染色體變異采取單點變異方式，在該道工序可選擇的其他工裝里隨機選取一個替換。例如：隨機生成一個不大于染色體長度的整數(shù)2，染色體上第二位的基因為1，即工裝M1，該工序可選擇的工裝有[M1,M2,M3]，隨機選擇除M1外的工裝，例如M2，則該位基因變?yōu)?。變異過程如圖4所示。

圖4 工裝染色體變異操作示例

5)改進選擇算子。將比例選擇與最佳個體保留結(jié)合，形成復(fù)合種群選擇方法，具體方法是：在0～1之間產(chǎn)生一個隨機數(shù)random，即若狀態(tài)a滿足：

(12)

則選擇狀態(tài)a進行復(fù)制。式中：sizepop為種群大小，fb為個體的適應(yīng)度值。

3.2 改進的遺傳與模擬退火混合算法(GASA)設(shè)計

與遺傳算法尋優(yōu)的方式不同，模擬退火算法根據(jù)Metorpolis接受準則[8]在計算過程中以概率P接受比較差的解，可使計算過程跳出局部收斂，實現(xiàn)全局尋優(yōu)。Metorpolis接受準則：狀態(tài)從A變?yōu)锽時，對應(yīng)的系統(tǒng)能量由Fit(A)變?yōu)镕it(B)，此時系統(tǒng)從A到B能夠接受的概率P為：

(13)

混合算法流程：1)設(shè)置初始參數(shù)。2)編碼，確定目標函數(shù)。3)生成初始種群，計算個體適應(yīng)度Fit。4)初始化遺傳迭代計數(shù)變量z=0。5)進行初始種群的交叉、變異、選擇操作，產(chǎn)生新種群，并計算新種群中每個個體適應(yīng)度Fit'。6)計算新個體與父代個體的適應(yīng)度差值ΔE=Fit'-Fit，若ΔE≥0，則接受新個體，淘汰父代個體，若ΔE<0，則以概率P接受新個體。7)判斷z是否達到最大迭代次數(shù)，若是則轉(zhuǎn)到步驟8；否則令z=z+1，并轉(zhuǎn)向4)。8)判斷是否滿足算法終止條件，即當前溫度Tk是否小于終止溫度Tend，若是則終止算法得到全局最優(yōu)解，否則執(zhí)行退火降溫操作，即Tk+1=qTk，同時令k=k+1，并轉(zhuǎn)到4)，其中q為冷卻系數(shù)。

4 仿真結(jié)果與分析

以某企業(yè)飛機功能系統(tǒng)裝配作業(yè)為例，進行仿真計算，其裝配作業(yè)調(diào)度表見表2。

表2 裝配作業(yè)調(diào)度表

參數(shù)初始化：sizepop=100，迭代次數(shù)為100，工裝交叉概率Pc1=0.9，工裝變異概率Pm1=0.01，工序交叉概率Pc2=0.6，工序變異概率Pm2=0.01，c=80，q=0.9，初始溫度T0=100，Tend=1，w1=0.4，w2=0.6，連續(xù)進行20次仿真實驗，最優(yōu)解調(diào)度方案甘特圖如圖5所示。

圖5 飛機功能系統(tǒng)安裝生產(chǎn)計劃優(yōu)化方案甘特圖

優(yōu)化后的總裝配時長為26 h，根據(jù)實地調(diào)研，該企業(yè)飛機功能系統(tǒng)安裝約需要8～10個工作日，所以本文的優(yōu)化方法是可行的；工裝作業(yè)負荷為3，處于比較平衡的狀態(tài)，改善了企業(yè)生產(chǎn)閑忙不均的問題；20次實驗中的兩次算法尋優(yōu)曲線如圖6所示，平均收斂代數(shù)約為退火過程的15代左右，且20次試驗中每次計算結(jié)果差別不大，比較穩(wěn)定。另外，改變算法的參數(shù)也基本不會影響計算結(jié)果。

圖6 算法尋優(yōu)曲線

運用標準遺傳算法和本文的改進遺傳算法對相同的模型分別計算20次，與本文的改進GASA混合算法相比較，3種算法的優(yōu)化效果與計算能力對比見表3。通過對比可以看出，改進GASA優(yōu)化效果更好，計算速度更快，且在20次實驗中，改進GASA計算結(jié)果比另外兩種方法更穩(wěn)定。

表3 3種算法的計算效果對比

5 結(jié)束語

本文將多個目標進行歸一化處理，構(gòu)建多約束多目標的民機裝配生產(chǎn)調(diào)度模型；針對民機數(shù)字化裝配現(xiàn)場管控的實際情況設(shè)計出改進的遺傳與模擬退火混合算法，以某民機裝配企業(yè)為例，進行仿真與求解，實驗結(jié)果顯示，改進的GASA混合算法優(yōu)化效果較好、計算速度較快，且計算結(jié)果更加穩(wěn)定，對民機數(shù)字化裝配現(xiàn)場管控中的生產(chǎn)計劃優(yōu)化具有一定的指導(dǎo)意義。