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

1、    淺談遺傳算法及其部分改進算法    唐文琦 曾干敏 劉澤宇摘 要：遺傳算法廣泛應(yīng)用于函數(shù)尋優(yōu)、組合尋優(yōu)等方面，同時算法設(shè)計靈活易實現(xiàn)，但具有易早熟收斂的缺點。本文簡單闡述遺傳算法工作原理，分析其易早熟收斂的原因，最后介紹了兩種改進算法多種群遺傳算法、模擬退火遺傳算法，并分析兩種算法在避免早熟收斂上的原理及效果。關(guān)鍵詞：遺傳算法；模擬退火遺傳算法；多種群遺傳算法遺傳算法（genetic algorithm）是一種全局優(yōu)化概率算法，其借鑒進化論的自然選擇機制和染色體的交叉變異機制，最終保留對于當(dāng)前環(huán)境適應(yīng)能力最強的個體或者群體。對于具體的問題，通過編

2、碼表示解空間中的解；使用適應(yīng)度函數(shù)衡量解的優(yōu)劣程度；交叉和變異引入隨機因素，避免尋優(yōu)過程陷入局部最優(yōu)；在每次進化的過程中，淘汰部分適應(yīng)度較弱的個體，最終尋得全局最優(yōu)。1 遺傳算法的具體步驟以及優(yōu)缺點在遺傳算法中，個體（染色體）為一段編碼，代表解空間中的一個可行解；基因表示個體上的編碼片段；群體為個體集合；適應(yīng)度為個體對應(yīng)解的優(yōu)劣程度。1.1 具體步驟算法的主要步驟如下：1）編碼。使用適當(dāng)?shù)木幋a表示解空間中的所有可行解，目前有二進制碼等被廣泛使用的編碼方案。但是對于具體的問題，需要設(shè)計特定的編碼方案，例如解決tsp問題時，以所有點的訪問順序作為編碼。2）初始化染色體種群。隨機生成個體上的編碼信息

3、，其所對應(yīng)的解應(yīng)該是可行的，遺傳算法從這些初始解出發(fā)迭代進化。3）計算個體適應(yīng)度。對于具體的問題，通常都有一個目標(biāo)函數(shù)，通過個體的編碼計算出其目標(biāo)值大小，再根據(jù)待優(yōu)化問題的性質(zhì)，得到對應(yīng)的適應(yīng)度。4）選擇。隨機挑選個體進行交叉、變異，適應(yīng)度越大，選中概率越大。5）交叉、變異。模擬生物細(xì)胞核內(nèi)染色體間交換基因片段和染色體上基因突變的過程。交叉和變異均是隨機發(fā)生的，其中變異發(fā)生的概率很低。交叉讓個體間交換基因片段，生成新的個體；變異使得個體上某個編碼片段發(fā)生突變，生成新的個體。6）更新種群。模擬自然選擇機制，一般是基于適應(yīng)度大小，保留較優(yōu)的部分個體，從而使得種群進化。1.2 遺傳算法優(yōu)缺點1.2.

4、1 遺傳算法的優(yōu)點遺傳算法尋優(yōu)過程不依賴于梯度，可以通過交叉、變異跳出局部最優(yōu)，具有較強的全局搜索能力；具有很強的靈活性，各個步驟的具體實現(xiàn)可以高度自定義；可以作為其他算法的外部框架來提升改進其他算法。1.2.2 遺傳算法的缺點早熟收斂1是遺傳算法的最大缺點，其表現(xiàn)為群體中所有個體之間相似度很高，進而導(dǎo)致進化緩慢甚至停止。發(fā)生早熟收斂的原因主要有：1）群體中出現(xiàn)部分個體的適應(yīng)度比其余個體高很多，在每次迭代過程中，這些個體極易被選中，經(jīng)過多次交叉、變異后，群體中所有個體彼此相似，相互之間失去了競爭性，導(dǎo)致群體的進化過程停滯不前，無法尋得全局最優(yōu)解。2）參數(shù)設(shè)置不當(dāng)和每個步驟具體的實現(xiàn)設(shè)計得不合適

5、，對于參數(shù)和步驟的具體實現(xiàn)沒有科學(xué)的標(biāo)準(zhǔn)，只能試探性地給出。2 遺傳算法的部分改進算法對于遺傳算法的易早熟收斂，這里提出兩個改進算法多種群遺傳算法、模擬退火遺傳算法。2.2 多種群遺傳算法鑒于參數(shù)和遺傳算法每個步驟具體實現(xiàn)的設(shè)置不當(dāng)導(dǎo)致算法早熟收斂，多種群遺傳算法4（multiple population genetic algorithm）在遺傳算法的基礎(chǔ)上做了如下改進：1）引入多個種群并行尋優(yōu)，每個種群具有不同的算法參數(shù)（影響著全局、局部尋優(yōu)能力）。2）使用移民算子在算法迭代過程中，使種群定期使用最優(yōu)個體替換掉相鄰種群的最劣個體，實現(xiàn)多種群之間協(xié)同進化。3）在每次迭代過程中，使用人工選擇算

6、子選出各種群最優(yōu)個體，組成精英種群，作為判斷算法迭代結(jié)束的依據(jù)，一般迭代結(jié)束條件為精英種群中的最優(yōu)個體保持指定代數(shù)以上。精英種群不發(fā)生交叉、變異，只起保存作用。3 總結(jié)遺傳算法尋優(yōu)不依賴于梯度，全局尋優(yōu)能力較強，但是易早熟收斂。模擬退火遺傳算法引入metropolis接受準(zhǔn)則，對于較差的解不完全拋棄，以一定的概率保留，有效的抑制了早熟收斂。多種群遺傳算法引入具有不同參數(shù)的種群協(xié)同搜索，有效地避免了參數(shù)設(shè)置不當(dāng)造成的搜索效果不佳。參考文獻：1蔣騰旭，謝楓.遺傳算法中防止早熟收斂的幾種措施j.計算機與現(xiàn)代化，2006（12）：54-56.2王雪梅，王義和.模擬退火算法與遺傳算法的結(jié)合j.計算機學(xué)報，1997（4）：381-384.3常忠東.對模擬退火算法的衰減函數(shù)t和metropolis準(zhǔn)則的改進j