基于多種群實(shí)數(shù)編碼遺傳算法的圓度誤差評(píng)定

繆立棟， 郭 慧， 張 帆

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

圓度誤差是指回轉(zhuǎn)體在同一正截面上實(shí)際被測(cè)輪廓相對(duì)其理想圓的變動(dòng)量。它是衡量圓柱形零件形狀精度的重要指標(biāo)之一，誤差的大小將嚴(yán)重影響其工作性能。在GB7234—87（圓度測(cè)量術(shù)語(yǔ)、定義及參數(shù)）中，圓度誤差的評(píng)定方法有：最小區(qū)域圓法、最小二乘圓法、最小外接圓法和最大內(nèi)接圓法。用最小區(qū)域圓評(píng)定準(zhǔn)則所評(píng)定的圓度誤差值為最小，且具有唯一性。我國(guó)標(biāo)準(zhǔn)規(guī)定圓度誤差必須按最小區(qū)域圓評(píng)定準(zhǔn)則進(jìn)行評(píng)定[1]。

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

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

1 多種群遺傳算法(RMGA)

1.1 遺傳算法(RGA)的不足

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

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

（1） 在選擇操作過(guò)程中。當(dāng)群體中存在適應(yīng)度比其他個(gè)體高得多的個(gè)體時(shí)，該個(gè)體將會(huì)多次被選中，下一代群體很快被該個(gè)體所控制，群體失去競(jìng)爭(zhēng)性，使問(wèn)題過(guò)早地收斂于局部解。

（2） 交叉和變異操作中。交叉概率Pτ、變異概率Pm取值不當(dāng)極容易收斂于局部解。且不同的問(wèn)題所對(duì)應(yīng)的最佳Pτ、Pm取值往往不同，每個(gè)問(wèn)題都要通過(guò)不斷的反復(fù)試驗(yàn)才可確定，效率低下。

（3） 當(dāng)群體規(guī)模較小時(shí)，群體中多樣性程度低，個(gè)體間競(jìng)爭(zhēng)較弱。群體易趨于單一化，交叉操作的作用漸趨消失，群體的更新僅靠變異操作來(lái)維持，群體將很快收斂于局部最優(yōu)解；當(dāng)群體規(guī)模較大時(shí)，勢(shì)必造成計(jì)算量的增加，計(jì)算效率受到影響。

（4） 如果規(guī)定的最大遺傳代數(shù)過(guò)少，進(jìn)化不充分，也會(huì)造成未成熟收斂。

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

針對(duì)簡(jiǎn)單遺傳算法所存在的上述問(wèn)題，為克服未成熟收斂，本文應(yīng)用了一種算法性能更好的遺傳算法模型——多種群遺傳算法結(jié)構(gòu)模型[3]（簡(jiǎn)稱RMGA），可以用來(lái)取代常規(guī)的標(biāo)準(zhǔn)計(jì)算模型。RMGA 在RGA 的基礎(chǔ)上主要引入了以下幾個(gè)概念：

（1） 突破RGA 僅靠單個(gè)群體進(jìn)行遺傳進(jìn)化的框架，引入多個(gè)種群同時(shí)進(jìn)行優(yōu)化搜索；

（2） 各個(gè)種群之間通過(guò)遷移因子進(jìn)行聯(lián)系，實(shí)現(xiàn)多種群的協(xié)同進(jìn)化；最優(yōu)解的獲取是多個(gè)種群協(xié)同進(jìn)化的綜合結(jié)果；

（3） 在進(jìn)化收斂后，在全部種群的所有個(gè)體之間選擇適應(yīng)度函數(shù)最大的個(gè)體作為最優(yōu)解。多種群遺傳算法的結(jié)構(gòu)（以3個(gè)種群為例）如圖1所示。

圖 1 多種群算法結(jié)構(gòu)示意圖

因?yàn)橛?個(gè)種群同時(shí)對(duì)解空間進(jìn)行協(xié)同搜索，群體的多樣性由3個(gè)種群協(xié)同維持，故各種群的群體規(guī)模可以減小。多種群中的精華種群和其他種群有很大不同。在進(jìn)化的每一代，將各個(gè)種群的最優(yōu)個(gè)體放入精華種群加以保存。精華種群不進(jìn)行選擇、交叉、變異等遺傳操作，保證進(jìn)化過(guò)程中各種群產(chǎn)生的最優(yōu)個(gè)體不被破壞和丟失。同時(shí)，判斷算法終止條件在精華種群中產(chǎn)生，收斂判據(jù)是精華種群中最優(yōu)個(gè)體適應(yīng)值連續(xù)保持不變的最大代數(shù)和最大遺傳代數(shù)相結(jié)合，這樣比RGA 收斂判據(jù)更合理。

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

