基于數據流的K-S變化檢測的動態多目標規劃算法

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

1.長江大學信息與數學學院，湖北 荊州 434023 2.荊楚理工學院數理學院，湖北 荊門 448000

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

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

1 模型與概念

動態多目標規劃問題一般可以定義為如下形式[1]：

(1)

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

在最小化動態多目標規劃問題中，對任意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時刻，如果不存在可行域內的x，使得xx*，則x*為t時刻的Pareto最優解，其組成的集合稱為Pareto最優解集，記為PSt。而t時刻，PSt在目標空間的映射稱為Pareto最優前沿，記為PFt。

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

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

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

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

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

2 環境變化檢測和環境變化應答機制

動態多目標規劃問題的算法設計主要考慮環境變化檢測和環境變化應答機制兩個方面。首先要檢測出環境是否發生改變，然后針對改變做出相應的應答，使算法快速地適應改變的環境。

2.1 環境變化檢測

2.1.1 數據流上移動窗口的數據提取

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

2.1.2 Kolmogorov-Smirnov(K-S)檢驗

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

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

(2)

(3)

2.2 環境應答機制

當檢測到環境發生變化時，立即啟動環境應答機制來適應環境的變化，調整搜索的方向，開始搜尋新的環境下的PS。

2.2.1 評估環境變化強度

一個進化算法通常很難準確的求得Pareto最優前沿，所以不能直接得到變化的程度?？梢酝ㄟ^當前種群和歷史種群之間目標值的偏差評估環境的變化。測量偏差Fmean和環境變化強度Ieva(t)的公式如下[24]：

(4)

(5)

2.2.2 系統預設的環境變化強度

環境變化的幅度τt會對算法對環境的適應程度產生比較大的影響，所以將系統預設的環境變化強度Isys設置為：

(6)

2.2.3 種群初始化比例自適應調整

如果環境發生了變化，則根據環境變化強度自適應調整種群初始化比例：

(7)

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

3 DSK-SDMOP算法

DSK-SDMOP算法以求解靜態多目標規劃問題的NSGA-Ⅱ算法為基礎，DSK-SDMOP算法的具體步驟如下：

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

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

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

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

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

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

4 仿真實驗與結果分析

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

4.1 測試函數

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

4.2 性能指標

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

4.3 實驗結果及分析

表1 算法性能指標比較

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

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

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

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

圖2 不同環境下的SS和IGDFig.2 SS and IGD in different environments

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

5 結論

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

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