孫小晴，季偉東，林 平，徐浩天

1(哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，哈爾濱 150025)2(哈爾濱醫(yī)科大學(xué)，哈爾濱 150086)

1 引 言

自然計(jì)算(Natural Computation)是智能算法中的一個(gè)術(shù)語(yǔ)，它包含3種方法：

1)從自然種群進(jìn)化中汲取靈感，從而發(fā)現(xiàn)新的問(wèn)題解決方法；

2)基于利用計(jì)算機(jī)分析自然現(xiàn)象的方法；

3)利用自然材料(例如分子)進(jìn)行計(jì)算的方法.

構(gòu)成這3個(gè)分支的主要研究領(lǐng)域是人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化算法、群體智能、人工免疫系統(tǒng)、分形幾何、人造生命、DNA計(jì)算和量子計(jì)算等[1].

基于種群的自然計(jì)算方法是模擬自然界生物進(jìn)化機(jī)理的群智能優(yōu)化算法.隨著群智能算法種類(lèi)的增長(zhǎng)，其改進(jìn)算法也呈指數(shù)增長(zhǎng)，因此，尋找一種不針對(duì)具體算法且具有普適意義的改進(jìn)策略是目前自然計(jì)算領(lǐng)域研究的熱點(diǎn).在改進(jìn)策略中，種群管理對(duì)算法的搜索性能有較大的影響.2019年杜永兆等人[2]提出了一種多種群協(xié)方差學(xué)習(xí)的差分進(jìn)化算法，該算法將每一子種群賦予不同的變異策略，從而提高種群的多樣性，子種群之間通過(guò)協(xié)方差學(xué)習(xí)，建立一個(gè)溝通的橋梁.劉彬等人[3]針對(duì)遺傳算法的種群多樣性和局部搜索能力差的問(wèn)題，提出了多種群遺傳算法，多種群遺傳算法具有運(yùn)行時(shí)間短，搜索能力強(qiáng)的優(yōu)點(diǎn).申雨軒等人[4]提出了變搜索區(qū)域的多種群遺傳算法，采用種群搜索區(qū)域自適應(yīng)變化策略逐漸縮小搜索范圍，降低空間搜索消耗，提高搜索效率和最優(yōu)解精度.劉小龍[5]提出了改進(jìn)多元宇宙算法求解大規(guī)模實(shí)值優(yōu)化問(wèn)題，解決了代間宇宙信息溝通問(wèn)題.孫輝等人[6]提出了一種混合均值中心反向?qū)W習(xí)粒子群優(yōu)化算法，該算法對(duì)混合均值中心進(jìn)行反向?qū)W習(xí)，從而使得粒子探索更多搜索區(qū)域.在多種群方面，鄧先禮等人[7]提出了一種基于多種群的自適應(yīng)遷移PSO算法，每個(gè)子種群采用不同的加速因子，并通過(guò)歷史評(píng)估來(lái)指導(dǎo)個(gè)體遷移，從而實(shí)現(xiàn)種群間的協(xié)作.針對(duì)大規(guī)模優(yōu)化問(wèn)題，梁靜等人[8]提出了協(xié)同進(jìn)化動(dòng)態(tài)粒子群優(yōu)化算法，將此策略加入到動(dòng)態(tài)多種群粒子群優(yōu)化算法中，實(shí)驗(yàn)效果顯著提升.夏學(xué)文等人[9]提出了多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO算法，粒子不僅能夠根據(jù)自身狀態(tài)在多個(gè)尺度自適應(yīng)選擇，而且利用歷史信息指導(dǎo)種群逃離局部最優(yōu).Yuhua Li等人[10]提出了一種信息共享機(jī)制，使得粒子之間的相互作用就得到了充分的增強(qiáng)，大大提高了它們的搜索整個(gè)群體的信息能力.2014年M.R.Tanweer等人[11]提出了一種自調(diào)節(jié)粒子群優(yōu)化算法(Self Regulating Particle Swarm Optimization，簡(jiǎn)稱(chēng)SRPSO)，該算法能夠根據(jù)當(dāng)前粒子的現(xiàn)狀和對(duì)其他粒子最佳經(jīng)驗(yàn)的感知，從而調(diào)整搜索方向，充分利用群體信息，以最佳效果尋找最優(yōu)解.李朝華等人[12]則是將適應(yīng)度值好的粒子組成精英粒子群，普通種群與精英種群協(xié)同進(jìn)化，實(shí)現(xiàn)種群功能分配，以更好的收斂精度和收斂速度進(jìn)行全局搜索.Xin Jin等人[13]提出了基于距離的維數(shù)選擇算法，該算法這對(duì)大規(guī)模群體具有顯著優(yōu)勢(shì).胡成玉等人[14]提出了多種群協(xié)同的動(dòng)態(tài)多目標(biāo)粒子群算法，該算法同時(shí)利用多種群的競(jìng)爭(zhēng)協(xié)作關(guān)系，從而更好的求解多目標(biāo)問(wèn)題.蔡良偉等人[15]提出了多種群遺傳算法，多個(gè)種群直接通過(guò)相互競(jìng)爭(zhēng)和優(yōu)良個(gè)體共享，從而提高資源利用率，克服個(gè)體早熟，提高收斂性能.文獻(xiàn)[16]提出了自適應(yīng)動(dòng)態(tài)控制種群分組的自然計(jì)算方法，該方法采用高斯函數(shù)，擬合粒子運(yùn)動(dòng)曲線，從而達(dá)到自適應(yīng)分組的目的.

