基于自適應多種群遺傳算法的圓度誤差評定*

劉思遙,黃美發,,馮建國,程彬彬,吳　芬,吳常林

?

基于自適應多種群遺傳算法的圓度誤差評定*

劉思遙1,黃美發1,2,馮建國2,程彬彬1,吳芬1,吳常林1

(1.桂林電子科技大學 機電工程學院，廣西 桂林 541004；2.桂林機床股份有限公司，廣西 桂林 541000)

針對傳統遺傳算法在圓度誤差評定方法存在搜索穩定性差、易陷入局部收斂和全局搜索能力不足的問題，改進傳統遺傳算法(TGA)，提出了采用自適應多種群遺傳算法(AMPGA)的評定方法。根據圓度誤差評定的特點，建立了多種群協同進化的遺傳方式，并引入了交叉概率Pc和變異概率Pm隨個體適應度值變化而不斷調整的遺傳機制，通過編寫自適應多種群遺傳算法(AMPGA)程序對圓度誤差進行評定，得到相應結果與三坐標測量機的實測值對比。對比分析結果表明該方法能有效的克服傳統遺傳算法(TGA)在圓度誤差評定上存在的搜索穩定性差、易陷入局部收斂和全局搜索能力不足的問題，是一種更有效的圓度誤差評定方法。

遺傳算法;自適應;多種群遺傳算法;圓度評定;最小區域圓法

0　引言

圓度誤差是指回轉體在任意橫截面內被測實際圓對其理想圓的變動量。圓度誤差是衡量回轉體零件形狀精度的一個重要指標，直接影響到機器零部件的旋轉精度和裝配精度。因此，準確的評定圓度誤差是保證回轉體零件加工精度和裝配精度的重要依據[1]。

如何快速精確有效的評定圓度誤差的大小一直受到國內外研究者們的廣泛關注，圓度誤差的評定方法有最小二乘法、最小區域圓法、最小外接圓法和最大內接圓法等方法。根據國標(GB1183—80)的規定，圓度誤差須按最小區域圓法進行評定[2]。

與其他優化算法不同的是遺傳算法屬于全局搜索算法，具有較高的并行計算能力，對初始值的要求是解區間而非單個的點，全局搜索能力和魯棒性好[3]。但傳統遺傳算法(TGA)在評定圓度誤差時，存在以下不足：固定不變的交叉概率Pc和變異概率Pm并不符合算法各階段的要求，會直接影響算法的全局搜索能力；TGA在算法快要找到最優解的時候，容易在最優解附近來回變動，局部搜索能力差，算法遲遲不能收斂，嚴重降低了算法的收斂速度；TGA停止的依據是到達規定的最大遺傳代數，如果規定的最大遺傳代數過小，進化不充分，也會造成未成熟收斂[1]；種群中個體更新只靠變異操作來維持，存在較大的隨機性[4-5]。

本文根據圓度誤差評定實際需要，改進遺傳算法，提出自適應多種群遺傳算法(AMPGA)對圓度誤差進行評定，建立了多種群協同進化的遺傳方式，并引入了交叉概率Pc和變異概率Pm隨個體適應度值變化而不斷調整的遺傳機制，通過編寫自適應多種群遺傳算法(AMPGA)程序對圓度誤差進行評定，并分別與三坐標實測圓度誤差值和TGA評定的結果作對比，結果表明AMPGA能有效克服TGA在圓度誤差評定上的搜索穩定性差、易陷入局部收斂和全局搜索能力不足的問題，同時在遺傳代數、收斂速度方面，AMPGA要明顯優于TGA，能快速準確的評定出圓度誤差值，是一種有效的圓度誤差評定優化算法。

1　自適應多種群遺傳算法原理

多種群協同進化是加快遺傳算法收斂速度的一個重要手段，用參數MP表示子種群數量,本文取MP=10。每個子種群獨立執行遺傳算法，所有子種群協同進化，選定遺傳算法的參數GGAP=0.9[6]。

1.1個體適應度大小計算

本文采用采用實數編碼遺傳算法，適應度值函數采用線性排序函數：

(1)

