基于多種群遺傳與思維進化的混合算法

倪水平，戚海濤，李慧芳

（河南理工大學計算機科學與技術學院，河南焦作 454000）

0 概述

進化算法作為計算機科學與生物進化規律結合發展形成的一類啟發式搜索算法，克服了傳統優化算法存在的全局尋優能力差、解的質量依賴初始值等缺陷，對求解復雜問題表現出較強的魯棒性［1］。標準遺傳算法（Standard Genetic Algorithm，SGA）［2］作為進化算法的代表之一，廣泛應用于圖像處理［3］、組合優化［4］、函數優化［5］、車間調度［6］等領域。然而，SGA 存在收斂速度慢、易早熟等問題［7-9］。

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

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

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

1 思維進化算法與多種群遺傳算法

1.1 思維進化算法

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

定義1子群體范圍內的個體為成為勝者而進行競爭的過程稱為趨同。

定義2各子群體在解空間范圍內為成為勝者而相互競爭并進行不斷地探索的過程稱為異化。

定義3當一個子群體在趨同過程中不再產生新的勝者時，該子群體稱為成熟子群體，其趨同過程也隨之結束。

MEA 的尋優流程如圖1 所示。

圖1 MEA 尋優過程Fig.1 Optimization process of MEA

MEA 在尋優過程中，把全部解空間看作一個群體，再把群體劃分為若干個子群體，每個子群體包含對應局部區域的若干個體。適應度得分高的子群體會作為優勝子群體，用于記錄全局競爭中優勝者的信息；得分低的子群體則作為臨時子群體，用于記錄并輔助完成全局競爭的過程。

趨同操作負責各子群體內的局部搜索，該操作的關鍵步驟是搜尋局部最優個體，并在其臨近區域隨機生成若干新的成員繼續參與搜索，這種尋優方式使得MEA 的搜索精度較低。待子群體成熟后，MEA 執行異化操作，通過查找全局公告板記錄的信息釋放得分低的子群體，并使在解空間隨機生成新的臨時子群體繼續參與競爭，保證最優解正向進化，這一過程決定著MEA 的全局尋優能力。如此反復迭代，實現全局尋優。

1.2 標準遺傳操作

遺傳操作是SGA 的核心，包括選擇、交叉和變異。3 種遺傳操作的實現過程如下：

1）選擇操作

從當代群體中以一定的概率選擇個體作為父輩，并繁衍下一代。個體被選中的概率與適應度值成正相關，選擇操作為后代的質量提供了保障。

GA 常用的選擇操作有錦標賽法和輪盤賭法，本文選用基于適應度比例的輪盤賭法。在該選擇策略下，選中個體i的概率pi的計算公式如式（1）所示：

其中：N為種群中的個體數目；Fi為個體i的適應度得分。

2）交叉操作

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

其中：b是［0，1］之間的隨機數。交叉算子是產生新個體的主要算子，取較大的交叉概率值有助于提升算法的全局尋優能力。

3）變異操作

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

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

其中：g為當前迭代次數；r2是一個隨機數；Gmax為最大進化次數。變異算子是產生新個體的輔助算子，取較小的變異概率值有利于提高局部尋優的精度。

1.3 多種群遺傳算法

與SGA 相比，MPGA 具有以下特點：

1）MPGA 在解空間生成規模、搜索域相同的多個種群中進行并行優化搜索，打破了SGA 單種群進化的框架，其通過對不同種群賦予不同的控制參數，實現不同的搜索目的。

2）各種群之間通過移民算子實現協同進化，最終獲得最優解。

3）通過人工選擇算子保存各種群在每個進化代中的最優個體，并作為判斷算法是否收斂的依據。

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

1）移民算子。用源種群中的最優個體定期地替換目標種群中的最差個體。

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

MPGA 的尋優過程如圖2 所示。可以看出，MPGA 中多種群的差異性是由SGA 的不同控制參數來維持的，即交叉概率和變異概率的取值。這2 個參數的計算公式如式（5）所示：