（1） 根據(jù)圓度誤差測(cè)試數(shù)據(jù)給出圓心坐標(biāo)，即染色體(x, y)的解域范圍，可以根據(jù)經(jīng)驗(yàn)或者通過(guò)傳統(tǒng)算法給出；

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

（3） 計(jì)算每一個(gè)體的適應(yīng)度函數(shù)，適應(yīng)度函數(shù)采用如下線性函數(shù)

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

（4） 每個(gè)子群分別獨(dú)立采用遺傳算法進(jìn)行復(fù)制、交叉、變異操作，子種群每進(jìn)化若干代就進(jìn)行子群間的遷移；

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

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

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

（7） 變異操作：隨機(jī)的選取一個(gè)個(gè)體，并隨機(jī)的使其中1個(gè)參數(shù)在其取值范圍內(nèi)隨機(jī)的增加或者減少5%；

（8） 種群是否達(dá)到最大進(jìn)化代數(shù)，如果未達(dá)到就轉(zhuǎn)向步驟(4)。否則此時(shí)選出全體種群中適應(yīng)度最大的個(gè)體所對(duì)應(yīng)的目標(biāo)函數(shù)值，即為全局最優(yōu)解。

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

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

2 圓度誤差評(píng)定的數(shù)學(xué)模型

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

圖 3 圓度誤差

圓度誤差值的評(píng)定按其定義應(yīng)為最小區(qū)域圓法(MZC)，近似的評(píng)定方法有最小二乘圓法(LSC)，另外有最大內(nèi)切圓(MIC)方法，最小外接圓(MCC)方法。不同的方法，對(duì)應(yīng)不同中心的理想圓。

圓度誤差是衡量圓形零件形狀精度的重要指標(biāo)之一，按最小區(qū)域法來(lái)計(jì)算圓度誤差是一個(gè)非線性優(yōu)化問(wèn)題，已有的方法受到計(jì)算精度的限制。

為了提高算法精度和收斂速度，快速準(zhǔn)確評(píng)定圓度誤差，本文運(yùn)用RMGA方法通過(guò)多個(gè)子種群計(jì)算并遷移優(yōu)良個(gè)體的進(jìn)化過(guò)程來(lái)實(shí)現(xiàn)對(duì)理想圓圓心以及圓度誤差的快速搜索。

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

按最小區(qū)域法評(píng)定圓度誤差，實(shí)質(zhì)上是尋找包容被測(cè)實(shí)際圓且具有半徑差為最小的兩理想同心圓，包容被測(cè)輪廓的同心圓有無(wú)數(shù)對(duì)，但只有一對(duì)半徑差是最小的，這對(duì)同心圓的圓心即為所求。

根據(jù)最小區(qū)域要求，圓度誤差為

式(5)即為用RMGA方法求解滿足最小區(qū)域 要求圓度誤差的目標(biāo)函數(shù)，優(yōu)化變量為使 ( )

f x,y最小的x 和y，圓度誤差的評(píng)定轉(zhuǎn)化為求二元函數(shù) f ( x,y )的最小值問(wèn)題。

3 計(jì)算實(shí)例

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

RMGA方法進(jìn)化過(guò)程如圖4所示，計(jì)算結(jié)果列于表2中，并將文獻(xiàn)[6]最小區(qū)域法的求解結(jié)果一并列入表中以便比較。同時(shí)，應(yīng)用RGA方法對(duì)表1的數(shù)據(jù)進(jìn)行計(jì)算，計(jì)算結(jié)果列入表2中，迭代曲線如圖5所示。

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

表1 圓度誤差計(jì)算的數(shù)據(jù)測(cè)量[6]

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

表 2 圓度誤差計(jì)算結(jié)果的比較

比較表2的結(jié)果可知，RMGA 方法的結(jié)果優(yōu)于文獻(xiàn)[6]的最小區(qū)域法結(jié)果和RGA 方法的結(jié)果。從圖4可知RMGA 進(jìn)化計(jì)算很快獲得最優(yōu)解，RMGA 方法在30多代以后就已經(jīng)基本收斂，RGA方法在40多代以后還在波動(dòng)，說(shuō)明RMGA 方法比RGA 方法有更快的收斂速度，用于計(jì)算圓度誤差是很有效的。

4 結(jié) 論

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

[1] 甘立永. 形狀和位置誤差檢測(cè)[M]. 北京： 國(guó)防工業(yè)出版社, 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] 鄒 琳, 夏巨諶, 胡國(guó)安. 基于實(shí)數(shù)編碼的多種群并行遺傳算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2004, 25(6)： 982-986.

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

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