季偉東 倪婉璐

(哈爾濱師范大學計算機科學與信息工程學院 哈爾濱 150025)

1 引言

自然計算(natural computation)是指受自然現(xiàn)象啟發(fā)而發(fā)展起來的智能算法，如人工神經(jīng)網(wǎng)絡(luò)、進化計算、群智能、人工免疫系統(tǒng)、量子計算等[1]。自然計算具有自組織、自學習、自適應(yīng)能力，能夠?qū)W習運用自然規(guī)律、模擬自然系統(tǒng)甚至社會系統(tǒng)的演變過程，在復雜優(yōu)化問題求解、智能控制與機器人控制、網(wǎng)絡(luò)通信與信息安全、社會經(jīng)濟、生態(tài)環(huán)境、航空航天與軍事等領(lǐng)域的應(yīng)用非常廣[2]。

自然計算方法是基于種群的優(yōu)化方法，其中，種群規(guī)模對算法的搜索能力和算法計算成本有較大影響。種群規(guī)模越大，搜索范圍越大，則全局最優(yōu)解存在概率越高，同時增加計算成本；而種群規(guī)模小可以降低計算成本，但是可能導致種群無法搜索到更多有效區(qū)域[1]。所以，如何恰當?shù)乜刂品N群規(guī)模來平衡算法的全局和局部搜索能力，成為自然計算方法應(yīng)用亟待解決的問題。

針對此問題，已經(jīng)存在很多控制種群規(guī)模的方法。種群分組是最簡單的控制種群規(guī)模的方法，Sun等人[3]將種群分為主群和從群，平衡算法的多樣性；為保證算法的全局勘探能力，夏學文等人[4]提出了具備反向?qū)W習和局部學習能力相結(jié)合的粒子群優(yōu)化算法；文獻[5]提出了基于多種群的自適應(yīng)遷移PSO算法(Muti-population based Self-adaptive Migration PSO, MSMPSO)，對初始種群等分，為各子種群分配相應(yīng)的加速因子而平衡算法；文獻[6]通過高斯函數(shù)遞減慣性權(quán)重來平衡粒子群優(yōu)化算法的全局搜索和局部搜索能力，提出了基于高斯函數(shù)遞減慣性權(quán)重的粒子群優(yōu)化算法(Particle Swarm Optimization algorithms with Decreasing Inertia Weight based on Gaussian function, GDIWPSO)；Xu等人[7]利用雙種群的思想，提高了收斂精度和收斂速度。過大的規(guī)模會降低算法效率，然而通過種群分組后，過小的種群規(guī)模又會導致算法過早收斂。文獻[8]已經(jīng)證明不同的進化階段需要不同的種群規(guī)模，因此，動態(tài)控制種群規(guī)模更為關(guān)鍵。可變種群規(guī)模的遺傳算法[9]使用離散Logistic模型控制種群規(guī)模；Affenzeller等人[10]根據(jù)算法實際難易程度來調(diào)整實際的種群大小；Wang等人[11]采用可變的人口規(guī)模機制，自適應(yīng)地調(diào)整人口規(guī)模；文獻[12]更是對種群規(guī)模從確定性、適應(yīng)性和自適應(yīng)方法3個方面進行綜述，進一步說明動態(tài)控制種群規(guī)模的優(yōu)越性。同時，大多文獻采用距離判定法作為種群規(guī)模動態(tài)控制的先驗方法，應(yīng)用最為廣泛的是歐氏距離判定方法。歐氏距離較多應(yīng)用于機器學習中的特征提取、特征選擇、分類。Patel等人[13]基于歐氏距離進行特征排序與子集的選擇；Bouley等人[14]用歐幾里得矩陣定義整體幾何構(gòu)型，利用多維展開技術(shù)從距離上重建點集；Alguliyev等人[15]提出基于歐氏距離平方度量的加權(quán)共識聚類方法，提高了聚類精度。通過在特征提取、特征選擇、分類等方面的應(yīng)用，歐式距離可以很好地解釋樣本間的屬性差異，擴展應(yīng)用到自然計算中，可以理解為個體間的相似度，個體距離越小越相似，則個體間可交互信息越缺乏價值，以此來判定個體對算法的有效性，從而進行增刪個體的操作控制種群規(guī)模來提高算法性能。例如，基于改進小生境粒子群算法的多模函數(shù)優(yōu)化[16]、基于歐氏距離的黑洞尋優(yōu)算法[17]、基于歐氏距離與多種搜索策略的人工蜂群算法[18]均是根據(jù)歐氏距離判定個體間的位置從而進行增刪個體的操作。這些算法分別側(cè)重提高算法收斂速度、精度，以及對算法探索和開發(fā)能力的平衡，欠缺對算法性能綜合性的考量。

