高 博 胡曉宇 彭珍瑞 劉君泉

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

0 引言

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

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

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

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

1.1 操作單元的定義

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

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

ui={O,M,D,T}

(1)

u={u1,u2,…,uk}

i=1，2，…，k

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

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

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

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

(2)

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

裝夾規(guī)劃問題是一個(gè)典型的NP組合優(yōu)化問題，通過對操作單元的分組，以實(shí)現(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)

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

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

(4)

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

(5)

(6)

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

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

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

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

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

(7)

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

具有流動(dòng)速度v(k)的智能水滴k從節(jié)點(diǎn)i流到節(jié)點(diǎn)j的同時(shí)，從兩節(jié)點(diǎn)間路徑上獲得的泥土量也相應(yīng)地增加，節(jié)點(diǎn)間路徑上的泥土量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)為泥土增量，其表達(dá)式如下：

(9)

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

(10)

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

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

為使智能水滴算法能夠合理地解決裝夾規(guī)劃問題，結(jié)合智能水滴算法的定義，將待加工零件的各個(gè)操作單元設(shè)為智能水滴算法的每個(gè)節(jié)點(diǎn)。這樣，水滴流經(jīng)k個(gè)節(jié)點(diǎn)的路徑即為某個(gè)零件擁有k個(gè)操作單元的裝夾序列。圖1所示為一個(gè)具體的通過智能水滴算法獲得的操作單元的裝夾序列。其中，操作單位ui均取自于操作單元集合u，機(jī)床Mi均取自備選機(jī)床集合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)可以看出，兩個(gè)相鄰操作單元的裝夾相似度越高，代表這兩個(gè)操作單元的兩個(gè)相鄰節(jié)點(diǎn)間的泥土量越少。

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

(13)

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

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

(14)

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

(15)

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

g(s(i,j))=

(16)

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

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

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

(17)

(18)

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

綜合式(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é)束時(shí)，由智能水滴尋找的迭代最優(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)為一個(gè)取決于節(jié)點(diǎn)數(shù)Nc的正系數(shù)，這里選取k(Nc)=1/(Nc-1)。參數(shù)ρs為一個(gè)正常數(shù)，參數(shù)ρIWD為一個(gè)負(fù)常數(shù)。

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

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

(22)

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

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

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

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

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

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

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

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

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

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

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

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

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

(23)

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

④根據(jù)式(8)，更新兩節(jié)點(diǎn)間路徑中的泥土量s(i,j)，流經(jīng)兩節(jié)點(diǎn)后水滴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ù)達(dá)到最大。

(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 實(shí)例驗(yàn)證

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

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

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

表1 操作單元信息集

通過對各個(gè)操作單元的定位基準(zhǔn)、幾何特征、加工精度要求以及生產(chǎn)成本進(jì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)過迭代計(jì)算后，從種群集合中隨機(jī)選取4個(gè)種群與最優(yōu)種群進(jìn)行對比，具體迭代曲線如圖5所示?？梢姼鞣N群的初始適應(yīng)變度值較大，即由智能水滴算法獲得的初始解質(zhì)量較高。經(jīng)過前期迭代更新后適應(yīng)度值逐漸趨于穩(wěn)定，最終獲得最佳的流動(dòng)路徑，即最優(yōu)的裝夾規(guī)劃方案。

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

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

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

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

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

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

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

4 結(jié)論

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