引言 ?
傳統的遺傳算法是一種借鑒于生物界自然選擇和進(jìn)化機制發(fā)展起來(lái)的高度并行、隨機、自適應的全局優(yōu)化概率搜索算法。因為優(yōu)化時(shí)不依賴(lài)于梯度，具有很強的魯棒性和全局搜索能力。因此，被廣泛應用于機器學(xué)習、模式識別、數學(xué)規劃等領(lǐng)域。然而，隨著(zhù)遺傳算法的廣泛應用以及研究的深人，其諸多缺陷與不足也暴露出來(lái)，例如，早熟收斂問(wèn)題（下簡(jiǎn)稱(chēng)“早熟”）。
1
“早熟收斂”介紹
1.1
何為“早熟”
早熟性收斂，也叫“早熟”(Prematurity)，是指在遺傳算法早期，在種群中出現了超級個(gè)體，該個(gè)體的適應值大大超過(guò)當前種群的平均個(gè)體適應值。從而使得該個(gè)體很快在種群中占有絕對的比例，種群的多樣性迅速降低，群體進(jìn)化能力基本喪失，從而使得算法較早收斂于局部最優(yōu)解的現象。
1.2
“早熟”現象舉例
具體來(lái)講，當我們在某個(gè)算法上尋優(yōu)求解時(shí)，不可避免地有時(shí)得到的解為局部最優(yōu)解，如圖1所示：
圖1 遺傳算法陷入局部最優(yōu)
此時(shí)，算法就進(jìn)入局部最優(yōu)解，且由于算法的某方面限制，使得算法跳不出局部最優(yōu)解的范圍，這種現象就稱(chēng)作算法早熟。
在使用算法對多維函數進(jìn)行優(yōu)化時(shí)，算法同樣可能會(huì )陷入局部最優(yōu)解，如圖2所示：
圖2 多維優(yōu)化問(wèn)題陷入局部最優(yōu)
1.3
“早熟”現象成因
早熟收斂的發(fā)生主要和下列幾個(gè)方面有關(guān):
? 群體中存在超級個(gè)體
選擇操作中當群體中存在個(gè)別超級個(gè)體時(shí)(該個(gè)體的適應度比其他個(gè)體高得多)，該個(gè)體在選擇算子作用下將會(huì )多次被選中，下一代群體很快被該個(gè)體所控制，從而導致群體停滯不前。
?交叉概率與變異概率的設置
交叉和變異操作發(fā)生的頻度是受交叉概率Pc和變異概率Pm控制的，Pc和Pm的恰當設定涉及全局搜索和局部搜索能力的均衡，進(jìn)化搜索的最終結果對Pc、Pm的取值相當敏感，不同Pc、Pm的取值很可能會(huì )導致不同的計算結果。
? 群體規模的設置
當群體規模較小時(shí)，群體中多樣性程度低，個(gè)體之間競爭性較弱，隨著(zhù)進(jìn)化的進(jìn)行，群體很快趨于單一化，交叉操作產(chǎn)生新個(gè)體的作用漸趨消失，群體的更新只靠變異操作來(lái)維持，群體很快終止進(jìn)化；當群體規模取值較大時(shí)，勢必造成計算量的增加，計算效率受到影響。
?最大迭代次數作為終止條件
遺傳算法常用的終止判斷條件為，當迭代次數達到人為規定的最大遺傳代數時(shí)，則終止進(jìn)化。如迭代次數過(guò)少，進(jìn)化不充分，也會(huì )造成未成熟收斂。
為克服未成熟收斂，許多學(xué)者對算法改進(jìn)進(jìn)行了一些有益的探索，特別對遺傳控制參數的設定，提出了自適應的交叉和變異，并獲得了一些有益的結論。但是遺傳算法的未成熟收斂與上述諸多因素有關(guān)，在應用遺傳算法解決實(shí)際問(wèn)題時(shí)，控制參數如何設定、遺傳算子如何設計往往是根據實(shí)際問(wèn)題試探性地給出的，不恰當的設定會(huì )在很大程度上影響算法的性能。
2
多種群遺傳算法
針對遺傳算法存在的上述問(wèn)題，出現了一種多種群遺傳算法(Multiple Population GA，MPGA）來(lái)取代常規的標準遺傳算法(Standard GA,SGA)
2.1
多種群遺傳算法的改進(jìn)
MPGA在SGA的基礎上主要有以下改進(jìn)：
1.各種群取不同的控制參數
SGA僅靠單個(gè)群體進(jìn)行進(jìn)化，而遺傳算法的結果往往又依賴(lài)于一些重要控制參數，如種群數、交叉概率、變異概率、編碼方式等。MPGA引入多個(gè)種群同時(shí)進(jìn)行優(yōu)化搜索，對不同的種群賦予不同的控制參數，從而兼顧算法的全局搜索和局部搜索。
2.移民算子溝通多種群進(jìn)行協(xié)同進(jìn)化
各種群相對獨立，種群交互通過(guò)移民算子聯(lián)系。移民算子將各種群的最優(yōu)個(gè)體定期引入其它種群中，實(shí)現種群之間的協(xié)同進(jìn)化，最終獲取最優(yōu)解。
3.人工選擇算子輔助算法終止
通過(guò)人工選擇算子保存各種群每個(gè)進(jìn)化代中的最優(yōu)個(gè)體，并作為判斷算法收斂的依據。
多種群遺傳算法的流程圖如圖3所示：
圖3 多種群遺傳算法流程圖
下面對上述改進(jìn)展開(kāi)詳細說(shuō)明與分析。
2.2
各種群取不同的控制參數
交叉概率Pc和變異概率Pm的取值決定了算法全局搜索和局部搜索能力的均衡。在SGA中，交叉算子是產(chǎn)生個(gè)體的主要算子，它決定了遺傳算法全局搜索的能力；而變異算子只是產(chǎn)生新個(gè)體的輔助算子，它決定了遺傳算法的局部搜索能力。許多學(xué)者建議選擇較大的Pm(0.7~0.9)和較小的Pm(0.001~0.05)。但是Pc和Pm的取值方式還是有無(wú)數種，對于不同的選擇，優(yōu)化結果差異也是很大的。
MPGA彌補了SGA的這一不足，通過(guò)多個(gè)設有不同控制參數的種群協(xié)同進(jìn)化，同時(shí)兼顧了算法的全局搜索和局部搜索。使得對遺傳控制參數的敏感性降低，能夠有效地克服未成熟收斂的現象。
2.3
移民算子
各種群是相對獨立的，相互之間通過(guò)移民算子聯(lián)系。移民算子將各種群在進(jìn)化過(guò)程中出現的最優(yōu)個(gè)體定期地(每隔一定的進(jìn)化代數)引人其他的種群中，實(shí)現種群之間的信息交換。
具體的操作規則是將目標種群中的最差個(gè)體用源種群的最優(yōu)個(gè)體代替。移民算子在MPGA中至關(guān)重要，如果沒(méi)有移民算子，各種群之間失去了聯(lián)系，MPGA將等同于用不同的控制參數進(jìn)行多次SGA計算，從而失去了MPGA的特色。
2.4
人工選擇算子
精華種群和其它種群不同，每一代進(jìn)化后，通過(guò)人工選擇算子選出種群的最優(yōu)個(gè)體放入精華種群，并且精華種群不進(jìn)行選擇、交叉、變異等操作，保證進(jìn)化過(guò)程中最優(yōu)個(gè)體不被破壞和丟失。
精華種群的最優(yōu)個(gè)體最少保持代數將作為算法終止判據，該判據充分利用了遺傳算法在進(jìn)化中的知識積累，較之最大遺傳代數更為合理。
3
總結
??多種群遺傳算法就相當于多個(gè)標準遺傳算法的結合體，只不過(guò)需要通過(guò)移民算子將這些個(gè)標準的遺傳算法聯(lián)系起來(lái)。
??如果沒(méi)有移民算子，各種群之間將失去聯(lián)系變成獨立進(jìn)化。MPGA將等同于用不同控制參數進(jìn)行多次SGA計算，從而失去了MPGA的特色。
??然后通過(guò)人工選擇算子保存各種群每個(gè)進(jìn)化代中的最優(yōu)個(gè)體，最后以最優(yōu)個(gè)體最少保持代數作為終止判據。
參考資料
[1].愛(ài)聽(tīng)雨的犬貓.多種群遺傳算法優(yōu)化算法[EB/OL].(2022-8-26)[2023-3-27].
https://blog.csdn.net/m0_56306305/article/details/126437357
[2].M.scoe.遺傳算法系列 | 多種群遺傳算法(matlab)[EB/OL].(2022-7-21)[2023-3-27].
https://blog.csdn.net/sfejojno/article/details/125918337
[3].早熟收斂_百度百科(baidu.com)[EB/OL].(2022-8-5)[2023-3-27].
聯(lián)系客服
