一種帶變異算子的自適應(yīng)慣性權(quán)重二進(jìn)制粒子群優(yōu)化算法

王 越,邱飛岳，郭海東

(浙江工業(yè)大學(xué) 教育科學(xué)與技術(shù)學(xué)院,杭州 310023)

1 引 言

粒子群算法(Particle Optical Swarm)是由美國心理學(xué)家James Kennedy和電氣工程師Russell Eberhart[1]在1995年提出的一種自適應(yīng)群體智能搜索算法,由于PSO算法所需調(diào)節(jié)的參數(shù)較少,概念簡單且容易實(shí)現(xiàn),已被廣泛應(yīng)用于神經(jīng)醫(yī)學(xué)、網(wǎng)絡(luò)訓(xùn)練和運(yùn)籌學(xué)等領(lǐng)域的優(yōu)化問題[2-4].由于在實(shí)際應(yīng)用當(dāng)中很多問題是離散型的問題,因此,James Kennedy和Russell Eberhart在1997年又提出一種二進(jìn)制粒子群算法(Binary Particle Optical Swarm)[5],用來解決離散性的優(yōu)化組合問題.二進(jìn)制粒子群優(yōu)化算法也已被很多領(lǐng)域廣泛應(yīng)用,例如背包問題[6]、電力系統(tǒng)[7]、數(shù)據(jù)挖掘[8,9]、圖像處理[10]等.BPSO算法尋找最優(yōu)解依靠粒子間信息傳遞與共享的特征決定了算法種群多樣性和搜索性能對算法的收斂速度和收斂精度起主要作用.但二進(jìn)制粒子群算法不能動態(tài)調(diào)整粒子群算法的搜索范圍,因?yàn)樗膽T性權(quán)重值不能隨種群迭代動態(tài)改變,這就引起了二進(jìn)制粒子群算法會隨著種群多樣性的下降,容易早熟收斂而陷入局部最優(yōu).針對這種二進(jìn)制粒子群算法的缺點(diǎn),很多學(xué)者都提出了各種改進(jìn)方法.首先Chuang L Y等學(xué)者[11]采用混沌映射確定慣性權(quán)重值的方法提高二進(jìn)制粒子群優(yōu)化算法的性能.由于混沌映射的行為不存在固定點(diǎn)、周期軌道或準(zhǔn)周期軌道.因此,改進(jìn)的算法可以避免陷入局部最優(yōu).Mirjalili S等學(xué)者[12]采用慣性權(quán)重值線性減小的策略來優(yōu)化二進(jìn)制粒子群算法.然而,沒有理論研究或分析能支持直接采用這種方法的有效性.Liu J等學(xué)者[13]證明了在二進(jìn)制情況下,較小的慣性權(quán)重提高探索能力,而較大的慣性權(quán)重提高開發(fā)能力,所以提出了慣性權(quán)重線性增長的二進(jìn)制粒子群優(yōu)化算法.但在慣性權(quán)重值線性增長的過程中往往會忽略線性增長附近最優(yōu)解的存在.

本文提出一種帶變異算子的自適應(yīng)慣性權(quán)重二進(jìn)制粒子群優(yōu)化算法(MABPSO).首先提出慣性權(quán)重的非線性遞增策略,該策略確保慣性權(quán)重能夠根據(jù)種群迭代進(jìn)行自適應(yīng)調(diào)整,使算法在迭代后期擁有較大的慣性權(quán)重,提高算法全局搜索能力,避免陷入局部最優(yōu);其次設(shè)計變異算子用于粒子的搜索過程,擴(kuò)大粒子的搜索范圍,進(jìn)而提高二進(jìn)制粒子群優(yōu)化算法跳出局部最優(yōu)的能力.通過測試函數(shù)表明該算法提高了收斂速度和收斂精度,同時避免了早熟收斂和陷入局部最優(yōu)的問題.

2 二進(jìn)制粒子群優(yōu)化算法

