王玉鑫，任 帥

(中國(guó)民航大學(xué) 航空工程學(xué)院，天津 300300)

0 引 言

為確保使產(chǎn)品具有良好的維修性，并且保證新產(chǎn)品在投入運(yùn)營(yíng)后，可以正確地使用和維修，制造商應(yīng)開發(fā)并提供正確、合理、詳盡、便于使用的新產(chǎn)品運(yùn)行文件，后勤保障分析國(guó)際程序規(guī)范(S3000L)明確要求產(chǎn)品在設(shè)計(jì)階段應(yīng)該考慮在運(yùn)營(yíng)階段和報(bào)廢階段的拆解，這要求在技術(shù)出版物中必須有相關(guān)拆解流程，即需要進(jìn)行拆卸序列規(guī)劃(disassembly sequence planning，DSP)。

進(jìn)行拆卸序列規(guī)劃在設(shè)計(jì)階段有助于提高產(chǎn)品的維修性，且可對(duì)技術(shù)出版物進(jìn)行有效驗(yàn)證；在運(yùn)營(yíng)階段或報(bào)廢階段也可以有效地在工程中提高工作效率，降低維修成本。

拆卸序列規(guī)劃的目的是生成零件或者部件的拆卸順序，以使得在維修工作中達(dá)到?jīng)Q策者的“最佳目標(biāo)”，此最佳目標(biāo)一般指拆卸成本最小、拆卸收益最大、對(duì)環(huán)境污染最小等要求，其好壞程度對(duì)于產(chǎn)品維修活動(dòng)的有效性和經(jīng)濟(jì)性有著直接的影響[1]。

DSP問(wèn)題本質(zhì)上可以抽象為一個(gè)排列組合的優(yōu)化問(wèn)題，隨著產(chǎn)品零件數(shù)量的增加，拆卸序列的數(shù)量會(huì)呈指數(shù)型增長(zhǎng)，即組合爆炸現(xiàn)象[2]。因此，DSP問(wèn)題的求解將會(huì)是DSP問(wèn)題的關(guān)鍵。對(duì)此，國(guó)內(nèi)外大量學(xué)者對(duì)其進(jìn)行了深入研究，比如蟻群算法[3-5]、人工蜂群算法[6，7]、遺傳蝙蝠算法[8]等。

蟻群算法經(jīng)改進(jìn)后具有良好的收斂性；人工蜂群算法起步較晚，在該問(wèn)題的應(yīng)用也較少，其同樣可在保證種群多樣性的前提下實(shí)現(xiàn)算法的快速收斂；雖鮮有人將蝙蝠算法用于拆卸序列規(guī)劃問(wèn)題，但經(jīng)改進(jìn)的遺傳蝙蝠算法的收斂性和收斂速度也優(yōu)于遺傳算法(GA)。TSENG Y J[9]等提出了一種基于粒子群算法(PSO)的閉環(huán)裝配與拆卸序列規(guī)劃的綠色裝配序列規(guī)劃模型，但是未考慮在通過(guò)粒子群迭代后的序列優(yōu)先關(guān)系；同樣地，張秀芬[10]在通過(guò)粒子群算法對(duì)拆卸序列進(jìn)行尋優(yōu)中也未考慮新一代的序列是否滿足拆卸優(yōu)先約束；在后續(xù)研究中，張濟(jì)濤等[11]提出了基于量子遺傳算法的拆卸序列規(guī)劃模型，對(duì)該問(wèn)題進(jìn)行改進(jìn)，其結(jié)論為迭代次數(shù)減少，可較快得出最優(yōu)解；然而其方法在每次迭代之后對(duì)所得出序列進(jìn)行檢驗(yàn)，若序列滿足優(yōu)先約束，則進(jìn)入下一步，否則重新進(jìn)行迭代。本質(zhì)上看，迭代次數(shù)要遠(yuǎn)高于其所得次數(shù)，其迭代次數(shù)的減少并不可靠。因此，以上研究雖然可以有效地得出較優(yōu)的拆解序列，但是在其算法的迭代過(guò)程中或是未考慮優(yōu)先約束，或是迭代速度過(guò)慢。

