倪水平，戚海濤，李慧芳

（河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454000）

0 概述

進(jìn)化算法作為計(jì)算機(jī)科學(xué)與生物進(jìn)化規(guī)律結(jié)合發(fā)展形成的一類啟發(fā)式搜索算法，克服了傳統(tǒng)優(yōu)化算法存在的全局尋優(yōu)能力差、解的質(zhì)量依賴初始值等缺陷，對(duì)求解復(fù)雜問(wèn)題表現(xiàn)出較強(qiáng)的魯棒性［1］。標(biāo)準(zhǔn)遺傳算法（Standard Genetic Algorithm，SGA）［2］作為進(jìn)化算法的代表之一，廣泛應(yīng)用于圖像處理［3］、組合優(yōu)化［4］、函數(shù)優(yōu)化［5］、車間調(diào)度［6］等領(lǐng)域。然而，SGA 存在收斂速度慢、易早熟等問(wèn)題［7-9］。

為克服SGA 存在的早熟收斂問(wèn)題，研究者提出自適應(yīng)遺傳算法［10］、免疫遺傳算法［11］、小生境遺傳算法［12］、基于結(jié)構(gòu)相似度的遺傳算法［13］等改進(jìn)算法，并進(jìn)行實(shí)際應(yīng)用。但SGA 的這一缺陷與諸多因素有關(guān)，并且其控制參數(shù)的設(shè)定［14］和遺傳算子的設(shè)計(jì)［15］應(yīng)根據(jù)實(shí)際問(wèn)題試探性地進(jìn)行。文獻(xiàn)［16］在SGA 的基礎(chǔ)上提出了多種群遺傳算法（Multiple Population Genetic Algorithm，MPGA）。MPGA 引入了多種群的概念，通過(guò)為不同種群賦予不同控制參數(shù)的方式，提高了SGA 控制參數(shù)的靈活性，同時(shí)，還定義了移民算子和人工選擇算子，用于加強(qiáng)各種群之間的聯(lián)系，實(shí)現(xiàn)了多種群協(xié)同進(jìn)化，但該算法的全局尋優(yōu)能力存在進(jìn)一步提升的空間［17］。

文獻(xiàn)［18］針對(duì)早期進(jìn)化算法存在的問(wèn)題提出了思維進(jìn)化算法（Mind Evolution Algorithm，MEA）。MEA 在結(jié)構(gòu)上保留了進(jìn)化算法的并行性，其定義的趨同操作和異化操作分別用于局部搜索和全局探測(cè)，兩者相互協(xié)調(diào)并保持一定的獨(dú)立性。雖然MEA具有靈活、高效的搜索框架，但其執(zhí)行過(guò)程存在重復(fù)搜索、局部尋優(yōu)能力弱、異化過(guò)程生成的臨時(shí)子群體具有隨機(jī)性等缺陷。文獻(xiàn)［19-20］分別提出了基于禁忌搜索思想和使用小生境技術(shù)改進(jìn)的MEA，解決了MEA 重復(fù)搜索的問(wèn)題。此外，文獻(xiàn)［21］使用粒子群算法提高了MEA 的局部尋優(yōu)能力。

本文提出一種MPGA 與MEA 的混合算法，將MPGA 的尋優(yōu)機(jī)制和遺傳操作融入MEA 的搜索框架，以期在保留MPGA 優(yōu)點(diǎn)的基礎(chǔ)上提升MEA 局部搜索精度和全局尋優(yōu)能力。

1 思維進(jìn)化算法與多種群遺傳算法

1.1 思維進(jìn)化算法

MEA 是對(duì)人類思維進(jìn)化過(guò)程的模擬，其中包含的趨同操作和異化操作使得該算法具有“記憶”和“正向進(jìn)化”的能力。MEA 中趨同操作、異化操作和成熟子群體的定義分別如下：

定義1子群體范圍內(nèi)的個(gè)體為成為勝者而進(jìn)行競(jìng)爭(zhēng)的過(guò)程稱為趨同。

