加權(quán)微粒群算法在模型配準(zhǔn)中的應(yīng)用

劉 晶， 林大鈞

（華東理工大學(xué)機(jī)械與動力工程學(xué)院，上海 200237）

微粒群算法[1]是在1995年由美國社會心理學(xué)家James Kennedy和電氣工程師Russell Eberhart共同提出的，其基本思想是受他們早期對鳥類群體行為研究結(jié)果的啟發(fā)，并利用了生物學(xué)家Frank Heppner的生物群體模型[2]。目前微粒群算法應(yīng)用范圍較廣，已經(jīng)在函數(shù)優(yōu)化，多目標(biāo)優(yōu)化，人工神經(jīng)網(wǎng)絡(luò)，模式識別等領(lǐng)域得到應(yīng)用[3]。基本微粒群算法由于收斂性能還有待優(yōu)化，本文利用加權(quán)函數(shù)以及分群搜索來對基本微粒群算法進(jìn)行改進(jìn)。

1 基本微粒群算法

很多進(jìn)化算法對于個體使用進(jìn)化算子，基本微粒群算法與這些進(jìn)化算法的不同之處在于，它是將每個個體看作是在n維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進(jìn)行動態(tài)調(diào)整[2]。設(shè)第i個微粒的當(dāng)前位置表示為xi=(xi1, xi2, …, xin)，微粒i的當(dāng)前飛行速度表示為vi=(vi1, vi2, …, vin)，微粒i經(jīng)歷過的最好位置表示為pi=(pi1, pi2, …, pin)，設(shè)群體中微粒個數(shù)為m，所有微粒經(jīng)歷的最好位置用pg來表示。則微粒群算法的進(jìn)化方程如下

其中 參數(shù)t表示第t代，c1, c2為加速常數(shù)，c1用于調(diào)節(jié)微粒飛向自身最好位置方向的步長，c2用于調(diào)節(jié)微粒向全局最好位置飛行的步長。r1, r2為位于0與1之間的隨機(jī)函數(shù)。vi通常介于[-vmax, vmax]之間。公式（1）中第一部分是微粒上一代的速度，第二部分是認(rèn)知部分，表示微粒自身的思考，第三部分是社會部分，表示微粒間的社會信息共享。第一部分用于保證算法的全局收斂性，第二部分和第三部分保證算法具有局部收斂能力[2]。 基本微粒群算法的進(jìn)化過程中，只有當(dāng)微粒的當(dāng)前位置處的適應(yīng)值好于所經(jīng)歷的最好位置處的適應(yīng)值時，就用微粒的當(dāng)前位置替換微粒所經(jīng)歷的最好位置。迭代中止條件可以通過最大迭代數(shù)或者最小適應(yīng)閾值來控制。但是，基本微粒群算法的收斂性還有待完善，因此需要引入權(quán)函數(shù)。

2 加權(quán)微粒群算法

為了改善基本微粒群算法的收斂性能，加權(quán)微粒群算法在速度進(jìn)化過程中引入權(quán)函數(shù)，同時在迭代一定次數(shù)后進(jìn)行分群優(yōu)化。

因此引入權(quán)函數(shù)后公式（1）改進(jìn)如下

文獻(xiàn)[4]建議w 的取值范圍為[0,1.4]，但實驗結(jié)果表明當(dāng)w 取[0.8,1.2]時，算法收斂速度更快，而當(dāng)w＞1.2 時，算法則較多地陷入局部極值[2]。因此，本文建立的權(quán)函數(shù)使之范圍在[0.8,1.2]這個范圍。由于較大的w 具有較好的全局收斂能力，而較小的w 具有較好的局部收斂能力。因此，在迭代初期應(yīng)使得w 大些，在迭代后期應(yīng)使得w小些。從而使得微粒群算法在迭代初期具有較好的全局收斂能力，而在迭代后期具有較好的局部收斂能力。因此，建立權(quán)函數(shù)公式如下

其中 fs表示最小適應(yīng)閾值，ft表示第t代最好位置處的適應(yīng)值。

當(dāng)微粒群迭代了一定次數(shù)時，就可以進(jìn)行分群，將微粒群分為兩個子群。分群的目的是提高多樣性和擴(kuò)大搜索范圍，避免找到局部最優(yōu)。分群的原則是：根據(jù)各個微粒的最優(yōu)適應(yīng)值，將其按從小到大排序，然后把位于奇數(shù)位置的微粒放到一個群，把位于偶數(shù)位置的微粒放到一個群。分群后每個微粒所經(jīng)歷過的最好位置作為它在分群中的初始位置，以便后續(xù)過程能快速找到最優(yōu)解。

本文采用的加權(quán)微粒群算法的基本流程如下：

Step 1 隨機(jī)初始化微粒的速度和位置。

Step 2 計算每個微粒的適應(yīng)值，微粒i經(jīng)歷過的最好位置表示為pi, pg設(shè)置為全局所經(jīng)歷的最好位置。

