繆立棟, 郭 慧, 張 帆
(華東理工大學(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)有效的提高了全局搜索能力和局部搜索速度,收斂更快,精度更高。
遺傳算法是一種借鑒生物界自然選擇機(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)化,算法最終不能給出令人滿(mǎ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ì)造成未成熟收斂。
針對(duì)簡(jiǎn)單遺傳算法所存在的上述問(wèn)題,為克服未成熟收斂,本文應(yīng)用了一種算法性能更好的遺傳算法模型——多種群遺傳算法結(jié)構(gòu)模型[3](簡(jiǎn)稱(chēng)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ī)??梢詼p小。多種群中的精華種群和其他種群有很大不同。在進(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) 根據(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ù)采用如下線(xiàn)性函數(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)生后代,按照線(xià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 多種群遺傳算法程序框圖
圓度誤差是指被測(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è)非線(xiàn)性?xún)?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方法求解滿(mǎn)足最小區(qū)域 要求圓度誤差的目標(biāo)函數(shù),優(yōu)化變量為使 ( )
f x,y最小的x 和y,圓度誤差的評(píng)定轉(zhuǎn)化為求二元函數(shù) f ( x,y )的最小值問(wèn)題。
以文獻(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中,迭代曲線(xiàn)如圖5所示。
圖 4 圓度誤差的RMGA迭代曲線(xiàn)
表1 圓度誤差計(jì)算的數(shù)據(jù)測(cè)量[6]
圖 5 圓度誤差的RGA迭代曲線(xiàn)
表 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ì)算圓度誤差是很有效的。
本文針對(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.