基于改進離散差分進化算法的多目標第Ⅱ類裝配線平衡問題研究

張海軍，閆　瓊，張國輝，劉元朋

（鄭州航空工業管理學院，河南　鄭州　450046）

基于改進離散差分進化算法的多目標第Ⅱ類裝配線平衡問題研究

張海軍，閆瓊，張國輝，劉元朋

（鄭州航空工業管理學院，河南鄭州450046）

為求解多目標第Ⅱ類裝配線平衡問題（MOALBP-Ⅱ），提出了一種改進的離散性差分進化算法—DDEA。采用生產節拍和工位載荷波動構建一個自適應的多目標優化函數；開發了適度貪心算法分配作業元素，約束貪婪幅度；采用了基于優先權的編碼方法使得個體解碼后總滿足裝配線約束關系；并提出一種新型的雙變異策略和交叉算子。最后，采用標準問題集測試分析，結果顯示該算法在求解大規模MOALBP-Ⅱ的質量最優。

第Ⅱ類裝配線平衡問題；多目標優化；差分進化算法；離散

1　引言

裝配線平衡問題（Assembly Line Balancing Problem，ALBP）是工廠建設規劃中要解決的首要問題，其優化改進能給生產帶來顯著的、長期的收益。ALBP是指在不違背約束條件（如產品工藝規劃）的前提下，將組裝任務的各作業元素合理分配至一系列工位上，使各個工位的總作業負荷趨于均衡，并使得一個或多個目標函數最優化［1］。多目標第Ⅱ類裝配線平衡問題（Multi-objective Assembly Line Balancing Problem，MOALBP-Ⅱ）是指在滿足產品優先關系等約束下，給定工位數的情況下如何向各工位分配作業，以生產節拍及其它目標為優化對象的一種ALBP，實質上是組合優化問題，也是一類典型的NP-hard問題［2］。

學者對相關的第Ⅱ類裝配線平衡問題進行了研究，但較少涉及MOALBP-Ⅱ的研究。例如：劉儼后等建立了隨機作業時間的單目標ALBP-Ⅱ模型，以完工率節拍為優化指標，設計了一種雙染色體遺傳算法（Genetic Algorithm，GA）對模型進行求解［3］。李明等針對大規模多工位裝配線平衡問題，提出一種基于規則組合的求解算法，將操作的選擇規則和分配規則進行組合，求解單目標的ALBP-Ⅰ和ALBP-Ⅱ［4］。李英德等提出了一種改進的蟻群算法，兼顧最小節拍和負荷均衡兩個目標求解MOALBP-Ⅱ［5］。Zacharia等應用GA求解具有模糊作業時間的單目標ALBP-Ⅱ［6］。Triki等提出一個多目標GA優化節拍時間和時間成本的MOALBP-Ⅱ［7］。由于經濟全球化市場競爭加劇，ALBP中影響因素逐漸多元化，同時優化多個目標導致MOALBP-Ⅱ建模多樣性和求解難度增加，優化算法求解效率和求解質量方面有待進一步提升。

差分進化算法（Differential Evolutionary Algorithm，DEA）是一種基于群體差異的隨機全局搜索啟發式算法［8］，由Storn和Price于1995年提出，已在許多單目標的、連續型的優化領域得到廣泛研究和應用?；綝EA不適合多目標離散優化問題的求解，而現實中的MOALBP-Ⅱ則是典型的多目標離散優化問題。雖然部分學者研究了離散型的DEA，采用的方法大多數需要連續空間與離散空間相互轉換，此方法雖然簡單，但轉換和差分進化過程可能會丟失重要的啟發信息［9］。本文設計了一種新型的離散DEA—DDEA，可直接處理MOALBP-Ⅱ中的離散變量。

2　多目標第Ⅱ類裝配線平衡問題

為對MOALBP-Ⅱ進行數學建模，在不脫離實際情況下做以下假設：

（1）裝配線布局是串行的，沒有并行的工位。

（2）每個作業的時間都是明確已知的，與工位無關。

（3）工位不限制作業種類和數量。

（4）除裝配工藝路線約束外沒有其他約束關系。

（5）優先權圖中每個作業都是最小單元，不可再分解。

（6）作業在兩個工位之間移動的時間忽略不計。

