交叉反向學習和同粒社會學習的粒子群優(yōu)化算法

張新明，康 強，王 霞，程金鳳

(1.河南師范大學 計算機與信息工程學院，河南 新鄉(xiāng) 453007； 2.河南省高校計算智能與數(shù)據(jù)挖掘工程技術研究中心，河南 新鄉(xiāng) 453007)

交叉反向學習和同粒社會學習的粒子群優(yōu)化算法

張新明1,2*，康 強1，王 霞1，程金鳳1

(1.河南師范大學 計算機與信息工程學院，河南 新鄉(xiāng) 453007； 2.河南省高校計算智能與數(shù)據(jù)挖掘工程技術研究中心，河南 新鄉(xiāng) 453007)

針對社會學習粒子群優(yōu)化(SLPSO)算法存在的優(yōu)化效率低、收斂速度慢等問題，提出了一種改進的SLPSO算法，即基于交叉反向學習和同粒社會學習的PSO算法(CPPSO)。首先，將最優(yōu)解隨機縱向交叉與一般反向學習以及隨機反向學習構建交叉反向學習；然后，以此交叉反向學習策略更新種群中的最優(yōu)粒子位置，增強探索能力，并克服SLPSO中最優(yōu)粒子無更新導致效率低下的缺點；最后，對于非最優(yōu)粒子，與SLPSO采用基于維的社會學習不同，均采用新型基于粒子的社會學習機制，在提高全局搜索能力同時，更提高開采能力和搜索效率。在一組不同維基準函數(shù)上優(yōu)化的實驗結果表明，CPPSO的優(yōu)化性能、搜索效率和普適性大幅度領先于SLPSO和其他先進的PSO改進算法，如交叉搜索PSO(CSPSO)算法、自我調(diào)節(jié)的PSO(SRPSO)算法、異構綜合學習的PSO(HCLPSO)算法和反向學習和局部學習能力的PSO(RLPSO)算法。

智能優(yōu)化算法；粒子群優(yōu)化算法；社會學習；反向學習

0 引言

(1)

(2)

其中：c1和c2是學習因子；r1和r2是區(qū)間[0,1]中兩個獨立的均勻分布隨機變量；d表示維的序號;t是當前迭代次數(shù)。

雖然PSO被廣泛應用到諸多領域解決了許多問題，但研究發(fā)現(xiàn)，PSO存在早熟收斂、易陷于局部最優(yōu)、種群多樣性丟失等問題, 導致這些問題的原因來自PSO的更新方式。從式(1)可知，種群中的每個粒子都向著兩個最優(yōu)位置趨近，使得PSO快速收斂，而且采用逐個粒子動態(tài)更新最優(yōu)解的方式更加劇了快速收斂；當最優(yōu)粒子為局部最優(yōu)點時，整個粒子群趨向局部最優(yōu)，尤其在PSO解決多個局部最優(yōu)值的問題時，經(jīng)過一定的迭代次數(shù)之后粒子集中于局部最優(yōu)值附近，導致種群多樣性降低，不能跳出局部最優(yōu)點。針對PSO存在的缺點，許多研究人員對PSO搜索方式進行改進以便提高其優(yōu)化性能[2-5]，其中不乏借助不同的學習策略來獲得算法中探索能力和開采能力的平衡，提高其性能；文獻[6]針對PSO的早熟收斂問題，連續(xù)使用5次變異策略，提出了一種增強領導者的PSO算法；文獻[7]將PSO與兩種人類最好的學習策略有機融合，提出了一種自我調(diào)節(jié)的PSO算法(Self-Regulating PSO, SRPSO)；文獻[8]將綜合學習策略與PSO結合，提出了一種異構綜合學習的PSO(Heterogeneous Comprehensive Learning PSO, HCLPSO) 算法；文獻[9]通過協(xié)同反向學習與局部學習的行為，提出了一種具有反向學習和局部學習能力的PSO算法(Reverse learning and Local learning PSO, RLPSO)；文獻[10]將局部擾動學習和高斯子空間學習的兩種學習策略與改進的骨干PSO算法融合，提出了多策略并行學習的異構PSO算法；文獻[11]采用帶有擾動精英的反向學習和對慣性權重的改進，提出了擾動的精英反向學習PSO算法；文獻[12]將社會學習機制引入PSO算法中，得到了社會學習PSO(Social Learning PSO, SLPSO)算法, 不同于傳統(tǒng)的PSO改進算法，SLPSO算法中的每個粒子采用向當前種群中更優(yōu)粒子(稱為示范者)學習的機制來更新解，提高了種群的多樣性和全局搜索能力。雖然SLPSO算法提高了PSO的優(yōu)化性能，但在解決高維或者復雜的優(yōu)化問題時仍然存在搜索能力不足、收斂速度慢、普適性較差、搜索效率低等缺點。

