基于改進(jìn)差分進(jìn)化算法的自由曲面測(cè)量路徑優(yōu)化

王冠中 王士軍 冉川東

（山東理工大學(xué)機(jī)械工程學(xué)院，山東 淄博 255000）

隨著社會(huì)的不斷進(jìn)步，應(yīng)用于動(dòng)力機(jī)械、航海航空和其他工業(yè)等領(lǐng)域的機(jī)械零件呈現(xiàn)結(jié)構(gòu)精細(xì)、曲面復(fù)雜等特點(diǎn)，而零件的形面精度直接決定了它所構(gòu)成的產(chǎn)品質(zhì)量和性能，因此，高效率、高精度曲面測(cè)量技術(shù)的研究與開發(fā)具有十分重要的理論意義，其對(duì)生產(chǎn)制造也有實(shí)際應(yīng)用價(jià)值。自由復(fù)雜曲面的計(jì)算機(jī)建模過程中，需要使用到曲面測(cè)點(diǎn)檢測(cè)技術(shù)，該技術(shù)所用到的主要設(shè)備為三坐標(biāo)測(cè)量機(jī)。在計(jì)算機(jī)中，曲面由許多密密麻麻的測(cè)點(diǎn)組成，為了提高檢測(cè)效率，就需要找到一條既能讓測(cè)頭掃過曲面全部，又能使測(cè)頭移動(dòng)的總距離最短的檢測(cè)路徑，并且能夠不重復(fù)地走過曲面上需要的所有點(diǎn)[1]。

國(guó)內(nèi)外學(xué)者對(duì)于路徑優(yōu)化問題方面做了許多的研究，白蕓等學(xué)者通過試驗(yàn)表明，差分進(jìn)化算法在解決旅行商問題時(shí)的收斂逐步優(yōu)化，最大程度排除旅行商問題內(nèi)部存在的動(dòng)態(tài)誤差，具有較強(qiáng)的優(yōu)化能力，但差分進(jìn)化算法收斂速度慢，容易陷入局部最優(yōu)化問題[2]；李中偉等學(xué)者提出了改進(jìn)反序-雜交算子應(yīng)用于差分進(jìn)化算法[3]，該算子使算法在搜索后期，能夠有效地改善差分進(jìn)化算法收斂速度慢的問題，同時(shí)避免了原來(lái)逆轉(zhuǎn)操作中對(duì)基因位置的限制；梅覓等學(xué)者則提出了一種新的交叉操作——?jiǎng)⒑＝徊娌僮鱗4]，這種交叉操作方法取代了常規(guī)的遺傳交叉算子，包括順序交叉、循環(huán)交叉等，這些交叉操作后出現(xiàn)的子代有一些缺點(diǎn)，例如不能很好地保留父代的優(yōu)秀基因，而子代需要做些改動(dòng)才能保留。新的交叉操作則彌補(bǔ)了傳統(tǒng)遺傳算法隨機(jī)生成初始種群的不足；而張敬敏等學(xué)者提出了改進(jìn)差分進(jìn)化算法用于求解JSP 問題，算法中通過改進(jìn)算法中的變異算子以及縮放因子，來(lái)提高算法的運(yùn)行效率和種群的多樣性[5]。

以上文獻(xiàn)所述都是基于求解TSP 問題的差分進(jìn)化算法的改進(jìn)，通過延伸和拓展，差分進(jìn)化算法也可應(yīng)用于求解自由曲面的測(cè)點(diǎn)檢測(cè)路徑規(guī)劃問題，但有所不同的是：TSP 問題是一個(gè)二維平面求解路徑規(guī)劃問題，而自由曲面測(cè)點(diǎn)坐標(biāo)檢測(cè)路徑規(guī)劃問題則是一個(gè)三維問題。本文設(shè)計(jì)了改進(jìn)的差分進(jìn)化算法，并經(jīng)過實(shí)驗(yàn)驗(yàn)證表明，改進(jìn)的差分進(jìn)化算法能夠高效、穩(wěn)定地完成自由曲面測(cè)點(diǎn)檢測(cè)路徑優(yōu)化問題。

1 自由曲面的測(cè)點(diǎn)檢測(cè)過程

