張志生 路 輝 劉 星

1(云南電網(wǎng)有限責(zé)任公司信息中心 云南 昆明 650021) 2(昆明能訊科技有限責(zé)任公司 云南 昆明 650021)

0 引 言

隨著電網(wǎng)業(yè)務(wù)量以及用電需求數(shù)量的增加，為保障供電質(zhì)量與供電安全，對負(fù)責(zé)電網(wǎng)數(shù)據(jù)采集與傳輸?shù)闹悄茈娋W(wǎng)穩(wěn)定性以及安全性提出了更高要求。為此，常通過在智能電網(wǎng)部分節(jié)點(diǎn)中部署探針[1]以實(shí)現(xiàn)對全部節(jié)點(diǎn)的實(shí)時(shí)監(jiān)測，以便及時(shí)對網(wǎng)絡(luò)中出現(xiàn)故障的節(jié)點(diǎn)處設(shè)備進(jìn)行及時(shí)修復(fù)或替換，從而保證智能電網(wǎng)穩(wěn)定且安全地運(yùn)行，達(dá)到供需平衡、安全用電的目的。在電網(wǎng)節(jié)點(diǎn)中所部署探針均通過向被監(jiān)測節(jié)點(diǎn)發(fā)送監(jiān)測數(shù)據(jù)信息包，并以該探針能否接收到來自該監(jiān)測節(jié)點(diǎn)返回的確認(rèn)信息為指標(biāo)，從而判定所監(jiān)測節(jié)點(diǎn)是否為故障節(jié)點(diǎn)。因此，如何以最少數(shù)量探針監(jiān)測電網(wǎng)中所有節(jié)點(diǎn)從而達(dá)到降低監(jiān)測成本并提升監(jiān)測效率的目的是需解決的首要問題。

1 問題模型

探針監(jiān)測數(shù)據(jù)包具體發(fā)送與接收過程如圖1所示。

圖1 故障監(jiān)測過程示意圖

圖1中，節(jié)點(diǎn)A1、A4、A5、A6均為探針部署節(jié)點(diǎn)，若A1通過路徑A1→A4→A7向A7發(fā)送監(jiān)測數(shù)據(jù)信息包，因路徑中A4已部署探針[2]，故可根據(jù)A1能否接收到確認(rèn)信息，判定A7是否出現(xiàn)故障。然而若A1通過路徑A1→A2→A5→A7對A7發(fā)送監(jiān)測數(shù)據(jù)信息包，因該路徑中A2未部署探針，故當(dāng)A1無法接收到確認(rèn)信息時(shí)，無法判定是A2還是A7出現(xiàn)故障，需縮短探針與被監(jiān)測節(jié)點(diǎn)間路徑。因此，為保證各探針及時(shí)準(zhǔn)確地定位故障節(jié)點(diǎn)，需使得各節(jié)點(diǎn)均至少存在一個(gè)與其直接相連的探針節(jié)點(diǎn)的同時(shí)，所部署探針數(shù)量最少，故可將該問題簡述為部署最少數(shù)量的探針覆蓋智能電網(wǎng)中所有的邊，即無向圖G=(V,E)(V為圖G中所有頂點(diǎn)的集合，E為所有邊的集合)中最小點(diǎn)覆蓋[3]的求解問題。

針對上述經(jīng)改進(jìn)蟻群算法在最小點(diǎn)覆蓋求解過程中存在的問題，本文提出一種基于禁忌搜索與擾動(dòng)策略的探針部署算法[5](Probe Deployment Algorithm Based on Taboo Search and Perturbation Strategy，PDA-TSPS)，該算法首先通過快速鄰域切換與禁忌表構(gòu)建降低智能電網(wǎng)中的頂點(diǎn)狀態(tài)更新時(shí)間，同時(shí)避免對頂點(diǎn)進(jìn)行重復(fù)計(jì)算，其次結(jié)合擾動(dòng)策略對局部最優(yōu)解中一定比例的關(guān)鍵節(jié)點(diǎn)進(jìn)行移除，以突破空間限制、擴(kuò)展集合求解范圍，使所求解最小點(diǎn)覆蓋結(jié)果達(dá)全局最優(yōu)。