在這些方法中，收斂速度和全局最優(yōu)的問(wèn)題依然是一直在探索的關(guān)鍵問(wèn)題.種群規(guī)模大，全局搜索能力較強(qiáng)，但收斂速度就會(huì)降低，同時(shí)還會(huì)增加運(yùn)行負(fù)荷；種群規(guī)模小會(huì)減少運(yùn)行時(shí)間，收斂速度較快，但全局搜索能力又會(huì)下降，對(duì)于多峰問(wèn)題極易陷入局部最優(yōu)，導(dǎo)致算法早熟[17].因此，找到一個(gè)恰當(dāng)?shù)奶幚矸N群規(guī)模的問(wèn)題對(duì)自然計(jì)算方法就顯得格外重要.

為了解決這一問(wèn)題，本文提出了一種具有普適意義的多空間協(xié)同進(jìn)化(Multispace Coevolution，MSC)的自然計(jì)算方法，該方法與具體的進(jìn)化算法無(wú)關(guān)，因而適用于各種基于種群優(yōu)化的自然計(jì)算方法.MSC自然計(jì)算方法的子種群分為指導(dǎo)空間和進(jìn)化空間，進(jìn)化空間根據(jù)指導(dǎo)空間傳遞信息而進(jìn)化.將該策略應(yīng)用到3種不同的自然計(jì)算方法中，使用不同的測(cè)試函數(shù)來(lái)驗(yàn)證該策略的普適應(yīng)和有效性.

2 協(xié)同進(jìn)化

在MSC自然計(jì)算方法中，不是所有的粒子都同時(shí)進(jìn)化，而是有先后順序，指導(dǎo)空間對(duì)進(jìn)化空間進(jìn)行有意義指導(dǎo)，兩個(gè) 空間協(xié)同進(jìn)化.如圖1所示.大種群隨機(jī)劃分為多個(gè)小種群.

圖1 子種群分組Fig.1 Sub population grouping

指導(dǎo)空間有多個(gè)不同的等規(guī)模的小種群，不同的小種群之間互不干擾，各自進(jìn)化，并且按照原始的自然計(jì)算方法或者改進(jìn)的方法進(jìn)化，對(duì)于不同的自然計(jì)算方法會(huì)得到不同的信息傳遞方式，即指導(dǎo)空間如何將關(guān)于進(jìn)化方向的信息傳遞給進(jìn)化空間.本文以粒子群和遺傳算法為例，粒子群算法的空間信息傳遞方式是速度和適應(yīng)度值，遺傳算法的空間信息傳遞方式是最優(yōu)個(gè)體適應(yīng)度值，對(duì)進(jìn)化空間進(jìn)行有意義搜索，更快的找到全局最優(yōu)解.

2.1 指導(dǎo)空間

指導(dǎo)空間(Guiding space)是由個(gè)體的行為特征組成的信息單元，是群體的全局信息知識(shí)庫(kù).指導(dǎo)空間中的信息是每個(gè)子種群的行為經(jīng)驗(yàn)概括所得.然而，概括絕不是一代或者幾代所積累形成的，而是成百上千代的集合，每一代的經(jīng)驗(yàn)值都對(duì)進(jìn)化空間的對(duì)應(yīng)進(jìn)化代產(chǎn)生影響，從而指導(dǎo)其進(jìn)化的方向.指導(dǎo)空間的進(jìn)化方式依然按照原算法進(jìn)化.