針對這些問題，本文提出了一種改進的SLPSO算法，即基于交叉反向學習和同粒社會學習的PSO(Cross opposition learning and Particle-based social learning PSO, CPPSO)算法。對粒子群中的非最優(yōu)粒子均采用基于粒子的社會學習新機制，在提高全局搜索能力同時，更提高局部搜索能力，加快收斂；對粒子群中的最優(yōu)粒子采用交叉反向學習機制來提高全局搜索能力，二者協(xié)作共建CPPSO，以便克服SLPSO搜索效率低和收斂慢等的缺點。

1 社會學習粒子群算法

對于傳統(tǒng)PSO及其大多數(shù)改進算法，粒子都是基于歷史信息(包括整個群體發(fā)現(xiàn)的最優(yōu)解gbest和個體發(fā)現(xiàn)的最優(yōu)解pbest)進行更新的，而在SLPSO中，每個粒子向當前種群中的更優(yōu)粒子(稱為示范者)學習。每個粒子的每一維都來自不同的示范粒子，極大地提高了種群的多樣性，避免了PSO存在的早熟收斂、種群多樣性丟失等的缺陷。SLPSO與5個典型的改進PSO在包括平移和旋轉函數(shù)的40個低維函數(shù)上和與5個最先進的大規(guī)模優(yōu)化算法在7個高維函數(shù)上進行了比較。結果表明SLPSO算法在解決低維問題時表現(xiàn)優(yōu)異，且在解決大規(guī)模問題上也很有前途。算法具體流程如下：

步驟1 初始化包含N個粒子的群體P(t)，其中，N是群體大小。種群大小N和社會影響因子ε由式(3)決定。P(t)中的每個粒子保持一個隨機初始化的決策向量(行為向量)Xi(t)，其代表了優(yōu)化問題的候選解。

(3)

步驟2 適應度值評估。每個粒子將被分配從目標函數(shù)f(X)計算的適應度值。

步驟3 依據(jù)適應度值對粒子群由差至優(yōu)排序，即排在第一的粒子適應度值是最差的，排在最后的粒子適應度值是最優(yōu)的。

步驟4 社會行為學習。每個粒子(除了最優(yōu)粒子外)將通過從具有更好適應度值的粒子(示范粒子)學習來矯正其行為，最優(yōu)粒子不作更新。對所有非最優(yōu)粒子進行行為矯正ΔXi, j(t+1)，每維更新包含三個部分。第一部分：與標準PSO算法中的慣性分量相同，但慣性權重采用0～1的隨機數(shù)r1。第二部分：模仿成分。取代標準PSO中的向pbest學習，粒子i向比它優(yōu)秀的任何示范者學習。第三部分：社會影響成分。取代標準PSO中的向gbest學習，粒子i向當前群中所有粒子的平均行為學習，即集體行為，其中r2和r3都是0～1的隨機數(shù)，k是每一維隨機選擇的粒子標號,j表示維的標號。

ΔXi, j(t+1)=r1·ΔXi, j(t)+r2·Ii, j(t)+r3·ε·Ci, j(t)

(4)

(5)

步驟5 當滿足終止條件時，則輸出最終解，算法結束；否則轉到步驟2。

2 交叉反向學習和社會同粒學習的PSO

2.1 SLPSO算法存在的問題

雖然SLPSO將社會學習機制引入到PSO中，增加了全局搜索能力，提升了優(yōu)化性能，但存在如下問題：

1)從整個算法流程可以看出，SLPSO每一代僅對非最優(yōu)粒子進行更新，而最優(yōu)粒子未參與解的更新中，從而不僅導致搜索效率低下，而且算法的搜索能力受到影響。

2)從式(4)可以看出，非最優(yōu)粒子的更新采用基于維的社會學習方式，即每一維都隨機選擇示范粒子對應的維和整個粒子群對應維的平均值進行更新，如果需要更新D維，那就需要選擇D個示范粒子用來學習，這種基于維的更新方式是從示范粒子選擇一維學習，雖然能增加種群的多樣性，但開采能力受到影響導致收斂速度慢，另外，一個示范粒子整體值得學習，不一定某一維就是較優(yōu)的，有可能是較差的，因此這種方式不僅限制優(yōu)化性能的提升，而且難以進行并行化處理。

