基于FTC-SA算法的孔群在機(jī)測(cè)量路徑優(yōu)化*

周 續(xù),安 迪,王駿豪,張從鵬

(北方工業(yè)大學(xué)機(jī)械與材料工程學(xué)院,北京 100144)

0 引言

隨著精密制造技術(shù)的不斷發(fā)展,在機(jī)測(cè)量越來(lái)越廣泛地應(yīng)用于機(jī)械零件的加工精度檢測(cè)中。相比于離線三坐標(biāo)測(cè)量,在機(jī)測(cè)頭測(cè)量具有成本低、無(wú)需二次裝夾定位、便于后續(xù)工序加工等優(yōu)勢(shì),同時(shí)可以將測(cè)量數(shù)據(jù)直接反饋給加工系統(tǒng),實(shí)現(xiàn)加工誤差補(bǔ)償[1-2]。對(duì)于機(jī)械零件中的孔群特征,需要在孔群加工完成后進(jìn)行孔心位置、孔直徑、孔軸線的精度檢測(cè)。而根據(jù)孔類型、孔尺寸、孔位置等信息編制的孔群在機(jī)測(cè)量程序,往往存在測(cè)頭移位不合理、空行程距離過(guò)長(zhǎng)等問(wèn)題,導(dǎo)致生產(chǎn)效率低、機(jī)床能耗大[3]。

目前,孔群特征的加工/測(cè)量路徑主要采用標(biāo)準(zhǔn)或改進(jìn)的啟發(fā)式算法進(jìn)行優(yōu)化,如遺傳算法(GA)[4-5]、蟻群優(yōu)化(ACO)算法[6-7]、模擬退火(SA)算法[8]、免疫算法(IA)[9]等。肖軍民[4]根據(jù)孔的序號(hào)進(jìn)行染色體編碼,提出了一種基于改進(jìn)遺傳算法的孔群加工路徑優(yōu)化方法。龔玉玲等[5]則在遺傳算法中引入模擬退火算法的Metropolis準(zhǔn)則,以此來(lái)調(diào)節(jié)新種群的更新機(jī)制,提高了孔群加工路徑在全局范圍的尋優(yōu)能力和收斂效率。ABBAS等[6]基于改進(jìn)蟻群算法規(guī)劃了矩形陣列孔群的加工路徑。馬旭東等[7]通過(guò)正交試驗(yàn)對(duì)蟻群算法的初始化參數(shù)進(jìn)行優(yōu)選,獲得了全局優(yōu)化的塑?？兹杭庸ぢ窂?。張明祿等[8]先利用K-means聚類算法進(jìn)行孔群分組,再利用改進(jìn)模擬退火算法完成了孔群加工路徑優(yōu)化。戴紅偉等[9]提出了一種自適應(yīng)量子交叉免疫算法,在進(jìn)行孔群加工路徑優(yōu)化時(shí)可以有效平衡全局搜索和局部挖掘能力。

上述研究主要針對(duì)孔群按類型或尺寸進(jìn)行分組的加工路徑優(yōu)化情況,是快速有效的求解算法。然而在孔群精度檢測(cè)時(shí),通常無(wú)需進(jìn)行分組處理,參與路徑優(yōu)化的個(gè)體數(shù)量倍增,使得各算法出現(xiàn)收斂緩慢、解的質(zhì)量低、穩(wěn)定性差等問(wèn)題。本文針對(duì)大規(guī)?？兹杭庸ぞ鹊脑跈C(jī)測(cè)量需求,提出一種波動(dòng)式溫度控制的模擬退火(FTC-SA)算法,以優(yōu)化出高效率、低能耗的孔群檢測(cè)路徑。

1 孔群在機(jī)測(cè)量路徑模型

如圖1所示,在測(cè)量坐標(biāo)系Om-XmYmZm中,觸發(fā)式測(cè)頭從安全平面上的作業(yè)零點(diǎn)出發(fā),依次運(yùn)動(dòng)至各加工孔的安全點(diǎn),然后沿Zm軸進(jìn)給至目標(biāo)點(diǎn)進(jìn)行孔中心位置、孔直徑、孔軸線的精度測(cè)量,最后返回到作業(yè)零點(diǎn)。為了減少問(wèn)題的復(fù)雜性,對(duì)孔群在機(jī)測(cè)量路徑模型作如下假設(shè):

(1)測(cè)頭直徑和長(zhǎng)度可以滿足所有加工孔的精度測(cè)量要求,即測(cè)量過(guò)程中無(wú)需更換測(cè)頭。