圖2 MPGA 尋優過程Fig.2 Optimization process of MPGA

其中：Pcro和Pmut為交叉概率和變異概率的初始值；dcro和dmut為變化的區間長度；rand()為產生隨機數的函數；Gn為種群數目。

1.4 算法分析

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

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

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

2 MPGA 與MEA 的混合算法

2.1 混合策略

本文將MPGA 和MEA 相結合，提出MPGA-MEA算法，混合策略為：利用MPGA 的尋優過程替代MEA子群體內的個體競爭，并在局部公告板中定期記錄子群體的最優個體用于移民操作，當局部公告板不再更新時，判定其對應的子群體成熟，此時更新全局公告板，釋放得分低的成熟子群體。在此基礎上，利用全局公告板信息選擇父代，對選中的個體執行交叉、變異操作，將產生的子代個體作為中心個體，以此生成高質量的臨時子群體，用于下一輪的迭代尋優。

MPGA-MEA 尋優的簡化過程如圖3 所示，具體步驟如下：

圖3 MPGA-MEA 尋優過程Fig.3 Optimization process of MPGA-MEA

步驟1參數設置。設群體規模為PPopsize，優勝子群體的數量為SN，臨時子群體的數量為TN，子群體規模NNind=PPopsize/(SN+TN)。

步驟2群體初始化。在解空間內隨機生成規模為PPopsize的群體，并根據適應度得分進行排序。取得分最高的(SN+TN)個個體作為中心個體，在以它們為中心的一定區域內分別產生規模為NNind的SN個優勝子群體和TN個臨時子群體。

步驟4異化操作。完成臨時子群體和優勝子群體的替換和釋放，并選擇全局公告板中記錄的優勝個體執行交叉、變異操作得到新個體，在以該個體為中心的一定區域內生成新的臨時子群體參與下一輪競爭，保證子群體的總數不變。

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

2.2 算法實現

MPGA-MEA 算法實現偽代碼如下：

算法1MPGA-MEA

上述偽代碼中各部分與算法步驟的對應關系如下：輸入參數設置對應于步驟1；1～3對應于步驟2；5和6對應于步驟3；7.1～7.5 對應于步驟4；4 和8～10 對應于步驟5。通過算法描述可知，MPGA-MEA的迭代包括2種：1）步驟3 中MPGA 的尋優過程，子群體需要進行多次迭代直至成熟，記為內部迭代；2）步驟5 MEA 框架中的迭代，用于輔助子群體正向進化，記為外部迭代。

3 測試與分析

3.1 測試函數與對比算法

為驗證MPGA-MEA 的性能，選取表1 中列出的6 個標準測試函數進行尋優測試，其中：f1、f2、f3分別為碗狀、板狀、山谷狀的單峰函數，常用于檢測算法的收斂性能和搜索精度；f4、f5、f6為局部極值點分布規律各異的多峰函數，可有效檢測算法對復雜優化問題的全局搜索能力。6 個標準測試函數的搜索域各不相同，全局最小值均為0。

表1 測試函數Table 1 Test functions

選擇MPGA 和MEA 作為MPGA-MEA 的對比算法。各算法的時間復雜度與具體的參數設置有關，為降低計算成本，需要根據目標函數的尋優難度和變量維度分別設置合理的初始參數。

3.2 測試結果及分析

本文對不同維度的測試函數設置不同的目標精度，如表2 所示。當算法搜索到滿足目標精度的最優解時停止運行，同時為算法陷入局部極值的情況設置相應的終止條件。每個算法對不同維度的測試函數運行50 次，適應度函數即為對應的測試函數。

表2 測試函數在不同維度下的目標精度Table 2 Target accuracy of the test functions under different dimensions