本文使用的符號規定如下：

CT：生產節拍；

I：作業數量；

vi，k：作業i是否被安排至工位k的決策變量；如果是，則vi，k=1，否則vi，k=0；

K：給定的工位數；

Sk：安排至工位k的作業集；

ti：作業i的執行時間；

IdleTk=CT-T（Sk）：工位k的空閑時間；

因此，建立MOALBP-Ⅱ的數學模型如下：

式（1）表示最小化生產節拍，式（2）表示最小化平均載荷波動，式（3）表示每個工作僅被安排一次，式（4）表示所有工作都須安排完畢，式（5）表示每個工位的工作時間不能超過節拍時間，式（6）表示工作安排順序嚴格遵守工藝路線優先級。

3　離散差分進化算法（DDEA）

3.1個體的編碼與解碼

為DDEA能在離散空間中尋優，合適的個體編碼和解碼方法至關重要。本文基于面向任務的表達機制，采用基于優先權的個體編碼方法［10］，在本文中將其稱為基于優先權的染色體（Priority-Based Chromosome，PBC）。每個PBC的長度等于裝配線作業數量I，其維度稱為基因，代表工作i的優先權 pi，且取值范圍是［0，I-1］的整數。

經過以上個體編碼后，需要將工作安排至各個工位，即個體解碼。首先根據基于優先權的排序算法生成一個FTS，使用傳統的貪心算法可能獲得最小生產節拍的分配方案，但可能會導致最后一個分配的工作站空閑時間較大［11］，不能滿足多目標優化。本文引入適度原則，約束貪婪幅度以避免過度貪婪，適度貪心算法具體方法如下：

步驟1：根據FTS中作業順序，將作業FTS［i］分配至第k個工位，直到若增加一個作業該工位的且若增加兩個作業該工位的為止；

步驟3：若FTS中有未被分配的作業，則新開一個工位k←k+1轉到步驟1，否則結束。

3.2變異操作

根據上一節編碼的方法得到十進制整數形式的個體向量，但經過傳統的變異操作后會變成實數形式，為此本文設計個體向量轉換機制，具體方法如下（如圖1所示）：

步驟1：將整數形式PBC每個維度值轉換為二進制；

步驟2：計算PBC中維度值最大的二進制位數MaxN；

步驟3：補充維度二進制位數不夠的直至MaxN位數。

圖1　個體向量轉換

本文采用自適應雙變異策略，平衡種群收斂速度和求解質量之間的矛盾?！癉E/rand/1/bin”變異策略有利于保持種群多樣性，但收斂速度較慢；“DE/best/2/bin”有利于提高收斂速度，但易陷于局部最優。為此，本文定義了種群的個體位置密度（Diversity of Individual Position，DIP）函數，表示種群中個體與當前最優個體之間的平均Euclidean距離：

如式（8）所示，如果DIP≤ε（ε∶密度闕值），離散差分進化算法采用“DE/rand/1/bin”作為變異策略，否則采用“DE/best/2/bin”。

3.3交叉操作

交叉操作是從試驗個體或目標個體獲得有用的信息，為了較好地保留信息元素以及目標個體良好的結構，本文設計以下交叉方法：

（3）除了以上兩種情況，根據式（9）進行交叉操作方式。

圖2　交叉操作（CR=0.30）

3.4選擇操作

基本DEA的選擇操作采用貪婪方式選擇“相對優化”個體，但該機制有較大局限性，容易拋棄一些次優信息，種群的整體質量可能得不到提高。本文采用“精英保留（elite-preserving）”選擇策略［12］，將目標個體和試驗個體合并一個種群，根據個體適應度排序，保留該種群的前50%，隨機產生剩下的50%個體作為新一代群體。

本文考慮的是MOALBP-Ⅱ，目標函數包括生產線生產節拍CT和工位載荷波動MADW。傳統多目標優化問題解決方法是設置各個目標權重從而轉化為單目標優化問題，但如何設置合理的權重值較為困難。本文采用自適應權重方法計算個體的適應度，公式如下：

其中 fq表示第q個目標函數，根據式（1）、（2），即表示第q個目標函數在當前種群中的最大值，同理表示第q個目標函數在當前種群中的最小值。

4　算法測試與分析

4.1測試參數設置

