遺傳算法(Genetic Algorithms)，也有人把它叫作進化算法(Evolutionary Algorithms)，是基于生物進化的“物競天擇，適者生存”理論發(fā)展起來的一種應(yīng)用廣泛且高效隨機搜索與優(yōu)化并舉的智能算法，其主要特點是群體搜索策略和群體中個體之間的信息交換，不依賴于問題的梯度信息。遺傳算法最初被研究的出發(fā)點不是為專門解決最優(yōu)化問題而設(shè)計的，它與進化策略、進化規(guī)劃共同構(gòu)成了遺傳算法的主要框架，都是為當(dāng)時人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是智能計算中最廣為人知的一種算法。
遺傳算法就是模擬自然界進化論的基本思想，可以很好地用于優(yōu)化問題，若把它看作對自然過程高度理想化的模擬，更能顯出它本身的優(yōu)雅與應(yīng)用的重要。該算法以一個群體中的所有個體為對象，并利用隨機化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進行高效搜索。其中，選擇、雜交和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定五要素組成了遺傳算法的核心內(nèi)容。作為一種新的全局優(yōu)化搜索算法，遺傳算法以其簡單通用、健壯性強、適于并行處理以及高效、實用等顯著特點，在各個領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并逐漸成為重要的智能算法之一。
近幾年來，遺傳算法主要在復(fù)雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應(yīng)用等方面，取得了一些令人信服的結(jié)果，所以引起更多人的關(guān)注。
要想進一步的了解遺傳算法，當(dāng)然要先了解遺傳、進化及其有關(guān)的一些概念和知識，下面就對其進行一些簡單介紹。作為遺傳算法生物背景的介紹，了解下面的一些概念及內(nèi)容也就夠了。
個體：組成種群的單個生物；
種群：生物進化以群體的形式進行，這樣的一個群體稱為種群；
基因：DNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也叫遺傳因子；

基因DNA、RNA片段(摘自互聯(lián)網(wǎng))

染色體：是生物細胞中含有的一種微小的絲狀物，是遺傳物質(zhì)的主要載體，由多個遺傳基因組成；
遺傳：新個體會遺傳父母雙方各自一部分的基因，承現(xiàn)出親子之間以及子代個體之間性狀相似性，表明性狀可以從親代傳遞給子代；
變異：親代和子代之間、子代和子代的不同個體之間總會存在一些差異，這種現(xiàn)象稱為變異；變異是隨機發(fā)生的，變異的選擇和積累是生命多樣性的根源；
進化：生物在其延續(xù)生命的過程中，逐漸適應(yīng)其生存環(huán)境使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化；生物的進化是以種群的形式進行的；
生存競爭，適者生存：生物的繁殖過程，會發(fā)生基因交叉、基因突變，適應(yīng)度低的個體會被逐步淘汰，而適應(yīng)度高的個體會越來越多；這樣經(jīng)過多代的自然選擇后，保存下來的都是適應(yīng)度很高的個體，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那些個體。
遺傳算法是解決搜索問題的一種通用算法，各種各樣、類型不同的問題都可以使用。遺傳算法的共同特征有：？① 首先組成一組候選解；？② 依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度；？③ 根據(jù)適應(yīng)度保留某些優(yōu)良候選解，放棄其中欠佳的部分候選解；？④ 對保留的候選解進行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起，如基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。
除上述共同特征外，遺傳算法還具有以下幾方面的特點：
(1) 遺傳算法從問題解的串集中開始搜索，而不是從單個解開始，這是遺傳算法與傳統(tǒng)優(yōu)化算法的最大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解，容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。
(2) 許多傳統(tǒng)搜索算法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。
(3) 遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)、可微等的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應(yīng)用范圍得到很大擴展。
(4) 遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。
(5) 具有自組織、自適應(yīng)和自學(xué)習(xí)等特性。遺傳算法利用進化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。
遺傳算法以一個群體中的所有個體為對象，利用隨機化技術(shù)對編碼參數(shù)空間進行高效搜索，把選擇、雜交和變異等遺傳現(xiàn)象構(gòu)成遺傳操作。作為一種全局優(yōu)化搜索算法，遺傳算法不考慮函數(shù)本身是否連續(xù)、是否可微等性質(zhì)，以其簡單通用、健壯性強和高效、實用、隱含并行性、容易找到“全局最優(yōu)解”等顯著特點，在許多領(lǐng)域得到成功應(yīng)用，成為一種重要的智能算法。
上面的描述是簡單的遺傳算法模型，可由此給出下面的遺傳算法流程圖，再加延伸，可以在這一基本型上進行改進和發(fā)展，形成諸多不同類別的遺傳算法，使其在科學(xué)和工程領(lǐng)域得到更廣泛的應(yīng)用。