指導(dǎo)空間中的小種群數(shù)目可以有多個(gè)，本文以分為3個(gè)子種群為例，每個(gè)子種群作為一個(gè)信息單元為進(jìn)化空間傳送信息.因此，在指導(dǎo)空間和進(jìn)化空間之間需要通信方式，該通信方式指定了一些操作，不同的群體智能算法因需要指定不同的操作，本文以粒子群和遺傳算法為例，粒子群算法采用的是每個(gè)子種群中最優(yōu)個(gè)體的適應(yīng)度值和速度作為空間信息傳遞方式，遺傳算法采用的是指導(dǎo)空間每個(gè)子種群的最優(yōu)個(gè)體替代進(jìn)化空間適應(yīng)度最劣的3個(gè)個(gè)體.

2.2 進(jìn)化空間

進(jìn)化空間(Evolutionary space)由另外剩余的小種群構(gòu)成.進(jìn)化空間中小種群的數(shù)量一般為1個(gè)，小種群的粒子數(shù)目可以和指導(dǎo)空間小種群數(shù)目相等也可以不相等.進(jìn)化空間通過(guò)空間信息傳遞方式得到指導(dǎo)空間的信息，利用這些信息指導(dǎo)進(jìn)化朝著最優(yōu)解的方向進(jìn)化.

進(jìn)化空間與指導(dǎo)空間的不同之處在于：其一，指導(dǎo)空間利用原算法的進(jìn)化方式進(jìn)化，而進(jìn)化空間則是在原算法中加入指導(dǎo)空間所傳遞的信息從而達(dá)到進(jìn)化的目的；其二，大種群分為若干個(gè)個(gè)數(shù)相等的子種群，其中1個(gè)子種群作為進(jìn)化空間單元，剩余作為指導(dǎo)空間單元；其三，指導(dǎo)空間要為進(jìn)化空間提供有關(guān)進(jìn)化方向的信息，即通信方式，這些通信方式或者是速度或者是位移或者是最優(yōu)值等等，根據(jù)具體的算法選擇合適的通信方式.

2.3 算法流程

多空間協(xié)同進(jìn)化的自然計(jì)算方法首先初始化種群的個(gè)體數(shù)目Size和選取算法的參數(shù)；然后，劃分子種群，并且給子種群分組，一組是指導(dǎo)空間，另一組是進(jìn)化空間；接著，指導(dǎo)空間的小種群按照原算法進(jìn)化規(guī)則進(jìn)化，并保留經(jīng)驗(yàn)概括所得的通信方式；最后，進(jìn)化空間根據(jù)信息傳遞方式，在原算法基礎(chǔ)上進(jìn)化.算法1是本文所提策略的偽碼表示.

算法1.MSC策略.

Step 1.初始化種群的數(shù)目Size，以及相應(yīng)算法的參數(shù)；

Step 2.劃分子種群Sizei(i=1，2，…，m).Sizej(j=1，2，…，m-1)作為指導(dǎo)空間小種群，Sizem作為進(jìn)化空間小種群；

Step 3.FNs=1；

Step 4.指導(dǎo)空間小種群進(jìn)化，并計(jì)算適應(yīng)度值；

Step 5.根據(jù)適應(yīng)度值獲得通信信息Infj(j=1，2，…，m-1)；

Step 6.進(jìn)化空間小種群根據(jù)Infj(j=1，2，…，m-1)進(jìn)化，并計(jì)算適應(yīng)度值；

Step 7.FNs = FNs + 1；

Step 8.判斷是否滿足終止條件，若不滿足，轉(zhuǎn)Step 4，若滿足，轉(zhuǎn)Step 9；

Step 9.結(jié)束.

3 試驗(yàn)及仿真測(cè)試

實(shí)驗(yàn)仿真平臺(tái)為Window7，Matlab2019b.本實(shí)驗(yàn)把MSC策略分別應(yīng)用到標(biāo)準(zhǔn)遺傳算法(GA)[18]、標(biāo)準(zhǔn)粒子群算法(PSO)[19]和改進(jìn)的粒子群算法EXPPSO(Exponential Decay Weight PSO)[20]中，得到MSCGA算法、MSCPSO算法和MSCEXPPSO算法，并與標(biāo)準(zhǔn)遺傳算法、標(biāo)準(zhǔn)粒子群算法和7個(gè)關(guān)于種群規(guī)模算法[2，3，4，7，10，11，13]做對(duì)比實(shí)驗(yàn).