Step 3 對于每個微粒，將其適應(yīng)值與所經(jīng)歷過的最好位置pi的適應(yīng)值進(jìn)行比較，若好于所經(jīng)歷過的最好位置pi處的適應(yīng)值，則將其作為當(dāng)前的最好位置。

Step 4 對每個微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置pg的適應(yīng)值進(jìn)行比較，若好于全局最好位置pg處的適應(yīng)值，則將其作為當(dāng)前的全局最好位置。

Step 5 根據(jù)公式(3)和公式(2)對微粒的速度和位置進(jìn)行進(jìn)化，再執(zhí)行Step 3和Step 4。

Step 6 當(dāng)?shù)欢ù螖?shù)時，進(jìn)行分群，將目前的這群微粒分為兩個分群，由于已經(jīng)進(jìn)行一定次數(shù)的迭代，因此每個微粒所經(jīng)歷過的最好位置作為它在分群中的初始位置，從而保證分群中的初始位置都是比較好的位置。

Step 7 將兩個分群分別按照Step 5進(jìn)行優(yōu)化，如適應(yīng)值小于設(shè)定好的適應(yīng)閾值則結(jié)束，從而分別得到各自的最優(yōu)值，將兩個分群的最優(yōu)值進(jìn)行比較，其中較好的值作為最終的最優(yōu)值。

3 實例分析

本文利用上文提到的加權(quán)微粒群算法對三坐標(biāo)機(jī)測量的葉片散亂點云到其三維CAD 模型的配準(zhǔn)問題進(jìn)行研究。散亂點云與三維CAD 模型的配準(zhǔn)其實質(zhì)就是使散亂點云到三維CAD 模型的距離平方和最小。因此，加權(quán)微粒群算法中每個微粒的適應(yīng)值就是該微粒條件下散亂點云到三維CAD 模型的最小距離平方和。適應(yīng)值公式如下

其中 Ai(i=1, 2, …, L)表示散亂點云中的數(shù)據(jù)點，Bi為Ai在CAD 模型上的投影點，R 為旋轉(zhuǎn)矩陣，T 為平移矩陣，L 為散亂點云的數(shù)目。R可以表達(dá)成下式

其中 3 個參數(shù)α, β, γ 分別表示圍繞X，Y，Z三個坐標(biāo)軸的旋轉(zhuǎn)角度。

T 可以表達(dá)成下式

其中 3個參數(shù)Tx, Ty, Tz分別表示沿X，Y，Z方向的位移量。

因此，從公式（5）中可以看出適應(yīng)值是一個包含了6個參數(shù)的函數(shù)。從而可以確定加權(quán)微粒群算法的搜索空間為6維，以α, β, γ，Tx, Ty, Tz這6個參數(shù)可以確定出微粒的位置。只要按照第三部分?jǐn)⑹龅募訖?quán)微粒群算法的基本流程，當(dāng)適應(yīng)值小于設(shè)定好的適應(yīng)閾值時，就可以確定出全局最好位置，也就是確定出R 和T 最佳變換的6個參數(shù)，從而實現(xiàn)配準(zhǔn)。

取群體微粒數(shù)為20, w按公式(4)獲得，c1= c2= 2 , vmax= 4。散亂點云數(shù)目為224，設(shè)定適應(yīng)閾值為0.1,分別利用基本微粒群算法和加權(quán)微粒群算法對散亂點云與三維CAD模型的配準(zhǔn)問題進(jìn)行研究，結(jié)果如表1所示。如果想提高配準(zhǔn)精度，可以修改中止條件，使適應(yīng)閾值更小。

表 1 運(yùn)算結(jié)果

普通微粒群算法以及加權(quán)微粒群算法的適應(yīng)值迭代過程以及配準(zhǔn)后平均誤差的迭代過程如圖1 和圖2 所示。

圖1 適應(yīng)值迭代圖

圖2 平均誤差迭代圖

4 結(jié) 論

本文把加權(quán)微粒群算法運(yùn)用到散亂點云與CAD 模型間的配準(zhǔn)。根據(jù)算法收斂較快的權(quán)值范圍，建立加權(quán)函數(shù)并將其引入速度進(jìn)化過程中，同時在進(jìn)化過程中分群優(yōu)化，從而維護(hù)全局和局部搜索能力的平衡。進(jìn)而更好地實現(xiàn)了散亂點云與三維CAD 模型之間的配準(zhǔn)。

[1] Kennedy J, Eberhart R C. Particle swarm optimization [C]// Proc. of IEEE Int. Conf. on Neural Networks. Perth, WA, Australia, 1995： 1942-1948.

[2] 曾建潮. 微粒群算法[M]. 北京： 科學(xué)出版社, 2004. 7.

[3] 謝曉鋒, 張文俊, 楊之廉. 微粒群算法綜述[J]. 控制與決策, 2003, 18(2)： 129-134.

[4] Shi Y, Eberhart R C. Parameter selection in particle swarm optimization [C]//Evolutionary Programming VII： Proc. EP98. New York： Springer-Verlag, 1998： 591-600.