基于邊界變異的一種新的粒子群優(yōu)化算法

劉依依+徐生兵

【 摘 要 】 針對傳統(tǒng)粒子群優(yōu)化算法易早熟，收斂精度低，特別是在解決大維數(shù)問題時，效果很不理想等缺點。針對這類問題，首先提出一個判別機制，判定算法什么時候達到早熟，若達到早熟則提出一種基于邊界與隨機變異的方法使部分粒子進行變異，從而使粒子重新分散后，再進行搜索。通過對四個經(jīng)典測試函數(shù)的數(shù)值仿真實驗證明，該方法能極大地提高算法的尋優(yōu)能力，特別是在高維函數(shù)尋優(yōu)時獲得了較好的優(yōu)化效果。

【 關鍵詞 】 粒子群優(yōu)化；早熟；邊界；變異

【 中圖分類號 】 TP18

【 文獻標識碼 】 A

New Particle Swarm Optimization Base On Boundary Mutation

Liu Yi-yi Xu Sheng-bing

（City College of Dongguan University of Technology GuangdongDongguan 523419）

【 Abstract 】 The traditional particle swarm optimization algorithm was premature convergence， low accuracy.Especially in solving large dimension problems， the effect is not ideal.In order to solve these problems，first it presents adecision mechanism when the algorithm reaches puberty.If the algorithm reaches puberty，present a method based on the boundary and random variation.It makes part of particle variation and then these particles are variationso that the particles bounce early regional and search again。Based on the 4 classical test functions of numerical simulation experiment， the method can greatly improve the searching capability especially in highdimensional function optimization it obtained better optimization effect.

【 Keywords 】 particle swarm optimization； premature； boundary； mutation

1 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 于1995 年提出的一種優(yōu)化算法。它是一種仿真算法，是模擬自然界一些生物的行為，如鳥群覓食、魚群學習等。由于其容易理解、易于實現(xiàn)、不要求目標函數(shù)和約束條件是可微的， 并能以較大概率求得全局最優(yōu)解， 目前已在許多優(yōu)化問題中得到成功應用。與其它進化算法類似， 粒子群優(yōu)化算法也存在早熟收斂現(xiàn)象， 尤其是在比較復雜的多峰搜索問題中。目前解決這一問題的主要方法是增加粒子群的規(guī)模， 雖然對算法性能有一定改善， 但同樣存在缺陷：一是不能從根本上克服早熟收斂問題；二是會大大增加算法的運量。

基于這種情況提出一種改進的PSO算法。此算法首先設計出一種方法判定算法在什么情況達到了早熟；當粒子達到早熟時，設計讓其中一個粒子呆在早熟區(qū)，而其它粒子的其中一維上加入一個[-1，1]中的隨機數(shù)進行變異，使其能夠跳出該區(qū)域。這樣，使陷入該區(qū)域的粒子能夠在跳出早熟狀態(tài)的情況下，又能夠在保持目前搜尋到的最優(yōu)值，再次重新尋找最優(yōu)值，從而保證了算法能夠找到比現(xiàn)在更好的全局最優(yōu)值。

這種思想在理論上也是行得通的，因為粒子在尋優(yōu)過程中達陷入早熟時，其目前尋到的最好值離理論最優(yōu)值雖然有一定的距離，但相對于算法迭代前的位子肯定有一個很大的提高，這時我們保持一個粒子在這個區(qū)域中就保留了這個值的優(yōu)越性，使算法在以后的迭代中能達到的最優(yōu)值一定不會比現(xiàn)在的值更差，而其它粒子進行變異是為了能夠使粒子跳出該區(qū)域，從而讓算法重新進行搜索去尋找更好的最優(yōu)值。加入一個[-1，1]中的隨機數(shù)進行變異是因為當粒子陷入早熟說明此時粒子在某種程度上已經(jīng)比較接近最優(yōu)值了，此時粒子進行變異不宜進行大的變動，只需小的變動使其跳出該區(qū)域重新尋找最優(yōu)值即可。其通過數(shù)值模擬實驗，發(fā)現(xiàn)改進的PSO算法對改進粒子群優(yōu)化的性能方面特別是對大維數(shù)的尋優(yōu)方面有極大的提高。