(2)階梯孔的加工精度在一次探測(cè)過(guò)程中全部完成,即階梯孔的各目標(biāo)點(diǎn)共用一個(gè)安全點(diǎn)。

(3)測(cè)頭在孔群中進(jìn)行移位及探測(cè)時(shí),進(jìn)給速度保持不變。

(4)測(cè)頭在確定的探測(cè)參數(shù)下進(jìn)行各加工孔精度測(cè)量。

由此,對(duì)于某一組給定的孔群,其在機(jī)測(cè)量路徑的總距離僅會(huì)受到測(cè)頭在各加工孔之間探測(cè)順序的影響。此時(shí)孔群在機(jī)測(cè)量路徑模型可以轉(zhuǎn)化為典型的旅行商問(wèn)題(TSP):即測(cè)頭的作業(yè)零點(diǎn)和各加工孔的安全點(diǎn)共同按自然數(shù)進(jìn)行編碼,構(gòu)成n個(gè)城市(城市編碼最小值為1,最大值為n),測(cè)頭則對(duì)應(yīng)旅行商人;旅行商人從某個(gè)城市出發(fā),尋找出一條遍歷所有n個(gè)城市一次并最終回到出發(fā)城市的最短路徑[10]。

將n個(gè)城市的遍歷序列用向量C進(jìn)行表示,C=(c1,c2,…,cn,cn+1),其中cn+1=c1,表示旅行商人由最后訪問(wèn)城市返回到出發(fā)城市。則城市ci與城市ci+1之間的路徑距離可以表示為:

(1)

式中:(xi,yi)和(xi+1,yi+1)分別為城市ci和城市ci+1在測(cè)量坐標(biāo)系中的Xm軸、Ym軸坐標(biāo)值。

按序列C遍歷n個(gè)城市的總路徑距離為:

(2)

則孔群在機(jī)測(cè)量路徑模型對(duì)應(yīng)的目標(biāo)函數(shù)為:

D(Cbest)=minD(C)

(3)

式中:Cbest為優(yōu)化的城市遍歷序列。

2 FTC-SA算法設(shè)計(jì)

SA算法的思想來(lái)源于金屬熱處理工藝中的退火原理,是一種求解組合優(yōu)化問(wèn)題的隨機(jī)尋優(yōu)算法[11]。該算法可以在搜索過(guò)程中概率性地跳出局部最優(yōu)解并趨于全局最優(yōu)解,其關(guān)鍵核心為Metropolis準(zhǔn)則:

(4)

ΔD=D(Cnew)-D(Cold)

(5)

式中:P為新解的接受概率,T為當(dāng)前溫度,D(Cnew)為新解Cnew對(duì)應(yīng)的總路徑距離,D(Cold)為當(dāng)前解Cold對(duì)應(yīng)的總路徑距離,ΔD為新解Cnew與當(dāng)前解Cold對(duì)應(yīng)的總路徑距離的差。

2.1 初始溫度的設(shè)定

標(biāo)準(zhǔn)SA算法通常將初始溫度T0設(shè)定為一個(gè)充分大的值,以保證更強(qiáng)的全局搜索能力,但會(huì)導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)。本文借鑒混沌尋優(yōu)方法進(jìn)行初始溫度的設(shè)定。通過(guò)在解空間內(nèi)隨機(jī)選取m個(gè)可行解,可以計(jì)算得到各可行解對(duì)應(yīng)的總路徑距離。根據(jù)Metropolis準(zhǔn)則,退火的初始溫度可表示為:

(6)

式中:D(Cmax)和D(Cmin)分別為解空間內(nèi)隨機(jī)選取的m個(gè)可行解對(duì)應(yīng)的最大和最小總路徑距離,P0為設(shè)定的接受概率。

2.2 多鄰域貪心搜索機(jī)制

通過(guò)多鄰域搜索可以產(chǎn)生優(yōu)質(zhì)新解。本文對(duì)當(dāng)前解進(jìn)行4種形式的擾動(dòng)操作來(lái)產(chǎn)生新解,如圖2所示。

(a) 個(gè)體插入操作 (b) 個(gè)體交叉操作

(1)個(gè)體插入操作:在當(dāng)前解中隨機(jī)指定兩個(gè)序列位置,將位置1的元素插入到位置2的元素后面。

(2)個(gè)體交叉操作:在當(dāng)前解中隨機(jī)指定兩個(gè)序列位置,將兩個(gè)位置對(duì)應(yīng)的元素進(jìn)行交換。

