基于改進(jìn)離散差分進(jìn)化算法的多目標(biāo)第Ⅱ類裝配線平衡問(wèn)題研究

張海軍，閆　瓊，張國(guó)輝，劉元朋

（鄭州航空工業(yè)管理學(xué)院，河南　鄭州　450046）

基于改進(jìn)離散差分進(jìn)化算法的多目標(biāo)第Ⅱ類裝配線平衡問(wèn)題研究

張海軍，閆瓊，張國(guó)輝，劉元朋

（鄭州航空工業(yè)管理學(xué)院，河南鄭州450046）

為求解多目標(biāo)第Ⅱ類裝配線平衡問(wèn)題（MOALBP-Ⅱ），提出了一種改進(jìn)的離散性差分進(jìn)化算法—DDEA。采用生產(chǎn)節(jié)拍和工位載荷波動(dòng)構(gòu)建一個(gè)自適應(yīng)的多目標(biāo)優(yōu)化函數(shù)；開(kāi)發(fā)了適度貪心算法分配作業(yè)元素，約束貪婪幅度；采用了基于優(yōu)先權(quán)的編碼方法使得個(gè)體解碼后總滿足裝配線約束關(guān)系；并提出一種新型的雙變異策略和交叉算子。最后，采用標(biāo)準(zhǔn)問(wèn)題集測(cè)試分析，結(jié)果顯示該算法在求解大規(guī)模MOALBP-Ⅱ的質(zhì)量最優(yōu)。

第Ⅱ類裝配線平衡問(wèn)題；多目標(biāo)優(yōu)化；差分進(jìn)化算法；離散

1　引言

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

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

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

2　多目標(biāo)第Ⅱ類裝配線平衡問(wèn)題

為對(duì)MOALBP-Ⅱ進(jìn)行數(shù)學(xué)建模，在不脫離實(shí)際情況下做以下假設(shè)：

（1）裝配線布局是串行的，沒(méi)有并行的工位。

（2）每個(gè)作業(yè)的時(shí)間都是明確已知的，與工位無(wú)關(guān)。

（3）工位不限制作業(yè)種類和數(shù)量。

（4）除裝配工藝路線約束外沒(méi)有其他約束關(guān)系。

（5）優(yōu)先權(quán)圖中每個(gè)作業(yè)都是最小單元，不可再分解。

（6）作業(yè)在兩個(gè)工位之間移動(dòng)的時(shí)間忽略不計(jì)。

本文使用的符號(hào)規(guī)定如下：

CT：生產(chǎn)節(jié)拍；

I：作業(yè)數(shù)量；

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

K：給定的工位數(shù)；

Sk：安排至工位k的作業(yè)集；

ti：作業(yè)i的執(zhí)行時(shí)間；

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

因此，建立MOALBP-Ⅱ的數(shù)學(xué)模型如下：

式（1）表示最小化生產(chǎn)節(jié)拍，式（2）表示最小化平均載荷波動(dòng)，式（3）表示每個(gè)工作僅被安排一次，式（4）表示所有工作都須安排完畢，式（5）表示每個(gè)工位的工作時(shí)間不能超過(guò)節(jié)拍時(shí)間，式（6）表示工作安排順序嚴(yán)格遵守工藝路線優(yōu)先級(jí)。

3　離散差分進(jìn)化算法（DDEA）

3.1個(gè)體的編碼與解碼

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

經(jīng)過(guò)以上個(gè)體編碼后，需要將工作安排至各個(gè)工位，即個(gè)體解碼。首先根據(jù)基于優(yōu)先權(quán)的排序算法生成一個(gè)FTS，使用傳統(tǒng)的貪心算法可能獲得最小生產(chǎn)節(jié)拍的分配方案，但可能會(huì)導(dǎo)致最后一個(gè)分配的工作站空閑時(shí)間較大［11］，不能滿足多目標(biāo)優(yōu)化。本文引入適度原則，約束貪婪幅度以避免過(guò)度貪婪，適度貪心算法具體方法如下：

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

步驟3：若FTS中有未被分配的作業(yè)，則新開(kāi)一個(gè)工位k←k+1轉(zhuǎn)到步驟1，否則結(jié)束。

3.2變異操作

根據(jù)上一節(jié)編碼的方法得到十進(jìn)制整數(shù)形式的個(gè)體向量，但經(jīng)過(guò)傳統(tǒng)的變異操作后會(huì)變成實(shí)數(shù)形式，為此本文設(shè)計(jì)個(gè)體向量轉(zhuǎn)換機(jī)制，具體方法如下（如圖1所示）：