基于此，為提高拆卸序列規(guī)劃的效率，在工程中更快、更精準(zhǔn)地得出最優(yōu)解，本文根據(jù)產(chǎn)品零件的裝配約束關(guān)系，通過(guò)拆解優(yōu)先圖來(lái)表達(dá)拆解對(duì)象，并提出一種基于遺傳-粒子群混合優(yōu)化算法(GA-PSO)；最后以液壓泵作為算例，來(lái)驗(yàn)證算法的可行性及優(yōu)越性。

1 產(chǎn)品拆卸優(yōu)先圖建模

1.1 拆卸優(yōu)先圖建立

本文所涉及的拆卸序列規(guī)劃主要是完全拆卸，其目標(biāo)函數(shù)一般為時(shí)間最短，所以選用較簡(jiǎn)單的拆卸優(yōu)先圖進(jìn)行表達(dá)，若為選擇性拆卸則不適用。

拆卸優(yōu)先圖可以簡(jiǎn)單有效地表達(dá)產(chǎn)品的拆卸優(yōu)先約束關(guān)系[12]，拆卸優(yōu)先圖如圖1所示。

圖1 拆卸優(yōu)先圖

圖1中，A、B、C、D、E、F分別表示該產(chǎn)品的組成構(gòu)件，有向箭頭代表約束關(guān)系，表示各部件優(yōu)先約束關(guān)系，如F→A表示在拆卸A之前，必須先拆卸F。

不同于之前研究的表達(dá)，本文所采用的拆解優(yōu)先圖使用分層表達(dá)，A為第0層，B、C為第一層，D為第二層，E為第三層，F(xiàn)為第四層。分層表達(dá)便于對(duì)序列進(jìn)行“合規(guī)化處理”，“合規(guī)化處理”即為對(duì)隨機(jī)序列進(jìn)行處理使其滿足優(yōu)先約束。

1.2 模型的數(shù)學(xué)描述

DSP為離散組合優(yōu)化問(wèn)題，基于拆卸優(yōu)先圖模型，可將此問(wèn)題描述為：

產(chǎn)品可拆卸單元為N個(gè)，每次僅能拆卸其中一個(gè)，所求序列應(yīng)該滿足拆卸優(yōu)先關(guān)系，并且每個(gè)頂點(diǎn)都需遍歷且只能遍歷一次。

A-F按1-6進(jìn)行排列，拆卸優(yōu)先矩陣R如下式所示：

(1)

其中，Rrc—矩陣R的第r行第c列位置的數(shù)值，

Rrc=

4即為拆卸優(yōu)先矩陣層數(shù)。

通過(guò)搜索優(yōu)先矩陣可以將隨機(jī)序列進(jìn)行合規(guī)化處理，合規(guī)化處理流程圖如圖2所示。

圖2 合規(guī)化處理流程圖

M—拆卸優(yōu)先矩陣層數(shù)

對(duì)于完全拆卸序列規(guī)劃，其總拆卸操作時(shí)間一致，由于總時(shí)間=總拆卸操作時(shí)間+操作換向時(shí)間+變換工具時(shí)間，則可以將目標(biāo)函數(shù)看作換向次數(shù)及工具變換次數(shù)的函數(shù)。該目標(biāo)函數(shù)即可作為算法中的適應(yīng)度函數(shù)。

(1)拆卸工具變換次數(shù)如下式所示：

(2)

(2)拆卸方向變換次數(shù)如下式所示：

(3)

2 GA-PSO混合優(yōu)化算法

2.1 算法原理及模型映射

2.1.1 算法1 (粒子群算法)

粒子群算法采用群體進(jìn)化，通過(guò)適應(yīng)度函數(shù)評(píng)價(jià)每個(gè)粒子的好壞，模擬鳥群飛行覓食行為，集體協(xié)作尋找最優(yōu)解。將鳥群作為一個(gè)粒子群，每只鳥作為G維空間的一個(gè)粒子，其代表問(wèn)題的一個(gè)可行解，具有位置和速度兩個(gè)屬性。