三坐標(biāo)測(cè)量機(jī)是自由曲面測(cè)點(diǎn)檢測(cè)過程中使用到的最主要設(shè)備，自由曲面測(cè)點(diǎn)檢測(cè)過程主要分為三段：第一段為測(cè)頭定位到曲面測(cè)點(diǎn)上方的A點(diǎn)，然后以固定的檢測(cè)速度沿著檢測(cè)路徑a移動(dòng)到曲面測(cè)點(diǎn)B點(diǎn)；第二段為當(dāng)B點(diǎn)檢測(cè)完成后，測(cè)頭以固定的回退速度沿著b到達(dá)C點(diǎn)；第三段為測(cè)頭從曲面上方C點(diǎn)以固定速度移動(dòng)到下一個(gè)檢測(cè)點(diǎn)E點(diǎn)上方的D點(diǎn)；最后重復(fù)第一段的運(yùn)動(dòng)，直到全部測(cè)點(diǎn)檢測(cè)完成，如圖1 所示。

圖1 局部檢測(cè)路徑示意圖

2 差分進(jìn)化算法簡(jiǎn)介

差分進(jìn)化算法（differential evolution algorithm）屬于一類基于群體差異的啟發(fā)式隨即搜索算法，這類算法具有高效性。該算法最初由Store R 和Price K 提出，用于求解Chebyshev 多項(xiàng)式。其演化流程與傳統(tǒng)的遺傳算法非常接近，基本包括變異、交叉和選擇操作，然而具體的定義又有所不同，其基本思想為：首先，隨機(jī)產(chǎn)生一個(gè)初始種群，計(jì)算在種群中隨機(jī)選擇的兩個(gè)不同個(gè)體的向量差，并將這個(gè)向量差與第三個(gè)個(gè)體相加，以此來(lái)產(chǎn)生新的個(gè)體；然后，產(chǎn)生的新個(gè)體會(huì)與當(dāng)代種群中相對(duì)應(yīng)的個(gè)體進(jìn)行適應(yīng)度值的比較，若新個(gè)體的適應(yīng)度值高于當(dāng)前個(gè)體，在下一代中，新個(gè)體將會(huì)取代舊個(gè)體，否則將保留舊個(gè)體進(jìn)入下一代的循環(huán)，直至達(dá)到最高迭代次數(shù)。通過這樣的演化過程，不斷保留優(yōu)秀個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索逐步接近最優(yōu)解。

3 差分進(jìn)化算法的設(shè)計(jì)與改進(jìn)

3.1 編碼方式

在解決TSP 問題時(shí)，有多種編碼方式可供選擇，其中之一是對(duì)經(jīng)過每個(gè)城市的順序進(jìn)行逐次編碼，即采用整體離散化編碼，例如當(dāng)編碼為3271456 時(shí)，表示測(cè)頭從3 號(hào)點(diǎn)出發(fā)，依次經(jīng)過點(diǎn)2、7、1、4、5、6，完成該條路徑的檢測(cè)。

3.2 初始化總體

3.3 適應(yīng)度函數(shù)

從三坐標(biāo)測(cè)量機(jī)測(cè)頭檢測(cè)過程的描述和示意圖中可以看出：測(cè)頭的單次運(yùn)動(dòng)路徑D=La+Lb+Lc，測(cè)頭的單次運(yùn)行時(shí)間則為T=ta+tb+tc，而無(wú)論檢測(cè)路徑如何變化，AB段及BC段的運(yùn)動(dòng)過程總是固定不變的，即路徑和運(yùn)行時(shí)間不變，因此，在上述兩個(gè)表達(dá)式中，只有Lc和tc影響表達(dá)式的結(jié)果，簡(jiǎn)化公式后，測(cè)點(diǎn)檢測(cè)過程就簡(jiǎn)化為了三維狀態(tài)下的求解TSP 問題。同遺傳算法一樣，差分近乎算法也是依靠適應(yīng)度函數(shù)來(lái)判斷解的優(yōu)劣，即適應(yīng)度函數(shù)是衡量解的質(zhì)量或優(yōu)劣的標(biāo)準(zhǔn)。目標(biāo)函數(shù)可以定義為：（Lci表示為兩個(gè)測(cè)點(diǎn)之間的測(cè)頭移動(dòng)距離），當(dāng)D最小時(shí)，優(yōu)化的結(jié)果最好。在差分進(jìn)化算法中，通常會(huì)選擇一定比例的個(gè)體進(jìn)行變異操作，然后通過交叉操作產(chǎn)生新的個(gè)體，最后通過適應(yīng)度函數(shù)來(lái)選擇保留哪些個(gè)體，由目標(biāo)函數(shù)可知，適應(yīng)度函數(shù)的目標(biāo)是最小化路徑的總長(zhǎng)度，因此適應(yīng)度值越大，代表路徑越短，個(gè)體越優(yōu)秀，所以適應(yīng)度函數(shù)確定為目標(biāo)函數(shù)的倒數(shù)，即：

