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

王冠中 王士軍 冉川東

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

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

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

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

1 自由曲面的測點檢測過程

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

圖1 局部檢測路徑示意圖

2 差分進化算法簡介

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

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

3.1 編碼方式

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

3.2 初始化總體

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

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

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

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

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

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

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

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

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

基準(zhǔn)誤差是零件坐標(biāo)系關(guān)于夾具坐標(biāo)系的偏差，影響零件坐標(biāo)系到夾具坐標(biāo)系的實際轉(zhuǎn)換矩陣，使實際轉(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ù)啟動策略

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

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

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

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

（4）多次運行差分進化算法：差分進化算法會在不同的初始化條件下多次運行，每次運行都有獨立的初始種群。

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

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

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

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

圖2 改進差分進化算法流程圖

（1）生成初始種群。

（2）進行種群個體的適應(yīng)度值評估。

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

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

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

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

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

4 實驗研究

4.1 Matlab 仿真對比實驗

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

圖3 Matlab 仿真實驗自由曲面

在該曲面上隨機選取50 個點作為測頭移動路徑的測點，取其中10 個點的坐標(biāo)，見表1。

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

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

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

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

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

表2 仿真對比實驗數(shù)據(jù)

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

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

4.2 實際檢測對比實驗

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

表3 實際檢測實驗對比數(shù)據(jù)表

圖6 檢測過程

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

5 結(jié)語

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