近年來(lái)，優(yōu)化高維函數(shù)已經(jīng)成為優(yōu)化算法領(lǐng)域的研究熱點(diǎn).本實(shí)驗(yàn)采用國(guó)際通用的12個(gè)標(biāo)準(zhǔn)高維測(cè)試函數(shù)：F1～F12(如表1所示).F1～F4、F11、F12是高維單峰函數(shù)，僅有一個(gè)全局最優(yōu)點(diǎn)；F5～F7、F9、F10是高維多峰函數(shù)，這些測(cè)試函數(shù)具有許多局部最優(yōu)點(diǎn)，是優(yōu)化界中較難優(yōu)化的函數(shù).這些測(cè)試函數(shù)的全局最優(yōu)值為0，F(xiàn)8的維數(shù)不能少于4維，且全局最小值和維數(shù)有關(guān).由于部分測(cè)試函數(shù)有多個(gè)最優(yōu)點(diǎn)，因此，在尋優(yōu)過(guò)程中極易陷入局部最優(yōu).

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)
Table 1 Benchmark functions

測(cè)試函數(shù)維數(shù)可行解空間F1=∑Di=1xi21000[-100,100]nF2=∑D-1i=1[100(xi+1-x2i)2+(xi-1)2]1000[-5,10]nF3=(x1-1)2+∑Di=1i*(2xi2-xi-1)21000[-10,10]nF4=∑Di=1|xi|i+11000[-1,1]nF5=-a*exp-b1D∑Di=1xi2 -exp1D∑Di=1cos(cxi) +a+exp(1)a=20,b=0.2,c=2π1000[-32.768,32.768]nF6=∑Di=1(xi2-10*cos(2*π*xi)+10)1000[-5.12,5.12]nF7=∑Di=1xi24000-∏Di=1cosxii +11000[-600,600]nF8=∑D/4i=1[(x4i-3+10x4i-2)2+5(x4i-1-x4i)2+(x4i-2-2x4i-1)4+10(x4i-3-x4i)4]1000[-4,5]nF9=sin2(πω1)+∑D-1i=1(ωi-1)2[1+10sin2(πωi+1)]+(ωD-1)2[1+sin2(2πωD)]ωi=1+ωi-141000[-10,10]nF10=418.9829D-∑Di=1xisin(|xi|)1000[-500,500]nF11=∑Di=1ix2i1000[-10,10]nF12=∑Di=1x2i+(∑Di=10.5ixi)2+(∑Di=10.5ixi)41000[-5,10]n

3.1 粒子群相關(guān)實(shí)驗(yàn)對(duì)比

3.1.1 MSC策略與相關(guān)粒子群算法的實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)中，PSO、MSCPSO、EXPPSO和MSCEXPPSO的參數(shù)設(shè)置為：維數(shù)D=1000，種群規(guī)模均為Size=50，應(yīng)用MSC策略的指導(dǎo)空間每個(gè)子種群規(guī)模Sizei=10(i=1，2，3)，進(jìn)化空間子種群規(guī)模size=20，學(xué)習(xí)因子c1=c2=2，慣性權(quán)重ωmax=0.9，ωmin=0.4，指數(shù)衰減參數(shù)e=2.71828.每個(gè)算法獨(dú)立運(yùn)行20次，進(jìn)化迭代1000次.在進(jìn)化過(guò)程中，本文提出新的速度更新公式.MSCPSO的進(jìn)化空間速度使用公式(1)，MSCEXPPSO的進(jìn)化空間速度使用公式(2)，其他參數(shù)在迭代過(guò)程中不會(huì)發(fā)生改變.PSO和MSCPSO的指導(dǎo)空間使用速度及位移公式(3)，EXPPSO和MSCEXPPSO的指導(dǎo)空間使用速度及位移公式(4).

vt+1=w*(1/f1*v1+1/f2*v2+1/f3*v3)+c1*r1(pbest-x)+c2*r2(gbest-x)

(1)

vt+1=e-1*(1/f1*v1+1/f2*v2+1/f3*v3)+c1*r1(pbest-x)+c2*r2(gbest-x)

(2)

(3)

(4)

其中，f1，f2，f3分別是指導(dǎo)空間3個(gè)小種群的最佳適應(yīng)度值；v1、v2、v3分別是指導(dǎo)空間3個(gè)小種群中最佳粒子對(duì)應(yīng)的速度；pbest和gbest代表進(jìn)化空間的個(gè)體最優(yōu)和群體最優(yōu).

