邵明臣　彭業(yè)飛　張維繼　馮智鑫　張武湛

摘要：針對(duì)粒子群算法存在早熟和收斂較慢兩種缺陷，首先對(duì)粒子群算法的越界方式進(jìn)行了改進(jìn)，由于慣性權(quán)重是標(biāo)準(zhǔn)粒子群優(yōu)化算法中一個(gè)重要的參數(shù)，決定了當(dāng)前粒子速度對(duì)后續(xù)粒子的影響程度，從而控制整個(gè)算法的性能。在研究現(xiàn)有的幾種慣性權(quán)重改進(jìn)策略的基礎(chǔ)上，提出基于適應(yīng)度自適應(yīng)動(dòng)態(tài)調(diào)節(jié)的慣性權(quán)重改進(jìn)算法。通過仿真研究不同的慣性權(quán)重對(duì)算法的影響，發(fā)現(xiàn)改進(jìn)的粒子群算法在每次種群進(jìn)行迭代時(shí)，根據(jù)每個(gè)粒子的適應(yīng)度值自適應(yīng)地改變其慣性權(quán)重，動(dòng)態(tài)調(diào)整每個(gè)粒子的活性，提高了算法的全局搜索能力和收斂能力，較好的改進(jìn)了原算法存在的缺點(diǎn)。

關(guān)鍵詞：粒子群；早熟；慣性權(quán)重；自適應(yīng)；全局搜索

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）02-0196-04

Abstract：The Particle Swarm Optimization has some shortcomings such as premature and slow convergence. Firstly， Transboundary way of the Particle Swarm Optimization has been improve in the paper. The Inertia Weight is an important parameter within the Particle Swarm Optimization.It determine the influence level which current particle against to the subsequent particle， so that it can controll the performance of the algorithm. The Fitness Adaptation Particle Swarm Optimization has been put forward based on researching several existing Inertia Weight improvement strategies. The simulation has been taken through comparing different inertia weight influence of the algorithm. Each particle adaptively change their inertia weight and dynamic adjustment active in each iteration. The Fitness Adaptation Particle Swarm Optimization improve the algorithm's global search ability and convergence capability. Simultaneously， it also improve the shortcomings of the original algorithm exists.

Key words： particle swarm； premature； inertia weight； adaptive； global search

1 概述

作為一種隨機(jī)搜索算法，PSO算法主要存在著“早熟”和收斂較慢兩個(gè)缺陷。為了避免“早熟”，許多研究者提出了通過控制種群多樣性來提高算法性能的方法。Krink等學(xué)者通過解決粒子間的沖突和聚集[1]，基于種群隨機(jī)多代初始化[2]等思想，給出了增強(qiáng)種群多樣性的不同方法，使算法不會(huì)過早陷入局部極值；閆元元[3]等學(xué)者通過引入遺傳算法的“交叉”和“變異”操作來增強(qiáng)全局搜索性能。雖然這些研究工作已經(jīng)給出了提高PSO全局搜索能力的方法，但是它們很難既提高搜索速度又保持種群多樣性。

粒子群優(yōu)化算法的粒子在迭代過程中一直不斷地向最優(yōu)方向飛行，如果遇到局部極值點(diǎn)，所有粒子的速度很快降為零，導(dǎo)致粒子停滯不動(dòng)，出現(xiàn)早熟收斂現(xiàn)象，且難以跳出局部極值點(diǎn)。針對(duì)這一缺點(diǎn)，出現(xiàn)了很多基本粒子群優(yōu)化算法的改進(jìn)算法。慣性權(quán)重是粒子群算法中非常重要的一個(gè)參數(shù)，是微粒群局部搜索和全局搜索能力的平衡點(diǎn)。慣性權(quán)重的選取對(duì)算法的優(yōu)化效果具有較大影響?；诖?，本文通過介紹現(xiàn)有的幾種慣性權(quán)重改進(jìn)策略，建立自適應(yīng)動(dòng)態(tài)調(diào)節(jié)策略的慣性權(quán)重改進(jìn)算法，并進(jìn)行仿真測(cè)試分析。