在D維解空間中,有N個粒子組成一個群體x=[x1,x2,…,xN],每個維度下的粒子都可以由其速度向量信息和位置向量信息進(jìn)行表示,粒子i的速度向量和位置向量表示如下:vi=[vi1,vi2,…,viD],xi=[xi1,xi2,…,xiD].第i個粒子的個體極值為pi=[pi1,pi2,…,piD];gi=[gi1,gi2,…,giD]表示種群的全局極值.當(dāng)前粒子位置的優(yōu)劣程度由適應(yīng)度函數(shù)進(jìn)行檢測,達(dá)到最大迭代次數(shù)或最佳精度后,輸出最優(yōu)解.BPSO算法的速度和位置更新公式如式(1)、式(2)所示:

(1)

(2)

在BPSO中,用概率描述了粒子位置的變化和速度的變化狀態(tài).狀態(tài)空間中粒子的位置用0或1表示,S(vid)代表xid取1的概率,基本公式如下所示:

(3)

(4)

其中,rand()是分布在[0,1]內(nèi)的隨機(jī)數(shù),式(4)表示Sigmoid函數(shù).

3 改進(jìn)二進(jìn)制粒子群優(yōu)化算法

3.1 慣性權(quán)重非線性遞增策略

在二進(jìn)制粒子群優(yōu)化算法中較小的慣性權(quán)重提高探索能力,而較大的慣性權(quán)重注重開發(fā).通過文獻(xiàn)[13]可知,對慣性權(quán)重進(jìn)行線性優(yōu)化雖然有助于提升算法性能,但是該策略不能有效滿足算法的尋優(yōu)過程,對開發(fā)和搜索性能不能達(dá)到有效平衡.因此,為了更加的接近算法尋優(yōu)的實(shí)際進(jìn)化狀態(tài),本文對慣性權(quán)重進(jìn)行非線性遞增優(yōu)化.在每次迭代中,慣性權(quán)重ω計算如下:

(5)

其中t和T分別代表迭代次數(shù)和最大迭代次數(shù),取ωmax=0.9,ωmin=0.4時曲線如圖1所示:

圖1曲線表明,隨著迭代次數(shù)的增加,慣性權(quán)重呈現(xiàn)非線性遞增狀態(tài),可以知道改進(jìn)后的算法在尋優(yōu)早期有較小的w,具有較強(qiáng)的局部探索能力;在尋優(yōu)后期具有較大的w,具有較強(qiáng)的全局探索能力.

3.2 變異算子

由于變異算子在提升算法收斂性能方面有著顯著表現(xiàn),因此本文在借鑒遺傳算法變異思想的基礎(chǔ)上,結(jié)合文獻(xiàn)[14],將變異算子融入二進(jìn)制粒子群優(yōu)化算法中,防止算法出現(xiàn)早熟收斂的現(xiàn)象.對二進(jìn)制粒子群改進(jìn)公式如下:

圖1 慣性權(quán)重變化曲線Fig.1 Inertia weight change curve

(6)

其中,Random為解空間隨機(jī)位置;ρ為對未知世界的好奇系數(shù),經(jīng)過大量實(shí)驗(yàn)觀察,設(shè)置ρ=2可以得到最好的效果,r3是分布在[0,1]內(nèi)的隨機(jī)數(shù).由于加入了對未知空間探索的機(jī)制,不僅使粒子尋優(yōu)范圍得到擴(kuò)大,種群多樣性得到增強(qiáng),而且使算法更易于跳出局部最優(yōu),從而防止算法的早熟收斂.

3.3 MABPSO算法步驟

MABPSO算法從慣性權(quán)重和變異算子兩個角度對BPSO進(jìn)行了優(yōu)化,步驟如下:

Step 1.初始化MABPSO算法的粒子速度、位置、個體與全局極值等參數(shù).

Step 2.計算粒子適應(yīng)度值.

Step 3.粒子根據(jù)適應(yīng)度值,更新個體最優(yōu)和全局最優(yōu)