定義2各子群體在解空間范圍內(nèi)為成為勝者而相互競(jìng)爭(zhēng)并進(jìn)行不斷地探索的過(guò)程稱為異化。

定義3當(dāng)一個(gè)子群體在趨同過(guò)程中不再產(chǎn)生新的勝者時(shí)，該子群體稱為成熟子群體，其趨同過(guò)程也隨之結(jié)束。

MEA 的尋優(yōu)流程如圖1 所示。

圖1 MEA 尋優(yōu)過(guò)程Fig.1 Optimization process of MEA

MEA 在尋優(yōu)過(guò)程中，把全部解空間看作一個(gè)群體，再把群體劃分為若干個(gè)子群體，每個(gè)子群體包含對(duì)應(yīng)局部區(qū)域的若干個(gè)體。適應(yīng)度得分高的子群體會(huì)作為優(yōu)勝子群體，用于記錄全局競(jìng)爭(zhēng)中優(yōu)勝者的信息；得分低的子群體則作為臨時(shí)子群體，用于記錄并輔助完成全局競(jìng)爭(zhēng)的過(guò)程。

趨同操作負(fù)責(zé)各子群體內(nèi)的局部搜索，該操作的關(guān)鍵步驟是搜尋局部最優(yōu)個(gè)體，并在其臨近區(qū)域隨機(jī)生成若干新的成員繼續(xù)參與搜索，這種尋優(yōu)方式使得MEA 的搜索精度較低。待子群體成熟后，MEA 執(zhí)行異化操作，通過(guò)查找全局公告板記錄的信息釋放得分低的子群體，并使在解空間隨機(jī)生成新的臨時(shí)子群體繼續(xù)參與競(jìng)爭(zhēng)，保證最優(yōu)解正向進(jìn)化，這一過(guò)程決定著MEA 的全局尋優(yōu)能力。如此反復(fù)迭代，實(shí)現(xiàn)全局尋優(yōu)。

1.2 標(biāo)準(zhǔn)遺傳操作

遺傳操作是SGA 的核心，包括選擇、交叉和變異。3 種遺傳操作的實(shí)現(xiàn)過(guò)程如下：

1）選擇操作

從當(dāng)代群體中以一定的概率選擇個(gè)體作為父輩，并繁衍下一代。個(gè)體被選中的概率與適應(yīng)度值成正相關(guān)，選擇操作為后代的質(zhì)量提供了保障。

GA 常用的選擇操作有錦標(biāo)賽法和輪盤(pán)賭法，本文選用基于適應(yīng)度比例的輪盤(pán)賭法。在該選擇策略下，選中個(gè)體i的概率pi的計(jì)算公式如式（1）所示：

其中：N為種群中的個(gè)體數(shù)目；Fi為個(gè)體i的適應(yīng)度得分。

2）交叉操作

對(duì)挑選的2 個(gè)個(gè)體以一定的概率交換彼此的部分染色體，生成保留父輩特性的新個(gè)體。第l個(gè)染色體xl和第m個(gè)染色體xm在j位的交叉操作如式（2）所示：

其中：b是［0，1］之間的隨機(jī)數(shù)。交叉算子是產(chǎn)生新個(gè)體的主要算子，取較大的交叉概率值有助于提升算法的全局尋優(yōu)能力。

3）變異操作

對(duì)種群中的個(gè)體以一定的概率改變其一個(gè)或多個(gè)基因座上的基因值。第i個(gè)個(gè)體的第j個(gè)基因xij執(zhí)行變異操作如式（3）所示：

其中：xmax和xmin分別為基因xij的上下界；r為［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)。f(g)的計(jì)算公式如式（4）所示：

其中：g為當(dāng)前迭代次數(shù)；r2是一個(gè)隨機(jī)數(shù)；Gmax為最大進(jìn)化次數(shù)。變異算子是產(chǎn)生新個(gè)體的輔助算子，取較小的變異概率值有利于提高局部尋優(yōu)的精度。

