改進(jìn)的遺傳算法用于工業(yè)測(cè)量數(shù)據(jù)處理.doc

改進(jìn)的遺傳算法用于工業(yè)測(cè)量數(shù)據(jù)處理摘要：從遺傳算法的兩個(gè)缺陷入手，在幾個(gè)方面對(duì)其進(jìn)行改進(jìn)，并且用MATLAB語(yǔ)言編程實(shí)現(xiàn)了改進(jìn)后的算法。文章用一個(gè)工程實(shí)例，探討了將改進(jìn)后的遺傳算法應(yīng)用于工業(yè)測(cè)量和逆向工程領(lǐng)域的可行性，并且通過(guò)比較發(fā)現(xiàn)改進(jìn)后的算法在全局收斂以及收斂速度方面都有了較大的改善，說(shuō)明了文章所作的改進(jìn)是有效的。文章提出的遺傳算法的改進(jìn)和應(yīng)用的探討具有較好的實(shí)用價(jià)值。關(guān)鍵詞：遺傳算法改進(jìn)全局收斂性收斂速度工業(yè)測(cè)量數(shù)據(jù)處理馬鞍面（雙曲拋物面）ApplicationofImprovedGAinIndustrialSurveyingDataProcessingAbstract:Viewingfromtwodefectsoftraditionalsimplegeneticalgorithm,thispapermodifiesitfromseveralaspects,andrealizestheimprovedalgorithmusingMATLABlanguageprogramming.Usinganengineeringexample,thispaperdiscussesthefeasibilityofapplyingimprovedGAintoindustrialsurveyingandreverseengineering.Throughcomparison,thispaperfindsoutthattheimprovedGAhasgoodbettermentinglobalconvergenceandconvergencerate,whichreflectsthattheimprovementiseffective.TheimprovementofGAanditsapplicationhasgoodpracticability.Keywords:geneticalgorithm,improvement,globalconvergence,convergencerate,industrialsurveying,dataprocessing,hyperbolicparaboloid1引言在工業(yè)測(cè)量以及逆向工程中，由于實(shí)物的形狀通常有嚴(yán)格的數(shù)學(xué)公式描述，通過(guò)采集其表面數(shù)據(jù)點(diǎn)的三維坐標(biāo)，可以擬合出實(shí)物表面在空間三維坐標(biāo)系中的幾何方程，這對(duì)于發(fā)現(xiàn)實(shí)物的整體變形以及生成模型設(shè)計(jì)CAD圖紙是至關(guān)重要的。對(duì)于平面擬合問(wèn)題，已經(jīng)得到很好的解決，但對(duì)于復(fù)雜曲面，即便是簡(jiǎn)單的二次曲面的最小二乘擬合的研究也相對(duì)較少，而且已有的擬合算法存在方程求解問(wèn)難、有奇異值和算法不穩(wěn)定等問(wèn)題1，因此一種好的全局優(yōu)化算法就顯得極其必要。遺傳算法(GeneticAlgorithm，簡(jiǎn)稱GA)是由美國(guó)Michigan大學(xué)的JohnH.Holland教授于1975年在他的著作AdaptationinNaturalandArtificialSystems中根據(jù)C.R.Darwin的生物進(jìn)化論和G.Mendel的遺傳變異理論提出的一種基于種群搜索的優(yōu)化算法。其思想是隨機(jī)產(chǎn)生初始種群,通過(guò)選擇(Reproduction)、交叉(Crossover)和變異(Mutation)等遺傳算子的共同作用使種群不斷進(jìn)化,最終得到最優(yōu)解2。與其他優(yōu)化方法相比，遺傳算法以單一字符串的形式描述所研究的問(wèn)題，只需利用適應(yīng)度函數(shù)進(jìn)行優(yōu)化計(jì)算,而不需要函數(shù)導(dǎo)數(shù)等其他信息，特別適合解決其他學(xué)科技術(shù)無(wú)法解決或難以解投稿日期：2008-01-12基金項(xiàng)目國(guó)家自然科學(xué)基金（40674010）；“十一五”科技支撐項(xiàng)目（2006BAC01B02-02-02,05）作者簡(jiǎn)介：潘國(guó)榮：教授、博士生導(dǎo)師，主要研究方向?yàn)榫芄こ虦y(cè)量、工業(yè)測(cè)量與測(cè)量數(shù)據(jù)處理。Email:決的復(fù)雜和非線性問(wèn)題，是繼專家系統(tǒng)、人工神經(jīng)網(wǎng)絡(luò)之后又一受人青睞的人工智能學(xué)科，一直是研究的一個(gè)熱點(diǎn)，被廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)、智能機(jī)器系統(tǒng)、智能制造系統(tǒng)、系統(tǒng)工程，人工智能、人工生命等領(lǐng)域，是21世紀(jì)智能計(jì)算中的關(guān)鍵技術(shù)之一3。習(xí)慣上將JohnH.Holland提出的遺傳算法稱為簡(jiǎn)單遺傳算法(SimpleGeneticAlgorithm,簡(jiǎn)稱SGA)。和其它優(yōu)化方法一樣，由于全局性的要求，簡(jiǎn)單遺傳算法作為一種通用的自適應(yīng)隨機(jī)搜索算法，還存在著早熟收斂(過(guò)早收斂于局部最優(yōu)值)和收斂速度慢這兩個(gè)缺陷，而且比較難克服,這給遺傳算法的應(yīng)用帶來(lái)了很大的不便。遺傳算法的改進(jìn)出現(xiàn)早熟往往是由于種群中出現(xiàn)了某些超級(jí)個(gè)體，隨著模擬生物演化過(guò)程的進(jìn)行，這些個(gè)體的基因物質(zhì)很快占據(jù)種群的統(tǒng)治地位，導(dǎo)致種群中由于缺乏新鮮的基因物質(zhì)而不能找到全局最優(yōu)值；另一個(gè)主要原因是由于遺傳算法中選擇及雜交變異等算子的作用，使得一些優(yōu)秀的基因片段過(guò)早丟失，從而限制了搜索范圍，使得搜索只能在局部范圍內(nèi)找到最優(yōu)值，而不能得到滿意的全局最優(yōu)值4。Whitley認(rèn)為，遺傳算法中最重要的兩個(gè)因素就是“種群多樣性”和“選擇壓力”，而選擇壓力過(guò)大是導(dǎo)致早熟收斂的一個(gè)重要原因。過(guò)大的選擇壓力雖然可以加快算法的收斂速度，卻會(huì)使種群中適應(yīng)度不利于問(wèn)題的求解的個(gè)體迅速“死亡”，種群的多樣性遭到破壞，使得算法搜索空間減小，進(jìn)而導(dǎo)致算法錯(cuò)誤地收斂到局部最優(yōu)值。降低選擇壓力雖然可以增大算法搜索到全局最優(yōu)值的概率，但卻會(huì)降低搜索效率，使算法的收斂速度變慢。為了使算法具有良好的性能，必須在提高選擇壓力和保持種群多樣性之間達(dá)到某種平衡5。為提高遺傳算法的搜索效率并保證得到問(wèn)題的最優(yōu)解，從以下幾個(gè)方面對(duì)簡(jiǎn)單遺傳算法進(jìn)行改進(jìn)：2.1初始種群產(chǎn)生在遺傳算法中，采用實(shí)數(shù)編碼策略比二進(jìn)制編碼策略具有精度高、搜索范圍大、表達(dá)自然直觀等優(yōu)點(diǎn)。如此，能克服二進(jìn)制編碼所存在的諸多缺點(diǎn)，如不易求解高精度問(wèn)題、不便于反應(yīng)所求問(wèn)題的特定知識(shí)及無(wú)法借鑒一些經(jīng)典優(yōu)化算法的寶貴經(jīng)驗(yàn)等。2.2個(gè)體適應(yīng)度計(jì)算計(jì)算適應(yīng)度，需先構(gòu)造適應(yīng)度函數(shù)。合理的適應(yīng)度函數(shù)能引導(dǎo)搜索朝最優(yōu)化方向前行。本文的適應(yīng)度函數(shù)是基于順序的基礎(chǔ)，其特點(diǎn)是個(gè)體被選擇的概率與目標(biāo)函數(shù)的具體值無(wú)關(guān)，僅與順序有關(guān)。構(gòu)造方法是先將種群中所有個(gè)體按目標(biāo)函數(shù)值的好壞進(jìn)行排序，設(shè)參數(shù)(0,1)，定義基于順序的適應(yīng)度函數(shù)為：1)1()(iiXevali=1,2,m(1)式中，iX為種群個(gè)體按優(yōu)劣排序后的第i個(gè)個(gè)體。一般在0.010.3之間取值。2.3選擇與交叉放棄賭輪選擇，避免早期的高適應(yīng)度個(gè)體迅速占據(jù)種群和后期的種群中因個(gè)體的適應(yīng)度相差不大而導(dǎo)致種群停止進(jìn)化。此處采用基于種群的按個(gè)體適應(yīng)度大小排序的選擇算法代替賭輪選擇方法，其過(guò)程偽碼描述如下：fitsort()將種群中的個(gè)體按適應(yīng)度大小進(jìn)行排序；while(種群還沒(méi)有掃描完)do排在最前面的個(gè)體復(fù)制兩份；排在中間的個(gè)體復(fù)制一份；排在后面的個(gè)體不復(fù)制；在不破壞種群基因多樣性的前提下加快算法的進(jìn)化速度。交叉率Pc按照公式(2)進(jìn)行自適應(yīng)調(diào)整：aveaveaveffkffffffkPcmaxmax21(2)式中，fmax為群體中最大的適應(yīng)度值；fave為每代群體的平均適應(yīng)度值；f為要交叉的兩個(gè)個(gè)體中較大的適應(yīng)值。此處，只要設(shè)定k1，k2（在0，1取值）的值，Pc即可進(jìn)行自適應(yīng)調(diào)整。2.4個(gè)體子代的產(chǎn)生在選擇出父本和母本后，按照交叉方法（單點(diǎn)、多點(diǎn)、一致交叉）進(jìn)行n次交叉，產(chǎn)生2n個(gè)個(gè)體，再?gòu)倪@2n個(gè)個(gè)體中選出最優(yōu)的兩個(gè)個(gè)體加入到新的種群中。如此，既保留了父本和母本的基因，又在進(jìn)化的過(guò)程中種群中個(gè)體的平均性能。2.5變異在遺傳算法中，如采用固定的變異概率Pm，則當(dāng)Pm取值很小時(shí)，變異算子對(duì)群體不會(huì)產(chǎn)生影響，不利于新的基因的引入；而當(dāng)Pm取值很大時(shí)，有可能破壞群體中的優(yōu)良基因，使得算法收斂速度變慢甚至不收斂。此處，本文采用動(dòng)態(tài)確定變異概率的方法，該方法既可防止優(yōu)良基因因?yàn)樽儺惗馄茐?，又可在陷入局部最?yōu)解時(shí)引入新的基因，該方法的偽碼描述如下：if個(gè)體的適應(yīng)度平均適應(yīng)度thenPm取值很小或?yàn)?；elsePm取值相對(duì)很大；endif如此，使得種群中好的基因不被破壞，既有利于不良基因的去除，又有利于新的基因的引入，從而可以很大程度的提高遺傳算法的性能。具體的自適應(yīng)調(diào)整的公式為：aveaveaveffkffffffkPm43maxmax(3)式中，fmax為群體中最大的適應(yīng)度值；fave為每代群體的平均適應(yīng)度值；f為要變異個(gè)體的適應(yīng)度值。此處，只要設(shè)定k3，k4（在0，1取值）的值，Pm即可進(jìn)行自適應(yīng)調(diào)整2.6種群的進(jìn)化與進(jìn)化終止條件將初始種群和產(chǎn)生的子代種群放在一起，形成新的種群，然后計(jì)算新的種群各個(gè)體的適應(yīng)度，將適應(yīng)度排在前面的m個(gè)個(gè)體保留，將適應(yīng)度排在后面m個(gè)個(gè)體淘汰，這樣種群便得到了進(jìn)化。每進(jìn)化一次計(jì)算一下各個(gè)個(gè)體的目標(biāo)函數(shù)值，當(dāng)相鄰兩次進(jìn)化平均目標(biāo)函數(shù)之差小于等于某一給定精度時(shí)，即滿足如下條件：)()1(ttXFXF(4)式中，)1(tXF為第t+1次進(jìn)化后種群的平均目標(biāo)函數(shù)值，)(tXF為第t次進(jìn)化后種群的平均目標(biāo)函數(shù)值，此時(shí)，可終止進(jìn)化。2.8遺傳算法流程及編程實(shí)現(xiàn)遺傳算法流程的偽碼表示為：ProcedureGeneticAlgorithm；begink=0；初始化P(k)；計(jì)算P(k)的適應(yīng)值；while(不滿足停止準(zhǔn)則)dobegink=k+1；從P(k-1)中選擇P(k)；復(fù)制算子重組P(k)；雜交和變異算子計(jì)算P(k)的適應(yīng)值；endendend作者采用MATLAB編程語(yǔ)言，實(shí)現(xiàn)了本文提出的改進(jìn)遺傳算法的程序包6。為了證明其有效性和探討其用于工業(yè)測(cè)量和逆向工程領(lǐng)域求取復(fù)雜模型參數(shù)的有效性，采用了一個(gè)鋼結(jié)構(gòu)部件表面方程擬合的工程實(shí)例來(lái)說(shuō)明問(wèn)題。改進(jìn)遺傳算法用于工業(yè)測(cè)量數(shù)據(jù)處理某鋼結(jié)構(gòu)工業(yè)構(gòu)件的表面為馬鞍面（雙曲拋物面），用工業(yè)測(cè)量的手段測(cè)得了其表面數(shù)十個(gè)點(diǎn)的坐標(biāo)，標(biāo)記為(Xi,Yi,Zi)。由于工業(yè)測(cè)量系統(tǒng)采用的是與該構(gòu)件相一致的坐標(biāo)系統(tǒng)，故無(wú)須進(jìn)行旋轉(zhuǎn)平移等操作。得到的測(cè)量點(diǎn)臨近點(diǎn)相連接得到如圖1所示的圖形。圖1采樣點(diǎn)分布圖Fig.1Distributionmapofsamplingpoints由空間立體幾何的知識(shí)可知，馬鞍面（雙曲拋物面）的標(biāo)準(zhǔn)方程為：)0(222qpzqypx(5)運(yùn)算采用的電腦配置為：IntelCPU雙核T25002.00GHz，1.00GB內(nèi)存，80GBHITACHI硬盤(pán)，ATIMobilityRadeonX1400顯卡，顯存128M。分別采用本文的改進(jìn)遺傳算法(ImprovedGA)以及傳統(tǒng)簡(jiǎn)單遺傳算法(SGA)進(jìn)行了多次運(yùn)算。由于遺傳算法的特性，每一次計(jì)算求得的參數(shù)值均在最后數(shù)位上略有差異，本文中采用計(jì)算得到的各項(xiàng)指標(biāo)的平均值，對(duì)兩種方法所得結(jié)果進(jìn)行比較，并且將計(jì)算得到的曲面參數(shù)值同設(shè)計(jì)值（p0=1.3,q0=1.6）進(jìn)行比較，將比較結(jié)果列舉如表1所示。表1曲面擬合結(jié)果比較Tab.1Comparisonofsurfacefittingresults采用方法平均遺傳代數(shù)平均計(jì)算時(shí)間(s)有無(wú)陷入局部極小參數(shù)估值變化比率（%）平均RMSE()pqp/pq/qSGA5040有1.32021.58361.6-1.08ImprovedGA303無(wú)1.31741.58671.30.84同設(shè)計(jì)的鋼結(jié)構(gòu)構(gòu)件表面幾何參數(shù)p0、q0進(jìn)行比較的結(jié)果可知，p和q都發(fā)生了一定的變化，超過(guò)了3的相對(duì)誤差限值，分析認(rèn)為該鋼結(jié)構(gòu)部件在長(zhǎng)期的使用過(guò)程中發(fā)生了變形。采用改進(jìn)遺傳算法擬合得到的雙曲拋物面圖形如圖2所示：圖2擬合結(jié)果Fig.2Fittingresult結(jié)語(yǔ)本文針對(duì)遺傳算法的兩個(gè)缺陷從幾個(gè)方面著手進(jìn)行了改進(jìn)，并且用一個(gè)鋼結(jié)構(gòu)工業(yè)構(gòu)件表面檢測(cè)的工程實(shí)例說(shuō)明了改進(jìn)算法的有效性和探索其應(yīng)用于工業(yè)測(cè)量和逆向工程的可行性。通過(guò)文中的實(shí)例和比較結(jié)果發(fā)現(xiàn)，改進(jìn)后的遺傳算法在全局收斂性和收斂速度方面都有了很大的改善，并且快速準(zhǔn)確有效地求得復(fù)雜結(jié)構(gòu)物體數(shù)學(xué)描述方程的參數(shù)，由此可以得出結(jié)論，改進(jìn)后的遺傳算法具有很好的優(yōu)勢(shì)，并且完全可以應(yīng)用于工業(yè)測(cè)量和逆向工程領(lǐng)域。參考文獻(xiàn):1顧步云，周來(lái)水，劉勝蘭，陳濤.逆向工程中二次曲面擬合方法的研究J.南京：機(jī)械制造與研究，2004,33(1)：11-14.1GuBuyun,ZhouLaishui,LiuShenglan,ChenTao.StudyonalgorithmofquadricsurfacefittinginreverseengineeringJ.Nanjing:MachineBuilding&Automation,2004,33(1):11-14.2HollandJ.AdaptationinnaturalandartificialsystemsM.UniversityofMichganPress,1975.3王福林，王吉權(quán)，吳昌友，吳秋峰.實(shí)數(shù)遺傳算法的改進(jìn)研究J.鞍山：生物數(shù)學(xué)學(xué)報(bào)，2006，21（1）：153-158.3WangFulin,WangJiquan,WuChangyou,WuQiufeng.Theimprovedresearchonacturalnu