為此，本文提出一種基于歐氏距離的種群規(guī)模動態(tài)控制方法(a dynamic control method of Population Size based on Euclidean Distance, EDPS)，并將該方法分別運用于3種不同的自然計算方法中，通過對收斂性分析，并在測試函數(shù)仿真實驗及對實驗數(shù)據(jù)進行非參數(shù)檢驗，驗證本文提出的方法的有效性和普適性，能更好地平衡算法的探索和開發(fā)能力。

2 基于核心圓域動態(tài)控制種群規(guī)模的優(yōu)化策略

2.1 歐氏距離

歐氏距離計算的是D維空間中兩點之間的真實距離，是通常采用的一個距離定義。在自然計算方法中，基于歐氏距離的相似性度量[19]用來判定個體的相似程度，距離越近就越相似，可利用的有效信息就越匱乏，更易使算法陷入局部最優(yōu)，算法全局搜索能力減弱。

本文計算初始種群的全局最優(yōu)點與種群平均適應(yīng)度值點間的歐氏距離，以此作為核心圓域的初始半徑，初始半徑可定義為

2.2 動態(tài)控制策略

基于核心圓域動態(tài)控制種群規(guī)模的主要思想為：建立核心圓域，核心圓域的圓心為每次迭代的全局最優(yōu)點，半徑為初始半徑r間隔K代線性遞減；迭代前期圓域范圍較大，增強全局搜索能力，若圓域內(nèi)的個體數(shù)超過θ倍的種群個體數(shù)，則隨機刪除圓域內(nèi)20%的個體，同時圓域外增加等量個體，增加個體多樣性；迭代后期，隨著半徑線性遞減，圓域范圍縮小，進行局部搜索，若圓域外個體數(shù)超過θ倍的種群個體數(shù)，則將圓域外個體按年齡參數(shù)[20]降序排位，刪除前20%的個體。其中，K是控制種群規(guī)模的激活閾值，為了平衡算法全局和局部搜索能力，K應(yīng)該取較小值，使得迭代前后期有較顯著的差異，增強種群多樣性，不易陷入局部最優(yōu)；θ是進行增刪個體的判定閾值，理論上，前期進行全局搜索，核心圓域范圍較大，圓域內(nèi)個體數(shù)目應(yīng)多于圓域外的；后期進行局部搜索，接近全局最優(yōu)，核心圓域范圍縮小，因此，在這里設(shè)置增刪個體的判定閾值的范圍為[1/2, 1)；年齡參數(shù)，即個體優(yōu)化迭代次數(shù)，年齡較大的個體到后期缺失探索的有效性，將其刪除降低迭代后期收斂到局部最優(yōu)的概率，保證了種群整體的活性。激活閾值K和增刪個體的判定閾值θ的具體取值由第2部分實驗證明給出。

動態(tài)控制流程如圖1所示。其中，n i,no分別表示核心圓域的內(nèi)外個體數(shù)；n idec,nodec分別表示核心圓域內(nèi)外的刪除個體數(shù)；i是種群迭代的當前代數(shù)； r em()取余操作，是控制種群規(guī)模操作判定的前提條件。

圖1 動態(tài)控制流程圖

2.3 基于Sigmoid函數(shù)的半徑非線性遞減

Sigmoid函數(shù)大多用于最小均方誤差(Least Mean Squar，LMS)自適應(yīng)濾波算法，解決固定步長的LMS算法在收斂速度和穩(wěn)態(tài)誤差之間存在的矛盾[21,22]。針對此矛盾，許多學者提出了變步長LMS算法，例如，基于Sigmoid函數(shù)的變步長LMS自適應(yīng)濾波算法[23-25]，在初始階段采用大步長因子加快收斂速度，收斂后采用小步長因子降低穩(wěn)態(tài)誤差[26]。本文對核心圓域半徑步長自適應(yīng)調(diào)整的主要思想是，在算法早期搜索過程中，采用大半徑擴大圓域的范圍，提高算法多樣性；局部搜索階段采用小半徑，增強算子的有效性，提高收斂精度。而自然界中種群的隨機性可用正態(tài)分布或近似正態(tài)分布來描述，但是由于正態(tài)分布函數(shù)的計算成本高，而Sigmoid函數(shù)與正態(tài)分布函數(shù)的形式類似，且公式簡單，計算成本低。

2.4 反向?qū)W習策略分析

