基于多種群多策略的競爭粒子群算法

李媛媛,李文博,尚志豪

(大連交通大學 軟件學院,遼寧 大連 116028)

粒子群優化算法是一種基于群體智能的優化算法,它通過模擬智能群體中每個個體的行為來解決優化問題.主要應用在工程設計[1]、控制工程[2]、路徑規劃[3]、計算機視覺[4]等方面.文獻[1]為了在鍛坯過程中找到最佳的工藝參數,改善傳統數值模擬方法的不足,采用粒子群算法對參數進行優化,從材料本身和鍛壓成形節能的角度出發,采用該算法找到最合適的參數結果.文獻[2]使用非線性PID (NLPID)控件取代了傳統的PID控件,提出了一種基于廣義對立學習算法的粒子群優化算法來優化NLPID控制器,成功抑制了系統超調.文獻[4]提出了一種靈活的卷積自編碼器,利用粒子群優化設計了一種架構發現方法,該方法能夠自動搜索所提出的柔性卷積自編碼器的最優架構,無需任何人工干預,大大減少計算資源,解除了傳統卷積自編碼器對卷積層和池化層數量的禁錮,并證明了加入粒子群算法后的新的圖像分類算法遠優于其他同類算法.

標準粒子群優化算法(standarding particle swarm optimization,SPSO)最初由Shi和Eb-erhart等[5]在1998年提出,它擁有慣性權重,是為了解決原始PSO算法易陷入局部最優值而進行的改進.帶有壓縮因子的粒子群優化算法在1999年由Clerc等[6]提出,目的是在幫助粒子跳脫局部最優值的同時加快整個優化過程的收斂速度.這兩種改進方式是針對原始PSO最經典的改進方法.其他的改進算法通常都是在此基礎上進行改進,方法包括：改變粒子拓撲結構、與其他算法結合、引入新的機制、或是對參數進行修改.例如：為了克服傳統的Pareto最優前沿形狀變化分解方法的不穩定性,Zheng Jinhua等[7]提出了1種基于對抗分解和鄰域演化的動態多目標粒子群優化算法;針對存在多個pareto最優解且適應度值相同的多模態多目標優化問題,Liang Jing等[8]提出了一種具有自組織機制的多目標粒子群優化算法;Liu Yaxian等[9]通過將強化學習算法與粒子群算法結合起來,得到了自適應參數;為了使算法尋優過程中更輕松地跳出局部最優值,徐利鋒等[10]在帶有收縮因子的粒子群算法基礎上引入了多級擾動機制.

粒子群優化算法的優勢在于它可以快速收斂到最優解,同時具有較好的全局搜索能力.在眾多應用中,粒子群優化算法已經取得了良好的效果,但是在實際應用中還是會出現易陷入局部最優[11-12]、收斂性差[13-14]、求解精度低[15]等問題.為了減少這些問題對算法的影響,作者對標準粒子群算法進行改進,提出基于Logistic混沌映射權重及混合高斯、柯西擾動變異,同時使用了收縮因子的多種群多策略競爭粒子群算法(multi-swarm multistrategy competitive particle swarm optimization,MMCPSO).為了獲得比標準粒子群算法更好的尋優性能,作者將每一代的粒子群劃分為不同的子種群,并使用不同的更新機制來更新這些子種群,從而使粒子的全局搜索能力和局部開采能力在尋優過程中達到平衡.

1 標準粒子群算法

在粒子群算法中,每個粒子的位置代表了給定問題的潛在解決方案,并使用適應度函數來評判當前位置的優劣.群體中的粒子會通過信息共享機制來更新自身的速度和位置,從而更新整個群體.群體在迭代過程中不斷追尋最優粒子,在解空間內進行搜索運動,從而逐漸從無序向有序演變,最終達到在限制條件內求得待解決問題的帕累托最優解的目的.

粒子速度和位置更新公式：

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+c2r2(gbestij(t)-xij(t)).

(1)

xij(t+1)=xij(t)+vij(t+1).

(2)