1.3 多種群遺傳算法

與SGA 相比，MPGA 具有以下特點(diǎn)：

1）MPGA 在解空間生成規(guī)模、搜索域相同的多個(gè)種群中進(jìn)行并行優(yōu)化搜索，打破了SGA 單種群進(jìn)化的框架，其通過(guò)對(duì)不同種群賦予不同的控制參數(shù)，實(shí)現(xiàn)不同的搜索目的。

2）各種群之間通過(guò)移民算子實(shí)現(xiàn)協(xié)同進(jìn)化，最終獲得最優(yōu)解。

3）通過(guò)人工選擇算子保存各種群在每個(gè)進(jìn)化代中的最優(yōu)個(gè)體，并作為判斷算法是否收斂的依據(jù)。

MPGA 引入的移民算子和人工選擇算子描述如下：

1）移民算子。用源種群中的最優(yōu)個(gè)體定期地替換目標(biāo)種群中的最差個(gè)體。

2）人工選擇算子。在進(jìn)化的每一代選出各種群的最優(yōu)個(gè)體放入精英種群進(jìn)行保存，并且精英種群不進(jìn)行選擇、交叉、變異等遺傳操作。

MPGA 的尋優(yōu)過(guò)程如圖2 所示?？梢钥闯觯琈PGA 中多種群的差異性是由SGA 的不同控制參數(shù)來(lái)維持的，即交叉概率和變異概率的取值。這2 個(gè)參數(shù)的計(jì)算公式如式（5）所示：

圖2 MPGA 尋優(yōu)過(guò)程Fig.2 Optimization process of MPGA

其中：Pcro和Pmut為交叉概率和變異概率的初始值；dcro和dmut為變化的區(qū)間長(zhǎng)度；rand()為產(chǎn)生隨機(jī)數(shù)的函數(shù)；Gn為種群數(shù)目。

1.4 算法分析

MEA 定義的趨同操作和異化操作相互獨(dú)立并彼此協(xié)作，任何一方的改進(jìn)都有利于提高算法的搜索性能：趨同操作并行作用于多個(gè)子群體，保證了搜索的高效性；異化操作對(duì)成熟子群體進(jìn)行篩選并探索解空間中新的區(qū)域，保證了群體的每一次迭代都是正向進(jìn)化的。然而，MEA 中各子群體相互獨(dú)立，不同子群體中的個(gè)體無(wú)法交流，缺乏尋優(yōu)多樣性，并且趨同操作和異化操作在生成子群體成員時(shí)具有隨機(jī)性，增加了搜索成本同時(shí)也降低了尋優(yōu)的效率和精度。

SGA 的優(yōu)點(diǎn)是不受約束條件的限制，在進(jìn)行函數(shù)尋優(yōu)時(shí)不依賴于目標(biāo)函數(shù)的梯度信息、連續(xù)性及可導(dǎo)性，其所定義的遺傳操作可有效降低算法陷入局部最優(yōu)的可能性，具有突出的全局搜索能力。但同時(shí)，SGA 的進(jìn)化搜索性能受交叉概率、變異概率以及種群規(guī)模的影響較大，致使其無(wú)法兼顧搜索精度和計(jì)算效率，難以找到問(wèn)題的最優(yōu)解。MPGA 針對(duì)SGA 的缺陷進(jìn)行了改進(jìn)，通過(guò)多種群協(xié)同進(jìn)化的方式降低單個(gè)種群規(guī)模對(duì)算法的影響，引入移民算子增強(qiáng)種群的多樣性，通過(guò)對(duì)不同種群設(shè)置不同的參數(shù)降低尋優(yōu)結(jié)果對(duì)交叉概率和變異概率取值的敏感度。MPGA 的特性決定了其具有解決大規(guī)模、非線性優(yōu)化問(wèn)題的能力，但對(duì)高維、復(fù)雜的多峰函數(shù)進(jìn)行尋優(yōu)時(shí)，仍存在不可忽略的早熟收斂風(fēng)險(xiǎn)。