3.4 改進(jìn)的適應(yīng)性突變策略

傳統(tǒng)DE 算法中的突變運(yùn)算是從初始化的群體中隨機(jī)選擇兩個(gè)不同的個(gè)體進(jìn)行差分計(jì)算，然后與第三個(gè)不同的個(gè)體進(jìn)行加權(quán)計(jì)算。該算法有不同的突變策略，其中最主流的策略[6]包括：

以上策略的提出在一定程度上都提高了差分進(jìn)化算法的收斂速度和收斂性，而You X M 等學(xué)者提出了一種新的突變策略“DE/average/2”[7]，該策略的表達(dá)式為

這個(gè)新策略在仿真實(shí)驗(yàn)中的結(jié)果表明，與其他主流算法相比具有更強(qiáng)的求優(yōu)能力，但是這個(gè)新策略存在收斂速度慢、迭代時(shí)間長(zhǎng)、最優(yōu)結(jié)果不穩(wěn)定的問題。

為了提高算法求優(yōu)能力的穩(wěn)定性以及算法收斂速度慢的問題，在這里，我們提出一種新的突變策略，該策略的表達(dá)式為

新的突變策略以每代種群中最優(yōu)秀個(gè)體以及兩個(gè)隨機(jī)的不同個(gè)體為基礎(chǔ)，在此基礎(chǔ)上分別求3 個(gè)個(gè)體的平均值，最優(yōu)秀個(gè)體與隨機(jī)個(gè)體的差值，差值并分別乘以一個(gè)適應(yīng)度值F，依次來(lái)產(chǎn)生一個(gè)新的向量。其中適應(yīng)度值F是一個(gè)動(dòng)態(tài)調(diào)整的自適應(yīng)因子，F(xiàn)的范圍則是在均值為0，標(biāo)準(zhǔn)差為0.5 之間的隨機(jī)數(shù)，這個(gè)隨機(jī)數(shù)按照下面公式進(jìn)行調(diào)整：

該公式使得算法在更新自適應(yīng)因子時(shí)，如果個(gè)體當(dāng)前的適應(yīng)度值小于其歷史適應(yīng)度值，則自適應(yīng)因子增加，使得個(gè)體具有更好的變異性；如果適應(yīng)度值變大，則適應(yīng)度自適應(yīng)因子減小，使得個(gè)體更加傾向于利用當(dāng)前已經(jīng)找到的優(yōu)解，這樣可以在全局搜索和局部搜索之間進(jìn)行更好的平衡。

基準(zhǔn)誤差是零件坐標(biāo)系關(guān)于夾具坐標(biāo)系的偏差，影響零件坐標(biāo)系到夾具坐標(biāo)系的實(shí)際轉(zhuǎn)換矩陣，使實(shí)際轉(zhuǎn)換矩陣在理想轉(zhuǎn)換矩陣的基礎(chǔ)上又增加了偏差轉(zhuǎn)換矩陣。零件從工序k-1到k，將k-1的輸出X(k-1)作為k的輸入，X(k-1)由基準(zhǔn)選擇矩陣D(k)得到第k道工序的定位基準(zhǔn)Da(k)，

3.5 重復(fù)啟動(dòng)策略

在差分進(jìn)化算法中，重復(fù)啟動(dòng)策略是一種啟發(fā)式技巧，在提高DE 算法的性能，尤其是處理復(fù)雜、多模態(tài)的優(yōu)化問題時(shí)具有很好的效果。重復(fù)啟動(dòng)策略的運(yùn)行機(jī)制如下。

