基于數(shù)據(jù)流的K-S變化檢測的動態(tài)多目標規(guī)劃算法

張濤，周晨，杜鋒，陳芳，劉瑞林

1.長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023 2.荊楚理工學(xué)院數(shù)理學(xué)院，湖北 荊門 448000

動態(tài)多目標規(guī)劃問題(dynamic multi-objective optimization problem，DMOP)是一個涉及兩個或多個目標函數(shù)、約束條件和問題參數(shù)隨時間變化的問題[1]。動態(tài)多目標規(guī)劃有著廣泛的應(yīng)用，如調(diào)度問題[2-6]、控制問題[7-10]、資源管理問題[11-13]、水熱發(fā)電問題[14]等。由于動態(tài)多目標規(guī)劃問題具有廣泛的應(yīng)用性與復(fù)雜性，其求解算法設(shè)計逐漸成為優(yōu)化領(lǐng)域的熱點與難點。馬永杰等[15]利用種群的歷史信息提出了一種基于卡爾曼濾波預(yù)測并修正種群中心點位置的動態(tài)多目標優(yōu)化算法；呼子宇等[16]為了在檢測到環(huán)境變化時能夠及時有效地做出響應(yīng)，提出了一種基于決策變量關(guān)系的動態(tài)多目標優(yōu)化算法(DVR)；張杰等[17]為了能有效應(yīng)對劇烈的環(huán)境變化提出了一種基于混合預(yù)測策略與改進社會學(xué)習(xí)優(yōu)化算法的動態(tài)多目標優(yōu)化方法；唐曉樂等[18]為適應(yīng)較為復(fù)雜的動態(tài)環(huán)境，結(jié)合動態(tài)優(yōu)化問題的可預(yù)測特性，提出一種基于組合預(yù)測策略的多目標優(yōu)化算法。

由于動態(tài)多目標規(guī)劃問題具有時變性，隨時間動態(tài)變化，當(dāng)環(huán)境變化較快時，該問題求解會變得更加的困難與復(fù)雜。怎樣快速檢測環(huán)境是否發(fā)生變化，以及怎樣在時間窗的約束下準確追蹤到當(dāng)前時刻的Pareto最優(yōu)前沿是算法設(shè)計的重點與難點。當(dāng)前大多數(shù)變化檢測的方法基于統(tǒng)計法，如SAHMOUD和TOPCUOGLU提出的一些檢測環(huán)境變化的機制(sensor-based change detection，SBCD)[19]，實際上是選取一部分的個體進行重評估；還有楊圣祥等[20]提出的穩(wěn)定狀態(tài)的檢測方法，該種環(huán)境檢測方法對環(huán)境變化很敏感，不易于設(shè)置其閾值，具有不精確性。探索出新的環(huán)境變化檢測方法，感知環(huán)境變化的類型和強度，提高對環(huán)境變化檢測精度，已成為該領(lǐng)域亟需解決的問題。為此，筆者就環(huán)境檢測與環(huán)境應(yīng)答機制做了一定的研究，提出了一種基于數(shù)據(jù)流的K-S變化檢測的動態(tài)多目標規(guī)劃算法(DSK-SDMOP)，該算法使用非參數(shù)檢測方法——Kolmogorov-Smirnov(K-S)檢驗來檢測基于數(shù)據(jù)流的Pareto最優(yōu)前沿是否發(fā)生變化，再根據(jù)變化的劇烈程度實行相應(yīng)的環(huán)境變化應(yīng)答機制，以提高對環(huán)境的適應(yīng)程度。

1 模型與概念

動態(tài)多目標規(guī)劃問題一般可以定義為如下形式[1]：

(1)

式中：x={x1，x2，…，xn}為n維決策變量；t為時間變量；f(x，t)為目標函數(shù)；m為目標函數(shù)的個數(shù)；g(x，t)，h(x，t)分別為相應(yīng)的不等式約束和等式約束。

在最小化動態(tài)多目標規(guī)劃問題中，對任意2個決策變量xa和xb，如果滿足下列2個條件：

1)對于?i∈1，2，…，m，都有fi(xa，t)≤fi(xb，t)成立；