粒子位置坐標(biāo)即為解向量，可通過(guò)適應(yīng)度函數(shù)對(duì)其進(jìn)行評(píng)價(jià)，各粒子可以通過(guò)自身所經(jīng)歷的位置、最佳位置和全局最佳位置提供的信息，在解空間內(nèi)不斷更新，尋找最優(yōu)解[13]。個(gè)體最優(yōu)解為粒子本身所經(jīng)歷的最佳位置，全局最優(yōu)解為種群所經(jīng)歷的最佳位置。

傳統(tǒng)的連續(xù)性尋優(yōu)規(guī)則一般如下：

G維空間粒子i的信息可表示為：

位置信息如下：

xi=(xi1,xi2,…,xiG)

(4)

速度信息如下：

vi=(vi1,vi2,…,viG)

(5)

根據(jù)個(gè)體最優(yōu)解和全局最優(yōu)解進(jìn)化，速度更新如下：

(6)

位置更新如：

(7)

2.1.2 算法2 (遺傳算法)

解決拆卸序列規(guī)劃問(wèn)題可直接采用零件或者操作編號(hào)進(jìn)行編碼，通過(guò)選擇算子對(duì)各染色體進(jìn)行選擇以得到父代染色體，再通過(guò)交叉、變異算子[14-16]。對(duì)種群染色體進(jìn)行迭代尋找最優(yōu)解。

傳統(tǒng)的遺傳算法中，選擇算子一般選用輪盤賭選擇法。具體方法為將每個(gè)粒子被選擇的概率設(shè)定為該粒子的適應(yīng)度所占種群總適應(yīng)度的大小，若適應(yīng)度越小越好，則通過(guò)各個(gè)粒子適應(yīng)度與種群總適應(yīng)度的差值之間的比值來(lái)確定。例如：3個(gè)粒子適應(yīng)度為1、4、5，則總適應(yīng)度為10，3個(gè)粒子被選擇概率的比值為9 ∶6 ∶5，三者被選擇的概率分別為0.45、0.3、0.25。

交叉算子一般是隨機(jī)確定一個(gè)或幾個(gè)交叉點(diǎn)的位置，然后將兩個(gè)染色體的基因進(jìn)行交換，從而選擇兩個(gè)新的個(gè)體。

變異算子一般是隨機(jī)選擇某染色體的某個(gè)位置，在其可變范圍內(nèi)進(jìn)行按一定規(guī)則隨機(jī)變化。

2.2 遺傳-粒子群混合優(yōu)化算法

粒子群算法多適用于連續(xù)組合優(yōu)化問(wèn)題[17]，通過(guò)PSO求解DSP這種離散問(wèn)題，需通過(guò)以下方法將其進(jìn)行對(duì)應(yīng)。

在產(chǎn)品模型基礎(chǔ)上，產(chǎn)生多個(gè)粒子，每個(gè)粒子由1-N的自然數(shù)組成，即可構(gòu)成一個(gè)粒子群：

(1)粒子的位置：對(duì)應(yīng)拆卸序列；

(2)粒子的速度：前人將速度取值空間定為0,1來(lái)代表至下一代粒子元素是否發(fā)生變動(dòng)。但是，通過(guò)此方式進(jìn)行粒子的移動(dòng)會(huì)產(chǎn)生不合規(guī)的粒子，需要再對(duì)粒子進(jìn)行合規(guī)劃處理。因此，本文取消粒子群中的速度概念；

(3)粒子的適應(yīng)度：對(duì)應(yīng)拆卸成本函數(shù)，其值越小，序列越佳。

遺傳算法在求解DSP問(wèn)題時(shí)同樣需要進(jìn)行改進(jìn)，傳統(tǒng)的交叉、變異算子可能導(dǎo)致從原本合規(guī)的父代染色體得到不合規(guī)的子代染色體。因此，要重新設(shè)計(jì)交叉及變異算子：

