趙曉帥，曾志強(qiáng)，阮小琪，王俊元，杜文華

(中北大學(xué) 機(jī)械工程學(xué)院，太原 030051)

0 引言

伴隨著計(jì)算機(jī)、光學(xué)等技術(shù)的不斷發(fā)展，現(xiàn)代視覺(jué)理論研究的深入，以視覺(jué)理論為依據(jù)的影像測(cè)量技術(shù)發(fā)展速度越發(fā)迅猛。它作為一種新興的、非接觸式的測(cè)量技術(shù)，以其高精度、快速、非接觸式的特點(diǎn)在各個(gè)領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用。隨著工業(yè)生產(chǎn)對(duì)自動(dòng)化程度要求的不斷提高，為實(shí)現(xiàn)高效、快速、精確的測(cè)量，一方面可以提高測(cè)量軟件的性能，另一方面影像測(cè)量?jī)x的測(cè)量路徑規(guī)劃技術(shù)有待完善。

路徑規(guī)劃是指如何尋找從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，使得運(yùn)動(dòng)物體安全繞過(guò)障礙物，并且路徑長(zhǎng)度最短。蟻群算法的提出，為解決路徑規(guī)劃問(wèn)題提供了新的思路和方法，然而傳統(tǒng)的蟻群算法存在搜索時(shí)間比較長(zhǎng)、容易陷入局部最優(yōu)解、收斂速度慢等問(wèn)題。目前，在移動(dòng)機(jī)器人領(lǐng)域，路徑規(guī)劃是研究的熱點(diǎn)問(wèn)題，但是針對(duì)影像測(cè)量的路徑規(guī)劃的研究較少。

針對(duì)影像測(cè)量的路徑規(guī)劃問(wèn)題，本文提出通過(guò)蟻群算法對(duì)影像測(cè)量?jī)x的測(cè)量路徑進(jìn)行規(guī)劃，使得測(cè)量平臺(tái)的移動(dòng)距離最短、減少耗時(shí)。同時(shí)針對(duì)蟻群算法搜索時(shí)間長(zhǎng)、收斂速度慢的問(wèn)題，從初始信息素設(shè)置、信息素更新機(jī)制和迭代停止條件三個(gè)方面進(jìn)行改進(jìn)，以提高算法的整體求解性能。

1 測(cè)量路徑規(guī)劃分析

1.1 影像測(cè)量系統(tǒng)工作原理

如圖1所示，基于本課題組現(xiàn)有HT-4030型影像測(cè)量?jī)x，該測(cè)量設(shè)備由運(yùn)動(dòng)控制系統(tǒng)、自動(dòng)聚焦系統(tǒng)、影像測(cè)量軟件和上位工控機(jī)4部分組成。它的基本工作原理是在完成零件的擺放之后，利用運(yùn)動(dòng)控制系統(tǒng)驅(qū)動(dòng)工作平臺(tái)沿X和Y軸方向運(yùn)動(dòng)，使得待測(cè)工件移動(dòng)至視覺(jué)探頭的視野范圍內(nèi)，其自動(dòng)聚焦系統(tǒng)由影像測(cè)量模塊和聚焦定位模塊組成，通過(guò)影像信息反饋驅(qū)動(dòng)Z軸做垂直于工作平臺(tái)的上下運(yùn)動(dòng)，獲取清晰、銳利的圖像，達(dá)到自動(dòng)聚焦的目的，最后應(yīng)用視覺(jué)影像測(cè)量原理，對(duì)待測(cè)工件的幾何元素進(jìn)行測(cè)量。

圖1 HT-4030三維結(jié)構(gòu)圖

1.2 測(cè)量路徑規(guī)劃分析

在實(shí)際測(cè)量過(guò)程中，HT-4030型影像測(cè)量?jī)x往往通過(guò)驅(qū)動(dòng)工作平臺(tái)改變待測(cè)工件和相機(jī)的位置關(guān)系，同樣也可將這一過(guò)程視待測(cè)工件為靜止的，驅(qū)動(dòng)測(cè)量相機(jī)在做X和Y軸的運(yùn)動(dòng)，為便于分析，本文采用第二種方式進(jìn)行說(shuō)明。則測(cè)量過(guò)程可以描述為：相機(jī)移動(dòng)至采樣位置，此時(shí)相機(jī)暫停運(yùn)動(dòng)并進(jìn)行圖像采集，采集的圖像存儲(chǔ)至上位工控機(jī)，然后測(cè)量相機(jī)移動(dòng)至下一個(gè)采樣位置。如果工作臺(tái)上存在n個(gè)待測(cè)零件，并且將每個(gè)零件視為一個(gè)采樣點(diǎn)，則本文的測(cè)量路徑規(guī)劃問(wèn)題可具體描述為：采樣點(diǎn)集合Ω0={P(x0,y0),P(x1,y1),...,P(xn,yn)}，測(cè)量相機(jī)從初始位置出發(fā)，依次在采樣點(diǎn)Pi(xi,yi)(i=1,2,...,n)處采集圖像，最后返回初始位置。

