湯繼濤，戴月明

TANG Jitao,DAIYueming

江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122

School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China

1 引言

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種基于種群搜索策略的全局優(yōu)化進(jìn)化算法。它源于鳥(niǎo)群和魚(yú)群群體覓食運(yùn)動(dòng)行為研究結(jié)果的啟發(fā)，于1995年由Kennedy和Eberhart共同提出[1]。算法的原理是：每個(gè)粒子都有初始位置和速度，都是解空間中的可行解。系統(tǒng)首先初始化為一群隨機(jī)粒子，然后粒子通過(guò)追隨個(gè)體最優(yōu)解和群體最優(yōu)解來(lái)完成優(yōu)化。算法收斂速度較快，涉及參數(shù)較少，實(shí)現(xiàn)簡(jiǎn)單，具有較強(qiáng)的全局優(yōu)化能力。PSO算法作為一種并行優(yōu)化算法，可以用于解決大量非線性、不可微和多峰值的復(fù)雜問(wèn)題優(yōu)化，并已廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模式分類和模糊控制等領(lǐng)域[2-4]。PSO中每個(gè)粒子具有記憶功能，能夠在迭代中記憶自己進(jìn)化過(guò)程中的最優(yōu)位置，并結(jié)合自身學(xué)習(xí)能力和社會(huì)學(xué)習(xí)的能力，協(xié)同其他粒子追隨種群最優(yōu)粒子，所有粒子都是向著最優(yōu)解的方向飛去。由于粒子后期在行進(jìn)的過(guò)程中趨于同一化，群體的多樣性逐漸喪失，致使后期算法的收斂速度明顯變慢，甚至處于停滯狀態(tài)，出現(xiàn)早熟現(xiàn)象。

為克服算法過(guò)早陷入局部最優(yōu)，保證全局收斂，提升算法的尋優(yōu)能力，不少學(xué)者做了大量的工作，對(duì)算法進(jìn)行了改進(jìn)[5-7]。改進(jìn)的粒子群算法大多引入了變異操作，當(dāng)粒子趨于局部收斂時(shí)或算法后期使粒子產(chǎn)生變異，跳出局部收斂位置，從而達(dá)到全局收斂的效果。本文結(jié)合PSO強(qiáng)大的全局尋優(yōu)能力，以粒子群中每個(gè)粒子的收斂吸引子為中心，引入?yún)^(qū)域震蕩搜索因子，使粒子在吸引子的周圍區(qū)域震蕩搜索尋求全局最優(yōu)值，避免算法陷入早熟。這有效提升了算法的收斂精度和速度。通過(guò)實(shí)驗(yàn)結(jié)果進(jìn)行了驗(yàn)證。

2 標(biāo)準(zhǔn)粒子群優(yōu)化算法（SPSO）

粒子群算法是在1995年由美國(guó)社會(huì)心理學(xué)家Kennedy和電氣工程師Eberhart共同提出的，其基本思想起源于他們?cè)缙趯?duì)鳥(niǎo)類群體行為研究結(jié)果，并利用了生物學(xué)家Frank Heppner的生物群體模型而形成的。粒子群優(yōu)化算法是一種基于群體的具有全局尋優(yōu)能力的優(yōu)化工具。它通過(guò)迭代搜尋最優(yōu)值，系統(tǒng)初始化為一組最優(yōu)解，而粒子（潛在的解）在解空間追隨最優(yōu)的粒子進(jìn)行搜索。假設(shè)在一個(gè)D維的目標(biāo)搜索空間中，有N個(gè)粒子組成一個(gè)群體，其中第i個(gè)粒子表示一個(gè)D維的向量 xi，i=1，2，…，N ，即第i個(gè)粒子在D維的搜索空間中的位置是xi；第i個(gè)粒子的飛行速度也是一個(gè)D維的向量，記為vi，i=1，2，…，N。每個(gè)粒子的位置就是一個(gè)潛在的解，將xi代入一個(gè)目標(biāo)函數(shù)就可以計(jì)算出其適應(yīng)度值，根據(jù)適應(yīng)度值的大小衡量xi的優(yōu)劣。記第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為 pbi，i=1，2，…，N，整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為gb。