反向?qū)W習策略在2005年由Tizhoosh提出，該策略廣泛應(yīng)用于各類算法中，有效地提高了求解全局最優(yōu)的效率[27,28]。對高維復雜函數(shù)而言，各維相互間的信息干擾，會使得某些變優(yōu)的維度被變差的維度所影響，變異效率降低，相較于多次的變異，逐維變異避免了維度間的干擾，變異效率更高，得到的變異解通常更好。因此，本文采用逐維重心反向策略[29]，設(shè)當前迭代次數(shù)的最優(yōu)個體

2.5 算法實現(xiàn)策略

3 算法收斂性分析

文獻[31]表明，目前算法收斂性的分析還不夠充分。同時，理論依據(jù)多來源于對生物群落社會性的模擬，與其相關(guān)的數(shù)學分析比較缺乏，這導致現(xiàn)有研究還存在許多不足，缺乏具備普遍意義的理論性分析[32]。因此，本文在此對算法的收斂性進行分析。

min{f(x)|?x ∈S,

定義1 (最小優(yōu)化問題)令

圖2 算法流程圖

證明 種群在算法迭代過程中，根據(jù)圓域內(nèi)外個體的分布比例來對整個種群進行個體的均衡配比操作。圓域外個體通過年齡排序進行刪減，從而達到控制種群規(guī)模的效果，加快收斂速度。圓域外個體占種群全部個體的相對比例為

4 仿真實驗與結(jié)果分析

為檢驗EDPS的綜合性能，將其運用到3種不同的自然計算方法中：粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)，遺傳算法(Genetic Algorithm, GA)，差分進化算法(Differential Evolution algorithm, DE)。對應(yīng)的3種新算法是EDPS+PSO, EDPS+GA和EDPS+DE，并與PSO, GA, DE進行對比。采用通用標準測試函數(shù)(Sphere, Rosenbrock, Dixon-price, Powell, Ackley,Levy, Sum squares, Griewank, Rastrigin, Schwefel 2.22, Step)[35]來驗證其對不同算法的改進效果。所有測試函數(shù)的維數(shù)均取30維。各算法對測試函數(shù)分別執(zhí)行30次，取平均結(jié)果。

4.1 參數(shù)設(shè)置

改進的PSO中涉及的參數(shù)有3個，分別是種群規(guī)模、慣性權(quán)重、學習因子。按照文獻[36]的參數(shù)設(shè)置，令慣性權(quán)重ω由0.9到0.4線性遞減，學習因子c1=c2=2。遺傳算法中涉及的參數(shù)是種群規(guī)模、交叉概率Pc、變異概率Pm，令Pc=0.70，Pm=0.05。差分進化算法中涉及的參數(shù)是種群規(guī)模、縮放因子F=0.5 ，交叉概率Cr=0.9。本文中涉及的參數(shù)有種群規(guī)模的下界 P Smin、種群規(guī)模的上界 P Smax、激活閾值K。PSO, GA, DE中的種群規(guī)模P Smax都設(shè)為100。

4.2 不同改進點實驗結(jié)果分析

為驗證不同方面對EDPS的改進效果，主要從以下3處進行對比分析：

(1)激活閾值K對算法的影響；

(2)增刪個體的判定閾值θ的取值對算法的影響；

(3)增刪的個體數(shù)對算法的影響；

在此考慮篇幅問題，只選用經(jīng)典測試函數(shù)F1和F5，驗證改進方法與PSO算法結(jié)合的性能。

通過表1激活閾值的數(shù)據(jù)可以看出，隨著K的增大，算法對單峰和多峰函數(shù)效果越好，但是當激活閾值K取30之后，收斂精度沒有顯著提高，且當K由40增加到50時，算法在單峰和多峰函數(shù)上的尋優(yōu)精度都有所下降。因此，本文的激活閾值K取值為40。觀察表中判定閾值，在單峰函數(shù)F1和多峰函數(shù)F5上，θ為4/5時的平均尋優(yōu)結(jié)果最佳。因此，本文中θ取值為4/5。

表1 函數(shù)F1和F5基于激活閾值K和判定閾值θ的平均結(jié)果

