基于改進(jìn)和聲搜索算法的裝配序列規(guī)劃

曹忠園，周學(xué)良，郭靖

（湖北汽車工業(yè)學(xué)院 機械工程學(xué)院，湖北 十堰442002）

據(jù)統(tǒng)計，產(chǎn)品制造過程中約有40%以上的成本用于裝配工作［1］。由裝配工藝占制造過程成本比例可以看出，好的裝配序列有利于降低企業(yè)的制造時間與經(jīng)濟成本，裝配序列隨著裝配體零件的復(fù)雜化出現(xiàn)爆炸式增長。裝配序列規(guī)劃與拆卸序列規(guī)劃是計算機輔助工藝過程設(shè)計中的研究熱點，當(dāng)前已經(jīng)有眾多學(xué)者在裝配序列規(guī)劃方面做了許多研究。在裝配模型構(gòu)建方面主要有空間干涉矩陣、Petri 網(wǎng)、圖、TPD（task precedence diagram）、AOG（and/or graph）、TAOG（transformed and/or graph）等［2-7］。鄧明星等［8］將裝配穩(wěn)定性、裝配經(jīng)驗考慮進(jìn)裝配評價指標(biāo)中，采用裝配優(yōu)先關(guān)系圖避免了不可行序列的產(chǎn)生，運用改進(jìn)的蟻群算法有效減少了算法的搜索空間，得出了較好的裝配序列。Wang等［9］將裝配穩(wěn)定性、連接器的強度、裝配方向的變化、工具更換考慮在加權(quán)有向圖中，用模糊層次分析法量化各指標(biāo)，設(shè)計了一種基于最小生成樹的基于加權(quán)裝配優(yōu)先圖的裝配序列算法。在拆卸序列規(guī)劃方面，Lu 等［10］基于TAOG 模型建立了機器人拆卸線模型，將機器人數(shù)量、工位數(shù)量、零件需求量和CO2排放量作為評價指標(biāo)，采用改進(jìn)的遺傳算法對產(chǎn)品的拆卸序列以及工位的拆卸任務(wù)分配問題進(jìn)行計算，實現(xiàn)拆卸線的平衡。Liu 等［11-12］在空間干涉矩陣的約束下運用改進(jìn)的人工蜂群算法對機器人拆卸線的拆卸序列與平衡問題同時優(yōu)化，以照相機與齒輪泵模型為例，驗證了方法的可行性。

綜上所述，采用TAOG方法時節(jié)點數(shù)量隨產(chǎn)品零件數(shù)量增多呈幾何級數(shù)增加，難以在算法求解過程中實時構(gòu)造裝配模型［13］；未考慮實際裝配情況，求解出的裝配序列僅僅在算法方面能夠?qū)崿F(xiàn)；評價指標(biāo)不完善，最終得到的裝配序列不能全面反映實際工程問題。文中采用空間綜合干涉矩陣約束零件裝配先后關(guān)系進(jìn)行模型構(gòu)建，根據(jù)企業(yè)實際裝配環(huán)境，綜合考慮裝配工作臺的翻轉(zhuǎn)角及移動行程，確保生成可行序列，改進(jìn)普通和聲搜索（harmony search，HS）算法進(jìn)行裝配序列問題研究。

1 干涉矩陣

裝配序列中每個部件都需要在干涉矩陣的約束下產(chǎn)生，否則得到的序列有可能僅僅滿足于算法層面，而不滿足實際的裝配要求。裝配干涉矩陣Sd的定義如式（1）所示：

