改進布谷鳥算法在裝配序列規(guī)劃中的應(yīng)用研究

秦紅斌， 王玲軍， 唐紅濤， 孔仁杰

（武漢理工大學(xué)機電工程學(xué)院， 湖北武漢 430070）

0 前言

在制造業(yè)中， 產(chǎn)品裝配過程所耗費的時間占整個生產(chǎn)時間的20%～50%， 產(chǎn)品的裝配成本耗費超過40%［1］。 裝配序列規(guī)劃（Assembly Sequence Planning，ASP） 是產(chǎn)品設(shè)計和制造的重要環(huán)節(jié)， 裝配序列的優(yōu)化對降低生產(chǎn)成本、 提高產(chǎn)品裝配質(zhì)量和生產(chǎn)效率至關(guān)重要。 裝配序列規(guī)劃已經(jīng)被證明是一個典型的NPhard 問題［2－3］。 因此， 國內(nèi)外的諸多學(xué)者對ASP 問題展開大量的研究。 在已有的解決ASP 問題的方法中，智能優(yōu)化算法展現(xiàn)了其獨有的優(yōu)勢。 BONNEVILLE等［4］首次將遺傳算法應(yīng)用于求解ASP 的問題中， 隨后蟻群優(yōu)化算法［5］、 粒子群優(yōu)化算法［6］等都被應(yīng)用于求解ASP 問題。

劉冬等人［7］針對基本粒子群算法早熟的缺點， 提出了變種群策略－粒子群優(yōu)化算法（VPS－PSO） 用于求解ASP 問題， 避免了種群陷入局部最優(yōu)。 HAN等［8］提出了一種結(jié)合共生生物搜索（Symbiotic Organ?isms Search， SOS） 和蟻群優(yōu)化（Ant Clony Optimiza?tion， ACO） 的SOS－ACO 算法來計算最優(yōu)或者接近最優(yōu)的裝配序列。 孟冠軍、 楊大春［9］建立遺傳－蟻群算法求解ASP 問題， 以加快算法的收斂速度。 任云、劉丹［10］提 出 一 種 將 天 牛 須 搜 索 （Beetle Antennae Search， BAS） 算 法 和 閃 電 搜 索 算 法 （Lightning Search Algorithm， LSA） 混合的BAS－LSA 混合算法，結(jié)合天牛須算法較優(yōu)的局部搜索能力和閃電搜索算法較優(yōu)的全局搜索能力， 提高了求解精度。 但上述研究仍存在以下不足： 在建立裝配關(guān)系模型時未考慮零件之間的支撐關(guān)系， 或者在建立適應(yīng)度函數(shù)時未考慮待裝配零件與所有已裝配好的零件之間的裝配關(guān)系。 布谷鳥優(yōu)化算法（Cuckoo Search， CS） 是由YANG 和DEB［11］提出的一種群智能優(yōu)化算法， 也是一種新型元啟發(fā)式算法。 布谷鳥算法結(jié)構(gòu)簡單、 算法參數(shù)少、易于實現(xiàn)， 兼?zhèn)漭^優(yōu)的全局搜索和局部搜索能力。 雍升［12］將布谷鳥算法運用到求解ASP 問題上， 但是群體中每只布谷鳥都執(zhí)行Lévy 飛行， 并且飛行步長是一個定值， 缺乏自適應(yīng)性， 導(dǎo)致收斂速度變慢。 針對以上問題， 本文作者建立考慮裝配序列的幾何可行性、 穩(wěn)定性、 聚合性、 重定向性的裝配關(guān)系模型和適應(yīng)度函數(shù)， 提出一種改進布谷鳥算法 （Improved Cuckoo Search， ICS）， 設(shè)計編碼方案， 改進種群初始化和種群進化策略， 加快解的收斂速度， 使其具有較強的尋優(yōu)能力。

1 裝配關(guān)系模型及適應(yīng)度函數(shù)構(gòu)建

產(chǎn)品的裝配序列有多種方案可供選擇， 裝配序列會影響裝配成本和裝配效率， 在評價裝配序列的優(yōu)劣時， 應(yīng)首先考慮裝配序列的幾何可行性， 即裝配序列在幾何空間內(nèi)可進行裝配， 再綜合考慮裝配序列的穩(wěn)定性、 聚合性、 重定向性。

1.1 裝配序列的幾何可行性

