基于改進(jìn)免疫遺傳算法和Holt-Winters的電能計(jì)量器具配送優(yōu)化

王 杰，孫 林，鄭 直，張嘉浩，黃 雷

(1.國電南瑞科技股份有限公司，江蘇 南京 210032；2.金現(xiàn)代信息產(chǎn)業(yè)股份有限公司，山東 濟(jì)南 250101；3.湖南大學(xué)電氣與信息工程學(xué)院，湖南 長沙 410082)

隨著智能電網(wǎng)的迅速發(fā)展，電能計(jì)量器具也逐步由傳統(tǒng)電能表轉(zhuǎn)變?yōu)橹悄茈姳怼Ｖ悄茈姳硐啾扔趥鹘y(tǒng)電能表可以給用戶提供更加精確的用電信息，通過科學(xué)記錄，可以讓用戶用電更趨合理，同時(shí)可以調(diào)整電能質(zhì)量，及時(shí)處理電能故障，提高人身與設(shè)備的安全性。然而，大規(guī)模安裝使用智能電表會導(dǎo)致倉儲規(guī)模的持續(xù)擴(kuò)大和物流量的不斷增長。這就要求電網(wǎng)計(jì)量中心不僅要采取相應(yīng)措施降低物流配送成本,還要保持較高的客戶服務(wù)水平[1-2]。

目前，國家電網(wǎng)提出了“整體授權(quán)、自動(dòng)檢定、智能倉儲、高效配送”的基本目標(biāo)，然而現(xiàn)今智能電表的各項(xiàng)配送活動(dòng)主要以人工安排和調(diào)度為主，以計(jì)量中心為起始點(diǎn)，通過人工上報(bào)的數(shù)據(jù)將智能電表送往各個(gè)調(diào)度中心，用戶購買時(shí)進(jìn)行配送，此情況下的配送效率相對較低，配送信息的共享性較差。因此，有必要規(guī)劃計(jì)量中心—配送中心—客戶的二級物流配送網(wǎng)絡(luò)，才能實(shí)現(xiàn)不同運(yùn)輸方式的有機(jī)配合。規(guī)劃物流配送網(wǎng)絡(luò)要確定網(wǎng)絡(luò)中配送中心數(shù)量、所處位置及其客戶分配情況，配送網(wǎng)絡(luò)的合理化程度對企業(yè)物流配送效益的高低起著決定性作用，開展關(guān)于電能計(jì)量器具物流配送網(wǎng)絡(luò)優(yōu)化的相關(guān)研究十分有必要[3]。

配送網(wǎng)絡(luò)優(yōu)化問題大致可分為預(yù)測和選址兩部分，大量學(xué)者對此開展了研究工作。關(guān)于時(shí)間序列預(yù)測，文獻(xiàn)[4]根據(jù)配電系統(tǒng)的歷史負(fù)荷信息，運(yùn)用Holt-Winters模型預(yù)測了負(fù)荷的偽測量值，進(jìn)而優(yōu)化了用于配電系統(tǒng)狀態(tài)評估的無跡卡爾曼模型；文獻(xiàn)[5]提出了一種基于業(yè)務(wù)特征的電能表需求預(yù)測模型，該模型根據(jù)安裝類型對電能表分類，再利用平穩(wěn)性檢驗(yàn)來分析安裝類型影響需求量的主要因素，進(jìn)而自適應(yīng)地使用時(shí)間序列模型(autoregressive integrated moving average model，ARIMA)對電能表需求量進(jìn)行分析預(yù)測，預(yù)測數(shù)據(jù)可靠。關(guān)于選址優(yōu)化問題，免疫遺傳算法具有保證種群多樣性的特征，克服了粒子群算法容易陷入局部最優(yōu)的缺點(diǎn)，且具有較高的收斂速度，能夠很好地解決多目標(biāo)優(yōu)化問題[6-7]。免疫遺傳算法還可通過多種方式對其進(jìn)行改進(jìn)，文獻(xiàn)[8]運(yùn)用改進(jìn)免疫遺傳算法，通過重新定義抗體濃度，提出一種抗體濃度新定義下的策略，解決電壓無功優(yōu)化問題時(shí)改進(jìn)算法在計(jì)算速度和優(yōu)化效果方面都具有明顯的優(yōu)勢。