式中：n為裝配件編號；Sij為零件i從部件j的d方向進(jìn)行裝配的狀態(tài)，若可以裝配，則Sij=0，否則Sij=1，約定當(dāng)i=j時，Sij=0。由式（1）可知每個裝配體存在6個分別代表6個方向的干涉矩陣。為了得到可行裝配序列，將分別代表6個不同方向的干涉矩陣結(jié)合成綜合空間干涉矩陣。將綜合空間干涉矩陣每行元素進(jìn)行“或”運算，得出每個零件與其他零件的干涉情況，將矩陣中與其他零件沒有干涉的零件依次加入到裝配序列中，由于每次可選擇加入裝配序列的零件不止1 種，所以裝配序列具有多樣性，需建立指標(biāo)對不同序列進(jìn)行評價。

2 評價指標(biāo)的建立

文中在評價指標(biāo)中增加了移動行程及工作臺翻轉(zhuǎn)角，其他評價指標(biāo)有裝配重定向角以及裝配過程中裝配工具更換。各指標(biāo)建立方法如下：

1）裝配移動行程 裝配完零件（i-1）后，裝配零件i 時由于裝配點發(fā)生變化造成裝配操作人員手或者身體移動的距離稱為裝配移動行程。如圖1 所示，假設(shè)P1對應(yīng)零件（i-1），P2對應(yīng)零件i，則對應(yīng)的裝配移動行程如式（2）所示：

式中：m（i-1，i）為裝配零件（i-1）到裝配零件i所產(chǎn)生的移動行程。

圖1 裝配移動行程

2）工作臺翻轉(zhuǎn)角與裝配重定向角 裝配完零件（i-1）再裝配零件i 時，由于裝配點發(fā)生變化，裝配人員必須轉(zhuǎn)動工作臺來適應(yīng)新的裝配工作，翻轉(zhuǎn)角度變化越大所花費時間成本越大，工作臺翻轉(zhuǎn)角如式（3）所示：

式中：d（i-1，i）表示工作臺翻轉(zhuǎn)角變化；diri為裝配第i 個零件的工作臺角度。裝配重定向角是由于裝配點發(fā)生改變造成的裝配角度的改變，計算方式類似工作臺翻轉(zhuǎn)角，如式（4）所示：

式中：r（i-1，i）表示裝配重定向角變化。

3）裝配工具更換 如果裝配完零件（i-1）后裝配零件i 時需要更換裝配工具同樣會造成成本的增加，同種工具不同型號之間同樣存在更換情況，由工具更換造成的成本增加如式（5）～（6）所示：

式中：n 為工具種類數(shù)；u 為n 維方陣；TTi為同種工具不同型號轉(zhuǎn)換矩陣；tti，j表示是否存在工具a 到工具b 的轉(zhuǎn)換，存在則tti，j取1，否則tti，j取0；ttai，j表示是否存在同種工具中從第i種型號到第j種型號的轉(zhuǎn)換，存在則ttai，j取1，否則ttai，j取0。

4）適應(yīng)值函數(shù) 將上述4 種評價指標(biāo)綜合考慮，得到裝配序列評價函數(shù)如式（7）所示：

式中：n為裝配體中零件個數(shù)；w1～w4為各指標(biāo)權(quán)重。

3 和聲搜索算法的改進(jìn)

HS 算法是2001 年由韓國學(xué)者提出的一種具有良好全局搜索能力的算法，HS 算法中不同的樂手演奏出音樂組成和聲，算法的好壞通過和聲來衡量，每個樂手通過不斷演奏配合達(dá)到期望的和聲。算法中的變量包括和聲記憶庫取值概率HMCR、音調(diào)微調(diào)概率PAR 和音調(diào)微調(diào)帶寬BW，其中PAR 與BW 在算法迭代過程中始終保持不變，而在迭代后期算法趨于收斂，固定不變的PAR與BW會對迭代后期的和聲庫產(chǎn)生較大擾動，使算法收斂變慢?；綡S算法中新和聲的產(chǎn)生方式容易使算法陷入局部最優(yōu)解，根據(jù)以上分析，主要從算法參數(shù)設(shè)置與新和聲產(chǎn)生方式對算法進(jìn)行改進(jìn)，在算法迭代過程中PAR與BW隨著迭代次數(shù)動態(tài)改變，且是隨著迭代次數(shù)增長PAR 與BW 逐漸變小。文中提出了一種自適應(yīng)全局最優(yōu)算法（the self-adaptive harmony search algorithm，SGHS）求解裝配序列規(guī)劃問題。