3)雖然SLPSO更新方式不同于式(1)，但式(4)與標準的PSO更新方式一樣都由三項構成，且SLPSO每次更新都要計算整個種群每一維的均值，故增加了計算復雜度。

基于上述原因，SLPSO在解決復雜問題可能仍然存在搜索能力不足、收斂速度慢和搜索效率低等缺點，具有較大改進的空間。

依據(jù)現(xiàn)代智能優(yōu)化理論，隨機優(yōu)化算法找到問題的最優(yōu)解主要基于兩種能力，即探索能力和開采能力。其中探索能力即全局搜索能力，探索整個搜索空間以尋找有前途的區(qū)域的能力；開采能力即局部搜索能力，在所識別的有前途的區(qū)域中微調(diào)搜索最優(yōu)解的能力。二者互相矛盾和互相牽制，過分強調(diào)一方必定會損害另一方，只有當找到探索和開采過程之間的適當平衡時，可以獲得算法的良好優(yōu)化性能。因此，在基于種群的進化算法中，重要的是獲得在搜索空間中的探索與開采之間的良好平衡。

本文針對SLPSO存在的問題和現(xiàn)代智能優(yōu)化理論，提出了一種基于交叉反向學習和同粒社會學習的PSO算法(CPPSO)。首先，將基于粒子的社會學習原理運用到粒子搜索中，以整體的全維方式學習示范粒子，在提高探索能力同時，更增強開采能力，克服了SLPSO基于維的社會學習方式存在的缺點；其次，對于種群中最優(yōu)個體，選擇交叉反向學習機制，不僅提高種群的多樣性和探索能力，而且使其探索能力與同粒社會機制的開采能力達到平衡，由此提高了搜索效率和整體的優(yōu)化性能。

2.2 同粒社會學習

社會學習在社會動物的行為學習中起著重要的作用。與個人學習相反，社會學習的優(yōu)點是允許個人從他人行為中學習，而不會導致個體反復實驗引起的昂貴成本。為了解決SLPSO基于維的社會學習存在的問題，本文提出了新的社會學習策略，即同粒社會學習策略。所謂同粒社會學習，即從比自己較優(yōu)的粒子群體中隨機挑選出一個粒子，供自己學習，所有維的學習都來自同一示范粒子，這就是同粒的含義。在同粒社會學習中，每次迭代后都依據(jù)適應度值按照降序對整個粒子群進行排序，也就是說排在前面的個體一定比后面的個體優(yōu)秀，是后面?zhèn)€體的示范者，越是后面的粒子供學習的示范粒子越多。基于同粒社會學習粒子速度與位置更新方式見式(6)和式(7)：

(6)

(7)

其中：pbestk為隨機選擇的第k個較優(yōu)粒子的個體歷史最優(yōu)位置，ω為慣性權重因子，c1為認知因子，i表示當前粒子的序號。這里k是從多個較優(yōu)粒子中隨機選取的序號，如果k等于當前粒子的序號i時，同粒社會學習的PSO就是標準PSO的認知模型，表示學習自身的過去經(jīng)驗；如果k等于最優(yōu)粒子序號時，就是標準PSO的社會模型，表示向種群的最優(yōu)者學習。與SLPSO速度更新方式的式(4)相比，式(6)只有兩項，更加簡潔，而且每一維的更新都來自第k個示范粒子。因為第一個粒子是最優(yōu)粒子，它沒有學習的示范者，故每個非最優(yōu)粒子(從第2個粒子開始到最后一個粒子)從比自己優(yōu)秀的粒子群里隨機選擇一個優(yōu)者學習，提高自身的搜索能力，克服了SLPSO存在的缺點。同粒社會學習策略的偽代碼見算法1。

算法1 同粒社會學習。

fori=2 toNdo

從多個示范粒子中隨機選取一個示范粒子k；

每一維都執(zhí)行式(6)和式(7)；

end for

其中:慣性權重w=1-t/M，這里M為最大迭代次數(shù)，ω采用動態(tài)調(diào)整方式，不用人工設置，以便提高算法的可操作性。從算法1可以看出：與PSO相比，CPPSO是隨機選擇一個優(yōu)者學習，這增加了群體的多樣性和提高了探索能力。因為都整體向著較優(yōu)者趨近，與SLPSO相比，更提高了開采能力，但多樣性不足。