本文采用Holt-Winters模型預(yù)測變化規(guī)律具有線性趨勢性和季節(jié)性的電能計(jì)量器具需求量時(shí)間序列，需求量和客戶位置信息作為已知量，以運(yùn)輸成本最小為目標(biāo)建立數(shù)學(xué)模型，采用免疫遺傳算法對電能計(jì)量器具配送網(wǎng)絡(luò)進(jìn)行優(yōu)化，為了改善算法的收斂性，提高種群的多樣性，基于相似性和矢量距對抗體濃度進(jìn)行調(diào)整，改進(jìn)免疫遺傳算法，并應(yīng)用于電能計(jì)量器具配送網(wǎng)絡(luò)的選址、定位以及分配客戶。

1 理論基礎(chǔ)

1.1 Holt-Winter模型

Holt-Winters模型是多參數(shù)季節(jié)模型，適用于預(yù)測具有線性變化趨勢且變化規(guī)律具有明顯季節(jié)性的短期時(shí)間序列，Holt-Winters模型是在一、二次指數(shù)平滑算法的基礎(chǔ)上推導(dǎo)的，也被稱為三次指數(shù)平滑模型[9]。

一次指數(shù)平滑模型適用于預(yù)測無明顯變化趨勢的時(shí)間序列，預(yù)測公式如下：

Si=αxi+(1-α)Si-1

(1)

式中Si為第i期的一次指數(shù)平滑值；xi為第i期的實(shí)際值(i=1,2,…,n)；α為平滑系數(shù)(0≤α≤1)。

二次指數(shù)平滑模型加入趨勢項(xiàng)t，可用于預(yù)測具有線性變化趨勢的時(shí)間序列，預(yù)測公式如下：

(2)

三次指數(shù)平滑模型是在二次指數(shù)平滑的基礎(chǔ)上再平滑，加入季節(jié)項(xiàng)p，可分為加法和乘法模型。加法模型適用于變化季節(jié)性較為穩(wěn)定的時(shí)間序列，而乘法模型適用于季節(jié)性呈現(xiàn)比例變化的情況。加法、乘法模型分別如下：

(3)

(4)

確定初始化水平值、趨勢值的計(jì)算公式分別為

Si=αxi+(1-α)(Si-1+ti-1)

(5)

(6)

確定初始化季節(jié)性值的方法：首先，將所給的時(shí)間序列包含的周期數(shù)計(jì)算出來；然后，將各個(gè)周期內(nèi)時(shí)間序列值的平均值計(jì)算出來。對于加法模型來說，要將時(shí)間序列每個(gè)時(shí)刻的實(shí)際值減去其所對應(yīng)周期的平均值來獲得每個(gè)時(shí)刻的差值，然后將這些差值取平均就能得到其第1個(gè)周期的初始化季節(jié)值。而對于乘法模型來說，需將時(shí)間序列每個(gè)時(shí)刻的實(shí)際值除以相應(yīng)周期的平均值得到每個(gè)時(shí)刻的比值，然后將這些比值進(jìn)行平均，得到第1個(gè)周期的初始化季節(jié)性值。

Holt-Winters模型預(yù)測趨勢是否符合實(shí)際的關(guān)鍵在于平滑系數(shù)a的選取、平滑系數(shù)控制權(quán)數(shù)下降速度，a接近1時(shí)近期數(shù)據(jù)的權(quán)重較大，a接近0時(shí)歷史數(shù)據(jù)的權(quán)重較大。它既表征了模型對時(shí)間序列數(shù)據(jù)變化的反應(yīng)速度，又決定了預(yù)測模型修勻誤差的能力。為了提高預(yù)測模型的準(zhǔn)確性，本文采用黃金分割法篩選最優(yōu)平滑系數(shù)[10]。