每個(gè)粒子的當(dāng)前最好位置由以下公式?jīng)Q定：

而粒子群優(yōu)化算法采用下列公式對(duì)粒子進(jìn)行動(dòng)態(tài)調(diào)整：

其中，i=1，2，…，N；公式中，t為當(dāng)前的迭代次數(shù)；w為慣性權(quán)重因子，用來(lái)控制種群長(zhǎng)時(shí)間不陷入早熟；自身學(xué)習(xí)c1和社會(huì)學(xué)習(xí)因子c2是非負(fù)常數(shù)；r1和r2是介于[0，1]之間的隨機(jī)數(shù)。迭代終止條件根據(jù)具體問(wèn)題一般選為最大迭代次數(shù)或粒子群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值。

3 區(qū)域震蕩的粒子群優(yōu)化算法（RSPSO）

M.Clerc通過(guò)代數(shù)和數(shù)學(xué)分析方法，對(duì)PSO算法中粒子收斂行為進(jìn)行了分析[8]，研究表明，粒子i的收斂過(guò)程是以點(diǎn) pi=(pi1，pi2，…，piD)為吸引子，其坐標(biāo)為：

或者

實(shí)際上，當(dāng) c1=c2時(shí)，φi，j(t)本身就是一個(gè)區(qū)間（0，1）上均勻分布的隨機(jī)數(shù)，即 φi，j(t)～U(0，1)。因此在實(shí)際計(jì)算過(guò)程中可以直接由隨機(jī)數(shù)發(fā)生器產(chǎn)生，這時(shí)公式（4）（5）就可以合并起來(lái)寫成：

在區(qū)域震蕩搜索的粒子群優(yōu)化算法中，將采用這個(gè)公式。在收斂過(guò)程中，隨著速度的減小，粒子i不斷接近 pi點(diǎn)，最后跌落到 pi點(diǎn)。因此在整個(gè)過(guò)程中，在 pi點(diǎn)存在某種形式的吸引力吸引著粒子，最后促使整個(gè)種群保持聚集性。

本文在確立粒子群中每個(gè)粒子的吸引子的基礎(chǔ)上，計(jì)算出每個(gè)粒子當(dāng)前所處位置和該粒子吸引子的距離Δi，j(t)。

Δi，j(t)的大小是粒子群收斂程度的反映。 Δi，j(t)的值越小代表著在吸引子的作用下粒子越靠近吸引子，種群的聚集性就越強(qiáng)；相反，Δi，j(t)的值越大代表著粒子還沒(méi)有及時(shí)靠近吸引子，種群相對(duì)比較發(fā)散，種群的聚集性相對(duì)較弱。在算法初期，Δi，j(t)的值相對(duì)比較大，在后期由于迭代種群趨向同一化，Δi，j(t)的值就會(huì)變小，粒子i會(huì)不斷靠近吸引子 pi點(diǎn)，最終收斂到 pi點(diǎn)。

為防止Δi，j(t)在種群迭代的過(guò)程中逐漸變小，種群?jiǎn)适Ф鄻有?，算法陷入局部極值，本文提出了區(qū)域震蕩的粒子群優(yōu)化算法。區(qū)域震蕩算法應(yīng)用于粒子群粒子的每一維，粒子i的各維區(qū)域震蕩因子為 Δi，j(t)，?1≤ i≤ N，1≤ j≤ D 。 Δi，j(t)描述的是粒子i當(dāng)前的 j維度位置和該粒子相應(yīng)維度的吸引子之間的距離，前面已經(jīng)講到，距離的大小反映粒子的聚集程度。粒子震蕩搜索的范圍是以吸引子為中心，區(qū)域震蕩因子為半徑的搜索區(qū)域，即 regioni，j=pi，j± Δi，j。粒子既是受到吸引子的吸引，則粒子震蕩搜索的方向即為粒子指向吸引子的方向。粒子搜索的過(guò)程中，區(qū)域震蕩因子線性減小，從而使粒子能夠在吸引子周圍區(qū)域以一定概率尋找到比自身歷史極值更佳的值。區(qū)域震蕩因子線性減少的公式為：