幾何可行性是指在裝配體中裝配零件Pi時， 已裝配好的零件是否對零件Pi產(chǎn)生干涉。 通常情況下，零件是按d（k）＝｛＋x，－x，＋y，－y，＋z，－z｝6 個裝配方向中一個方向進行裝配的， 建立零件在6 個方向的干涉矩陣［13］， 如式（1） 所示：

其中：pij表示零件Pj沿k方向裝配時與零件Pi的干涉情況， 若pij＝1， 表示零件Pj沿k方向裝配時與零件Pi發(fā)生干涉； 若pij＝0， 則無干涉。 矩陣如式（2） 所示：

定義Iik為零件Pi沿k方向裝配時與已裝好的零件的干涉值之和， 若Iik＝0， 則零件Pi可以沿k方向進行裝配， 否則， 不能沿k方向進行裝配。Iik的計算公式如式（3） 所示：

對于一個裝配序列， 若V1＝0， 則證明裝配體中所有零件都無干涉， 為可行裝配序列； 若V1≠0， 則證明為幾何不可行裝配序列。

1.2 裝配序列的穩(wěn)定性

穩(wěn)定性包含2 個方面： （1） 零件之間的連接穩(wěn)定性， 通過建立連接矩陣來表示裝配體中各零件之間的連接關(guān)系， 用于判斷連接穩(wěn)定性； （2） 零件在裝配過程中重力方向上的支撐穩(wěn)定性， 通過建立支撐矩陣來表示零件之間支撐關(guān)系。 裝配序列穩(wěn)定性的量化指標(biāo)V2的計算公式如式（5） 所示：

其中：V21表示裝配序列連接穩(wěn)定性的量化指標(biāo)；V22表示裝配序列支撐穩(wěn)定性的量化指標(biāo)。

（1） 連接穩(wěn)定性。 各零件之間的連接關(guān)系用連接矩陣C＝ ［cij］n×n表示， 元素cij表示零件Pi與零件Pj之間的連接類型。 定義cij的值如式（6） 所示：

接觸連接關(guān)系表示零件之間相互接觸， 穩(wěn)定連接表示兩零件之間通過連接件連接， 具備穩(wěn)定的連接關(guān)系。

裝配序列連接穩(wěn)定性指標(biāo)V21的求解算法如下：

①參數(shù)初始化， 令V21＝0，S1＝0，S1為算法計算中間變量；

②從連接矩陣C中取出零件Pi與前i－1 個已裝配好的零件連接信息， 并將它置于N1中，N1為算法臨時存儲信息的變量；

③若N1存在值為0， 則S1＝0， 若不存在， 則判斷N1中是否存在1， 若存在， 則S1＝1， 若不存在，則判斷S1＝2；

④V21＝V21＋S1；

⑤i＝i＋1， 如果i＜n， 轉(zhuǎn)至步驟②； 否則轉(zhuǎn)至步驟⑥；

⑥結(jié)束。

由上述可知：V21的數(shù)值越小， 代表裝配過程中穩(wěn)定連接越多， 裝配過程中的穩(wěn)定性越好。

（2） 支撐穩(wěn)定性。 各零件之間的支撐關(guān)系用矩陣M＝ ［mij］n×n表示， 元素mij表示零件Pi與零件Pj之間的支撐類型。 定義mij的值如式（7） 所示：

裝配序列支撐穩(wěn)定性指標(biāo)V22的求解算法如下：

①參數(shù)初始化， 令V22＝0，S2＝0，S2為算法計算中間變量；

②從支撐矩陣M中取出零件Pi與前i－1 個已裝配好的零件支撐信息， 并將它置于N2中，N2為算法臨時存儲信息的變量；

③如果N2存在值為0， 則S2＝0； 否則，S2＝1；

④V22＝V22＋S2；

⑤i＝i＋1， 如果i＜n， 轉(zhuǎn)至步驟②； 否則轉(zhuǎn)至步驟⑥；

⑥結(jié)束。

由上述可知：V22的數(shù)值越小， 則代表裝配過程中在重力方向的支撐越多， 裝配穩(wěn)定性越好。

1.3 裝配序列的聚合性

聚合性表示裝配過程中零件裝配工具的改變次數(shù)， 在裝配過程中應(yīng)該盡可能地減少裝配工具的改變次數(shù)， 有助于降低裝配成本。 裝配工具的改變定量計算如式（8） 所示：

裝配過程中裝配工具的改變次數(shù)V3越小， 裝配序列的聚合性越好， 裝配序列越優(yōu)。

1.4 裝配序列的重定向性