遺傳算法流程圖

上面遺傳算法流程圖中有六個重要的環(huán)節(jié)：
（1）編碼和初始群體的生成：遺傳算法在進行搜索之前先將解空間的解數(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)成了一個群體。遺傳算法以這N個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。當(dāng)然，初始群體應(yīng)該選取適當(dāng)，如果選取的過小則雜交優(yōu)勢不明顯，算法性能很差，群體選取太大則計算量會過大。
（2）檢查算法收斂準則是否滿足，控制算法是否結(jié)束，也可以采用判斷與最優(yōu)解的適配度或者選定一個迭代次數(shù)來結(jié)束計算。
（3）適應(yīng)度評估選擇和檢測：適應(yīng)性函數(shù)表明個體或解的優(yōu)劣性，在程序的開始也應(yīng)該評價適應(yīng)性，以便和以后的做比較。不同的問題，適應(yīng)性函數(shù)的定義方式也不同。根據(jù)適應(yīng)性的好壞，進行選擇。選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進行選擇的原則是適應(yīng)性強的個體為下一代貢獻一個或多個后代的概率大。選擇實現(xiàn)了達爾文的適者生存原則。
（4）選擇:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。
（5）雜交：按照雜交概率進行雜交。雜交操作是遺傳算法中最主要的遺傳操作。通過雜交操作可以得到新一代個體，新個體組合了其父輩個體的特性。雜交體現(xiàn)了信息交換的思想。
可以選定一個點對染色體串進行互換，插入，逆序等雜交，也可以隨機選取幾個點雜交。雜交概率如果太大，種群更新快，但是高適應(yīng)性的個體很容易被淹沒，概率小了搜索會停滯。
（6）變異：按照變異概率進行變異。變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個串的值。同生物界一樣，遺傳算法中變異發(fā)生的概率很低，但為新個體的產(chǎn)生提供了機會。
變異可以防止有效基因的缺損造成的進化停滯。比較低的變異概率就已經(jīng)可以讓基因不斷變更，太大了會陷入隨機搜索。不難想象一下，生物界每一代都和上一代差距很大，會出現(xiàn)是怎樣一種可怕的情形。
就像自然界的變異適和任何物種一樣，對變量進行了編碼的遺傳算法沒有考慮函數(shù)本身是否可導(dǎo)，是否連續(xù)等性質(zhì)，所以適用性很強；并且，它開始就對一個種群進行操作，隱含了并行性，也容易找到“全局最優(yōu)解”。
由上面遺傳算法流程圖不難看出，遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，計算時不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，不依賴于問題的具體領(lǐng)域，對問題的種類有很強的穩(wěn)健性，可廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域。
（1）函數(shù)優(yōu)化：函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價的常用算例，特別是對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果；（2）組合優(yōu)化：隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、圖形劃分問題等各種具有NP難度的問題中得到成功的應(yīng)用；（3）生產(chǎn)調(diào)度問題：車間調(diào)度問題是一個典型的NP問題,從最初的傳統(tǒng)車間調(diào)度問題到柔性作業(yè)車間調(diào)度問題，遺傳算法都有優(yōu)異的結(jié)果顯示，在很多算例中都得到了最優(yōu)解或近優(yōu)解；（4）自動控制；（5）？機器人學(xué)；（6）？圖像處理；（7）人工生命；（8）遺傳編程；（9）機器學(xué)習(xí)；（10）數(shù)據(jù)挖掘等。
隨著應(yīng)用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：（1）基于遺傳算法機器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的機器學(xué)習(xí)算法。這一新的學(xué)習(xí)機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。（2）遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀中新的智能計算技術(shù)將具有重要的意義。（3）并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。（4）遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，（5）遺傳算法和進化規(guī)劃以及進化策略等進化計算理論日益結(jié)合。它們幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能算法，即同遺傳算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點。
進入二十一世紀，遺傳算法迎來了興盛發(fā)展時期，無論是數(shù)學(xué)理論研究、計算機硬件研發(fā)還是應(yīng)用研究都成了十分熱門的課題，尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應(yīng)用方面，同樣也會取得更多新的突破，使得遺傳算法的研究更上一層樓。