Δi，j(S)為粒子指向吸引子開(kāi)始的震蕩幅度，由于粒子的搜索區(qū)域是以吸引子為中心，粒子和吸引子的距離為半徑的范圍，所以設(shè)定為 2Δi，j(t)，Δi，j(E)為粒子指向吸引子結(jié)束時(shí)的震蕩幅度，這里設(shè)定為0，RS為粒子最大的震蕩次數(shù)，k則為當(dāng)前的粒子震蕩次數(shù)。

粒子各維每震蕩搜索一次，粒子各維的位置則改變一次，粒子各維的位置更新式為：

xi，j(k)記錄第k次在吸引子附近震蕩搜索的粒子位置，xi，j(t)為粒子震蕩搜索前粒子所在的位置。 flag則是來(lái)決定粒子震蕩的方向，使粒子在每次搜索的過(guò)程中都保證粒子是向著吸引子靠近。粒子從第一維度開(kāi)始搜索，每搜索一次粒子要結(jié)合該粒子剩余的還沒(méi)有震蕩搜索的維度位置計(jì)算出粒子的適應(yīng)度值，在完成震蕩搜索之后選取適應(yīng)度值最小的位置，剩下的維度則按照相同的方法實(shí)現(xiàn)。當(dāng)粒子的各個(gè)維度都完成設(shè)定的粒子區(qū)域震蕩次數(shù)RS后，將各個(gè)維度的最佳位置拼接起來(lái)計(jì)算粒子的適應(yīng)度值，如果適應(yīng)度值優(yōu)于粒子的歷史最優(yōu)極值則取代震蕩搜索前粒子的歷史最優(yōu)極值，如果適應(yīng)度值優(yōu)于整個(gè)種群的全局最優(yōu)值，則取代震蕩搜索前種群的全局最優(yōu)值成為新的全局最優(yōu)值。

綜上所述，算法的流程描述如下：

步驟1初始化種群及相關(guān)參數(shù)。種群規(guī)模N，每個(gè)粒子的維度D，種群的迭代次數(shù)Max DT，粒子區(qū)域震蕩搜索次數(shù)RS；根據(jù)種群規(guī)模和維度隨機(jī)生成種群，并確定每個(gè)粒子的局部最優(yōu)位置和種群的全局最優(yōu)位置。

步驟2根據(jù)公式（6）計(jì)算出每個(gè)粒子吸引子 pi的位置。

步驟3根據(jù)公式對(duì)粒子進(jìn)行區(qū)域震蕩搜索。

步驟3.1根據(jù)公式（7）計(jì)算出粒子每維的區(qū)域震蕩因子 Δi，j(t)。

步驟3.2根據(jù)公式（8）計(jì)算出當(dāng)前震蕩次數(shù)時(shí)的震蕩幅度 Δi，j(k)。

步驟3.3粒子的每一維按照公式（9）進(jìn)行震蕩搜索，并結(jié)合粒子的其他維度計(jì)算出粒子在該維度上最佳適應(yīng)度值時(shí)的位置。

步驟3偽代碼描述如下：

步驟4計(jì)算經(jīng)過(guò)區(qū)域震蕩搜索后的粒子適應(yīng)度值，更新粒子的局部最優(yōu)位置 pbi，更新全局最優(yōu)位置gb。

重復(fù)計(jì)算步驟2至步驟4，直到滿足迭代的次數(shù)。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證RSPSO算法的有效性和正確性，本文采用了表1中的經(jīng)典測(cè)試函數(shù)來(lái)評(píng)價(jià)算法的性能，并與標(biāo)準(zhǔn)PSO算法及帶有柯西變異的PSO算法[9]的測(cè)試結(jié)果作比較。

表1 經(jīng)典測(cè)試函數(shù)及相關(guān)參數(shù)

