組合預(yù)測策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法

唐曉樂，王宏偉+，夏 浩，羅洪平

(1.新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830047； 2.大連理工大學(xué) 控制科學(xué)與工程學(xué)院，遼寧 大連 116024)

0 引 言

現(xiàn)實(shí)生活中許多問題可抽象為動(dòng)態(tài)多目標(biāo)優(yōu)化問題。近年來，動(dòng)態(tài)多目標(biāo)優(yōu)化在工程應(yīng)用[1,2]與科學(xué)研究[3,4]中得到了廣泛應(yīng)用。在交通運(yùn)輸領(lǐng)域，海上運(yùn)輸中多個(gè)港口對不同產(chǎn)品的供需要求，不同港口開放的時(shí)間窗口都是動(dòng)態(tài)變化的，考慮上述因素的情況下，如何合理規(guī)劃船舶路線與調(diào)度的同時(shí)減小碳排放與運(yùn)輸成本就是一個(gè)動(dòng)態(tài)多目標(biāo)優(yōu)化問題(dynamic multi-objective optimization problems，DMOPs)；在節(jié)能環(huán)保方面，污水處理過程中的進(jìn)水流量與污染物濃度總是隨時(shí)間動(dòng)態(tài)變化的，如何在這一變化過程中優(yōu)化污水處理廠的處理成本，提高污水質(zhì)量指標(biāo)也是一類DMOPs。動(dòng)態(tài)問題的時(shí)變性為解決動(dòng)態(tài)多目標(biāo)優(yōu)化問題帶來了很大的挑戰(zhàn)[5]。在過去5年里，許多新的策略被陸續(xù)提出，其中多以預(yù)測機(jī)制為主[6-9]。但這些方法大多只適用于線性的環(huán)境變化，并且算法在歷史信息較少的前期，若歷史信息不夠準(zhǔn)確，則會影響后續(xù)預(yù)測的準(zhǔn)確性。考慮到上述問題，本文提出一種基于新型組合預(yù)測策略的多目標(biāo)優(yōu)化算法(ADNSGA)。與現(xiàn)有算法相比，該算法主要有以下優(yōu)勢：

(1)利用ARIMA(autoregressive integrated moving average)與SVR(support vector regression)組合預(yù)測模型對Pareto解集(pareto set，PS)質(zhì)心進(jìn)行預(yù)測，可以增強(qiáng)算法對復(fù)雜問題與非線性問題預(yù)測的準(zhǔn)確性；

(2)歷史信息不足時(shí)，通過慣性預(yù)測方法在新環(huán)境下真實(shí)Pareto前沿(pareto front，PF)附近生成初始種群，保持多樣性的同時(shí)加快算法收斂，確保歷史最優(yōu)解集的準(zhǔn)確性；

(3)ARIMA-SVR與慣性預(yù)測方法的組合預(yù)測策略既增強(qiáng)了預(yù)測的準(zhǔn)確性，又在多個(gè)方向上增加了預(yù)測的多個(gè)可能性，避免種群陷入局部最優(yōu)。

本文選取FDA1、FDA4、FDA5[10]、dMOP1、dMOP2[11]、SW2[12]這6個(gè)動(dòng)態(tài)測試函數(shù)，將本文提出的ADNSGA算法與DNSGA-II-A、DNSGA-II-B[13]、PMGA算法[14]和SGEA算法[15]進(jìn)行對比研究，實(shí)驗(yàn)結(jié)果表明，所提算法在多個(gè)測試問題中均表現(xiàn)出更好的收斂性、多樣性與分布性，在適應(yīng)環(huán)境變化，處理線性及非線性問題方面具有一定的優(yōu)勢。

1 問題描述

考慮如下動(dòng)態(tài)多目標(biāo)優(yōu)化問題

(1)

2 基于新型預(yù)測策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法(ADNSGA)

