基于智能水滴算法的裝夾規(guī)劃方法

高 博 胡曉宇 彭珍瑞 劉君泉

蘭州交通大學機電工程學院，蘭州，730070

0 引言

計算機輔助工藝規(guī)劃(computer aided process planning，CAPP)是計算機輔助制造(computer aided manufacturing，CAM)和計算機輔助設計(computer aided design，CAD)之間的橋梁[1]。裝夾規(guī)劃作為計算機輔助工藝規(guī)劃的重要組成部分，包括以下幾個重要功能：確定零件的加工特征及其分組排序，識別加工基準面和規(guī)劃裝夾所需的各個夾具等。裝夾規(guī)劃的優(yōu)劣決定著零件的可加工性和加工質量，同時也關系到制造成本。但因為裝夾規(guī)劃本身的多因性及制造資源所具有的多樣性，使得裝夾規(guī)劃問題具有一定的復雜性和特殊性[2]。

為了解決加工制造中的裝夾規(guī)劃問題，傳統(tǒng)方法有很多，如基于圖論的方法[3-4]、基于聚類分析的方法[5]等。同時，一些研究者提出運用現代智能優(yōu)化算法來解決該問題，其中包括遺傳算法[6-7]、粒子群算法[8]、蟻群算法[9-10]和模擬退火算法[11]等。但上述智能優(yōu)化方法存在一定的局限性，如多以加工特征為主要著手點，但對制造資源間的各種約束考慮欠妥，可能存在加工順序沖突問題；有些方法對加工特征中的加工階段(精、粗加工等)缺乏考慮。同時，上述方法在尋求最優(yōu)裝夾方案的效率上不是很高，在加工資源的利用優(yōu)化方面仍有改進的地方。

針對上述問題，本文在考慮裝夾的可行性和連續(xù)性的前提下，提出一種基于智能水滴(intelligent water drops，IWD)算法的裝夾規(guī)劃方法。通過定義操作單元和構建裝夾約束矩陣，利用智能水滴算法的全局搜索能力，將獨特的迭代機制與裝夾規(guī)劃相結合來尋求較好的規(guī)劃方案。

1 裝夾序列規(guī)劃問題的相關描述

1.1 操作單元的定義

針對加工工序較為復雜、生產批量較大的零部件，在裝夾規(guī)劃中，需要對這些零件不同的加工特征(如孔、槽、平面、臺階和型腔等)進行分析，結合機床和刀具等所需的加工資源，以及刀具接近方向等裝夾特征，將各個加工特征拆解為加工操作單元，通過對這些操作單元進行分組來形成合理的加工次序，以此來構建零部件加工的工序及工步。

操作單元由加工階段、備選機床、刀具接近方向以及備選刀具構成，其表達形式如下：

ui={O,M,D,T}

(1)

u={u1,u2,…,uk}

i=1，2，…，k

其中，ui表示不同的操作單元，k為操作單元的個數，O表示加工特征的各個精粗加工階段，M表示備選機床，D表示加工特征中刀具的接近方向，T表示備選刀具。

1.2 操作單元的約束關系

裝夾規(guī)劃中，各操作單元之間的加工先后排序受到定位基準、幾何特征、生產成本等因素的約束。同時，操作單元的排序也受到待加工零件的精度要求的影響，如精加工過程中的操作單元需放在粗加工及半精加工的后面。

綜合上述約束條件，為保證裝夾順序的合理性，可構建一個n階方陣M來表示操作單元間的順序約束關系：

(2)

1.3 裝夾序列規(guī)劃的數學模型

裝夾規(guī)劃問題是一個典型的NP組合優(yōu)化問題，通過對操作單元的分組，以實現獲得最少的裝夾次數以及相同加工特征盡可能分配在一次加工的目的。

假定{u1，u2，…，uk}為待加工零件的操作單元。設第m次規(guī)劃后所產生的結果為集合Sm={Sm,1，Sm,2，…，Sm,n}，其中n為零件的裝夾次數，則裝夾規(guī)劃問題的目標函數如下：

f(Sm)=minn

(3)

同時，各操作單元滿足以下約束條件：

u1(M)∩u2(M)∩…∩ui(M)≠?，?ui∈Sm,n

(4)

u1(D)∪u2(D)∪…∪ui(D)?{D}，?ui∈Sm,n

(5)

(6)

式(4)表示不同操作單元可以選取同一個機床；式(5)表示所有操作單元的刀具接近方向(tool approach direction,TAD)需從刀具接近方向的集合中選??；式(6)表示各個操作單元需符合加工順序約束條件。

2 基于智能水滴算法的裝夾規(guī)劃方法

2.1 智能水滴算法的基本原理

