淺談遺傳算法及其部分改進(jìn)算法

唐文琦 曾干敏 劉澤宇

摘 要：遺傳算法廣泛應(yīng)用于函數(shù)尋優(yōu)、組合尋優(yōu)等方面，同時算法設(shè)計靈活易實現(xiàn)，但具有易早熟收斂的缺點。本文簡單闡述遺傳算法工作原理，分析其易早熟收斂的原因，最后介紹了兩種改進(jìn)算法——多種群遺傳算法、模擬退火遺傳算法，并分析兩種算法在避免早熟收斂上的原理及效果。

關(guān)鍵詞：遺傳算法；模擬退火遺傳算法；多種群遺傳算法

遺傳算法（Genetic Algorithm）是一種全局優(yōu)化概率算法，其借鑒進(jìn)化論的自然選擇機制和染色體的交叉變異機制，最終保留對于當(dāng)前環(huán)境適應(yīng)能力最強的個體或者群體。

對于具體的問題，通過編碼表示解空間中的解；使用適應(yīng)度函數(shù)衡量解的優(yōu)劣程度；交叉和變異引入隨機因素，避免尋優(yōu)過程陷入局部最優(yōu)；在每次進(jìn)化的過程中，淘汰部分適應(yīng)度較弱的個體，最終尋得全局最優(yōu)。

1 遺傳算法的具體步驟以及優(yōu)缺點

在遺傳算法中，個體（染色體）為一段編碼，代表解空間中的一個可行解；基因表示個體上的編碼片段；群體為個體集合；適應(yīng)度為個體對應(yīng)解的優(yōu)劣程度。

1.1 具體步驟

算法的主要步驟如下：

1）編碼。使用適當(dāng)?shù)木幋a表示解空間中的所有可行解，目前有二進(jìn)制碼等被廣泛使用的編碼方案。但是對于具體的問題，需要設(shè)計特定的編碼方案，例如解決TSP問題時，以所有點的訪問順序作為編碼。

2）初始化染色體種群。隨機生成個體上的編碼信息，其所對應(yīng)的解應(yīng)該是可行的，遺傳算法從這些初始解出發(fā)迭代進(jìn)化。

3）計算個體適應(yīng)度。對于具體的問題，通常都有一個目標(biāo)函數(shù)，通過個體的編碼計算出其目標(biāo)值大小，再根據(jù)待優(yōu)化問題的性質(zhì)，得到對應(yīng)的適應(yīng)度。

4）選擇。隨機挑選個體進(jìn)行交叉、變異，適應(yīng)度越大，選中概率越大。

5）交叉、變異。模擬生物細(xì)胞核內(nèi)染色體間交換基因片段和染色體上基因突變的過程。交叉和變異均是隨機發(fā)生的，其中變異發(fā)生的概率很低。交叉讓個體間交換基因片段，生成新的個體；變異使得個體上某個編碼片段發(fā)生突變，生成新的個體。

6）更新種群。模擬自然選擇機制，一般是基于適應(yīng)度大小，保留較優(yōu)的部分個體，從而使得種群進(jìn)化。

1.2 遺傳算法優(yōu)缺點

1.2.1 遺傳算法的優(yōu)點

遺傳算法尋優(yōu)過程不依賴于梯度，可以通過交叉、變異跳出局部最優(yōu)，具有較強的全局搜索能力；具有很強的靈活性，各個步驟的具體實現(xiàn)可以高度自定義；可以作為其他算法的外部框架來提升改進(jìn)其他算法。

1.2.2 遺傳算法的缺點

早熟收斂[1]是遺傳算法的最大缺點，其表現(xiàn)為群體中所有個體之間相似度很高，進(jìn)而導(dǎo)致進(jìn)化緩慢甚至停止。

發(fā)生早熟收斂的原因主要有：

1）群體中出現(xiàn)部分個體的適應(yīng)度比其余個體高很多，在每次迭代過程中，這些個體極易被選中，經(jīng)過多次交叉、變異后，群體中所有個體彼此相似，相互之間失去了競爭性，導(dǎo)致群體的進(jìn)化過程停滯不前，無法尋得全局最優(yōu)解。

2）參數(shù)設(shè)置不當(dāng)和每個步驟具體的實現(xiàn)設(shè)計得不合適，對于參數(shù)和步驟的具體實現(xiàn)沒有科學(xué)的標(biāo)準(zhǔn)，只能試探性地給出。

2 遺傳算法的部分改進(jìn)算法

對于遺傳算法的易早熟收斂，這里提出兩個改進(jìn)算法——多種群遺傳算法、模擬退火遺傳算法。

2.2 多種群遺傳算法

鑒于參數(shù)和遺傳算法每個步驟具體實現(xiàn)的設(shè)置不當(dāng)導(dǎo)致算法早熟收斂，多種群遺傳算法[4]（Multiple Population Genetic Algorithm）在遺傳算法的基礎(chǔ)上做了如下改進(jìn)：

1）引入多個種群并行尋優(yōu)，每個種群具有不同的算法參數(shù)（影響著全局、局部尋優(yōu)能力）。

2）使用移民算子在算法迭代過程中，使種群定期使用最優(yōu)個體替換掉相鄰種群的最劣個體，實現(xiàn)多種群之間協(xié)同進(jìn)化。

3）在每次迭代過程中，使用人工選擇算子選出各種群最優(yōu)個體，組成精英種群，作為判斷算法迭代結(jié)束的依據(jù)，一般迭代結(jié)束條件為精英種群中的最優(yōu)個體保持指定代數(shù)以上。精英種群不發(fā)生交叉、變異，只起保存作用。

3 總結(jié)

遺傳算法尋優(yōu)不依賴于梯度，全局尋優(yōu)能力較強，但是易早熟收斂。模擬退火遺傳算法引入Metropolis接受準(zhǔn)則，對于較差的解不完全拋棄，以一定的概率保留，有效的抑制了早熟收斂。多種群遺傳算法引入具有不同參數(shù)的種群協(xié)同搜索，有效地避免了參數(shù)設(shè)置不當(dāng)造成的搜索效果不佳。

參考文獻(xiàn)：

[1]蔣騰旭，謝楓.遺傳算法中防止早熟收斂的幾種措施[J].計算機與現(xiàn)代化，2006（12）：54-56.

[2]王雪梅，王義和.模擬退火算法與遺傳算法的結(jié)合[J].計算機學(xué)報，1997（4）：381-384.

[3]常忠東.對模擬退火算法的衰減函數(shù)T和MetrOPolis準(zhǔn)則的改進(jìn)[J].內(nèi)蒙古民族大學(xué)學(xué)報（自然漢文版），2011，26（4）：408-409.

[4]葉在福，單淵達(dá).基于多種群遺傳算法的輸電系統(tǒng)擴展規(guī)劃[J].電力系統(tǒng)自動化，2000，24（5）.

作者簡介：唐文琦，男，漢族，本科。