(1)交叉是GA更新和探索解空間的關(guān)鍵操作。傳統(tǒng)的交叉算子可能會(huì)導(dǎo)致序列錯(cuò)誤，比如FEDBAC與FECDBA在第3個(gè)點(diǎn)交叉則產(chǎn)生FECBAC與FEDDBA。

為保證基因的完整性，將使用優(yōu)先選擇交叉方式進(jìn)行交叉[18]，優(yōu)先保存交叉算子如圖3所示。

圖3 優(yōu)先保存交叉算子F1—父代1；F2—父代2；C1—子代掩碼，C2—子代

步驟如下：①隨機(jī)生成序列C1，該序列為1-2的隨機(jī)排列，長(zhǎng)度與染色體長(zhǎng)度相同；②C1中第一個(gè)數(shù)字是1，則C2第一個(gè)基因從F1的第一個(gè)基因提取，并刪除F1與F2中的該基因；③第二個(gè)數(shù)字是2，則C2從父代2的第一個(gè)染色體提取，并刪除F1與F2的該基因；④重復(fù)以上步驟即可得出新染色體C2；

(2)變異算子。不同于傳統(tǒng)變異算子，變異算子不能簡(jiǎn)單地選取任意兩點(diǎn)進(jìn)行置換，原因是交換后的染色體可能不能滿足優(yōu)先約束，合規(guī)化處理后可能與變異前相同，變異無(wú)效。對(duì)其進(jìn)行改進(jìn)，任取兩點(diǎn)將兩點(diǎn)間所有基因倒序排列，再經(jīng)過(guò)合規(guī)化處理后變異有效的概率較高。

由于粒子群算法種群中一旦產(chǎn)生相對(duì)較優(yōu)的粒子，則粒子都會(huì)朝著該粒子進(jìn)化，若該粒子并非全局最優(yōu)，且全局最優(yōu)的方向與此粒子的方向相反，則粒子將無(wú)法找到全局最優(yōu)解，使得其局部搜索能力較強(qiáng)。在對(duì)求解質(zhì)量要求不高時(shí)，該算法可高效求得高質(zhì)量的解，但并非最優(yōu)解。因此，隨著PSO算法的不斷更新迭代，種群多樣性必然減少，易陷入局部最優(yōu)，從而得到局部最優(yōu)解。

另外，拆卸序列規(guī)劃問(wèn)題是離散型數(shù)值尋優(yōu)問(wèn)題，且其序列順序已被約束，這容易導(dǎo)致初始種群本身很可能已散落在局部最優(yōu)解附近，以致無(wú)法尋找到全局最優(yōu)解，從而得不出最優(yōu)序列。遺傳算法通過(guò)變異可提高其全局搜索性，將遺傳算法與粒子群算法進(jìn)行結(jié)合，可以增強(qiáng)粒子群算法的全局搜索能力。

稱之為覆蓋粒規(guī)則(xi)B→Dk的置信度,其中|·|指一個(gè)集合的基數(shù)。如果conf((xi)B→Dk)=1,則(xi)B→Dk稱為一條確定性規(guī)則;否則稱之為一條可能性規(guī)則。

因此，本研究提出了GA-PSO混合的優(yōu)化算法。

遺傳-粒子群混合優(yōu)化算法流程圖如圖4所示。

圖4 遺傳-粒子群混合算法流程圖

步驟一：設(shè)定算法基本參數(shù)，如種群數(shù)量，交叉、變異概率，粒子維度，約束矩陣，各零件拆卸的操作方向及工具信息，生成初始種群；

步驟二：對(duì)初始種群進(jìn)行合規(guī)化處理；

步驟三：計(jì)算適應(yīng)度，找出個(gè)體和全局最優(yōu)；

步驟四：判斷是否滿足終止條件，條件一般設(shè)定為迭代次數(shù)或者達(dá)到所要求的適應(yīng)度值，若達(dá)到終止條件則結(jié)束迭代，未達(dá)到則進(jìn)行步驟五；

步驟五：各個(gè)粒子先后與個(gè)體最優(yōu)解和全局最優(yōu)解進(jìn)行優(yōu)先保存交叉操作，得到新的子代；