3 改進的粒子群算法

3.1 PSO的早熟現(xiàn)象和判定機制

從公式（1）中可看出，PSO 速度更新方程由三部分組成：式（1）中第一項表示粒子的當前速度，說明了粒子的目前狀態(tài)；第二項為“認知（Cognition）”部分，考慮了粒子自身經(jīng)驗；第三項為“社會（Social）”部分，代表著粒子之間的“社會”作用。分析此式不難發(fā)現(xiàn)，當粒子的當前位置處在全局極值位置Gbest 時，該粒子只有在先前速度和慣性權系數(shù)不等于零情形下，粒子才有可能離開這一點；如果種群中粒子的先前速度都接近于零時，一旦它們落于全局極值位置Gbest，則種群中的粒子很難再重新移動，此時意味著算法將收斂到種群目前尋優(yōu)到的最優(yōu)解，即全局極值位置Gbest。此時搜索到的全局極值位置Gbest對應的解如果只是優(yōu)化問題的一個局部最優(yōu)解，那么算法就出現(xiàn)了早熟收斂現(xiàn)象。在實驗中，我們采取了一些具體方法，來判定粒子什么情況達到早熟。

在粒子群算法中，我們用個Gbest的值來保存現(xiàn)尋到的最優(yōu)值，若是下次迭代中尋到的最優(yōu)值比現(xiàn)尋到的最優(yōu)值更優(yōu)越則更新Gbest的值。但當算法陷入早熟時，粒子只在一個很小的區(qū)域內(nèi)變動，此時最優(yōu)值幾乎不改變，則我們設計出如下判別早熟方法， 我們定義兩個變量Gbest與Gbest1，Gbest保存算法目前尋到的最優(yōu)值，Gbest1保存前一次算法尋到的最優(yōu)值，兩者相比較，若不相等，則用Gbest值更新Gbest1的值；若相等，則我們用一個初始化h=0的值來記它們相等的次數(shù)，h的值加1，當h的值達到100時，若此時算法還沒達到最優(yōu)值，則判定出算法陷入局部最優(yōu)。過程偽代碼如下：

If（gbest！=gbest1）

gbest1=gbest；

else

h=h+1；

3.2 基于邊界與隨機變異的PSO算法

在粒子群優(yōu)化算法中，在k+1代的粒子群位置由（2）式計算得出。當粒子超過邊界時，我們一般取其邊界值，然而在數(shù)值模擬實驗中，我們發(fā)現(xiàn)當例子超出邊界時，我們?nèi)∑渲敌∮谶吔鐣r，對算法的提高有很大幫助，似乎邊界對它們的尋優(yōu)有一定的障礙。

當粒子陷入早熟時，算法再進行迭代時，粒子的位置幾乎不發(fā)生改變，此時，在進行算法迭代已經(jīng)沒有太大意義了。本文提出一個加隨機數(shù)的方法，對陷入早熟的粒子保留一個在其區(qū)域，而對剩下的粒子，每一個粒子的其中一維加上一個[-1，1]之間的一個隨機數(shù)使粒子進行變異跳出早熟區(qū)域，重新搜索。進行變異偽代碼如下：

For（i=0； i

x[i][i]+=2*rand（）-1；

其中x[i][i]表示第i個粒子第i維分量。

根據(jù)以上分析，提出一種新的基于邊界變異的PSO算法，本文記為BVPSO算法，算法步驟如下所示：

Step1 在初始化范圍內(nèi)， 對粒子群 （種群規(guī)模N，維度M ）中各粒子進行隨機初始化，包括隨機位置和隨機速度，算法開始迭代。

Step2 判斷粒子是否達到最優(yōu)值，達到算法結束，輸出最優(yōu)值；若沒達到，則判斷粒子是否陷入局部最優(yōu)，若是，粒子進行變異；若否，則算法再行迭代

Step3 判斷粒子是否達到最優(yōu)值，達到算法結束，輸出最優(yōu)值；若否，判斷算法是否達到最大迭代次數(shù)，若是結束程序，不是返回第二步。

