蘇玉　孔國利

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

關(guān)鍵詞： 粒子群算法； 動態(tài)優(yōu)化； 目標函數(shù)時變分類； 移動峰問題

中圖分類號： 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 引 言

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

由于動態(tài)優(yōu)化問題千變?nèi)f化，目標函數(shù)變化程度和變化類型也多種多樣，因此應(yīng)該根據(jù)具體的問題采取具體的措施加以解決。

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

1 問題描述

一般來說，任何動態(tài)優(yōu)化問題都可以用以下定義式來表征。

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

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

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

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

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

若上述目標函數(shù)中僅含有單個目標，則為動態(tài)單目標優(yōu)化，單目標優(yōu)化只有惟一最優(yōu)解。此外，優(yōu)化過程中有可能添加新的目標或者刪減目標，這也將導(dǎo)致問題的動態(tài)變化。

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

2 動態(tài)優(yōu)化粒子群算法

2.1 環(huán)境變化的檢測及分類

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

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

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

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

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

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

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

2.2 動態(tài)優(yōu)化算法計算過程

經(jīng)典標準粒子群算法將每個粒子均當作[D]維解空間中的一個點，而且它們均有一個速度[v，]它會根據(jù)自身和群體的飛行經(jīng)驗確定自身的飛行速度，并調(diào)整飛行軌跡向最優(yōu)點靠近。同時，不同粒子借助自身的個體適應(yīng)度值對該粒子評估[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]表示群體中最佳位置；[ω]表示慣性權(quán)重；[c1]和[c2]表示加速因子；[r1]和[r2]表示在[0，1]范圍內(nèi)的隨機數(shù)。

基于標準粒子群算法設(shè)計的多種增大種群多樣性機制的動態(tài)優(yōu)化算法計算步驟如下：

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

Step2：評估種群中所有的個體，并得到所有尋優(yōu)粒子的適應(yīng)度值，存儲當前的全局最優(yōu)解，計算監(jiān)測粒子的適應(yīng)度值；

Step3：得到前后時刻監(jiān)測粒子適應(yīng)度值的變化度[ε（t），]若[ε（t）>ε1，]轉(zhuǎn)Step4；若[ε2<ε（t）≤ε1，]轉(zhuǎn)Step5；若[ε（t）≤ε2，]則轉(zhuǎn)Step6；

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

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

Step6：更新每個尋優(yōu)粒子的速度和位置；

Step7：判斷是否達到最大迭代次數(shù)，若否轉(zhuǎn)至Step2，若是則計算結(jié)束。

3 實驗驗證及分析

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

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

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

移動峰問題已經(jīng)被廣泛采用作為典型的動態(tài)優(yōu)化測試問題[16]，通過改變多個峰的高度、寬度和位置來模擬環(huán)境的變化。評價函數(shù)由多個峰構(gòu)成，形式如下：

[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表示峰的個數(shù)；[D]表示峰的位置維度。

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

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

式中：[vi（t）]即為峰i在t時刻的移動方向；[r]為隨機向量；[λ]為相關(guān)系數(shù)，表示t時刻的移動方向與t-1時刻移動方向的相關(guān)程度；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]范圍內(nèi)滿足高斯分布的隨機數(shù)；width_severity表示峰的寬度變化程度。

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

將改進粒子群算法的種群規(guī)模設(shè)定為50，每迭代100次改變一次環(huán)境，一共改變100次，運行該算法得到如圖1所示的結(jié)果。

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

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

從表2中的數(shù)據(jù)可以發(fā)現(xiàn)：標準型粒子群算法雖然也能跟蹤到動態(tài)環(huán)境中的最優(yōu)解，但不穩(wěn)定，甚至誤差很大，這是由于此時的標準粒子群算法已經(jīng)陷入了局部最優(yōu)解；而改進粒子群算法的尋優(yōu)結(jié)果更穩(wěn)定，精度高，標準差更小，且還可在較短的時間內(nèi)得出變化環(huán)境中的最優(yōu)解。

4 結(jié) 語

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

參考文獻

[1] 許君，魯海燕，石桂娟.限制速度粒子群優(yōu)化和自適應(yīng)速度粒子群優(yōu)化在無約束優(yōu)化問題中的應(yīng)用[J].計算機應(yīng)用，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] 葛亮，吳承乾，吳丹，等.一種基于碼率控制的無線自組織網(wǎng)絡(luò)傳輸功率優(yōu)化方案[J].現(xiàn)代電子技術(shù)，2015，38（9）：9?11.

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

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

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

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

[8] 耿光飛，楊仁剛.基于定向變異遺傳算法的地區(qū)電網(wǎng)無功功率優(yōu)化[J].電網(wǎng)技術(shù)，2004，28（10）：42?44.

[9] 文娟，譚陽紅，雷可君，等.基于量子粒子群算法多目標優(yōu)化的配電網(wǎng)動態(tài)重構(gòu)[J].電力系統(tǒng)保護與控制，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] 饒興華，王文格，胡旭.多樣性反饋與控制的粒子群優(yōu)化算法[J].計算機應(yīng)用，2014，34（2）：506?509.

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

[13] 孫東磊，韓學山，李文博.風儲共存于配網(wǎng)的動態(tài)優(yōu)化潮流分析[J].電力自動化設(shè)備，2015，35（8）：110?117.

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

[15] 陳昊，黎明，陳曦.動態(tài)環(huán)境下基于預(yù)測機制的多種群進化算法[J].小型微型計算機系統(tǒng)，2012，33（4）：795?799.

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