通過(guò)以上分析可知：MEA 具有靈活、高效的尋優(yōu)框架，趨同操作和異化操作均可單獨(dú)進(jìn)行改進(jìn)；MPGA 具有多種群協(xié)同尋優(yōu)的特點(diǎn)，能夠?qū)ΨN群所在的連續(xù)區(qū)域進(jìn)行全面、細(xì)致的搜索，但各初始種群的分布會(huì)影響其搜尋最優(yōu)解的能力。由于這2 種算法的操作都是面向多種群/子群體的，因此存在一定的相似性，這為本文將MPGA 嵌入MEA 提供了理論基礎(chǔ)。MPGA 的尋優(yōu)機(jī)制可輔助MEA 趨同操作的執(zhí)行，增強(qiáng)子群體間的交互，實(shí)現(xiàn)局部精細(xì)化尋優(yōu)，保證成熟子群體的質(zhì)量，并且選擇、交叉和變異算子用于異化過(guò)程可以提升臨時(shí)子群體的質(zhì)量，避免低效搜索。同時(shí)，異化操作又能指導(dǎo)新一輪的迭代繼續(xù)向有利方向進(jìn)行，最終實(shí)現(xiàn)提高M(jìn)EA 局部尋優(yōu)精度和全局收斂能力的目的。

2 MPGA 與MEA 的混合算法

2.1 混合策略

本文將MPGA 和MEA 相結(jié)合，提出MPGA-MEA算法，混合策略為：利用MPGA 的尋優(yōu)過(guò)程替代MEA子群體內(nèi)的個(gè)體競(jìng)爭(zhēng)，并在局部公告板中定期記錄子群體的最優(yōu)個(gè)體用于移民操作，當(dāng)局部公告板不再更新時(shí)，判定其對(duì)應(yīng)的子群體成熟，此時(shí)更新全局公告板，釋放得分低的成熟子群體。在此基礎(chǔ)上，利用全局公告板信息選擇父代，對(duì)選中的個(gè)體執(zhí)行交叉、變異操作，將產(chǎn)生的子代個(gè)體作為中心個(gè)體，以此生成高質(zhì)量的臨時(shí)子群體，用于下一輪的迭代尋優(yōu)。

MPGA-MEA 尋優(yōu)的簡(jiǎn)化過(guò)程如圖3 所示，具體步驟如下：

圖3 MPGA-MEA 尋優(yōu)過(guò)程Fig.3 Optimization process of MPGA-MEA

步驟1參數(shù)設(shè)置。設(shè)群體規(guī)模為PPopsize，優(yōu)勝子群體的數(shù)量為SN，臨時(shí)子群體的數(shù)量為T(mén)N，子群體規(guī)模NNind=PPopsize/(SN+TN)。

步驟2群體初始化。在解空間內(nèi)隨機(jī)生成規(guī)模為PPopsize的群體，并根據(jù)適應(yīng)度得分進(jìn)行排序。取得分最高的(SN+TN)個(gè)個(gè)體作為中心個(gè)體，在以它們?yōu)橹行牡囊欢▍^(qū)域內(nèi)分別產(chǎn)生規(guī)模為NNind的SN個(gè)優(yōu)勝子群體和TN個(gè)臨時(shí)子群體。

步驟4異化操作。完成臨時(shí)子群體和優(yōu)勝子群體的替換和釋放，并選擇全局公告板中記錄的優(yōu)勝個(gè)體執(zhí)行交叉、變異操作得到新個(gè)體，在以該個(gè)體為中心的一定區(qū)域內(nèi)生成新的臨時(shí)子群體參與下一輪競(jìng)爭(zhēng)，保證子群體的總數(shù)不變。

步驟5判斷是否滿足終止條件。若是，結(jié)束迭代并輸出結(jié)果；否則，返回步驟3，進(jìn)行下一輪迭代搜索。

2.2 算法實(shí)現(xiàn)