2.3 交叉反向學習

正如上文所述，基于粒子的社會學習方式增加了開采能力，但降低了種群的多樣性，影響探索能力。因此為了平衡探索與開采，需進一步提高種群的多樣性，也為了充分發(fā)揮每一個粒子的作用，提高效率，將交叉反向學習策略用于最優(yōu)粒子的更新中。首先介紹3個概念：一般反向學習、隨機反向學習和最優(yōu)解隨機交叉。

(8)

式中：ad和bd分別表示X第d維的下界和上界。

(9)

其中：ad和bd同樣表示粒子的下、上邊界，rand表示[0, 1]間的均勻分布隨機數(shù)。

(10)

pc采用自適應線性下降的方法如式(11)所示：

pc=Cmax-(Cmax-Cmin)·t/M

(11)

其中：Cmax和Cmin分別表示最大交叉概率和最小交叉概率。為了進一步提高種群的多樣性，對于全局最優(yōu)個體，采用交叉反向學習機制，更有利于提高種群的多樣性。即在搜索前期采用隨機反向學習，在搜索后期采用自身隨機交叉機制與一般反向學習的交叉，提高算法的種群多樣性。在搜索后期中，具體操作方式是當隨機產(chǎn)生的值小于等于0.5時，采用最優(yōu)解隨機交叉，否則采用一般反向學習。這里交叉概率采用自適應方式，即隨著迭代次數(shù)的增加，交叉概率由大變小，前期交叉概率大，以便利于搜索全局最優(yōu)解，后期交叉概率小，有利于提高收斂速度。交叉反向學習的偽代碼見算法2。

算法2 交叉反向學習。

ift>M/2

//迭代后期

ifrand<=0.5

按照交叉概率pc產(chǎn)生隨機維；

并執(zhí)行最優(yōu)解隨機交叉式(10)；

else

執(zhí)行一般反向學習式(8);

end if

else

//迭代前期

執(zhí)行隨機反向學習式(9)；

end if

從算法2看出，最優(yōu)解隨機交叉屬于位置交叉，而反向學習之間以及與前者都屬于時間交叉，這種空間與時間交叉的有機融合極大地保證了其探索與同粒社會學習的開采達到良好的平衡。所以最優(yōu)粒子的交叉反向學習不僅是發(fā)揮其搜索作用，提高搜索效率之舉，更是同粒社會學習機制所必需的。

2.4 CPPSO算法

將同粒學習策略和交叉反向學習方案有機融合，構建CPPSO算法，使得探索與開采得到良好的平衡，搜索性能得到提升。CPPSO算法主流程如圖1所示。

圖1 CPPSO算法主流程Fig. 1 Main flow of CPPSO

3 實驗結果與分析

為了驗證CPPSO算法的有效性，在一組不同維的基準函數(shù)上進行對比算法的優(yōu)化實驗。表1中給出了6個測試函數(shù)的信息。它們包括單峰函數(shù)如f1～f3，多峰函數(shù)如f4～f6，函數(shù)的維度選擇包括低高維(30維)、中高維(100維)和高高維(200維，這種維數(shù)優(yōu)化問題目前文獻較少討論)，不同的維度選擇可以增加尋優(yōu)難度，以便驗證CPPSO的普適性和處理各種復雜優(yōu)化問題的能力。

3.1 對比算法與參數(shù)設置

在實驗中，不僅將CPPSO測試結果與SLPSO[12]測試結果進行比較，還與其他4種最近提出的、優(yōu)秀的PSO改進算法的優(yōu)化結果進行對比。這些對比算法分別為CSPSO[5]、SRPSO[7]、HCLPSO[8]和RLPSO[9]，在它們對應的文獻中已經(jīng)證明，它們的性能大幅度領先于原始PSO和其先前的改進版，具有很好的代表性和可比性。本文用5種算法對不同維度的基準函數(shù)進行優(yōu)化實驗，以便驗證CPPSO的有效性、高優(yōu)化效率和強普適性等，其共同參數(shù)設置見表2。其中，最大迭代次數(shù)M隨優(yōu)化函數(shù)的維數(shù)不同而不同，除SLPSO采用式(3)外，其他算法的種群大小N都為20。為公平起見，每種算法保證最大目標函數(shù)評價次數(shù)相同，并獨立運行次數(shù)Num為30。另外，這些對比算法的其他參數(shù)設置與原文獻相同。CPPSO需要設置的參數(shù)有兩個：一個是學習因子c1，按照諸多文獻推薦設置為1.494 45; 另一個是交叉概率，采用自適應方式，其中，Cmax取最大值，即Cmax=1，而對于Cmin的取值，通過大量的實驗驗證，Cmin=0.3為最佳，受版面所限，對Cmin取值不作討論。仿真實驗的環(huán)境：操作系統(tǒng)為Windows 7，PC機為主頻為3.10 GHz的CPU和4 GB內(nèi)存，編程語言為Matlab R2014a。