(3)區(qū)域插入操作:在當(dāng)前解中隨機(jī)指定3個(gè)序列位置,將位置1至位置2的元素插入到位置3的元素后面。

(4)區(qū)域倒置操作:在當(dāng)前解中隨機(jī)指定兩個(gè)序列位置,將位置1至位置2的元素進(jìn)行倒置。

同時(shí)借鑒貪心策略,將4種擾動(dòng)操作中總路徑距離最小的新解保留下來(lái)。這樣既保證了新解較大的搜索范圍,又提升了算法的局部尋優(yōu)效率。

2.3 波動(dòng)式溫度控制函數(shù)

標(biāo)準(zhǔn)SA算法中常用的降溫方式為快速降溫和指數(shù)降溫[12],兩者均為單調(diào)遞減式溫度控制策略。由式(3)可知,算法對(duì)劣解的接受概率與溫度直接相關(guān)。當(dāng)退火至低溫時(shí),對(duì)劣解的接受概率很小,算法跳出局部最優(yōu)的能力也基本喪失。而通過(guò)引入升溫回火操作,可以重新激活劣解的接受概率[12-14]。

在文獻(xiàn)[12]的基礎(chǔ)上,本文提出一種改進(jìn)的波動(dòng)式溫度控制函數(shù),使得溫度在總體趨于下降時(shí),可以實(shí)現(xiàn)多次降溫退火與升溫回火。波動(dòng)式溫度控制函數(shù)表示為:

(7)

式中:Tk為第k次迭代時(shí)的溫度,k為外循環(huán)迭代次數(shù),α為溫度衰減參數(shù),β為波谷控制參數(shù),λ為波動(dòng)間隔參數(shù)。

該函數(shù)是基于指數(shù)降溫函數(shù)和三角余弦函數(shù)進(jìn)行實(shí)現(xiàn)的,不僅具有幅值波動(dòng)特性,還實(shí)現(xiàn)了波峰和波谷遞減。與文獻(xiàn)[12]相比,該函數(shù)引入了β參數(shù)來(lái)控制波谷遞減,更易于判斷退火是否完成;與文獻(xiàn)[13]相比,該函數(shù)的相關(guān)參數(shù)含義清晰且更易于初始化。

圖3為4種不同降溫方式下的溫度控制曲線。從圖3可以發(fā)現(xiàn),當(dāng)采用快速降溫方式時(shí),迭代初期溫度下降過(guò)快,導(dǎo)致算法無(wú)法充分地進(jìn)行全局尋優(yōu)而早熟收斂。當(dāng)采用指數(shù)降溫方式時(shí),降溫速率由快變慢,盡管算法搜索更加充分,但在中后期的執(zhí)行效率太低。以上兩種方式在趨于低溫時(shí),對(duì)劣解的接受概率非常小,算法困于局部最優(yōu)后將難以跳出。多次回火方式是對(duì)指數(shù)降溫方式的改進(jìn),在達(dá)到某個(gè)低溫時(shí),通過(guò)升溫操作拉升算法的全局搜索能力;但該方式下的溫度下降緩慢,算法執(zhí)行效率較低。而采用波動(dòng)溫控方式時(shí),溫度快速下降,算法尋優(yōu)較充分且執(zhí)行效率較高;在趨于低溫時(shí)增加升溫回火操作,提高劣解的接受概率,使得算法能夠跳出局部最優(yōu)而尋到全局最優(yōu);由于是多次退火操作,需要對(duì)當(dāng)前最優(yōu)解進(jìn)行記憶,避免在迭代過(guò)程中遺失。

圖3 溫度控制曲線對(duì)比

2.4 FTC-SA算法流程

圖4為FTC-SA算法流程圖,具體的算法步驟為:

圖4 FTC-SA算法流程圖

步驟1:根據(jù)式(6)設(shè)定初始溫度T0,同時(shí)對(duì)終止溫度Tend、內(nèi)循環(huán)迭代次數(shù)L、溫度衰減參數(shù)α、波谷控制參數(shù)β、波動(dòng)間隔參數(shù)λ、記憶向量Cbest以及外循環(huán)迭代次數(shù)k進(jìn)行初始化設(shè)定,并根據(jù)城市編碼隨機(jī)產(chǎn)生一個(gè)初始解C0,令Cold=C0,T=T0;

步驟2:重置內(nèi)循環(huán)迭代次數(shù),令j=1;

步驟3:根據(jù)多鄰域搜索機(jī)制對(duì)當(dāng)前解Cold進(jìn)行擾動(dòng),利用貪心策略確定新解Cnew;