1）PAR 與BW 的改進(jìn) 為使PAR 隨著迭代次數(shù)增加而逐漸減小，算法中設(shè)置PARmax值與PARmin值，通過2 個音調(diào)微調(diào)概率構(gòu)造實時PAR 值，具體構(gòu)造方法如式（8）所示：

式中：PAR（t）為實時音調(diào)微調(diào)概率；Tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)。用HS算法求解裝配問題時，音調(diào)編碼方式如圖2所示，根據(jù)BW對音調(diào)進(jìn)行微調(diào)時不能僅僅考慮算法層面對音調(diào)進(jìn)行增減，否則求解方案不滿足實際需求。根據(jù)遺傳算法中染色體交叉的思想，將和聲搜索算法中的BW改為和聲交叉概率BC，每次迭代時和聲中的音調(diào)以BC進(jìn)行交叉，根據(jù)音調(diào)微調(diào)概率的改進(jìn)思想，BC同樣需要隨著迭代次數(shù)增加逐漸減小，構(gòu)造方式為

式中：BC（t）為實時和聲交叉概率；BCmax與BCmin分別為最大與最小和聲交叉概率。

圖2 和聲編碼結(jié)構(gòu)

2）新和聲產(chǎn)生方式改進(jìn) 在基本HS 算法中，新和聲產(chǎn)生方式為根據(jù)HMCR 從和聲庫中隨機選取和聲，當(dāng)從記憶庫中選取和聲時根據(jù)PAR 在原來和聲的基礎(chǔ)上進(jìn)行微調(diào)得到新的和聲，這種新和聲產(chǎn)生方式容易使算法在迭代過程中降低和聲庫中和聲種類多樣性使算法收斂在局部最優(yōu)解。文中提出的SGHS 算法根據(jù)HMCR 在和聲庫中隨機選擇1組和聲并交換和聲中的音調(diào)產(chǎn)生新和聲，增加了和聲庫的多樣性。當(dāng)對新產(chǎn)生的和聲進(jìn)行微調(diào)時，基本和聲算法根據(jù)PAR和BW進(jìn)行微調(diào)得到新和聲，SGHS 算法從和聲庫中隨機選擇2 個和聲根據(jù)BC進(jìn)行交叉，得到2個新和聲，再使用適應(yīng)度評價函數(shù)對2個新和聲進(jìn)行評價，選擇適應(yīng)度較好的和聲作為新和聲。

4 實例分析

4.1 算法編碼

裝配序列評價指標(biāo)分別為移動行程m、工作臺翻轉(zhuǎn)角d、重定向角r 與工具更換成本u，裝配1 個零件時需要確定的因素有裝配零件號、裝配方向、與裝配工具。在算法中單個和聲中的音調(diào)xi的結(jié)構(gòu)如圖2a 所示，每個音調(diào)由3 個位組成，第1 位表示零件代號，第2位表示裝配方向，第3位表示裝配工具，每個和聲由n個音調(diào)組成，n表示裝配零件集中零件的個數(shù)。

4.2 裝配實例驗證

以某型號齒輪泵為例驗證所提出的SGHS 算法，齒輪泵模型見圖3，相關(guān)信息見表1。根據(jù)式（2）計算出裝配移動行程，將移動行程換算成移動時間，設(shè)裝配人員手或身體移動速度為12 cm·s-1，各裝配點之間移動行程均在NX軟件中進(jìn)行測量，得到裝配行程成本矩陣Md。通過式（3）～（4）計算得到裝配工作臺翻轉(zhuǎn)角成本矩陣Dc與重定向角所增加的成本Dr，通過式（5）～（6）計算得到裝配工具更換增加的成本矩陣P，由這些指標(biāo)構(gòu)成裝配序列評價函數(shù)F。由表1 可知各部件在x+與z-方向的空間干涉矩陣如式（10）～（11）所示：