式(1)中F為個體的適應度值，sp為選擇壓差1≤sp≤2，選擇壓差一般取1.5，P為個體在種群中的位置，N是子種群中的個體數量，本文取N=40。個體按ranking函數進行排序。

1.2選擇操作

AMPGA的每個子種群在規定的遺傳代數內分別獨立的執行選擇、交叉和變異操作。采用隨機遍歷抽樣的方式，個體被選中概率用式(2)計算：

(2)

1.3自適應交叉和變異概率

為了改善TGA在圓度誤差評定上的易陷入局部收斂和全局搜索能力不足的問題。本文提出了交叉概率Pc和變異概率Pm隨個體適應度值自適應變化的遺傳機制。

相比TGA中交叉概率Pc和變異概率Pm為固定值，AMPGA的交叉概率Pc和變異概率Pm是隨著適應度值的變化自適應調整，在遺傳算法前期如果交叉概率Pc過小，那么群體極容易陷入局部最優解，同樣算法初期需要加強遺傳算法的變異概率Pm，從而保證種群的多樣性；到算法的后期，個體比較接近最優解，如果交叉概率Pc很大的話，則容易造成算法在最優解附近變化不收斂的情況。另外在種群中，適應度較大的個體應當施加較小的交叉概率Pc和變異概率Pm，使種群中的優良個體得以延續。而適應度小的個體則應當施加較大的交叉概率Pc和變異概率Pm。AMPGA交叉概率Pc與變異概率Pm調整公式為：

(3)

(4)

式(3)、式(4)中Fmax{i}表示第i個子種群中最大適應度個體的適應度值，Fave{i}表示第i個子種群平均適應度值，F{i}表示第i個子種群中個體的適應度值，t1代表適應度值大于或等于平均適應度值個體的序號，t2表示適應度值小于平均適應度值個體的序號；取Pc2=0.85，Pm2=0.05[7-8]。

1.4遷移操作和優良種群選擇操作

為了改善TGA只靠變異操作來維持種群更新的隨機性大弊端，本文引入了種群間遷移和優良種群選擇的概念，種群間個體遷移是指在適應度值排序的基礎上，從源種群中選擇適應最大的個體遷移到目標種群中并替換掉目標種群中適應度最小的個體；優良種群選擇操作是指在達到規定的遺傳代數后，從所有子種群中選擇最優的個體組成優良種群。AMPGA在達到規定的遺傳代數，即最大保持代數gen0時，子種群間發生遷移，調用遷移算子，選擇源種群中的適應度最大個體，替代目標種群中的適應度最小個體。AMPGA示意圖如圖1所示。

圖1　AMPGA種群間遷移與優良種群示意圖

1.5自適應多種群遺傳算法停止的依據

AMPGA停止的依據是：某一代的優良種群中的最優解個體達到要求，即算法搜索到了全局最優解，當算法計算最小值時，某一代優良種群中的最優解不小于上一代優良種群中的最優解，gen0=gen0+1算法停止；否則最大進化代數gen0=0，再重復上述操作。同理，在計算最大值的操作過程中，當某一代優良種群中的最優解不大于上一代優良種群中的最優解，gen0=gen0+1算法停止；否則最大進化代數gen0=0，再重復上述操作。AMPGA流程如圖2所示。

圖2　AMPGA流程圖

2　實驗驗證

建立AMPGA最小區域圓法圓度評定的目標函數。利用MATLAB平臺，編寫AMPGA和TGA程序，評定圓度誤差。并與三坐標測量機的實測值對比。

本文的數據來源為海克斯康global07-10-07型三坐標測量機的實測值，對一圓柱體零件的一個橫截面進行采樣取點，一共在圓截面上采樣30個點，覆蓋整個圓周，測量零件圓度誤差為0.0185mm，最小區域圓圓心點坐標為(-0.0018,0.0014)，單位為mm，海克斯康global07-10-07型三坐標測量機精度為次微米級，精度等級高，符合圓度評定要求。采樣輪廓的被測點坐標P{(xj,yj)|j=1,2,……m}，采樣點分布于整個圓周上，測點的最小值和最大值分別表示為xmin=min{xj}，ymin=min{yj}；xmax=max{xj}，ymax=max{yj}。被測點構成的圓的圓心(xc,yc)范圍為xmin≤xc≤xmax，ymin≤yc≤ymax。取0≤a≤1,0≤b≤1，輪廓的圓心點坐標xc與yc可以表示為式(5)、式(6):