MPGA-MEA 算法實(shí)現(xiàn)偽代碼如下：

算法1MPGA-MEA

上述偽代碼中各部分與算法步驟的對(duì)應(yīng)關(guān)系如下：輸入?yún)?shù)設(shè)置對(duì)應(yīng)于步驟1；1～3對(duì)應(yīng)于步驟2；5和6對(duì)應(yīng)于步驟3；7.1～7.5 對(duì)應(yīng)于步驟4；4 和8～10 對(duì)應(yīng)于步驟5。通過(guò)算法描述可知，MPGA-MEA的迭代包括2種：1）步驟3 中MPGA 的尋優(yōu)過(guò)程，子群體需要進(jìn)行多次迭代直至成熟，記為內(nèi)部迭代；2）步驟5 MEA 框架中的迭代，用于輔助子群體正向進(jìn)化，記為外部迭代。

3 測(cè)試與分析

3.1 測(cè)試函數(shù)與對(duì)比算法

為驗(yàn)證MPGA-MEA 的性能，選取表1 中列出的6 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行尋優(yōu)測(cè)試，其中：f1、f2、f3分別為碗狀、板狀、山谷狀的單峰函數(shù)，常用于檢測(cè)算法的收斂性能和搜索精度；f4、f5、f6為局部極值點(diǎn)分布規(guī)律各異的多峰函數(shù)，可有效檢測(cè)算法對(duì)復(fù)雜優(yōu)化問(wèn)題的全局搜索能力。6 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的搜索域各不相同，全局最小值均為0。

表1 測(cè)試函數(shù)Table 1 Test functions

選擇MPGA 和MEA 作為MPGA-MEA 的對(duì)比算法。各算法的時(shí)間復(fù)雜度與具體的參數(shù)設(shè)置有關(guān)，為降低計(jì)算成本，需要根據(jù)目標(biāo)函數(shù)的尋優(yōu)難度和變量維度分別設(shè)置合理的初始參數(shù)。

3.2 測(cè)試結(jié)果及分析

本文對(duì)不同維度的測(cè)試函數(shù)設(shè)置不同的目標(biāo)精度，如表2 所示。當(dāng)算法搜索到滿足目標(biāo)精度的最優(yōu)解時(shí)停止運(yùn)行，同時(shí)為算法陷入局部極值的情況設(shè)置相應(yīng)的終止條件。每個(gè)算法對(duì)不同維度的測(cè)試函數(shù)運(yùn)行50 次，適應(yīng)度函數(shù)即為對(duì)應(yīng)的測(cè)試函數(shù)。

表2 測(cè)試函數(shù)在不同維度下的目標(biāo)精度Table 2 Target accuracy of the test functions under different dimensions

選用尋優(yōu)成功率、最差解和耗時(shí)作為算法的評(píng)價(jià)指標(biāo)。尋優(yōu)成功率表示算法尋優(yōu)值達(dá)到目標(biāo)精度的測(cè)試次數(shù)占測(cè)試總次數(shù)的百分比；最差解是在算法尋優(yōu)失敗的測(cè)試中所搜索到的最差目標(biāo)值精度；耗時(shí)即每次搜索的總用時(shí)，評(píng)價(jià)時(shí)取50 次測(cè)試用時(shí)的平均值用于對(duì)比。測(cè)試環(huán)境為64 位Windows10操作系統(tǒng)，Intel?CoreTMi7-4510U 處理器，仿真平臺(tái)為MATLAB R2017b，MPGA 的相關(guān)操作借助Sheffield 遺傳算法工具箱完成。

俗話說(shuō)：“書(shū)中自有黃金屋，書(shū)中自有顏如玉?！弊盍钗议_(kāi)心的既不是去旅游，也不是品嘗美食，而是在圖書(shū)館中遨游。

3.2.1 單峰函數(shù)測(cè)試與分析

