基于改進引力搜索算法的異步并行拆卸序列規劃研究*

李佰霖,武攀旗,吳志超,付文龍

(1.三峽大學 電氣與新能源學院,湖北 宜昌 443002;2.三峽大學 梯級水電站運行與控制湖北省重點實驗室,湖北 宜昌 443002;3.哈爾濱電機廠有限責任公司,黑龍江 哈爾濱 150040)

0 引 言

機械設備維修涉及對維修目標件的拆卸,維修人員通過更換或維修有缺陷或磨損的零部件,使設備恢復到正常的運行狀態。

在執行拆卸操作之前,工程師需要確定可行且最優的拆卸順序[1],這有利于人力和物力的合理調度,縮短維修時間,提高維修效率。而尋找最佳的拆卸順序是一個拆卸序列規劃問題。然而由于設備的復雜約束,拆卸序列規劃是一個具有挑戰性的組合優化問題[2]。

早期的拆卸序列規劃研究主要傾向于圖論研究,如與或圖、有向圖和Petri網等方法。雖然這些圖適合數學分析,但隨著零部件數量的增多,問題的求解難度呈指數增長。于是許多學者利用圖形表示和啟發式算法相結合以解決該問題[3]。常見的啟發式算法有遺傳算法[4,5]、粒子群算法[6]和蟻群算法[7]等。

目前,拆卸序列規劃的研究主要集中在串行拆卸,即僅有一個操作者將零部件依次順序拆卸,而并行拆卸允許多人執行不同的拆卸任務。

在實際應用中,異步并行拆卸對于大型復雜設備的拆卸更具有重要意義。然而,異步并行拆卸存在并行拆卸序列長度不確定、非線性、拆卸操作區域干涉等問題,因此,異步并行拆卸比串行拆卸更復雜。

郭硯榮等人[8]提出了基于分布估計算法來求解并行拆卸序列規劃,但拆卸時間只考慮了零件的基本拆卸時間,而拆卸零件的準備時間也影響任務的完成時間。鄧明星等人[9]構建了異步并行拆卸的數學模型,使用改進的遺傳算法進行了求解,以方向改變作為準備時間。ZHU J F等人[10]提出了雙鏈編碼方法和譯碼算子,使用改進的蛙跳算法優化序列。郭鈞等人[11]以拆卸時間最短、利潤最大為優化目標,設計了三層鏈表的編碼方法,并使用改進的生物地理優化算法進行了求解。

上述研究雖然取得了很好的結果,但是還存在以下問題:(1)在拆卸準備時間上主要考慮了方向和工具改變造成的時間,對于體積較大的設備,拆卸工位的移動時間沒有考慮;(2)拆卸過程中假設無操作空間區域干涉,而在實際拆卸中工作區域的干涉必然導致拆卸不能按計劃進行[12];(3)許多算法在求解含有大量零部件的復雜設備時,收斂速度慢,易陷入局部最優,尋找到最優值的概率低。

引力搜索算法(GSA)是模擬個體之間由萬有引力引起相互作用的優化算法[13]。由于GSA具有良好的收斂特性和參數少的優點,它已廣泛應用于解決多個研究領域的組合優化問題。

在現有研究的基礎上,筆者綜合考慮拆卸作業空間沖突和零部件的幾何約束關系,分析影響拆卸時間的多個因素,并提出改進的引力搜索算法;最后,通過實例對改進的引力搜索算法求解異步并行拆卸序列規劃的優越性進行驗證。

1 問題的描述

1.1 優先約束模型建立

要獲得一個可行的拆卸序列,零部件之間的幾何約束和工作區域沖突是必須要考慮的。幾何約束是指設備中緊固件對零件的約束,以及零件沿d(d=±x,±y,±z)方向移動中受到其他零件的約束;工作區域沖突是指在并行拆卸過程中,參與拆卸的操作者所需工作空間上的干涉。

有向圖能簡潔有效地表達零部件之間的幾何約束關系,零部件的拆卸有向圖如圖1所示。

圖1 拆卸有向圖

在圖1中:節點表示零部件,有向邊的始端零部件約束箭頭指向的零部件。為了適應多個零部件一起拆卸的情況,圖1中又引入了組合節點的概念。如組合節點6表示其內部包含的零部件作為一個整體進行拆卸。在圖1中:使用粗實線來聚合有向線,使有向圖更簡潔。

工作區域的干涉關系通過文獻[14]提出的工作區域碰撞矩陣得到。

