基于改進(jìn)狼群算法的模糊時間序列預(yù)測模型

鮮思東 ,李堂金

(1.重慶郵電大學(xué)復(fù)雜系統(tǒng)智能分析與決策重點(diǎn)實(shí)驗室,重慶 400065;2.重慶郵電大學(xué)自動化學(xué)院,重慶 400065)

1 引言

以時間軸為依據(jù),按照一定的時間間隔記錄的數(shù)據(jù)稱為時間序列.利用時間序列進(jìn)行分析是預(yù)測未來結(jié)果最古老和最可靠的技術(shù)之一.傳統(tǒng)的時間序列預(yù)測方法不能解決時間序列值為“差”、“中等”、“好”等由語言術(shù)語描述的問題.為了克服這一缺陷,Zadeh教授提出了模糊集(fuzzy sets,FS)理論[1],Song和Chissom將模糊集理論成功引入時間序列模型中,首次提出了模糊時間序列(fuzzy time series,FTS)模型[2–4].在這種模型中,觀測值是模糊集,并在當(dāng)前狀態(tài)和以前狀態(tài)之間建立關(guān)系.

模糊時間序列的另一個特點(diǎn)是它分析處理小數(shù)據(jù)集的能力相對于傳統(tǒng)的時間序列更好.20多年以來,廣大學(xué)者們在大學(xué)招生[2,5–14]、氣候?qū)W[8–9,15]、股票市場[5,8–10,16–19]、醫(yī)療健康[20]、旅游[21]等不同的應(yīng)用領(lǐng)域建立了許多模糊時間序列預(yù)測模型.

論域劃分是影響模糊時間序列模型預(yù)測精度的關(guān)鍵因素之一[5].論域劃分方法可以分為兩類:等長度劃分和非等長度劃分.早期的研究都采用相等長度的論域劃分方法[6–7],現(xiàn)在學(xué)者們更多地采用了非等長度的論域劃分方法.在基于數(shù)學(xué)模型的劃分方法中,“最小熵原理法”和“梯形模糊化法”[22]、自動聚類技術(shù)[8,16]、“動態(tài)挖掘距離法”[23]、“基于均值的離散化法”[9]都表現(xiàn)出了較好的性能.此外,為了提高預(yù)測精度,“信息粒”[10,17]和“模糊離散化技術(shù)”[24]也被用來劃分區(qū)間.在基于仿生優(yōu)化算法的論域劃分方法中,粒子群優(yōu)化算法(particle swarm optimization,PSO)[11–12,25]、蟻群優(yōu)化(ant colony optimization,ACO)[18]、遺傳算法(genetic algorithm,GA)[13,19]、人工魚群算法(artificial fish swarm algorithm,AFSA)[14,26]均取得了不錯的效果.

為了進(jìn)一步提高模糊時間序列預(yù)測模型的預(yù)測精度,本文將狼群算法(wolf pack algorithm,WPA)進(jìn)行了改進(jìn)并用于模糊區(qū)間的劃分,提出了一種基于改進(jìn)的狼群算法(improved wolf pack algorithm,IWPA)的模糊時間序列預(yù)測模型(IWPA–FTS).首先針對基本狼群算法在游走過程中收斂速度慢、容易陷入局部極值的缺陷,引入趨向行為和死亡概率,有效提高探狼的收斂速度和跳出局部極值的能力.然后將改進(jìn)的狼群算法用于優(yōu)化論域的劃分.最后以Alabama大學(xué)入學(xué)人數(shù)作為實(shí)驗數(shù)據(jù)來驗證所提模型的有效性.通過與現(xiàn)有的一些模型進(jìn)行對比分析,本文所提模型具有更高的預(yù)測精度.

2 模糊時間序列(FTS)

定義1設(shè)X為論域,X由有限個離散的元素構(gòu)成,即X{x1,x2,···,xn}.則定義在論域上的模糊集合可以表示為

其中:fA是模糊集合A的隸屬度函數(shù),并且fA:X →[0,1],fA(xi)表示xi屬于模糊集A的隸屬度值.

定義2設(shè)論域Y(t)(t···,0,1,2,···)是實(shí)數(shù)集R上的一個子集,fi(t)(i1,2,···)是定義在Y(t)上的模糊集.如果F(t)是f1(t),f2(t),f3(t),···的一個集合,即F(t){f1(t),f2(t),f3(t),···},則把F(t)稱為定義在Y(t)上的模糊時間序列.