其中,vij(t)表示第t代粒子i在第j維度上的速度,wvij(t)部分表示上一代歷史速度對當前速度的影響,慣性權重w用來調節此影響的大小,從而調節粒子在解空間的搜尋范圍,使粒子全局搜索和局部開采能力達到平衡.c1r1(pbestij(t)-xij(t))為粒子的自我認知部分,c2r2(gbestj(t)-xij(t))為社會認知部分.pbestij(t),gbestj(t)分別為粒子的個體歷史最優位置和全局歷史最優位置.加速度因子c1,c2分別用來調節粒子向自己歷史最優位置和全局最優位置學習的步長.隨機數r1,r2都取值[0,1]內,用以增加粒子搜索的隨機性.

2 改進的粒子群算法MMCPSO

標準PSO尋優過程一直伴隨著局部搜索能力不夠強,搜索精度差,處理復雜非線性多峰問題常陷入局部最優等問題.為了擺脫這個困擾,MMCPSO根據同代種群粒子的適應度值將粒子分別劃為3個子種群：優等子群(superiors)、普通子群(ordinaries)、劣等子群(inf-eriors);針對不同子種群粒子的特點分別加入擾動變異、Logistic混沌映射、收縮因子3種不同策略來進行粒子的更新;不同子種群產生的新一代粒子通過參與適應度值競爭排序后,更新到不同的子種群;算法中的每個子種群會通過粒子更新公式,不同程度的參與引領整個種群更新.不同于標準PSO的所有粒子只對本身歷史最優和全局歷史最優進行追逐,這種新的更新策略使整體算法尋優全程擁有較強的全局和局部尋優能力并兼具了易跳出局部最優、保持種群多樣性的特性,彌補了標準PSO的不足.下面將詳細介紹MMCPSO的種群劃分方式和不同子種群的更新策略.

2.1 種群劃分

以求最小值問題為例,在MMCPSO中,每一代的所有粒子按照適應度從低到高進行競爭排序后,求得當代種群適應度的平均值和標準差.在求最小值的優化問題中：取平均適應度一倍標準差內的粒子組成普通子群;取適應度值小于普通子群的粒子組成優等子群;取適應度值大于普通子群的粒子為劣等子群.劣等子群向優等子群和普通子群兩個子群按照合理的權重學習更新,盡快向兩個區域靠攏;普通子群使用帶有w慣性的更新公式,平衡普通子群粒子的全局和局部探索能力.

適應度平均值和標準差的計算公式如下：

(3)

(4)

圖1 子種群劃分方式

2.2 優等子群更新策略

優等子群粒子已經獲得了較優的適應度值,所以優等子群進行自我學習更新.同時,該種群粒子聚集在局部最優解附近.為了避免陷入局部最優,同時又使粒子具備好的局部尋優能力,作者設計了帶有局部開發能力強的高斯變異和具有兩翼分布概率且更易跳出局部最優的柯西變異的粒子更新方式.

高斯-柯西變異算子GC定義式：

GC=αG+(1-α)C,0<α<1.

(5)

G=Gaussion(0,1)=rand(0,1)～N(0,1).

(6)

(7)

優等子群粒子更新公式：

(8)

(9)

2.3 劣等子群更新策略

劣等子群中的個體通過主要向優等子群學習,兼顧受種群中心平均值牽引的方式更新.采用收縮因子對整個更新過程進行壓縮,使劣等子群的粒子能快速脫離劣勢區域向優勢區域收斂,同時又能對各個學習因子進行調節,均衡了該階段算法的收斂性能,避免在快速靠近優等子群的過程中喪失了開發能力.

收縮因子φ定義式：

c=c1+c2+c3,c≥4.

(10)

(11)

劣等子群更新公式：

(12)

2.4 普通子群更新策略

普通子群粒子處于解空間合理位置范圍內,無明顯優劣勢,該子群進化過程中需要平衡算法的勘探和開采能力.SPSO算法使用的線性遞減權重w在一定程度上平衡了粒子的全局探索和局部開發,但線性的調整方式在多維復雜非線性函數的優化過程中常陷入局部最優.混沌映射作為非線性映射方式的一種,其產生的隨機序列具有良好的空間便利性.因此,作者在SPSO算法基礎上對權重w加入Logistic混沌映射,用非線性權重wL對粒子的速度進行更新,使算法搜索能力均衡的同時又能很好地遍歷解空間,不易陷入局部最優.

Logistic混沌映射慣性權重wL定義式：

r(t+1)=4r(t)(1-r(t)),r(0)=rand(0,1)且r(0)≠{0,0.25,0.75,1}.

(13)