表1 Benchmark函數(shù)信息表Tab. 1 Functions of Benchmark

表2 基本參數(shù)設置Tab. 2 Parameters setting

3.2 優(yōu)化性能比較

3.2.1 與SLPSO、CSPSO、SRPSO和HCLPSO算法的比較

在6個基準函數(shù)上對不同維度(30維、100維和200維)的測試結果見表3～6，其中包含30次獨立運行的尋優(yōu)結果的最大值Vmax、最小值Vmin、均值Mean、標準差值Std，下劃線表示測試結果的最優(yōu)者。其中均值和標準差值越小說明該算法的搜索能力越好和穩(wěn)定性越強。

表3給出了5種算法在30維函數(shù)上的測試結果。從表中可以看出，在各種對比數(shù)據(jù)上，CPPSO擁有極大的優(yōu)勢，大幅度領先于對比算法。在f3和f5上，CPPSO的均值達到了理想最優(yōu)值0，即表1的Fmin，CSPSO只有在f5上的均值達到了理想最優(yōu)值0，SLPSO及另外2種對比算法沒有均值達到理想最優(yōu)值。而對于函數(shù)f1、f2、f4、f6，CPPSO雖然沒有達到其理想的最優(yōu)值，但與包含SLPSO的4種對比算法相比，CPPSO無論在Vmax、Vmin、Mean和Std上都遠遠優(yōu)于4個對比算法。除此之外，5種算法中在Vmin上有3種算法都得到了最優(yōu)值，分別是CPPSO、SLPSO、CSPSO。從30維函數(shù)上的運行結果上可知，CPPSO在低高維函數(shù)上的優(yōu)化性能表現(xiàn)最優(yōu)。

表3 5種算法在30維函數(shù)上的測試結果Tab. 3 Results of 5 algorithms on 30-dimensional functions

表4給出了5種算法在100維函數(shù)上的測試結果。從整體來看，CPPSO算法，沿襲了30維函數(shù)上的高性能態(tài)勢，仍然是5種算法中的最優(yōu)者，其優(yōu)化性能遠優(yōu)勝于4種對比算法。在f3和f5上，CPPSO的Mean再次達到了理想最優(yōu)值0。對于函數(shù)f1、f2、f4和f6，CPPSO算法雖然沒有達到理想最優(yōu)值，但與4種對比算法相比，CPPSO算法的優(yōu)化性能仍然最優(yōu)的。相比30維函數(shù)，100維函數(shù)的維數(shù)增加了，優(yōu)化復雜度增加了，但從實驗結果看，CPPSO在中高維基準函數(shù)上的優(yōu)化性能并沒有明顯地減退。而對比算法隨著維數(shù)的增加，優(yōu)化性能明顯下降了，如在30維f2上SLPSO和CSPSO的均值分別為2.939 1E-52和1.364 2E-50，在100維f2上分別為5.954 0E-47和3.823 0E-29，結果精度下降了許多。

表4 5種算法在100維函數(shù)上的測試結果Tab. 4 Results of 5 algorithms on 100-dimensional functions

表5列出了5種算法在200維函數(shù)上的測試結果。10～100維函數(shù)的優(yōu)化問題是目前國內(nèi)外文獻主要討論的問題，200維函數(shù)的優(yōu)化問題，目前國內(nèi)外相關研究相對較少，主要原因是隨著維數(shù)增加，優(yōu)化難度加大，一般智能優(yōu)化算法難以在如此高維的函數(shù)上獲得理想的優(yōu)化結果。從表5可以看出，CPPSO仍然獲得了最優(yōu)性能。在f3和f5上，CPPSO仍然達到了理想的最優(yōu)值0。在其他基準函數(shù)上，仍然大幅度優(yōu)于對比算法。與30維和100維相比，CPPSO在200維函數(shù)上的優(yōu)化性能有所下降，但與對比算法相比，下降的趨勢較為緩慢。200維函數(shù)上的測試結果足以表明CPPSO能夠很好地處理高高維函數(shù)的優(yōu)化問題。

