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