2 粒子群算法的越界處理

PSO算法基本思想可以描述如下：

3 現(xiàn)有的慣性權(quán)重值改進(jìn)算法

慣性權(quán)重（）是標(biāo)準(zhǔn)粒子群優(yōu)化算法中一個(gè)重要的參數(shù)，決定了當(dāng)前粒子速度對(duì)后續(xù)粒子的影響程度，從而控制整個(gè)算法的性能。具有較強(qiáng)的探索能力的粒子繼承較多，速度較大；具有較強(qiáng)的開發(fā)能力的粒子繼承較小，速度較小。

3.1 線性遞減權(quán)值策略（LAPSO）

線性遞減權(quán)值（[LDW]）策略（Line Adaptation Particle Swarm Optimization，LAPSO）是由shi[4]等學(xué)者在1998年的進(jìn)化計(jì)算的國(guó)際會(huì)議上提出的。慣性權(quán)重[ω]是用來控制粒子以前速度對(duì)當(dāng)前速度的影響，進(jìn)而影響粒子的全局和局部搜索能力。開始Shi只是將[ω]設(shè)為常數(shù)，通過實(shí)驗(yàn)統(tǒng)計(jì)發(fā)現(xiàn)，采用動(dòng)態(tài)的[ω]比固定值更能夠獲得好的尋優(yōu)結(jié)果。當(dāng)[ω]較小，可以提高算法的局部細(xì)致尋優(yōu)能力，而[ω]較大，可以提升算法收斂速度，所以通過調(diào)節(jié)[ω]可以取得收斂速度和局部尋優(yōu)能力間的平衡。在PSO算法運(yùn)算中，[ω]不僅可以線性變化，也可根據(jù)某個(gè)測(cè)度函數(shù)動(dòng)態(tài)改變。LDW策略為：

[ωmax]、 [ωmin]分別為最大和最小慣性權(quán)重，[t]為當(dāng)前迭代步數(shù)，[T]為算法總的迭代次數(shù)，[ω]常在[0.4，0.9]之間變化，隨著迭代步數(shù)的增加而減小，算法在早期具有較快的收斂速度，而后期又有較強(qiáng)的局部搜索能力，[ω]引入使PSO算法性能有了很大提高。

3.2 周期性隨機(jī)擾動(dòng)策略（RAPSO）

學(xué)者于來行[5]提出了具有周期性擾動(dòng)的慣性權(quán)重改進(jìn)策略（Rand Adaptation Particle Swarm Optimization，RAPSO）。該策略基本思想是構(gòu)造一個(gè)非線性變化的公式，通過加入周期性的隨機(jī)擾動(dòng)策略，從而避免算法陷入局部極值的弱點(diǎn)。由于較大的慣性權(quán)重[ω]有利于跳出局部極值點(diǎn)，而較小的有利于提高搜索精度，因此，通過加入正弦函數(shù)和隨機(jī)函數(shù)對(duì)慣性權(quán)重[ω]交互擾動(dòng)，并分別設(shè)定約束系數(shù)，使其隨機(jī)改變，并且具有周期性波動(dòng)下降趨勢(shì)。

4 自適應(yīng)動(dòng)態(tài)調(diào)節(jié)的慣性權(quán)重改進(jìn)算法

如前所述，在粒子群算法中，慣性權(quán)重[ω]起到了一個(gè)平衡全局尋優(yōu)能力和局部尋優(yōu)能力的作用，選擇恰當(dāng)?shù)腫ω]是提高算法的尋優(yōu)能力和收斂能力的關(guān)鍵，基于此，本文在前人的基礎(chǔ)上，建立基于適應(yīng)度自適應(yīng)動(dòng)態(tài)調(diào)節(jié)的粒子群算法（Fitness Adaptation Particle Swarm Optimization，F(xiàn)APSO），根據(jù)種群適應(yīng)度平均值來自適應(yīng)的調(diào)整[ω]。為了，本文建立的自適應(yīng)調(diào)整策略，充分發(fā)揮自適應(yīng)操作的效能，不僅用到群體早熟收斂信息，還根據(jù)個(gè)體適應(yīng)值的不同將群體分為3個(gè)子群，對(duì)各自群體采用不同的自適應(yīng)操作，并根據(jù)粒子的平均適應(yīng)度評(píng)價(jià)粒子的優(yōu)劣。這樣就使得群體始終保持慣性權(quán)重的多樣性。具體算法步驟為：

