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

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