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

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

編碼

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

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

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

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

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

適應(yīng)度函數(shù)

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

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

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

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

b） 合理、一致性

c）計(jì)算量小

d）通用性強(qiáng)。

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

初始群體選取

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

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

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

運(yùn)算過程

遺傳算法的基本運(yùn)算過程如下：

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

（2）個(gè)體評價(jià)：計(jì)算群體P（t）中各個(gè)個(gè)體的適應(yīng)度。

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

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

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

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

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

選擇

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

交叉

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

變異

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

a）實(shí)值變異。

b）二進(jìn)制變異。

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

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

b）對進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異。

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

終止條件

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