從文獻中選擇一系列標準Benchmarks問題集［13］進行仿真測試，包括4個中小規模的MOALBP-Ⅱ問題集（Buxey，Sawyer，Gunther，Kilbridge）的35個案例和3個大中規模問題集（Tonge，Arcus83，Arcus111）的59個案例。兩個版本的基本差分進化算法（BDEA1，BDEA2）和兩個版本的離散型差分進化算法（DDEA1，DDEA2）的實驗結果進行對比。

所有的算法都采用C#高級編程語言編寫，運行在CPU為AMD 2.29GHz，內存為3GB的個人計算機上。通過大量仿真測試，建議參數設置如下：種群規模N=200，變異概率F=0.90，交叉概率CR=0.90，密度闕值ε=0.30，每種算法獨立運行10次取最優值。算法終止的標準是：（1）發現MOALBP-Ⅱ的最好優化結果：找到理論最優節拍CT*以及MADW=0%；（2）達到最大的迭代次數MaxGen=100×I。

4.2測試結果分析

根據以上參數設置，算法測試結果見表1，其中各性能參數定義如下：

（3）MADW：平均工作站載荷波動，由式（2）計算；

（4）CORA=（n_iter/MaxGen）×100：收斂效率，其中n_iter表示算法獲得最優節拍時的迭代次數。

表1　算法測試結果

從表1可以看出，在ARDC性能方面，對于中小規模的MOALBP-Ⅱ問題，BDEA2和DDEA2不相上下，其中BDEA2表現最好（4個問題中3個最優：Buxey：1.57%，Gunther：2.97%，Kilbridge：1.54%），BDEA1和DDEA1表現最差，特別是Kilbridge問題ARDC分別是5.47%和4.57%。對于中大規模的MOALBP-Ⅱ問題，本文提出的DDEA2表現出較大的優勢（Tonge：2.31%，Arcus83：3.14%，Arcus111：4.05%），BDEA1表現最差（Tonge：8.99%，Arcus83：6.27%，Arcus111：9.85%），其次是BDEA2（Tonge：5.82%，Arcus111：7.27%），說明DDEA相對于BDEA（即連續型的差分進化）在求解大規模的離散優化問題時平均求解精度上具有較大優勢。在MRDC性能方面，DDEA2在Sawyer、Tonge、Arcus111問題上獲得最優值，BDEA2在Buxey、Kilbridge、Arcus83問題上獲得最優值，說明本文采用的適度貪心分配作業法、自適應權重法和雙變異策略整體起到明顯的改進作用。在CORA性能方面，DDEA1、BDEA1分別優于對應的DDEA2、BDEA2，說明雙變異策略能起到一定的防陷于局部最優的效果。另隨著問題規模的擴大，不同算法的CORA數值不同程度上增大，說明問題求解空間對所有算法有影響。在MADW性能方面，采用了本文提出的適度貪心法和雙變異策略的BDEA2和DDEA2能獲得較優的結果，特別是Arcus111問題上分別為165.32%和108.74%，遠低于BDEA1和DDEA1的結果（304.15%和230.15%），驗證了DDEA2求解多目標優化問題的有效性。

從圖3可看出，BDEA1和BDEA2隨著MOALBP-Ⅱ規模的增加，ARDC有明顯惡化的趨勢，特別是BDEA1；而DDEA1和DDEA2的趨勢比較平緩。從圖4可看出，BDEA2和DDEA2在MADW性能方面優于BDEA1和DDEA1。

圖3　測試案例最優方案的ARDC

圖4　測試案例最優方案的MADW

圖5是針對大規模MOALBP-Ⅱ問題集Arcus83（K=5，CT*=15142）案例進行的測試結果。從圖5（a）可看出，迭代次數從0到500時DDEA1和DDEA2收斂速度較快，BDEA1較早地陷于局部最優而 BDEA2和DDEA2在迭代次數2 500～3 500之間還有跳出局部最優的能力。從圖5（b）可看出，DDEA2收斂結果最優（MADW=3.41%），其次是BDEA2（MADW=5.17%），說明本文提出的DDEA2求解質量最優。

5　結語

