帶互動界面的遺傳算法演示系統(tǒng)文獻綜述

PAGE9 本科畢業(yè)設計文獻綜述（2012屆）論文題目帶互動界面的遺傳算法演示系統(tǒng)帶互動界面的遺傳算法演示系統(tǒng)摘要：本文是關于帶互動界面的遺傳算法演示系統(tǒng)設計與實現(xiàn)的一篇文獻綜述，先對遺傳算法進行簡單介紹，然后詳述一下國內(nèi)外相關研究現(xiàn)狀以及現(xiàn)階段存在的技術關鍵及問題，最后進行簡單總結與預測未來的發(fā)展趨勢。關鍵詞：遺傳算法，選擇，最優(yōu)解，發(fā)展趨勢一、引言遺傳算法通過有組織的然而是隨機的信息交換來重新結合那些適應性好的稱為染色體的二進制數(shù)串，在每一代中，利用上一代串結構中適應性好的位和段來生成一個新的串的群體；作為額外增添，偶爾也要在串結構中嘗試新的位和段來替代原來的部分[1]。利用二進制編碼的方法，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。二、研究意義遺傳算法作為具有系統(tǒng)優(yōu)化、適應和學習的高性能計算和建模方法的研究，廣泛應用于自動控制、計算科學、模式識別、智能故障診斷管理科學和社會科學領域，適用于解決復雜的非線性和多維空間尋優(yōu)問題[2]。利用遺傳算法的搜索過程不受優(yōu)化函數(shù)的連續(xù)性約束，也沒有優(yōu)化函數(shù)的導數(shù)必須存在的要求；遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度；遺傳算法更適合大規(guī)模復雜問題的優(yōu)化。正因遺傳算法有如此多的優(yōu)點，所以對它的研究將具有重要意義。標準遺傳算法的流程如下表所示[3]：GA（Fitness，F(xiàn)itness＿threshold，p，r，m）Fitness：適應度評分函數(shù)，為給定假設賦予一個評估分數(shù)Fitness＿threshold：指定終止判據(jù)的閾值p：群體中包含的假設數(shù)量r：每一步中通過交叉取代群體成員的比例m：變異率初始化群體：P←隨機產(chǎn)生的p個假設評估：對于P中的每一個h，計算Fitness（h），當[maxFitness（h）]＜Fitness＿threshold時，產(chǎn)生新的一代Ps：（1）選擇：用概率方法選擇P的（1－r）p個成員加入Ps從P中選擇假設hi的概率Pr（hi）用下面公式計算：（2）交叉：根據(jù)上面給出的Pr（hi），從P中按概率r*p／2選擇對假設對于每對假設＜h1，h2＞，應用交叉算子產(chǎn)生兩個后代,把所有的后代加入Ps（3）變異：使用均勻的概率從Ps中選擇成員，對于選出的每個成員，在其表示中隨機選擇一個位取反（4）更新：P←Ps（5）評估：對于P中h的每個計算Fitness（h）從P中返回適應度最高的假設三、國內(nèi)外研究現(xiàn)狀及難點遺傳算法最早是由美國Michigan大學的Holland教授和他的學生們在70年代初提出而創(chuàng)立的。從80年代開始，對遺傳算法的研究與應用進入了一個新高潮，國際上有大量關于這方面的論文與研究成果。進入90年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。應用研究尤其活躍，利用遺傳算法進行優(yōu)化和規(guī)則學習的能力顯著提高。一些新的理論和方法在應用研究中也得到了迅速的發(fā)展。理論上,成功地應用齊次有限馬爾科夫鏈理論分析了簡單遺傳算法、最優(yōu)保存簡單遺傳算法和自適應遺傳算法的收斂性，從而得到簡單遺傳算法不是全域收斂,而和是全域收斂的重要結論[5]。此外，有人利用馬爾科夫鏈理論對浮點數(shù)編碼的遺傳算法進行了嚴密的全域收斂性分析，另有學者也研究了達到全局最優(yōu)解的遺傳算法的時間復雜性問題[6]。這些理論問題的相繼解決,為遺傳算法獲得更好的實際應用奠定了基礎。在遺傳算法與其他方法的混合研究上較為成功，它既發(fā)揮了遺傳算法的全局性特點又發(fā)揮了某一種方法對于某一特定問題有效收斂性的特長并且能夠快速穩(wěn)定的搜索到問題的全局最優(yōu)解。主要的混合方法有并行遺傳與神經(jīng)網(wǎng)絡混合學習方法，遺傳與進化編程混合方法，模擬退火與遺傳算法混合方法等[7]。目前遺傳算法已被廣泛應用于自動控制、機器人學、計算機科學、模式識別、模糊與人工神經(jīng)網(wǎng)絡和工程優(yōu)化設計等領域。在國外，1975年Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應》（AdaptationinNaturalandArtificialSystems），這是第一本系統(tǒng)論述遺傳算法的專著，因此有人把1975年作為遺傳算法的誕生年。Holland在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（schematheory）。該理論首次確認了結構重組遺傳操作對于獲得隱并行性的重要性[8]?；陬I域交叉的交叉算子這一概念是由D.Whitey于1991年在他的論文中提出的，該算子是特別針對用序號表示基因的個體的交叉，并將其應用于TSP問題中，通過實驗對其進行驗證。常用的交叉操作方法有一點交叉。二點交叉、一致交叉、二維交叉、樹結構交叉等等[9]。D.H.Ackley等提出了隨機迭代遺傳爬山算法（SIGH），采用了一種復雜的概率選舉機制，此機制中由m個“投票者”來共同決定新個體的值[10]?？傮w來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力。單一操作的多親交叉算子是將遺傳算法與但單一方法結合起來，它根據(jù)兩個母體和一個額外的個體產(chǎn)生新個體，其交叉結果與對三個個體用選舉交叉產(chǎn)生的結果相同[11]。該算子由H.Bersini和G.Seront提出。就國內(nèi)來說在遺傳算法方面也取得了很大進展。2002年，戴曉明等應用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題。2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Building-blockCodedParallelGA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005年，江雷等針對并行遺傳算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進化。盡管這一算法已具有較多的優(yōu)點,業(yè)已在實際中得到了大量應用,但它也存在著許多急待解決的問題。例如，如何進行算法本身的參數(shù)優(yōu)化選擇，即對群體的規(guī)模N、交換概率Pc和變異概率Pm進行優(yōu)化選擇。因為實踐發(fā)現(xiàn)這些參數(shù)的選取直接關系著GA求解問題的成敗。如何避免算法過早收斂的產(chǎn)生，過早收斂是指GA在執(zhí)行過程中會出現(xiàn)群體中的個體過早地在一個非最優(yōu)點上達到完全相同或接近完全相同的現(xiàn)象。一旦出現(xiàn)該現(xiàn)象,利用GA就不能求得問題的全域最優(yōu)解[12]。對于動態(tài)數(shù)據(jù)，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過早地收斂，而對以后變化了的數(shù)據(jù)不再變化[13]。針對這一問題，研究者提出了一些方法增加基因的多樣性，從而防止過早地收斂。其中一種是觸發(fā)式超級變異，就是當染色體群體的質量下降（彼此區(qū)別減少）時增加變異概率；另一種是隨機外來染色體，是偶爾加入一些全新的隨機生成的染色體個體，從而增加染色體多樣性[14]。還有如何改進操作手段或引入新操作手段來提高算法的執(zhí)行效果，如何將該算法與其它傳統(tǒng)優(yōu)化方法有機結合起來等等問題。以上存在的問題有的已基本獲得解決,而有的則正在解決當中。四、總結與展望遺傳算法作為具有系統(tǒng)優(yōu)化、適應和學習的高性能計算和建模方法的研究漸趨成熟。遺傳算法具有進化計算的所有特征，同時又具有自身的特點[15]：（1）搜索過程既不受優(yōu)化函數(shù)的連續(xù)性約束，也沒有優(yōu)化函數(shù)導數(shù)必須存在的要求（2）遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度（3）遺傳算法是一種自適應搜索技術，其選擇交叉變異等運算都是以一種概率方式來進行，從而增加了搜索過程的靈活性，具有較好的全局優(yōu)化求解能力（4）遺傳算法直接以目標函數(shù)值為搜索信息，對函數(shù)的性態(tài)無要求，具有較好的普適性和易擴充性（5）遺傳算法更適合大規(guī)模復雜問題的優(yōu)化但遺傳算法也存在很多問題，如：（1）Holland在運用模式定理分析編碼機制時建議使用二進制編碼，但二進制編碼不能直接反映問題的固有結構、精度不高、個體長度大和占用計算機內(nèi)存多[16]。解決這個問題的措施有：①動態(tài)編碼即在保持串長不變的前提下減小搜索區(qū)域，當算法收斂到某局部最優(yōu)時增加搜索的精度，從而使得在全局最優(yōu)點附近可以進行更精確的搜索[17]。②對于問題的變量是實向量的情形，可以直接采用實數(shù)進行編碼，便于引入與問題領域相關的啟發(fā)式信息以增加算法的搜索能力[18]。③復數(shù)編碼本是為了描述和解決二維問題，還可以推廣到多維問題的描述中[19]。（2）適應度函數(shù)[20]：適應度函數(shù)是用來區(qū)分群體中個體好壞的標準，選擇的好壞直接影響算法的優(yōu)劣，選擇的不好容易引起兩種不利于優(yōu)化的現(xiàn)象：①異常個體引起早熟收斂，影響求得全局最優(yōu)解這種現(xiàn)象常出現(xiàn)在小規(guī)模群體中。②個體差距不大引起搜索成為隨機漫游，特別是平均適應度已接近最佳適應度時，最佳個體與其他許多個體在選擇過程中就會有大體相等的選擇機會，影響求得最優(yōu)解。（3）選擇策略[21]：優(yōu)勝劣汰的選擇機制使得適應值大的個體有較大的存活機會，不同的選擇策略對算法性能有較大的影響輪盤賭法是使用最多的選擇策略，但這種策略可能會產(chǎn)生較大的抽樣誤差，對此提出了很多的改進方法，如繁殖池選擇、非線性排名選擇、基于局部競爭機制的選擇等。（4）控制參數(shù)[22]：群體大小、交換概率、變異概率等這些參數(shù)對遺傳算法性能影響較大，會影響算法的全局最優(yōu)性和收斂性Davis提出自適應算子概率的方法，用自適應機制把算子概率與算子產(chǎn)生的個體適應性結合，而且高適應性值被分配高算子概率這種方法較好地解決了這一問題。隨著應用領域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結構的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃（EvolutionProgramming,EP）以及進化策略（EvolutionStrategy,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點。這三者之間的比較研究和彼此結合的探討正形成熱點。參考文獻：李敏強，寇繼松，林丹，李書全.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.3．L.Davis,HandbookofGeneticAlgorithms,vanNostrandRei－nhold,NewYork，1991．席裕庚，柴天佑，惲為民．遺傳算法綜述．1996，13（60）:69－7－708．劉勇，等．非數(shù)值并行算法（二）遺傳算法[M]．北京:科學出版社，1995．陳國良，等．遺傳算法及應用．BehaviourofAClassofGeneticAdaptiveSystems[D]．UniversityofMichigan，1975．孫艷豐．王眾托．自然數(shù)編碼遺傳算法的最優(yōu)種群規(guī)模[J]．沈陽：信息與控制，1996（5）．陳文清．遺傳算法綜述[J]．洛陽：洛陽高等?？茖W校學報，2003．徐清振，肖成林．遺傳算法的研究與應用[J]．廣州：現(xiàn)代計算機，2006．章曉級，戴冠中，徐乃平．一種新的優(yōu)化搜索算法-遺傳算法[J]．廣州：控制理論與應用．1999，12（3）:365－273．TomM．Michell．機器學習[M]．北京：機械工業(yè)出版社，2003．(美）卡倫著．人工智能．黃厚寬，等譯．北京：電子工業(yè)出版社，2004．Goldberg,DavidE．創(chuàng)新的設計:競爭遺傳算法課程[M]，Addison-Wesley,Reading，MA.2002.Schmitt，LotharM，遺傳算法理論[M]，TheoreticalComputerScience(259)，pp。1-61,2001．Schmitt，LotharM，遺傳算法理論(二)[M]，TheoreticalComputerScience(310)，pp.181-231,2004．Vose,MichaelD,簡單遺傳算法：基礎和理論[M].MITPress，Cambridge，MA，1999．PanZJ,KangLS．AnAdaptiveEvolutionaryAlgorithmsforNumericalOptimization．Proc．ofSEAL＇96,Taej