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

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