步驟4:計(jì)算并比較新解Cnew和當(dāng)前解Cold對(duì)應(yīng)的總路徑距離,若ΔD≤0,接受Cnew作為新的當(dāng)前解,即Cold=Cnew;否則,按概率P接受新解;

步驟5:當(dāng)k=1時(shí),直接將當(dāng)前解記錄在記憶向量Cbest中;當(dāng)k>1時(shí),若當(dāng)前解為更優(yōu)解,將其更新在記憶向量Cbest;

步驟6:判斷是否完成迭代,若j

步驟7:判斷是否完成退火,若T

3 試驗(yàn)結(jié)果與分析

圖5 模具零件的孔群分布

利用MATLAB 2017b軟件對(duì)本文所提的FTC-SA算法進(jìn)行仿真,并與標(biāo)準(zhǔn)的GA、ACO、SA算法及多次回火升溫的MSA算法[14]進(jìn)行性能對(duì)比。FTC-SA算法的初始化參數(shù)設(shè)定如下:初始溫度接受概率P0=0.6,終止溫度Tend=0.001,內(nèi)循環(huán)迭代次數(shù)L=200,溫度衰減參數(shù)α=0.993、波谷控制參數(shù)β=1.2、波動(dòng)間隔參數(shù)λ=100。

對(duì)各算法分別仿真10次,得到孔群在機(jī)測(cè)量路徑優(yōu)化結(jié)果,如表1所示?？梢钥闯?FTC-SA算法優(yōu)化的最優(yōu)值和平均值均為最佳,其中最優(yōu)值相比于GA、ACO、SA、MSA算法分別縮短55.52、42.12、9.7、4.85;平均值相應(yīng)地分別縮短95.31、59.17、30.66、10.61。

表1 不同算法的優(yōu)化結(jié)果 (mm)

將各算法優(yōu)化的結(jié)果繪制成箱形圖,如圖6所示。箱形圖是一種顯示數(shù)據(jù)離散程度的統(tǒng)計(jì)圖,可以體現(xiàn)出各算法優(yōu)化效果的穩(wěn)定性。可以發(fā)現(xiàn),FTC-SA算法的箱形圖位置最低,四分位距也最小,說(shuō)明FTC-SA算法優(yōu)化的解的整體質(zhì)量和穩(wěn)定程度為最好;MSA算法優(yōu)化效果其次;GA、ACO、SA算法優(yōu)化效果較差。

圖6 不同算法的箱形圖

MSA算法與FTC-SA算法優(yōu)化的最短路徑如圖7所示,相應(yīng)的迭代過(guò)程如圖8所示。兩種算法優(yōu)化的最短路徑均未出現(xiàn)交叉現(xiàn)象,但FTC-SA算法優(yōu)化的解的質(zhì)量更高。圖7b對(duì)應(yīng)的城市遍歷序列為(1,45,43,18,29,30,46,20,9,19,7,44,26,3,25,2,5,27,17,28,37,16,4,6,38,8,39,40,41,10,12,22,42,32,23,34,13,14,35,15,36,50,11,21,48,31,33,24,49,47,1)。從迭代過(guò)程來(lái)看,FTC-SA算法表現(xiàn)出更強(qiáng)的解空間搜索能力,收斂速度也更快。

(a) MSA(D=2 583.37) (b) FTC-SA(D=2 578.52)圖7 MSA與FTC-SA算法最短路徑

圖8 MSA與FTC-SA算法迭代過(guò)程

4 結(jié)論

合理安排孔群的在機(jī)測(cè)量路徑,可以有效縮短測(cè)頭空行程距離,提高檢測(cè)效率,降低機(jī)床能耗。本文采用FTC-SA算法對(duì)大規(guī)?？兹旱脑跈C(jī)測(cè)量路徑優(yōu)化問(wèn)題進(jìn)行研究,建立了測(cè)頭遍歷路徑的數(shù)學(xué)模型和目標(biāo)函數(shù);通過(guò)對(duì)標(biāo)準(zhǔn)SA算法中的初始溫度設(shè)定、鄰域搜索機(jī)制、溫度控制函數(shù)進(jìn)行改進(jìn),提高了算法的局部收斂性能和全局尋優(yōu)能力;以某型號(hào)模具零件為對(duì)象進(jìn)行了實(shí)例分析,結(jié)果表明本文所提的FTC-SA算法可以獲得更好的求解質(zhì)量和優(yōu)化效果。