在物理界中，河流可以視為由無數個小水滴所構成，各個水滴在地球引力的作用下會持續(xù)地流動。水滴在流動過程中會改變河床，同時河床也會影響到水滴的流動[12]。在自然界中水滴所具有的特征包括：①水滴在流動過程中會沖刷掉河床中的部分泥土；②河床中被沖刷掉的泥土量與水滴的流動速度成正比；③流經路徑中的泥土量越少，則水滴在該路徑間獲得的速度增量就越大；④水滴在面臨流動路徑選擇時，選取泥土量更少的路徑概率會更大[13]。

利用上述的水滴特征來構建虛擬模型，即基于智能水滴(IWD)算法的裝夾規(guī)劃方法。該方法基于水滴的流動速度和所包含的泥土量這兩個重要特征，用s(IWD)表示水滴中包含的泥土量，用v(IWD)表示水滴的流動速度。在自然界中，液體的流動過程是連續(xù)不斷的,但是智能水滴在移動過程中的環(huán)境假定為離散的。該環(huán)境假定由Nc個節(jié)點構成，需要從一個節(jié)點流到另一個節(jié)點。當水滴k從節(jié)點i流到下一個節(jié)點j時，這兩節(jié)點間的路徑上的泥土量用s(i,j)表示，同時水滴的速度會發(fā)生變化，用Δv(k)(i,j)來表示其速度增量。其中，s(i,j)和Δv(k)(i,j)存在反比的關系，其表達式如下：

(7)

式中，av、bv、cv為針對所給問題設置的恒定速度參數，均取正值；α為自定義參數，也取正值。

具有流動速度v(k)的智能水滴k從節(jié)點i流到節(jié)點j的同時，從兩節(jié)點間路徑上獲得的泥土量也相應地增加，節(jié)點間路徑上的泥土量s(i,j)相應地減少，即

s(i,j)=ρ0s(i,j)-ρnΔs(i,j)

(8)

其中，ρ0和ρn為根據所給問題從0～1之間選取的正數，在裝夾規(guī)劃問題中，ρ0=1-ρn。Δs(i,j)為泥土增量，其表達式如下：

(9)

其中，as、bs、cs和θ均為用戶自定義的恒定參數，均取正值；t(i,j;v(k))為具有速度v(k)的智能水滴k從節(jié)點i流到節(jié)點j所花費的時間，其表達式如下：

(10)

式中，H(i,j)為根據所給問題定義的局部反向啟發(fā)函數，表示智能水滴不愿選擇從節(jié)點i流向節(jié)點j的程度。

2.2 基于智能水滴算法的裝夾規(guī)劃問題

為使智能水滴算法能夠合理地解決裝夾規(guī)劃問題，結合智能水滴算法的定義，將待加工零件的各個操作單元設為智能水滴算法的每個節(jié)點。這樣，水滴流經k個節(jié)點的路徑即為某個零件擁有k個操作單元的裝夾序列。圖1所示為一個具體的通過智能水滴算法獲得的操作單元的裝夾序列。其中，操作單位ui均取自于操作單元集合u，機床Mi均取自備選機床集合M，刀具接近方向x、y、z等均取自于刀具接近方向集合D，刀具Ti均取自于備選刀具集合T。

(a)水滴流經路徑(b)對應路徑生成的裝夾序列圖1 基于智能水滴算法獲得的裝夾序列Fig.1 Setup sequence obtained based o n IWD algorithm

(11)

其中，e為各操作單元間屬性值相同的變量的數量,w為各操作單位間變量的總量。即操作單元間的裝夾相似度越高，劃分到一次裝夾的可能性越大。反之，相似度越低，劃分到不同裝夾分組的可能性就越大。

(12)

由式(12)可以看出，兩個相鄰操作單元的裝夾相似度越高，代表這兩個操作單元的兩個相鄰節(jié)點間的泥土量越少。

同時，將反向啟發(fā)函數H(i,j)與兩節(jié)點間的泥土量s(i,j)相結合，其表達式如下：

(13)

由式(13)可知，反向啟發(fā)函數H(i,j)與兩節(jié)點間的泥土量s(i,j) 為正相關關系，即兩節(jié)點i和j間的泥土量越多，則智能水滴越不愿從節(jié)點i流向節(jié)點j。

當智能水滴處于節(jié)點i時，從節(jié)點i流至節(jié)點j的概率為P(i,j)，其表達式如下：

(14)

其中，l為水滴下一步可能選擇的節(jié)點，h(s(i,j))是以節(jié)點i、j間路徑中的泥土量為變量的函數，其表達式為

(15)

其中，常量εs為一個非常小的正數，以避免函數中出現分母為0的情況，這里取εs= 0.01。函數g(s(i,j))用于將節(jié)點i至節(jié)點j間路徑上的泥土量轉換為正值，具體如下：