黃金分割法搜尋最優(yōu)平滑系數(shù)的原理是在平滑系數(shù)的取值區(qū)間找到2個(gè)黃金分割點(diǎn)，并將區(qū)間分為三部分，對比平滑系數(shù)分別取這2個(gè)值時(shí)的預(yù)測值，確定預(yù)測值較為準(zhǔn)確的黃金分割點(diǎn)，保留該點(diǎn)的相鄰兩區(qū)間，保留區(qū)間即為縮小后的平滑系數(shù)取值區(qū)間。循環(huán)上述過程，逐步縮小搜索區(qū)間，直到區(qū)間長度在允許誤差范圍時(shí)，區(qū)間內(nèi)的任意一點(diǎn)都可看作極小點(diǎn)的近似值，以此來確定最佳的平滑系數(shù)a。

1.2 改進(jìn)免疫遺傳算法

遺傳算法是一種模擬自然選擇和生物進(jìn)化過程搜索最優(yōu)解的隨機(jī)優(yōu)化方法，基本操作包括選擇、交叉和變異。免疫遺傳算法是將免疫系統(tǒng)相關(guān)概念及其理論應(yīng)用于遺傳算法中的一種智能優(yōu)化算法，該算法綜合了遺傳算法的搜索特性和免疫算法求解目標(biāo)函數(shù)的自適應(yīng)特性，能有效地抑制進(jìn)化過程中出現(xiàn)退化現(xiàn)象，同時(shí)避免搜索結(jié)果收斂于局部極值，具有良好的全局搜索能力[11-13]。免疫遺傳算法的重要概念和操作步驟如下。

1)隨機(jī)生成N個(gè)初始抗體種群。

Xi=L+U+rand(U-L)

(7)

式中Xi為第i個(gè)抗體；L、U分別為可行解的下界、上界。

2)計(jì)算抗體與抗原之間的親和力。親和度表示可行解對目標(biāo)問題的匹配程度，由于本文為物流配送優(yōu)化問題，因此，抗體與抗原之間的親和度為目標(biāo)方程的倒數(shù)：

(8)

式中f(Xi)、f(Xj)分別為第i、j個(gè)抗體的適應(yīng)度值；N為抗體總數(shù)。

抗體與抗體之間的親和度主要表示2個(gè)抗體之間的相似程度，根據(jù)歐氏距離，計(jì)算公式為

(9)

抗體濃度是指抗體種群中相似抗體所占據(jù)的比重，常規(guī)免疫遺傳算法的抗體濃度：

(10)

其中，H(Xi,Xj)≥T時(shí)取H(Xi,Xj)=1；否則，取H(Xi,Xj)=0，T為相似度閾值。

每個(gè)抗體激勵(lì)度由抗體和抗原之間的親和度與抗體濃度構(gòu)成，即

(11)

其中ε為常數(shù)(0≤ε≤1)。當(dāng)抗體的親和度越高時(shí)，抑制濃度高的抗體，這樣可以有效的保持抗體的多樣性。

3)選取親和度高的Nc個(gè)個(gè)體進(jìn)行克隆作為記憶庫，按照一定的概率對克隆的抗體進(jìn)行交叉和變異，用親和度高的變異抗體替代親和度低的克隆抗體，同時(shí)保留當(dāng)代種群中親和度最大的抗體并更新記憶庫，進(jìn)入到下一抗體群。

4)對種群進(jìn)行刷新，隨機(jī)產(chǎn)生N-Nc個(gè)抗體與記憶庫中的Nc個(gè)抗體形成新的種群。

5)判斷程序是否滿足終止條件，滿足則輸出結(jié)果，否則轉(zhuǎn)步驟2。

