改進(jìn)的蜂群算法評定空間直線度誤差

辛帥，李研

（重慶大學(xué) 光電技術(shù)及系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，重慶 400030）

直線是構(gòu)成實(shí)體零件的最基本的幾何元素，常作為設(shè)計(jì)、加工、裝配和檢測的基準(zhǔn)，直線度誤差的大小對產(chǎn)品的質(zhì)量及其使用壽命至關(guān)重要，因而高效準(zhǔn)確地對直線度誤差進(jìn)行評定，具有重要的工程意義。

根據(jù)零件的功能要求，直線度誤差的評定可分為在給定平面內(nèi)、在給定方向上和空間任意方向上3種情況。評定直線度誤差的方法有最小區(qū)域包容法、最小二乘中線法和兩端點(diǎn)連線法。其中，最小區(qū)域包容法是一種與公差帶概念完全吻合的評定方法，可以得到理想誤差值。在給定平面和方向上的直線度評定較簡單且已非常成熟，本文基于最小區(qū)域包容法來討論空間直線度誤差的評定。

目前，許多學(xué)者致力于空間直線度誤差的研究。Huang[1]提出了用最小平行六面體包絡(luò)的方法計(jì)算空間直線度誤差，但只能提供誤差計(jì)算的近似值。Zhang[2-3]建立了基于最小區(qū)域條件的數(shù)學(xué)模型，根據(jù)偏微分理論的求解來判斷誤差評定是否達(dá)到最小條件，并用幾何判別方法對最后的誤差評定結(jié)果進(jìn)行驗(yàn)證。廖平[4]和CUI[5]分別提出了基于遺傳算法（Genetic Algorithms，GA）的空間直線度誤差評定方法；茅健[6]則提出使用粒子群算法（Particle Swarm Optimization，PSO）對空間直線度進(jìn)行評定，相比于遺傳算法在一定程度上提高了計(jì)算精度。這兩種智能進(jìn)化算法雖然能夠解決傳統(tǒng)算法存在的不足[7]，但是依然存在設(shè)置參數(shù)較多，魯棒性欠佳的問題。

筆者提出將蜂群算法引入空間直線度評定，采用混沌序列初始化改進(jìn)蜂群算法，進(jìn)一步提高其收斂速度與魯棒性。該算法相對于經(jīng)典的智能優(yōu)化算法，在評定空間直線度誤差問題上具有一定的優(yōu)勢。

1 基本人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）由土耳其人Karaboga在2005年提出[8]，是受啟于蜜蜂采蜜過程用于搜尋最優(yōu)解的群智能優(yōu)化算法，以其在很多研究領(lǐng)域表現(xiàn)出來的比其他算法更佳的優(yōu)化性能而成為目前學(xué)術(shù)界的研究熱點(diǎn)。

ABC算法模擬蜂群采蜜的過程，通過不同角色蜜蜂間的交流、轉(zhuǎn)換和協(xié)作來實(shí)現(xiàn)群體智能。被優(yōu)化問題的備選解被稱為食物源，蜜蜂采蜜的過程就是搜尋最優(yōu)解的過程，食物源的價(jià)值通過收益度值衡量，即優(yōu)化問題的適應(yīng)度值。適應(yīng)度函數(shù)是算法的判決依據(jù)，直接決定優(yōu)化的方向，算法的目標(biāo)就是求解適應(yīng)度函數(shù)的最優(yōu)解。在ABC算法中，將人工蜂群分為 3 種：雇傭蜂（employer）、觀察蜂（onlooker）和偵查蜂（scout）。規(guī)定雇傭蜂與觀察蜂的數(shù)量相等，均為蜂群數(shù)量的一半，一個(gè)雇傭蜂對應(yīng)一個(gè)確定的蜜源（source）。單次迭代的過程如下：雇傭蜂隨機(jī)尋找蜜源，并在該蜜源鄰域內(nèi)尋找新的蜜源，雇傭蜂通過舞蹈、氣味等將蜜源信息反饋給等待區(qū)的觀察蜂，觀察蜂則按照蜜源收益度概率通過輪盤賭方式選擇蜜源，并在其鄰域內(nèi)搜索收益度更高的蜜源。如果在迭代過程中某雇傭蜂在設(shè)定的搜索次數(shù)limit內(nèi)沒有找到更好的蜜源，便放棄這個(gè)蜜源，同時(shí)雇傭蜂成為偵查蜂，偵查蜂隨機(jī)尋找新的蜜源。算法中，蜜源的位置對應(yīng)函數(shù)優(yōu)化問題的一個(gè)可行解，蜜源的收益度（蜜量）對應(yīng)函數(shù)問題的適應(yīng)度（函數(shù)值），尋找并采集蜜源的速度代表解決問題的速度。

假設(shè)種群規(guī)模 S，有 SN 個(gè)蜜源，每個(gè)解 xi（i=1，2，...SN）是一個(gè)D維向量，即搜索空間為D維，蜜蜂對所有蜜源進(jìn)行搜索，總的循環(huán)搜索次數(shù)為MCN（Maximum Number of Cycles）。蜜蜂找到蜜源后根據(jù)公式（1）計(jì)算蜜源的收益度，式（2）為蜜源的鄰域搜索公式。