為了便于計算機處理分析,筆者將幾何約束關系和工作區域沖突轉變成矩陣的形式,數學表達式如下所示:

Mp={bi,j}n×n,Mc={ai,j}n×n

(1)

式中:n—零部件個數;Mp—幾何約束矩陣;Mc—工作區域沖突矩陣。

其中:

1.2 待拆卸零部件集合的獲取

筆者以維修目標件為起始點進行逆向遞歸搜索,以此來獲取待拆卸零部件。設S為待拆零部件集合,搜索集合S1,優先集合S2,其具體步驟如下:

步驟1。把檢修的目標零部件加入S1、S中;

步驟2。判斷S1是否為空集,如果為空,執行步驟5;否則,根據Mp搜索出S1中零部件的優先零部件,并將其放入S2中;

步驟3。判斷S2是否為空集,如果是執行步驟5;否則,將S2去重,然后把S2中與S中有交集的部分從S2中刪除,并把S2中的零部件放入S中;

步驟4。讓S2替換S1,使S2中的零部件成為新的搜索集合S1,返回步驟2;

步驟5。輸出待拆卸集合S。

1.3 數學模型

異步并行拆卸序列規劃問題可描述如下:設設備有s個待拆卸零部件,以總體拆卸時間最小為目標,并行序列總數為r,且滿足優先約束關系。

根據所描述問題,筆者做出以下假設:

(1)每個拆卸任務不可中斷;(2)拆卸過程無破壞;(3)每個操作者均可以獨立完成所分配的拆卸任務;(4)不同的操作者拆卸相同的零部件所用的基本拆卸時間相同。

根據上述問題描述,建立數學模型如下:

操作者之間無拆卸工作區域沖突滿足條件:

stpi≥etpj或stpj≥etpi,pj∈W[pi]

(2)

式中:stpi—拆卸零部件pi的開始時間;etpj—拆卸零部件pj的結束時間;W[pi]—零部件pi的工作區域沖突零部件集合。

零部件之間滿足幾何約束條件:

stpi≥TC[pi],?pi∈S

(3)

式中:TC[pi]—零部件pi的優先零部件集合中最大結束時間;S—待拆卸零部件集合,S={p1,p2,…,ps}，s—為了拆卸目標零部件必須要拆卸的零部件的數量。

目標函數:

(4)

結束時間為:

(5)

開始時間為:

(6)

(7)

(8)

式(6～8)表示不同約束情況下的開始時間計算公式。

準備時間為:

(9)

其中:

(10)

(11)

式中:dj-1,j—操作者k移動到下一個拆卸任務所需的距離,它由零部件之間的歐拉距離確定;vk—操作者k的移動速度。

根據不同的工具類型,拆卸工具單次變換時間標準如表1所示。

表1 拆卸工具變換時間標準 (單位:s)

2 改進的引力搜索算法

在GSA中,搜索空間中的每個個體都作為一個待優化的解決方案,并根據其質量衡量解的優劣。在迭代的過程中,低質量的個體會向高質量的個體移動,在該過程中尋找最優值。

由于標準的引力搜索算法是用來解決連續優化問題,因此筆者提出了改進的引力搜索算法,以適應異步并行拆卸序列規劃的離散性,并對其進行求解。

2.1 個體位置的編碼和初始群體的產生

有效的編碼方式可以避免不可行序列的產生。筆者針對異并行拆卸序列的特點,采用兩段式編碼結構來構成個體的位置:X={X1,X2}。X1={p1,p2,…,pi,…,ps}代表一個可行拆卸任務序列。X2={k1,…,ki,…,ks,}代表操作者序列,其中ki∈{1,2,…,r}。兩個序列中相同位置的元素是一一對應的,即零部件pi由操作者ki拆卸。

一個可行個體的生成步驟如下:

步驟1。更新幾何約束矩陣Mp,Mp只包含待拆卸零部件集合S中零部件之間的幾何約束關系;定義拆卸任務序列X1,當前可拆卸集合A,X1=?,A=?;

步驟2。根據幾何約束矩陣Mp獲得當前可拆卸零部件集合A;

步驟3。從A中隨機選擇零部件pi放在X1的第一個空缺位置;

步驟4。更新幾何約束矩陣Mp,將pi所在的列置零,解除對其他零部件的約束;

步驟5。判斷集合A是否為空,如果是，執行步驟6,否則執行步驟2;