在本節(jié)中提出了一種以NSGA-II為進(jìn)化框架，用以解決DMOPs的新型進(jìn)化算法，目的是利用歷史最優(yōu)信息，通過組合預(yù)測策略在新環(huán)境下的真實(shí)PS附近生成初始種群。為了實(shí)現(xiàn)這一目的，首先對每個(gè)時(shí)刻的歷史信息進(jìn)行有效篩選，利用聚類算法選出一定數(shù)量的代表個(gè)體。當(dāng)檢測到環(huán)境發(fā)生變化時(shí)，通過這些代表個(gè)體在前兩個(gè)時(shí)刻的值預(yù)測產(chǎn)生初始種群。最后，當(dāng)積累的質(zhì)心時(shí)間序列足夠長時(shí)使用組合預(yù)測模型預(yù)測新的質(zhì)心，并與慣性預(yù)測方法結(jié)合產(chǎn)生初始種群，這一初始種群的產(chǎn)生過程可以描述為下文中的算法2。

2.1 代表個(gè)體的選取

對環(huán)境變化后的目標(biāo)函數(shù)進(jìn)行預(yù)測的基礎(chǔ)是使用大量的歷史數(shù)據(jù)。在多目標(biāo)優(yōu)化問題中，目標(biāo)函數(shù)所形成的點(diǎn)集較大，記錄PS的全部歷史信息需要大量的存儲空間，這將影響算法的性能。為了避免占用大量的存儲空間，可從PS中選擇幾個(gè)有代表性的點(diǎn)，但是所選擇的點(diǎn)需要能夠近似描述PS及PS的分布，而不是隨意選擇幾個(gè)點(diǎn)。綜上考慮本文采取聚類的方法，在每一次檢測到環(huán)境變化時(shí)，選取K-1個(gè)代表個(gè)體，與當(dāng)前PS的質(zhì)心點(diǎn)Ci(t) 組成代表個(gè)體集，以此來代替當(dāng)前的PS流形。

首先選擇當(dāng)前PS的質(zhì)心點(diǎn)Ci(t) 以及在M個(gè)目標(biāo)函數(shù)上的極值點(diǎn)組成初始代表個(gè)體集，然后通過計(jì)算PS中所有個(gè)體到每一個(gè)代表個(gè)體的距離，將PS劃分成若干簇。若選取代表性的個(gè)體不充分，則以半徑最大的聚類中，距離代表個(gè)體最遠(yuǎn)的個(gè)體最為新的代表個(gè)體，重新計(jì)算該類下每個(gè)個(gè)體與代表個(gè)體的歐氏距離，相應(yīng)的PS中的個(gè)體將被重新劃分到對應(yīng)的類中。如此往復(fù)直到選出K個(gè)代表個(gè)體。

2.2 預(yù)測模型

2.2.1 ARIMA-SVR預(yù)測模型

ARIMA-SVR組合預(yù)測模型在處理線性問題與非線性問題方面均有著良好的表現(xiàn)。歷史最優(yōu)信息先由ARIMA進(jìn)行線性擬合，然后通過SVR模型預(yù)測殘差，彌補(bǔ)ARIMA在非線性性能方面的缺失，具體流程如圖1所示。該模型在一些工程應(yīng)用領(lǐng)域中已驗(yàn)證了其有效性。ARIMA與SVR的模型及定義請參見文獻(xiàn)[16,17]。

圖1 組合預(yù)測模型流程

2.2.2 慣性預(yù)測模型

在算法運(yùn)行前期，因可用的歷史信息較少，無法建立復(fù)雜的時(shí)間序列預(yù)測模型，為了在環(huán)境變化后更快的跟蹤最優(yōu)解集，采用慣性預(yù)測方法提高算法的適應(yīng)性，使得歷史信息更加準(zhǔn)確，為ARIMA-SVR模型的建立提供有效的歷史最優(yōu)信息。慣性預(yù)測可表示如下

xi(t+1)=xi(t)+(xi(t)-xi(t-1))

(2)

其中，xi(t+1) 是新環(huán)境下的預(yù)測點(diǎn)，因?yàn)閼T性預(yù)測并不準(zhǔn)確，因此需要加入高斯變異的方式在減小預(yù)誤差的同時(shí)增加種群在新環(huán)境下的多樣性。鄰域中的點(diǎn)采用高斯變異的方式產(chǎn)生，產(chǎn)生方式如下