2)?j∈1，2，…，m，使得fj(xa，t)

則稱xa支配xb，表示為xaxb。t時刻，如果不存在可行域內(nèi)的x，使得xx*，則x*為t時刻的Pareto最優(yōu)解，其組成的集合稱為Pareto最優(yōu)解集，記為PSt。而t時刻，PSt在目標空間的映射稱為Pareto最優(yōu)前沿，記為PFt。

根據(jù)PS和PF隨時間變化的情況，DMOPs有以下4種類型[21]：

1)PS隨時間變化而PF不隨時間變化；

2)PS、PF都隨時間變化；

3)PS不隨時間變化而PF隨時間變化；

4)PS、PF都不隨時間變化。

2 環(huán)境變化檢測和環(huán)境變化應(yīng)答機制

動態(tài)多目標規(guī)劃問題的算法設(shè)計主要考慮環(huán)境變化檢測和環(huán)境變化應(yīng)答機制兩個方面。首先要檢測出環(huán)境是否發(fā)生改變，然后針對改變做出相應(yīng)的應(yīng)答，使算法快速地適應(yīng)改變的環(huán)境。

2.1 環(huán)境變化檢測

2.1.1 數(shù)據(jù)流上移動窗口的數(shù)據(jù)提取

實際上，在動態(tài)多目標規(guī)劃的求解中，每一時刻都能求得一個PF，可以看成一個數(shù)據(jù)流，而且t時刻與t+1時刻求得的|PF|大小可能不一樣，導(dǎo)致取得的窗口所包含的數(shù)據(jù)點不一樣。因此，為了更好檢測環(huán)境是否發(fā)生了變化，筆者采用基于數(shù)據(jù)流的雙移動窗口的檢測方法，也就是說“參考窗口”與當(dāng)前窗口都是移動的，并且每個窗口的數(shù)據(jù)的數(shù)量是不固定的。將上一個時刻所求得的目標函數(shù)值的所有數(shù)據(jù)作為“參考窗口”與當(dāng)前時刻對應(yīng)目標函數(shù)的函數(shù)值作為當(dāng)前窗口，來進行環(huán)境檢測。

2.1.2 Kolmogorov-Smirnov(K-S)檢驗

K-S檢驗用于比較基于分布函數(shù)的2個樣本[18]，檢驗?zāi)硞€經(jīng)驗分布是否與某種理論分布相符或者比較兩個經(jīng)驗分布之間是否有顯著性的差異。筆者運用的是K-S雙樣本檢驗，通過檢驗2個樣本的累計頻數(shù)分布是否相當(dāng)接近來判斷是否接受原假設(shè)H0(H0表示2個樣本分布一致)；反之，則認為不服從同一分布，拒絕原假設(shè)。其優(yōu)點在于不用對數(shù)據(jù)做任何假設(shè)，也不要求樣本容量一致，將“參考窗口”和當(dāng)前窗口的數(shù)據(jù)當(dāng)成2個獨立的樣本運用K-S檢驗來檢測2個樣本是否服從同一分布以此判斷環(huán)境是否發(fā)生變化。

環(huán)境檢測方法如下所示(以目標數(shù)為2的測試問題為例)：

(2)

(3)

2.2 環(huán)境應(yīng)答機制

當(dāng)檢測到環(huán)境發(fā)生變化時，立即啟動環(huán)境應(yīng)答機制來適應(yīng)環(huán)境的變化，調(diào)整搜索的方向，開始搜尋新的環(huán)境下的PS。

2.2.1 評估環(huán)境變化強度

一個進化算法通常很難準確的求得Pareto最優(yōu)前沿，所以不能直接得到變化的程度。可以通過當(dāng)前種群和歷史種群之間目標值的偏差評估環(huán)境的變化。測量偏差Fmean和環(huán)境變化強度Ieva(t)的公式如下[24]：

(4)

(5)

2.2.2 系統(tǒng)預(yù)設(shè)的環(huán)境變化強度

環(huán)境變化的幅度τt會對算法對環(huán)境的適應(yīng)程度產(chǎn)生比較大的影響，所以將系統(tǒng)預(yù)設(shè)的環(huán)境變化強度Isys設(shè)置為：

