人工魚群算法在孔群加工路徑優(yōu)化中的應(yīng)用研究

蔡 蕓,周立煒

(武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院,湖北武漢,430081)

大量孔的連續(xù)加工任務(wù)稱為孔群加工,孔群加工常見于鈑金加工、印刷電路板加工和機(jī)械零件加工中。合理規(guī)劃孔群加工路徑,縮短刀具移動(dòng)路徑、減少換刀次數(shù)及刀具變向次數(shù),將有助于減少輔助加工時(shí)間,提高生產(chǎn)效率,節(jié)約成本。

孔群加工路徑規(guī)劃含有典型的旅行商問題(Travel Sale-man Problem,TSP),其解空間存在“組合爆炸”,例如在一塊已確定初始位置的工件上加工某類孔(數(shù)量為n>2),加工完畢后返回,則其可選路徑為條,傳統(tǒng)的數(shù)學(xué)規(guī)劃方法難以求解。目前已經(jīng)有學(xué)者采用遺傳算法、蟻群算法、人工免疫系統(tǒng)算法、禁忌搜索算法等智能計(jì)算方法求解了孔群加工路徑優(yōu)化的單目標(biāo)或多目標(biāo)問題[1-4]。

人工魚群算法(Artificial Fish Swarm Algorithm,AFSA)是近年來提出的一種模擬魚群行為的隨機(jī)搜索方法,是群智能思想的一個(gè)具體應(yīng)用[5-6]。該算法通過仿真魚的覓食、聚群、追尾行為快速獲得最優(yōu)解,在解決函數(shù)優(yōu)化、組合優(yōu)化等問題上都取得了成功。但目前國內(nèi)外學(xué)者還沒有將人工魚群算法應(yīng)用于孔群加工路徑優(yōu)化的研究。本文嘗試對(duì)此進(jìn)行研究,并通過具體實(shí)例的算法實(shí)現(xiàn),對(duì)比人工魚群算法與其他人工智能算法的求解效果,以期為講求實(shí)效的生產(chǎn)作業(yè)提供更好的理論方法。

1 路徑優(yōu)化的數(shù)學(xué)模型

式(1)為目標(biāo)函數(shù),其中Y表示刀具行進(jìn)路徑長度,Dij為孔i和孔j間已知距離。式(2)～式(5)為約束條件,式(2)表示是否選擇孔i到孔j的路徑,aij=0時(shí),表示不選擇從孔i到孔j;當(dāng)aij=1時(shí),表示選擇從孔i到孔j;式(3)和式(4)表示孔i和孔j的出入只有一次;式(5)約束的是在任何一個(gè)孔的真子集中不形成回路[7]。

2 應(yīng)用人工魚群算法求解

2.1 符號(hào)定義

X:人工魚群的狀態(tài),即被搜索到的最優(yōu)解狀態(tài)。X=(X1,X2,…,Xn),其中Xi(i=1,…,n)代表第i條人工魚的狀態(tài),它是孔群加工的序列,這里采用自然數(shù)鏈進(jìn)行孔序編碼,如Xi=(3 2 5 4 7 1 6 9 8),即從孔3出發(fā)依次經(jīng)過孔2—5—4—7—1—6—9—8,然后返回孔3的一條路徑。

Yi:對(duì)應(yīng)于Xi的目標(biāo)函數(shù)值,即刀具行進(jìn)的路徑長度,它表示人工魚當(dāng)前狀態(tài)的食物濃度。

Dij:第i條和第j條人工魚間的距離,它表示兩條路徑間的差異程度,即兩條路徑同序列位置的孔序編碼差異數(shù)目,如Xi=(1,3,2,5,6,4)和Xj=(1,3,6,2,5,4)在路徑序列位置3、4、5處的孔序編碼不相同,故Dij=3。

Visual:人工魚的視野范圍。

N(Xi,Visual):第i條魚的視覺鄰居集合。

N(Xi,Visual)={Xj|Dij≤Visual}。

式(5)說明，損失規(guī)避性購電商的期望效用是(風(fēng)險(xiǎn)中性時(shí)的)期望利潤和損失規(guī)避特性帶來的期望效用損失的和。購電商的目標(biāo)是給定批發(fā)價(jià)格下，確定最優(yōu)購電量使其期望效用最大。

δ:表示擁擠度因子,0<δ<1。

FishNum:參與尋優(yōu)的人工魚的數(shù)目。

Maxgen:最大迭代次數(shù)。

Trynumber:人工魚覓食時(shí)最大的試探次數(shù)。

Center稱為決策變量X1,X2,…,Xm的中心。

2.2 人工魚群算法的行為描述

