論文題目:遺傳應用算法院系：計算機工程系專業：網絡工程班級學號：學生姓名：2014年10月23日摘要：遺傳算法是基于自然界生物進化基本法則而發展起來的一類新算法。本文在簡要介紹遺傳算法的起源與發展、算法原理的基礎上，對算法在優化、擬合與校正、結構分析與圖譜解析、變量選擇、與其他算法的聯用等方面的應用進行了綜述。該算法由于無需體系的先驗知識，是一種全局最優化方法，能有效地處理復雜的非線性問題，因此有著廣闊的應用前景。關鍵詞：遺傳算法；化學計量學；優化THEORYANDAPPLICATIONOFGENETICALGORITHMABSTRACT:GeneticAlgorithm(GA)isakindofrecursivecomputationalprocedurebasedonthesimulationofprincipleprinciplesofevaluationoflivingorganismsinnature1Basedonbriefintroductionoftheprinciple,thebeginninganddevelopmentofthealgorithms,thepaperrevieweditsapplicationsinthefieldsofoptimization,fittingandcalibration,structureanalysisandspectrainterpretationvariableselection,anditsusageincombinationwithothersTheapplicationofGAneedsnoinitiatingknowledgeofthesystem,andthereforeisacomprehensiveoptimizationmethodwithextensiveapplicationintermsofprocessingcomplexnonlinearproblemsoKEYWORDS:GeneticAlgorithm(GA)ChemometricsOptimization遺傳算法是在模擬自然界生物遺傳進化過程中形成的一種自適應優化的概率搜索算法，它于1962年被提出，直到1989年才最終形成基本框架。遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法，由美國J.H.Hollad教授提出，其主要特點是群體搜索策略和群體中個體之間的信息交換。該算法尤其適用于處理傳統搜索方法難以解決的復雜和非線性問題，可廣泛用于組合優化、機器學習、自適應控制、規劃設計和人工生命等領域。顧名思義，遺傳算法(GeneticAlgorithm,GA)是模擬自然界生物進化機制的一種算法，即遵循適者生存、優勝劣汰的法則，也就是尋優過程中有用的保留，無用的則去除。在科學和生產實踐中表現為，在所有可能的解決方法中找出最符合該問題所要求的條件的解決方法，即找出一個最優解。這種算法是1960年由Holland提出來的，其最初的目的是研究自然系統的自適應行為，并設計具有自適應功能的軟件系統。它的特點是對參數進行編碼運算,不需要有關體系的任何先驗知識，沿多種路線進行平行搜索，不會落入局部較優的陷阱，能在許多局部較優中找到全局最優點，是一種全局最優化方法。近年來，遺傳算法已經在國際上許多領域得到了應用。1985年召開了第1屆有關遺傳算法的國際會議，第1部關于這方面的專著在1989年問世。遺傳算法是一種有廣泛應用前景的算法但是它的研究和應用在國內尚處于起步階段。遺傳算法是一種基于生物的自然選擇和群體遺傳機理的搜索算法。它模擬了自然選擇和自然遺傳過程中發生的繁殖、交配和突變現象。它將每個可能的解看做是群體(所有可能解)中的一個個體，并將每個個體編碼成字符串的形式，根據預定的目標函數對每個個體進行評價，給出一個適應度值。開始時總是隨機地產生一些個體(即候選解)，根據這些個體的適應度利用遺傳算子對這些個體進行操作，得到一群新個體，這群新個體由于繼承了上一代的一些優良性狀，因而明顯優于上一代，這樣逐步朝著更優解的方向進化。遺傳算法在每一代同時搜索參數空間的不同區域，然后把注意力集中到解空間中期望值最高的部分，從而使找到全局最優解的可能性大大增加。作為進化算法的一個重要組成部分，遺傳算法不僅包含了進化算法的基本形式和全部優點，同時還具備若干獨特的性能：在求解問題時，遺傳算法首先要選擇編碼方式，它直接處理的對象是參數的編碼集而不是問題參數本身，搜索過程既不受優化函數連續性的約束，也沒有函數導數必須存在的要求。通過優良染色體基因的重組，遺傳算法可以有效地處理傳統上非常復雜的優化函數求解問題。若遺傳算法在每一代對群體規模為n的個體進行操作，實際上處理了大約O(n3)個模式，具有很高的并行性，因而具有明顯的搜索效率。在所求解問題為非連續、多峰以及有噪聲的情況下，能夠以很大的概率收斂到最優解或滿意解，因而具有較好的全局最優解求解能力。對函數的性態無要求，針對某一問題的遺傳算法經簡單修改即可適應于其他問題，或者加入特定問題的領域知識，或者與已有算法相結合，能夠較好地解決一類復雜問題，因而具有較好的普適性和易擴充性。遺傳算法的基本思想簡單，運行方式和實現步驟規范，便于具體使用。1算法原理1.1基本遺傳算法在自然界，由于組成生物群體中各個體之間的差異，對所處環境有不同的適應和生存能力，遵照自然界生物進化的基本原則，適者生存、優勝劣汰，將要淘汰那些最差個體，通過交配將父本優秀的染色體和基因遺傳給子代，通過染色體核基因的重新組合產生生命力更強的新的個體與由它們組成的新群體。在特定的條件下，基因會發生突變，產生新基因和生命力更強的新個體;但突變是非遺傳的，隨著個體不斷更新，群體不斷朝著最優方向進化，遺傳算法是真實模擬自然界生物進化機制進行尋優的。在此算法中，被研究的體系的響應曲面看作為一個群體，相應曲面上的每一個點作為群體中的一個個體，個體用多維向量或矩陣來描述，組成矩陣和向量的參數相應于生物種組成染色體的基因，染色體用固定長度的二進制串表述，通過交換、突變等遺傳操作，在參數的一定范圍內進行隨機搜索，不斷改善數據結構，構造出不同的向量，相當于得到了被研究的不同的解，目標函數值較優的點被保留，目標函數值較差的點被淘汰。由于遺傳操作可以越過位壘，能跳出局部較優點，到達全局最優點。遺傳算法是一種迭代算法，它在每一次迭代時都擁有一組解，這組解最初是隨機生成的，在每次迭代時又有一組新的解由模擬進化和繼承的遺傳操作生成，每個解都有一目標函數給與評判，一次迭代成為一代。典型的算法步驟有：（1）初始化，即隨機生成一個符號串群體；（2）基于適度函數對符號串進行評價；（3）應用一組遺傳操作生成一個新的符號串群體；（4）重復步驟（2）和（3）直至結果收斂。基于對自然界中生物遺傳與進化機理的模仿，針對不同的問題，很多學者設計了許多不同的編碼方法來表示問題的可行解，開發了許多種不同的遺傳算子來模仿不同環境下的生物遺傳特性。這樣，由不同的編碼方法和不同的遺傳算子就構成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優解的自適應搜索過程。基于這個共同特點，Goldberg總結出了一種統一的最基本的遺傳算法一—基本遺傳算法（simplegeneticalgorithms，簡稱SGA）[20]。基本遺傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應用價值。下面給出基本遺傳算法的構成要素：（1）染色體編碼方法。基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集｛0，1｝所組成的。初始群體中各個個體的基因值可用均勻分布的隨機數來生成。如：X=100111001000101101就可表示一個個體，該個體的染色體長度是n=18。（2）個體適應度評價。基本遺傳算法按與個體適應度成正比的概率來決定當前群體中每個個體遺傳到下一代群體中的機會多少。為正確計算這個概率，這里要求所有個體的適應度必須為正數或零。這樣，根據不同種類的問題，必須預先確定好由目標函數值到個體適應度之間的轉換規則，特別是要預先確定好當目標函數值為負數時的處理方法。遺傳算子。基本遺傳算法使用下述三種遺傳算子：?選擇運算使用比例選擇算子；?交叉運算使用單點交叉算子；?變異運算使用基本位變異算子或均勻變異算子。基本遺傳算法的運行參數。基本遺傳算法有下述4個運行參數需要提前設定：?N:群體大小，即群體中所含染色體的數量，一般取為20?100。?maxgen:遺傳運算的終止進化代數，一般取為100?500。?pc:交叉概率，一般取為0.4?0.99。?pm:變異概率，一般取為0.0001?0.1。需要說明的是，這里給出的4個運行參數的取值范圍是在經過了多次試驗后得到的經驗值，它們對遺傳算法的求解結果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據。所以我們在遺傳算法的實際應用中，要根據問題的不同并經過多次試驗來合理地選擇這些參數的取值大小或取值范圍。1.2遺傳算法的運算流程遺傳算法的主要運算流程如下：步驟一：初始化。設置進化代數計數器t=0；設置最大進化代數T；隨機生成M個個體作為初始群體P(0)。步驟二：個體評價。計算群體P(t)中各個個體的適應度。步驟三：選擇運算。將選擇算子作用于群體。步驟四：交叉運算。將交叉算子作用于群體。步驟五：變異運算。將變異算子作用于群體。群體P(t)經過選擇、交叉、變異運算之后得到下一代群體P(t+1)。步驟六：終止條件判斷。若t忍T，則：t=t+1，轉到步驟二；若t>T，則以進化過程中所得到的具有最大適應度的個體作為最優解輸出，終止計算。2遺傳算法的應用遺傳算法可處理連續變量參數的優化問題，特別是適用于復雜非線性問題的處理。可用于NMR脈沖形狀分析、RNA核苷酸測定、DNA構象分析、分子識別和設計、變量選擇等，在分析化學、環境科學、機械設計中的應用也非常廣泛。2.1優化遺傳算法用于優化的研究成果目前已經發表了較多的論文。這些成果有的是對此算法進行改進，如李通化等給出了一種動態的遺傳算法，詳細討論了變異函數對優化進程的影響，并用紅外光譜數據和二極管陣列檢測液相色譜數據進行了驗證。楊立民等運用雙極性壓縮函數適應度定標和基于排擠方法的選擇算子改進標準遺傳算法(SGA)，使其成為簡單通用、快速收斂的并行全局搜索算法；利用該算法優化誤差反向傳播網絡(BPN)，克服了BPN收斂慢和不具有全局收斂性的缺陷，并在此基礎上，建立大氣環境質量評價模型。張昆等為了使金屬切削加工中切削參數能實現實時優化以保證產品質量和設備效率，提出采用遺群體P(t)選擇運算交叉運算變異運算群體P(t+1)解碼解集合個體評價遺傳空間解空間傳算法，結合現場實際工況的反饋信息實現了實時優化，在任一不同的生產條件下均能達到最優值。也有應用遺傳算法去解決某一實際問題，如宋仁國等將人工神經網絡用于建立7175鋁合金的性能預測模型，在此基礎上，采用遺傳算法對其工藝進行優化；王舉等將間歇化工過程的最優設計問題，分解為只包含離散變量的主導問題和只含連續變量的子問題，把遺傳算法和線性規劃法結合起來對其進行求解，并在算法中引入了一類新的算子，顯著地提高了收斂概率。2.2擬合與校正分析儀器是通過分析信號的檢測從而得到物質的濃度，因此對儀器信號的分辨和校正就顯得尤為重要。蔡煜東等將遺傳算法用于化學校正，運用改進的遺傳算法擬合離子選擇電極工作曲線，并以半對數線性函數模型和二階幕函數模型嘗試了該算法的效果;結果表明，改進的遺傳算法性能較好，優于一般遺傳算法和直線回歸法，可望成為各類傳感器非線性曲線擬合的有效手段。蔡煜東還提出非線性多元函數擬合的遺傳算法，為分析化學中非線性函數擬合、曲線校正提供了一種性能較好的方法。孫雪峰等研究了遺傳算法求解復雜穆斯堡爾譜的方法，得到了滿意的結果。姚萌等從一系列雷達信號圖像獲得必要的物體的相關信息，以遺傳算法對其進行處理，將探測目標定位轉換為曲線擬合，在地下遺址探測中取得了較好結果。曲鐵軍等設計了使用遺傳算法的自適應濾波器，給出了離線和在線兩種實現方案。離線方案以識別濾波參數為主要目的，進而可以對狀態進行較準確的事后估計；在線方案以實時地對狀態進行估計為目的，對濾波器參數尋優采用具有良好性能的浮點編碼遺傳算法。2.3結構分析與圖譜解析結構分析在有機化學和藥物化學領域中的應用是非常廣泛的，遺傳算法主要應用在需要分子三維構像信息的時候，這在合成新的有機化合物和藥物、充分合理地利用天然資源具有重要的意義，鄧勃對這方面的應用作了簡要的評述。侯廷軍等對遺傳算法在計算機輔助藥物分子設計中的應用做了系統闡述。蔡文生等提出一種采用整數編碼和基于節點基因交換方式的遺傳算法，并應用于化學結構圖的同態研究。遺傳算法在一組隨機生成的表示目標結構與查詢結構節點間映射關系的整數串中進行逐步優化，直到找出與查詢結構匹配的映射，從而實現化學結構圖的同態匹配。盧佩章等將遺傳算法引入色譜峰解析程序，結合色譜峰模型及峰形經驗公式實現了恒溫色譜圖的全自動解析。陳閩軍等提出了一種基于遺傳算法的色譜指紋峰配對識別方法，該方法根據色譜指紋圖譜峰分布特性初選出若干標定峰，將其存入一個候選標定峰庫，同時根據這些候選標定峰從待測指紋圖譜中選出相應的候選標定峰，以遺傳算法對指紋峰進行識別。2.4變量選擇在各領域中，都存在目標函數與影響因素的某種關系，而這些影響因素是千變萬化的，它們的數量巨大，如何從大量的影響因素中尋找到最有利于建模的因素就成了研究的重要課題，遺傳算法在這方面顯示了它的優勢。LeardiR,BarrosAS等將遺傳算法用于主成分的選擇。鄭延斌等將遺傳算法應用于過飽和溶液Li2O-3B2O3-H2O體系結品過程動力學參數辨識，確定了結品反應速率常數、熱力學平衡濃度和表觀反應級數。另外，遺傳算法也可以用于光度分析中波長的選擇，進而用回歸算法求解。夏之寧等將遺傳算法用于紫外光譜數據處理，實現了多元分辨與校正，并對多組分分析體系進行同時定量測量。楊杰等介紹了激光切割、拼焊的一種基于遺傳算法的神經網絡工藝參數選擇方法的原理及實現方法，通過遺傳和變異的方法來優化和選擇權值進行評價，從而達到了智能化選擇參數的目的。章元等在傳統的遺傳算法中引入Metropolis接受準則，結合有序Gram-Schmidt正交化，得到了預測能力較強的模型，該法用于處理鋼中微量元素及熱處理工藝條件與鋼的力學性能關系問題，是一種較實用的變量篩選方法。2.5與神經網絡的聯用近年來神經網絡研究成為國際前沿的科學研究領域之一,將神經網絡與遺傳算法聯用，具有更強的建模、尋優等能力。孫衛國等用遺傳算法訓練神經網絡，為苯乙酸胺類化合物的QSAR建模，效果良好。王雅琳等針對電力部門提出的分時計價原則，以鋅電解過程為研究對象，用生產過程數據建立了不同酸度下電流密度與電流效率間關系，由此建立了分時供電優化模型，并用一種變形的多變量遞推最小二乘自適應策略不斷修正優化模型，采用高效模擬退火優化算法，引入懲罰算子，求解帶非線性約束和邊界約束的優化問題，獲得了合理的分時供電方案。路文江等利用人工神經網絡的自學習以及非線性逼近能力對材料元素與硬度的相關性進行擬合和預測，并用遺傳算法的強尋優能力對噴涂材料成分進行優化。張玉祥將遺傳算法、小波分析、人工神經網絡和模擬退火思想結合起來，提出了用遺傳算法來學習小波神經網絡層間的權值、尺度參數和位置參數，將其應用于礦壓預報，得到了比傳統神經網絡更優的效果。何耀華等針對化工過程系統中難于建立機理模型的過程或設備，提出了集成運用神經網絡和遺傳算法的優化方法(NN-GA方法)，并介紹了對神經網絡訓練算法的有效改進以及NN-GA方法的實施過程，給出了應用實3結論遺傳算法的研究歸納起來可分為理論與技術研究和應用研究兩個方面。可以說，遺傳算法的應用已經滲透到了各個領域。但目前遺傳算法的算法分析和理論分析還沒有跟上，還有很多富有挑戰性的課題亟待完善與解決，主要有：算法規模小。雖然遺傳算法模擬了生物的進化過程，但目前遺傳算法的運行規模還遠小于生物的進化規模。隨著計算機系統性能的不斷提高，人們將有可能實現模擬更接近于自然的進化系統，從而充分利用遺傳算法的并行性解決更復雜更有價值的問題。遺傳算法的編碼問題。編碼是遺傳算法求解問題的前提，最基本的是二進制編碼。其他的編碼方法有格雷碼、實數編碼、符號編碼、多參數編碼和DNA編碼等。不同的應用應該采用不同的編碼方式，因此基于不同的應用，遺傳算法的編碼還有待改進與完善。遺傳算法控制參數的選擇問題。遺傳算法中控制參數的不同選取會對遺傳算法的性能產生較大的影響，將影響到整個算法的收斂性。這些參數包括交叉概率(P。)、變異概率(兒)和種群數目(J7v。)等。早熟收斂和局部搜索能力差問題。早熟收斂和局部搜索能力差是遺傳算法最突出的兩個問題。有很多學者針對這兩個問題發表了大量的學術文章，但從根本上解決這兩個問題還有待研究發現。遺傳算子的無方向性問題。基本遺傳算子包括選擇算子、交叉算子和變異算子。設計性能優良的遺傳算子一直是遺傳算法的重要問題，如果能從遺傳算子的方向性著手改進遺傳算法，有可能會得到意想不到的結果。對上述問題的深入研究必將大大促進