2 經(jīng)改進(jìn)的蟻群算法

2.1 算法原理及步驟

通常將傳統(tǒng)蟻群算法進(jìn)行改進(jìn)設(shè)計(jì)出一種經(jīng)改進(jìn)的蟻群算法以實(shí)現(xiàn)對無向圖G=(V,E)中S集的求解，該算法首先對無向圖中各頂點(diǎn)以及邊賦予權(quán)值，構(gòu)建點(diǎn)邊賦權(quán)圖Gc=(V,Ec)，如圖2所示。

圖2 點(diǎn)邊賦權(quán)圖構(gòu)建過程示意圖

對上述點(diǎn)邊賦權(quán)圖Gc=(V,Ec)中原有各邊均賦權(quán)值1，對Gc中新構(gòu)建的各邊(Ec-E)均賦權(quán)值0，構(gòu)建連接函數(shù)ψk(i,j)，即：

(1)

假定選擇頂點(diǎn)a1為所求解最小點(diǎn)覆蓋集S1的初始頂點(diǎn)，則令與其關(guān)聯(lián)所有邊的連接函數(shù)值ψk(i,j)均歸0，然后計(jì)算a1的各相鄰頂點(diǎn)動(dòng)態(tài)啟發(fā)因子ηkj，并結(jié)合該因子確定最小點(diǎn)覆蓋集中的下一頂點(diǎn)，當(dāng)各相鄰頂點(diǎn)動(dòng)態(tài)啟發(fā)因子均為0時(shí)停止計(jì)算，動(dòng)態(tài)啟發(fā)因子ηkj的計(jì)算式為：

(2)

(3)

經(jīng)計(jì)算頂點(diǎn)a4，被選作下一頂點(diǎn)，令與頂點(diǎn)a4所有相關(guān)聯(lián)邊的連接函數(shù)值ψk(i,j)均歸0，并重復(fù)上述步驟，求解出下一頂點(diǎn)為a3，直至各相鄰頂點(diǎn)ηkj值均為0時(shí)停止算法，求解出最小點(diǎn)覆蓋集S1，并通過選擇不同初始頂點(diǎn)，重復(fù)上述步驟依次類推求解出最小點(diǎn)覆蓋集S2，S3，…，Sn(n為圖G中頂點(diǎn)數(shù))，在點(diǎn)覆蓋數(shù)最少的集合中，選擇點(diǎn)覆蓋權(quán)值和∑w(j)最小的集合作為最終所求最小點(diǎn)覆蓋集S，即：

S=Sj,∑w(j)=min∑w(j)

(4)

2.2 問題描述

問題1：由于在采用上述改進(jìn)蟻群算法進(jìn)行最小點(diǎn)覆蓋集求解過程中，可能會(huì)存在同一頂點(diǎn)被重復(fù)選作最小覆蓋集中的頂點(diǎn)，從而增加CPU計(jì)算的時(shí)間，降低探針部署效率，結(jié)合如圖3所示的點(diǎn)邊賦權(quán)圖，解釋具體計(jì)算冗余過程。

圖3 點(diǎn)邊賦權(quán)圖

結(jié)合上述經(jīng)改進(jìn)蟻群算法步驟對圖3中不同初始節(jié)點(diǎn)的最小點(diǎn)覆蓋集進(jìn)行計(jì)算，可得不同初始點(diǎn)下的最小點(diǎn)覆蓋集，即：

(5)

根據(jù)式(5)中各最小點(diǎn)覆蓋集計(jì)算結(jié)果可知：其中頂點(diǎn)a1、a3和a4均多次進(jìn)行過重復(fù)計(jì)算[6]，由此會(huì)造成計(jì)算冗余，增加CPU計(jì)算時(shí)間。