(14)

普通子群粒子更新公式：

(15)

(16)

圖2 慣性權重隨迭代次數變化圖

3 實驗

3.1 標準函數測試

選取11個基本測試函數與標準粒子群算法從尋優精度、尋優速度,跳出局部最優的能力等方面進行比對,來驗證MMCPSO算法的有效性.11個標準測試函數的基本信息由表1給出,fopt為函數最優值.函數f1～f6是用來測試算法尋優的快慢和所得解優劣的單峰函數,函數f7～f11為測試算法跳出局部最優,避免過早收斂的能力的多峰函數.

3.2 算法性能測試

將MMCPSO與SPSO進行對比實驗,給予2種算法相同的種群大小N=90和最大迭代次數tmax=150,令二者在一個30維的解空間內對11個基本測試函數進行最小值尋優.在相同的硬件條件下,運行兩個算法50次,記錄兩種算法50次的尋優結果,分別求取平均值(Mean)和標準差(standard deviation,SD)作為評價算法性能的指標.算法參數設置見表2.

2種算法對基本測試函數的尋優結果見表3.

表1 11個標準測試函數

表2 各算法參數表

表3 2種算法求解11個標準測試函數適應度的平均值和標準差

繪制出FPSO和MMCPSO在求解11個標準測試函數時的適應度曲線,以便更直觀的對比觀察2種算法的求解精度和收斂速度,如圖3、圖4、圖5所示.

(a)f1 (b)f2

(c)f3 (d)f4圖3 各算法f1～f4函數尋優適應度曲線

(a)f5 (b)f6

(c)f7 (d)f8圖4 各算法f5～f8函數尋優適應度曲線

(a)f5 (b)f6 (c)f6圖5 各算法f9～f11函數尋優適應度曲線

從表3可知,在標準測試函數f1～f4、f7～f9上MMCPSO算法的尋優精度較FPSO算法有著明顯的數量級優勢,在剩余的測試函數上新算法求得適應度的平均值也更接近函數本身的最優值.從圖3、圖4、圖5中各個測試函數的適應度曲線可以看出新算法收斂速度更加迅速,又得益于變異機制和混沌映射慣性權重,跳出局部最優解的能力也更強.

3.3 對比實驗

為了證明MMCPSO算法的優越性,將其與3種典型的PSO變體進行比較,包括自適應慣性權重的全局PSO(GPSO-AW)[16]、動態維度自適應PSO(DDAPSO)[17]和局部競爭PSO(LC-PSO)[18].具體的參數設置如表4所示.為確保用不同算法進行實驗比較的公正性,測試函數的維度D設置為30,種群規模N設置為90,最大迭代次數t_max設置為150,每個算法獨立運行50次.

表5給出了MMCPSO算法和當前3種PSO在11個基準測試函數上的性能比較結果.

表4 算法參數表

實驗結果分析：

1)算法尋優能力.將MMCPSO 算法與GPSO-AW、DDAPSO、LC-PSO 3個算法在多個單峰、雙峰函數下進行測試,MMCPSO算法表現極佳.無論是在單峰測試函數f1、f3、f4、f5,還是多峰測試函數f2、f7～f9上,其求得的Mean值比其它算法更接近測試函數的最優值.這說明該算法尋優能力出眾.

2)算法穩定性.在性能評價指標中的SD值也遠小于其它算法,這說明MMCPSO算法性能穩定.美中不足的是在f6和f11上MMCPSO算法的表現都不如GPSO-AW算法.

表5 不同算法性能比較

4 結語

設計了1種可以根據不同子種群狀況,采用不同更新策略的改進粒子群算法MM-CPSO.MMCPSO利用競爭學習機制和收縮因子加快了劣等子群學習速度;通過引入融合的變異算子和使用自適應變異步長增大了優等子群中粒子局部開發能力和跳出局部最優的概率值;加入Logistic混沌映射慣性權重令普通子群更好地遍歷解空間.新的更新策略有效地避免種群在優化單峰、多峰問題時早熟收斂和無法跳出局部最優解.改進后的算法在11個標準測試函數上的優化表現表明采用不同子種群不同更新策略能夠有效取得探索和開發能力的最佳平衡.下一步的目標是將該算法引入到深度學習中,幫助神經網絡模型選取優秀的初始權重和高效的網絡結構模型.