免疫遺傳算法在評價(jià)抗體優(yōu)秀程度時(shí)，常用抗體濃度控制的方法以保證物種多樣性和全局最優(yōu)解。對于電能計(jì)量器具配送網(wǎng)絡(luò)優(yōu)化問題，這些濃度控制方法的全局搜索能力較差，易因變異概率不合理而導(dǎo)致局部最優(yōu)，抗體經(jīng)過交叉變異后會產(chǎn)生大量的不可行解，且收斂速度較慢。為了解決這些問題，本文提出一種基于相似性矢量距改進(jìn)抗體濃度的免疫遺傳算法，將其應(yīng)用于優(yōu)化電能計(jì)量器具配送網(wǎng)絡(luò)中。

根據(jù)抗體間相似度對抗體進(jìn)行選擇，相似度可根據(jù)信息熵或歐式距離求出，進(jìn)而可得到基于相似性的抗體濃度函數(shù)：

(12)

式中H(Xi,Xj)為第i、j個(gè)抗體的相似度。

抗體矢量距是指該抗體與其他抗體間適應(yīng)度值差值的總和，計(jì)算公式如下：

(13)

根據(jù)抗體矢量距對抗體進(jìn)行選擇，可得到基于矢量距的抗體濃度函數(shù)：

D2(Xi)=1/[N·V(Xi)]

(14)

綜合考慮上述2種抗體選擇策略，可得到抗體濃度函數(shù)：

D(Xi)=αD1(Xi)+(1-α)D2(Xi)

(15)

式中α為常數(shù)調(diào)節(jié)因子(0≤α≤1)，α的取值需一個(gè)訓(xùn)練的過程。

基于相似性和矢量距的抗體濃度函數(shù)選擇低濃度、高適應(yīng)度抗體的同時(shí)，可以維持種群的多樣性，有效避免局部最優(yōu)現(xiàn)象，提高免疫遺傳算法的全局搜索能力。

1.3 目標(biāo)函數(shù)

在進(jìn)行電能計(jì)量器具配送網(wǎng)絡(luò)優(yōu)化時(shí)，需要獲取每個(gè)客戶的電能計(jì)量器具需求量，可通過建立預(yù)測模型的方式來計(jì)算得到。此外，計(jì)量中心和客戶點(diǎn)的位置信息也是必不可少的。然而，收集到的原始信息通常是經(jīng)緯度坐標(biāo)，不能直接用于建模和計(jì)算。高斯投影法可將橢球面的經(jīng)緯坐標(biāo)轉(zhuǎn)換為平面直角坐標(biāo)，為便于計(jì)算，再將平面直角坐標(biāo)進(jìn)行平移，使所有的點(diǎn)都落在第1象限內(nèi)。

對于電能計(jì)量器具配送網(wǎng)絡(luò)優(yōu)化問題，以電能計(jì)量器具的運(yùn)輸成本最小作為目標(biāo)，配送單價(jià)和運(yùn)輸費(fèi)用等數(shù)據(jù)為已知量，為了便于計(jì)算，假設(shè)客戶點(diǎn)之間的運(yùn)輸距離為2點(diǎn)間的直線距離。構(gòu)造配送網(wǎng)絡(luò)優(yōu)化的目標(biāo)函數(shù)：

(16)

(17)

s.t.xc0

(18)

yc0

(19)

(20)

式中j為待建配送中心，j=1,2,…,m；i為客戶點(diǎn),i= l,2,…,n；dij為配送中心j到客戶i的運(yùn)輸距離；(x0,y0)為計(jì)量中心的位置坐標(biāo)；d0j為計(jì)量中心到配送中心j的運(yùn)輸距離；(Xj,Yj)為待建配送中心的位置坐標(biāo)；cij為配送中心j到客戶i的運(yùn)輸單價(jià)；c0j為計(jì)量中心到配送中心j的整車運(yùn)輸單價(jià)；zij為決策變量,當(dāng)客戶點(diǎn)i由待建配送中心j配送貨物時(shí)取1,否則取0；(xc0,yc0)為配送區(qū)域的起始點(diǎn)坐標(biāo)；Di為客戶點(diǎn)需求量；(xc1,yc1)為配送區(qū)域的終止點(diǎn)坐標(biāo)；H為運(yùn)輸車輛的最大載量；(xi,yi)為客戶點(diǎn)位置坐標(biāo)。