Step 4.根據(jù)公式(5)對慣性權(quán)重更新.

Step 5.通過公式(6)和公式(3)實(shí)現(xiàn)粒子速度和位置更新

Step 6.若算法達(dá)到終止條件,則輸出最優(yōu)值,否則返回到步驟2.

4 實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計

為了驗(yàn)證本文提出的MABPSO算法的優(yōu)化性能,分別在三個單峰Sphere、Step、Rosenbrock函數(shù)和三個復(fù)雜的多峰Rastrigin、Ackley、Griewank函數(shù)進(jìn)行測試.并利用慣性權(quán)重線性遞減的二進(jìn)制粒子群優(yōu)化算法(BPSO)[5]、慣性權(quán)重線性增大的二進(jìn)制粒子群優(yōu)化算法(UPBPSO)[13]和結(jié)合本文提出的帶未知空間探索變異算子的二進(jìn)制粒子群優(yōu)化算法(MBPSO)進(jìn)行對比.測試函數(shù)參數(shù)如表1所示.

算法參數(shù)設(shè)置如下:4種算法最大迭代次數(shù)為1000,種群規(guī)模為30,在300維情況下運(yùn)行.4個算法BPSO、UPBPSO、MBPSO、MABPSO中,慣性權(quán)重初始值ω為2,最大值ωmax為0.9,最小值ωmin為0.4,c1、c2值為2,MABPSO算法中ρ值設(shè)置為2.

表1 測試函數(shù)
Table 1 Test function

函數(shù)名稱表達(dá)式極值Sphere(F1)F1(x)=∑Di=1x2i0Step(F2)F2(x)=∑Di=1(xi+0.5)20Ackley(F3)F3(x)=-20exp-0.21D∑Di=1x2i()-exp1D∑Di=1cos(2πxi)()+20+e0Rastrigin(F4)F4(x)=∑Di=1[x2i-10cos(2πxi)+10]0Griewank(F5)F5(x)=1400∑Di=1x2i-∏Di=1cosxii+10Rosenbrock(F6)F6(x)=∑Di=1(1-xi)2+100(xi+1-x2)20

實(shí)驗(yàn)中對算法性能的評價標(biāo)準(zhǔn)如下:

1)均值:算法運(yùn)行n次得到最優(yōu)解結(jié)果的均值.

2)方差:算法執(zhí)行n次得到最優(yōu)解結(jié)果的方差.

3)最優(yōu)值:算法執(zhí)行n次后,n個最優(yōu)值中最好的一個.

4)最劣值:算法執(zhí)行n次后,n個最優(yōu)值中最差的一個.

為使測試結(jié)果更加公平,所有測試均采用Inter Core i5 2.3G雙核處理器,16G內(nèi)存,MacOS操作系統(tǒng),Matlab2014b仿真環(huán)境.

4.2 實(shí)驗(yàn)結(jié)果分析

4種算法在300維情況下對每個測試函數(shù)獨(dú)立運(yùn)行30次,分別保存最好值、最差值、平均值和標(biāo)準(zhǔn)差,實(shí)驗(yàn)結(jié)果如表2所示.

單峰函數(shù)只有一個全局最優(yōu)解而沒有局部最優(yōu)解,適合檢測算法的收斂精度.從表2中可以看出,在單峰函數(shù)F1、F2、F6中,MBPSO所得最優(yōu)值、最劣值、均值均好于BPSO和UPBPSO算法,說明MBPSO的收斂精度高于BPSO和UPBPSO算法,同時MABPSO的最好值、最差值、均值均好于MBPSO,說明MABPSO的收斂精度高于MBPSO,并且是4個算法中最好的.

表2 測試函數(shù)為300維時數(shù)據(jù)
Table 2 Test function is 300-dimensional data

