加權微粒群算法在模型配準中的應用

劉 晶， 林大鈞

（華東理工大學機械與動力工程學院，上海 200237）

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

1 基本微粒群算法

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

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

2 加權微粒群算法

為了改善基本微粒群算法的收斂性能，加權微粒群算法在速度進化過程中引入權函數，同時在迭代一定次數后進行分群優化。

因此引入權函數后公式（1）改進如下

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

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

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

本文采用的加權微粒群算法的基本流程如下：

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

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

Step 3 對于每個微粒，將其適應值與所經歷過的最好位置pi的適應值進行比較，若好于所經歷過的最好位置pi處的適應值，則將其作為當前的最好位置。

Step 4 對每個微粒，將其適應值與全局所經歷的最好位置pg的適應值進行比較，若好于全局最好位置pg處的適應值，則將其作為當前的全局最好位置。

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

Step 6 當迭代一定次數時，進行分群，將目前的這群微粒分為兩個分群，由于已經進行一定次數的迭代，因此每個微粒所經歷過的最好位置作為它在分群中的初始位置，從而保證分群中的初始位置都是比較好的位置。

Step 7 將兩個分群分別按照Step 5進行優化，如適應值小于設定好的適應閾值則結束，從而分別得到各自的最優值，將兩個分群的最優值進行比較，其中較好的值作為最終的最優值。

3 實例分析

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

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

其中 3 個參數α, β, γ 分別表示圍繞X，Y，Z三個坐標軸的旋轉角度。

T 可以表達成下式

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

因此，從公式（5）中可以看出適應值是一個包含了6個參數的函數。從而可以確定加權微粒群算法的搜索空間為6維，以α, β, γ，Tx, Ty, Tz這6個參數可以確定出微粒的位置。只要按照第三部分敘述的加權微粒群算法的基本流程，當適應值小于設定好的適應閾值時，就可以確定出全局最好位置，也就是確定出R 和T 最佳變換的6個參數，從而實現配準。

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

表 1 運算結果

普通微粒群算法以及加權微粒群算法的適應值迭代過程以及配準后平均誤差的迭代過程如圖1 和圖2 所示。

圖1 適應值迭代圖

圖2 平均誤差迭代圖

4 結 論

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

[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]. 北京： 科學出版社, 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.