測(cè)量相機(jī)在完成所有零件測(cè)量時(shí)所走路徑的長(zhǎng)短因測(cè)量路徑的不同存在很大差異，當(dāng)相機(jī)運(yùn)動(dòng)速度一定的條件下，測(cè)量路徑越短，工作平臺(tái)移動(dòng)過(guò)程消耗的時(shí)間越少。因此，在完成一個(gè)零件的測(cè)量后，如何選取下一個(gè)測(cè)量零件，以什么策略進(jìn)行下一個(gè)測(cè)量零件的選取，對(duì)于整個(gè)測(cè)量系統(tǒng)完成全部測(cè)量工作的運(yùn)行時(shí)間有著很大的影響。

上述問(wèn)題可以視為旅行商問(wèn)題，即TSP(Travelling Salesman Problem)，是計(jì)算從某一城市出發(fā)，拜訪所有城市并返回出發(fā)城市的最短拜訪路徑的問(wèn)題，蟻群算法的提出為解決此類(lèi)問(wèn)題提供了新的思路和方法。

2 改進(jìn)的蟻群算法

研究發(fā)現(xiàn)在覓食過(guò)程中，螞蟻會(huì)在其走過(guò)的路徑上分泌一種被稱作信息素的化學(xué)物質(zhì)，其它螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知到信息素的存在及其濃度高低，并且傾向于朝著該物質(zhì)濃度高的方向移動(dòng)，通過(guò)這種信息交流方式，最終選擇到食物的最短路徑。針對(duì)傳統(tǒng)蟻群算法搜索時(shí)間長(zhǎng)、收斂速度慢的問(wèn)題，本文提出引入模糊集合理論和信息熵分別對(duì)信息素更新機(jī)制、收斂停止條件進(jìn)行改進(jìn)，以提高算法的整體求解性能。

2.1 基于模糊集合的信息素更新機(jī)制

t+n時(shí)刻路徑(i,j)上信息素濃度的計(jì)算公式為：

(1)

(2)

(3)

其中，Q表示信息素濃度總量，Lk表示螞蟻k在本次循環(huán)中所走路徑長(zhǎng)度。

模糊集合的定義：假設(shè)存在論域U，對(duì)于U上的模糊子集A，是指存在任意的x∈U，都能確定一個(gè)位于單位區(qū)間的映射μA(x):U→[0,1]，用μA(x)表示x屬于A的程度。這個(gè)映射稱為A的隸屬度函數(shù)，μA(x)則被稱為U中的元素對(duì)模糊子集A的隸屬度，主要用來(lái)表示x屬于A的程度，且μA(x)∈[0,1]，μA(x)越接近0則表示x屬于A的程度越小。

本文引入模糊子集與隸屬度的概念對(duì)蟻群算法中螞蟻在每次循環(huán)中搜索到的路徑長(zhǎng)短進(jìn)行評(píng)估，首先定義模糊子集A=“路徑較短”。隸屬度函數(shù)選擇Z函數(shù)，它是一種偏小型下降函數(shù)，它的數(shù)學(xué)表達(dá)式為：

y=zmf(x,[ab])

(4)

其中，a代表本次迭代中所尋找到的最短路徑長(zhǎng)度，b代表本次迭代中所尋找到的最長(zhǎng)路徑長(zhǎng)度。為了加快蟻群系統(tǒng)的搜索速度，并且對(duì)模糊子集更加充分的利用，系統(tǒng)在較短的那些路徑進(jìn)行信息素更新，建立一個(gè)新的信息素計(jì)算模型：

(5)

其中，μt(k)表示螞蟻k對(duì)于A的隸屬度。

則信息素的更新規(guī)則變成：

(6)

2.2 基于信息熵的收斂判據(jù)

在經(jīng)典蟻群算法中，算法的終止條件是判斷是否達(dá)到系統(tǒng)的最大迭代次數(shù)Ncmax，而對(duì)不同規(guī)模的問(wèn)題進(jìn)行求解時(shí)，算法完成收斂的迭代次數(shù)差別很大；為了得到一個(gè)較好的搜索結(jié)果，Ncmax的值往往設(shè)置的比較高，以避免算法在找到最優(yōu)解之前停止運(yùn)行。但是在本文的零件測(cè)量路徑規(guī)劃問(wèn)題中，對(duì)算法的運(yùn)行時(shí)間也要求做到盡量低，通過(guò)設(shè)置一個(gè)確定的Ncmax作為算法的收斂條件是不完善的，對(duì)于不同規(guī)模的零件測(cè)量工作，很難界定一個(gè)合適的Ncmax。算法初期每條路徑上的信息量是隨機(jī)的，每只螞蟻在一次迭代中需要進(jìn)行n-1次選擇才能得到最終解，而螞蟻的每一次選擇都具有不確定性，整個(gè)蟻群系統(tǒng)的路徑選擇不確定性越大，搜索到的解空間范圍就越大，蟻群系統(tǒng)的種群平均信息熵也會(huì)因?yàn)椴淮_定性的增大而增大。為此，引入信息熵對(duì)系統(tǒng)的不確定性進(jìn)行衡量，根據(jù)螞蟻系統(tǒng)的種群平均信息熵的收斂性判斷算法是否收斂。

