改進粒子群算法的目標函數變化分類動態優化

蘇玉　孔國利

摘 要： 由于優化問題的目標函數和約束條件都隨著時間而改變導致其最優值也發生改變，提出一種基于改進粒子群算法的目標函數變化分類動態優化算法。首先對動態優化問題進行定義，明確問題的研究對象，提出對目標函數隨時間變化程度分類的思想，通過對變化的函數進行監測的方法將其分為劇烈變化、中等程度變化和弱變化三種類型，并針對不同的強度變化對粒子群算法采用不同的改進策略，最后將不同的策略融入計算。通過采用移動多峰問題進行測試，結果表明，提出的改進粒子群優化算法能監測目標函數變化，并能隨時跟蹤到最優解，平均離線誤差相對于標準粒子群算法更小，性能更穩定。

關鍵詞： 粒子群算法； 動態優化； 目標函數時變分類； 移動峰問題

中圖分類號： TN911.1?34； TP301.6 文獻標識碼： A 文章編號： 1004?373X（2017）07?0175?04

Dynamic optimization of objective function changing classification based on improved particle swarm optimization

SU Yu， KONG Guoli

（College of Information Engineering， Zhongzhou University， Zhengzhou 450001， China）

Abstract： The objective function and constraint condition for the optimization problem are changed with time， and may change its optimal value. A dynamic optimization of the objective function changing classification based on improved particle swarm optimization is proposed. The dynamic optimization problem is defined to determine the study object of the problem. The classification thought that the objective function is changed with the time varying degree is put forward. The varying function is divided into the types of drastic change， medium grade change and weak change with the monitoring method. Different strategies are adopted for the particle swarm optimization according to the different intensity changes， and integrated for computation. The algorithm was tested with the moving multi?peak problem. The test results show that the improved particle swarm optimization can monitor the changes of the objective function， track the optimal solution momentarily， its average offline error is smaller than that of the standard particle swarm optimization algorithm， and the performance is more stable.

Keywords： particle swarm optimization； dynamic optimization； time varying classification of objective function； moving peak problem

0 引 言

由于在很多實際生產過程中遇到的優化問題都在不停變化，同時其目標函數和約束條件也會隨著時間在不停的發生著變化，最終導致其問題的最優解改變[1?3]。如動態旅行商問題（DTSP）[4]中旅行城市的增加或減少；車輛路徑規劃問題（DVRP）[5]中的交通狀況；動態背包問題（DKP）[6]中物品價值或重量會改變，顧客需求等大量不確定性，這類動態特性使得目前的優化算法面臨著巨大挑戰。對于這類動態優化問題，不僅需要求解最優解，并且算法能夠時刻跟隨最優解的變化[7]。目前已經提出了很多研究方法，包括基于遺傳算法的超級變異[8]、基于粒子群算法[9]、基于種群增量學習[10]、隨機重新多樣性[11]等。此外，預測方法、多種群方法也被應用到該問題中。

由于動態優化問題千變萬化，目標函數變化程度和變化類型也多種多樣，因此應該根據具體的問題采取具體的措施加以解決。

本文首先對所研究問題進行表述，對目標函數的變化進行合理分類，針對不同的變化采取不同措施，使算法能有效跟蹤最優解的變化。粒子群算法是一種優秀的智能啟發式算法，已被廣泛使用，為此提出一種基于改進粒子群算法的目標函數變化分類動態優化算法，在算法迭代過程中根據不同的環境變化采取不同的種群多樣性方法。最后用移動峰問題測試該算法的有效性。

1 問題描述

一般來說，任何動態優化問題都可以用以下定義式來表征。

定義1： 記[V0×VF]和[W]分別為[n0]維、[nF]維和[M]維連續或離散矢量空間；[g]和[h]為定義不等式和等式約束的兩個函數；[f]為從[V0×VF]映射到[W]上的一個函數，那么[M]個目標的參數化和多標準最小化問題定義為[12]：