xc=xmin+a×(xmax-xmin)

(5)

yc=ymin+b×(ymax-ymin)

(6)

最小區域圓建立圓度誤差評定方程，以此作為遺傳算法的優化目標函數。目標函數優化參數分別為被測圓的最小區域圓的圓心的橫坐標xc與縱坐標yc。同樣考慮到遺傳算法搜索時圓心點的橫坐標和縱坐標取值是在坐標原點附近來回變化的，因此在本文中AMPGA和TGA取-1≤xc≤1,-1≤yc≤1。最小區域圓法圓度誤差計算公式為：

e=min(rmax-rmin)

(7)

式(7)中rmax是最小區域法的兩個同心圓外圓的半徑，rmin是最小區域圓的兩個同心圓內圓的半徑[9-10]。測點到最小區域法圓心的距離用式(8)表示。

(8)

圖3　圓度誤差最小區域圓法示意圖

算法的實質是搜索最小區域法同心圓的圓心點坐標，這樣的同心圓有無窮多個，但只有一對同心圓的半徑差是最小的，這個最小差值就是圓度誤差值。

3　數據的對比分析

3.1三坐標測量機測取點

本文利用海克斯康global07-10-07 三坐標測量機在圓柱體零件外表面上測取30個點，這些點覆蓋整個圓周，符合圓度評定的要求。在pc-dmis軟件選擇評定方式為最小區域圓法，評定的圓度誤差值為0.0185mm，最小區域圓圓心點坐標為(-0.0018,0.0014)，單位mm，海克斯康global07-10-07 型三坐標測量機精度是次微米級。實際測量的測點橫坐標xi和縱坐標yi記錄如表1所示。

表1　測點的坐標

3.2利用程序評定圓度誤差

將測點數據分別導入到AMPGA與TGA程序中，利用算法程序分別評定圓度誤差值，各自計算10次，記錄下圓心點坐標值xc、yc和圓度誤差值e，取小數點后三位有效數字。傳統遺傳算法中取最大遺傳代數MAXGEN=1000，自適應多種群遺傳算法中取最大保持代數MAXGEN=500[9-10]，計算結果如表2所示。

表2　TGA與AMPGA評定結果對比

從表2中可以看出AMPGA的穩定性明顯優于TGA，AMPGA的相對誤差δ穩定0.07%左右，而TGA的相對誤差δ均值為2.4%，表現的很不穩定。同樣在最小區域圓圓心點坐標的評定上，AMPGA也表現出了良好的穩定性，圓心點的橫坐標和縱坐標值都相對穩定，且明顯優于TGA。

3.3最優解隨遺傳代數變化過程

利用算法程序記錄下優良種群中最優解的變化過程，算法計算到某一代是最優解不再發生變化，此時算法收斂，即算法搜索到了全局最優解。圖4是AMPGA最優解隨遺傳代數的變化曲線圖，圖5是TGA最優解隨遺傳代數的變化曲線圖。

圖4　AMPGA進化過程圖

圖5　TGA進化過程圖

由圖4可以看出AMPGA在計算到100左右時，最優解的值基本趨于穩定，即算法到達成熟收斂，找到了全局最優解，此時的最優解即為評定的圓度誤差值；由圖5可以看出TGA在算法計算到400代左右時，仍然沒有收斂，算法并沒有趨于穩定。由此看出AMPGA在遺傳代數上要明顯小于TGA收斂速度更快。

4　結論

通過改進傳統遺傳算法，利用MATLAB平臺，建立了AMPGA與TGA最小區域圓法圓度評定的目標函數，通過編寫算法程序，分別對AMPGA和TGA做了最小區域圓法圓度評定。通過與三坐標測量機的實測值對比分析，得出以下結論：

(1)AMPGA對遺傳算法中的兩個重要參數交叉概率Pc和變異概率Pm運用自適應取值，根據個體在不同的進化階段適應度的線性排序自適應取值，保證了種群的多樣性，能有效克服傳統遺傳算法的未成熟收斂。