步驟6。根據操作者的數量隨機產生X2;

步驟7。輸出結果X。

假設種群規模為N,重復以上步驟1～7N次即可初始化種群。種群中第i個粒子表示為Xi=(X1,X2),i=1,2,…,N。

2.2 個體位置的解碼

根據異步并行拆卸的特點,操作者k完成一次拆卸任務后,由于幾何約束和空間區域干涉可能需要等待其他操作者完成任務之后才能繼續拆卸,上述情況對異步并行序列的求解造成困難,因此,筆者提出了一種高效的解碼方法。

求解零部件結束時間的具體流程如下:

步驟1。定義F為已拆卸零部件集合,ck為操作者k正在執行的任務編號;F=?,ck=1,k∈{1,2,…,r};

步驟2。根據個體的編碼X,確定每個操作者的拆卸任務序列;

步驟10。若操作者k所有拆卸任務已完成,則該操作者停止拆卸,否則ck=ck+1;

步驟11。若所有零部件的完工時間已被求出,結束解碼過程,否則返回步驟3。

2.3 個體的質量

較重質量的個體表示更有效的解決方案。通過以下公式更新質量:

(12)

(13)

式中:fi(t)—個體i在第t代的目標函數值;worst(t)—最差適應度值;best(t)—最佳適應度值;Mi(t)—第i個個體的質量。

其中:

best(t)=min{fi(t)},j∈(1,…,N)worst(t)=max{fi(t)},j∈(1,…,N)

(14)

2.4 個體的進化

為了在全局探索和局部優化之間達到平衡,GSA中只有Kbest中的個體作用于其他個體,使種群中的個體向更優的個體移動。Kbest是一組較大質量個體的集合,并且隨著迭代的進行而減少。

筆者采用交叉的方式更新個體,根據個體質量的大小采用正比例選擇策略從Kbest中選擇個體來構成交叉集合G,針對兩段式編碼結構形式分別對X1、X2采用不同的交叉策略來保證新個體的可行性。

在第t代,Kbest中個體的數量為b,把即將更新的個體放入Kbest中,Kbest={KX1,KX2,…,KXb+1}。個體的質量在數值上等于個體的選擇概率。

根據下式確定Kbest中每個個體的累計概率:

(15)

式中:Pi—Kbest中第i個個體的累計概率,i=(1,2,…,b+1);Mj—Kbest中第j個個體的質量。

設初始值P0=0,產生s個隨機數ξa,ξa∈(0,Pb+1),a=1,2,…,s。當Pi-1≤ξa≤Pi,則從Kbest中選擇個體KXi,并把其放入交叉集合G中。每一個ξa對應Kbest中的一個個體,質量越大,被選擇的次數越多。最后G={GX1,GX2,…,GXs}包含s個個體。

每個GXi的X1和X2中的相應變量分別產生新解決方案中的一個變量。

關于X2交叉更新的數學模型如下:

(16)

X2采用上述模型的交叉方式,但對于X1需要采用優先關系保留的交叉方式,使交叉后的序列依舊滿足優先關系。

X1的具體交叉方法如下:從G中選擇個體GXi,然后在GXi的X1中從左到右尋找新個體中未出現的變量,把找到的第一個變量放在新個體的X1的第一個空缺位置;遍歷G中的每一個個體重復交叉過程,直到完整的X1的生成。

生成新個體的兩段式編碼對應的交叉示意圖如圖2所示。

圖2 交叉示意圖

在圖2中,操作者序列無優先拆卸關系,其元素來自交叉個體對應位置上的元素。

對于X1,其步驟為:(1)GX1的X1的第一個元素1被選擇;(2)元素3未在新個體的X1中,且按從左到右的順序被首先找到,因此,把3放在新個體的X1的第一個空缺位置。

2.5 逃脫算子

算法在搜索最優解的過程中,當種群中的粒子全部聚集到一起時,種群就會陷入局部最優解。

為了在種群陷入局部最優時種群具有一定的尋優能力,筆者提出了逃脫算子。在種群收斂時:

(1)從當前種群中選擇c1個優質解加入交叉集合G中;

(2)根據第2.1節新生成c2個新的解作為多樣性解放入交叉集合G中;

(3)按照第2.4節所述方法更新個體。

值得注意的是c1+c2=s。當種群中worst(t)等于best(t)時,認為算法已經陷入局部最優。

2.6 算法流程

綜上所述,筆者在綜合考慮各類因素的情況下，提出一種改進算法。

