淺談遺傳算法及其部分改進算法

唐文琦 曾干敏 劉澤宇

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

關鍵詞：遺傳算法；模擬退火遺傳算法；多種群遺傳算法

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

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

1 遺傳算法的具體步驟以及優缺點

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

1.1 具體步驟

算法的主要步驟如下：

1）編碼。使用適當的編碼表示解空間中的所有可行解，目前有二進制碼等被廣泛使用的編碼方案。但是對于具體的問題，需要設計特定的編碼方案，例如解決TSP問題時，以所有點的訪問順序作為編碼。

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

3）計算個體適應度。對于具體的問題，通常都有一個目標函數，通過個體的編碼計算出其目標值大小，再根據待優化問題的性質，得到對應的適應度。

4）選擇。隨機挑選個體進行交叉、變異，適應度越大，選中概率越大。

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

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

1.2 遺傳算法優缺點

1.2.1 遺傳算法的優點

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

1.2.2 遺傳算法的缺點

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

發生早熟收斂的原因主要有：

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

2）參數設置不當和每個步驟具體的實現設計得不合適，對于參數和步驟的具體實現沒有科學的標準，只能試探性地給出。

2 遺傳算法的部分改進算法

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

2.2 多種群遺傳算法

鑒于參數和遺傳算法每個步驟具體實現的設置不當導致算法早熟收斂，多種群遺傳算法[4]（Multiple Population Genetic Algorithm）在遺傳算法的基礎上做了如下改進：

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

2）使用移民算子在算法迭代過程中，使種群定期使用最優個體替換掉相鄰種群的最劣個體，實現多種群之間協同進化。

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

3 總結

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

參考文獻：

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

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

[3]常忠東.對模擬退火算法的衰減函數T和MetrOPolis準則的改進[J].內蒙古民族大學學報（自然漢文版），2011，26（4）：408-409.

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

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