定義3設(shè)F(t)(t1,2,3,···)為一個模糊時間序列,如果F(t)由F(t?1)確定,R(t ?1,t)為F(t)和F(t ?1)之間的模糊邏輯關(guān)系(fuzzy logic relation,FLR),則

定義4設(shè)有一組一階模糊模糊邏輯關(guān)系為Ai→Ak1,Ai→Ak2,···,Ai→Akm,即它們擁有相同的當(dāng)前狀態(tài),則可以用一個模糊邏輯關(guān)系組(fuzzy logical relation group,FLRG)將它們表示為

定義5設(shè)F(t)由F(t ?n),F(t ?n+1),···,F(t ?1)導(dǎo)致,則n階模糊邏輯關(guān)系可以表示為

模糊時間序列的一般預(yù)測步驟如下:1)確定并劃分論域;2)模糊化實(shí)際數(shù)據(jù);3)建立FLRs和FLRGs;4)去模糊化計算預(yù)測值.

3 改進(jìn)的狼群算法(IWPA)

吳虎勝等人受到自然界狼群狩獵行為和它們的獵物分配模式的啟發(fā),提出了狼群算法(WPA)[27],并用它來解決優(yōu)化問題.WPA中的狼一般分為3類:頭狼、探狼和猛狼,狼群的整個捕食行為被抽象為3種智能行為,即游走、召喚和圍攻行為,以及兩種智能規(guī)則,即“勝者為王”的頭狼生成規(guī)則和“強(qiáng)者生存”的狼群更新規(guī)則.下面對這些行為和規(guī)則進(jìn)行詳細(xì)的說明.

假設(shè)人工狼群的獵場空間為N ×D維,其中N為人工狼的數(shù)量,D為解空間變量的個數(shù),則第i匹人工狼的位置可以表示為

xid(d1,2,···,D)為人工狼i的第d個待尋優(yōu)的變量.位置在XXXi的第i匹人工狼的適應(yīng)度值(目標(biāo)函數(shù)值)可定義為Yif(XXXi).

1)“勝者為王”的頭狼產(chǎn)生規(guī)則:在初始解空間中,選擇目標(biāo)函數(shù)值最優(yōu)的人工狼為頭狼.每次迭代后,將目標(biāo)函數(shù)值最好的人工狼與上一代頭狼進(jìn)行比較.如果它的目標(biāo)函數(shù)值更好,那么上一代頭狼將被替換,頭狼的位置將被更新.頭狼不參與執(zhí)行3種智能行為,而是直接進(jìn)入下一次迭代,直到被更強(qiáng)的狼替換.

2)游走行為:除了頭狼外,讓目標(biāo)函數(shù)值最佳的Snum匹人工狼充當(dāng)探狼.Snum是在區(qū)間中隨機(jī)選擇的整數(shù).α為探狼比例因子.首先,探狼分別向h不同方向邁出一步,記錄每個方向的適應(yīng)度值.然后回到原來的位置.探狼i向第p(p1,2,···,h)個方向邁出一步后,它的位置表示為

其中:rand()是在區(qū)間[?1,1]中均勻分布的隨機(jī)數(shù),stepa表示游走步長.探狼i向h個方向中選擇具有最優(yōu)適應(yīng)度值且優(yōu)于原位置的方向前進(jìn)一步,更新位置XXXi.重復(fù)上述行為直到某匹人工狼的適應(yīng)度值優(yōu)于頭狼或者達(dá)到最大游走次數(shù)Tmax.

3)召喚行為:頭狼通過嚎叫召喚周圍的Mnum匹猛狼快速向頭狼靠近.其中MnumN ?Snum?1.猛狼以相對較大的步長stepb向頭狼的位置聚集.猛狼i的位置更新式如下:

其中GGGk是第k代頭狼的位置.在奔襲的過程中,如果猛狼i的適應(yīng)度值Yi比頭狼的適應(yīng)度值Ylead更好,該猛狼將代替頭狼,同時YleadYi.然后由新的頭狼發(fā)起召喚行為.否則,猛狼i繼續(xù)向頭狼的位置靠攏直到d(i,lead)

其中:?是距離判定因子,[mind,maxd]是第d個變量的取值范圍.

4)圍攻行為:通過向頭狼的位置聚集后,猛狼離頭狼的位置都比較近了.這時將頭狼的位置視為獵物的位置,猛狼將和探狼一起進(jìn)行圍攻獵物.圍攻過程中人工狼i的位置更新式如下:

