改進(jìn)粒子群算法的目標(biāo)函數(shù)變化分類動(dòng)態(tài)優(yōu)化

蘇玉　孔國利

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

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

中圖分類號(hào)： TN911.1?34； TP301.6 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：[ε1]為劇烈強(qiáng)度變化的分界點(diǎn)；[ε2]為中等程度分界點(diǎn)。

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

2.2 動(dòng)態(tài)優(yōu)化算法計(jì)算過程

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

基于標(biāo)準(zhǔn)粒子群算法設(shè)計(jì)的多種增大種群多樣性機(jī)制的動(dòng)態(tài)優(yōu)化算法計(jì)算步驟如下：

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證及分析

為了驗(yàn)證該算法的可行性，采用移動(dòng)峰問題（Moving Peaks Benchmark Problem）進(jìn)行測試[15]，并且用離線誤差作為性能評(píng)價(jià)標(biāo)準(zhǔn)。離線誤差可以表示為：

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

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

移動(dòng)峰問題已經(jīng)被廣泛采用作為典型的動(dòng)態(tài)優(yōu)化測試問題[16]，通過改變多個(gè)峰的高度、寬度和位置來模擬環(huán)境的變化。評(píng)價(jià)函數(shù)由多個(gè)峰構(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在時(shí)刻t的寬度和高度；[Xij（t）]表示峰i在時(shí)刻t時(shí)第j維的位置；P表示峰的個(gè)數(shù)；[D]表示峰的位置維度。

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

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

式中：[vi（t）]即為峰i在t時(shí)刻的移動(dòng)方向；[r]為隨機(jī)向量；[λ]為相關(guān)系數(shù)，表示t時(shí)刻的移動(dòng)方向與t-1時(shí)刻移動(dòng)方向的相關(guān)程度；s為移動(dòng)長度。

[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)滿足高斯分布的隨機(jī)數(shù)；width_severity表示峰的寬度變化程度。

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

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

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)

[1] 許君，魯海燕，石桂娟.限制速度粒子群優(yōu)化和自適應(yīng)速度粒子群優(yōu)化在無約束優(yōu)化問題中的應(yīng)用[J].計(jì)算機(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] 李妍峰，李軍，趙達(dá).動(dòng)態(tài)搜索算法求解時(shí)間依賴型旅行商問題研究[J].控制與決策，2009，24（2）：274?278.

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

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

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

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

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

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

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

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

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

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