對圓域內(nèi)外個體的增刪個數(shù)的選擇，首先對比3種情況對算法的影響：在原圓域內(nèi)外個體數(shù)的基礎(chǔ)上隨機增刪、隨機增刪(0, 1/2)的原圓域內(nèi)外個體、增刪個體數(shù)取前兩種情況取值區(qū)間內(nèi)的隨機值。根據(jù)圖3可以明顯看出，隨機增刪個體數(shù)的取值范圍小于半數(shù)的算法收斂效果更好，其次是對總數(shù)的隨機取值，這是由于增刪過半數(shù)的個體，在收斂前期，通過刪除圓域內(nèi)個體，增加圓域外個體，雖然提高了各種群多樣性，但是影響算法的收斂速度；而在收斂后期，刪除多數(shù)圓域外較差個體，又極大程度地破壞了種群多樣性，影響算法收斂精度；而對總數(shù)的隨機取值，雖然收斂精度有所提高，但是降低了算法的魯棒性。實驗在(0,1/2]隨機取值的基礎(chǔ)上，又進行了較準確的增刪個體數(shù)的對比，分別為原圓域內(nèi)外個體數(shù)的10%, 20%, 30%,40%和50%。通過觀察對比單峰函數(shù)F1和多峰函數(shù)F5的收斂曲線，都清晰地表明，當增刪的個體數(shù)為總體的20%時，算法的性能最佳，且不同取值情況在不同性質(zhì)的函數(shù)上的優(yōu)劣等級相同，更證明了較確切的增刪個體在算法的收斂精度和魯棒性方面都有積極的作用。

圖3 增刪的不同個體數(shù)的收斂圖

4.3 與PSO結(jié)合的算法對比分析

為說明本文算法的優(yōu)勢，將EDPS+PSO與PSO、自適應(yīng)動態(tài)控制種群規(guī)模的自然計算方法(Self-adaptive Dynamic Control strategy of Population Size, SaDCPS+PSO)[1]、MSMPSO[5]、GDIWPSO[6]這3個運用種群策略的粒子群算法進行對比。表2和圖4是EDPS+PSO與其他算法對比的數(shù)據(jù)及收斂圖，考慮到篇幅問題，只選取部分測試函數(shù)收斂圖展示。表2的Mean和Std分別表示獨立運行函數(shù)30次得到的結(jié)果的平均值和標準差，括號內(nèi)數(shù)字表示算法在某一個函數(shù)上的性能排名，如果兩個算法的Mean值相同，則認為標Std較小的更優(yōu)。位于表格最后的Num表示算法在11個測試函數(shù)中取得最優(yōu)的次數(shù)，Ave.R表示算法的平均排名，T.R表示算法總的排名，若兩種算法的Ave.R值相同，則認為Num大的算法較優(yōu)；由于此實驗中EDPS+PSO在11個測試函數(shù)上的效果均優(yōu)于其他算法，使得PSO與MSMPSO無法以Mean比較優(yōu)劣，因此按照這兩個算法的Std平均排名確定最終的T.R?？紤]到篇幅問題，僅對相關(guān)的PSO算法進行了性能排名。

表2 適應(yīng)度值的平均值與標準差

圖4 收斂曲線

為了更直觀地比較EDPS+PSO的改進性能，觀察圖4，EDPS+PSO相比較其他4種算法有非常顯著的優(yōu)勢。在PSO, SaDCPS+PSO, MSMPSO,GDIWPSO在函數(shù)F5, F7上的差異較小，而EDPS+PSO在這4個測試函數(shù)上均表現(xiàn)出與其他算法的較大差異。在大多函數(shù)上EDPS+PSO迭代到5000次仍然有明顯的下降趨勢，而其他算法迭代到1000次左右就陷入了局部最優(yōu)，這是由于在搜索前期，EDPS+PSO運用歐氏距離規(guī)劃核心圓域來控制種群規(guī)模，增加種群多樣性，避免了種群較快收斂到局部最優(yōu)；而SaDCPS+PSO采用增刪算子策略，使得算法作用于多峰函數(shù)F5時，有跳出局部最優(yōu)的能力。

4.4 與GA, DE結(jié)合的算法對比分析

4.4.1 與傳統(tǒng)GA, DE的對比

表3是EDPS+GA, EDPS+DE與GA, DE的實驗對比數(shù)據(jù)，圖5是EDPS+GA, EDPS+DE與GA,DE的對比收斂曲線圖，考慮篇幅問題，只展示部分收斂曲線。橫軸是適應(yīng)度計算次數(shù)，縱軸是平均適應(yīng)度值。從表的數(shù)據(jù)可以得出，EDPS+DE在11個測試函數(shù)上的尋優(yōu)結(jié)果均優(yōu)于DE，尤其是函數(shù)F1, F4, F5, F7, F9, F10, F11，其收斂精度有顯著的提高；對于遺傳算法，只在單峰函數(shù)F2上表現(xiàn)出劣勢，這是由于此函數(shù)很難收斂到最小值。

表3 適應(yīng)度值的平均值與標準差