各算法對(duì)12個(gè)測(cè)試函數(shù)分別執(zhí)行20次，其平均結(jié)果及標(biāo)準(zhǔn)方差如表2所示.在優(yōu)化這12個(gè)測(cè)試函數(shù)時(shí)，MSCPSO算法和MSCEXPPSO算法較PSO算法和EXPPSO算法相比，在大部分測(cè)試函數(shù)中都能夠接近全局最優(yōu)，尤其是在測(cè)試函數(shù)F4、F5、F7上，MSCPSO算法和MSCEXPPSO算法在誤差允許的范圍內(nèi)已找到全局最優(yōu)解.與PSO和EXPPSO相比，MSCPSO算法和MSCEXPPSO算法的標(biāo)準(zhǔn)方差遠(yuǎn)低于其他算法.

表2 各PSO算法對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果
Table 2 Optimization results of each PSO algorithm for 12 benchmark functions

PSOMSCPSOEXPPSOMSCEXPPSOF14.7408e+05±6.0567e+04956.7405±537.71295.2279e+05±5.9804e+04934.7853±568.2368F26.8907e+06±1.0109e+062.0748e+05±2.2986e+048.4306e+06±1.5060e+062.1517e+05±2.1297e+04F31.1270e+08±2.1186e+076.3175e+03±4.5550e+031.3970e+08±3.0455e+076.6451e+03±5.5013e+03F42.4810e-07±6.6946e-070.0125± 0.03491.4728e-05±1.8879e-050.0588±0.0569F517.2093±0.48123.2987±0.763117.1461±0.36233.1378±0.5346F69.7236e+03±467.2895636.1493±406.70261.0717e+04±201.7529509.1434±255.0011F74.3360e+03±384.38178.0635±3.97364.5950e+03±505.400011.1476±5.2572F89.3610e+04±1.6402e+04529.9684±132.32701.1438e+05±1.5873e+04489.4651±172.9301F91.7026e+04±1.5059e+0398.1293±12.67282.0139e+04±1.6469e+03101.6254±12.6604F103.4472e+05±7.7329e+033.9481e+05±2.3389e+033.8024e+05±3.8340e+033.9321e+05±3.6025e+03F112.2562e+06±1.5279e+054.4887e+03±2.6061e+032.5115e+06±2.8375e+055.1138e+03±2.0446e+03F121.2171e+04±3.0807e+031.0767e+06±3.5088e+066.9048e+03±2.0376e+031.9944e+05±4.2817e+05

圖2 各PSO算法對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)優(yōu)化的收斂曲線Fig.2 Convergence curves of PSO algorithms for 12 benchmark functions

圖2是各PSO算法在12個(gè)測(cè)試函數(shù)F1～F12的收斂比較圖.橫軸代表進(jìn)化次數(shù)，縱軸代表平均適應(yīng)度值.從圖中可以清楚的看到，使用多空間協(xié)同進(jìn)化策略的算法比未使用該策略的算法具有更好的尋優(yōu)能力.

根據(jù)收斂曲線走勢(shì)可以清晰的觀察到，MSCPSO和MSCEXPPSO在測(cè)試函數(shù)F1，F(xiàn)2，F(xiàn)3，F(xiàn)5，F(xiàn)6，F(xiàn)7，F(xiàn)8，F(xiàn)9，F(xiàn)11中平均大概進(jìn)化200次左右，函數(shù)曲線保持水平，不再有下降趨勢(shì)，說(shuō)明算法陷入局部最優(yōu)，這是PSO算法本身的性質(zhì)所決定的；而PSO和EXPPSO在上述測(cè)試函數(shù)中大概進(jìn)化至50代左右，算法陷入局部最優(yōu)，說(shuō)明應(yīng)用MSC策略之后，算法具有了更好的全局搜索能力.但在測(cè)試函數(shù)F4和F10中，MSCPSO和MSCEXPPS的尋優(yōu)效果遠(yuǎn)不及PSO和EXPPSO，這是由于F4是一個(gè)連續(xù)但不可微的函數(shù)，因此分種群后指導(dǎo)空間的種群不能為進(jìn)化空間提供較優(yōu)的指導(dǎo)方向；F10是一個(gè)功能復(fù)雜且有許多局部最小值，因此，極易使算法陷入局部最優(yōu).

3.1.2 MSCPSO與其他4個(gè)算法的實(shí)驗(yàn)分析結(jié)果

