基于改進麻雀搜索算法的平面度誤差評定方法

姜春英, 張熙然, 王印超, 陶廣宏, 葉長龍

(1.沈陽航空航天大學(xué) 機電工程學(xué)院，遼寧 沈陽 110136；2.沈陽航空航天大學(xué) 人工智能學(xué)院，遼寧 沈陽 110136)

1 引 言

在平面度檢測國家標(biāo)準(zhǔn)規(guī)范中,對于平面度誤差檢測的評定方法[1]包括:最小包容區(qū)域法、最小二乘法、對角線平面法以及三遠點平面法。其中最小包容區(qū)域法的評定結(jié)果最接近理想平面度誤差值。常用的最小區(qū)域評定法[2]有:變換作圖法、旋轉(zhuǎn)變換法、變換計算法、極點計算法、計算幾何法等。然而對于其搜索及判別相對耗時,不能滿足當(dāng)今制造業(yè)高效測量的需求。

隨著智能優(yōu)化算法的發(fā)展,基于群體搜索的仿生智能優(yōu)化算法引起了形位誤差評定領(lǐng)域相關(guān)學(xué)者極大關(guān)注。近年來國內(nèi)外許多相關(guān)學(xué)者將粒子群算法[3]、人工蜂群算法[4]、人工蟻群算法[5]、遺傳算法[6,7]等群智能算法成功應(yīng)用于形位誤差評定當(dāng)中,取得了較好的效果。羅鈞等[4]提出針對傳統(tǒng)人工蜂群算法,采用禁忌搜索策略并引入新角色牽引蜂,以提升算法收斂速度,增強跳出局部最優(yōu)的能力,并應(yīng)用于平面度誤差評定中;楊健等[8]研究了一種在傳統(tǒng)遺傳算法的基礎(chǔ)之上,引入模擬退火思想,應(yīng)用浮點數(shù)編碼、三段式交叉、輪盤式選擇以及貪婪選擇機制的改進遺傳算法,算法整體性能優(yōu)異,應(yīng)用于平面度誤差計算,精度顯著提高;畢立恒等[9]提出一種粒子群分群策略,將基本粒子群算法中的種群分成兩個部分,分別用來進行全局搜索和局部搜索,該方法提高了平面度誤差評定的精度。

2020年,Xue J K等[10]提出了麻雀搜索算法(sparrow search algorithm, SSA),作為一種新型基于群體智能的優(yōu)化方法,該算法結(jié)構(gòu)清晰、原理簡明易于編程實現(xiàn)且控制參數(shù)較少、收斂速度快,被成功用于解決圖像處理[11]、路徑規(guī)劃[12,13]、故障診斷、車間調(diào)度[14]、功率預(yù)測[15]等各種工程領(lǐng)域的優(yōu)化問題。然而當(dāng)處理復(fù)雜優(yōu)化問題時,基本SSA算法仍存在搜索速度變慢、全局搜索和局部開采能力不平衡導(dǎo)致過早收斂、個體多樣性減少以及迭代后期難以跳出局部最優(yōu)等問題。

本文利用最小包容區(qū)域法對平面度誤差評估問題進行模型建立,針對數(shù)學(xué)模型提出一種基于Kent映射的改進麻雀搜索算法(improved sparrow search algorithm, ISSA),在算法初始化階段引入Kent混沌映射提高全局搜索能力,迭代過程中引入透鏡成像學(xué)習(xí)策略加強局部開發(fā)能力,以解決平面度誤差評定過程中出現(xiàn)的陷入局部最小、收斂速度慢和精度低等問題。

2 平面度評定的最小區(qū)域法數(shù)學(xué)模型

2.1 平面度誤差評定最小包容區(qū)域法

最小包容區(qū)域法符合國家標(biāo)準(zhǔn),并且與國際標(biāo)準(zhǔn)相一致。平面度誤差最小包容區(qū)域法評定如圖1所示。

圖1 平面度誤差示意圖Fig.1 Schematic diagram of flatness error

最小包容區(qū)域法評定平面度誤差fMZ實質(zhì)上就是搜索一個平面基準(zhǔn)方向,使得在該方向上包含所有測量點P兩平行平面M1、M2之間距離最小,且兩平行平面與被測實際平面的接觸狀態(tài)符合平面度最小包容區(qū)域判別的某一準(zhǔn)則。