以上在不同維度基準函數(shù)上的實驗結果證明了CPPSO的可行性，不僅在不同維度單峰函數(shù)上有較好的收斂精度，而且在不同維度多峰函數(shù)上顯示了更好的全局搜索能力，以明顯的優(yōu)勢優(yōu)于對比算法。

總之，不管是低高維乃至高高維函數(shù)，CPPSO都顯示出極好的優(yōu)化性能，具有較強的普適性。這是由于新型的社會學習使得非最優(yōu)粒子向著自己的較優(yōu)粒子學習，具有較好開采能力的結果，而且還是由于最優(yōu)粒子采用交叉反向學習機制使得粒子探索能力增強，與同粒社會學習的開采能力獲得良好平衡的結果。

表5 5種算法在200維函數(shù)上的測試結果Tab. 5 Results of 5 algorithms on 200-dimensional functions

3.2.2 與RLPSO算法的比較

為了進一步說明CPPSO算法的尋優(yōu)性能，將CPPSO算法與目前國內(nèi)最優(yōu)秀的RLPSO算法[9]進行性能對比。這兩種算法都采用了反向學習機制，具有較強的可比性。兩種算法在6個函數(shù)上維數(shù)均為30，種群大小為20。其實驗結果見表6, 其中RLPSO的實驗數(shù)據(jù)直接來自對應的文獻[9]。

表6 CPPSO與RLPSO算法的優(yōu)化結果對比Tab. 6 Results comparison between CPPSO and RLPSO

表6中， 對于單峰函數(shù)f1～f3，CPPSO算法在f3上的均值達到了理想的最優(yōu)值0，在f1和f2上，CPPSO的均值也比RLPSO小得多，說明其局部搜索能力強，收斂精度較高，具有極強的穩(wěn)定性。在優(yōu)化多峰函數(shù)f4～f6時，不管是均值還是標準差值，CPPSO大幅度優(yōu)于RLPSO，說明其全局尋優(yōu)能力強?？傊?，相比RLPSO，CPPSO優(yōu)化性能更好，收斂速度更快以及收斂精度更高，而且對比實驗中本文提出CPPSO的最大目標函數(shù)評價次數(shù)(maxEFs)比RLPSO少許多，前者為5E+4，后者為1E+5，進一步說明CPPSO比RLPSO優(yōu)化性能好。雖然二者都使用了反向學習策略，但二者性能差距巨大，其原因是CPPSO能將隨機反向學習、一般反向學習和最優(yōu)解隨機縱向交叉有機融合，并一直用來更新最優(yōu)解，很好地與同維社會學習策略配合，使得算法的探索與開采達到較好的平衡，因此整體性能得到大幅度提升。

3.2.3 運行時間比較與計算復雜度分析

為了考察CPPSO的優(yōu)化速度，統(tǒng)計5種算法運行時間。表7給出了在所有基準函數(shù)上獨立運行30次的平均時間。

表7 5種算法在高維函數(shù)上的平均運行時間Tab. 7 Average runtime of 5 algorithms on high-dimension functions

從表7中可以看出，不管從每個基準函數(shù)的單向運行時間，還是從所有基準函數(shù)的平均運行時間，除了在30維f2外，CPPSO的耗時是5種算法中最少的。

一個優(yōu)化算法的復雜度由兩部分組成，即目標函數(shù)評價次數(shù)和算法自身的復雜度，對于前者，5種算法相同，即它們有相同的目標函數(shù)評價次數(shù)，所以5種算法的運行耗時的差別主要源于算法自身復雜度的不同。CPPSO作為SLPSO的改進算法，其運行耗時更少，主要原因有二：第一、CPPSO采用基于維的并行方式進行搜索節(jié)省了時間，在30維上，這種并行方式在運行耗時上的優(yōu)勢不明顯，CPPSO的平均耗時為0.447 1 s，比SLPSO的運行時間(0.470 1 s)稍少，然而隨著問題維數(shù)增加，這種優(yōu)勢逐漸顯著，雖然2種算法在處理維度更高的基準函數(shù)時的運行耗時都有所增加，但CPPSO平均耗時較SLPSO平均耗時的差距明顯增大；其二、CPPSO中新的社會學習策略中的速度更新公式計算復雜度低于SLPSO中式(4)的計算復雜度，從而減少了運行耗時?？偟膩碚f，CPPSO在100維基準函數(shù)上的耗時為1.396 3 s，大約分別是SLPSO、SRPSO、CSPSO和HCLPSO的64.69%、32.33%、73.12%和39.44%。在200維基準函數(shù)上的耗時CPPSO為 3.005 7 s，大約分別是SLPSO、SRPSO、CSPSO和HCLPSO的56.33%、32.32%、66.86%和35.50%。 由此可知，CPPSO用最少的時間使優(yōu)化性能最大化，故有更高的優(yōu)化效率。

