基于多種群實數編碼遺傳算法的圓度誤差評定

繆立棟， 郭 慧， 張 帆

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

圓度誤差是指回轉體在同一正截面上實際被測輪廓相對其理想圓的變動量。它是衡量圓柱形零件形狀精度的重要指標之一，誤差的大小將嚴重影響其工作性能。在GB7234—87（圓度測量術語、定義及參數）中，圓度誤差的評定方法有：最小區域圓法、最小二乘圓法、最小外接圓法和最大內接圓法。用最小區域圓評定準則所評定的圓度誤差值為最小，且具有唯一性。我國標準規定圓度誤差必須按最小區域圓評定準則進行評定[1]。

按最小區域法評定圓度誤差，關鍵是如何找到相夾被測輪廓且半徑差最小的兩同心圓。這種評定方法實際是最優化問題，采用遺傳算法進行計算可以準確快速的找到最優解。遺傳算法作為一種全局收斂算法，較之優化迭代算法如單純形法，Gauss-Newton 法、levenberg-Marquart 法，已證明能夠較為準確，有效搜索到全局最優解。但是，仍存在而收斂速度慢、效率不高、局部收斂及精度不高等問題。

本文在實數編碼(RGA)的遺傳算法的基礎上，運用遺傳算法自有的并行性，對算法進行了改進，引入多種群遺傳算法，通過實驗對比，證明多種群實數編碼遺傳算法(RMGA)有效的提高了全局搜索能力和局部搜索速度，收斂更快，精度更高。

1 多種群遺傳算法(RMGA)

1.1 遺傳算法(RGA)的不足

遺傳算法是一種借鑒生物界自然選擇機制和自然遺傳機制的隨機化搜索算法，該算法中種群規模的大小、交叉率、變異率的選取，各染色體適應度函數值的相對大小，以及收斂條件的設定等，對優化結果以及收斂速度都有一定影響。

但常用的簡單遺傳算法(RGA)往往存在著不易成熟收斂[2]的現象，主要表現在群體中的所有個體都趨于同一狀態而停止進化，算法最終不能給出令人滿意的解。未成熟收斂的發生主要和下列幾個方面有關：

（1） 在選擇操作過程中。當群體中存在適應度比其他個體高得多的個體時，該個體將會多次被選中，下一代群體很快被該個體所控制，群體失去競爭性，使問題過早地收斂于局部解。

（2） 交叉和變異操作中。交叉概率Pτ、變異概率Pm取值不當極容易收斂于局部解。且不同的問題所對應的最佳Pτ、Pm取值往往不同，每個問題都要通過不斷的反復試驗才可確定，效率低下。

（3） 當群體規模較小時，群體中多樣性程度低，個體間競爭較弱。群體易趨于單一化，交叉操作的作用漸趨消失，群體的更新僅靠變異操作來維持，群體將很快收斂于局部最優解；當群體規模較大時，勢必造成計算量的增加，計算效率受到影響。

（4） 如果規定的最大遺傳代數過少，進化不充分，也會造成未成熟收斂。

1.2 改進的多種群遺傳算法(RMGA)

針對簡單遺傳算法所存在的上述問題，為克服未成熟收斂，本文應用了一種算法性能更好的遺傳算法模型——多種群遺傳算法結構模型[3]（簡稱RMGA），可以用來取代常規的標準計算模型。RMGA 在RGA 的基礎上主要引入了以下幾個概念：

（1） 突破RGA 僅靠單個群體進行遺傳進化的框架，引入多個種群同時進行優化搜索；

（2） 各個種群之間通過遷移因子進行聯系，實現多種群的協同進化；最優解的獲取是多個種群協同進化的綜合結果；

（3） 在進化收斂后，在全部種群的所有個體之間選擇適應度函數最大的個體作為最優解。多種群遺傳算法的結構（以3個種群為例）如圖1所示。

圖 1 多種群算法結構示意圖

因為有3個種群同時對解空間進行協同搜索，群體的多樣性由3個種群協同維持，故各種群的群體規模可以減小。多種群中的精華種群和其他種群有很大不同。在進化的每一代，將各個種群的最優個體放入精華種群加以保存。精華種群不進行選擇、交叉、變異等遺傳操作，保證進化過程中各種群產生的最優個體不被破壞和丟失。同時，判斷算法終止條件在精華種群中產生，收斂判據是精華種群中最優個體適應值連續保持不變的最大代數和最大遺傳代數相結合，這樣比RGA 收斂判據更合理。

1.3 多種群遺傳算法的具體步驟[4-5]

（1） 根據圓度誤差測試數據給出圓心坐標，即染色體(x, y)的解域范圍，可以根據經驗或者通過傳統算法給出；

（2） 確定子種群數量及子種群的初始群體數量Ni，交叉概率Pτ以及變異概率Pm、子種群遷移率、最大進化代數；

（3） 計算每一個體的適應度函數，適應度函數采用如下線性函數

式中 Ni為種群的大小，P 根據目標函數式(5)的大小所確定的個體在種群中的位置；sp 為選擇壓力，1≤sp≤2；所以一般取sp=1.7；

（4） 每個子群分別獨立采用遺傳算法進行復制、交叉、變異操作，子種群每進化若干代就進行子群間的遷移；

（5） 選擇操作：將種群中的個體按適應度由大到小排序，然后根據單個個體所對應的適應度確定其繁殖后在交配池中所占比例