在平面度誤差檢測國家標(biāo)準(zhǔn)中明確指出, 平面度最小包容區(qū)域判別法有以下3種準(zhǔn)則[1], 如圖2所示。

圖2 平面度誤差最小包容區(qū)域判別準(zhǔn)則Fig.2 Minimum zone criteria of flatness error

1) 三角形準(zhǔn)則:兩個最小區(qū)域面分別由3個高極點與1個低極點(或相反)確定,其中一個低極點(或高極點)的投影點位于3個高極點構(gòu)成的三角形的內(nèi)部或者邊緣線之上。

2) 交叉準(zhǔn)則:2個最小區(qū)域面由投影成相互交叉形式的2個高極點與2個低極點確定。

3) 直線準(zhǔn)則:2個最小區(qū)域面由投影成直線排列的2個高極點與1個低極點(或相反)確定。

最小包容區(qū)域法評定平面度誤差是以測量點為限制條件,使得所求評估基面方向上平面度包容區(qū)域最小的最優(yōu)化問題。因此可以轉(zhuǎn)化為對評估基面的平面方程參數(shù)優(yōu)化問題。

2.2 平面度誤差評定數(shù)學(xué)模型

根據(jù)標(biāo)準(zhǔn)中的平面度誤差定義,設(shè)通過最小包容區(qū)域法確定的基準(zhǔn)平面方程為

z=ax+by+c

(1)

式中a、b、c為平面方程系數(shù)。

假設(shè)被測面上若干測量點Pi(x,y,z),i=1,2,…,n;則測量點P相對于基準(zhǔn)平面的偏移量為

(2)

最小包容平面間的距離可以轉(zhuǎn)化為各測量點相對于基準(zhǔn)平面M0的最大與最小偏差之差,即平面度誤差建模示意圖如圖3所示,可以表示為

f=Dmax-Dmin

(3)

由文獻[16]可知a、b?1,故:

(4)

因而最小包容區(qū)域法平面度誤差評定問題轉(zhuǎn)變成對目標(biāo)函數(shù)f參數(shù)a、b的最優(yōu)化問題:

fMZ=minf(a,b)

(5)

根據(jù)目標(biāo)函數(shù)f可設(shè)計出SSA算法適應(yīng)度函數(shù)fit,

fit=1/(0.1+fMZ)

(6)

3 ISSA算法

3.1 SSA算法

SSA算法是根據(jù)自然界中麻雀的覓食行為和反捕食行為而衍生出的一種優(yōu)化方法見文獻[9],麻雀種群依照角色分工可以抽象為發(fā)現(xiàn)者、加入者以及偵查者3種,他們通過交流、協(xié)作和轉(zhuǎn)換來實現(xiàn)覓食。群體中有麻雀意識到危險時,整個種群就會立即躲避危險。麻雀覓食的過程也是搜索最優(yōu)解的過程。

SSA具有較好的全局探索和局部開發(fā)的能力,能夠促進麻雀向全局最優(yōu)值移動,有效避免“早熟”現(xiàn)象,與其它先進的算法相比仍能給出非常有競爭力的結(jié)果。該算法具有良好的魯棒性和收斂速度,是解決優(yōu)化問題的一種有效工具。

發(fā)現(xiàn)者麻雀位置更新的數(shù)學(xué)模型為

(7)

其中:Xi為第i只麻雀的位置向量;t代表當(dāng)前迭代數(shù);MaxIter為最大的迭代次數(shù);α為(0, 1]間的隨機數(shù);R2(R2∈[0, 1])和ST(ST∈[0.5, 1.0])分別表示預(yù)警閾值和安全閾值;Q是隨機數(shù)且滿足正態(tài)分布;L表示為每個元素全部為1的一個1×d的矩陣(d表示維數(shù))。

加入者麻雀位置更新的數(shù)學(xué)模型為

Xi(t+1)=

(8)

式中:Xp和Xworst分別為發(fā)現(xiàn)者最優(yōu)的位置和全局最差的位置;A表示為每個元素隨機賦值為1或-1的一個1×d的矩陣,并且A+=AT(AAT)-1。

