基于鄰域搜索的粒子群動態優化算法

申鼎才, 胡聲洲

(1.贛南師范大學 數學與計算機科學學院,江西 贛州 341000; 2.湖北工程學院 計算機與信息科學學院,湖北 孝感 432000)

基于鄰域搜索的粒子群動態優化算法

申鼎才1,2, 胡聲洲1

(1.贛南師范大學 數學與計算機科學學院,江西 贛州 341000; 2.湖北工程學院 計算機與信息科學學院,湖北 孝感 432000)

常規的粒子群優化(particle swarm optimization,PSO)算法在求解動態環境下優化問題時，由于其收斂性而失去對最優解的跟蹤能力。為了更好地增加種群的多樣性,以保證算法更好地追蹤動態環境下最優解的變化,文章提出一種基于鄰域搜索的粒子群動態優化算法(neighborhood search particle swarm optimization,NSPSO)。在每一演化代中對個體依適應值從大到小排序,并對排序后的個體按從大到小的順序以一定的比例分配Leader、Follower、Scouter 3種不同的角色,不同角色的個體采用不同的更新策略,使得算法在維持一定開發能力的同時維持較強的探索能力。通過對移動峰問題的實驗發現NSPSO算法具有較小的離線誤差,且離線誤差受變化強度的影響均小于其他用于比較的算法,從而驗證了NSPSO算法能夠有效地跟蹤動態環境下最優解的變化。

粒子群優化(PSO);動態優化問題;鄰域搜索;多角色;演化計算

0 引 言

粒子群優化(particle swarm optimization,PSO) 算法[1]是一種基于群體智能的演化算法,由于PSO算法參數少、收斂速度快,在大規模優化問題的求解中取得了很好的性能[2],因此自提出以來得到了廣泛的應用,但大多數研究成果是基于靜態優化問題。然而實際應用中很多優化問題是動態的,即被優化問題的目標函數、約束條件、環境參數中的1個或多個會隨著時間的變化而改變。因此算法的目的不再是獲得優化問題的最優解,而轉變為算法對最優解在搜索空間內的追蹤能力,從而給傳統的PSO帶來新的挑戰。因為隨著算法的不斷演化,種群中的粒子逐漸收斂到最優解附近,種群多樣性減小,從而失去對環境變化的跟蹤能力。

為了使PSO在整個算法的執行期間維持較大的種群多樣性,同時又能更快地追蹤到最優解的變化,本文提出一種基于鄰域搜索的粒子群動態優化算法(neighborhood search particle swarm optimization,NSPSO),通過對移動峰測試函數(move peak benchmark,MPB)的實驗,驗證了該算法能很好地跟蹤動態環境的變化。

1 相關研究

在動態環境下,為了使算法能較好地跟蹤最優解的變化,研究者們提出了各種策略來提高演化算法在動態環境下的性能,如基于記憶的機制[3]采用保存算法獲得的最優解并把該解參與到后續的演化過程中,這種策略在周期性變化的環境中能夠獲得較好的動態性能。另外在算法的演化過程中維持較高的種群多樣性也是算法獲得較高跟蹤最優解變化能力的有效策略。典型的有隨機移民策略[4]、超變異策略[5]等。隨機移民策略通過在演化過程中引入隨機生成的新個體并按一定比例替換種群中已有個體。具體替換策略主要分隨機替換和替換種群中適應值最差個體2種;超變異策略則在演化過程中一旦檢測到環境發生變化，則采用加大變異概率,以此來增加種群多樣性,從而使算法能更好地適應變化的環境。此外,采用多種群算法,并在不同的種群采用不同的搜索策略在動態的環境下也取得了很好的效果[6-7]。近年來,PSO應用于動態環境下優化問題的求解受到廣泛關注[8]。

2 基于領域搜索的動態粒子群算法

2.1 算法基本思想

在PSO群體中,個體的運動方向受其自身歷史最優位置和群體中全局最優位置影響而不時作出調整。在常規的PSO中,隨著演化的進行,種群中的所有粒子將聚集在最優個體附近,此時如果最優解的位置發生變化,則算法將失去探索新解的能力[9]。在演化動態優化領域,通過維持種群多樣性來達到跟蹤最優解的變化是一類有效的策略。因此,如果在算法的演化過程中能引入相應策略來保持種群的多樣性,使得算法在維持一定開采能力的同時,又能維持較高的探索能力。受文獻[10]和人工蜂群算法[11]中把個體分為不同角色進行演化的思想啟發,本文提出NSPSO算法。該算法在每一演化代中,種群中的粒子依適應值從大到小排序,并按一定比例分成3類角色,各角色在更新的過程中采用不同的更新策略。本文把PSO中個體分為Leader、Follower和Scoute 3類角色,其中Leader為當前種群中適應值排在最前面一定比例的個體,其個數可以是1個到多個,緊接著Leader個體為Follower角色個體,其數量也是按一定比例設定,種群中剩余的個體為Scouter個體。Leader個體的更新公式如下:

(1)

其中，xL為當前Leader角色中不同于個體i的隨機選擇的個體;xk為Leader角色個體中不同于i、L的個體;φi為[-1,1]范圍內的一個隨機數;R為鄰域半徑常數。

Follower個體的更新策略與Leader更新類似,所不同的是(1)式中xL設為Leader角色個體中隨機選擇的個體,即Follower個體圍繞Leader個體一定鄰域內搜索最優值。Scouter角色更新采用常規的PSO更新策略[2]。即Scouter在其余搜索區域隨機搜索。

2.2 算法實現

NSPSO算法實現的基本步驟如下:

(1) 初始化,t←0,在目標搜索空間內隨機生成N個個體種群P(t),設置Leader個體和Follower個體占種群大小的比值RL和RF。

(2) 對種群P(t)進行評估,并依適應值由高到低進行排序。

(3) 根據預設的RL和RF依適應值從高到低的順序按比例分配Leader個體和Follower個體,其余個體分配為Scouter個體。

(4) 分別對Leader、Follower、Scouter角色個體執行更新操作,并同時更新個體歷史最優值和全局最優值。

(5) 若終止條件不滿足,則P(t)←P(t+1),t←t+1,轉步驟(2);否則算法終止。

本文比較了NSPSO算法與帶電粒子群優化算法[12](charged particle swarm optimization,CPSO)、隨機移民粒子群優化算法(random immigrant particle swarm optimization,RIPSO)和常規PSO(standard PSO,SPSO)在動態優化問題中的性能。

3 實驗結果與分析

MPB[13]被經常用來測試動態優化算法的性能。MPB具有多維、多峰的特點,具有m個峰的n維函數可表示為:

F(x,t)=maxB(x),

(2)

其中,B(x)為一個非時變的基準函數;P為定義峰形狀的函數,每經歷Δe次評估,各個峰的位置pi、寬度wi、高度hi均依一個高斯變量σ∈N(0,1)變化,峰位置移動由一個長度為s的隨機變量控制,s的大小決定環境變化的強度,Δe的大小則決定環境變化的頻率。

PSO相關的參數及用于比較的算法中參數設置為:慣性權重w設置為0.729 8,學習因子c1=c2=2.05。 CPSO中,Q=0.1,pcore=2.187,prepel=31.5;RIPSO中遷移率為種群大小的10%;NSPSO中各角色比例分配經初步實驗得出Leader、Follower、Scouter之比為0.04∶0.5∶0.46時取得較好性能,(1)式中鄰域半徑R設為1.62。所有算法中種群大小均為50。MPB的設置則依文獻[13]中第2種情形設置。主要參數設置為:峰的個數m=10,s=1.0,Δe=5 000。同時對所選算法在其他變化強度s下離線誤差性能作了分析。

在動態環境中,最優解隨著環境的變化而變化,算法不再以求得唯一最優解為最終目標,而是以算法對最優解的跟蹤能力來衡量算法的性能。由于選定的MPB測試函數每次環境變化中實際最優值是已知的,因此本文采用離線誤差,即每次評估時實際最優值和算法求得的最優解的誤差平均值,其計算公式為:

(3)

其中,e(t)為到第t次評估時最優解的誤差；T為總的評估次數。

3.1 離線誤差結果和分析

在隨機的環境變化中,函數的適應值曲線隨機變化,各個峰的高度、寬度和位置隨機變化,函數最優解的位置也隨之發生變化。 在上述設定參數下,各算法采用相同隨機數種子生成移動峰進行測試,實驗中種群個體采用不同的隨機數種子隨機生成,對MPB運行30次取平均值,所獲得的離線誤差及標準差見表1所列。

表1 離線誤差及其標準差

同時,為了更好地比較算法在執行過程中的性能,各算法離線誤差與迭代次數的關系如圖1所示。

圖1 各算法離線誤差性能曲線