問題2：由于在結(jié)合上述經(jīng)改進(jìn)蟻群算法進(jìn)行各個(gè)覆蓋集的下一頂點(diǎn)計(jì)算過程中，若各相鄰頂點(diǎn)的動(dòng)態(tài)啟發(fā)因子ηkj值均為0，則停止計(jì)算，導(dǎo)致各最小點(diǎn)覆蓋集的運(yùn)算陷入一個(gè)局部區(qū)域的求解，從而使得計(jì)算結(jié)果無法同時(shí)兼顧局部最優(yōu)與全局最優(yōu)[7]，探針部署方案有待改進(jìn)。

3 算法設(shè)計(jì)

3.1 構(gòu)造點(diǎn)賦權(quán)圖與初始解

在本文所提基于禁忌搜索與擾動(dòng)策略的探針部署算法中，為求解最小點(diǎn)覆蓋集，首先在無向圖G=(V,E)中對各頂點(diǎn)賦予相應(yīng)權(quán)值(ω(vi)≥0)，構(gòu)建點(diǎn)賦權(quán)圖[8]G′=(V,E′)，如圖4所示。

圖4 點(diǎn)賦權(quán)圖

在構(gòu)建初始頂點(diǎn)集合V′的過程中，針對未被探針部署頂點(diǎn)集合V′覆蓋的邊，結(jié)合貪心算法選擇該邊中權(quán)值較小的頂點(diǎn)，加入頂點(diǎn)集V′中，以保證覆蓋所有邊的最小點(diǎn)覆蓋集V′中Wtotal值最小，即：

(6)

式中：Wtotal為所有頂點(diǎn)權(quán)值和，且滿足：

?(vi,vj)∈E′:vi∈V′or,vi∈V′(1≤i,j≤n,V′∈V)

(7)

如圖4所示，邊(v11、v16)未被頂點(diǎn)集V′覆蓋，為保證頂點(diǎn)集合V′中所有頂點(diǎn)的權(quán)值和Wtotal最小，故選擇權(quán)值較小的頂點(diǎn)v16加入頂點(diǎn)集V′中，并且定義集合V′中頂點(diǎn)為關(guān)鍵頂點(diǎn)，不在集合中頂點(diǎn)為非關(guān)鍵頂點(diǎn)，頂點(diǎn)集合V中任意一點(diǎn)可在關(guān)鍵頂點(diǎn)[9]與非關(guān)鍵頂點(diǎn)兩種狀態(tài)間切換。

3.2 快速鄰域切換與禁忌表構(gòu)建

通過鄰域動(dòng)作MV(vi)將初始解頂點(diǎn)集合V′進(jìn)行有效解變換，以增強(qiáng)局部最優(yōu)解[10]尋優(yōu)能力，即：將上述初始解頂點(diǎn)集合V′中關(guān)鍵頂點(diǎn)vi切換為非關(guān)鍵頂點(diǎn)，并將頂點(diǎn)vi鄰近節(jié)點(diǎn)中屬于集合Vr(vi)的頂點(diǎn)全部切換為關(guān)鍵頂點(diǎn)，具體過程如圖5所示。

圖5 鄰域動(dòng)作過程示意圖

由于進(jìn)行鄰域動(dòng)作MV(B)將集合V′中頂點(diǎn)B移除，導(dǎo)致邊(B,C)、(B,D)、(B,F)中均無關(guān)鍵頂點(diǎn)，為保證集合V′的合法性，將頂點(diǎn)C、D、F加入集合V′中，由此產(chǎn)生圖5中右圖所示經(jīng)鄰域變換的合法解。