%假設(shè)求解最大值問題

[Step 1] 計(jì)算種群粒子適應(yīng)度值的平均值[Fmean]，將最優(yōu)粒子適應(yīng)度記為[fm]；

[Step 2] 取出適應(yīng)度值大于[Fmean]的粒子，計(jì)算其平均適應(yīng)度[favg]，將適應(yīng)度值大于[favg]的粒子賦予[ωmax]；

[Step 3] 取出適應(yīng)度值小于[Fmean]的粒子，計(jì)算其平均適應(yīng)度[f′avg]，將適應(yīng)度值小于[f′avg]的粒子[ωmin]；

[Step 4] 將處于[favg]和[f′avg]之間的粒子賦予隨[favg]和[fm]線性變化的值（式2.4）。

式5中，[i=1，2，…m]（[m]為種群大小），[ωmax]、[ωmin]分別表示[ω]最初設(shè)定的最大值和最小值，[fi]表示第[i]粒子當(dāng)前的目標(biāo)函數(shù)值。該方法的慣性權(quán)重隨著粒子的目標(biāo)函數(shù)值而自動(dòng)改變，若粒子的目標(biāo)值區(qū)域一致或者趨于局部最優(yōu)，增加慣性權(quán)重使之跳出局部進(jìn)行全局最優(yōu)搜索；若各粒子的目標(biāo)值比較分散，減小慣性權(quán)重進(jìn)行最優(yōu)搜索。同時(shí)，對(duì)于目標(biāo)函數(shù)值優(yōu)于平均目標(biāo)的粒子，減小慣性權(quán)重可以保護(hù)該粒子，反之對(duì)于差于平均目標(biāo)值的粒子，對(duì)應(yīng)的權(quán)重增大，使之向較好的搜索區(qū)域靠攏。

5 算法仿真測(cè)試

5.1 測(cè)試函數(shù)

為了測(cè)試算法的性能，選用國(guó)際上通用[CEC]提出的[benchmarch]測(cè)試函數(shù)。本文采用以下四個(gè)經(jīng)典的測(cè)試函數(shù)：

Rosenbrock函數(shù)在[x1，x2…xn=1，1…1]時(shí)達(dá)到極小值0。Rosenbrock函數(shù)全局最優(yōu)點(diǎn)位于一個(gè)狹長(zhǎng)且平滑的山谷內(nèi)，一般的優(yōu)化算法很難辨別搜索方向，使得函數(shù)的最優(yōu)解很難尋找。

本文所有算法的仿真平臺(tái)：處理器：Intel（R）Core（TM）i5-4210U CPU @1.7GHz 2.4GHz；安裝內(nèi)存：4.00GB；Windows版本：Windows7旗艦版；系統(tǒng)類型：64位操作系統(tǒng)；仿真軟件：MatLab2013a。

5.2 仿真結(jié)果與分析

為了測(cè)試算法的性能，本文選取Griewank和Rastrigrin函數(shù)將LAPSO、RAPSO、FAPSO三種算法與BPSO算法（原始粒子群算法）進(jìn)行仿真比較，參數(shù)設(shè)置為：迭代次數(shù)Gmax=500；種群規(guī)模m=20，學(xué)習(xí)因子C1=C2=2慣性權(quán)重[ω]最大值0.9，最小值0.4， 粒子最大速度設(shè)為粒子的范圍寬度， BPSO算法的慣性權(quán)重為 0.64，越界處理方法均采用本文提出的隨機(jī)初始化法。每種算法各運(yùn)行 30 次并記錄每次得到的全局極值，計(jì)算每種算法的可靠性和準(zhǔn)確性并進(jìn)行比較。