人工魚群算法模擬魚集群游弋覓食的行為,通過魚群之間的集體協(xié)作使群體達(dá)到目的。在AFSA中,每個(gè)備選解被稱為一條“人工魚”,多條人工魚共存,合作尋優(yōu)(類似魚群尋找食物)。AFSA初始化為一群人工魚(隨機(jī)解),通過迭代搜尋最優(yōu)解,在每次迭代過程中,人工魚通過覓食、聚群及追尾等行為來更新自己,從而實(shí)現(xiàn)尋優(yōu)。人工魚的行為描述如下。

(1)追尾行為:指魚向臨近的最活躍者追捉的行為。人工魚Xi搜索其視野內(nèi)的所有伙伴中函數(shù)值為最小的伙伴Xmin,如果Yi>Ymin,且Xmin的鄰域內(nèi)伙伴的數(shù)目nf滿足nf/N(Xi,Visual)<δ(0<δ<1),表明Xmin的附近有較多的食物并且不太擁擠,則向Xmin的位置前進(jìn)一步,否則執(zhí)行覓食行為。

(2)覓食行為:指魚向著食物多的方向游動(dòng)的一種行為。人工魚Xi在其視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj,如果Yi>Yj,則向狀態(tài)Xj方向前進(jìn)一步;否則,Xi繼續(xù)在其視野內(nèi)重新隨機(jī)選擇狀態(tài)Xj,判斷是否滿足前進(jìn)條件,反復(fù)嘗試Trynumber次后,如果仍沒有找到更優(yōu)的狀態(tài),則執(zhí)行其他行為。

(3)聚群行為:指每條魚在游動(dòng)過程中盡量向臨近伙伴的中心移動(dòng)并避免過分擁擠。設(shè)人工魚當(dāng)前狀態(tài)為Xi,探索其鄰域內(nèi)的伙伴數(shù)目nf,如果nf/N(Xi,Visual)<δ(0<δ<1),則表明伙伴中心有較多的食物并且不太擁擠,如果此時(shí)Yi>Yc,則人工魚向中心位置Xc前進(jìn)一步,否則執(zhí)行其他行為。

2.3 算法步驟

步驟1:設(shè)置參數(shù)FishNum,Maxgen,Trynumber,Visual,δ;隨機(jī)產(chǎn)生人工魚群來初始化X=(X1,X2,…,Xi,…,XFishNum)。m=0,i=0。

步驟2:m=m+1;

步驟.3:i=i+1;對(duì)人工魚Xi執(zhí)行追尾行為;如發(fā)現(xiàn)更好的解Xj,用Xj代替Xi并轉(zhuǎn)到步驟8,否則轉(zhuǎn)到步驟4。

步驟4:圓整Visual×(1-m/Maxgen)獲得最近的整數(shù)Visual2;如果Visual2>0,轉(zhuǎn)到步驟5并將Visual2應(yīng)用于其中,否則轉(zhuǎn)到步驟6。

步驟5:對(duì)人工魚Xi,執(zhí)行覓食行為;如果發(fā)現(xiàn)一個(gè)更佳的解Xj,則用Xj代替Xi然后轉(zhuǎn)到步驟8,否則轉(zhuǎn)到步驟6。

步驟6:對(duì)于人工魚Xi,執(zhí)行聚群行為;如發(fā)現(xiàn)一個(gè)更佳的解Xj,用Xj代替Xi然后轉(zhuǎn)到步驟8,否則轉(zhuǎn)到步驟7。

步驟7:對(duì)于人工魚Xi,隨機(jī)改變Xi的元素得到新狀態(tài)Xj。如果它是一個(gè)較佳的狀態(tài),則用Xj代替Xi并轉(zhuǎn)到步驟8,否則轉(zhuǎn)到步驟3,評(píng)價(jià)第i+1條人工魚。

步驟8:更新公告板上的最優(yōu)化解記錄,如果i=FishNum,則轉(zhuǎn)到步驟9,否則轉(zhuǎn)到步驟3,評(píng)價(jià)第i+1條人工魚。

步驟9:如果m=Maxgen,輸出最優(yōu)解,程序結(jié)束,否則轉(zhuǎn)到步驟2,計(jì)算第m+1代人工魚群。

3 算例分析

3.1 算例的已知條件

為了比較人工魚群算法與其他智能算法的優(yōu)化性能,采用文獻(xiàn)[1]、文獻(xiàn)[3]中的注塑模上模具的孔群加工實(shí)例。模具簡圖如圖1所示。已知條件為:26個(gè)孔中心的坐標(biāo)鄰接矩陣B=[50,50;50,450;690,450;690,50;100,120;100,380;640,380;640,120;30,150;30,350;710,350;710,150;160,70;580,430;160,150;160,350;580,350;580,150;230,250;300,130;440,130;510,250;440,370;300,370;250,180;490,320]。