執(zhí)行一個(gè)上述鄰域動(dòng)作會(huì)引起相鄰頂點(diǎn)狀態(tài)變化，形成多個(gè)鄰域解[11]，但由于該過程中只有部分關(guān)鍵頂點(diǎn)的權(quán)值ω(vi)發(fā)生變化，因此，為避免在鄰域解的選擇過程中，對集合中所有頂點(diǎn)的權(quán)值進(jìn)行全面計(jì)算從而增加無效計(jì)算時(shí)間，本文所提基于禁忌搜索與擾動(dòng)策略的探針部署算法通過引入評估函數(shù)EV(vi)，計(jì)算各鄰域動(dòng)作的增量目標(biāo)函數(shù)值[12]，進(jìn)行快速鄰域切換以降低無效計(jì)算時(shí)間，評估函數(shù)EV(vi)計(jì)算如下：

(8)

結(jié)合圖6中鄰域動(dòng)作MV(A)為例進(jìn)行各相鄰頂點(diǎn)EV(vi)值的計(jì)算，如圖6所示。

圖6 鄰域動(dòng)作示意圖

在上述應(yīng)用鄰域動(dòng)作對始解頂點(diǎn)集合V′進(jìn)行優(yōu)化的過程中，為防止在局部區(qū)域中陷入循環(huán)搜索，可結(jié)合禁忌搜索構(gòu)建禁忌表對重復(fù)的鄰域動(dòng)作進(jìn)行限制，以避免鄰域動(dòng)作陷入循環(huán)搜索，使用禁忌搜索具體方法如下：

(9)

當(dāng)鄰域動(dòng)作MV(u)中涉及的關(guān)鍵頂點(diǎn)u與相鄰非關(guān)鍵頂點(diǎn)集Vr(u)中頂點(diǎn)同時(shí)滿足式⑼中條件時(shí)，則禁忌該鄰域動(dòng)作，否則予以執(zhí)行。

3.3 應(yīng)用擾動(dòng)策略突破空間限制

圖7 PDA-TSPS流程

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

4.1 評價(jià)指標(biāo)

為充分比較改進(jìn)的蟻群算法(IACA)與本文所提基于禁忌搜索與擾動(dòng)策略的探針部署算法(PDA-TSPS)的求解效率與最小點(diǎn)覆蓋集尋優(yōu)能力，測試實(shí)驗(yàn)中采用不同迭代次數(shù)下兩種算法的平均CPU計(jì)算時(shí)間(以秒為單位)以及不同規(guī)模算例集下兩種算法各類解(better、equal和worse)在所有解集中所占的比例作為IACA與PDA-TSPS求解效率與尋優(yōu)能力的評價(jià)指標(biāo)。

4.2 測試環(huán)境及參數(shù)設(shè)置

測試環(huán)境：本文采用C語言進(jìn)行測試實(shí)驗(yàn)編寫，PC機(jī)配置為：CPU型號(hào)為AMD A6- 3400M，64位處理器，CPU主頻為1.40 GHz，內(nèi)存為8 GB。

參數(shù)設(shè)置：首先設(shè)置各種規(guī)模算例集測試場景(即所含頂點(diǎn)與邊的數(shù)量不同的帶權(quán)無向圖G=(V,E))，假定一個(gè)測試算例集中頂點(diǎn)數(shù)量為n，邊的數(shù)量為m；其次，根據(jù)頂點(diǎn)與邊的數(shù)量不同將測試場景分為：小規(guī)模測試算例集(SPI)(n=500,m=500)、中等規(guī)模算例集(MPI)(n=1 000,m=1 000)、大規(guī)模算例集(LPI)(n=1 000,m=2 000)；最后，為保證實(shí)驗(yàn)結(jié)果有效驗(yàn)證IACA與PDA-TSPS的求解效率與尋有能力并降低計(jì)算冗余，故只在中等規(guī)模算例集(MPI)與大規(guī)模算例集(LPI)兩類測試場景下對比兩種算法的各類解比例與CPU計(jì)算時(shí)間，各類解中better類解集代表所有解集中高于平均值的最優(yōu)解，equal類解集代表所有解集中處于平均值水平的中等解，worse類解集代表所有解集中低于平均值水平的較差解。

4.3 實(shí)驗(yàn)結(jié)果對比分析