函數(shù)算法最好值最差值均值標(biāo)準(zhǔn)差F1BPSO6.1E+017.6E+016.93667+013.1457E+00UPBPSO5E+016.3E+015.80333E+012.7852E+00MBPSO1.4E+012.3E+011.91667E+012.0356E+00MABPSO1.1E+011.4E+011.26333E+019.6431E-01F2BPSO2.01E+022.23E+022.13067E+025.343E+00UPBPSO1.79E+022.01E+021.89867E+025.1644E+00MBPSO1.07E+021.21E+021.13733E+023.7686E+00MABPSO9.3E+011.03E+029.84E+012.634E+00F3BPSO1.7515E+001.9033E+001.8318E+003.3575E-02UPBPSO1.6125E+001.7648E+001.6831E+004.1957E-02MBPSO8.7472E-011.1E+009.9547E-014.8829E-02MABPSO7.5146E-018.7472E-018.0348E-013.399E-02F4BPSO8.97058E+058.97074E+058.97068E+053.3107E+00UPBPSO8.97051E+058.97066E+058.97058E+053.4833E+00MBPSO8.97016E+058.97021E+058.97019E+051.4499E+00MABPSO78.97009E+058.97015E+058.97012E+051.4559E+00F5BPSO2.8021E-013.2892E-013.0051E-011.2605E-02UPBPSO2.3249E-012.7367E-012.5647E-019.7287E-03MBPSO7.3791E-021.0507E-018.794E-027.3989E-03MABPSO74.3721E-026.422E-025.3927E-025.8385E-03F6BPSO8.847E+031.0147E+049.58153E+033.09499E+02UPBPSO8.149E+039.446E+038.95893E+033.44979E+02MBPSO3.22E+034.326E+033.73267E+032.75589E+02MABPSO72.01E+033.374E+032.522E+033.66129E+02

多峰函數(shù)具有多個局部最優(yōu)解且隨問題維度的增加成指數(shù)增加,適合檢測算法避免陷入局部最優(yōu)解的能力.從表2中可以看出,在多峰函數(shù)F3、F4、F5中,MBPSO所得最好值、最差值、均值均好于BPSO和UPBPSO算法,說明MBPSO避免陷入局部最優(yōu)解的能力強(qiáng)于BPSO和UPBPSO,同時MABPSO在所有測試函數(shù)上的最好值、最差值、均值均好于MBPSO,說明MABPSO避免陷入局部最優(yōu)解的能力強(qiáng)于MBPSO,并且是四個算法中最好的.

無論是多峰函數(shù)還是單峰函數(shù),MBPSO所得最好值、最差值、均值均好于BPSO和UPBPSO算法,說明未知空間探索的變異算子對速度公式的改進(jìn)使粒子探索范圍得到擴(kuò)大,逃離局部解的能力得到加強(qiáng);同時MABPSO在所有測試函數(shù)上的最好值、最差值、均值均好于MBPSO,說明慣性權(quán)重值的非線性增長,更好的平衡了算法全局探索與局部開采的性能,較大提升了算法收斂效率.在F1、F2、F5上,MABPSO有最好的標(biāo)準(zhǔn)差,在F3、F4、F6上,MABPSO的標(biāo)準(zhǔn)差比BPSO和MBPSO略大,但差別很小,說明MABPSO算法在提升收斂精度和增強(qiáng)算法跳出局部最優(yōu)解能力的同時,沒有破壞算法的穩(wěn)定性.

圖2 函數(shù)F1收斂曲線圖Fig.2 Function F1 convergence curve

圖3 函數(shù)F2收斂曲線圖Fig.3 Function F2 convergence curve

圖4 函數(shù)F3收斂曲線圖Fig.4 Function F3 convergence curve

圖5 函數(shù)F4收斂曲線圖Fig.5 Function F4 convergence curve

圖6 函數(shù)F5收斂曲線圖Fig.6 Function F5 convergence curve

圖7 函數(shù)F6收斂曲線圖Fig.7 Function F6 convergence curve