表1中涉及的函數(shù)比較全面，有單峰函數(shù)(f1～f4)，同時(shí)也有多峰函數(shù)(f5～f8)。表中除 f6函數(shù)以外，其余的函數(shù)的理論最優(yōu)值均為0，函數(shù) f6的理論最優(yōu)值為－418.982 9n，結(jié)合表中的具體維數(shù)，該函數(shù)的最優(yōu)值為－12 569.5。算法參數(shù)設(shè)置為：f1～f3測(cè)試函數(shù)中，粒子種群規(guī)模N=10，f4～f8中，粒子種群規(guī)模N=50，粒子的維數(shù)和各維搜索范圍參見(jiàn)表1，粒子群除 f4外迭代次數(shù)Max DT=100，優(yōu)化 f4迭代次數(shù)Max DT=1 000，區(qū)域震蕩搜索的次數(shù)RS=10。選取的幾個(gè)測(cè)試函數(shù)分別對(duì)三種算法進(jìn)行測(cè)試，為了減少偶然性，每個(gè)函數(shù)獨(dú)立運(yùn)行30次。取30次實(shí)驗(yàn)結(jié)果的平均最優(yōu)適應(yīng)度值和標(biāo)準(zhǔn)方差作為對(duì)比結(jié)果。

表2中的實(shí)驗(yàn)結(jié)果顯示，RSPSO算法相比另外兩個(gè)算法在平均最優(yōu)值和標(biāo)準(zhǔn)方差上都有顯著的提升，尤其在 f1～f2的函數(shù)尋優(yōu)中，結(jié)果提升了100多個(gè)數(shù)量級(jí)，f3也有著很大程度的改善。 f4函數(shù)的最小值位于非常狹窄的一個(gè)條帶上，沿著這一條帶，函數(shù)變化非常緩慢。從結(jié)果來(lái)看，RSPSO算法在 f4上雖標(biāo)準(zhǔn)方差有所不及，但平均最優(yōu)值卻得到提升。平均最優(yōu)值結(jié)果的對(duì)比中顯示出RSPSO算法有著更高的收斂精度，標(biāo)準(zhǔn)方差結(jié)果的對(duì)比中顯示出RSPSO算法有著更高的穩(wěn)定性。由此可見(jiàn)算法能夠有效地?cái)[脫局部極值，避免陷入早熟，有著很強(qiáng)的全局尋優(yōu)能力。從實(shí)驗(yàn)結(jié)果來(lái)看，算法在單峰連續(xù)函數(shù)的尋優(yōu)中，有著很強(qiáng)的全局尋優(yōu)能力。

表2 算法在 f1～f4上的平均最優(yōu)值和標(biāo)準(zhǔn)方差

表3中的測(cè)試函數(shù)變量的維數(shù)都是30維，種群規(guī)模N=50。 f5～f8為多峰函數(shù)，相比單峰函數(shù)尋優(yōu)，多峰函數(shù)尋優(yōu)，算法更易局部收斂，陷入早熟。從實(shí)現(xiàn)結(jié)果看，RSPSO有效避免了陷入局部極值。 f5的尋優(yōu)結(jié)果得到長(zhǎng)足的改善，f6的尋優(yōu)結(jié)果雖不及HPSO但是相比PSO也有著長(zhǎng)足的進(jìn)步，f7和 f8更是達(dá)到了Matlab的最小精度值，顯示為0。由此可以得出，RSPSO在多峰連續(xù)函數(shù)中也有著很強(qiáng)的全局尋優(yōu)效果。

表3 算法在 f5～f8上的平均最優(yōu)值和標(biāo)準(zhǔn)方差

圖1 HPSO算法在 f1和 f3上的進(jìn)化曲線

圖2 RSPSO算法在 f1和 f3上的進(jìn)化曲線

圖3 HPSO算法在 f5和 f7上的進(jìn)化曲線

HPSO的時(shí)間復(fù)雜度為O(N×D×Iter max)，其中，N為粒子群規(guī)模，D為粒子維數(shù)，Iter max為迭代次數(shù)。RSPSO提出了區(qū)域震蕩搜索思想，即粒子在每次迭代的過(guò)程中，嵌套搜索周圍區(qū)域，粒子每震蕩搜索一次，其作用就相當(dāng)于HPSO迭代搜索一次，由于嵌套搜索次數(shù)的存在，所以粒子群整體的搜索次數(shù)為Max DT×RS，其中：Max DT為RSPSO的迭代次數(shù)，RS為嵌套震蕩搜索的次數(shù)。為保證粒子群搜索次數(shù)和時(shí)間復(fù)雜度與HPSO算法的一致，就不能將RSPSO的迭代次數(shù)設(shè)置和HPSO算法的一樣，否則算法在對(duì)比中參數(shù)設(shè)置就不一致了，故將迭代次數(shù)設(shè)置為Max DT=Iter max/RS，這樣保證了算法對(duì)比的公平性。文獻(xiàn)[9]中的算法的迭代次數(shù)設(shè)置為1 000，為保證算法對(duì)比中參數(shù)一致，本文中算法震蕩搜索次數(shù)RS=10，故RSPSO算法的迭代次數(shù)應(yīng)設(shè)置為1 000/10=100，由于算法的迭代次數(shù)不同，故不同算法對(duì)同一函數(shù)優(yōu)化的結(jié)果不能放在同一張圖中顯示，本文將結(jié)果分開(kāi)展示。

圖4 RSPSO算法在 f5和 f7上的進(jìn)化曲線

圖1 和圖2為文獻(xiàn)[9]中HPSO和RSPSO算法在 f1和 f3上的進(jìn)化曲線，圖3和圖4為兩種算法在 f5和 f7上的進(jìn)化曲線。橫坐標(biāo)為進(jìn)化次數(shù)，縱坐標(biāo)為粒子適應(yīng)度值的lg對(duì)數(shù)。雖然分開(kāi)顯示，但是從圖上還是可以很直觀地看出，RSPSO算法在單峰和多峰函數(shù)的優(yōu)化效果上，從進(jìn)化一開(kāi)始就顯示出強(qiáng)大的尋優(yōu)能力，整體在收斂精度和速度上得到實(shí)質(zhì)性的提升。尤其在 f7的尋優(yōu)上，尋優(yōu)結(jié)果超出了Matlab最小精度值，顯示為0，因?yàn)榭v坐標(biāo)為粒子適應(yīng)度值的lg對(duì)數(shù)，所以后期曲線無(wú)法顯示。