u(t+1)=gaussrand(xi(t+1),d)i=1,2,…,K

(3)

其中，gaussrand產(chǎn)生以預(yù)測點(diǎn)為均值，方差為d的高斯隨機(jī)數(shù)，d用來控制隨機(jī)數(shù)鄰域大小。

2.3 預(yù)測集的產(chǎn)生

通過歷史最優(yōu)時(shí)間序列，利用ARIMA-SVR預(yù)測模型可以對新環(huán)境下的Pareto最優(yōu)解集的質(zhì)心進(jìn)行預(yù)測，從而提高算法的適應(yīng)性。然而在前期并沒有足夠多的變化來提供歷史數(shù)據(jù)，可用歷史數(shù)據(jù)較少。因此首先采用一種簡單的預(yù)測方法，稱為慣性預(yù)測，當(dāng)累積到一定的歷史最優(yōu)數(shù)據(jù)后，再加入質(zhì)心預(yù)測策略，進(jìn)一步提高算法的適應(yīng)性。預(yù)測集的產(chǎn)生可以描述為算法1。

算法1：預(yù)測集的產(chǎn)生

步驟1 選取K個(gè)代表個(gè)體組成代表個(gè)體集CS(t)；

步驟2 當(dāng)t=1時(shí)，轉(zhuǎn)到步驟7；當(dāng)1T時(shí)，t取正整數(shù)，轉(zhuǎn)到步驟4；

步驟3 根據(jù)式(2)生成新環(huán)境下的K個(gè)預(yù)測個(gè)體Cset， 然后根據(jù)式(3)得到新環(huán)境下預(yù)測集u(t+1)。 轉(zhuǎn)到步驟6；

步驟5 其它K-1個(gè)預(yù)測個(gè)體根據(jù)式(2)生成，然后根據(jù)式(3)通過Cset得到新環(huán)境下預(yù)測集u(t+1)。 轉(zhuǎn)到步驟6；

步驟6 對預(yù)測集中個(gè)體ui(t+1) 進(jìn)行如下調(diào)整

(4)

其中，ai，bi分別為搜索空間的上界與下界，i=1,2,…,n， 算法結(jié)束。

2.4 新型預(yù)測模型的動(dòng)態(tài)多目標(biāo)優(yōu)化算法(ADNSGA)

本文將所提出的組合預(yù)測策略作為環(huán)境變化響應(yīng)與DNSGA-II框架相結(jié)合，提出了基于新型預(yù)測策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法ADNSGA，其算法框架可以描述如算法2所示。

算法2：ADNSGA

步驟2 環(huán)境變化檢測，若環(huán)境發(fā)生變化則Dynamic←Truth， 否則Dynamic←False；

步驟3 若Dynamic=Truth；

由算法1生成新環(huán)境下的預(yù)測集u(t+1) 并計(jì)算其F(x,t)， 接著pop←u(t+1)，t←t+1；

步驟4 若Dynamic←False；

(1)根據(jù)交叉概率Pc從種群pop(t) 中選出父代 (xi(t),xj(t)) 進(jìn)行算數(shù)雜交，生成后代種群O1(t)；

(2)按照變異概率Pm對種群pop(t) 進(jìn)行變異操作，生成后代種群O2(t)；

步驟5 對pop(t)∪O1(t)∪O2(t) 中的個(gè)體進(jìn)行快速非支配排序，根據(jù)前沿等級與擁擠度距離選擇出N個(gè)個(gè)體，得到新的種群Q(t)， 并令pop(t)←Q(t)；

步驟6 若t>tmax， 則停止；否則轉(zhuǎn)步驟2。

ADNSGA從初始種群initialpop(N)開始，每次迭代前都會先進(jìn)行環(huán)境變化檢測，一般可以通過對當(dāng)前種群的部分個(gè)體進(jìn)行重新評估[5]，本文中采用當(dāng)前種群5%的個(gè)體pl， 根據(jù)如下環(huán)境變化檢測算子進(jìn)行檢測

