高 博 胡曉宇 彭珍瑞 劉君泉

蘭州交通大學(xué)機電工程學(xué)院，蘭州，730070

0 引言

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

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

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

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

1.1 操作單元的定義

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

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

ui={O,M,D,T}

(1)

u={u1,u2,…,uk}

i=1，2，…，k

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

1.2 操作單元的約束關(guān)系

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

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

(2)

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

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

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

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 智能水滴算法的基本原理

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

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

(7)

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

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

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

(8)

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

(9)

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

(10)

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

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

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

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

(11)

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

(12)

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

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

(13)

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

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

(14)

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

(15)

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

g(s(i,j))=

(16)

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

2.3 基于智能水滴算法的適應(yīng)度函數(shù)構(gòu)造

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

(17)

(18)

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

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

(19)

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

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

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

(20)

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

路徑上泥土量的更新應(yīng)包括一定量的質(zhì)量解，具體為

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

?(i,j)∈ZIB

(21)

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

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

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

(22)

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

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

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

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

(2)生成操作單元。基于裝夾信息集合所提供的加工特征，生成各個操作單元。

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

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

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

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

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

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

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

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

(23)

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

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

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

(24)

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

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

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

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

(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

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

表1 操作單元信息集

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

(25)

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

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

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

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

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

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

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

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

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

4 結(jié)論

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