重定向性是指在裝配過程中零件裝配方向的改變次數(shù)， 裝配過程中應(yīng)降低裝配方向的改變次數(shù)， 提高裝配效率。 裝配方向的改變定量計算方式如式（9）所示：

裝配過程中裝配方向的改變次數(shù)V4越小， 裝配序列的重定向性越好， 裝配序列越優(yōu)。

1.5 適應(yīng)度函數(shù)構(gòu)建

綜上所述， 綜合考慮裝配序列的幾何可行性、 裝配序列的穩(wěn)定性、 裝配序列的聚合性、 裝配序列的重定向性4 個評價指標(biāo)， 通過量化方法建立適應(yīng)度函數(shù)， 如式（10） 所示：

其中：ωi（i＝1， 2， 3， 4） 為權(quán)重系數(shù)；V1、V2、V3、V4分別表示裝配序列的幾何可行性、 穩(wěn)定性、 聚合性和重定向性評價指標(biāo)。 適應(yīng)度值F越小，裝配序列越好。

2 改進布谷鳥算法求解ASP 問題

2.1 標(biāo)準(zhǔn)布谷鳥算法

基于被發(fā)現(xiàn)概率Pa來淘汰更新后的解， 采用隨機游走的局部搜索策略生成相同數(shù)量的解補充種群，保持種群數(shù)量的一致， 如式（17） 所示：

2.2 編碼與解碼

標(biāo)準(zhǔn)布谷鳥算法適用于求解連續(xù)性問題， 而裝配序列規(guī)劃問題是離散型， 無法直接應(yīng)用求解。 為此，文中采用隨機鍵和最小位置規(guī)則（Smallest Position Value， SPV） 的方法， 對編碼方式進行處理， 從而建立起個體與裝配序列的映射關(guān)系。 如圖1 所示，SPV 規(guī)則為原向量的每個元素生成隨機值， 原向量的元素根據(jù)隨機值的大小經(jīng)過升向排序， 得到一個新向量。

圖1 編碼過程Fig.1 Encoding process

ASP 問題涉及多零件的裝配順序、 裝配方向選擇、 裝配工具選擇問題， 因此， 文中采用基于零件編號、 裝配方向、 裝配工具的3 層編碼規(guī)則。 編碼時首先生成零件編號序列（Number）， 然后根據(jù)所生成的零件編號序列對零件的裝配方向（Direction）、 裝配工具（Tool） 進行選擇。 裝配方向、 裝配工具層用于記錄該條裝配序列的裝配信息。件4 的裝配方向也為＋y。 如果后續(xù)零件的可行裝配方向無法與前一位保持一致， 例如零件2 中可行裝配方向沒＋y， 則考慮后續(xù)零件5 的可行裝配方向， 選擇零件2 的裝配方向為＋x， 同理可得零件5 和零件1 的裝配方向分別為＋x、＋x， 該裝配序列的裝配方向分別為｛＋y，＋y，＋x，＋x，＋x｝ 。 裝配工具與裝配方向的選擇機制一樣， 可得該裝配序列的裝配工具分別為｛T3，T3，T3，T1，T3｝ 。

結(jié)合編碼過程可得： 零件裝配順序為5→3→6→2→7→1→4， 裝配方向分別為｛－ x，＋x，＋x，＋y，＋z，－y，－y｝ ， 裝配工具分別為｛T1，T2，T3，T2，T2，T1，T3｝ 。

2.3 混合種群初始化策略

為了提高初始化種群的質(zhì)量和保證種群的多樣性，文中設(shè)計了混合種群初始化策略進行種群的初始化（包括幾何不可行序列）， 即： （1） 基于最大化可行序列和最小裝配成本的種群初始化； （2） 隨機初始化策略。 2 種策略生成的初始化種群數(shù)量分別為50%。

文中的編碼采用基于零件編號、 裝配方向、 裝配工具的3 層編碼， 在裝配模型評價指標(biāo)中， 裝配序列的幾何可行性、 穩(wěn)定性評價指標(biāo)在零件編號層確定后， 就可以通過對應(yīng)的算法計算出來。 最大化可行序列和最小裝配成本策略體現(xiàn)在對裝配方向和裝配工具的合理選擇上， 隨機策略則是對零件的裝配方向和裝配工具進行隨機選擇。 如圖2 所示， 有裝配序列3→4→2→5→1， 裝配方向?qū)訛榇肆慵c前一個零件不發(fā)生干涉的可裝配方向， 裝配工具層為此零件裝配時所需要使用的工具。