其中: λ是在區(qū)間[?1,1]均勻分布的隨機(jī)數(shù);stepc表示圍攻步長.如果人工狼i執(zhí)行圍攻行為后,新位置的適應(yīng)度值優(yōu)于原位置的值,則更新該狼的位置XXXi.否則不變.

在3種智能行為中涉及的步長stepa,stepb和stepc之間具有如下的關(guān)系:

其中S表示步長因子,它決定了人工狼在解空間尋找最優(yōu)解的精細(xì)程度.

5)“強(qiáng)者生存”的狼群更新規(guī)則:這個規(guī)則模擬達(dá)爾文提出的自然選擇法則.為了保障種族的延續(xù),食物按照先強(qiáng)后弱的順序進(jìn)行分配,這會導(dǎo)致一些弱小的狼因為分配不到食物而餓死.在實(shí)際算法中表現(xiàn)為淘汰m匹具有最差適應(yīng)度值的人工狼,同時在解空間內(nèi)隨機(jī)生成m匹新的人工狼.m是在區(qū)間隨機(jī)選擇的一個整數(shù).β為群體更新比例因子.

WPA算法具有良好的全局收斂能力,同時也有一些缺點(diǎn),如收斂速度慢、容易陷入局部極值等.本文對WPA的游走行為進(jìn)行改進(jìn),提出了改進(jìn)的狼群算法(IWPA).

在狼群算法的游走行為中,當(dāng)h個方向中具有最優(yōu)適應(yīng)度值的位置比原位置好的時候,人工狼僅僅向該方向前進(jìn)一步,然后重新選擇h個方向重復(fù)前面的行為,這導(dǎo)致了狼群算法的收斂速度過慢.事實(shí)上,具有最優(yōu)適應(yīng)度值的方向是最可能改善適應(yīng)度值的方向.因此,為了加速狼群算法的收斂速度,本文在這里引入一個趨向行為.當(dāng)人工狼朝著改善適應(yīng)度值的方向移動一步后,人工狼將繼續(xù)沿同一方向前進(jìn)幾步,直到人工狼的適應(yīng)度值不再改善或移動步數(shù)(Ns)達(dá)到了最大值(Nsmax).在前進(jìn)的過程中,人工狼的位置更新式如下:

其中:rand是在區(qū)間[0,1]之間均勻分布的隨機(jī)數(shù),

為適應(yīng)度改善的方向,XXXj為具有更優(yōu)適應(yīng)度值的位置向量.

另外,在游走過程中,當(dāng)h方向中的最優(yōu)適應(yīng)度比初始位置差時,算法可能已經(jīng)陷入局部極值.在這種情況下,為了提高人工狼跳出局部極值的能力,本文做出如下改進(jìn):對于上述情況的人工狼,本文設(shè)置一個死亡概率Pe,當(dāng)人工狼滿足死亡概率時,該人工狼死亡,并隨機(jī)地在解空間的任何地方生成一個新的個體,否則位置不變.改進(jìn)后的人工狼游走行為的偽代碼如算法1所示.

算法1改進(jìn)后的游走行為.

4 IWPA–FTS預(yù)測模型

為了進(jìn)一步提高模糊時間序列模型的預(yù)測精度,本文將IWPA算法用于模糊區(qū)間的劃分,建立了IWPA–FTS預(yù)測模型.利用IWPA尋找最優(yōu)的區(qū)間劃分點(diǎn)的具體步驟如下:

步驟1初始化參數(shù).

步驟2計算每匹人工狼在當(dāng)前位置的適應(yīng)度值.

步驟2.1模糊化每一個歷史數(shù)據(jù).

在模糊時間序列中,模糊集通常由下面的公式定義:

其中u1,u2,u3,···,un表示區(qū)間.

確定好模糊集后,就可以將每個數(shù)據(jù)模糊化.為了確定數(shù)據(jù)x所對應(yīng)的模糊集,本文首先要確定數(shù)據(jù)x所屬的模糊區(qū)間ui,然后計算數(shù)據(jù)x屬于區(qū)間ui的隸屬度值,接著找出最大隸屬度值所對應(yīng)的模糊集Ai.最后,數(shù)據(jù)x就被模糊化為Ai.

步驟2.2建立模糊關(guān)系和模糊關(guān)系組.

通過定義3–4建立FLRs和FLRGs.高階FLRs可根據(jù)定義5建立.

步驟2.3去模糊化并計算預(yù)測值.

預(yù)測值通過兩種不同的方法計算:對訓(xùn)練階段的數(shù)據(jù)采用基于下一狀態(tài)嵌入式貝葉斯網(wǎng)絡(luò)(embedded Bayesian network,EBN)的方法,對測試階段的數(shù)據(jù)采用主投票(master voting,MV)方法進(jìn)行計算.

