遺傳算法（Genetic   Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機制）演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975 年首先提出，其主要特點是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自 動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、信號處理、自適應(yīng) 控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計算中的關(guān)鍵技術(shù)之一。  
   
  1.遺傳算法與自然選擇    
   
  達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說。這種學(xué)說認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭。生存斗爭包括種內(nèi)斗爭、種間斗爭以及生物 跟無機環(huán)境之間的斗爭三個方面。在生存斗爭中，具有有利變異的個體容易存活下來，并且有更多的機會將有利變異傳給后代；具有不利變異的個體就容易被淘汰， 產(chǎn)生后代的機會也少的多。因此，凡是在生存斗爭中獲勝的個體都是對環(huán)境適應(yīng)性比較強的。達(dá)爾文把這種在生存斗爭中適者生存，不適者淘汰的過程叫做自然選 擇。它表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。自然界中的多種生物之所以能夠適應(yīng)環(huán)境而得以生存進(jìn)化，是和遺傳和變異生命現(xiàn)象分不開的。正是生物的這 種遺傳特性，使生物界的物種能夠保持相對的穩(wěn)定；而生物的變異特性，使生物個體產(chǎn)生新的性狀，以致于形成新的物種，推動了生物的進(jìn)化和發(fā)展。  
   
  遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存＋檢測”的迭代過程的搜 索算法。遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳 操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容。   作為一種新的全局優(yōu)化搜索算法，遺傳算法以其簡單通用、魯棒性強、適于并行處理以及高效、實用等顯著特點，在各個領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并 逐漸成為重要的智能算法之一。  
   
  2.遺傳算法的基本步驟    
  　  
   
  我們習(xí)慣上把Holland1975年提出的GA稱為傳統(tǒng)的GA。它的主要步驟如下：  
   
  編碼：GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點。  
   
  初始群體的生成：隨機產(chǎn)生N個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體，   N個個體構(gòu)成了一個群體。GA以這N個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。  
   
  適應(yīng)性值評估檢測：適應(yīng)性函數(shù)表明個體或解的優(yōu)劣性。不同的問題，適應(yīng)性函數(shù)的定義方式也不同。  
   
  選擇：選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)性強的個體為下一代貢獻(xiàn)一個或多個后代的概率大。選擇實現(xiàn)了達(dá)爾文的適者生存原則。  
   
  交換：交換操作是遺傳算法中最主要的遺傳操作。通過交換操作可以得到新一代個體，新個體組合了其父輩個體的特性。交換體現(xiàn)了信息交換的思想。  
   
  變異：變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001~0.01之間。變異為新個體的產(chǎn)生提供了機會。  
   
  GA的計算過程為：  
   
  選擇編碼方式  
   
  產(chǎn)生初始群體  
   
  計算初始群體的適應(yīng)性值  
   
  如果不滿足條件   {  
        選擇    
        交換  
        變異  
        計算新一代群體的適應(yīng)性值  
  }  
   
   
  3.遺傳算法的特點    
   
  遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示  
   
  出明顯的優(yōu)勢。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點：  
   
  搜索過程不直接作用在變量上，而是在參數(shù)集進(jìn)行了編碼的個體。此編碼操作，    
  使得遺傳算法可直接對結(jié)構(gòu)對象（集合、序列、矩陣、樹、圖、鏈和表）進(jìn)行操作。  
   
  搜索過程是從一組解迭代到另一組解，采用同時處理群體中多個個體的方法，降    
  低了陷入局部最優(yōu)解的可能性，并易于并行化。  
   
  采用概率的變遷規(guī)則來指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。    
  對搜索空間沒有任何特殊要求（如連通性、凸性等），只利用適應(yīng)性信息，不需要    
  導(dǎo)數(shù)等其它輔助信息，適應(yīng)范圍更廣。  
   
  　  
   
  4.遺傳算法的研究歷史與現(xiàn)狀    
   
  遺傳算法研究的興起是在80年代末和90年代初期，但它的歷史起源可追溯至60年代  
   
  初期。早期的研究大多以對自然系統(tǒng)的計算機模擬為主。如Fraser的模擬研究，他提出了和現(xiàn)在的遺傳算法十分相似的概念和思想。Holland和 DeJong的創(chuàng)造性研究成果改變了早期遺傳算法研究的無目標(biāo)性和理論指導(dǎo)的缺乏。其中，Holland于1975年出版的著名著作<<自然 系統(tǒng)和人工系統(tǒng)的適配>>系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論。這一理論首次確認(rèn) 了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。  
   
  同年，DeJong的重要論文<<遺傳自適應(yīng)系統(tǒng)到的行為分析>>將Holland的模式理論與他的計算實驗結(jié)合起來，并提出了諸如代溝等新的遺傳操作技術(shù)。可以認(rèn)為，DeJong所作的研究工作是遺傳算法發(fā)展過程中的一個里程碑。  
   
  進(jìn)入80年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用領(lǐng)域也不斷擴大。目前遺傳算法所涉及 的主要領(lǐng)域有自動控制、規(guī)劃設(shè)計、組合優(yōu)化、圖象處理、信號處理、人工生命等。可見，遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解拓展到了許多更新。更工程 化的應(yīng)用方面。 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1512648