本文的電能計(jì)量器具配送網(wǎng)絡(luò)優(yōu)化策略包括需求預(yù)測、配送中心選址、分配客戶點(diǎn)等，流程如圖1所示。

圖1 優(yōu)化策略流程Figure 1 Flow chart of optimization strategy

首先，輸入客戶的電能計(jì)量器具需求量和客戶的經(jīng)緯度坐標(biāo)，通過建立預(yù)測模型并計(jì)算預(yù)測結(jié)果誤差，若誤差不滿足限制條件，則通過黃金分割法重新計(jì)算a、b和γ，建立新的預(yù)測模型；若誤差滿足限制條件，則陸續(xù)計(jì)算出未來一年客戶計(jì)量器具月度需求量。然后，采用高斯投影法對用戶的經(jīng)緯度坐標(biāo)進(jìn)行處理，得到在第一象限的平面直角坐標(biāo)，同時(shí)輸入各個(gè)客戶點(diǎn)的計(jì)量器具需求量，將其代入配送中心選址優(yōu)化模型，采用改進(jìn)免疫遺傳算法進(jìn)行計(jì)算，進(jìn)化得到適應(yīng)度值最優(yōu)的物流配送方案。

2 實(shí)例分析

2.1 預(yù)測結(jié)果

為了驗(yàn)證Holt-Winters模型預(yù)測電能計(jì)量器具月度需求量的準(zhǔn)確性，本文選用2015—2017年某省網(wǎng)某品規(guī)單相電能表月度故障搶修需求量作為原始數(shù)據(jù)[14]。采用黃金分割法選取最優(yōu)平滑系數(shù)，然后利用Holt-Winters模型對2018年月度的電能表需求量進(jìn)行預(yù)測，并將預(yù)測值與實(shí)際值進(jìn)行比較。原始數(shù)據(jù)如表1所示，原始數(shù)據(jù)與Holt-Winters模型擬合結(jié)果的對比如圖2所示，可知擬合曲線與實(shí)際變化曲線重合，預(yù)測的變化趨勢和季節(jié)性符合實(shí)際變化規(guī)律，預(yù)測效果較好。

表1 原始數(shù)據(jù)Table 1 Raw data

圖2 Holt-Winters模型預(yù)測結(jié)果Figure 2 Prediction results of Holt-Winters model

2018年月度電能表需求量的實(shí)際值與預(yù)測值的對比如表2所示(預(yù)測誤差=|預(yù)測值-實(shí)際值|/實(shí)際值×100%)，可知預(yù)測效果較好。由于政策、市場、特殊氣候等實(shí)際因素對電能表需求量的影響較為復(fù)雜，少量的預(yù)測結(jié)果誤差較大難以避免，但預(yù)測結(jié)果與實(shí)際結(jié)果的變化趨勢性和季節(jié)性一致，驗(yàn)證了Holt-Winters模型用于電能計(jì)量器具需求預(yù)測的可行性。

表2 2018年月度電能表需求量的實(shí)際值與預(yù)測值Table 2 Actual value and predictive value of monthly power meter demand in 2018

2.2 配送方案

本文的電能計(jì)量器具配送網(wǎng)絡(luò)優(yōu)化策略將應(yīng)用于求解一個(gè)計(jì)量中心—配送中心—客戶的二級配送網(wǎng)絡(luò)實(shí)例，實(shí)例包括52個(gè)客戶點(diǎn)[15]和1個(gè)計(jì)量中心。利用高斯投影法可將用戶和計(jì)量中心的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為平面直角坐標(biāo)并進(jìn)行坐標(biāo)平移，利用Holt-Winters模型可預(yù)測未來1 a的電能表月度需求量，年度需求量由月度數(shù)據(jù)累加得到，最終結(jié)果如表3所示，其中計(jì)量中心坐標(biāo)為(0,0)。