首先分別在中等規(guī)模算例集(MPI)與大規(guī)模算例集(LPI)場景下測試IACA與PDA-TSPS，并分別統(tǒng)計(jì)兩種場景下算法的CPU計(jì)算時(shí)間，統(tǒng)計(jì)情況如圖8所示。

圖8 算法CPU計(jì)算時(shí)間統(tǒng)計(jì)情況

根據(jù)圖8中算法測試的CPU計(jì)算時(shí)間統(tǒng)計(jì)結(jié)果分析得出：本文所提基于禁忌搜索與擾動(dòng)策略的探針部署算法(PDA-TSPS)相較于改進(jìn)的蟻群算法(IACA)，其CPU計(jì)算時(shí)間明顯較低，計(jì)算效率更高；在大規(guī)模算例集(LPI)場景下，PDA-TSPS算法對計(jì)算效率的提升更為明顯，故本文PDA-TSPS算法普遍適用。

為充分體現(xiàn)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果中各類解集合的有效性及合理性，將中等規(guī)模算例集(MPI)與大規(guī)模算例集(LPI)場景下的各個(gè)算例最大測試時(shí)間均設(shè)定為600 s(提升兩類算法在設(shè)定時(shí)限內(nèi)找到最優(yōu)解的概率)，中等規(guī)模算例集(MPI)由40個(gè)中等規(guī)模算例組成，大規(guī)模算例集(LPI)由15個(gè)(由于各個(gè)大規(guī)模算例計(jì)算復(fù)雜度較高，故集合中算例個(gè)數(shù)不宜設(shè)置過大)大規(guī)模算例組成，各個(gè)算例均在同一規(guī)模類別初始條件(n、m數(shù)值)下隨機(jī)生成；為降低算法迭代過程中帶來的誤差，各類規(guī)模算例集中每個(gè)算例均對應(yīng)10個(gè)問題實(shí)例，后續(xù)統(tǒng)計(jì)結(jié)果中每個(gè)算例所得解均為所對應(yīng)10個(gè)問題實(shí)例所得函數(shù)值的平均值。

其次，分別統(tǒng)計(jì)在中等規(guī)模算例集(MPI)場景下，IACA與PDA-TSPS各類解集(better、equal和worse)在所有解集中所占的比例，統(tǒng)計(jì)結(jié)果如圖9所示。

圖9 MPI場景下各類解集占比統(tǒng)計(jì)情況

由圖9的統(tǒng)計(jì)結(jié)果可知，在中等規(guī)模算例集(MPI)下，PDA-TSPS相較IACA其better類解集所占比例較高，worse類解集占比較低。與此同時(shí)，分別統(tǒng)計(jì)在大規(guī)模算例集(LPI)場景下，IACA與PDA-TSPS各類解集(better、equal和worse)在所有解集中所占的比例，統(tǒng)計(jì)結(jié)果如圖10所示。

圖10 LPI場景下各類解集占比統(tǒng)計(jì)情況

根據(jù)圖10的統(tǒng)計(jì)結(jié)果可知，在大規(guī)模算例集(LPI)場景下，PDA-TSPS相較IACA其better類解集所占比例較高，且所有解集合中worse類解集占比為0。

5 結(jié) 語

本文提出一種基于禁忌搜索與擾動(dòng)策略的探針部署算法，通過快速鄰域動(dòng)作切換、禁忌表構(gòu)建以及擾動(dòng)策略強(qiáng)化了算法在局部區(qū)域中的求解能力，降低了計(jì)算時(shí)間，突破了空間限制，使所得最小點(diǎn)覆蓋集合同時(shí)達(dá)到局部最優(yōu)與全局最優(yōu)。實(shí)驗(yàn)結(jié)果表明：本文基于禁忌搜索與擾動(dòng)策略的探針部署算法相較于改進(jìn)的蟻群算法，其求解最優(yōu)解速率更快，適用場景更廣，尋優(yōu)方法更為合理。