[minfvO∈VO=f1（vO，vF）， f2（vO，vF），…， fM（vO，vF）s.t. g（vO，vF）≤0， h（vO，vF）=0] （1）

上述定義問題中變量[v0]對于優化是有用的，但[vF]為強加參數，其本身與優化變量沒有任何關系。而目標函數和約束條件均受其他參數的約束。如果只考慮時間參數，上述問題可以轉化為如下定義。

定義2： 記時間變量為[t；][V]和[W]分別為[n]維和[M]維連續或離散的矢量空間；[g]和[h]為定義不等式和等式約束的兩個函數；[f]為從[V×t]映射到[W]上的函數，那么[M]個目標的參數化和多標準最小化問題定義為 [13]：

[minfv∈V=f1（v，t），f2（v，t），…， fM（v，t）s.t. g（v，t）≤0， h（v，t）=0] （2）

若上述目標函數中僅含有單個目標，則為動態單目標優化，單目標優化只有惟一最優解。此外，優化過程中有可能添加新的目標或者刪減目標，這也將導致問題的動態變化。

通常主要利用環境變化的頻率、環境變化的強度、環境變化的可預測性和環境變化的周期性四個特征對動態環境進行描述，這四個特征也是人們構造和研究動態優化問題的依據。此外動態優化問題還包含變化動力學，該形式還包括：線性變化、非線性變化、連續變化/非連續變化、周期性變化和隨機性變化等。

2 動態優化粒子群算法

2.1 環境變化的檢測及分類

增加種群多樣性方法的前提是能準確識別出環境的變化，因此一個可靠的環境變化檢測算子格外重要。這里采取從種群中選擇一定數量的子種群進行適應度值評價的方法。這些子種群不隨算法迭代更新，若目標函數或約束函數變化了，那么就說明問題也改變了，從而得到檢測環境變化的計算公式如下：

[ε（t）=1nj=1nfj（x，t）-fj（x，t-1）] （3）

式中：[n]為重新評價個體的數目，一般為種群大小的10%。當[ε（t）>ε2]時，說明多目標優化問題已經改變，這時就需要在新環境下開始搜索。通常會依據目標函數變化的大小，提前給定一個固定的常數，這個常數的范圍通常為[10-3≤ε2≤10-2。]

實際上對優化問題影響較大的是環境變化的強度，當檢測到環境的變化較大時，那么就說明問題的本質已改變。而如果只是高頻小幅的環境變化，問題的最優解也只是在原始解附近波動。因此根據環境變化的強度進行分類，將環境變化分為三類：劇烈變化、中等程度變化和弱變化。根據環境變化檢測算子的計算式（3），對計算結果[ε（t）]進行如下分類：

[ε（t）>ε1ε2<ε（t）≤ε1ε（t）≤ε2] （4）

式中：[ε1]為劇烈強度變化的分界點；[ε2]為中等程度分界點。

當環境變化檢測結果超過[ε1]時，即為劇烈的環境變化，此時環境變化強度較大，最優值及其位置將會偏離原始值，可以按照一定比例隨機重新初始化種群來增大種群多樣性；當檢測結果介于[ε2]和[ε1]之間時，認為是中等強度的環境變化，此時的最優解及其位置應該在原始值附近，并不會偏離太遠，若仍然按照重新初始化的方法來增加種群多樣性，則會浪費計算時間，放緩了收斂速度。可以充分利用以前的計算結果對當前最優解及次優解進行高斯分布，生成部分個體，其余個體再按照隨機初始化的方法生成子種群。當檢測結果小于[ε2]時，認為是低強度的環境變化，此時環境變化范圍較小，對于一般研究問題可以忽略，但對于較為精確的研究問題還應該考慮。本文將此低強度環境變化忽略。

2.2 動態優化算法計算過程

經典標準粒子群算法將每個粒子均當作[D]維解空間中的一個點，而且它們均有一個速度[v，]它會根據自身和群體的飛行經驗確定自身的飛行速度，并調整飛行軌跡向最優點靠近。同時，不同粒子借助自身的個體適應度值對該粒子評估[14]。速度和位置更新公式如下：