從表1和圖1可以看出,NSPSO離線誤差明顯優于其他3種選定的算法,且算法比較穩定,其標準差在4種算法中最小。SPSO算法離線誤差最大,標準差也是4種算法中最大的。可以看出,常規的PSO算法雖然在靜態環境下取得了較好的性能,但在動態環境下,由于算法在迭代后期會收斂于最優解,從而失去對最優解的動態跟蹤。在參與比較的4種算法中,RIPSO的性能比較接近NSPSO,由此可以得出,雖然常規的PSO算法由于受全局最優解的影響而失去對動態環境的跟蹤能力,但通過在其演化過程中引入一定數量的新個體即可以比較好地跟蹤最優解的動態變化。CPSO在4種算法中動態性能居第3的位置,由于算法中參數的設置對其動態性能的影響較大[14],就本文選定的參數來看,其動態性能略優于常規的PSO算法,獲得該算法更好性能的參數設置有待于進一步的研究。

此外,從圖1可以得出,在迭代初期,NSPSO離線誤差要劣于其他算法,大約經過10次環境變化后,NSPSO的優勢逐漸顯現出來,離線誤差逐漸變小。對于SPSO,在環境變化初期,由于峰值位置相對于初始位置變化較小,接近于靜態環境下的位置,此時SPSO表現出較好的性能。隨著迭代的持續進行,峰值位置相對初始階段偏移較大,此時SPSO的跟蹤性能呈現逐漸降低的趨勢。從圖1中還可以發現,在種群中引入一定量的新生個體,對算法維持較高的多樣性有較大的幫助。在整個變化周期中,RIPSO的離線誤差維持在一個較為穩定的水平,其原因是算法每一代都引入一定比例的新的隨機產生的個體。

3.2 各變化強度下離線誤差結果和分析

不同變化強度下各算法離線誤差及其標準差見表2所列。

表2 不同變化強度下離線誤差及其標準差

從表2可以得出,隨著變化強度的增加,算法的離線誤差相應地增加,整體的變化趨勢與3.1節相似,即NSPSO在4個算法中最優,其次是RIPSO,再次是CPSO,最后是SPSO。進一步的分析可以看出,各算法雖然隨著變化強度的增加離線誤差也相應增加,但NSPSO在4個算法中離線誤差增加最為緩慢,變化強度從0.5變化到6,NSPSO的離線誤差從11.570增加到15.078,變化率約為30.3%。RIPSO、CPSO、SPSO算法的離線誤差變化率依次為49.7%、60.5%、67.5%。NSPSO在不同變化強度下都有較強的追蹤極值的能力,分析其原因是由于算法中把整個種群的粒子分為幾類角色,不同角色采用不同的更新策略,使得種群中一部分個體(Leader個體和Follower個體)圍繞當前最優解附近搜索的同時,還有一部分個體(Scouter個體)采用常規的更新策略在其他區域搜索。Scouter個體的搜索區域限制在其同類角色的范圍內,一旦最優解移動到這些區域,則很快就被發現并被更新為Leader角色,同時個體圍繞新的區域繼續探尋最優解。因此在NSPSO中,即使最優解的位置經過多個演化代而偏離初始位置較大,NSPSO也能迅速地跟蹤到其變化。當變化強度達到6時,其他算法已經很難跟蹤到最優解,NSPSO由于粒子角色的動態更新,還能繼續獲得較低的離線誤差。RIPSO由于每一代都引入一定新的個體,還能使算法獲得較強的探索能力,其動態搜索性能僅次于NSPSO。SPSO則隨著變化強度的增加,由于大多數粒子隨著演化的進行而逐漸收斂到最優解附近,因而失去探索能力。

4 結 論

為了促使PSO在動態環境下有較好的性能,本文提出了基于NSPSO算法,通過對標準移動峰函數的實驗,可以得出通過在PSO種群中引入多種角色,且不同角色執行不同的更新策略,使得算法在動態的環境下有較強的跟蹤極值的能力。由于在演化過程中,不同粒子的更新策略不同,且粒子的角色也會根據其適應值的不同而不斷變化,在不顯著增加算法復雜性的前提下,使得算法能夠較好地適應環境的變化。數值實驗表明,即使在較強的變化強度下,其追蹤極值的能力也能維持在較高的水平。通過多角色演化策略的引入,算法在不同的變化強度下均能維持探索能力和開采能力之間的平衡。

綜上所述,本文提出的NSPSO算法在求解動態優化問題時具有良好的性能,且在變化強度較大的情況下也能維持較高的動態性能。下一步將研究算法在更復雜情形下的動態性能,以及不同角色比例對算法動態性能的影響。