(6)

2.2.3 種群初始化比例自適應(yīng)調(diào)整

如果環(huán)境發(fā)生了變化，則根據(jù)環(huán)境變化強度自適應(yīng)調(diào)整種群初始化比例：

(7)

如果Irate(t)>Isys，證明環(huán)境變化是劇烈的，所以要大比例初始化種群，以更快地適應(yīng)環(huán)境變化，調(diào)整其搜索方向，更快地追蹤到新的Pareto最優(yōu)前沿；如果Ieva(t)≤Isys，證明環(huán)境是溫和可控的，只需要小幅度調(diào)整搜索方向即可。

3 DSK-SDMOP算法

DSK-SDMOP算法以求解靜態(tài)多目標規(guī)劃問題的NSGA-Ⅱ算法為基礎(chǔ)，DSK-SDMOP算法的具體步驟如下：

Step1 參數(shù)及種群的初始化：對參數(shù)進行設(shè)置，種群大小pop、最大迭代次數(shù)Iteration、環(huán)境變化幅度τt，環(huán)境變化的頻率為nt，并在決策空間中隨機生成規(guī)模為pop的初始種群p0；

Step 2 按照NSGA-Ⅱ的進化操作選擇、交叉、變異、快速非支配排序操作得到PFt；

Step 3 初始化種群，利用靜態(tài)多目標規(guī)劃算法NSGA-Ⅱ的進化操作與快速非支配排序得到PFt+1；

Step 4 當(dāng)Iteration≥2時進行環(huán)境變化檢測：利用K-S檢驗基于數(shù)據(jù)流的PFt與PFt+1中對應(yīng)的目標函數(shù)值是否服從同一分布，若服從則認為環(huán)境沒有變化，反之則認為發(fā)生變化；

Step 5 環(huán)境應(yīng)答機制：若環(huán)境發(fā)生變化，將PFt對應(yīng)PSt按照公式(4)～(7)初始化后，將其作為下一時刻的初始種群，即將當(dāng)前時刻得到的PSt按確定的比例隨機生成后得到的種群作為下一時刻的初始種群；若環(huán)境未發(fā)生變化，將t時刻進行進化操作得到PSt直接作為下一時刻的初始種群。

Step 6 判斷是否滿足算法停止的條件(達到最大迭代次數(shù))，若滿足則停止；若不滿足，t=t+1，轉(zhuǎn)Step 3。

4 仿真實驗與結(jié)果分析

選取了FDA系列的5個動態(tài)多目標規(guī)劃標準測試函數(shù)FDA1～FDA5來進行仿真實驗，并與文獻[14]提出的DNSGA-Ⅱ-A和DNSGA-Ⅱ-B算法來進行對比研究。

4.1 測試函數(shù)

在動態(tài)多目標規(guī)劃的4種類型中[21]，這里主要研究的前兩種類型的問題。對于類型Ⅲ，當(dāng)環(huán)境發(fā)生改變時，PS也會一直保持不變，此時只需要把算法當(dāng)前時刻追蹤到的最優(yōu)PS直接作為下一時刻的初始種群，研究意義不大；而對于類型Ⅳ中PS與PF都不發(fā)生變化的情形，不能將問題的變化特性用較為簡單的數(shù)學(xué)模型來進行描述，所以不作討論與研究。在測試函數(shù)FDA1～FDA5中，F(xiàn)DA1和FDA4屬于類型Ⅰ，當(dāng)環(huán)境發(fā)生變化時，PF不變；而FDA2、FDA3、FDA5屬于類型Ⅱ，當(dāng)環(huán)境發(fā)生變化時，PS和PF均改變。

4.2 性能指標

本文主要用到準確率(the true positive rate，TPrate)、反世代距離(inverted generational distance，IGD)以及其在環(huán)境變化下的平均值mIGD、間距(scotts spacing，SS)以及其在環(huán)境變化下的平均值mSS來評價算法的性能，具體計算方法分別見文獻[25-27]。其中，TPrate用來衡量正確檢測到環(huán)境變化的百分比，IGD通過度量真實Pareto前沿與算法獲得的Pareto前沿之間的接近程度來評價算法的收斂性與多樣性，SS度量Pareto前沿分布均勻程度。