式中 k∈{1，2，...SN}，j∈{1，2，...D}，k≠i，xij表示更新前的蜜源，xkj為鄰域內(nèi)蜜源，φij為[-1，1]的隨機(jī)數(shù)，控制 xij鄰域的生成范圍。

基本蜂群算法中，觀察蜂根據(jù)雇傭蜂的蜜源收益度信息，用輪盤賭方法選擇蜜源。選擇概率如式（3）所示。迭代中由于蜜源經(jīng)過限定的limit次搜索后仍然沒有得到改善的蜜蜂變?yōu)閭刹榉?，根?jù)式（4）重新選擇蜜源。

2 改進(jìn)的蜂群算法評定空間直線度

2.1 空間直線度誤差的最小區(qū)域評定模型

空間直線度的定義為 “包容被測輪廓且直徑最小的圓柱的直徑”。根據(jù)形狀誤差的定義，應(yīng)該按最小條件評定空間直線度誤差值，其大小可以用最小區(qū)域的直徑來表示。空間直線通常有3種表達(dá)方式：一般方程、點(diǎn)向式和參數(shù)式，這里采用點(diǎn)向式表示以將評定參數(shù)減少為4個(gè)。假定測量點(diǎn)坐標(biāo)集為{xi，yi，zi}，i=1，2，...，n，假定按最小包容區(qū)域確定的基準(zhǔn)直線方程為：

則測量點(diǎn)到空間直線的距離為：

根據(jù)最小包容區(qū)域條件，MABC算法評定空間直線度的目標(biāo)函數(shù)可定義為：

由公式（7）可知，優(yōu)化參數(shù)個(gè)數(shù)為4，待求的優(yōu)化變量為a，b，l，m。

2.2 改進(jìn)的蜂群算法

由于評定直線度誤差時(shí)，數(shù)據(jù)點(diǎn)越多，最后得到的評定結(jié)果就越精確，而大量的數(shù)據(jù)加大了算法的計(jì)算難度，因此采用混沌序列初始化蜂群[9]，混沌是自然界廣泛存在的一種非線性現(xiàn)象，具有隨機(jī)性、遍歷性、初始條件敏感性等特點(diǎn)，已被廣泛應(yīng)用于隨機(jī)優(yōu)化，在局部尋優(yōu)領(lǐng)域具有優(yōu)越的性能。改進(jìn)的ABC算法利用混沌序列的遍歷性可使產(chǎn)生的種群初始解隨機(jī)性均勻分布于整個(gè)解空間，從而提高收斂速度和算法魯棒性。

改進(jìn)的ABC算法評定直線度誤差的步驟如下：

步驟1 混沌初始化蜂群。設(shè)初始化規(guī)模為S，其中50%為雇傭蜂，50%為觀察蜂。

首先利用Logistic映射產(chǎn)生混沌序列：

式中 i∈[1，N]，i∈[1，D]。 μ 是系統(tǒng)混沌狀態(tài)的控制參數(shù)，本文中 μ=4，此時(shí)系統(tǒng)處于完全混沌狀態(tài)。 L（i），j表示 Li的第 j維變量。 向量 L1=[l1，1，l1，2，…，l1，D]包含有 D 個(gè)微小差異的初值，將其代入（3）式迭代N-1次即可得到N×D維的混沌序列。

然后運(yùn)用（10）式執(zhí)行載波操作，將混沌序列映射到整個(gè)解空間。

其中，xi，j表示第 i個(gè)初始解的第 j維的坐標(biāo)，xmin和 xman表示每一維的最小和最大取值。

步驟2 計(jì)算個(gè)體收益度。對雇傭蜂進(jìn)行鄰域搜索，并根據(jù)貪婪機(jī)制選擇收益度較高的解來更新蜜源。計(jì)算雇傭蜂蜜源收益度，并記錄下最優(yōu)蜜源位置Best。

步驟3 雇傭蜂招募觀察鋒。觀察蜂根據(jù)雇傭蜂的蜜源收益度信息，用輪盤賭方法選擇蜜源，即收益度較大的蜜源有較大的概率招募到更多的觀察蜂，選擇概率由公式（3）獲得。觀察蜂在選擇的蜜源附近搜尋新的可行解，并保留收益度較好的解，放棄收益度較低的解。

步驟4 放棄停止更新且收益度較低的蜜源。假如某一蜜源經(jīng)過限定的limit次搜索后仍然沒有得到改善，強(qiáng)制放棄該蜜源，該處的雇傭蜂轉(zhuǎn)變?yōu)閭刹榉?。偵查蜂在設(shè)定范圍內(nèi)隨機(jī)選擇新的蜜源。

步驟5 判斷是否滿足終止條件或達(dá)到最大迭代次數(shù)，若是則得到球度誤差的最優(yōu)解，若否則跳至步驟2。

3 實(shí)驗(yàn)測試