（1）初始化種群：差分進(jìn)化算法首先隨機(jī)生成一個(gè)種群，每個(gè)種群代表一個(gè)潛在的解決方案，這些個(gè)體的參數(shù)值實(shí)在問題定義的范圍內(nèi)隨機(jī)選擇的。

（2）目標(biāo)函數(shù)評(píng)估：對(duì)于每個(gè)個(gè)體，算法計(jì)算目標(biāo)函數(shù)的值，這個(gè)值則衡量了該個(gè)體解決方案的質(zhì)量，即優(yōu)化路徑長(zhǎng)度的值。

（3）重復(fù)啟動(dòng)策略：在差分進(jìn)化算法中，通常添加mutation、crossover 和selection 等操作來(lái)演化種群，以此來(lái)尋找更優(yōu)的解。重復(fù)啟動(dòng)策略的核心思想是在不同的種群初始化條件下，多次運(yùn)行差分進(jìn)化算法。

（4）多次運(yùn)行差分進(jìn)化算法：差分進(jìn)化算法會(huì)在不同的初始化條件下多次運(yùn)行，每次運(yùn)行都有獨(dú)立的初始種群。

（5）選擇最佳解：在每次運(yùn)行結(jié)束后，都會(huì)選擇最佳的個(gè)體作為該次運(yùn)行的結(jié)果，最終，從多次運(yùn)行中選擇具有最佳目標(biāo)函數(shù)值的個(gè)體作為全局最優(yōu)解。

實(shí)驗(yàn)表明，多重啟動(dòng)策略通過多次獨(dú)立運(yùn)行差分進(jìn)化算法，每次運(yùn)行都能從不同的起點(diǎn)開始，增加了算法的全局搜索性能，在一定程度上克服了局部最優(yōu)解的缺陷。同時(shí)，重復(fù)啟動(dòng)策略在一定程度上減輕了算法對(duì)于初始種群選擇的依賴，提高了算法的求優(yōu)穩(wěn)定性。

3.6 改進(jìn)差分進(jìn)化算法結(jié)構(gòu)

改進(jìn)差分進(jìn)化算法的流程圖如圖2 所示，基本流程如下：

圖2 改進(jìn)差分進(jìn)化算法流程圖

（1）生成初始種群。

（2）進(jìn)行種群個(gè)體的適應(yīng)度值評(píng)估。

（3）通過新的策略、交叉、變異操作得到新的個(gè)體。

（4）判定個(gè)體的適應(yīng)度值是否大于上一代個(gè)體的適應(yīng)度值。

（5）取適應(yīng)度值好的個(gè)體進(jìn)行下一輪迭代。

（6）基于歷史適應(yīng)度值更新自適應(yīng)因子。

（7）判定迭代次數(shù)是否到達(dá)最大值，若是，則輸出最優(yōu)解；若否，則進(jìn)行適應(yīng)度值計(jì)算并繼續(xù)進(jìn)行步驟4。

4 實(shí)驗(yàn)研究

4.1 Matlab 仿真對(duì)比實(shí)驗(yàn)

為了驗(yàn)證新策略的運(yùn)行穩(wěn)定性和收斂速度較“DE/average/2”有所提升，任意設(shè)計(jì)一個(gè)自由曲面作為仿真對(duì)比試驗(yàn)中的實(shí)驗(yàn)對(duì)象，如圖3 所示，該曲面的曲面表達(dá)式為Z=3x2+y2+6。

圖3 Matlab 仿真實(shí)驗(yàn)自由曲面

在該曲面上隨機(jī)選取50 個(gè)點(diǎn)作為測(cè)頭移動(dòng)路徑的測(cè)點(diǎn)，取其中10 個(gè)點(diǎn)的坐標(biāo)，見表1。

表1 三維坐標(biāo)點(diǎn)