同理可得出其他空間干涉矩陣，將分別代表6個方向的空間干涉矩陣合成綜合空間干涉矩陣：

對SGHS 算法進(jìn)行參數(shù)設(shè)置，算法中較大的HMCR有利于提高算法局部搜索能力，較小的HM?CR 有利于增加和聲庫HM 中和聲的多樣性，根據(jù)文獻(xiàn)［15］的研究，將算法中各參數(shù)分別設(shè)置為HM?CR 為0.90、PARmax為0.65、PARmin為0.20、BWmax為0.60、BWmin為0.20、HM 為100。和聲適應(yīng)度由式（7）中適應(yīng)值函數(shù)F 進(jìn)行評價，歸一化處理后通過層次分析法確定式中權(quán)重w1～w4分別為0.353 6、0.313 3、0.181 4、0.151 7，算法迭代次數(shù)Tmax為200。首先記錄通過空間綜合干涉矩陣生成的所有零件可能的裝配先后關(guān)系，算法迭代時通過判斷是否符合記錄的信息以保證裝配序列是可行序列，最終計算出裝配序列為11→7→6→9→10→8→17→1→12→2→13→3→14→4→15→5→16→22→23→24→25→21→18→19→20。

圖3 齒輪泵模型

表1 齒輪泵各部件屬性

蟻群算法具有較強的負(fù)反饋機制，在TSP問題上被廣泛應(yīng)用。裝配序列規(guī)劃問題類似TSP問題，螞蟻覓食路徑上的地點與裝配序列中的零件可以較好地結(jié)合，因此在裝配序列規(guī)劃問題上也常使用蟻群算法求解，由于蟻群算法在裝配序列規(guī)劃問題上研究較成熟，所以將SGHS算法與文獻(xiàn)［16］中所提出的蟻群算法相比較，分析解的質(zhì)量與收斂速度，結(jié)果如圖4所示。

從圖4 可以看出：由于基本HS 算法參數(shù)在迭代過程中不變，計算后期較大的音調(diào)微調(diào)概率與和聲交叉概率會對結(jié)果造成較大擾動，造成基本HS算法收斂速度比SGHS 算法慢。蟻群算法相比較于基本HS 算法具有求解速度快、計算結(jié)果好的特點，而比SGHS 算法計算得到的裝配成本高，且收斂速度相較于SGHS算法慢。由此可以證明SGHS算法性能優(yōu)于基本HS算法與蟻群算法。

圖4 不同算法比較

5 結(jié)論

1）通過建立裝配空間約束矩陣保證生成可行裝配序列，同時減小了算法的搜索空間。將裝配移動行程、工作臺翻轉(zhuǎn)角、裝配重定向角以及工具更換考慮進(jìn)裝配成本中，建立了裝配成本評價函數(shù)并通過層次分析法確定了各評價指標(biāo)的權(quán)重。

2）對基本HS算法進(jìn)行改進(jìn)，將算法中的中音調(diào)微調(diào)概率與音調(diào)微調(diào)帶寬改為隨算法迭代實時減小，使算法迭代擾動隨迭代次增大而減小，加快了算法的收斂速度。根據(jù)工程實際應(yīng)用需求，結(jié)合遺傳算法的思想對新和聲的產(chǎn)生方式作了改進(jìn)，增加了和聲庫的多樣性，避免收斂到局部最優(yōu)解。

3）用齒輪泵模型分析了基本HS 算法、SGHS算法與蟻群算法在求解裝配序列方面的特點，試驗結(jié)果表明，SGHS算法相比基本HS算法與蟻群算法具有一定優(yōu)越性。