一個(gè)離散型隨機(jī)變量的信息熵可以定義為：

(7)

其中,pi表示狀態(tài)發(fā)生的概率，0≤pi≤1(i=1,2,…,n)，且p1+p2+…+pn=1。

引入信息熵后，算法在第t次迭代中，蟻群系統(tǒng)的種群信息熵定義為：

(8)

其中，pij(t)表示螞蟻t時(shí)刻從當(dāng)前節(jié)點(diǎn)i走向節(jié)點(diǎn)j的概率。

信息熵判據(jù)為：

(9)

其中，ε代表算法的停止門(mén)限，且ε∈(0，0.01)。

2.3 改進(jìn)蟻群算法的實(shí)現(xiàn)流程

Step1：初始化各參數(shù)，形成初始信息素矩陣。

Step2：散布m只螞蟻至不同位置。

Step3：路徑選擇。計(jì)算每只螞蟻的轉(zhuǎn)移概率，通過(guò)輪盤(pán)賭選擇的方式選擇下次將要到達(dá)的節(jié)點(diǎn)，并將所選的節(jié)點(diǎn)添加到禁忌表。

Step4：計(jì)算螞蟻所走路徑長(zhǎng)度Lk對(duì)于模糊子集A的隸屬度μ(k)，并與閾值φ比較，若μ(k)>φ，則進(jìn)行信息素更新。

Step5：根據(jù)式(6)進(jìn)行信息素更新。

Step6：判斷算法是否達(dá)到停止條件。若Haver<ε(ε為預(yù)設(shè)值，ε∈(0，2])，算法結(jié)束，輸出最終結(jié)果，否則清空所有禁忌表，并跳轉(zhuǎn)至Step2。

改進(jìn)的蟻群算法流程圖如圖2所示。

圖2 改進(jìn)蟻群算法流程

3 實(shí)驗(yàn)及分析

為證明基于改進(jìn)蟻群算法的影響測(cè)量路徑規(guī)劃的正確性和可行性，本文進(jìn)行了實(shí)驗(yàn)驗(yàn)證。將55個(gè)公稱直徑為8mm的e型擋圈隨機(jī)散布到測(cè)量平臺(tái)上，通過(guò)自主研發(fā)的圖像采集系統(tǒng)采集涵蓋所有待測(cè)零件的圖像，進(jìn)行相應(yīng)的圖像處理后獲取各個(gè)零件的位置信息如圖。算法中各個(gè)參數(shù)設(shè)置如下：蟻數(shù)m=55，α=1.5，β=3，ρ=0.35，ε=0.009。圖3和圖4分別為傳統(tǒng)逐列測(cè)量的測(cè)量路徑和改進(jìn)蟻群算法的測(cè)量路徑。

圖3 逐列測(cè)量路徑

圖4 改進(jìn)蟻群算法測(cè)量路徑

為驗(yàn)證本文提出的改進(jìn)蟻群算法的有效性，將傳統(tǒng)測(cè)量方式、傳統(tǒng)蟻群算法和改進(jìn)蟻群算法的測(cè)量路徑長(zhǎng)度、測(cè)量平臺(tái)運(yùn)行時(shí)間進(jìn)行了比較，其結(jié)果如表1所列。通過(guò)表1中的數(shù)據(jù)可以看到，不管從測(cè)量路徑的長(zhǎng)度，還是從測(cè)量平臺(tái)測(cè)量過(guò)程的運(yùn)行時(shí)間上，傳統(tǒng)蟻群算法和改進(jìn)蟻群算法的測(cè)量路徑優(yōu)化相比傳統(tǒng)的影像測(cè)量方式有大幅度的改善，并且改進(jìn)蟻群算法相對(duì)傳統(tǒng)蟻群算法的運(yùn)行時(shí)間平均減少27”53。

表1 三種測(cè)量路徑性能比較

4 結(jié)束語(yǔ)

針對(duì)影像測(cè)量?jī)x測(cè)量路徑問(wèn)題，本文提出基于改進(jìn)蟻群算法的影像測(cè)量路徑規(guī)劃方法。首先對(duì)影像測(cè)量?jī)x測(cè)量路徑問(wèn)題進(jìn)行分析，將其轉(zhuǎn)化為求解TSP問(wèn)題；其次針對(duì)傳統(tǒng)蟻群算法解決TSP問(wèn)題出現(xiàn)的搜索時(shí)間長(zhǎng)、收斂速度慢的問(wèn)題，提出引入模糊集合和隸屬度的概念對(duì)信息素更新機(jī)制進(jìn)行改進(jìn)，減少搜索時(shí)間，提高收斂速度；引入信息熵概念，對(duì)算法的收斂判據(jù)進(jìn)行改進(jìn)。最后實(shí)現(xiàn)了基于改進(jìn)蟻群算法的影像測(cè)量路徑規(guī)劃并進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的逐行逐列、傳統(tǒng)蟻群算法的測(cè)量路徑相比，該方法能有效減少測(cè)量路徑的長(zhǎng)度和平臺(tái)的運(yùn)行時(shí)間，證明了該方法是可行有效的。