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

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