遺傳算法綜述

《遺傳算法綜述》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、遺傳算法(綜述)一、什么是GA遺傳算法(GeneticAlgorithms簡稱GA)是計算數(shù)學中用于解決最優(yōu)化的搜索算法，是進化算法的一種。進化算法最初是借鑒了進化生物學中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。維基百科。二、GA的起源及發(fā)展50年代末60年代初,生物學家A．S．Fraser和H．J．Bremermann等人試圖通過計算的方法來模擬生物界“遺傳與選擇”的進化過程,這便是GA的雛形。1967年Bagley在其博士論文中首次提出了“遺傳算法”這一術語。到60年代中

2、期，美國Michigan大學的JohnHol－land在A．S．Fraser和H．J．Bremermann等人工作的基礎上提出了位串編碼技術。這種編碼既適于變異操作，又適于交配（即雜交）操作，并且強調(diào)將交配作為主要的遺傳操作。隨后，Holland將該算法用于自然和人工系統(tǒng)的自適應行為的研究中，并于1975年出版了其開創(chuàng)性著作“AdaptationinNaturalandArtificialSystems”．之后，Holland等人將該算法加以推廣，應用到優(yōu)化及機器學習等問題中，并正式定名為遺傳算法。遺傳

3、算法的通用編碼技術和簡單有效的遺傳操作為其廣泛、成功的應用奠定了基礎。http://blog.csdn.net/neupioneer/archive/2004/09/24/115989.aspx20世紀80年代中期以來是遺傳算法和進化計算的蓬勃發(fā)展期,多個相關國際會議在世界各地定期召開。1985年,在美國卡耐基·梅隆大學召開第一屆國際遺傳算法會議ICGA’85,以后每兩年舉行一次。1989年Goldberg所著的《搜索、優(yōu)化和機器學習中的遺傳算法》對遺傳算法理論及其多領域的應用展開了較為全面的分析和例證

4、。1992年,Michalewicz出版了《演化程序———遺傳算法與數(shù)據(jù)編碼的結(jié)合》,推動了遺傳算法應用于最優(yōu)化問題。1997年5月,IEEE的TransactionsonEvolutionaryComputation創(chuàng)刊。我國對于GA的研究起步較晚,不過從20世紀90年代以來一直處于不斷上升中。一、遺傳算法理論遺傳算法的研究主要包括三個領域：遺傳算法的理論與技術；用遺傳算法進行優(yōu)化；用遺傳算法進行分類系統(tǒng)的機器學習。其中，遺傳算法的理論與技術研究主要包括編碼、交叉運算、變異運算、選擇運算以及適應度評價

5、等問題。1.理論基礎遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們

6、往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)

7、解。百度百科。Holland的遺傳算法常被稱為簡單遺傳算法（SGA），其操作對象是一群二進制串（稱為染色體、個體），即種群（population）。在此，每個染色體都對應問題的一個解。從初始種群出發(fā)，采用基于適應值比例的選擇策略在當前種群中選擇個體，使用雜交和變異來產(chǎn)生下一代種群。如此一代代演化下去，直到滿足期望的終止條件。需要指出的是，目前的遺傳算法已不再局限于二進制編碼。Z．Michalewicz將不同的編碼策略（即不同的數(shù)據(jù)結(jié)構(gòu)）與遺傳算法的結(jié)合稱為演化程序（EvolutionProgram）。遺

8、傳算法的基礎理論主要以收斂性分析為主,即群體收斂到優(yōu)化問題的全局最優(yōu)解的概率。從整體上講,可以分為基于隨機過程的收斂性研究和基于模式理論的收斂性分析。1)隨機模型理論對于有限的編碼空間和有限的群體,遺傳算法的搜索過程可以表示為離散時間的馬爾可夫鏈模型,從而可以采用已有的隨機過程理論進行嚴密分析:①RudolphRudolphG.ConvergencePropertiesofCaucricalGGeneticAlgorithems[j].IE