3.2.4 顯著性分析

為了驗證實驗所得結果的有效性，對CPPSO在100維函數(shù)上獲得的結果與其他對比算法的結果進行了t-檢驗(雙尾)及顯著性分析。置信水平α=0.05，檢驗結果如表8所示，其中，在結果一欄分別用“+”“=”及“-”表示;p<0.05有明顯顯著差異，0.050.1無顯著差異，NA表示由于檢驗的兩個獨立樣本標準差值均為0，無法得到檢驗結果。

表8 CPPSO與對比算法的t-檢驗結果Tab. 8 t-test results of CPPSO with the other comparison algorithms

從表8可以看出，對于t-檢驗得到的23個結果中，CPPSO算法有18次較對比算法顯著更優(yōu)，且均有顯著差異，有5次無顯著差異，沒有較其他對比算法顯著更劣的情況，從而驗證了CPPSO算法優(yōu)秀的性能。

4 結語

針對SLPSO算法存在的收斂速度慢、普適性弱等缺點，本文提出了一種改進的SLPSO算法，即基于交叉反向學習和同粒社會學習的PSO算法(CPPSO)。首先，將基于粒子的社會學習原理運用到粒子搜索中，以整體的全維方式學習示范粒子，提高局部搜索能力和收斂速度，避免了SLPSO基于維的社會學習方式存在的缺點；其次，對于種群中最優(yōu)個體，選擇交叉反向學習機制，不僅提高自身的搜索能力和提高種群的多樣性，而且平衡了探索與開采能力，由此提高了搜索效率和整體的優(yōu)化性能。該算法的普適性強，在不同維度的基準函數(shù)優(yōu)化上效果比目前最優(yōu)秀的PSO改進算法更好，優(yōu)化性能大幅度領先于目前同類算法，在大規(guī)模和復雜優(yōu)化問題上具有較大的應用前景。

References)

[1] 張新明, 涂強, 尹欣欣, 等. 嵌入趨化算子的PSO算法及其在多閾值分割中的應用 [J]. 計算機科學, 2016, 43(2): 311-315. (ZHANG X M, TU Q, YIN X X, et al. Chemotaxis operator embedded particle swarm optimization algorithm and its application to multilevel thresholding[J]. Computer Science, 2016, 43(2): 311-315.)

[2] LIU H, XU G, DING G, et al. Integrating opposition-based learning into the evolution equation of bare-bones particle swarm optimization[J]. Soft Computing, 2014, 19(10): 539-546.

[3] SHANG J, SUN Y, LI S, et al. An improved opposition-based learning particle swarm optimization for the detection of SNP-SNP interactions[J]. Biomed Research International, 2015, 2015: 524821.

[4] DONG W, KANG L, ZHANG W. Opposition-based particle swarm optimization with adaptive mutation strategy[J]. Soft Computing, 2017,21(17): 5081-5090.

[5] MENG A B, LI Z, YIN H, et al. Accelerating particle swarm optimization using crisscross [J]. Information Sciences, 2016, 329(S1): 52-72.

[6] JORDEHI A R. Enhanced Leader PSO (ELPSO): a new PSO variant for solving global optimization problems[J]. Applied Soft Computing, 2015, 26(1): 401-417.

[7] TANWEER M R, SURESH S, SUNDARARAJAN N. Self regulating particle swarm optimization algorithm[J]. Information Science, 2015, 294: 182-202.

[8] LYNN N, SUGANTHAN P N. Heterogeneous comprehensive learning particle swarm optimization with enhanced exploration and exploitation[J]. Swarm & Evolutionary Computation, 2015, 24: 11-24.

[9] 夏學文, 劉經(jīng)南, 高柯夫, 等. 具備反向學習和局部學習能力的粒子群算法[J]. 計算機學報, 2015, 38(7): 1397-1407. (XIA X W, LIU J N, GAO K F, et al. Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Chinese Journal of Computers, 2015, 38(7): 1397-1407.)