（6） 交叉操作：操作是遺傳算法中最主要的操作，這里采用算術交叉方式產生后代，按照線性組合，產生新的個體，公式為

其中 Xi、Xi+1分別為父代的第i 個和第i+1個變 量，iX′，1i+X′ 分別為新產生的子代的第i 個和第 i +1個變量，r {0,∈ 1}為均勻分布的隨機變量。

（7） 變異操作：隨機的選取一個個體，并隨機的使其中1個參數在其取值范圍內隨機的增加或者減少5%；

（8） 種群是否達到最大進化代數，如果未達到就轉向步驟(4)。否則此時選出全體種群中適應度最大的個體所對應的目標函數值，即為全局最優解。

算法程序框圖如圖2所示。

圖 2 多種群遺傳算法程序框圖

2 圓度誤差評定的數學模型

圓度誤差是指被測實際圓對其理想圓的變動量，理想圓的選擇應使變動量為最小。其表示方法是用兩同心幾何圓將實際圓包容在中間，當兩幾何圓的間隙為最小時，該兩幾何圓半徑之差即實際圓的圓度誤差[1]，如圖3所示。圓度的誤差帶的大小和位置是一個待定的浮動區域。

圖 3 圓度誤差

圓度誤差值的評定按其定義應為最小區域圓法(MZC)，近似的評定方法有最小二乘圓法(LSC)，另外有最大內切圓(MIC)方法，最小外接圓(MCC)方法。不同的方法，對應不同中心的理想圓。

圓度誤差是衡量圓形零件形狀精度的重要指標之一，按最小區域法來計算圓度誤差是一個非線性優化問題，已有的方法受到計算精度的限制。

為了提高算法精度和收斂速度，快速準確評定圓度誤差，本文運用RMGA方法通過多個子種群計算并遷移優良個體的進化過程來實現對理想圓圓心以及圓度誤差的快速搜索。

設實際圓周上測量點的坐標值為 mi( xi,yi) (i=1, 2,…, n)，n為測點數，理想圓的圓心位置為m ( x, y )，則測量點到理想圓圓心的距離為

按最小區域法評定圓度誤差，實質上是尋找包容被測實際圓且具有半徑差為最小的兩理想同心圓，包容被測輪廓的同心圓有無數對，但只有一對半徑差是最小的，這對同心圓的圓心即為所求。

根據最小區域要求，圓度誤差為

式(5)即為用RMGA方法求解滿足最小區域 要求圓度誤差的目標函數，優化變量為使 ( )

f x,y最小的x 和y，圓度誤差的評定轉化為求二元函數 f ( x,y )的最小值問題。

3 計算實例

以文獻[6]中圓度的測量數據為例（見表1）進行誤差計算分別采用實數編碼遺傳算法(RGA)和實數編碼多種群(RMGA)方法計算圓度誤差，RMGA方法計算圓度誤差時參數設置為：種群范圍[0，0.1]，子種群數為4，每個種群的個體數目20，采用離散重組，變異率0.2，最大進化次數60，遷移率0.2，在5代之間發生遷移，代溝0.8。RGA方法的參數設置為：種群范圍[0，0.1]，個體數目80，采用離散重組，變異率0.2，最大進化次數60，遷移率0.2，代溝0.8。

RMGA方法進化過程如圖4所示，計算結果列于表2中，并將文獻[6]最小區域法的求解結果一并列入表中以便比較。同時，應用RGA方法對表1的數據進行計算，計算結果列入表2中，迭代曲線如圖5所示。

圖 4 圓度誤差的RMGA迭代曲線

表1 圓度誤差計算的數據測量[6]

圖 5 圓度誤差的RGA迭代曲線

表 2 圓度誤差計算結果的比較

比較表2的結果可知，RMGA 方法的結果優于文獻[6]的最小區域法結果和RGA 方法的結果。從圖4可知RMGA 進化計算很快獲得最優解，RMGA 方法在30多代以后就已經基本收斂，RGA方法在40多代以后還在波動，說明RMGA 方法比RGA 方法有更快的收斂速度，用于計算圓度誤差是很有效的。

4 結 論

本文針對遺傳算法所存在的早熟收斂、精度不高、計算效率低等缺點。分析了原因，并借助遺傳算法的并行性，引入多個種群對算法過程進行改進。通過實例計算，對實數編碼遺傳算法和多種群遺傳算法進行試驗比較。實驗表明改進后的多種群遺傳算法能有效克服原算法缺點，有效地收斂到全局最優解，提高了收斂速度和精度，該算法同時也能夠給其他形位誤差的評定提供參考。

[1] 甘立永. 形狀和位置誤差檢測[M]. 北京： 國防工業出版社, 1995. 73-94.

[2] Sbrizzai R, Torelli F. A pipelined—in—time parallel algorithm for transient stability analysis [J]. IEEE Transactions on Power Systems, 1991, 6(2)： 715-722.

[3] Potts J C, Giddens T D, Yadav S B. The development and evaluation of an improved genetic algorithms based on migration and artificial selection [J]. IEEE Trans on SMC. 1994, 24(1)： 73-86.

[4] 鄒 琳, 夏巨諶, 胡國安. 基于實數編碼的多種群并行遺傳算法研究[J]. 小型微型計算機系統, 2004, 25(6)： 982-986.

[5] 劉 勇, 康立山, 等. 非數值并行算法(第2冊)[M].北京： 科學出版社, 1995. 108-120.

[6] Huang J. A new strategy for circularity problems [J]. Precision Engineering, 2001, 25： 301-308.