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