Kuo等[28]提出了EBN算法.其基本思想是:對每一個FLRG中的所有下一狀態(tài)所對應(yīng)的模糊區(qū)間等長度劃分為3個小區(qū)間,然后根據(jù)下面的表達(dá)式計算出預(yù)測值:

其中: n表示在同一FLRG中下一狀態(tài)的總數(shù),midk(1kn)表示下一狀態(tài)對應(yīng)的模糊區(qū)間的中點(diǎn)值,submidk表示第k個下一狀態(tài)所對應(yīng)的實(shí)際數(shù)據(jù)在3個小區(qū)間中所屬的那個小區(qū)間的中點(diǎn)值.為便于理解,本文舉個簡單的例子進(jìn)行說明:假設(shè)在某一FLRG中的其中一個下一狀態(tài)對應(yīng)的實(shí)際數(shù)據(jù)為1550并且該狀態(tài)對應(yīng)的模糊區(qū)間為ui[1000,1600],則這3個小區(qū)間分別為ui1[1000,1200],ui2(1200,1400],ui3(1400,1600].因此,

在測試階段,本文采用Kuo等[11]提出的MV方法.其計算式如下：

其中λ代表預(yù)測時需要用的與預(yù)測時刻相鄰的前面時刻數(shù)據(jù)的個數(shù),mti(i1,2,···,λ)為前面第i時刻的數(shù)據(jù)所屬模糊區(qū)間的中點(diǎn)值,Wh表示與預(yù)測時刻相鄰時刻的數(shù)據(jù)對預(yù)測值的影響程度.為了方便比較,本文取Wh15.

步驟2.4計算適應(yīng)度值.

本文把預(yù)測值與真實(shí)值之間的均方根誤差(root mean square error,RMSE)作為人工狼的適應(yīng)度值,其計算式如下:

比較所有人工狼的初試適應(yīng)度值,選取擁有最優(yōu)適應(yīng)度值(最小RMSE值)的人工狼作為頭狼.

步驟3選擇人工狼的行為.

步驟3.1除頭狼外,選擇Snum匹具有最佳適應(yīng)度值的狼作為探狼,執(zhí)行改進(jìn)的游走行為,直到某匹狼的適應(yīng)度值優(yōu)于頭狼或者達(dá)到最大游走次數(shù)Tmax,然后轉(zhuǎn)向步驟3.2.

步驟3.2頭狼通過嚎叫執(zhí)行召喚行為.剩余的Mnum匹猛狼快速向獵物靠近.在奔襲的過程中,如果某匹猛狼的適應(yīng)度值優(yōu)于頭狼,則該猛狼將代替頭狼并發(fā)起召喚行為,否則,猛狼繼續(xù)向頭狼靠攏直到與頭狼的距離d(i,lead)

步驟3.3探狼和猛狼一起執(zhí)行圍攻行為.

步驟3.4根據(jù)“強(qiáng)者生存”的狼群更新原則更新狼群.

步驟4判斷結(jié)束條件.

如果算法達(dá)到最大迭代次數(shù)M或者已經(jīng)達(dá)到預(yù)設(shè)精度,則輸出最后一次迭代后頭狼的適應(yīng)度值和相應(yīng)的位置向量,同時得到的還有模糊時間序列、FLRs、FLRGs和訓(xùn)練階段的預(yù)測值.否則,重復(fù)步驟3–4.

5 實(shí)例分析

在本節(jié)中,利用了Alabama大學(xué)1971年至1992年的實(shí)際入學(xué)人數(shù)(表1第2列)來證明本文所提模型的有效性.本實(shí)驗使用MATLAB 2016a編寫仿真程序,在Windows 10操作系統(tǒng),因特爾i5–6500 3.19 GHz處理器,16 G內(nèi)存的PC機(jī)上實(shí)現(xiàn).預(yù)測精度通過式(11)定義的均方根誤差(RMSE)和式(12)平均預(yù)測誤差率(average forecasting error rate,AFER)進(jìn)行測量,AFER定義如下:

5.1 訓(xùn)練階段

相對應(yīng)的模糊化結(jié)果、3階FLR以及訓(xùn)練階段的預(yù)測值都如表1所示.圖1為訓(xùn)練階段的實(shí)際入學(xué)人數(shù)與預(yù)測入學(xué)人數(shù)的對比.從圖1中可以清楚地看出,運(yùn)用本文的模型計算出的預(yù)測值與實(shí)際值非常接近.