圖2 優(yōu)化策略Fig.2 Optimizing strategy

在為首位零件選擇裝配方向和裝配工具時應(yīng)考慮對后一位零件的影響， 如為零件3 選擇時裝配方向應(yīng)在｛－ x，＋y，＋z，－z｝ 中隨機選擇。 現(xiàn)隨機選為＋y方向， 后續(xù)選擇零件的裝配方向應(yīng)盡量在滿足裝配幾何可行性的前提下和前一位的零件保持一致。 零

2.4 改進的種群進化策略與搜索策略

在布谷鳥算法中， 群體中每只布谷鳥都執(zhí)行Lévy 飛行， 會造成收斂速度變慢， 并且標(biāo)準(zhǔn)Lévy 飛行中的步長是一個定值， 缺乏自適應(yīng)性， 同樣會導(dǎo)致收斂速度變慢。 針對此種情況， 文中將布谷鳥種群分為3 個子群， 分別采用不同的種群進化策略， 按種群的適應(yīng)度值進行升序排序。 首先取出適應(yīng)度較差的1/3 種群數(shù)量的布谷鳥作為一個子群， 采用交叉、 變異的方式來代替Lévy 飛行進行更新， 其中交叉相當(dāng)于Lévy 飛行的“長飛行”， 在全局的范圍內(nèi)進行搜索； 變異相當(dāng)于Lévy 飛行中的“短飛行”， 在局部范圍進行搜索， 可以減少Lévy 飛行的次數(shù)， 加快收斂速度； 然后再將剩下的種群隨機分為2 個子群， 分別采用固定步長的標(biāo)準(zhǔn)Lévy 飛行和基于自適應(yīng)步長的改進Lévy 飛行進行種群更新； 最后將更新后的3 個子群合并生成的新一代種群。

采用部分匹配交叉（Partially－Matched crossover，PMX） 的方式進行交叉操作［14］， 具體操作流程如圖3 所示。

圖3 PMX 交叉操作Fig.3 PMX crossover operation

從種群中隨機抽取2 個個體Z1和Z2作為父代，首先隨機選取2 個交叉的點， 將2 個點之間的部分進行交叉， 再將剩余的部分采用復(fù)制或相匹配的方式進行交叉替換。 如圖3 所示， 父代Z1中214 被選中，父代Z2中357 被選中， 那么2 與3、 1 與5、 4 與7 相匹配。 首先將214 與357 分別加入子代Z和子代Z中， 再將其他位置上的編號復(fù)制到子代中， 若子代中已經(jīng)存在此編號， 則運用匹配規(guī)則將匹配后的編號復(fù)制到子代中， 從而得到新的子代。

采用隨機選取2 個零件位置進行互換的變異操作方式， 具體操作如圖4 所示， 隨機選取的第一個是位置2， 第二個是位置6， 將位置2 與6 的零件編號互換， 從而得到新的個體Zf2。

圖4 互換變異操作Fig.4 Swap mutation operation

通過算法的迭代次數(shù)控制飛行步長： 在算法初期， 應(yīng)進行較大步長的Lévy 飛行， 有助于提高全局搜索能力， 避免陷入局部最優(yōu)； 在算法后期， 應(yīng)進行較小步長的Lévy 飛行， 有助于提高搜索精度。 文中步長因子α的取值如式（18） （19） 所示［15］：

其中：αmax表示步長因子的最大值；αmin表示步長因子的最小值；t為當(dāng)前迭代次數(shù)；T為迭代總次數(shù)。 經(jīng)文獻(xiàn)［15］實驗驗證，αmax取0.5、αmin取0.05效果最佳。

2.5 ICS 算法流程

改進布谷鳥算法流程如圖5 所示， 具體步驟如下：

圖5 ICS 算法流程Fig.5 ICS algorithm flow

步驟1， 對算法相關(guān)參數(shù)進行初始化， 包括種群數(shù)量n， 最大迭代次數(shù)T， 發(fā)現(xiàn)概率Pa， 交叉概率Pc， 變異概率Pm， 適應(yīng)度函數(shù)權(quán)值系數(shù)ωi（i＝1， 2，3， 4）；

步驟2， 采用上述混合種群初始化策略初始化種群；

步驟3， 按照種群適應(yīng)度值對種群進行升序排序， 首先取出適應(yīng)度較差的1/3 種群數(shù)量的個體作為一個子種群， 再將剩下的種群平均分為2 個子種群；