設(shè)置MPGA 和MPGA-MEA 的交叉概率Pcro=0.4，變異概率Pmut=0.2，最優(yōu)個(gè)體的保持代數(shù)MMaxGen=3；MEA子群體最優(yōu)個(gè)體的保持代數(shù)為10；MPGA-MEA 的最大外部迭代次數(shù)IIter=10；算法的各種群/子群體中的個(gè)體數(shù)NNind=30。在對(duì)不同維度的單峰函數(shù)尋優(yōu)時(shí)，其他主要參數(shù)設(shè)置如表3 所示。其中，MP為種群數(shù)，SN、TN分別為優(yōu)勝子群體和臨時(shí)子群體的數(shù)量。

表3 3 種算法在不同維度下的關(guān)鍵參數(shù)設(shè)置Table 3 Key parameters settings of three algorithms under different dimensions

表4 列出了各算法對(duì)單峰函數(shù)的測(cè)試結(jié)果?？梢钥闯觯簩?duì)于碗狀函數(shù)Sphere，MPGA 和MPGA-MEA 都具有良好的尋優(yōu)效果，MPGA-MEA 平均耗時(shí)略小于MPGA，MEA 的搜索結(jié)果與目標(biāo)精度相差很大；對(duì)于板狀函數(shù)Zakharov，最優(yōu)值附近梯度變化平緩，尋優(yōu)難度高，MEA 僅在維度取2 時(shí)有30%的尋優(yōu)成功率，在高維度下尋優(yōu)能力弱，MPGA 和MPGA-MEA 的尋優(yōu)能力接近，但MPGA-MEA 的平均耗時(shí)更短；對(duì)于2 維的山谷狀函數(shù)Rosenbrock，僅有MPGA-MEA 的尋優(yōu)成功率為100%，且耗時(shí)最短，當(dāng)維度取值為50、100、200時(shí)MEA難以達(dá)到目標(biāo)精度，但尋優(yōu)結(jié)果與目標(biāo)精度接近，而MPGA 在高維度下用時(shí)較短。

表4 3 種算法對(duì)單峰函數(shù)的尋優(yōu)性能比較Table 4 Comparison of optimization performance of three algorithms for unimodal functions

通過(guò)以上分析可知，MPGA-MEA 對(duì)單峰函數(shù)的尋優(yōu)成功率最高，MPGA次之，MEA的搜索精度遠(yuǎn)低于前兩者。MPGA 和MPGA-MEA 對(duì)單峰函數(shù)的綜合尋優(yōu)能力比較接近，對(duì)于MPGA存在尋優(yōu)失敗的情況（如2維的f3函數(shù)），MPGA-MEA可以通過(guò)異化操作對(duì)最優(yōu)值所在的局部區(qū)域加強(qiáng)搜索，直至滿足結(jié)束條件。為對(duì)MPGA和MPGA-MEA 的收斂規(guī)律做進(jìn)一步比較，繪制f1～f3在2維和100維時(shí)的收斂曲線，如圖4所示。

圖4 MPGA 和MPGA-MEA 算法對(duì)單峰函數(shù)尋優(yōu)的收斂曲線對(duì)比Fig.4 Comparison of convergence curves of MPGA and MPGA-MEA algorithms for unimodal functions optimization

由于MPGA-MEA 的迭代為優(yōu)勝子群體或臨時(shí)子群體執(zhí)行的內(nèi)部迭代，因此MPGA-MEA 參與執(zhí)行1 次迭代的子群體數(shù)少于MPGA 參與1 次迭代的種群數(shù)。同時(shí)由于單峰函數(shù)不存在局部極值，因此一般無(wú)需執(zhí)行MPGA-MEA 的異化操作，圖4 實(shí)質(zhì)是比較MPGA-MEA 中趨同操作和MPGA 的收斂能力。

MPGA-MEA 的子群體是以全局優(yōu)質(zhì)個(gè)體為中心生成的多個(gè)小范圍種群，因而其收斂曲線的起點(diǎn)一般優(yōu)于隨機(jī)分布的MPGA 的起點(diǎn)。此外，MPGA 的收斂過(guò)程變化相對(duì)平穩(wěn)，MPGA-MEA 對(duì)尋優(yōu)難度低的函數(shù)迭代次數(shù)更少，但兩者收斂曲線的整體變化趨勢(shì)相似。