表1 實(shí)際數(shù)據(jù)和訓(xùn)練階段結(jié)果Table 1 Actual data and training phase results

為了直觀地說明IWAP的優(yōu)越性,本文對混合人工魚群算法(hybrid artificial fish swarm algorithm,HAFSA)[26]、WPA和IWPA3種算法劃分論域進(jìn)行了比較,這里區(qū)間劃分個數(shù)為7,模型階數(shù)為2,仿真結(jié)果取20次運(yùn)行結(jié)果的平均值,它們的收斂曲線如圖2所示,優(yōu)化結(jié)果及耗時情況如表2所示.由圖2可知,IWPA具有更快的收斂速度和更高的優(yōu)化精度.在表2中,根據(jù)最好的最優(yōu)值、最差的最優(yōu)值、平均最優(yōu)值3項指標(biāo)可以看出,IWPA獲得的結(jié)果最好,其次為WPA和HAFSA.另外,根據(jù)平均耗時情況來看,雖然WPA的耗時比HAFSA多,但是WPA的優(yōu)化精度要比HAFSA高.IWPA耗時最少獲得的精度最高.說明本文在WPA算法的游走行為中引入的趨向行為和死亡概率能有效改善WPA算法的收斂速度和優(yōu)化精度.

圖1 實(shí)際值與預(yù)測值對比結(jié)果Fig.1 Actual vs forecasted

圖2 3種算法仿真結(jié)果比較Fig.2 Comparison results of three different algorithms

表2 優(yōu)化結(jié)果比較Table 2 The comparison of optimization results

為了驗證IWPA–FTS模型預(yù)測精度的提高,本文選取C96[6],Q11[29],W13[30],PSO[25],IFTS[31]以及HAFSA[26]多種預(yù)測模型進(jìn)行比較,所有模型的區(qū)間劃分?jǐn)?shù)都取7.比較結(jié)果如圖3所示,從圖3可以明顯看出本文所提模型在訓(xùn)練階段的預(yù)測精度最高.

為了驗證本文所提模型在不同階數(shù)情況下預(yù)測精度的有效性,本文與4個現(xiàn)有的預(yù)測模型:TVFTS[32],GA[33],PSO[11],HAFSA[26]分別在2階、3階和4階的情況下做了一個對比.所有預(yù)測模型的區(qū)間劃分個數(shù)為7,對比結(jié)果如表3所示.可以看出本文的模型在不同階情況下均得到了最小的RMSE值以及最小的平均RMSE值.

圖3 不同模型預(yù)測精度比較Fig.3 Comparison results of various forecast models

表3 不同階數(shù)情況下的對比結(jié)果Table 3 Comparison results of different orders

5.2 測試階段

為了驗證本文所提模型在測試階段的效果,即預(yù)測未來的能力.本文將實(shí)際數(shù)據(jù)的最后3個作為測試數(shù)據(jù)集,根據(jù)剩余的19個數(shù)據(jù)建立相應(yīng)的FLR和FLRG,對最后3個數(shù)據(jù)進(jìn)行預(yù)測.將本文的預(yù)測結(jié)果同模型C96[6],HPSO[11],AFPSO[12]的預(yù)測結(jié)果進(jìn)行對比,所有模型都采用MV方法進(jìn)行預(yù)測,Wh15,λ3,區(qū)間劃分個數(shù)n7,模型階數(shù)為3,比較結(jié)果如表4所示.從表4可以看出,本文所提模型得到的預(yù)測結(jié)果具有最小的RMSE值和AFER值.

表4 測試階段預(yù)測結(jié)果比較Table 4 Comparison of the predicted results for the testing phase

6 結(jié)論

本文提出了一種基于改進(jìn)狼群算法的模糊時間序列預(yù)測模型,并用它來預(yù)測Alabama大學(xué)的入學(xué)人數(shù).本文的主要創(chuàng)新點(diǎn)和貢獻(xiàn)如下:首先,提出了改進(jìn)的狼群算法(IWPA),有效地提高了算法在游走階段的收斂速度和跳出局部極值的能力.其次,本文首次將模糊時間序列與狼群算法相結(jié)合提出了IWPA–FTS預(yù)測模型,拓寬了狼群算法的應(yīng)用范圍.最后,通過與各種預(yù)測模型相比,本文所提模型在訓(xùn)練階段和測試階段均能獲得較好的預(yù)測性能,證實(shí)了該模型的有效性.