遺傳算法（Genetic Algorithm，GA）最早是由美國的 John holland于20世紀70年代提出，該算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。該算法通過數學的方式，利用計算機仿真運算，將問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為復雜的組合優化問題時，相對一些常規的優化算法，通常能夠較快地獲得較好的優化結果。遺傳算法已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域。

遺傳算法的起源可追溯到20世紀60年代初期。1967年，美國密歇根大學J． Holland教授的學生 Bagley在他的博士論文中首次提出了遺傳算法這一術語，并討論了遺傳算法在博弈中的應用，但早期研究缺乏帶有指導性的理論和計算工具的開拓。1975年， J． Holland等提出了對遺傳算法理論研究極為重要的模式理論，出版了專著《自然系統和人工系統的適配》，在書中系統闡述了遺傳算法的基本理論和方法，推動了遺傳算法的發展。20世紀80年代后，遺傳算法進入興盛發展時期，被廣泛應用于自動控制、生產計劃、圖像處理、機器人等研究領域。

編碼編碼

由于遺傳算法不能直接處理問題空間的參數，因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼，也可以稱作（問題的）表示（representation）。

評估編碼策略常采用以下3個規范：

a）完備性（completeness）：問題空間中的所有點（候選解）都能作為GA空間中的點（染色體）表現。

b）健全性（soundness）： GA空間中的染色體能對應所有問題空間中的候選解。

c）非冗余性（nonredundancy）：染色體和候選解一一對應。

適應度函數

進化論中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖后代的能力。遺傳算法的適應度函數也叫評價函數，是用來判斷群體中的個體的優劣程度的指標，它是根據所求問題的目標函數來進行評估的。

遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數來評估個體或解的優劣，并作為以后遺傳操作的依據。由于遺傳算法中，適應度函數要比較排序并在此基礎上計算選擇概率，所以適應度函數的值要取正值。由此可見，在不少場合，將目標函數映射成求最大值形式且函數值非負的適應度函數是必要的。

適應度函數的設計主要滿足以下條件：

a）單值、連續、非負、最大化

b） 合理、一致性

c）計算量小

d）通用性強。

在具體應用中，適應度函數的設計要結合求解問題本身的要求而定。適應度函數設計直接影響到遺傳算法的性能。

初始群體選取

遺傳算法中初始群體中的個體是隨機產生的。一般來講，初始群體的設定可采取如下的策略：

a）根據問題固有知識，設法把握最優解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內設定初始群體。

b）先隨機生成一定數目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數達到了預先確定的規模。

運算過程

遺傳算法的基本運算過程如下：

（1）初始化：設置進化代數計數器t＝0，設置最大進化代數T，隨機生成M個個體作為初始群體P（0）。

（2）個體評價：計算群體P（t）中各個個體的適應度。

（3）選擇運算：將選擇算子作用于群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

（4）交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。

（5）變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P（t）經過選擇、交叉、變異運算之后得到下一代群體P（t＋1）。

（6）終止條件判斷：若t＝T，則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。

遺傳操作包括以下三個基本遺傳算子（genetic operator）：選擇（selection）；交叉（crossover）；變異（mutation）。

選擇

從群體中選擇優勝的個體，淘汰劣質個體的操作叫選擇。選擇算子有時又稱為再生算子（reproduction operator）。選擇的目的是把優化的個體（或解）直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的，常用的選擇算子有以下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法。

交叉

在自然界生物進化過程中起核心作用的是生物遺傳基因的重組（加上變異）。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。

變異

變異算子的基本內容是對群體中的個體串的某些基因座上的基因值作變動。依據個體編碼表示方法的不同，可以有以下的算法：

a）實值變異。

b）二進制變異。

一般來說，變異算子操作的基本步驟如下：

a）對群中所有個體以事先設定的變異概率判斷是否進行變異

b）對進行變異的個體隨機選擇變異位進行變異。

遺傳算法引入變異的目的有兩個：一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交叉算子已接近最優解鄰域時，利用變異算子的這種局部隨機搜索能力可以加速向最優解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現未成熟收斂現象。此時收斂概率應取較大值。

終止條件

當最優個體的適應度達到給定的閾值，或者最優個體的適應度和群體適應度不再上升時，或者迭代次數達到預設的代數時，算法終止。預設的代數一般設置為100－500代。
編輯：lyn