3.2.2 多峰函數(shù)測(cè)試與分析

設(shè)置MPGA 和MPGA-MEA 的交叉概率Pcro=0.4，變異概率Pmut=0.2，最優(yōu)個(gè)體保持代數(shù)MMaxGen=3；MEA子群體最優(yōu)個(gè)體保持代數(shù)為10；MPGA-MEA 和MEA的最大迭代次數(shù)IIter=30；算法的各種群/子群體中的個(gè)體數(shù)NNind=30。由于不同的多峰函數(shù)尋優(yōu)難度相差較大，為保證算法的尋優(yōu)能力和對(duì)比的公平性，對(duì)多峰函數(shù)的不同維度進(jìn)行尋優(yōu)時(shí)，分別設(shè)置不同的種群和子群體數(shù)量，如表5～表7所示。其中：MP為種群數(shù)；SN、TN分別為優(yōu)勝子群體和臨時(shí)子群體的數(shù)量。

表5 3 種算法對(duì)f4的參數(shù)設(shè)置Table 5 Parameters settings of three algorithms to f4

表6 3 種算法對(duì)f5的參數(shù)設(shè)置Table 6 Parameters settings of thress algorithms to f5

表7 3 種算法對(duì)f6的參數(shù)設(shè)置Table 7 Parameters setting of three algorithms to f6

表8 列出了各算法對(duì)多峰函數(shù)的測(cè)試結(jié)果。可以看出：格柵函數(shù)Griewank 具有很多規(guī)律分布的局部極小值，MPGA 有較大幾率陷入局部極值致使尋優(yōu)失敗，此時(shí)搜索到的最優(yōu)值坐標(biāo)與實(shí)際最優(yōu)值坐標(biāo)發(fā)生明顯偏離，MPGA-MEA 的趨同操作同樣存在陷入局部極值的風(fēng)險(xiǎn)，得益于異化操作的介入，其能夠以較低的代價(jià)在最優(yōu)值附近重新生成新的臨時(shí)子群體參與迭代搜索，直至滿足結(jié)束條件，MEA 的尋優(yōu)成功率為0，且與目標(biāo)精度相差甚遠(yuǎn)；Rastrigin 函數(shù)的尋優(yōu)難度會(huì)隨著維度的增加迅速增大，使得各算法均無(wú)法搜索到高精度的目標(biāo)值，因此，在高維度下設(shè)置的目標(biāo)精度較低，該目標(biāo)精度下MPGA 的尋優(yōu)失敗率低，MPGA 和MPGA-MEA 的平均耗時(shí)無(wú)明顯差距，但后者的尋優(yōu)成功率穩(wěn)定在100%，MEA 無(wú)法達(dá)到目標(biāo)精度；Ackley 函數(shù)廣泛用于測(cè)試優(yōu)化算法，該函數(shù)最優(yōu)值附近的梯度變化大，尋優(yōu)難度相對(duì)較低，MPGA 和MPGA-MEA 在不同維度下都能以較高的精度收斂到最優(yōu)值附近，兩者耗時(shí)相近，MPGA-MEA 的尋優(yōu)成功率較高，MEA 的搜索精度遠(yuǎn)低于目標(biāo)精度。

表8 3 種算法對(duì)多峰函數(shù)的尋優(yōu)性能比較Table 8 Comparison of optimization performance of three algorithms for multimodal functions