偵察預(yù)警麻雀占種群總數(shù)量的10%到20%,位置更新的數(shù)學(xué)模型為

Xi(t+1)=

(9)

式中:fi、fg和fw分別是當(dāng)前麻雀個體的適應(yīng)度值以及全局最佳和最差的適應(yīng)度值;Xbest是當(dāng)前的全局最優(yōu)位置;K為[-1,1]間的隨機數(shù);β稱為步長控制參數(shù);ε是最小的常數(shù)以避免分母出現(xiàn)零。

基本SSA算法偽代碼步驟如算法1所示。

算法1:

輸入 種群大小N,進化次數(shù)t, 最大進化次數(shù)MaxIter,發(fā)現(xiàn)者麻雀數(shù)量PD,偵察預(yù)警麻雀個數(shù)SD,安全閾值ST;

輸出Xbest,fg

1) 在選定搜索范圍中隨機初始化生成N個麻雀個體構(gòu)成初始種群,其中發(fā)現(xiàn)者麻雀個數(shù)為PD,偵察預(yù)警麻雀數(shù)量為SD;

2) 初始化參數(shù);

3) 計算每個麻雀個體的適應(yīng)度值fi,i=1,2,…,N;

4) 排序適應(yīng)度值,記錄當(dāng)前個體的最好位置Xbest和當(dāng)前個體的最差位置Xworst,令t=0;

5) WHILEt

6) FORi=1 TOPD;

7) 根據(jù)式(7)更新第i只麻雀位置;

8) END FOR;

9) FORi=PD+1 TO N;

10) 根據(jù)式(8)更新第i只麻雀位置;

11) END FOR;

12) FORi=1 TOSD;

13) 根據(jù)式(9)更新第i只麻雀位置;

14) END FOR;

15) 計算每個麻雀個體的適應(yīng)度值fi,i=1,2,…,N;

16) 排序適應(yīng)度值,更新整個種群所經(jīng)歷的最優(yōu)位置Xbest和其適應(yīng)度fg,以及最差位置Xworst和其適應(yīng)度fw;

17)t=t+1;

18) END WHILE;

19) 輸出最優(yōu)解Xbest和其適應(yīng)度fg。

本文中Xbest即為平面度誤差定義中通過最小包容區(qū)域法確定的基準(zhǔn)平面方程的系數(shù)a、b。

3.2 平面度誤差評估與麻雀搜索算法

最小包容區(qū)域法求解平面度誤差是對評估基面的最優(yōu)化問題。本文中將其轉(zhuǎn)化成評估基面平面方程參數(shù)a、b的優(yōu)化問題。

通過SSA算法麻雀位置更新公式可知,該算法位置更新方式大致分為向當(dāng)前最優(yōu)位置靠近以及向原點位置靠攏2種。因此該算法對在原點附近時最優(yōu)解求解時,全局探索和局部開發(fā)的能力更強,收斂速度更快。而平面度誤差評定問題中優(yōu)化的系數(shù)a、b變量范圍為[-1, 1]且|a、b|?1,因此SSA算法應(yīng)用于平面度誤差評估問題中效果更好。

3.3 改進的麻雀搜索算法(ISSA)

3.3.1 基于Kent混沌映射的種群初始化

混沌作為普遍存在于非線性系統(tǒng)中的一種演化現(xiàn)象,它通過使用簡單的規(guī)則,產(chǎn)生一個長期的復(fù)雜行為,它有著精致內(nèi)在結(jié)構(gòu),具有遍歷性、隨機性、規(guī)律性的特點[17]。因此,很多學(xué)者將其應(yīng)用于優(yōu)化群搜索問題中,既能夠保持種群的多樣性,又有利于改善全局搜索能力。

為使初始化的種群盡可能地充分利用搜索范圍中的信息,本文將混沌序列中的Kent映射引入改進SSA算法的種群初始化步驟中,假設(shè)Xk為第k代種群,則Kent映射的數(shù)學(xué)模型[18]為

(10)

式中μ為(0,1)間的隨機數(shù)。