[vid（t+1）=ω*vid（t）+c1r1（pid-xid（t））+c2r2（pgd-xid（t））] （5）

[xid（t+1）=xid（t）+vid（t+1）] （6）

式中：[vid（t），][xid（t）]分別表示[t]時刻粒子[i]的飛行速度和位置；[pid]表示粒子[i]的個體歷史最佳位置；[pgd]表示群體中最佳位置；[ω]表示慣性權重；[c1]和[c2]表示加速因子；[r1]和[r2]表示在[0，1]范圍內的隨機數。

基于標準粒子群算法設計的多種增大種群多樣性機制的動態優化算法計算步驟如下：

Step1：初始化種群和最優解的存儲空間。然后隨機生成尋優粒子的位置、速度和一定比例的監測粒子的位置；

Step2：評估種群中所有的個體，并得到所有尋優粒子的適應度值，存儲當前的全局最優解，計算監測粒子的適應度值；

Step3：得到前后時刻監測粒子適應度值的變化度[ε（t），]若[ε（t）>ε1，]轉Step4；若[ε2<ε（t）≤ε1，]轉Step5；若[ε（t）≤ε2，]則轉Step6；

Step4： 隨機重新初始化種群和最優解存儲空間，生成尋優粒子的位置和速度，然后轉至Step2；

Step5：對當前最優解的粒子位置按照高斯分布生成部分種群，其余按照重新初始化隨機生成尋優粒子位置和速度，并轉至Step2；

Step6：更新每個尋優粒子的速度和位置；

Step7：判斷是否達到最大迭代次數，若否轉至Step2，若是則計算結束。

3 實驗驗證及分析

為了驗證該算法的可行性，采用移動峰問題（Moving Peaks Benchmark Problem）進行測試[15]，并且用離線誤差作為性能評價標準。離線誤差可以表示為：

[μ=1ki=1k（hi-fi）] （7）

式中：[hi]表示第[i]次環境下最高峰的高度值；[fi]表示第[i]次環境下算法能求得的適應度最優值；[k]表示環境變化總次數；[μ]即離線誤差值，反映的是算法跟蹤環境變化的能力，理論上[μ=0]為最佳。

移動峰問題已經被廣泛采用作為典型的動態優化測試問題[16]，通過改變多個峰的高度、寬度和位置來模擬環境的變化。評價函數由多個峰構成，形式如下：

[F（x，t）=maxi=1，2，…，PHi（t）1+Wi（t）*j=1D（xj（t）-Xij（t））2] （8）

式中：[Wi（t），][Hi（t）]表示峰i在時刻t的寬度和高度；[Xij（t）]表示峰i在時刻t時第j維的位置；P表示峰的個數；[D]表示峰的位置維度。

由于在搜索過程中，峰的高度、寬度和位置均在不停的改變，那么峰的位置為：

[vi（t）=sr+vi（t-1）（1-λ）r+λvi（t-1）] （9）

式中：[vi（t）]即為峰i在t時刻的移動方向；[r]為隨機向量；[λ]為相關系數，表示t時刻的移動方向與t-1時刻移動方向的相關程度；s為移動長度。

[Hi（t）=Hi（t-1）+height_severity*σ] （10）

[Wi（t）=wi（t-1）+width_severity*σ] （11）

[Xi（t）=Xi（t-1）+vi（t）] （12）

式中：height_severity表示峰的高度變化程度；[σ]表示在[0，1]范圍內滿足高斯分布的隨機數；width_severity表示峰的寬度變化程度。

采用的移動峰問題的參數如表1所示。

將改進粒子群算法的種群規模設定為50，每迭代100次改變一次環境，一共改變100次，運行該算法得到如圖1所示的結果。

從圖1可以看出，小方塊表示每個環境中所有峰的最高高度值，也就是真實的最優值。星號則表示得到的每個環境中的最優值。經過計算，本次運行的離線誤差為0，也就是說算法在環境發生變化后能夠真實跟蹤到每次環境中的最優值。