[10] 王蕓, 孫輝. 多策略并行學習的異構粒子群優(yōu)化算法[J]. 計算機應用, 2015, 35(11): 3238-3242.(WANG Y, SUN H. Heterogenous particle swarm optimization algorithm with multi-strategy parallel learning [J]. Journal of Computer Applications, 2015, 35(11): 3238-3242.)[11] 李俊, 汪沖, 李波,等. 基于擾動的精英反向學習粒子群優(yōu)化算法[J]. 計算機應用研究, 2016, 33(9): 2584-2591.(LI J, WANG C, LI B, et al. Elite opposition-based particle swarm optimization based on disturbances [J]. Application Research of Computers, 2016, 33(9): 2584-2591.)

[12] CHENG R, JIN Y C. A social learning particle swarm optimization algorithm for scalable optimization[J]. Information Sciences, 2015, 291(6): 43-60.

This work is partially supported by Key Scientific and Technologies Project of Henan Province (132102110209), the Research Program of Basic and Advanced Technology of Henan Province (142300410295).

ZHANGXinming, born in 1963, M. S., professor. His research interests include intelligent optimization algorithm, digital image processing, pattern recognition.

KANGQiang, born in 1989, M. S. candidate. His research interests include intelligent optimization algorithm, digital image processing.

WANGXia, born in 1993, M. S. candidate. Her research interests include intelligent optimization algorithm, digital image processing.

CHENGJinfeng, born in 1990, M. S. candidate. Her research interests include digital image processing.

Particleswarmoptimizationalgorithmwithcrossoppositionlearningandparticle-basedsociallearning

ZHANG Xinming1,2*, KANG Qiang1, WANG Xia1, CHENG Jinfeng1

(1.CollegeofComputerandInformationEngineering,HenanNormalUniversity,XinxiangHenan453007,China;2.EngineeringTechnologyResearchCenterforComputingIntelligence&DataMiningofHenanProvince,XinxiangHenan453007,China)

In order to solve the problems of the Social Learning Particle Swarm Optimization (SLPSO) algorithm, such as slow convergence speed and low search efficiency, a Cross opposition learning and Particle-based social learning Particle Swarm Optimization (CPPSO) algorithm was proposed. Firstly, a cross opposition learning mechanism was formulated based on combining general opposition learning, random opposition learning and vertical random cross on the optimal solution. Secondly, the cross opposition learning was adopted for the optimal particle to improve the population diversity, exploration ability and avoid the disadvantage of SLPSO’s slow convergence and low search efficiency. Finally, a novel social learning mechanism was adopted for the non-optimal particles in the particle swarm, and the new social learning method used particle-based approach, instead of the dimension-based one of SLPSO, not only improved the exploration capacity, but also improved exploitation and the optimization efficiency. The simulation results on a set of benchmark functions with different dimensions show that the optimization performance, search efficiency and generalizability of the CPPSO algorithm are much better than those of the SLPSO and the advanced PSO algorithms such as Crisscross Search PSO (CSPSO), Self-Regulating PSO (SRPSO), Heterogeneous Comprehensive Learning PSO (HCLPSO) and Reverse learning and Local learning PSO (RLPSO).

intelligent optimization algorithm; Particle Swarm Optimization (PSO) algorithm; social learning; opposition learning

2017- 05- 11;

2017- 05- 24。

河南省重點科技攻關項目(132102110209)；河南省基礎與前沿技術研究計劃項目(142300410295)。

張新明(1963—)，男，湖北孝感人，教授，碩士，CCF會員，主要研究方向：智能優(yōu)化算法、數(shù)字圖像處理、模式識別； 康強(1989—)，男，河南鄭州人，碩士研究生，主要研究方向：智能優(yōu)化算法、數(shù)字圖像處理； 王霞(1993—)，河南新鄉(xiāng)人，碩士研究生，主要研究方向：智能優(yōu)化算法、數(shù)字圖像處理； 程金鳳(1990—)，女，河南夏邑人，碩士研究生，主要研究方向：數(shù)字圖像處理。

時間 2017- 08- 17 09:04:21。 網(wǎng)絡出版地址 http://kns.cnki.net/kcms/detail/51.1307.TP.20170817.0904.002.html。

1001- 9081(2017)11- 3194- 07

10.11772/j.issn.1001- 9081.2017.11.3194

(*通信作者電子郵箱xinmingzhang@126.com)

TP181

A