由圖5可以看出，運用歐氏距離動態(tài)控制種群規(guī)模的算法比未使用的更具備較強的全局搜索能力。根據(jù)收斂曲線，在函數(shù)F1, F10中，結(jié)合本文策略的算法在迭代過程中幾乎一直保持下降的趨勢，而傳統(tǒng)算法則較早地陷入了局部最優(yōu)，說明本文的方法具備較強的全局搜索能力，這是由于早期減少核心圓域內(nèi)的較優(yōu)個體，增加外圍較差個體數(shù)，提高了個體的多樣性，增強了算法的全局搜索能力。對于函數(shù)F4, F8，在迭代前期保證種群規(guī)模的前提下增刪個體，使得算法大都較早地收斂到最優(yōu)值附近，說明前期增加個體多樣性對種群尋優(yōu)有積極的引導作用，體現(xiàn)了增刪個體操作的有效性。

圖5 收斂曲線

4.4.2 與其他改進GA, DE的算法對比分析

為綜合對比算法優(yōu)勢，將其與GA, DE結(jié)合的控制種群規(guī)模算法做對比分析。GAVaPS[37],APAGA[38], PL-GA[39], GPS-GA[40], dynNP-DE[41],SAMDE[42]這些算法基于不同的依據(jù)進行種群控制。將EDPS+GA, EDPS+DE與這些算法對比，進一步比較不同種群規(guī)?？刂撇呗运惴ǖ男阅埽瑓?shù)設(shè)置參考文獻[41]，算法在每個函數(shù)上運行10次，對10次的最佳尋優(yōu)結(jié)果進行平均。從表4結(jié)果可以看出，EDPS+GA在F1, F8, F9函數(shù)上的性能優(yōu)于其他算法；從函數(shù)角度來看，對于函數(shù)F1, F9，只有EDPS+GA和EDPS+DE能找到理想解?？偟膩碚f，EDPS+GA性能最好，因為它在大多數(shù)測試功能上具備較好的解，其次是SAMDE和EDPS+DE。

表4 適應(yīng)度值的平均結(jié)果對比

4.5 CEC13測試函數(shù)實驗結(jié)果分析

為進一步驗證本文策略的有效性，選用CEC13函數(shù)集作為測試函數(shù)[43]，考慮篇幅問題，只選取部分函數(shù)，其中為F1, F2, F5單峰函數(shù)，F(xiàn)6, F10, F11,F14, F16, F17, F19為基礎(chǔ)多模函數(shù)，F(xiàn)20, F21,F23～F25為組合函數(shù)。將EDPS+PSO, EDPS+GA, EDPS+DE與原始算法比較，取30次均值與全局最小值的誤差作為最終的結(jié)果，實驗結(jié)果見表5。

表5 適應(yīng)度值的運行平均結(jié)果

與原始算法進行對比，EDPS+PSO在10個函數(shù)上尋得較高的精度解，其中包含全部單峰函數(shù)，基礎(chǔ)多模函數(shù)F6, F10, F11, F14, F16, F17, F19，表明EDPS+PSO處理單峰函數(shù)問題的能力非常強，運用動態(tài)控制策略后，改善了PSO易陷入局部最優(yōu)的缺點，在多模和組合函數(shù)上也有較大的優(yōu)勢；EDPS+DE在全部函數(shù)上尋得精度最高的解，說明EDPS+DE在3類測試函數(shù)上的優(yōu)化性能都有一定的競爭力；而EDPS+GA僅在多模函數(shù)F6, F14,F17, F19和組合函數(shù)F20, F21, F24這7個函數(shù)上尋得的解的精度較高，這是由于GA本身不易于陷入局部最優(yōu)的特點，對單峰函數(shù)而言，若算法在前期就尋得全局最優(yōu)區(qū)域，動態(tài)控制策略的運用會造成評估次數(shù)的浪費，導致算法性能下降，相對來說，其處理組合函數(shù)問題的能力較強，說明本文提出的策略適用于解決此類函數(shù)優(yōu)化問題。

5 結(jié)論

平衡搜索本質(zhì)上就是早期擴大搜索范圍，后期精確搜索，本文通過動態(tài)控制種群規(guī)模從而達到平衡算法搜索能力的效果。迭代前期控制種群規(guī)模不變，刪除核心圓域內(nèi)較優(yōu)個體，在核心圓域外等添加等量個體，提高個體多樣性，達到擴大搜索范圍的目的；后期進行局部精細搜索，因此對核心圓域外的個體進行刪除操作，加速收斂，同時采用反向變異策略，避免算法陷入局部最優(yōu)。但是，算法的不足之處在于反向變異策略的逐維性大大增加了算法計算高維函數(shù)的時間成本，在后續(xù)研究中，可以針對高維函數(shù)的反向變異進一步改善，降低時間復雜度。