由于粒子群算法是一種隨機性尋優算法，為了消除偶然性因素的影響，將該改進型算法運行10次。用標準粒子群算法對同樣的移動峰問題參數尋優，運行10次，得到離線誤差和需要的計算時間數據記錄如表2所示。

從表2中的數據可以發現：標準型粒子群算法雖然也能跟蹤到動態環境中的最優解，但不穩定，甚至誤差很大，這是由于此時的標準粒子群算法已經陷入了局部最優解；而改進粒子群算法的尋優結果更穩定，精度高，標準差更小，且還可在較短的時間內得出變化環境中的最優解。

4 結 語

針對動態優化問題提出將環境變化進行分類，分為高強度、中等強度和低強度的環境變化。針對高強度的環境變化，采取重新初始化部分種群的策略；針對中等強度的環境變化，采取將當前最優解進行高斯分布取隨機數，將種群分布在當前最優解周圍；針對低強度環境變化，不作反應。應用移動多峰的動態問題測試本算法，結果表明，該改進型粒子群算法相比標準粒子群算法平均離線誤差更小，并且性能更穩定，能夠跟蹤到動態環境的最優值。

參考文獻

[1] 許君，魯海燕，石桂娟.限制速度粒子群優化和自適應速度粒子群優化在無約束優化問題中的應用[J].計算機應用，2015，35（3）：668?674.

[2] NGUYEN T T， YANG S X， BRANKE J. Evolutionary dynamic optimization： a survey of the state of the art [J]. Swarm and evolutionary computation， 2012， 6： 1?24.

[3] 葛亮，吳承乾，吳丹，等.一種基于碼率控制的無線自組織網絡傳輸功率優化方案[J].現代電子技術，2015，38（9）：9?11.

[4] 李妍峰，李軍，趙達.動態搜索算法求解時間依賴型旅行商問題研究[J].控制與決策，2009，24（2）：274?278.

[5] 趙冬玲，楊艷，潘正運.一種車輛路徑規劃的新型蟻群算法研究[J].電子器件，2014，37（3）：519?523.

[6] 賀毅朝，宋建民，張敬敏，等.利用遺傳算法求解靜態與動態背包問題的研究[J].計算機應用研究，2015，32（4）：1011?1015.

[7] 畢洪偉.一類帶移民的連續狀態分枝過程的非中性突變模型[J].北京師范大學學報（自然科學版），2014（4）：346?349.

[8] 耿光飛，楊仁剛.基于定向變異遺傳算法的地區電網無功功率優化[J].電網技術，2004，28（10）：42?44.

[9] 文娟，譚陽紅，雷可君，等.基于量子粒子群算法多目標優化的配電網動態重構[J].電力系統保護與控制，2015，43（16）：73?78.

[10] YANG S X， RICHTER H. Hyper?learning for population incremental learning in dynamic environments [C]// Proceeding of 2009 IEEE Congress on Evolutionary Computation. Los Alamitos： IEEE， 2009： 682?689.

[11] 饒興華，王文格，胡旭.多樣性反饋與控制的粒子群優化算法[J].計算機應用，2014，34（2）：506?509.

[12] 鄭金華，彭舟，鄒娟，等.基于引導個體的預測策略求解動態多目標優化問題[J].電子學報，2015，43（9）：1816?1825.

[13] 孫東磊，韓學山，李文博.風儲共存于配網的動態優化潮流分析[J].電力自動化設備，2015，35（8）：110?117.

[14] 高道镠，紀志成，吳定會.基于雙策略改進混沌粒子群的車間調度優化[J].計算機工程與設計，2015，36（7）：1944?1947.

[15] 陳昊，黎明，陳曦.動態環境下基于預測機制的多種群進化算法[J].小型微型計算機系統，2012，33（4）：795?799.

[16] 周長喜，毛力，吳濱，等.基于當前最優解的人工蜂群算法[J].計算機工程，2015，41（6）：147?151.