4 數(shù)值仿真實驗

4.1 標準測試函數(shù)

在數(shù)值仿真實驗中，選取了如表1所示的4個標準測試函數(shù)進行數(shù)值實驗。

4.2 實驗參數(shù)設置

各個測試函數(shù)的初始搜索范圍見表1，粒子的最大速度均為初始搜索范圍的10%；SPSO 和BVPSO中的最大最小權重分別取0.9 和0.1，CPSO中壓縮因子取值為0.729。

4.3 實驗方案

為了充分比較BVPSO、SPSO、CPSO算法的優(yōu)化性能，設置了兩種不同檢驗性能的實驗方案。

方案1 固定迭代次數(shù)和種群數(shù)，比較三種算法能達到的最優(yōu)值。該方案中，測試函數(shù)種群數(shù)為40，維數(shù)分別去80，100，每個函數(shù)運行50 次。若算法在10000次迭代中，取其能達到的最優(yōu)值。實驗結果如表2、表3所示。

方案2 預設精度，看算法收斂到預設精度的迭代次數(shù)。該方案取種群數(shù)40時，維數(shù)分別為30，40，預設精度看下表，若算法在超過100000次迭代后，還沒有達到預設的精度，則認為該算法收斂性達不到要求，次數(shù)就為100000。

5 結束語

針對粒子群算法易陷于早熟的問題和什么時候粒子陷入了早熟問題，提出了一種先判定粒子何時達到了早熟，當粒子達到早熟時，提出一種某些維加隨機數(shù)的方法，使陷入早熟的粒子進行變異的BVPSO算法，通過實驗結果分析得出BVPSO算法在解決復雜函數(shù)的大維尋優(yōu)面相對與傳統(tǒng)的SPSO，改進的CPSO算法的性能方面有極大的提高，且在維數(shù)相對來說較小的情況下相對與傳統(tǒng)的兩種算法無論是在收斂精度上還是速度上都有相當?shù)倪M步。 從模擬的實驗結果來看，相對于標準的粒子群優(yōu)化算法SPSO與改進的CPSO算法，新的BVPSO算法從收斂的速度與精度上都有很大的提多，是一種有效的改進算法。

參考文獻

[1] T L Seng， M B Khalid， R Yusof. Tuning of a neuro-fuzzy controller by genetic algorithm[J]. IEEE Trans.Syst.，Man， Cybern.B（S1083-4419），1999，29（2）：226-236.

[2] A Visioli. Tuning of PID controllers with fuzzy logic， Proc[C]//Inst. Elect. Eng. Contr. Theory Applicat， 2001， 148（1）： 1-8.

[3] R A Krohling， J P Rey. Design of optimal disturbance rejection PID controllers using genetic algorithm [J]. IEEE Trans. Evol. Comput. （S1089-778X）， 2001， 5（1）： 78-82.

[4] D B Fogel. Evolutionary Computation： Toward a New Philosophy of Machine Intelligence [M]. New York： IEEE Press， 2000.

[5] Z L Gaing. A Particle Swarm Optimization Approach for Optimum Design of PID Controller in AVR System [J]. IEEE Trans. on Energy Conversion （S0885-8969）， 2004， 19（2）： 384-391.

[6] J Kennedy，R Eberhart. Particle Swarm Optimization [C]//Proc. IEEE Int. Conf. Neural Networks， 1995， 1942-1948.

[7] Y Shi， R C Eberhart. A modified particle swarm optimizer [C]//Proc. IEEE Int. Conf. Evol. Comput.， Anchorage， Alaska， May 1998， 69-73.

基金項目：

東莞理工學院城市學院青年發(fā)展基金（2016QJY007Z）。

作者簡介：

劉依依（1986-），女，漢族，江西九江人，畢業(yè)于廣州大學，碩士，東莞理工學院城市學院，講師；主要研究方向和關注領域：應用數(shù)學、密碼安全。

徐生兵（1980-），男，漢族，湖北荊門人，畢業(yè)于深圳大學，碩士，東莞理工學院城市學院，講師；主要研究方向和關注領域：智能計算。