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

唐文琦 曾干敏 劉澤宇

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

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

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

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

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

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

1.1 具體步驟

算法的主要步驟如下：

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

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

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

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

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

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

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

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

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

1.2.2 遺傳算法的缺點(diǎn)

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

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

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

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

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

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

2.2 多種群遺傳算法

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

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

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

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

3 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

作者簡(jiǎn)介：唐文琦，男，漢族，本科。