圖8 函數(shù)F1箱須圖Fig.8 Function F1 box whisker

圖9 函數(shù)F2箱須圖Fig.9 Function F2 box whisker

圖10 函數(shù)F3箱須圖Fig.10 Function F3 box whisker

圖11 函數(shù)F4箱須圖Fig.11 Function F4 box whisker

圖13 函數(shù)F6箱須圖Fig.13 Function F6 box whisker

算法的收斂圖可以清楚的表明各個算法的尋優(yōu)過程.圖2-圖7分別表示4個算法在維數(shù)D=300時,在6個測試函數(shù)上獨(dú)立運(yùn)行30次的平均收斂曲線.從圖中可以看出,在F1、F2、F3、F4、F5、F6上,BPSO算法的最終收斂精度劣于UPBPSO算法;向基本的BPSO算法加入變異算子設(shè)計的MBPSO相比BPSO算法、UPBPSO算法,收斂速度和收斂精度顯著提高,說明加入未知空間探索的變異算子,擴(kuò)大了粒子的搜索范圍,增強(qiáng)了粒子的種群多樣性,極大提高了算法的收斂速度和收斂精度;但是在跳出局部最優(yōu)值方面的能力還有所欠缺.從圖中可知,融合變異算子和自適應(yīng)慣性權(quán)重的MABPSO算法比其他3種算法不易陷入局部最優(yōu),收斂精度上也更加精確,說明自適應(yīng)調(diào)整的慣性權(quán)重平衡了算法的全局搜索和局部搜索,慣性權(quán)重的非線性遞增變化比線性遞增變化更符合粒子的運(yùn)動規(guī)律,進(jìn)一步提高了算法的性能.

為了更加直觀看出解集分布情況,給出了4種算法在6個測試函數(shù)上的解集箱須圖,如圖8-圖13所示.

從圖8-圖13所示中可以看出,在F1、F2、F6三個單峰函數(shù)中,MABPSO算法得到的數(shù)據(jù)整體都比其他算法得到的數(shù)據(jù)更加接近橫坐標(biāo)軸,說明數(shù)據(jù)MABPSO算法得到的解優(yōu)于對比算法.在Sphere函數(shù)和Step函數(shù)上,數(shù)據(jù)MABPSO算法得到的數(shù)據(jù)范圍小于對比算法,說明MABPSO更加具有較好的穩(wěn)定性.在F3、F4、F5三個多峰函數(shù)上,MABPSO算法得到的數(shù)據(jù)同樣更加接近橫坐標(biāo)軸,得到的數(shù)據(jù)范圍也小于對比算法,說明MABPSO算法不僅具有較好的收斂性能,而且具有較好的穩(wěn)定性.因此,本文提出的MABPSO算法不管是在簡單的單峰函數(shù),還是在較復(fù)雜的多峰函數(shù)上都具有較好的收斂表現(xiàn).

5 結(jié) 論

為改善二進(jìn)制粒子群優(yōu)化算法在尋優(yōu)過程中收斂速度慢、搜索精度不高和易陷入局部最優(yōu)而無法取得全局最優(yōu)解的問題,本文提出慣性權(quán)重非線性遞增的改進(jìn)策略,該策略平衡了二進(jìn)制粒子群算法的全局探索與局部開采性能.同時,引入對未知空間搜索的變異算子對BPSO算法進(jìn)行改進(jìn),提高了算法的執(zhí)行速度,增強(qiáng)了種群多樣性,進(jìn)而大幅度加強(qiáng)了算法避免陷入局部最優(yōu)的能力,從整體上提高了算法的收斂速度和收斂精度.仿真實(shí)驗(yàn)結(jié)果表明,本文提出的帶變異算子的自適應(yīng)慣性權(quán)重二進(jìn)制粒子群優(yōu)化算法與其它算法相比,收斂速度更快,收斂精度更高,是一種優(yōu)化能力強(qiáng),穩(wěn)定性好的全局優(yōu)化算法.