圖1 注塑模上模具簡圖Fig.1 Upper die of in jection mold

3.2 計(jì)算結(jié)果

當(dāng)算法參數(shù)取FishNum=10,Maxgen=150,Trynumber=150,Visual=8,δ=0.8時(shí),采用配置為Intel Co re 2 Duo E6550,2.0GB RAM的計(jì)算機(jī),在MatLabR2010a軟件平臺(tái)上實(shí)現(xiàn)的算法程序,需耗時(shí)2.28 6 s找到最短路徑:1—5—13—15—19—25—20—21—18—8—4—12—11—3—7—14—17—22—26—23—24—16—6—2—10—9—1,其長度為2 696.381 mm,如圖2所示。按照傳統(tǒng)的孔類型分批加工(按孔的編號(hào)順序加工)的路徑總長度為9 449.5 mm[1]。通過人工魚群算法優(yōu)化,加工路徑縮短為傳統(tǒng)加工方式的28.53%。

圖2 最優(yōu)加工路徑Fig.2 Optimal holes machining path

不同算法的計(jì)算結(jié)果[1,3]如表1所示。表1中,除改進(jìn)遺傳算法外,其余均為經(jīng)過100次實(shí)驗(yàn)獲得的結(jié)果。由表1中可見,人工魚群算法求最優(yōu)解的效果優(yōu)于其他幾種算法,獲得的平均解也是較優(yōu)的。

表1 不同算法計(jì)算結(jié)果對(duì)比表Table 1 Comparison of computational results

3.3 算法參數(shù)分析

本例使用的算法參數(shù)是一個(gè)需要優(yōu)化的問題。筆者在FishNum=10～30,Maxgen=50～200,Trynumber=10～200,Visual=2～10,δ=0.2～1.0的參數(shù)范圍內(nèi)進(jìn)行了一些實(shí)驗(yàn),發(fā)現(xiàn)參與尋優(yōu)的人工魚數(shù)目和覓食探測次數(shù)選較大值時(shí),求優(yōu)效果較佳但耗時(shí)。考慮計(jì)算時(shí)效的情況下,參與尋優(yōu)的人工魚的數(shù)目選擇10較為合適,Trynumber在100～200期間,算法容易收斂,但是不能總是收斂到目前發(fā)現(xiàn)的最優(yōu)值2 696.381。另外,Visual值通常不能取太小,需要大于參與尋優(yōu)的人工魚的數(shù)目的一半以上,例如,魚群大小FishNum為10時(shí),Visual取7～8較好。此外,擁擠度因子也不能取得過小,取0.7～0.9時(shí),求解效果較優(yōu)。

4 結(jié)語

本文建立了最小化孔群加工路徑的數(shù)學(xué)優(yōu)化模型,對(duì)基本人工魚群算法進(jìn)行了應(yīng)用改進(jìn),對(duì)人工魚覓食過程中的視野范圍因子實(shí)行了逐代改進(jìn)的方法,提高了算法的搜索時(shí)效。實(shí)例計(jì)算表明人工魚群算法能夠較好地解決此類問題,在同類算法中有較優(yōu)秀的表現(xiàn)。由于隨機(jī)算法的性能同隨機(jī)初始解以及算法參數(shù)的選擇關(guān)系密切,所以今后還需做大量的數(shù)值實(shí)驗(yàn)來獲取較好的算法參數(shù)組合,便于算法的工程實(shí)際應(yīng)用。

[1] 凌玲,胡于進(jìn),王青青,等.基于改進(jìn)遺傳算法的孔群加工路徑優(yōu)化[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2009,37(8):88-91.

[2] Ghaiebi H,Solimanpur M.An ant algorithm for optimization of hole-making operations[J].Computers&Industrial Engineering,2007,52(2):308-319.

[3] 肖人彬,陶振武.孔群加工路徑規(guī)劃問題的進(jìn)化求解[J].計(jì)算機(jī)集成制造系統(tǒng),2005,11(5):682-689.

[4] Kolahan F,Liang M.Op timization of hole-making operations:a tabu-search approach[J].International Journal of Machine Tools&Manufacture,2000,40(12):1 735-1 753.

[5] 李曉磊,邵之江,錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.

[6] 李曉磊,路飛,田國會(huì),等.組合優(yōu)化問題的人工魚群算法應(yīng)用[J].山東大學(xué)學(xué)報(bào):工學(xué)版,2004,64(4):64-67.

[7] 張振普,王大承.群孔加工路徑的優(yōu)化方法[J].五邑大學(xué)學(xué)報(bào):自然科學(xué)版,2008,22(2):25-30.