使用Matlab2021b 分別編寫基于文獻(xiàn)[7]中提到的策略“DE/average/2”和基于本文提到的新策略的兩種差分進(jìn)化算法，在兩個(gè)代碼程式中，初始種群數(shù)目均為10 000，種群元素值的上下限均為500和-500，初始變異因子為F0=0.6，交叉概率為CR=0.1，自適應(yīng)參數(shù)為adaptF=F+rand()×0.1，分別用兩種算法對(duì)50 個(gè)測(cè)點(diǎn)進(jìn)行最優(yōu)路徑規(guī)劃，同時(shí)使用重復(fù)啟動(dòng)策略對(duì)兩種算法運(yùn)行后的數(shù)據(jù)進(jìn)行多次比較，優(yōu)化軌跡和優(yōu)化過程曲線如圖4 和圖5所示。

圖4 使用 DE/average/2策略生成的優(yōu)化路徑和優(yōu)化過程曲線

圖5 使用新策略生成的優(yōu)化路徑和優(yōu)化過程曲線

兩種策略的最優(yōu)路徑長(zhǎng)度和優(yōu)化時(shí)間見表2。

表2 仿真對(duì)比實(shí)驗(yàn)數(shù)據(jù)

從表2 中可以看出，“DE/average/2”策略的三次仿真實(shí)驗(yàn)的平均路徑長(zhǎng)度為142.05 mm，平均優(yōu)化時(shí)間為76 s，而本文提出的新策略的三次仿真實(shí)驗(yàn)的 平均路徑長(zhǎng)度為126.57 mm，平均優(yōu)化時(shí)間為68 s，因此可以得出新策略相較于 “DE/average/2”策略在優(yōu)化速度和收斂精度上都提高了10%左右。

而從圖4 和圖5 的仿真對(duì)比試驗(yàn)優(yōu)化路徑圖和優(yōu)化過程曲線中可以看出，“DE/average/2”策略在4 000 代之后曲線仍在收斂，且收斂精度保持在143 mm 左右，而新策略在4 000 代之后曲線趨于平穩(wěn)，且收斂精度保持在128 mm 左右，說(shuō)明新策略相較于“DE/average/2”策略在求優(yōu)穩(wěn)定性和收斂速度上要好。

4.2 實(shí)際檢測(cè)對(duì)比實(shí)驗(yàn)

通過使用德國(guó)的ZEISS SPECTRUM 三坐標(biāo)測(cè)量機(jī)來(lái)進(jìn)行實(shí)驗(yàn)參數(shù)曲面的檢測(cè)實(shí)驗(yàn)，在選擇機(jī)器參數(shù)時(shí)，測(cè)球直徑選擇3 mm，固定的定位和回退距離設(shè)置為5 mm，測(cè)頭的移動(dòng)速度為10 mm/s，分別對(duì)使用“DE/average/2”策略的差分進(jìn)化算法和優(yōu)化策略后的差分進(jìn)化算法的50 個(gè)測(cè)點(diǎn)進(jìn)行最小路徑檢測(cè)，檢測(cè)過程如圖6 所示，在檢測(cè)過程中，使用圖3 曲面，并分別對(duì)兩種策略算法進(jìn)行計(jì)時(shí)，統(tǒng)計(jì)的實(shí)驗(yàn)結(jié)果見表3。

表3 實(shí)際檢測(cè)實(shí)驗(yàn)對(duì)比數(shù)據(jù)表

圖6 檢測(cè)過程

從表3 的數(shù)據(jù)中可以看出，在實(shí)際的測(cè)點(diǎn)檢測(cè)過程中，新策略求優(yōu)的耗時(shí)和收斂精度相較于“DE/average/2”策略都減少了10%左右。

5 結(jié)語(yǔ)

在自由曲面測(cè)點(diǎn)路徑優(yōu)化問題上，使用新策略的差分進(jìn)化算法在測(cè)量路徑最小值求解的穩(wěn)定性上有較好的提升；就求優(yōu)速度以及最小值收斂精度兩方面，無(wú)論是在仿真實(shí)驗(yàn)還是實(shí)際檢驗(yàn)中，這兩方面的數(shù)據(jù)結(jié)果都提升了約10%，大大提高了實(shí)際生產(chǎn)中的效率。雖然改進(jìn)的新策略在穩(wěn)定性方面要好于“DE/average/2”策略，但仍有較低的概率出現(xiàn)最優(yōu)值過大的問題，需要進(jìn)一步的改進(jìn)。