(2)AMPGA屬于多種群并行遺傳算法，收斂速度明顯高于TGA。引入種群間遷移算子和優良種群選擇算子改變了TGA僅靠變異更新個體隨機性大的弊端。AMPGA在100代左右就能搜索到全局最優解，而TGA在400代左右仍表現的很不穩定性，并未達到全局收斂。多次計算的結果表明AMPGA在收斂速度和穩定性方面優于TGA。

[1] 繆立棟,郭慧,張帆.基于多種群實數編碼遺傳算法的圓度誤差評定[J].工程圖學學報,2010(2):43-48.

[2] 劉飛，梁霖，徐光華，等.一種圓度誤差最小區域評定方法[J].組合機床與自動化加工技術,2011(7):48-51.

[3] 陳颯，李郝林.基于改進遺傳算法的圓度誤差評定[J].機械設計與制造,2006(1):20-21.

[4] 謝耿勛.基于遺傳算法的性狀誤差算法的研究[D].沈陽:東北大學,2012.

[5] 史峰.MATLAB智能算法30個案例分析[M].北京:北京航空航天大學出版社,2011.

[6] 雷英杰.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2004.

[7] 廖平.用遺傳算法精確計算圓度誤差[J].南京航空航天大學學報,1999,31(4):393-397.

[8]PottsJC,GiddensTD,YadavSB.Thedevelopmentandevaluationofanimprovedgeneticalgorithmsbasedonmigrationandartificialselection[J].IEEETransonSMC,1994,24(1):73-86.

[9] 周劍平.基于MATLAB的圓度評定方法[J].計量與測試技術,2005,32(2):5-7.

[10] 張國強.自適應遺傳算法的改進與應用[J].艦船電子工程,2010,30(1):83-85.

(編輯李秀敏)

RoundnessErrorEvaluationBasedonAdaptiveMultiplePopulationGeneticAlgorithm

LIUSi-yao1,HUANGMei-fa1,2,FENGJian-guo2,CHENGBin-bin1,WUFen1,WUChang-lin1

(1.SchoolofMechanicalandElectricalEngineering,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China; 2.GuilinMachineToolCo.,Ltd,GuilinGuangxi541000,China)

Thetraditionalgeneticalgorithm(TGA)roundnesserrorevaluationarepoorstability,prematureconvergenceandinsufficientofglobalsearchability.Thispaperimprovethetraditionalgeneticalgorithm(TGA),putforwardtheadaptivemultiplepopulationgeneticalgorithm(AMPGA)roundnesserrorevaluationmethod.Basedonthecharacteristicsofroundnesserrorevaluation,weestablishmultiplepopulationsco-evolutionarygeneticalgorithm,andintroducetheadjustmentofcrossoverprobabilityandmutationprobabilitywiththeindividualfitnessvaluechanging.Wewriteadaptivemultiplepopulationgeneticalgorithm(AMPGA)programandworkouttheroundnesserror.Andcomparethecorrespondingresultswiththemeasuredvaluesofthreecoordinatemeasuringmachine.ThroughthecontrastanalysisresultsprovethattheAMPGAcaneffectivelyovercomepoorsearchstability,prematureconvergenceandinsufficientofglobalsearchabilityontheroundnesserrorevaluation,TheAMPGAisamoreeffectivemethodofroundnesserrorevaluationcomparewithTGA.

geneticalgorithm(GA);adaptive;multiplepopulationgeneticalgorithm(AMPGA);roundnesserrorevaluation;minimumzonecircleroundnesserrorevaluation

1001-2265(2016)08-0096-04DOI:10.13462/j.cnki.mmtamt.2016.08.027

2015-09-06；

2015-10-09

國家自然科學基金資助項目(51365009)；廣西制造系統與先進制造技術重點實驗室主任課題資助項目(13-051-09-009Z)；桂林電子科技大學研究生教育創新計劃資助項目(YJCXS201501)

劉思遙(1988—)，男，湖南永州人，桂林電子科技大學碩士研究生，研究方向為現代設計與制造技術，(E-mail)309141622@qq.com。

TH164;TG506

A