由于不同用戶對電能表的需求量差異較大，本模型選取配送中心數(shù)量為5；假設(shè)計(jì)量中心到配送中心和配送中心到客戶的單位長度運(yùn)輸成本相同，本文取100；電能表從計(jì)量中心運(yùn)輸?shù)脚渌椭行牡倪\(yùn)輸方式為整車運(yùn)輸，從配送中心到客戶的運(yùn)輸方式為零擔(dān)運(yùn)輸，整車運(yùn)輸?shù)淖畲筝d量取400；將不同位置點(diǎn)之間的直線距離視為其運(yùn)輸距離。

基于改進(jìn)免疫遺傳算法的配送中心位置和配送網(wǎng)絡(luò)客戶分配方案如圖3所示，可以看出，客戶點(diǎn)大致分為5個(gè)區(qū)域，每個(gè)區(qū)域由一個(gè)配送中心承擔(dān)配送電能表的任務(wù)。配送中心靠近這些區(qū)域的中心，配送路線呈放射狀到達(dá)每個(gè)客戶。電能表配送方案如表4所示，表中粗體的客戶編號為所選的5個(gè)配送中心。由于不同客戶對電能表的需求存在較大差異，故不同配送中心的分配客戶數(shù)量也存在著較大差異。

表3 客戶點(diǎn)位置及電能表需求量Table 3 Customer location and power meter demand

圖3 電能表配送方案Figure 3 Distribution scheme of power meter

表4 配送網(wǎng)絡(luò)選址及客戶分配Table 4 Distribution network location and customer allocation

2.3 收斂性對比

對常規(guī)免疫遺傳和改進(jìn)免疫遺傳算法的收斂性進(jìn)行對比。免疫遺傳算法應(yīng)用于本文實(shí)例的收斂特性曲線如圖4所示，可以看出，基于相似性和矢量距改進(jìn)抗體濃度的免疫遺傳算法優(yōu)化速度明顯優(yōu)于常規(guī)免疫遺傳算法，進(jìn)化代數(shù)達(dá)到50代左右時(shí)獲得了該實(shí)例的最優(yōu)解，具有更好的收斂性。

圖4 收斂特性曲線Figure 4 Curve of convergence characteristic

在進(jìn)化過程中，改進(jìn)算法的最優(yōu)適應(yīng)度值和平均適應(yīng)度值均維持相對穩(wěn)定的下降趨勢逼近最優(yōu)解，而常規(guī)算法的平均適應(yīng)度曲線出現(xiàn)了顯著的振蕩現(xiàn)象，說明在抗體選擇過程中，改進(jìn)算法比常規(guī)算法能更準(zhǔn)確地保留低濃度、高適應(yīng)度值的抗體，在保證物種多樣性的同時(shí)，增大了優(yōu)秀抗體的選擇概率。

3 結(jié)語

1)客戶對電能計(jì)量器具的需求量隨時(shí)間變化的趨勢較為平穩(wěn)，但受季節(jié)影響十分顯著。Holt-Winters模型適用于預(yù)測該類型的時(shí)間序列數(shù)據(jù)；采用黃金分割法逐步搜索并縮小平滑系數(shù)的可行區(qū)間，能求解出最優(yōu)平滑系數(shù)的近似值,提高預(yù)測準(zhǔn)確性。

2)免疫遺傳算法能有效避免收斂于局部最優(yōu)解，本文提出基于相似性和矢量距的濃度函數(shù)改進(jìn)免疫遺傳算法，其收斂性優(yōu)于常規(guī)算法，能高效解決配送中心選址和客戶分配問題。