算法的流程圖如圖3所示。

圖3 算法流程圖

3 實驗及結果分析

筆者以水輪機主軸密封為例進行實驗,以驗證筆者所提GSA算法的有效性。

所有的試驗都是在MATLAB R2019b軟件上進行算法編程,求解環境為Win10 Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz。

水輪機主軸密封爆炸圖如圖4所示。

圖4 水輪機主軸密封爆炸圖

水輪機主軸密封有向圖如圖5所示。

圖5 水輪機主軸密封有向圖

零部件的拆卸信息如表2所示。

表2 零部件的基本拆卸信息

拆卸的主要參數是指定的目標零部件x和并行度r。

根據不同的操作者數量和維修的目標零部件共設置4個案例,設操作者的移動速度為0.5 m/s,各案例的基本信息如表3所示。

表3 測試案例的基本信息

3.1 參數分析

從上述內容可知,c1和c2的取值會影響種群優質解和多樣性解的平衡,進而影響最優值的求解。為了確定合適的c1和c2,對比5組不同的值進行實驗分析。

每組的取值如表4所示(其中,c1、c2取整數)。

表4 5組c1、c2的取值

以T2為實驗對象,種群大小為20,每組運行10次,算法迭代100次,每組得到的10個解的分布如圖6所示。

由圖6可知:c1=0.1×s時算法沒有找到最優的解,因為當c1太小時,整個交叉集合G中優質解的個數太少,種群依舊處于全局探索階段;

圖6 不同c1值的運行結果

當c1在0.2×s到0.6×s之間時,隨著c1的增大,種群開始局部搜索并取得較好的解,而在c1=0.4×s時算法在全局探索和局部尋優之間取得了平衡,求解出了良好的解;

當c1=0.8×s時,解的最優值很差,這是因為種群缺乏多樣性易陷入局部最優。

因此,改進引力搜索算法中設置c1=0.4×s,c2=0.6×s。

3.2 算法對比及結果分析

為了進一步驗證筆者所提算法的優越性,筆者將該算法與SSO[15]和GA[16]算法進行了對比。

根據表3所示案例進行了測試,種群大小為20,每個算法獨立運行20次,迭代次數設置為100。對比算法采用相同的問題模型、編碼方式和解碼規則。

不同算法最優值的收斂曲線如圖7所示。

圖7 3種算法在不同測試案例中最優值的收斂曲線

各組案例的測試結果如表5所示。

表5 3種算法在不同測試案例中的對比結果

在測試T1時,由于拆卸規模過小,3種算法尋到的最優值近似,但GSA整體質量較好;

在測試中等規模T2時,GSA能夠求解到更好的完工時間,但運行時間大于SSO;

通過測試T3和T4,在求解大規模案例時,GSA的最優值、平均值明顯優于其他2種算法,并且隨著拆卸人員的增加,拆卸完成時間明顯縮短。

4 結束語

針對異步并行拆卸序列規劃復雜的建模和求解效率低的問題,筆者考慮了實際拆卸中多人操作空間區域干涉的問題,構建了符合實際拆卸所花費時間的優化目標模型,對異步并行拆卸序列規劃的拆卸模型和求解算法進行了研究,提出了一種基于改進引力搜索算法的異步并行拆卸序列規劃方法。

首先,建立了優先約束模型,逆向搜索出了最小待拆卸零部件集合;然后,建立了異步并行拆卸序列規劃的數學模型,構造了其編碼和解碼方法;最后,以水輪機主軸密封檢修為例進行了實驗,以驗證GSA算法的有效性,并將其結果與采用傳統算法所得結果進行對比,以證明新方法的優越性。

研究結論如下:

(1)基于GSA在解決組合優化方面的優勢,提出了改進的引力搜索算法;將所提算法與SSO和GA算法進行了對比。測試結果表明,在求解大規模案例時,GSA的最優值、平均值明顯優于其他兩種算法,并且隨著拆卸人員的增加,拆卸完成時間明顯縮短;

(2)通過水輪機主軸密封實例,驗證了所提算法在求解大型復雜設備維修拆卸中的有效性,所得到的結果可以很好地指導工業應用中的維修拆卸。

在未來,筆者將要研究不確定因素,以建立一個隨機的拆卸序列規劃模型,如拆卸零部件的質量、操作人員的熟練程度、拆卸零部件的狀況等,使拆卸模型更加符合實際工業現場。