(5)

其中，ω為當(dāng)前代數(shù)。當(dāng)μ(ω) 大于閾值μ*時(shí)，則判定此時(shí)環(huán)境發(fā)生了變化，采取相應(yīng)的變化響應(yīng)機(jī)制。

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

3.1 動(dòng)態(tài)優(yōu)化問題

本文將在6個(gè)測試問題上進(jìn)行算法比較，其中包括Farina等所提出的經(jīng)典測試問題FDA1，4，5[10]，兩個(gè)dMOP問題[11]，以及武燕等所提出的SW2測試問題[12]。其定義及其PS與PF見表1。

圖2(a)～圖2(f)分別為nT=10，n=20時(shí)F1～F6的真實(shí)帕累托前沿(pareto front，PF)，其中F1與F4的PF不隨時(shí)間變化。圖3(a)～圖3(f)分別為參數(shù)設(shè)置nT=10，n=20時(shí)F1～F6的PS在低維空間中的投影，其中F2的PS不隨時(shí)間變化。這些問題中時(shí)間步t=τ/τT， 其中τ為當(dāng)前種群迭代次數(shù)，τT為環(huán)境變化頻率，nT代表環(huán)境變化程度。

表1 動(dòng)態(tài)多目標(biāo)優(yōu)化問題定義

圖2 F1～F6的真實(shí)PF

圖3 F1～F6的PS在低維空間中的投影

3.2 性能指標(biāo)

本文采用改進(jìn)的反向世代距離MIGD(modified inver-ted generational distance)[6,15]、改進(jìn)的分布測度MHVD(modified hypervolume difference)、改進(jìn)的超體積MSP(modified spacing)3個(gè)評價(jià)指標(biāo)來評價(jià)算法的性能。MIGD、MHVD主要通過對真實(shí)PF的接近程度來衡量算法的收斂性與多樣性，MSP用于衡量算法的均勻分布性，3個(gè)評價(jià)指標(biāo)的結(jié)合可以幫助更加全面了解每種算法。與MIGD一樣，MHVD、MSP分別為一段時(shí)間內(nèi)HVD[6,15]與SP[6,15]的平均值。實(shí)驗(yàn)中兩目標(biāo)問題FDA1、dMOP1、dMOP2和SW2設(shè)置參考點(diǎn)數(shù)為1000個(gè)，三目標(biāo)問題FDA4、FDA5參考點(diǎn)數(shù)為2500個(gè)。

3.3 對比算法及參數(shù)設(shè)置

為了驗(yàn)證所提出算法的優(yōu)越性，本文選擇了有代表性的4種動(dòng)態(tài)多目標(biāo)算法來進(jìn)行對比研究。分別為：加入重新初始化種群方法的DNSGA-II-A、DNSGA-II-B[13]，當(dāng)檢測到環(huán)境變化時(shí)，前者隨機(jī)重新初始化部分個(gè)體，后者則是隨機(jī)對部分個(gè)體進(jìn)行變異操作；PMGA[14]通過聚類選取PS質(zhì)心，結(jié)合慣性預(yù)測的方法生成新環(huán)境下的初始種群。SGEA[15]通過線性時(shí)間序列模型，利用相鄰時(shí)刻的兩個(gè)PS中心點(diǎn)預(yù)測種群進(jìn)化的步長；通過少量相鄰時(shí)刻的非支配解集中心點(diǎn)預(yù)測進(jìn)化方向，指導(dǎo)生成預(yù)測種群。

5種算法中的參數(shù)設(shè)置如下：

(1)迭代進(jìn)化：兩目標(biāo)問題F1、F2、F3、F6中種群規(guī)模N=100，三目標(biāo)問題F4、F5中N=200；交叉概率Pc=0.9，變異概率Pm=0.1，n=20為決策空間的維數(shù)，進(jìn)化代數(shù)設(shè)定為gen=1600；