選用尋優成功率、最差解和耗時作為算法的評價指標。尋優成功率表示算法尋優值達到目標精度的測試次數占測試總次數的百分比；最差解是在算法尋優失敗的測試中所搜索到的最差目標值精度；耗時即每次搜索的總用時，評價時取50 次測試用時的平均值用于對比。測試環境為64 位Windows10操作系統，Intel?CoreTMi7-4510U 處理器，仿真平臺為MATLAB R2017b，MPGA 的相關操作借助Sheffield 遺傳算法工具箱完成。

俗話說：“書中自有黃金屋，書中自有顏如玉。”最令我開心的既不是去旅游，也不是品嘗美食，而是在圖書館中遨游。

3.2.1 單峰函數測試與分析

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

表3 3 種算法在不同維度下的關鍵參數設置Table 3 Key parameters settings of three algorithms under different dimensions

表4 列出了各算法對單峰函數的測試結果。可以看出：對于碗狀函數Sphere，MPGA 和MPGA-MEA 都具有良好的尋優效果，MPGA-MEA 平均耗時略小于MPGA，MEA 的搜索結果與目標精度相差很大；對于板狀函數Zakharov，最優值附近梯度變化平緩，尋優難度高，MEA 僅在維度取2 時有30%的尋優成功率，在高維度下尋優能力弱，MPGA 和MPGA-MEA 的尋優能力接近，但MPGA-MEA 的平均耗時更短；對于2 維的山谷狀函數Rosenbrock，僅有MPGA-MEA 的尋優成功率為100%，且耗時最短，當維度取值為50、100、200時MEA難以達到目標精度，但尋優結果與目標精度接近，而MPGA 在高維度下用時較短。

表4 3 種算法對單峰函數的尋優性能比較Table 4 Comparison of optimization performance of three algorithms for unimodal functions

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

圖4 MPGA 和MPGA-MEA 算法對單峰函數尋優的收斂曲線對比Fig.4 Comparison of convergence curves of MPGA and MPGA-MEA algorithms for unimodal functions optimization

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

MPGA-MEA 的子群體是以全局優質個體為中心生成的多個小范圍種群，因而其收斂曲線的起點一般優于隨機分布的MPGA 的起點。此外，MPGA 的收斂過程變化相對平穩，MPGA-MEA 對尋優難度低的函數迭代次數更少，但兩者收斂曲線的整體變化趨勢相似。

3.2.2 多峰函數測試與分析

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

表5 3 種算法對f4的參數設置Table 5 Parameters settings of three algorithms to f4

表6 3 種算法對f5的參數設置Table 6 Parameters settings of thress algorithms to f5

表7 3 種算法對f6的參數設置Table 7 Parameters setting of three algorithms to f6

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

表8 3 種算法對多峰函數的尋優性能比較Table 8 Comparison of optimization performance of three algorithms for multimodal functions

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

圖5 MPGA 和MPGA-MEA 算法對多峰函數的尋優曲線對比Fig.5 Comparison of optimization curves of MPGA and MPGA-MEA algorithms for multimodal functions

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

選取MPGA 對函數Rastrigin 尋優成功的收斂曲線進行對比，如圖5（c）和圖5（d）所示，可以看出，MPGA 和MPGA-MEA 的收斂規律相似。

選取MPGA 對函數Ackley 尋優失敗和成功的收斂曲線進行對比，如圖5（e）和圖5（f）所示，可以看出：維度為2 時，MPGA 前20 次迭代過程的收斂曲線變化和MPGA-MEA 相似，然后MPGA 陷入局部極值；當維度為100 時，兩者的收斂曲線變化規律相似。

綜上可知：MPGA-MEA 對單峰函數的尋優能力與MPGA 相近，遠高于MEA；對高維、復雜的多峰函數進行尋優時，MPGA-MEA 的優勢明顯，可在保證運算效率的同時，有效克服MPGA 和MEA 早熟收斂的缺陷。

4 結束語

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