本文針對MOALBP-Ⅱ多目標離散型優化問題，提出一種改進的離散型DEA（DDEA）。該算法能直接處理MOALBP-Ⅱ中的離散變量。開發了適度貪心算法用于分配作業，設計了自適應雙變異策略，能平衡算法收斂速度和搜索精度；設計了新型交叉操作機制，保證交叉后的PBC仍是離散的和具有良性的結構；選擇操作采用“精英保留”策略能保留真正的質優個體，并不失種群的隨機性。最后利用標準的Benchmarks問題集，將DDEA與BDEA對比測試，結果表明DDEA在解決大規模的MOALBP-Ⅱ問題上求解質量最優。下一步的研究方向將考慮利用DDEA求解多目標優化的ALBP-Ⅰ問題、混流型ALBP-Ⅱ問題等以及如何優化DDEA控制參數。

［1］Salveson M E.The assembly line balancing problem［J］.Journal of Industrial Engineering，1955，（6）∶18-25.

［2］Scholl A，Becker C.State-of-the-art exact and heuristic solution procedures for simple assembly line balancing［J］.European Journal of Operational Research，2006，168（3）∶666-693.

［3］劉儼后，左敦穩，張丹.隨機作業時間的裝配線平衡問題［J］.計算機集成制造系統，2014，20（6）∶1 372-1 378.

［4］李明，李珊，夏緒輝，等.大規模多工位裝配線平衡問題的規則組合算法［J］.計算機集成制造系統，2013，19（11）∶2 780-2 787.

［5］李英德，魯建夏.求解第二類裝配線平衡問題的改進蟻群算法［J］.計算機集成制造系統，2012，18（4）∶754-760.

［6］Zacharia P Th，Nearchou A C.Multi-objective fuzzy assembly line balancing using genetic algorithms［J］.Journal of Intelligent Manufacturing，2012，23∶615-627.

［7］Triki H，Mellouli A，Masmoudi F.A multi-objective genetic algorithm for assembly line resource assignment and balancing problem of type 2（ALRABP-2）［J］.Journal of Intelligent Manufacturing，2014∶1-15.

［8］Storn R，Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization，1997，（11）∶341-354.

［9］Datta D，Figueira J R.A real-integer-discrete-coded differential evolution［J］.Applied Soft Computing，2013，（13）∶3 884-3 893.

［10］Gen M，Cheng R.Genetic algorithms and engineering optimization［M］.New York∶Wiley，2000.

［11］Al-Hawari T，Ali M，Al-Araidah O.Development of a genetic algorithm for multi-objective assembly line balancing using multiple assignment approach［J］.International Journal of Advanced Manufacturing Technology，2015，77（5-8）∶1 419-1 432.

［12］Deb K，Agarwal S，Pratap A，et al.A fast and elitist multi-objective genetic algorithm∶NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）∶182-197.

［13］Homepage for assembly line optimization research［EB/OL］. http∶//www.wiwi.uni-jena.de/entscheidung/alb/albdata.htm，2016-02-20.

Study on MOALBP-II Based on Modified Discrete Differential Evolution Algorithm

Zhang Haijun，Yan Qiong，Zhang Guohui，Liu Yuanpeng
（Zhengzhou University of Aeronautics， Zhengzhou 450046， China）

In this paper， in order to solve the multi-objective assembly line balancing problem （MOALBP-II）， we proposed a modifieddiscrete differential evolution algorithm. First， according to production beat and station load fluctuation， we built an adaptive multi-objectiveoptimization function， developed a moderate greedy algorithm to schedule the activity elements， applied the priority-based encoding methodto ensure the compliance with the constraint of the assembly line， and proposed an innovative duo-mutation strategy and crossover operator.At the end， we applied the method to a standard problem set， which verified its effectiveness.

MOALBP-II； multi-objective optimization； differential evolution algorithm； discrete

圖5　Arcus83（K=5，CT*=15 142）案例的MADW測試結果

TH186；TP18

A

1005-152X（2016）03-0103-06

10.3969/j.issn.1005-152X.2016.03.023

2016-02-14

航空科學基金（2015ZG55018）；河南省科技廳軟科學研究計劃（132400410782）；河南省教育廳科學技術研究重點項目（15A630050）；鄭州市科技發展計劃（20140583）；校青年科研基金項目（2016053001）

張海軍（1983-），男，博士，講師，研究方向：智能算法、資源優化。