g(s(i,j))=

(16)

其中，函數min(s(i,l))表示節(jié)點i與下一步可能選擇的節(jié)點l之間的路徑上泥土量的最小值；vc為水滴已流經過的節(jié)點集合。

2.3 基于智能水滴算法的適應度函數構造

基于智能水滴算法，將各個操作單元作為智能水滴的節(jié)點，利用節(jié)點間泥土量來表示操作單元間的相似度。由式(7)可知，兩節(jié)點間的泥土量s(i,j)和智能水滴k通過下一節(jié)點后的速度增量Δv(k)(i,j)存在負相關關系，而由式(9)可知，速度增量Δv(k)(i,j)與所攜帶的泥土增Δs(i,j)存在正相關關系，所以，可以用智能水滴通過所有節(jié)點后最終攜帶的泥土量來表征裝夾規(guī)劃的適應度函數f：

(17)

(18)

式中，s(k)為智能水滴在通過初始節(jié)點前所攜帶的泥土量。

綜合式(17)和式(18)，定義裝夾規(guī)劃的適應度函數：

(19)

通過智能水滴生成的每一組操作單元的序列都有其相應的適應度函數，基于適應度函數來尋求最優(yōu)的裝夾方案。

2.4 智能水滴算法的迭代操作

考慮用適應度函數f(ZIWD)來尋找由智能水滴算法獲得的解ZIWD，即尋求操作單元的排序。在每次迭代結束時，由智能水滴尋找的迭代最優(yōu)解為

(20)

其中，迭代最優(yōu)解ZIB為所有解ZIWD中最終攜帶泥土質量最大的解?；诘顑?yōu)解f(ZIB)的泥土質量來更新解ZIB的路徑。

路徑上泥土量的更新應包括一定量的質量解，具體為

s(i,j)=ρss(i,j)+ρIWDk(Nc)sIB

?(i,j)∈ZIB

(21)

其中，sIB為迭代最優(yōu)水滴的泥土量。k(Nc)為一個取決于節(jié)點數Nc的正系數，這里選取k(Nc)=1/(Nc-1)。參數ρs為一個正常數，參數ρIWD為一個負常數。

式(21)中，ρss(i,j)表示由水滴獲得的當前解的質量，ρIWDk(Nc)sIB表示從上一次迭代中剩下的泥土量。因此，在式(21)中，水滴由節(jié)點i到節(jié)點j路徑上從總泥土量s(i,j)中獲得的泥土量的比例會減小。這樣迭代最優(yōu)解會不斷地增強，同時會引導水滴尋找附近優(yōu)秀的解，并有希望尋找到全局最優(yōu)解。

算法中每次迭代完成時，總的最優(yōu)解集ZTB會通過當前迭代最優(yōu)解集ZIB來更新，即

(22)

如此操作可以保證ZTB擁有目前由IWD算法獲得的最優(yōu)解。

2.5 智能水滴算法優(yōu)化裝夾規(guī)劃的實現步驟

智能水滴算法運用到裝夾規(guī)劃問題的具體步驟如下：

(1)分析加工特征。通過對待加工零件的加工特征進行分析和歸類分組，將其設置為操作單元的各個變量，構建裝夾信息集合。

(2)生成操作單元?；谘b夾信息集合所提供的加工特征，生成各個操作單元。

(3)構建操作單元順序約束矩陣。根據待加工零件的加工工藝和要求，記錄各操作單元間的約束關系，構建操作單元順序約束矩陣。

(4)初始化水滴靜態(tài)參數。設定水滴的數量NIWD為一個正整數，水滴所要流經的節(jié)點數量Nc等于待加工零件的操作單元數量。設定水滴流動的速度更新參數av、bv、cv和泥土量的更新參數as、bs、cs，確定局部泥土量更新參數ρn，以及全局泥土量更新參數ρIWD。設定水滴的初始速度vinit，以及算法的最大迭代次數imax。

(5)更新各個水滴的信息集合。對每個水滴所經過的節(jié)點列表，將其設置為空矩陣。設定每個水滴所攜帶的初始泥土量s(k)為0。

(6)基于操作單元順序約束矩陣的次序，令每個水滴隨機選取節(jié)點。

(7)更新每個水滴訪問過的節(jié)點列表，將已被訪問過的節(jié)點依次添加進去。

(8)沒有獲得完整流動路徑的水滴，則重復執(zhí)行下列步驟：

①在符合操作單元順序約束矩陣的前提下，從水滴未曾流經的節(jié)點列表中選取下一個需要訪問的節(jié)點。根據式(14)所定義的概率P(i,j)來更新即將訪問的節(jié)點。

②令式(7)中α=1。當水滴k從節(jié)點i流至j后，速度會更新，其表達式為