(2)預(yù)測部分：PMGA中質(zhì)心選取個(gè)數(shù)與ADNSGA中代表個(gè)體數(shù)均為K=10，ARIMA模型階數(shù)為p=3，q=3，SVR模型選取徑向基函數(shù)(RBF)為核函數(shù)，歷史最優(yōu)序列長度L=23，高斯隨機(jī)數(shù)的方差d=0.35；

(3)環(huán)境變化：設(shè)定環(huán)境變化程度nT=10，變化頻率τT=10，環(huán)境變化檢測閾值μ*=0.01，最大環(huán)境變化次數(shù)tmax=160； 從當(dāng)前種群中隨機(jī)選擇5%的個(gè)體用以檢測環(huán)境變化，當(dāng)t>tmax時(shí)算法終止。

3.4 實(shí)驗(yàn)結(jié)果與分析

表2～表4分別為5種算法在環(huán)境變化設(shè)置為nT=10，τT=10時(shí)，求解F1～F6動(dòng)態(tài)多目標(biāo)測試問題所獲得的3種度量的平均值與標(biāo)準(zhǔn)差。從表2中可以看出。

表2 獨(dú)立運(yùn)行20次的MSP度量統(tǒng)計(jì)結(jié)果

(1)就SP度量而言，在0≤t<20時(shí)，ADNSGA僅在F6上表現(xiàn)最佳，這說明單一的慣性預(yù)測策略無法保證算法在真實(shí)PF上分布的均勻性，應(yīng)在運(yùn)行前期結(jié)合一些策略來改善其分布性能；

(2)當(dāng)20≤t≤160時(shí)，ADNSGA在F1、F3、F5、F6上表現(xiàn)優(yōu)異，在F4上也優(yōu)于除DNSGA-II-A外的其它3種算法，說明組合預(yù)測策略比起單一的預(yù)測策略能有效提升算法沿真實(shí)PF均勻分布的性能；

(3)整個(gè)運(yùn)行過程中，ADNSGA在F6上始終優(yōu)于其它對比算法，表明了其在處理非線性問題方面有更好的分布性。

從表3中可以得到以下信息：

(1)當(dāng)0≤t<20時(shí)，ADNSGA在F2、F3、F6上有著更好的收斂性與多樣性，但在F4、F5兩個(gè)三目標(biāo)問題上，DNSGA-II-A優(yōu)于其它對比算法，說明重新初始化部分個(gè)體的動(dòng)態(tài)響應(yīng)策略在三目標(biāo)問題上比單一的預(yù)測方法擁有更好的適應(yīng)性;

(2)當(dāng)20≤t≤160時(shí)，ADNSGA在所有6個(gè)動(dòng)態(tài)測試問題上均優(yōu)于其它對比算法，表明了組合預(yù)測策略的有效性。

表3 獨(dú)立運(yùn)行20次的MHVD度量統(tǒng)計(jì)結(jié)果

從表4中可以看出：

(1)從數(shù)值上看，ADNSGA在大部分測試問題上都取得了不錯(cuò)的結(jié)果。當(dāng)0≤t<20時(shí)，ADNSGA算法在F1～F5的問題上，雖然不是表現(xiàn)最佳，但也始終處于第二的水平，優(yōu)于其它3種算法，這表明慣性預(yù)測方法在算法運(yùn)行初期是有效的，并且有著更好的普適性；

(2)當(dāng)20≤t≤160時(shí)，ADNSGA算法在F1、F3～F6問題上均表現(xiàn)更好的性能，在F2問題上，DNSGA-II-B算法表現(xiàn)出了更好的收斂性與多樣性，原因在于F2問題中PS是固定不變的，采用預(yù)測的方式并不能很好指引新環(huán)境下的初始種群，因此PMGA、SGEA、ADNSGA均表現(xiàn)欠佳，而采取重新初始化或變異部分個(gè)體的方法，一旦找到F2的真實(shí)PS，就可以快速逼近新環(huán)境下的PS和PF。DNSGA-II-B在均值上略微優(yōu)于DNSGA-II-A，說明采用變異的策略可以具有更好的多樣性；