當(dāng)μ=0.5時,系統(tǒng)呈現(xiàn)短周期狀態(tài),故本文設(shè)置限制條件μ≠0.5。且在應(yīng)用該映射時初值x0不能與參數(shù)μ相同,否則將演化成周期系統(tǒng),不能形成混沌映射。

圖4是將Kent映射與Logistic映射各迭代2×104次得到的在[0, 1]上的概率分布直方圖。如圖4 所示,作為一種典型的混沌系統(tǒng),Logistic映射生成呈切比雪夫型分布,概率密度函數(shù)邊緣稠密、內(nèi)部稀疏的序列,其在[0, 0.05]和[0.095, 1]兩個區(qū)間取值概率較高。受到Logistic映射遍歷不均勻性的影響,算法整體尋優(yōu)的效率和能力因此有所降低。而Kent映射的概率密度函數(shù)在各區(qū)間分布相對均勻。綜上所述,優(yōu)化算法應(yīng)用Kent映射產(chǎn)生的混沌序列,其遍歷均勻性和收斂速度均優(yōu)于應(yīng)用Logistic映射。

圖4 Kent映射和Logistic映射的概率分布直方圖Fig.4 Probability distribution histogram of Kent map and Logistic map

利用Kent混沌映射產(chǎn)生初始群體的具體步驟如算法2所示。

算法2:

輸入 種群規(guī)模N,維數(shù)d,最大混沌迭代步數(shù)T發(fā)現(xiàn)者麻雀數(shù)量PD,偵察預(yù)警麻雀數(shù)量SD,安全閾值ST;

輸出 初始序列Xk

1) 在搜索空間中隨機初始化序列初值x0;

2) FORi=1 TO T;

3) 根據(jù)式(10)更新迭代產(chǎn)生序列X0;

4) END FOR

5) 將混沌映射變換到優(yōu)化問題的搜索范圍:

Xk=dmin+(dmax-dmin)X0

式中:dmin和dmax分別為X0的第d維變量的最小和最大值。

3.3.2 基于透鏡成像原理的反向?qū)W習(xí)

由式(1)～(3)可知,麻雀個體的更新主要依賴于個體間的跟隨和相互作用, 個體的迭代更新過程缺少變異機制, 一旦陷入局部最優(yōu)停滯, 難以跳出當(dāng)前局部空間。在算法進化搜索后期,種群中所有個體受發(fā)現(xiàn)者麻雀個體影響,均堆積在一個窄小的范圍,導(dǎo)致種群多樣性明顯下降,如果當(dāng)前位置是僅一個局部最優(yōu)解而非全局最優(yōu)解,那么SSA算法容易陷入當(dāng)前位置無法跳出,在處理復(fù)雜優(yōu)化問題時更加嚴(yán)重。針對此類問題,當(dāng)前最常用的改善手段就是引入反向?qū)W習(xí)策略[19],本文使用一種基于透鏡成像原理的反向?qū)W習(xí)策略[20],在當(dāng)前最優(yōu)個體中通過反向?qū)W習(xí)產(chǎn)生新的個體,從而增加種群多樣性。

該策略能夠顯著提升啟發(fā)式群智能優(yōu)化算法性能,相較于一般反向?qū)W習(xí)策略,具有普適性更強、能夠動態(tài)調(diào)節(jié)候選個體、更好地避免算法陷入局部最優(yōu)、顯著提高算法收斂速度、精度以及穩(wěn)定性的特點。

具體過程描述如下:

透鏡成像原理是一種光學(xué)定律,它是指將物體放在除焦點之外的位置,會在凸透鏡另一側(cè)生成倒立的像這一現(xiàn)象。以一維空間為例,高度為h物體在水平軸上的投影為點x(假設(shè)x全局最優(yōu)),透鏡基點O(O為[a′,b′]的中點,焦距為r),經(jīng)透鏡成像能夠生成一個在水平軸上的投影為x*、高度為h′的像,(這里x*為全局最優(yōu)x的反向位置), 如圖5所示。

圖5 透鏡成像示意圖Fig.5 Lens image

當(dāng)前最優(yōu)x通過基點O獲得對應(yīng)的反向點x*,根據(jù)光學(xué)透鏡成像原理可以得出:

(11)

顯然可以令h/h′=k,表示物與像之間的比例關(guān)系,稱k為縮放因子,對于式(11)進行變換即可得到反向點x*的計算公式:

(12)

參數(shù)k可以調(diào)整反向?qū)W習(xí)策略得到的反向個體,從而進一步提高種群多樣性。將式(12)所示的反向?qū)W習(xí)策略推廣到多維即可得:

(13)

3.3.3 算法流程與步驟

改進麻雀搜索算法具體實施步驟如算法3所示。

算法3:

輸入 種群大小N,進化次數(shù)t, 最大進化次數(shù)MaxIter,發(fā)現(xiàn)者麻雀個量PD,偵察預(yù)警麻雀個數(shù)SD,安全閾值ST;

輸出Xbest,fg。

1) 在搜索空間中根據(jù)Kent混沌序列初始化N只麻雀個體構(gòu)成初始種群,其中發(fā)現(xiàn)者麻雀數(shù)量為PD,偵察預(yù)警麻雀數(shù)量為SD;

2) 初始化參數(shù);

3) 計算每個麻雀個體的適應(yīng)度值fi,i=1,2,…,N;

4) 排序適應(yīng)度值,記錄當(dāng)前個體的最好位置Xbest和當(dāng)前個體的最差位置Xworst,令t=0;

5) WHILEt

6) FORi=1 TOPD;

7) 根據(jù)式(7)更新第i只麻雀位置;

8) END FOR

9) FORi=PD+1 TO N;

10) 根據(jù)式(8)更新第i只麻雀位置;

11) END FOR;

12) FORi=1 TOSD;

13) 根據(jù)式(9)更新第i只麻雀位置;

14) END FOR;

15) 計算每個麻雀個體的適應(yīng)度值fi,i=1,2,…,N;

17) FORi=1TOPD;

20) END IF;

21) END FOR;

22) 計算每個麻雀個體的適應(yīng)度值fi,i=1,2,…,N;

23) 排序適應(yīng)度值,更新整個種群所經(jīng)歷的最優(yōu)位置Xbest和其適應(yīng)度fg,以及最差位置Xworst和其適應(yīng)度fw;

24)t=t+1;

25) END WHILE;

26) 輸出最優(yōu)解Xbest和其適應(yīng)度fg。

本文中Xbest即為平面度誤差定義中通過最小包容區(qū)域法確定的基準(zhǔn)平面方程的系數(shù)a、b。

算法流程圖,如圖6所示。

圖6 算法流程圖Fig.6 The flow chart of LSSA

4 實驗結(jié)果及分析

4.1 模型驗證

為了驗證ISSA算法的可行性,分別選取二維Rosenbrock和Schwefel作為測試函數(shù)。

二維Rosenbrock函數(shù)性質(zhì)如下:

(14)

最優(yōu)解為f1(1,1)=0。

Schwefel函數(shù)性質(zhì)如下:

(15)

對以上2個測試函數(shù),分別使用SSA和ISSA進行實驗。設(shè)定算法最大進化次數(shù)為1 000,種群規(guī)模設(shè)置為200。SSA和ISSA部分參數(shù)設(shè)置如下:發(fā)現(xiàn)者個數(shù)占種群整體的20%,意識到危險的麻雀個數(shù)SD占種群整體的占10%,安全閾值ST=0.8,縮放因子k=1×104。為了避免單一運行結(jié)果偏差,在實驗中運行30次來獲得目標(biāo)函數(shù)的最佳值、平均值和標(biāo)準(zhǔn)差。

實驗在2.40 GHz的英特爾i5處理器和8 GB內(nèi)存電腦上的Matlab R2018a中進行,函數(shù)測試結(jié)果如表1所示。

表1 函數(shù)測試結(jié)果比較Tab.1 The test result comparison of benchmark functions

ISSA算法相對于SSA算法具有更好的精度和穩(wěn)定性。從圖7的函數(shù)迭代曲線可以看出,引入Kent混沌映射和透鏡反向?qū)W習(xí)策略后的ISSA算法比SSA算法具有更強的收斂速度和全局尋優(yōu)能力,并且迭代結(jié)果更逼近測試函數(shù)的最優(yōu)解值,穩(wěn)定性也更好。綜上所述ISSA算法相比較傳統(tǒng)SSA算法性能更優(yōu)。