步驟七：對(duì)變異后的染色體再進(jìn)行合規(guī)化處理，返回步驟三。

本文所提的混合算法主要是從用遺傳算法來(lái)模擬粒子群算法的角度出發(fā)，重構(gòu)遺傳算法交叉及變異算子。從宏觀上來(lái)看,其行為是粒子群算法；從微觀來(lái)看，其行為是遺傳算法，從而構(gòu)成遺傳-粒子群混合算法。

3 算例驗(yàn)證及分析

本文所用適用于產(chǎn)品拆卸序列規(guī)劃的GA-PSO混合優(yōu)化算法由MATLAB(R2018A)編程實(shí)現(xiàn)，電腦配置為：Inter(R)Core(TM)i7- 4710MQ CPU@2.5GHz，在Windows 8系統(tǒng)下運(yùn)行，算法參數(shù)主要有粒子長(zhǎng)度lenchrom，種群數(shù)量swarmsize，最大迭代次數(shù)maxgen和約束矩陣R。

以文獻(xiàn)[19]中的液壓泵為例，筆者對(duì)該產(chǎn)品進(jìn)行分析。該液壓泵模型包括20個(gè)最小拆卸單位。

液壓泵拆卸優(yōu)先圖模型如圖5所示。

圖5 液壓泵拆卸優(yōu)先圖

液壓泵拆卸單元信息表如表1所示。

表1 液壓泵拆卸單元信息表

算法訓(xùn)練過(guò)程如圖6所示。

圖6 算法訓(xùn)練過(guò)程

各算法結(jié)果對(duì)比如表2所示。

表2 各算法結(jié)果對(duì)比

由表2可知：5種算法均能得到近似最優(yōu)解，但GA-PSO算法更為優(yōu)異：蟻群算法、粒子群算法、遺傳算法、改進(jìn)人工蜂群算法所得最優(yōu)解適應(yīng)度分別為21、21、21、20。

與以上4種算法相比，一方面，GA-PSO算法所得最優(yōu)解適應(yīng)度為17，其解更優(yōu)；另一方面，對(duì)比迭代次數(shù)與運(yùn)行時(shí)間，GA-PSO的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于以上幾種算法，且運(yùn)行時(shí)間與以上算法相比較短。

綜上所述，本文提出的GA-PSO算法與其他算法相比更具優(yōu)越性。

4 結(jié)束語(yǔ)

DSP問(wèn)題作為維修前所必須解決的問(wèn)題，組合優(yōu)化極具挑戰(zhàn)性。其一是由于其在進(jìn)行排列中，存在著優(yōu)先約束，使得模型的建立和算法的實(shí)現(xiàn)更加困難；其二是隨著裝配體可拆卸零件數(shù)量的增長(zhǎng)，其排列組合將呈爆炸式增長(zhǎng)，所以在建立模型和其求解算法時(shí)，要充分考慮這一現(xiàn)象。

本文通過(guò)拆卸優(yōu)先圖建立拆卸模型，并采用約束矩陣將模型表達(dá)為數(shù)學(xué)形式，不同于之前的研究，無(wú)需不斷對(duì)約束矩陣進(jìn)行迭代更新，將其作為約束運(yùn)用于后續(xù)算法，可以方便地對(duì)序列進(jìn)行合規(guī)調(diào)整；運(yùn)用優(yōu)先保存交叉方式和倒序式變異，對(duì)遺傳算法進(jìn)行了優(yōu)化，再將遺傳算法與粒子群算法相結(jié)合，改進(jìn)了粒子群算法的易陷入局部最優(yōu)的缺點(diǎn)。

最后，筆者以液壓泵作為算例，驗(yàn)證算法的可行性及優(yōu)越性，結(jié)果證明了其具有較好的全局搜索能力以及較快的收斂速度。

在今后的研究中，筆者將著手大型裝備的多人協(xié)作拆卸序列規(guī)則；同時(shí)，此算法只適用于單人完全拆卸，筆者會(huì)在將來(lái)的研究中做進(jìn)一步完善。