4.3 實驗結(jié)果及分析

表1 算法性能指標比較

測試函數(shù)的環(huán)境變化幅度τt=10，環(huán)境變化的頻率為nt=100，測試函數(shù)FDA1、FDA2、FDA3、FDA4、FDA5決策變量的維度分別為20、13、30、12、12。算法終止的條件為迭代1 000次，一共10個環(huán)境，對于每個測試函數(shù)算法都獨立運行10次。DSK-SDMOP算法和DNSGA-Ⅱ-A/B算法都以NSGA-Ⅱ為框架設(shè)計的，算法參數(shù)做如下設(shè)置，種群的大小pop=100，交叉概率pc=0.90，變異概率為pm=0.1。

1)實驗結(jié)果。將DSK-SDMOP、DNSGA-Ⅱ-A、DNSGA-Ⅱ-B這3種算法在FDA系列5個測試函數(shù)上獨立運行10次，求得TPrate、mSS、mIGD的均值如表1和圖1所示。10個不同的環(huán)境下3種算法在不同測試函數(shù)上SS、IGD如圖2所示。

圖1 算法性能評價指標比較Fig.1 Comparison of algorithm performance evaluation indicators

2)結(jié)果分析。由表1和圖1可知，DSK-SDMOP算法正確檢測到環(huán)境變化的百分比TPrate在除FDA4之外的四個測試函數(shù)上均為100%，而DNSGA-Ⅱ-A/B最高只能達到95%；在FDA4上本文算法檢測變化準確率方面為90%，DNSGA-Ⅱ-A/B僅為65%和70%。算法DSK-SDMOP與算法DNSGA-Ⅱ-A/B正確檢測到環(huán)境變化的百分比TPrate最大差值在40%，最小差值也有5%，說明該算法對環(huán)境變化判斷的準確性明顯高于DNSGA-Ⅱ-A/B；而mSS、mIGD分別用來評價解集內(nèi)部的解分布的均勻性、算法的收斂性與多樣性。在求得解集內(nèi)部的均勻性以及收斂性與多樣性方面，除了FDA3的mSS指標高于DNSGA-Ⅱ-B算法0.000 7，F(xiàn)DA5的mIGD指標高于DNSGA-Ⅱ-A算法0.002 7，稍顯遜色以外，DSK-SDMOP算法在指標mSS、mIGD都低于DNSGA-Ⅱ-A/B，表示著DSK-SDMOP算法的收斂性與多樣性以及Pareto前沿分布均勻程度都優(yōu)于算法DNSGA-Ⅱ-A/B。

圖2 不同環(huán)境下的SS和IGDFig.2 SS and IGD in different environments

由圖2可知，DSK-SDMOP算法的SS、IGD指標在每個環(huán)境下都保持很小的值，表明它求得的解集內(nèi)部分布均勻且更接近標準Pareto最優(yōu)前沿，表現(xiàn)出DSK-SDMOP算法良好的環(huán)境適應(yīng)性。

5 結(jié)論

1)針對動態(tài)多目標規(guī)劃問題，筆者提出了一種基于數(shù)據(jù)流的K-S變化檢測的動態(tài)多目標規(guī)劃算法DSK-SDMOP，該算法的環(huán)境變化檢測機制主要基于數(shù)據(jù)流中的滑動窗口以及K-S檢驗，能在沒有分布假設(shè)的情形中較準確的感知環(huán)境所發(fā)生的變化，并設(shè)計了一種自適應(yīng)環(huán)境應(yīng)答的機制來判斷環(huán)境變化的強度并確定多樣性引入的比例，使算法更好適應(yīng)環(huán)境，追蹤到Pareto最優(yōu)前沿。

2)動態(tài)多目標規(guī)劃算法FDA系列的標準測試函數(shù)仿真實驗結(jié)果表明，該算法在變化檢測的準確性、均勻性以及收斂性方面表現(xiàn)出良好的性能，并且該算法的結(jié)構(gòu)簡單，具有較好的遷移能力。