步驟4， 將適應(yīng)度較差的子種群采用交叉、 變異的方式進行種群更新， 剩余的2 個種群分別采用標(biāo)準(zhǔn)Lévy 飛行和基于自適應(yīng)步長的改進Lévy 飛行進行種群更新；

步驟5， 將采用3 種更新方式得到的新一代種群合并為新的種群， 按發(fā)現(xiàn)概率Pa來淘汰更新后的解，采用隨機游走策略生成相同數(shù)量的解；

步驟6， 判斷是否達(dá)到最大迭代次數(shù)T， 如果未達(dá)到， 轉(zhuǎn)至步驟3； 否則， 轉(zhuǎn)至步驟7；

步驟7， 輸出種群最優(yōu)解。

3 實例應(yīng)用與分析

為了驗證文中所提出的ICS 算法求解ASP 問題的有效性， 現(xiàn)以某液壓產(chǎn)品制造企業(yè)所生產(chǎn)的鎖緊機構(gòu)齒條缸為實例進行驗證。 將一組標(biāo)準(zhǔn)件作為一體化零件進行考慮， 則該裝配體有24 個零件， 如圖6 所示。

圖6 鎖緊機構(gòu)齒條缸Fig.6 Locking mechanism rack cylinder

采用MATLAB 2017b 編程軟件實現(xiàn)改進布谷鳥算法（ICS）， 為了驗證改進布谷鳥算法的優(yōu)越性， 將它與標(biāo)準(zhǔn)布谷鳥算法（CS）［12］、 遺傳算法（Genetic Algorithm， GA）［4］、 粒 子 群 算 法 （Particle Swarm Optimization， PSO）［16］進行對比。 改進布谷鳥算法的參數(shù)設(shè)置為： 最大迭代次數(shù)T＝200， 種群規(guī)模N＝90， 交叉概率Pc＝0.8， 變異概率Pm＝0.2， 發(fā)現(xiàn)概率Pa＝0.3。 對比算法參數(shù)的設(shè)置參考相應(yīng)文獻(xiàn)。 改進布谷鳥算法采用文中所提出的混合種群初始化策略， 對比算法均采用隨機初始化策略。

圖7 給出了某次迭代過程中改進布谷鳥算法與其他3 種算法在求解ASP 問題中適應(yīng)度值與迭代次數(shù)的收斂曲線， 圖8 給出了每代適應(yīng)度平均值與迭代次數(shù)的收斂曲線。 可以看出： 基于優(yōu)化最大化可行序列和最小裝配成本的種群初始化策略的改進布谷鳥算法的初始解質(zhì)量明顯優(yōu)于其他3 種采取隨機初始化的算法。 并且， 改進布谷鳥算法的收斂速度和求解質(zhì)量亦更優(yōu)。 改進布谷鳥算法的最優(yōu)適應(yīng)度值最小（5.25）， 在尋優(yōu)能力上有較大的優(yōu)勢。 改進布谷鳥算法獲得最優(yōu)的可行序列為零件3→零件17→零件4→零件2→零件1→零件14→零件16→零件19→零件21→零件22→零件12→零件15→零件13→零件9→零件7→零件11→零件10→零件8→零件6→零件5→零件18→零件23→零件24→零件20。

圖7 適應(yīng)度值算法迭代Fig.7 Fitness value algorithm iteration

圖8 適應(yīng)度平均值算法迭代Fig.8 Fitness mean algorithm iteration

4 結(jié)論

為了求解裝配序列的規(guī)劃問題， 文中建立了考慮裝配序列的幾何可行性、 穩(wěn)定性（連接穩(wěn)定性和支撐穩(wěn)定性）、 聚合性和重定向性評價指標(biāo)的裝配關(guān)系模型和適應(yīng)度函數(shù)。 針對標(biāo)準(zhǔn)布谷鳥優(yōu)化算法在求解ASP 問題時收斂速度慢的問題， 對布谷鳥算法進行改進， 根據(jù)模型的特點設(shè)計了混合種群初始化策略， 改進了種群的進化策略。 最后以鎖緊機構(gòu)齒條缸為實例， 驗證了所提出的改進布谷鳥算法的可行性， 結(jié)果表明： 改進布谷鳥算法加快了算法的收斂速度， 具備較強的全局搜索能力和尋優(yōu)能力， 能有效地應(yīng)用到求解裝配序列規(guī)劃問題上。