圖7 函數(shù)迭代結(jié)果Fig.7 The iteration result of function

3.3 平面度誤差實例評定

本文選用文獻[21]的測量數(shù)據(jù)(見表2)進行平面度誤差評定。

表2 平面度誤差測量數(shù)據(jù)Tab.2 Measurement data of flatness error mm

ISSA算法控制參數(shù)見表3。其他算法相關(guān)參數(shù)與本文提出算法保持一致[22]。

表3 控制參數(shù)Tab.3 Control parameters

應(yīng)用表2采樣點數(shù)據(jù),分別使用是最小二乘法(LSM),粒子群算法(PSO),遺傳算法(GA),SSA以及ISSA算法進行平面度測量50次并對比分析,評定結(jié)果如表4所示[23]。

表4 不同算法比較結(jié)果Tab.4 Comparison of calculation results for different algorithms

ISSA算法求得最優(yōu)目標(biāo)函數(shù)值的平均值為0.154 867 5 mm,標(biāo)準(zhǔn)差為2.068 9×10-10;SSA算法得到結(jié)果的平均值為0.154 87 mm,標(biāo)準(zhǔn)差為 5.872 69×10-5;兩者的平均計算時間為0.998 7 s和1.085 3 s;ISSA算法優(yōu)化效果明顯更優(yōu),與LSM、PSO、GA和SSA算法相比分別減小了18.032 5 μm、2.332 5 μm、6.132 5 μm、0.002 5 μm。

平面度誤差函數(shù)進化曲線如圖8所示,ISSA算法與SSA算法相比收斂速度更快。在整個迭代過程中,ISSA算法和SSA算法均可搜索的到各自的最優(yōu)平面,其中ISSA算法經(jīng)過45次迭代,用時 0.488 4 s;SSA算法經(jīng)過86次迭代,用時0.858 9 s,ISSA比傳統(tǒng)SSA算法迭代次數(shù)減少了41次,用時減少了0.370 5 s。當(dāng)評定方法獲得更小的誤差評定值時視作方法更好,這是因為該方法獲得了更小的符合平面度誤差定義的最小區(qū)域及其寬度。綜上可知,ISSA算法相比較于SSA算法,在計算精度,穩(wěn)定性和優(yōu)化效率上均有所改善。經(jīng)過驗算,ISSA算法的計算結(jié)果符合交叉準(zhǔn)則。

圖8 平面度誤差函數(shù)進化曲線Fig.8 Evolving curve of flatness error function

5 結(jié) 論

本文提出了一種新型的ISSA平面度誤差評估方法。通過引入Kent映射與透鏡成像學(xué)習(xí)策略,改善平面度誤差最小區(qū)域評估過程中易出現(xiàn)陷入局部最優(yōu)、收斂速度慢和精度低的問題。測試函數(shù)仿真實驗驗證了ISSA算法在理論上與傳統(tǒng)SSA算法相比更具有有效性和優(yōu)越性。平面度誤差實例測量實驗結(jié)果表明:ISSA算法經(jīng)過0.488 4 s找到最優(yōu)平面,比基本SSA算法快0.370 5 s,求得最優(yōu)目標(biāo)函數(shù)值的標(biāo)準(zhǔn)差為2.068 9×10-10;而且ISSA算法的計算結(jié)果比LSM、PSO、GA評定的結(jié)果分別小18.032 5 μm、2.332 5 μm、6.132 5 μm。

ISSA算法與本文所引的其它平面度誤差評估算法相比,所獲得的平面度誤差較小,更符合平面度誤差定義的最小區(qū)域及寬度標(biāo)準(zhǔn)。該方法流程簡單,結(jié)構(gòu)清晰、原理簡明易于編程實現(xiàn),SSA方法為平面度誤差評定提供了一種新的參考方法;對目標(biāo)適應(yīng)度函數(shù)及控制參數(shù)做適當(dāng)修改,可應(yīng)用于多種形位誤差測量儀器。