[1] KENNEDY J,EBERHART R.Particle swarm optimization[C]//ICNN’95:Proceedings of the International Conference on Neural Networks.Piscataway:IEEE,1995:1942-1948.

[2] 楊興明,許東昌,朱建,等.基于粒子群優化算法的兩輪小車能量優化策略[J].合肥工業大學學報(自然科學版),2014,37(3):292-295,375.

[3] Peng X,Gao X,Yang S.Environment identification-based memory scheme for estimation of distribution algorithms in dynamic environments[J].Soft Computing,2010,15(2):311-326.

[4] Wu Y,Liu X X.Genetic algorithms with immigrants scheme for dynamic optimization problems[J].Applied Mechanics and Materials,2013,333/334/335:1379-1383.

[5] CHENG H.Dynamic genetic algorithms with hyper-mutation schemes for dynamic shortest path routing problem in mobile ad hoc networks[J].International Journal of Adaptive,Resilient and Autonomic Systems,2012,3(1):87-98.

[6] NABIZADEH S,REZVANIAN A,MEYBODI M R.A multi-swarm cellular PSO based on clonal selection algorithm in dynamic environments[C]//2012 International Conference on Informatics,Electronics & Vision (ICIEV).[S.l.]:IEEE,2012:482-486.

[7] 王洪峰,汪定偉.一種動態環境下帶有記憶的三島粒子群算法[J].系統工程學報,2008,23(2):252-256.

[8] SHARIFI A,KAZEMI KORDESTANI J,MAHDAVIANI M,et al.A novel hybrid adaptive collaborative approach based on particle swarm optimization and local search for dynamic optimization problems[J].Applied Soft Computing,2015,32:432-448.

[9] SHEN D,LI Y,SUN Y.Particle swarm optimization with neighborhood search for multimodal optimization problems[J].ICIC Express Letters,2012,6(8):2133-2140.

[10] HE S,WU Q H,SAUNDERS J R.Group search optimizer:an optimization algorithm inspired by animal searching behavior[J].IEEE Transactions on Evolutionary Computation,2009,13(5):973-990.

[11] BANHARNSAKUN A,ACHALAKUL T,SIRINAOVAKUL B.The best-so-far selection in Artificial Bee Colony algorithm[J].Applied Soft Computing,2011,11(2):2888-2901.

[12] BLACKWELL T.Dynamic search with charged swarms[C]//Proceedings of the Genetic and Evolutionary Computation Conference.San Francisco:Morgan Kaufmann Publishers Inc,2002:19-26.

[13] BRANKE J.The moving peaks benchmark website[EB/OL].[2015-09-02].http://www.aifb.uni-karlsruhe.de/～jbr/movpeaks.

[14] BLACKWELL T,BRANKE J.Multiswarms,exclusion,and anti-convergence in dynamic environments[J].IEEE Transactions on Evolutionary Computation,2006,10(4):459-472.

(責任編輯 馬國鋒)

Particle swarm optimization based on neighborhood search in dynamic environment

SHEN Dingcai1,2, HU Shengzhou1

(1.College of Mathematics and Computer Science, Gannan Normal University, Ganzhou 341000, China; 2.School of Computer and Information Science, Hubei Engineering University, Xiaogan 432000, China)

Canonical particle swarm optimization(PSO) loses its ability of tracking optimum in dynamic environment due to its convergence. In order to increase the diversity of the population to ensure the ability of tracking the changing optimum in dynamic environment, a neighborhood search particle swarm optimization(NSPSO) was proposed. The individuals in the population were sorted in descending order according to their fitness values at each step of the evolution, each individual was assigned one of the Leader, Follower, Scouter roles according to a preset proportion, and the individuals with different roles adopted different update strategies during the evolution, thus making the algorithm maintain a certain exploitation ability, at the same time keep a stronger exploration ability. The performance of the NSPSO algorithm was validated by a commonly used moving peak benchmark(MPB). Numerical results show that the NSPSO algorithm can effectively reduce the offline error, and the impact of environmental change intensity on offline error is less than that of other compared algorithms, thus verifying that the NSPSO algorithm can effectively track the changing optimum in dynamic environment.

particle swarm optimization(PSO); dynamic optimization problem; neighborhood search; multi-role; evolutionary computation

2015-09-22；

2016-01-11

湖北省教育廳科學技術研究資助項目(D20142703)

申鼎才(1975-),男,江西南康人,博士，贛南師范大學講師.

10.3969/j.issn.1003-5060.2017.05.011

TP18

A

1003-5060(2017)05-0628-05