維度選擇的距離粒子群優(yōu)化算法(PSO with distance based dimension selection，簡(jiǎn)稱(chēng)PSODDS)[13]、具有信息共享機(jī)制的競(jìng)爭(zhēng)與合作粒子群算法(the competitive and cooperative PSO with information sharing mechanism，簡(jiǎn)稱(chēng)CCPSO-ISM)[10]、自調(diào)節(jié)粒子群算法(Self Regulating Particle Swarm Optimization，簡(jiǎn)稱(chēng)SRPSO)[11]和多種群的自適應(yīng)遷移 PSO 算法(Multi-population based self-adaptive migration PSO，簡(jiǎn)稱(chēng)MSMPSO)[7]，這4個(gè)算法都是對(duì)種群規(guī)模以及粒子維度進(jìn)行優(yōu)化的最新且具有代表性的算法.為了與這4個(gè)算法參數(shù)設(shè)置一致，MSCPSO的種群規(guī)模是30個(gè)粒子，每個(gè)粒子30維，迭代進(jìn)化10000次，實(shí)驗(yàn)重復(fù)30次取平均值.“-”表示算 法在指定測(cè)試函數(shù)中參考文獻(xiàn)沒(méi)有數(shù)據(jù)，結(jié)果如表3所示.

表3 MSCPSO與其他種群優(yōu)化算法在30維時(shí)的實(shí)驗(yàn)結(jié)果對(duì)比
Table 3 Comparison of experimental results between MSCPSO and other population optimization algorithms in 30 dimensions

PSODDSCCPSO-ISMSRPSOMSMPSOMSCPSOF18.45e+01±1.46e+023.78e-11±6.58e-111.31e+02±2.01e+024.5441±2.52343.7256±3.2303F26.05e+01±2.95e+006.37e+01±2.32e+016.95e+01±1.90e+0156.6348±39.07651.641±1.0634F3---5.4099±3.01401.6646±0.5473F4---6.51e-10±7.95e-100.0141±0.0094F52.09e+01±4.61e-022.09e+01±4.06e-022.10e+01±2.91e-023.9791±0.67313.0145±0.4534F61.62e+02±3.56e+013.91e+01±1.34e+015.60e+01±1.46e+0135.6772±8.79812.9239± 1.5589F77.63e+01±4.89e+011.17e-01±4.60e-029.07e+01±6.78e+011.0018±0.11011.3903±0.1790F8---1.1871±0.68001.1393±0.9634F9---1.1053±0.56042.6253±0.2563F102.00e+03±4.55e+021.40e+03±3.17e+021.37e+03±2.20e+024.7109e+03±949.34517.6800e+03±594.6053F11---2.0574±1.65790.8960±0.5266F12---1.6954±0.797016.4850±8.4478

MSCPSO在F2、F3、F5、F6、F8和F11這6個(gè)測(cè)試函數(shù)中取得的結(jié)果要優(yōu)于其他4個(gè)算法.MSCPSO將種群分為指導(dǎo)空間和進(jìn)化空間，進(jìn)化空間在指導(dǎo)空間的指引下進(jìn)行搜索，因此，其在多峰函數(shù)中的效果更佳.而PSODDS，CCPSO-ISM，SRPSO并未賦予每個(gè)粒子以不同的功能，導(dǎo)致粒子在搜索過(guò)程中易陷入局部最優(yōu)；采用多種群的MSMPSO在4個(gè)算法中的適應(yīng)度值較優(yōu)，這與本文所提出的算法有異曲同工之妙，因此，從側(cè)面證明了多空間協(xié)同進(jìn)化策略的有效性和實(shí)用性.

3.2 遺傳算法相關(guān)實(shí)驗(yàn)對(duì)比

3.2.1 MSC策略與相關(guān)遺傳算法實(shí)驗(yàn)結(jié)果分析

GA和MSCGA的參數(shù)設(shè)置為：交叉概率Pc=0.8，變異概率Pm=0.02，維數(shù)D=1000，種群規(guī)模Size=50.MSCGA的指導(dǎo)空間每個(gè)子種群規(guī)模Sizei=10(i=1，2，3)，進(jìn)化空間子種群規(guī)模size=20.每個(gè)算法獨(dú)立運(yùn)行20次，進(jìn)化迭代10000次.指導(dǎo)空間與進(jìn)化空間之間的通信方式采用指導(dǎo)空間最優(yōu)個(gè)體取代進(jìn)化空間適應(yīng)度值最劣的3個(gè)個(gè)體.