(3)在F6測試問題上，ADNSGA始終優(yōu)于其它對比算法，表現(xiàn)出更好的收斂性與多樣性。

表4 獨(dú)立運(yùn)行20次的MIGD度量統(tǒng)計(jì)結(jié)果

為了進(jìn)一步討論所提算法的性能，圖4(a)～圖4(f)繪制了ADNSGA及4種對比算法在F1～F6上，獨(dú)立運(yùn)行20次的平均IGD度量與時(shí)間的關(guān)系圖。首先在0≤t<20時(shí)，ADNSGA在大部分問題上優(yōu)于其它對比算法，當(dāng)t≥23時(shí)，開始通過ARIMA-SVR模型對PS質(zhì)心點(diǎn)進(jìn)行預(yù)測，ADNSGA的IGD值在除F2之外的5個(gè)問題上均優(yōu)于其它對比算法，且數(shù)值波動(dòng)較小，而未采取預(yù)測策略的DNSGA-II-A、DNSGA-II-B則波動(dòng)很大，這表明采用中心點(diǎn)預(yù)測的方法能夠有效的跟蹤環(huán)境變化。將PMGA、SGEA、ADNSGA這3種采取預(yù)測策略的算法進(jìn)行對比，采取組合預(yù)測策略的ADNSGA始終優(yōu)于PMGA與SGEA，在F6問題上優(yōu)勢尤為顯著。

圖4 5種算法平均IGD值與時(shí)間的關(guān)系

圖5、圖6中(a)～(e)分別為5種算法在F6問題上，20次獨(dú)立運(yùn)行中，當(dāng)t=140，t=143，t=147時(shí)IGD最小的初始種群與最終種群。從圖5和圖6中同樣能清晰看到，ADNSGA相比于對比算法能更準(zhǔn)確追蹤Pareto最優(yōu)前沿。

圖5 5種算法IGD最小的初始種群

圖6 5種算法IGD最小的最終種群

通過對5種算法的MIGD、MSP和MHVD性能指標(biāo)的統(tǒng)計(jì)分析可知，本文提出的ADNSGA算法所采取的組合預(yù)測策略更適用于PS變化及PS、PF同時(shí)變化的問題，在算法運(yùn)行前期加入的慣性預(yù)測方法可以使算法在大部分測試問題中保持較好的收斂性與多樣性，具有很好的推廣性與普適性，但在分布性方面有所欠缺，積累到足夠的歷史信息后，組合預(yù)測模型使得算法在非線性問題上表現(xiàn)出良好的競爭優(yōu)勢，同時(shí)提升算法對真實(shí)PF的均勻覆蓋性。

4 結(jié)束語

針對動(dòng)態(tài)多目標(biāo)優(yōu)化問題，本文提出一種基于組合預(yù)測策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法(ADNSGA)，該算法在單一的慣性預(yù)測方法上增加了組合預(yù)測模型的質(zhì)心預(yù)測，為預(yù)測最新的PS提供了更準(zhǔn)確的指導(dǎo)依據(jù)。實(shí)驗(yàn)結(jié)果表明，ADNSGA算法在多種動(dòng)態(tài)問題上都有很好的環(huán)境適應(yīng)能力。此外如何在算法前期提高在PF上的分布性是未來工作的一個(gè)可研究方向。另外如何根據(jù)環(huán)境變化程度[18]合理分配預(yù)測策略也是一個(gè)值得研究的課題。當(dāng)前，動(dòng)態(tài)多目標(biāo)優(yōu)化在控制問題、調(diào)度問題、機(jī)械設(shè)計(jì)問題、圖像分割問題，資源管理問題等現(xiàn)實(shí)生活和工業(yè)生產(chǎn)方面[5,16,17]應(yīng)用廣泛。本文所提算法在為求解此類問題提供新思路的同時(shí)，豐富了動(dòng)態(tài)多目標(biāo)優(yōu)化的應(yīng)用前景。