通過(guò)以上對(duì)比可知，MPGA-MEA 對(duì)多峰函數(shù)的尋優(yōu)能力突出，即使在高緯度下，該算法依舊具備很強(qiáng)的跳出局部極值的能力，可以較低的計(jì)算成本提高尋優(yōu)成功率；MPGA 在解決高維度、多極點(diǎn)問(wèn)題時(shí)存在不同程度陷入局部極值的風(fēng)險(xiǎn)，尋優(yōu)失敗的搜索過(guò)程耗時(shí)也略高；MEA的尋優(yōu)精度遠(yuǎn)低于前兩者。為對(duì)比MPGA和MPGA-MEA 的收斂特性，繪制f4～f6在2 維和100 維時(shí)MPGA 和MPGA-MEA 的收斂曲線，如圖5 所示。

圖5 MPGA 和MPGA-MEA 算法對(duì)多峰函數(shù)的尋優(yōu)曲線對(duì)比Fig.5 Comparison of optimization curves of MPGA and MPGA-MEA algorithms for multimodal functions

選取MPGA 對(duì)函數(shù)Griewank 尋優(yōu)失敗的收斂曲線進(jìn)行對(duì)比，如圖5（a）和圖5（b）所示，可以看出：MPGAMEA 的收斂精度明顯優(yōu)于MPGA，但兩者在前期的收斂曲線變化一致；當(dāng)維度取2 時(shí)，MPGA 在第10 次迭代時(shí)便陷入局部極值，直至尋優(yōu)結(jié)束也未能跳出；當(dāng)維度為100時(shí)，MPGA約在第1 300次迭代時(shí)陷入局部極值，直至結(jié)束尋優(yōu)過(guò)程；MPGA-MEA能利用異化操作跳出局部極值，生成新的子群體參與下輪搜索。

選取MPGA 對(duì)函數(shù)Rastrigin 尋優(yōu)成功的收斂曲線進(jìn)行對(duì)比，如圖5（c）和圖5（d）所示，可以看出，MPGA 和MPGA-MEA 的收斂規(guī)律相似。

選取MPGA 對(duì)函數(shù)Ackley 尋優(yōu)失敗和成功的收斂曲線進(jìn)行對(duì)比，如圖5（e）和圖5（f）所示，可以看出：維度為2 時(shí)，MPGA 前20 次迭代過(guò)程的收斂曲線變化和MPGA-MEA 相似，然后MPGA 陷入局部極值；當(dāng)維度為100 時(shí)，兩者的收斂曲線變化規(guī)律相似。

綜上可知：MPGA-MEA 對(duì)單峰函數(shù)的尋優(yōu)能力與MPGA 相近，遠(yuǎn)高于MEA；對(duì)高維、復(fù)雜的多峰函數(shù)進(jìn)行尋優(yōu)時(shí)，MPGA-MEA 的優(yōu)勢(shì)明顯，可在保證運(yùn)算效率的同時(shí)，有效克服MPGA 和MEA 早熟收斂的缺陷。

4 結(jié)束語(yǔ)

本文分析MPGA 和MEA 的優(yōu)缺點(diǎn)，從優(yōu)勢(shì)互補(bǔ)的角度出發(fā)設(shè)計(jì)混合算法MPGA-MEA。該算法以MEA 為框架，以MPGA 為內(nèi)核，將MPGA 的尋優(yōu)機(jī)制和遺傳操作應(yīng)用到MEA 的趨同操作和異化過(guò)程中，優(yōu)化趨同操作對(duì)各子群體的搜索效果，提高異化過(guò)程中生成的臨時(shí)子群體的質(zhì)量，實(shí)現(xiàn)對(duì)MEA 局部搜索精度和全局尋優(yōu)能力的均衡提升。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了MPGA-MEA 優(yōu)越的綜合性能。由于條件受限，本文僅對(duì)MPGA-MEA 進(jìn)行理論分析和部分標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真驗(yàn)證，下一步將研究高維度下提升MPGA-MEA 尋優(yōu)效率和搜索精度更優(yōu)的參數(shù)設(shè)置，探索各參數(shù)取值和算法性能之間的關(guān)系，并將現(xiàn)有對(duì)MPGA 的改進(jìn)方法應(yīng)用到MPGA-MEA 的趨同操作中，以進(jìn)一步提升算法的搜索性能。