在12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)中的測(cè)試結(jié)果如表4所示.GA算法與MSCGA算法相比，在F1、F2、F3、F5、F7、F8、F10、F11、F12這9個(gè)測(cè)試函數(shù)中，MSCGA表現(xiàn)出明顯的優(yōu)勢(shì)，在其他3個(gè)測(cè)試函數(shù)中MSCGA表現(xiàn)較優(yōu)，這也證明，在遺傳算法中選擇的通信策略有待提高.總之，MSCGA算法有較低的標(biāo)準(zhǔn)方差，證明應(yīng)用MSC策略的算法具有更好的穩(wěn)定性.

圖3是12個(gè)測(cè)試函數(shù)F1～F12的收斂比較圖.橫軸代表進(jìn)化次數(shù)，縱軸代表平均適應(yīng)度值.從圖中可以清楚的看到MSC策略?xún)?yōu)勢(shì).MSCGA幾乎在每個(gè)測(cè)試函數(shù)中進(jìn)化迭代10000次 之后均有繼續(xù)下降的趨勢(shì)，尤其在F2、F5、F6、F10最為明顯，在其他測(cè)試函數(shù)中也有緩慢的下降趨勢(shì)，說(shuō)明算法沒(méi)有被局部最優(yōu)值束縛.而GA在絕大部分函數(shù)中進(jìn)化100次左右陷入局部最優(yōu).這更加驗(yàn)證了改進(jìn)后的算法具有更強(qiáng)的全局搜索能力.

表4 GA算法對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果
Table 4 Optimization results of 12 benchmark functions

GAMSCGAF17.0450e+04±2.6740e+035.5516e+04±3.0685e+03F21.4381e+06±1.6934e+059.2895e+05±1.0614e+05F36.7909e+06±4.8759e+052.7244e+06±14.0154e+05F41.7129e-15±3.0166e-092.0026e-14±5.2458e-10F59.4205±0.16659.1100±0.2004F67.5555e+03±255.94247.9795e+03±98.3462F7616.7508±28.0638491.9251±37.2226F89.3112e+03± 601.99037.2109e+03±631.5110F93.5240e+03±344.08363.1303e+03±414.9190F103.1636e+05±2.6643e+033.1301e+05±1.7698e+03F113.2396e+05±1.4102e+042.3836e+05±1.7070e+04F129.7129e+03±635.32424.1983e+03±908.9310

3.2.2 MSCGA與其他3個(gè)算法的實(shí)驗(yàn)對(duì)比分析

多種群協(xié)方差學(xué)習(xí)差分進(jìn)化(MCDE)算法[2]、多種群遺傳算法(MGA)[3]、變區(qū)域多種群遺傳算法(VRMGA)[4]這3個(gè)算法均是關(guān)于多種群算法，且具有一定的代表性.為了保證實(shí)驗(yàn)對(duì)比的可信度，將MSCGA的實(shí)驗(yàn)參數(shù)分別參考文獻(xiàn)[2- 4]進(jìn)行設(shè)置，對(duì)比結(jié)果如表5所示.采用MSC策略的遺傳算法在8個(gè)測(cè)試函數(shù)中取得了最佳效果，在剩余3個(gè)測(cè)試函數(shù)中雖然沒(méi)有取得最佳，但是與最優(yōu)值在誤差允許的范圍內(nèi)基本一致.進(jìn)化空間在指導(dǎo)空間的作用下完成有目的的搜索，大大提高了實(shí)驗(yàn)結(jié)果的收斂精度和速度，使個(gè)體在多空間協(xié)同作用下向最優(yōu)解進(jìn)化.

圖3 各GA算法對(duì)12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)優(yōu)化的收斂曲線Fig.3 Convergence curves of GA algorithms for 12 benchmark functions

表5 與其他遺傳算法的實(shí)驗(yàn)結(jié)果對(duì)比
Table 5 Comparison of experimental results with other GA

算法函數(shù)最優(yōu)值F10F23.19E-10±7.12E-10MCDEF52.09E+01±4.21E-02(D=30)F62.28E+01±4.27E+00F71.52E-03±4.11E-03F102.12E+03±1.34E+03MGABranin0.39791(D=2,3)Hartmanl-3.86266VRMGA(D=2)Schaffer6(最優(yōu)值為最大值)1Shubert-186.7302Schaffer10F10F22.20E+01±1.43E+00F56.50E-03±1.40E-03F61.80E-03±4.48E-04F72.20E-03±4.90E-03MSCGAF109.73E+02±4.12E+02Branin0.3979Hartmanl-3.8627Schaffer6(最優(yōu)值為最大值)1Shubert-186.6944Schaffer10.0072

