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

劉依依+徐生兵

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

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

【 中圖分類號 】 TP18

【 文獻(xiàn)標(biāo)識碼 】 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)化算法。它是一種仿真算法，是模擬自然界一些生物的行為，如鳥群覓食、魚群學(xué)習(xí)等。由于其容易理解、易于實(shí)現(xiàn)、不要求目標(biāo)函數(shù)和約束條件是可微的， 并能以較大概率求得全局最優(yōu)解， 目前已在許多優(yōu)化問題中得到成功應(yīng)用。與其它進(jìn)化算法類似， 粒子群優(yōu)化算法也存在早熟收斂現(xiàn)象， 尤其是在比較復(fù)雜的多峰搜索問題中。目前解決這一問題的主要方法是增加粒子群的規(guī)模， 雖然對算法性能有一定改善， 但同樣存在缺陷：一是不能從根本上克服早熟收斂問題；二是會大大增加算法的運(yùn)量。

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

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

3 改進(jìn)的粒子群算法

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

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

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

If（gbest！=gbest1）

gbest1=gbest；

else

h=h+1；

3.2 基于邊界與隨機(jī)變異的PSO算法

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

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

For（i=0； i

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

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

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

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

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

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

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

4.1 標(biāo)準(zhǔn)測試函數(shù)

在數(shù)值仿真實(shí)驗(yàn)中，選取了如表1所示的4個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)。

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

4.3 實(shí)驗(yàn)方案

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)

[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.

基金項(xiàng)目：

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

作者簡介：

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

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