實(shí)驗(yàn)選用文獻(xiàn)[4]和文獻(xiàn)[6]中的原始數(shù)據(jù)，以方便對比本文算法和GA、PSO評定直線度誤差的效果。原始數(shù)據(jù)如表1所示。

表1 測量的原始數(shù)據(jù)Tab.1 Original data of measurement

根據(jù)原始數(shù)據(jù)，對本文算法進(jìn)行參數(shù)設(shè)置，由于空間直線度的優(yōu)化參數(shù)為a，b，l，m，所以將候選解維數(shù)D設(shè)置為4；limit在ABC算法中起著至關(guān)重要的作用，通常設(shè)置將其設(shè)置為迭代次數(shù)的 15%～20%，這里迭代次數(shù)為 300，limit為50，其余參數(shù)的具體設(shè)置如表2所示。

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

文獻(xiàn)[4]分別用遺傳算法和首末兩端點(diǎn)法對該直線度的誤差進(jìn)行了評定，采用首末兩端點(diǎn)法計(jì)算空間的直線度誤差為0.034 mm，采用遺傳算法的計(jì)算結(jié)果為0.026 mm。文獻(xiàn)[6]采用粒子群算法對該直線度進(jìn)行了評定，計(jì)算結(jié)果為0.024 932 mm。

應(yīng)用本文算法評定空間直線度耗時(shí)10.069 s，運(yùn)行50次求平均值得到空間直線的參數(shù)為：a=-49.412 4，b=-24.211 5，l=2.970 56，m=1.960 77。所得到的空間直線度的平均誤差為：0.00 902 366 mm，最大誤差為0.01 012 586 mm，最小值為0.00 895 716 mm。圖1是改進(jìn)的ABC算法的迭代曲線。實(shí)際計(jì)算結(jié)果表明，本文算法評定空間直線度誤差的精度比GA算法、兩端點(diǎn)法和PSO算法高，而且計(jì)算速度較快，魯棒性較好。經(jīng)驗(yàn)證算法符合最小區(qū)域法的評定標(biāo)準(zhǔn)。

圖1 ABC算法的迭代曲線Fig.1 Iterative curve of ABC algorithm

4 結(jié) 論

提出了基于混沌序列初始化的蜂群算法，并將其應(yīng)用于空間直線度誤差評定。對最小包容區(qū)域空間直線度誤差的實(shí)例測試表明，相對于GA和PSO算法，本文算法的精確度高、魯棒性強(qiáng)，非常適用于空間直線度誤差的精確評定。同時(shí)，該算法也可應(yīng)用于其他形狀誤差的評定和非線性優(yōu)化問題，具有很強(qiáng)的應(yīng)用價(jià)值。

[1]HUANGST，F(xiàn)ANKC.WUJH.Anewminimumzone method for evaluating straightness errors[J].Precision Engineering， 1993，15（3）：158-165.

[2]ZHANG Qing， FAN Guang-zhao， LI Zhu.Evaluation method for spatial straightness errors based on minimum zone condition[J].Precision Engineering， 1999（23）：264-272.

[3]張青，范光照，徐振高，等.按最小條件評定空間直線度誤差的理論研究[J].計(jì)量學(xué)報(bào)，1998，19（4）：246-253.ZHANG Qing， FAN Guang-zhao， XU Zhen-gao， et al.Theory research for spatial straightness error evaluation based on minimum zone condition[J].Acta Metrologica Sinica，1998， 19（4）：246-253.

[4]廖平，喻壽益.基于遺傳算法的空間直線度誤差的求解[J].中南工業(yè)大學(xué)學(xué)報(bào)，1998，29（6）：586-588.LIAO Ping，YU Shou-yi.A method of calculating 3-D line error using genetic algorithms[J].J Cent South Univ Technol，1998， 29（ 6） ：586-588.

[5]CUI Chang-cai， CHE Ren-sheng， HUANG Qing-cheng.Genetic algorithm-based evaluation of spatial straightness error[J].Journal of Harbin Institute of Technology， 2003， 10（4）：418-421.

[6]茅健，曹衍龍.基于粒子群算法的空間直線度誤差評定[J].工程設(shè)計(jì)學(xué)報(bào)， 2006， 13（5）：291-294.MAO Jian，CAO Yan-long.Evaluation method for spatial straightness errors based on particle swarm optimization[J].Journal of Engineering Design， 2006， 13（5）：291-294.

[7]劉永超，陳明.形位公差的進(jìn)化算法 [J].計(jì)量學(xué)報(bào)，2001，22（ 1） ：18-22.LIU Yong-chao，CHEN Ming.A new evaluation met ho d for form and position errors[J].Acta Metrologica Sinica， 2001，22（1）：18-22.

[8]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06， Erciyes University，2005.

[9]孟紅記，鄭鵬，梅國暉，等.基于混沌序列的粒子群算法[J]，控制與決策，2006，21（3）：263-266.MENG Hong-ji， ZHENG Peng， MEI Guo-hui， et al.Particle swarm optimization algorithm based on chaotic series[J]，Control and Decision， 2006，21（3）：263-266.