3.3 顯著性檢驗(yàn)

為了驗(yàn)證MSC策略的有效性，對(duì)MSCPSO、MSCEXPPSO、MSCGA和其他算法在D=1000時(shí)得到的結(jié)果逐一進(jìn)行顯著性檢驗(yàn).由于不能夠確定各算法多次優(yōu)化同一函數(shù)的結(jié)果服從分布的類(lèi)型，因此采用非參數(shù)檢驗(yàn)的方法，這里選用Mann Whitney檢驗(yàn)方法，顯著水平α=0.05.表6詳細(xì)列出了4種算法的檢驗(yàn)數(shù)據(jù)，這里以PSO列為例說(shuō)明表中各數(shù)據(jù)的意義：PSO列與F1行交叉的數(shù)據(jù)為“0.000↑”，“0.000”為Mann Whitney檢驗(yàn)的p值，“↑”表示PSO在F1上的運(yùn)行數(shù)據(jù)的秩均值大于MSCPSO的運(yùn)行數(shù)據(jù)的秩均值；若為“↓”，則表示PSO在此函數(shù)上的運(yùn)行數(shù)據(jù)的秩均值小于MSCPSO的運(yùn)行數(shù)據(jù)的秩均值；若為“→”，則表示兩種算法的運(yùn)行數(shù)據(jù)的秩均值相等；GA列是與MSCGA的Mann Whitney檢驗(yàn)數(shù)據(jù)；EXPPSO列是與MSCEXPPSO的Mann Whitney檢驗(yàn)數(shù)據(jù).表中的better行、same行和worse行分別表示在顯著水平為0.05下，12個(gè)測(cè)試函數(shù)中MSCPSO優(yōu)于PSO、與PSO無(wú)差和劣于PSO的函數(shù)的個(gè)數(shù).從表6中，可以清晰的看到，在12個(gè)測(cè)試函數(shù)上，MSCPSO、MSCGA、MSCEXPPSO和其他算法的綜合性能的比較結(jié)果，應(yīng)用本文所提MSC策略的算法明顯占優(yōu).

4 結(jié) 論

傳統(tǒng)的自然計(jì)算方法中，種群按照循規(guī)蹈矩的方式進(jìn)化.對(duì)某些特定群體智能算法的改進(jìn)，研究較多的有關(guān)于參數(shù)的修改，有關(guān)于拓?fù)浣Y(jié)構(gòu)的修改等等.但將種群分組思想應(yīng)用到自然計(jì)算方法中，利用指導(dǎo)空間對(duì)進(jìn)化空間的指導(dǎo)來(lái)尋找最優(yōu)解還有上升的余地.因此，本文提出了子種群分組策略，實(shí)現(xiàn)了種群在進(jìn)化過(guò)程中的信息指導(dǎo)與干預(yù).該方法與具體的群體智能算法無(wú)關(guān)，適用于所有的自然計(jì)算方法，具有普適性和通用性.因此，可以方便的將本策略應(yīng)用至各種群體智能算法中，來(lái)提高原方法的收斂精度和收斂效率.在PSO和GA的實(shí)驗(yàn)結(jié)果表明，基于MSC的PSO算法，在收斂精度和收斂速度方面都有大幅度的提高；基于MSC的GA算法，雖然沒(méi)有PSO算法改進(jìn)效果明顯，但也有一定程度的提升，這與本文所選的通信方式和原算法的性能有關(guān).而與關(guān)于種群改進(jìn)的其他4個(gè)算法相比，也表現(xiàn)出較好的優(yōu)勢(shì).后期將嘗試完善通信方式，以求得更理想的結(jié)果.

表6D=1000，Mann Whitney檢驗(yàn)數(shù)據(jù)
Table 6D=1000，Mann Whitney test data

PSOMSMPSOGAEXPPSOF10.000↑0.000↑0.010↑0.000↑F20.000↑0.000↓0.025↑0.000↑F30.000↑0.000↑0.000↑0.000↑F40.000↑0.000↓0.036↑0.000↓F50.000↑0.000↑0.957↓0.000↑F60.000↑0.000↑0.000↓0.000↑F70.000↑0.000↑0.152↑0.000↑F80.000↑0.000↑0.020↑0.000↑F90.000↑0.000↑0.000↓0.000↑F100.000↑0.000↓0.000↑0.000↓F110.000↑0.000↑0.011↑0.000↑F120.000↑0.000↓0.552↓0.000↓Bet-ter12879Worse0423Same0030