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

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

編碼編碼

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

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

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

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

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

適應度函數(shù)

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

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

適應度函數(shù)的設(shè)計主要滿足以下條件：

a）單值、連續(xù)、非負、最大化

b） 合理、一致性

c）計算量小

d）通用性強。

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

初始群體選取

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

a）根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。

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

運算過程

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

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

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

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

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

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

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

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

選擇

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

交叉

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

變異

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

a）實值變異。

b）二進制變異。

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

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

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

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

終止條件

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