秦紅斌, 王玲軍, 唐紅濤, 孔仁杰
(武漢理工大學(xué)機(jī)電工程學(xué)院, 湖北武漢 430070)
在制造業(yè)中, 產(chǎn)品裝配過(guò)程所耗費(fèi)的時(shí)間占整個(gè)生產(chǎn)時(shí)間的20%~50%, 產(chǎn)品的裝配成本耗費(fèi)超過(guò)40%[1]。 裝配序列規(guī)劃(Assembly Sequence Planning,ASP) 是產(chǎn)品設(shè)計(jì)和制造的重要環(huán)節(jié), 裝配序列的優(yōu)化對(duì)降低生產(chǎn)成本、 提高產(chǎn)品裝配質(zhì)量和生產(chǎn)效率至關(guān)重要。 裝配序列規(guī)劃已經(jīng)被證明是一個(gè)典型的NPhard 問(wèn)題[2-3]。 因此, 國(guó)內(nèi)外的諸多學(xué)者對(duì)ASP 問(wèn)題展開(kāi)大量的研究。 在已有的解決ASP 問(wèn)題的方法中,智能優(yōu)化算法展現(xiàn)了其獨(dú)有的優(yōu)勢(shì)。 BONNEVILLE等[4]首次將遺傳算法應(yīng)用于求解ASP 的問(wèn)題中, 隨后蟻群優(yōu)化算法[5]、 粒子群優(yōu)化算法[6]等都被應(yīng)用于求解ASP 問(wèn)題。
劉冬等人[7]針對(duì)基本粒子群算法早熟的缺點(diǎn), 提出了變種群策略-粒子群優(yōu)化算法(VPS-PSO) 用于求解ASP 問(wèn)題, 避免了種群陷入局部最優(yōu)。 HAN等[8]提出了一種結(jié)合共生生物搜索(Symbiotic Organ?isms Search, SOS) 和蟻群優(yōu)化(Ant Clony Optimiza?tion, ACO) 的SOS-ACO 算法來(lái)計(jì)算最優(yōu)或者接近最優(yōu)的裝配序列。 孟冠軍、 楊大春[9]建立遺傳-蟻群算法求解ASP 問(wèn)題, 以加快算法的收斂速度。 任云、劉丹[10]提 出 一 種 將 天 牛 須 搜 索 (Beetle Antennae Search, BAS) 算 法 和 閃 電 搜 索 算 法 (Lightning Search Algorithm, LSA) 混合的BAS-LSA 混合算法,結(jié)合天牛須算法較優(yōu)的局部搜索能力和閃電搜索算法較優(yōu)的全局搜索能力, 提高了求解精度。 但上述研究仍存在以下不足: 在建立裝配關(guān)系模型時(shí)未考慮零件之間的支撐關(guān)系, 或者在建立適應(yīng)度函數(shù)時(shí)未考慮待裝配零件與所有已裝配好的零件之間的裝配關(guān)系。 布谷鳥(niǎo)優(yōu)化算法(Cuckoo Search, CS) 是由YANG 和DEB[11]提出的一種群智能優(yōu)化算法, 也是一種新型元啟發(fā)式算法。 布谷鳥(niǎo)算法結(jié)構(gòu)簡(jiǎn)單、 算法參數(shù)少、易于實(shí)現(xiàn), 兼?zhèn)漭^優(yōu)的全局搜索和局部搜索能力。 雍升[12]將布谷鳥(niǎo)算法運(yùn)用到求解ASP 問(wèn)題上, 但是群體中每只布谷鳥(niǎo)都執(zhí)行Lévy 飛行, 并且飛行步長(zhǎng)是一個(gè)定值, 缺乏自適應(yīng)性, 導(dǎo)致收斂速度變慢。 針對(duì)以上問(wèn)題, 本文作者建立考慮裝配序列的幾何可行性、 穩(wěn)定性、 聚合性、 重定向性的裝配關(guān)系模型和適應(yīng)度函數(shù), 提出一種改進(jìn)布谷鳥(niǎo)算法 (Improved Cuckoo Search, ICS), 設(shè)計(jì)編碼方案, 改進(jìn)種群初始化和種群進(jìn)化策略, 加快解的收斂速度, 使其具有較強(qiáng)的尋優(yōu)能力。
產(chǎn)品的裝配序列有多種方案可供選擇, 裝配序列會(huì)影響裝配成本和裝配效率, 在評(píng)價(jià)裝配序列的優(yōu)劣時(shí), 應(yīng)首先考慮裝配序列的幾何可行性, 即裝配序列在幾何空間內(nèi)可進(jìn)行裝配, 再綜合考慮裝配序列的穩(wěn)定性、 聚合性、 重定向性。
幾何可行性是指在裝配體中裝配零件Pi時(shí), 已裝配好的零件是否對(duì)零件Pi產(chǎn)生干涉。 通常情況下,零件是按d(k)={+x,-x,+y,-y,+z,-z}6 個(gè)裝配方向中一個(gè)方向進(jìn)行裝配的, 建立零件在6 個(gè)方向的干涉矩陣[13], 如式(1) 所示:
其中:pij表示零件Pj沿k方向裝配時(shí)與零件Pi的干涉情況, 若pij=1, 表示零件Pj沿k方向裝配時(shí)與零件Pi發(fā)生干涉; 若pij=0, 則無(wú)干涉。 矩陣如式(2) 所示:
定義Iik為零件Pi沿k方向裝配時(shí)與已裝好的零件的干涉值之和, 若Iik=0, 則零件Pi可以沿k方向進(jìn)行裝配, 否則, 不能沿k方向進(jìn)行裝配。Iik的計(jì)算公式如式(3) 所示:
對(duì)于一個(gè)裝配序列, 若V1=0, 則證明裝配體中所有零件都無(wú)干涉, 為可行裝配序列; 若V1≠0, 則證明為幾何不可行裝配序列。
穩(wěn)定性包含2 個(gè)方面: (1) 零件之間的連接穩(wěn)定性, 通過(guò)建立連接矩陣來(lái)表示裝配體中各零件之間的連接關(guān)系, 用于判斷連接穩(wěn)定性; (2) 零件在裝配過(guò)程中重力方向上的支撐穩(wěn)定性, 通過(guò)建立支撐矩陣來(lái)表示零件之間支撐關(guān)系。 裝配序列穩(wěn)定性的量化指標(biāo)V2的計(jì)算公式如式(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)定連接表示兩零件之間通過(guò)連接件連接, 具備穩(wěn)定的連接關(guān)系。
裝配序列連接穩(wěn)定性指標(biāo)V21的求解算法如下:
①參數(shù)初始化, 令V21=0,S1=0,S1為算法計(jì)算中間變量;
②從連接矩陣C中取出零件Pi與前i-1 個(gè)已裝配好的零件連接信息, 并將它置于N1中,N1為算法臨時(shí)存儲(chǔ)信息的變量;
③若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ù)值越小, 代表裝配過(guò)程中穩(wěn)定連接越多, 裝配過(guò)程中的穩(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為算法計(jì)算中間變量;
②從支撐矩陣M中取出零件Pi與前i-1 個(gè)已裝配好的零件支撐信息, 并將它置于N2中,N2為算法臨時(shí)存儲(chǔ)信息的變量;
③如果N2存在值為0, 則S2=0; 否則,S2=1;
④V22=V22+S2;
⑤i=i+1, 如果i<n, 轉(zhuǎn)至步驟②; 否則轉(zhuǎn)至步驟⑥;
⑥結(jié)束。
由上述可知:V22的數(shù)值越小, 則代表裝配過(guò)程中在重力方向的支撐越多, 裝配穩(wěn)定性越好。
聚合性表示裝配過(guò)程中零件裝配工具的改變次數(shù), 在裝配過(guò)程中應(yīng)該盡可能地減少裝配工具的改變次數(shù), 有助于降低裝配成本。 裝配工具的改變定量計(jì)算如式(8) 所示:
裝配過(guò)程中裝配工具的改變次數(shù)V3越小, 裝配序列的聚合性越好, 裝配序列越優(yōu)。
重定向性是指在裝配過(guò)程中零件裝配方向的改變次數(shù), 裝配過(guò)程中應(yīng)降低裝配方向的改變次數(shù), 提高裝配效率。 裝配方向的改變定量計(jì)算方式如式(9)所示:
裝配過(guò)程中裝配方向的改變次數(shù)V4越小, 裝配序列的重定向性越好, 裝配序列越優(yōu)。
綜上所述, 綜合考慮裝配序列的幾何可行性、 裝配序列的穩(wěn)定性、 裝配序列的聚合性、 裝配序列的重定向性4 個(gè)評(píng)價(jià)指標(biāo), 通過(guò)量化方法建立適應(yīng)度函數(shù), 如式(10) 所示:
其中:ωi(i=1, 2, 3, 4) 為權(quán)重系數(shù);V1、V2、V3、V4分別表示裝配序列的幾何可行性、 穩(wěn)定性、 聚合性和重定向性評(píng)價(jià)指標(biāo)。 適應(yīng)度值F越小,裝配序列越好。
基于被發(fā)現(xiàn)概率Pa來(lái)淘汰更新后的解, 采用隨機(jī)游走的局部搜索策略生成相同數(shù)量的解補(bǔ)充種群,保持種群數(shù)量的一致, 如式(17) 所示:
標(biāo)準(zhǔn)布谷鳥(niǎo)算法適用于求解連續(xù)性問(wèn)題, 而裝配序列規(guī)劃問(wèn)題是離散型, 無(wú)法直接應(yīng)用求解。 為此,文中采用隨機(jī)鍵和最小位置規(guī)則(Smallest Position Value, SPV) 的方法, 對(duì)編碼方式進(jìn)行處理, 從而建立起個(gè)體與裝配序列的映射關(guān)系。 如圖1 所示,SPV 規(guī)則為原向量的每個(gè)元素生成隨機(jī)值, 原向量的元素根據(jù)隨機(jī)值的大小經(jīng)過(guò)升向排序, 得到一個(gè)新向量。
圖1 編碼過(guò)程Fig.1 Encoding process
ASP 問(wèn)題涉及多零件的裝配順序、 裝配方向選擇、 裝配工具選擇問(wèn)題, 因此, 文中采用基于零件編號(hào)、 裝配方向、 裝配工具的3 層編碼規(guī)則。 編碼時(shí)首先生成零件編號(hào)序列(Number), 然后根據(jù)所生成的零件編號(hào)序列對(duì)零件的裝配方向(Direction)、 裝配工具(Tool) 進(jìn)行選擇。 裝配方向、 裝配工具層用于記錄該條裝配序列的裝配信息。件4 的裝配方向也為+y。 如果后續(xù)零件的可行裝配方向無(wú)法與前一位保持一致, 例如零件2 中可行裝配方向沒(méi)+y, 則考慮后續(xù)零件5 的可行裝配方向, 選擇零件2 的裝配方向?yàn)椋玿, 同理可得零件5 和零件1 的裝配方向分別為+x、+x, 該裝配序列的裝配方向分別為{+y,+y,+x,+x,+x} 。 裝配工具與裝配方向的選擇機(jī)制一樣, 可得該裝配序列的裝配工具分別為{T3,T3,T3,T1,T3} 。
結(jié)合編碼過(guò)程可得: 零件裝配順序?yàn)?→3→6→2→7→1→4, 裝配方向分別為{- x,+x,+x,+y,+z,-y,-y} , 裝配工具分別為{T1,T2,T3,T2,T2,T1,T3} 。
為了提高初始化種群的質(zhì)量和保證種群的多樣性,文中設(shè)計(jì)了混合種群初始化策略進(jìn)行種群的初始化(包括幾何不可行序列), 即: (1) 基于最大化可行序列和最小裝配成本的種群初始化; (2) 隨機(jī)初始化策略。 2 種策略生成的初始化種群數(shù)量分別為50%。
文中的編碼采用基于零件編號(hào)、 裝配方向、 裝配工具的3 層編碼, 在裝配模型評(píng)價(jià)指標(biāo)中, 裝配序列的幾何可行性、 穩(wěn)定性評(píng)價(jià)指標(biāo)在零件編號(hào)層確定后, 就可以通過(guò)對(duì)應(yīng)的算法計(jì)算出來(lái)。 最大化可行序列和最小裝配成本策略體現(xiàn)在對(duì)裝配方向和裝配工具的合理選擇上, 隨機(jī)策略則是對(duì)零件的裝配方向和裝配工具進(jìn)行隨機(jī)選擇。 如圖2 所示, 有裝配序列3→4→2→5→1, 裝配方向?qū)訛榇肆慵c前一個(gè)零件不發(fā)生干涉的可裝配方向, 裝配工具層為此零件裝配時(shí)所需要使用的工具。
圖2 優(yōu)化策略Fig.2 Optimizing strategy
在為首位零件選擇裝配方向和裝配工具時(shí)應(yīng)考慮對(duì)后一位零件的影響, 如為零件3 選擇時(shí)裝配方向應(yīng)在{- x,+y,+z,-z} 中隨機(jī)選擇。 現(xiàn)隨機(jī)選為+y方向, 后續(xù)選擇零件的裝配方向應(yīng)盡量在滿足裝配幾何可行性的前提下和前一位的零件保持一致。 零
在布谷鳥(niǎo)算法中, 群體中每只布谷鳥(niǎo)都執(zhí)行Lévy 飛行, 會(huì)造成收斂速度變慢, 并且標(biāo)準(zhǔn)Lévy 飛行中的步長(zhǎng)是一個(gè)定值, 缺乏自適應(yīng)性, 同樣會(huì)導(dǎo)致收斂速度變慢。 針對(duì)此種情況, 文中將布谷鳥(niǎo)種群分為3 個(gè)子群, 分別采用不同的種群進(jìn)化策略, 按種群的適應(yīng)度值進(jìn)行升序排序。 首先取出適應(yīng)度較差的1/3 種群數(shù)量的布谷鳥(niǎo)作為一個(gè)子群, 采用交叉、 變異的方式來(lái)代替Lévy 飛行進(jìn)行更新, 其中交叉相當(dāng)于Lévy 飛行的“長(zhǎng)飛行”, 在全局的范圍內(nèi)進(jìn)行搜索; 變異相當(dāng)于Lévy 飛行中的“短飛行”, 在局部范圍進(jìn)行搜索, 可以減少Lévy 飛行的次數(shù), 加快收斂速度; 然后再將剩下的種群隨機(jī)分為2 個(gè)子群, 分別采用固定步長(zhǎng)的標(biāo)準(zhǔn)Lévy 飛行和基于自適應(yīng)步長(zhǎng)的改進(jìn)Lévy 飛行進(jìn)行種群更新; 最后將更新后的3 個(gè)子群合并生成的新一代種群。
采用部分匹配交叉(Partially-Matched crossover,PMX) 的方式進(jìn)行交叉操作[14], 具體操作流程如圖3 所示。
圖3 PMX 交叉操作Fig.3 PMX crossover operation
從種群中隨機(jī)抽取2 個(gè)個(gè)體Z1和Z2作為父代,首先隨機(jī)選取2 個(gè)交叉的點(diǎn), 將2 個(gè)點(diǎn)之間的部分進(jìn)行交叉, 再將剩余的部分采用復(fù)制或相匹配的方式進(jìn)行交叉替換。 如圖3 所示, 父代Z1中214 被選中,父代Z2中357 被選中, 那么2 與3、 1 與5、 4 與7 相匹配。 首先將214 與357 分別加入子代Z和子代Z中, 再將其他位置上的編號(hào)復(fù)制到子代中, 若子代中已經(jīng)存在此編號(hào), 則運(yùn)用匹配規(guī)則將匹配后的編號(hào)復(fù)制到子代中, 從而得到新的子代。
采用隨機(jī)選取2 個(gè)零件位置進(jìn)行互換的變異操作方式, 具體操作如圖4 所示, 隨機(jī)選取的第一個(gè)是位置2, 第二個(gè)是位置6, 將位置2 與6 的零件編號(hào)互換, 從而得到新的個(gè)體Zf2。
圖4 互換變異操作Fig.4 Swap mutation operation
通過(guò)算法的迭代次數(shù)控制飛行步長(zhǎng): 在算法初期, 應(yīng)進(jìn)行較大步長(zhǎng)的Lévy 飛行, 有助于提高全局搜索能力, 避免陷入局部最優(yōu); 在算法后期, 應(yīng)進(jìn)行較小步長(zhǎng)的Lévy 飛行, 有助于提高搜索精度。 文中步長(zhǎng)因子α的取值如式(18) (19) 所示[15]:
其中:αmax表示步長(zhǎng)因子的最大值;αmin表示步長(zhǎng)因子的最小值;t為當(dāng)前迭代次數(shù);T為迭代總次數(shù)。 經(jīng)文獻(xiàn)[15]實(shí)驗(yàn)驗(yàn)證,αmax取0.5、αmin取0.05效果最佳。
改進(jìn)布谷鳥(niǎo)算法流程如圖5 所示, 具體步驟如下:
圖5 ICS 算法流程Fig.5 ICS algorithm flow
步驟1, 對(duì)算法相關(guān)參數(shù)進(jìn)行初始化, 包括種群數(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)度值對(duì)種群進(jìn)行升序排序, 首先取出適應(yīng)度較差的1/3 種群數(shù)量的個(gè)體作為一個(gè)子種群, 再將剩下的種群平均分為2 個(gè)子種群;
步驟4, 將適應(yīng)度較差的子種群采用交叉、 變異的方式進(jìn)行種群更新, 剩余的2 個(gè)種群分別采用標(biāo)準(zhǔn)Lévy 飛行和基于自適應(yīng)步長(zhǎng)的改進(jìn)Lévy 飛行進(jìn)行種群更新;
步驟5, 將采用3 種更新方式得到的新一代種群合并為新的種群, 按發(fā)現(xiàn)概率Pa來(lái)淘汰更新后的解,采用隨機(jī)游走策略生成相同數(shù)量的解;
步驟6, 判斷是否達(dá)到最大迭代次數(shù)T, 如果未達(dá)到, 轉(zhuǎn)至步驟3; 否則, 轉(zhuǎn)至步驟7;
步驟7, 輸出種群最優(yōu)解。
為了驗(yàn)證文中所提出的ICS 算法求解ASP 問(wèn)題的有效性, 現(xiàn)以某液壓產(chǎn)品制造企業(yè)所生產(chǎn)的鎖緊機(jī)構(gòu)齒條缸為實(shí)例進(jìn)行驗(yàn)證。 將一組標(biāo)準(zhǔn)件作為一體化零件進(jìn)行考慮, 則該裝配體有24 個(gè)零件, 如圖6 所示。
圖6 鎖緊機(jī)構(gòu)齒條缸Fig.6 Locking mechanism rack cylinder
采用MATLAB 2017b 編程軟件實(shí)現(xiàn)改進(jìn)布谷鳥(niǎo)算法(ICS), 為了驗(yàn)證改進(jìn)布谷鳥(niǎo)算法的優(yōu)越性, 將它與標(biāo)準(zhǔn)布谷鳥(niǎo)算法(CS)[12]、 遺傳算法(Genetic Algorithm, GA)[4]、 粒 子 群 算 法 (Particle Swarm Optimization, PSO)[16]進(jìn)行對(duì)比。 改進(jìn)布谷鳥(niǎo)算法的參數(shù)設(shè)置為: 最大迭代次數(shù)T=200, 種群規(guī)模N=90, 交叉概率Pc=0.8, 變異概率Pm=0.2, 發(fā)現(xiàn)概率Pa=0.3。 對(duì)比算法參數(shù)的設(shè)置參考相應(yīng)文獻(xiàn)。 改進(jìn)布谷鳥(niǎo)算法采用文中所提出的混合種群初始化策略, 對(duì)比算法均采用隨機(jī)初始化策略。
圖7 給出了某次迭代過(guò)程中改進(jìn)布谷鳥(niǎo)算法與其他3 種算法在求解ASP 問(wèn)題中適應(yīng)度值與迭代次數(shù)的收斂曲線, 圖8 給出了每代適應(yīng)度平均值與迭代次數(shù)的收斂曲線。 可以看出: 基于優(yōu)化最大化可行序列和最小裝配成本的種群初始化策略的改進(jìn)布谷鳥(niǎo)算法的初始解質(zhì)量明顯優(yōu)于其他3 種采取隨機(jī)初始化的算法。 并且, 改進(jìn)布谷鳥(niǎo)算法的收斂速度和求解質(zhì)量亦更優(yōu)。 改進(jìn)布谷鳥(niǎo)算法的最優(yōu)適應(yīng)度值最?。?.25), 在尋優(yōu)能力上有較大的優(yōu)勢(shì)。 改進(jìn)布谷鳥(niǎo)算法獲得最優(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
為了求解裝配序列的規(guī)劃問(wèn)題, 文中建立了考慮裝配序列的幾何可行性、 穩(wěn)定性(連接穩(wěn)定性和支撐穩(wěn)定性)、 聚合性和重定向性評(píng)價(jià)指標(biāo)的裝配關(guān)系模型和適應(yīng)度函數(shù)。 針對(duì)標(biāo)準(zhǔn)布谷鳥(niǎo)優(yōu)化算法在求解ASP 問(wèn)題時(shí)收斂速度慢的問(wèn)題, 對(duì)布谷鳥(niǎo)算法進(jìn)行改進(jìn), 根據(jù)模型的特點(diǎn)設(shè)計(jì)了混合種群初始化策略, 改進(jìn)了種群的進(jìn)化策略。 最后以鎖緊機(jī)構(gòu)齒條缸為實(shí)例, 驗(yàn)證了所提出的改進(jìn)布谷鳥(niǎo)算法的可行性, 結(jié)果表明: 改進(jìn)布谷鳥(niǎo)算法加快了算法的收斂速度, 具備較強(qiáng)的全局搜索能力和尋優(yōu)能力, 能有效地應(yīng)用到求解裝配序列規(guī)劃問(wèn)題上。