圖4至圖7分別給出了三種策略下慣性權(quán)重值的變化過程，其中，圖4為隨迭代次數(shù)線性變化的慣性權(quán)重，圖5為周期性擾動(dòng)的慣性權(quán)重變化曲線圖，圖6記錄在FAPSO算法運(yùn)行過程中某一粒子經(jīng)歷過的慣性權(quán)重值，圖7給出了在FAPSO算法迭代100次時(shí)慣性權(quán)重在粒子中的分布圖。

由圖5可以看出，采用周期性隨機(jī)擾動(dòng)策略時(shí)，通過正弦函數(shù)和隨機(jī)函數(shù)的交互擾動(dòng)，慣性權(quán)重值隨機(jī)改變并且具有周期性波動(dòng)下降的趨勢(shì)，開始時(shí)[ω]較大，隨著迭代的進(jìn)行，[ω]周期性波動(dòng)下降。由圖6和圖7可以看出，基于適應(yīng)度自適應(yīng)調(diào)節(jié)[ω]的策略有這樣的特點(diǎn)：同一粒子在不同的迭代次數(shù)具有不同的慣性權(quán)重，同一迭代次數(shù)各粒子的慣性權(quán)重不同。這種不同性是基于粒子本身的適應(yīng)度實(shí)時(shí)進(jìn)行調(diào)節(jié)的，很好地體現(xiàn)了“自適應(yīng)”的思想。

由圖8和圖9可以看出，三種策略改進(jìn)的慣性權(quán)重值均較好的提高了算法的尋優(yōu)性能，尤其是基于適應(yīng)度自適應(yīng)調(diào)節(jié)的FAPSO算法，在搜索精度和收斂性上，更優(yōu)于其他算法。

由以上數(shù)據(jù)可以看出，基于適應(yīng)度動(dòng)態(tài)調(diào)節(jié)的FAPSO算法，無論是從可靠性和準(zhǔn)確性上比較，還是從最優(yōu)解和方差（即算法的穩(wěn)定性）上對(duì)比，F(xiàn)APSO比LAPSO、RAPSO、BPSO有較大改進(jìn)，同時(shí)，F(xiàn)APSO算法對(duì)解決一些多峰函數(shù)等復(fù)雜問題也更勝一籌。

6 小結(jié)

本文首先對(duì)粒子群算法進(jìn)行了越界改進(jìn)，通過研究現(xiàn)有的幾種慣性權(quán)重改進(jìn)策略，提出采用基于適應(yīng)度動(dòng)態(tài)調(diào)節(jié)的慣性權(quán)重改進(jìn)算法。改進(jìn)的粒子群算法在每次種群進(jìn)行迭代時(shí)，根據(jù)每個(gè)粒子的適應(yīng)度值自適應(yīng)地改變每個(gè)粒子的慣性權(quán)重，動(dòng)態(tài)調(diào)整每個(gè)粒子的活性，提高了算法的全局搜索能力和收斂能力?？傊Ｗ尤核惴ǖ膽T性權(quán)重在粒子尋優(yōu)過程中具有重要作用，如何尋找合適的慣性權(quán)重是提高算法性能關(guān)鍵。

參考文獻(xiàn)：

[1] Krink T， Vesterstrom J S， Riget J. Particle swarm optimization with spatial particle extension. Pros. of the IEEE Int'1Conf.on Evolutionary Computation. Honolulu： IEEE Inc. 2002：1474-1497.

[2] Hu XH， Eberhart RC. Adaptive particle swarm optimization： Detection and response to dynamic system. Proc. of the IEEE Int'1 Conf. on Evolutionary Computation. Honolulu： IEEE Inc.， 2002：1666-1670.

[3] 閆元元，高興寶，周喜虎. 基于變異和交叉的改進(jìn)粒子群算法[J]. 陜西科技大學(xué)學(xué)報(bào)，2011（29）：121-124.

[4] Shi Y，Ebernart R.C...A modined partiele swam optimizer[C].Proeeedings of the IEE Congresson Evolutionary ComPutation，1998，69-73.

[5] 于來行，喬蕊.周期性擾動(dòng)的微粒群算.計(jì)算機(jī)系統(tǒng)應(yīng)用[J].2011， 20（ 6）：203-205.