步驟1：將整數(shù)形式PBC每個(gè)維度值轉(zhuǎn)換為二進(jìn)制；

步驟2：計(jì)算PBC中維度值最大的二進(jìn)制位數(shù)MaxN；

步驟3：補(bǔ)充維度二進(jìn)制位數(shù)不夠的直至MaxN位數(shù)。

圖1　個(gè)體向量轉(zhuǎn)換

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

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

3.3交叉操作

交叉操作是從試驗(yàn)個(gè)體或目標(biāo)個(gè)體獲得有用的信息，為了較好地保留信息元素以及目標(biāo)個(gè)體良好的結(jié)構(gòu)，本文設(shè)計(jì)以下交叉方法：

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

圖2　交叉操作（CR=0.30）

3.4選擇操作

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

本文考慮的是MOALBP-Ⅱ，目標(biāo)函數(shù)包括生產(chǎn)線生產(chǎn)節(jié)拍CT和工位載荷波動(dòng)MADW。傳統(tǒng)多目標(biāo)優(yōu)化問(wèn)題解決方法是設(shè)置各個(gè)目標(biāo)權(quán)重從而轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，但如何設(shè)置合理的權(quán)重值較為困難。本文采用自適應(yīng)權(quán)重方法計(jì)算個(gè)體的適應(yīng)度，公式如下：

其中 fq表示第q個(gè)目標(biāo)函數(shù)，根據(jù)式（1）、（2），即表示第q個(gè)目標(biāo)函數(shù)在當(dāng)前種群中的最大值，同理表示第q個(gè)目標(biāo)函數(shù)在當(dāng)前種群中的最小值。

4　算法測(cè)試與分析

4.1測(cè)試參數(shù)設(shè)置

從文獻(xiàn)中選擇一系列標(biāo)準(zhǔn)Benchmarks問(wèn)題集［13］進(jìn)行仿真測(cè)試，包括4個(gè)中小規(guī)模的MOALBP-Ⅱ問(wèn)題集（Buxey，Sawyer，Gunther，Kilbridge）的35個(gè)案例和3個(gè)大中規(guī)模問(wèn)題集（Tonge，Arcus83，Arcus111）的59個(gè)案例。兩個(gè)版本的基本差分進(jìn)化算法（BDEA1，BDEA2）和兩個(gè)版本的離散型差分進(jìn)化算法（DDEA1，DDEA2）的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。

所有的算法都采用C#高級(jí)編程語(yǔ)言編寫(xiě)，運(yùn)行在CPU為AMD 2.29GHz，內(nèi)存為3GB的個(gè)人計(jì)算機(jī)上。通過(guò)大量仿真測(cè)試，建議參數(shù)設(shè)置如下：種群規(guī)模N=200，變異概率F=0.90，交叉概率CR=0.90，密度闕值ε=0.30，每種算法獨(dú)立運(yùn)行10次取最優(yōu)值。算法終止的標(biāo)準(zhǔn)是：（1）發(fā)現(xiàn)MOALBP-Ⅱ的最好優(yōu)化結(jié)果：找到理論最優(yōu)節(jié)拍CT*以及MADW=0%；（2）達(dá)到最大的迭代次數(shù)MaxGen=100×I。

4.2測(cè)試結(jié)果分析

根據(jù)以上參數(shù)設(shè)置，算法測(cè)試結(jié)果見(jiàn)表1，其中各性能參數(shù)定義如下：

（3）MADW：平均工作站載荷波動(dòng)，由式（2）計(jì)算；

（4）CORA=（n_iter/MaxGen）×100：收斂效率，其中n_iter表示算法獲得最優(yōu)節(jié)拍時(shí)的迭代次數(shù)。

表1　算法測(cè)試結(jié)果

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

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

圖3　測(cè)試案例最優(yōu)方案的ARDC

圖4　測(cè)試案例最優(yōu)方案的MADW

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

5　結(jié)語(yǔ)

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

［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］劉儼后，左敦穩(wěn)，張丹.隨機(jī)作業(yè)時(shí)間的裝配線平衡問(wèn)題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2014，20（6）∶1 372-1 378.

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

［5］李英德，魯建夏.求解第二類裝配線平衡問(wèn)題的改進(jìn)蟻群算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，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，F(xiàn)igueira 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測(cè)試結(jié)果

TH186；TP18

A

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

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

2016-02-14

航空科學(xué)基金（2015ZG55018）；河南省科技廳軟科學(xué)研究計(jì)劃（132400410782）；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（15A630050）；鄭州市科技發(fā)展計(jì)劃（20140583）；校青年科研基金項(xiàng)目（2016053001）

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