5 結(jié)束語(yǔ)

RSPSO算法將粒子吸引子位置和區(qū)域震蕩搜索操作結(jié)合，在保證了粒子群強(qiáng)大的全局尋優(yōu)能力的基礎(chǔ)上，增加種群的多樣性，有效避免了種群陷入局部極值，產(chǎn)生早熟現(xiàn)象。通過(guò)實(shí)驗(yàn)驗(yàn)證了算法無(wú)論在單峰還是多峰連續(xù)函數(shù)上都有著突出的尋優(yōu)效果。RSPSO算法涉及的參數(shù)比較少，相比SPSO沒(méi)有速度向量，實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單。將改進(jìn)的算法應(yīng)用于實(shí)際工程中，在實(shí)用中檢驗(yàn)RSPSO的性能將是本文下一步研究重點(diǎn)。

[1]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings IEEE International Conference on Neural Networks，1995：1942-1948.

[2]Vasant P，Ganesan T，Elamvazuthi I.An improved PSO approach for solving non-convex optimization problems[C]//2011 9th International Conference on ICT and Knowledge Engineering，2012：80-87.

[3]徐剛，黃先玖.一種粒子群優(yōu)化的神經(jīng)網(wǎng)絡(luò)綜合訓(xùn)練算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：37-38.

[4]朱文斌，許曉飛.基于混合粒子群算法的保障資源優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（29）：210-213.

[5]彭力，王茂海.基于前饋擾動(dòng)的粒子群改進(jìn)算法[J].控制工程，2012，19（1）：102-105.

[6]姜偉，王宏力，何星，等.基于適應(yīng)度反饋?zhàn)饔玫腜SO算法改進(jìn)[J].計(jì)算機(jī)工程，2012，38（22）：146-150.

[7]王興元，張鵬.基于細(xì)致化仿生的改進(jìn)粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（7）：1484-1492.

[8]Clerc M，Kennedy J.The particle swarm：explosion，stability，and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6（1）：58-73.

[9]Wang H，Liu Y，Li C H，et al.A hybrid particle swarm algorithm with cauchy mutation[C]//Proceedings of IEEE Swarm Intelligence Symposium，2007：356-360.