(23)

③根據式(9)，結合式(10)和式(12)，令θ=1，計算兩節(jié)點間的泥土減少量Δs(i,j)。

④根據式(8)，更新兩節(jié)點間路徑中的泥土量s(i,j)，流經兩節(jié)點后水滴k所攜帶的泥土量為

s(k)(t+1)=s(k)(t)+Δs(i,j)

(24)

(9)根據式(20)，尋找迭代最優(yōu)解ZIB。

(10)根據式(21)，設定ρs=(1-ρIWD)，更新當前迭代最優(yōu)解ZIB路徑中的泥土量。

(11)根據式(22)，用當前迭代最優(yōu)解ZIB來替代之前最優(yōu)解ZTB。

(12)重復開始第(4)步，直至迭代次數達到最大。

(13)獲得最終最優(yōu)解ZTB即最佳的裝夾方案后，終止算法。

圖2所示為算法步驟的流程，圖3為算法步驟(8)的具體流程。

圖2 利用智能水滴算法求解裝夾規(guī)劃的流程圖Fig.2 Flowchart for solving the setup planning b y IWD algorithm

圖3 智能水滴算法步驟(8)的流程圖Fig.3 Flowchart for step(8) of IWD algorithm

3 實例驗證

為了驗證智能水滴算法在裝夾規(guī)劃中的可行性及有效性，參照文獻[1]，本文選取圖4所示的零件模型作為分析對象，將使用的刀具、刀具接近方向和功能類型相同的操作單元進行簡化，使得該零件劃分為14個加工特征及20個操作單元。

圖4 零件的三維模型圖Fig.4 3D model of parts

根據零件的加工特征，細分各個不同的操作單元，將操作單元所需的機床、工具和刀具接近方向等信息匯集成加工信息集合，如表1所示。

表1 操作單元信息集

通過對各個操作單元的定位基準、幾何特征、加工精度要求以及生產成本進行綜合分析，確定了各操作單元之間的加工順序關系，由此構建加工順序約束矩陣M：

(25)

智能水滴算法的參數設定如下：初始種群數200，迭代次數30，局部泥土量的更新參數ρn=0.9，全局泥土量的更新參數ρIWD=-0.9，水滴的初始速度vinit=4。

在經過迭代計算后，從種群集合中隨機選取4個種群與最優(yōu)種群進行對比，具體迭代曲線如圖5所示?？梢姼鞣N群的初始適應變度值較大，即由智能水滴算法獲得的初始解質量較高。經過前期迭代更新后適應度值逐漸趨于穩(wěn)定，最終獲得最佳的流動路徑，即最優(yōu)的裝夾規(guī)劃方案。

圖5 智能水滴算法的適應度曲線Fig.5 Fitness curve of IWD algorithm

將智能水滴(IWD)算法與遺傳算法(GA)的裝夾分組過程進行對比，其迭代結果如圖6所示。

圖6 不同算法的裝夾分組過程Fig.6 Grouping process of setup based o n different algorithms

在通過操作單元順序約束矩陣對裝夾規(guī)劃方案進行篩選后，基于智能水滴算法的裝夾規(guī)劃過程中的初始裝夾次數要少于遺傳算法計算的初始裝夾次數。同時，由于算法的迭代特性，使得迭代過程中水滴所經過的路徑上的泥土量不斷減少，水滴所選取的節(jié)點順序逐漸趨于一致，算法的收斂速度提高，可以較快地獲得更為優(yōu)秀的裝夾規(guī)劃方案。

通過IWD算法的迭代計算后，得到的最優(yōu)裝夾規(guī)劃方案如表2所示。具體的裝夾分組方案如表3所示。

表2 智能水滴算法獲得的最優(yōu)裝夾規(guī)劃方案

表3 智能水滴算法獲得的最優(yōu)裝夾分組方案

4 結論

針對計算機輔助工藝規(guī)劃中的裝夾規(guī)劃問題，提出利用智能水滴算法來進行求解。由裝夾特征來定義零件的操作單元，通過順序約束矩陣來保證裝夾規(guī)劃方案的可行性。通過將智能水滴算法中流動路徑的各節(jié)點與各操作單元相匹配，使得水滴的流動路徑即為操作單元的排序。同時，將各節(jié)點間的泥土量與操作單元間的相似性相結合來構建適應度函數，符合裝夾規(guī)劃過程中的信息處理機制，提高了算法的搜索效率。基于智能水滴算法的特性，通過在迭代過程中使流動路徑上的泥土量不斷減少，使得水滴所選取的節(jié)點順序逐漸趨于一致，提高了算法的收斂速度，同時保證了所獲得的最優(yōu)裝夾規(guī)劃方案的質量。