基于禁忌搜索與擾動策略的探針部署算法

張志生 路 輝 劉 星

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

0 引 言

隨著電網業務量以及用電需求數量的增加，為保障供電質量與供電安全，對負責電網數據采集與傳輸的智能電網穩定性以及安全性提出了更高要求。為此，常通過在智能電網部分節點中部署探針[1]以實現對全部節點的實時監測，以便及時對網絡中出現故障的節點處設備進行及時修復或替換，從而保證智能電網穩定且安全地運行，達到供需平衡、安全用電的目的。在電網節點中所部署探針均通過向被監測節點發送監測數據信息包，并以該探針能否接收到來自該監測節點返回的確認信息為指標，從而判定所監測節點是否為故障節點。因此，如何以最少數量探針監測電網中所有節點從而達到降低監測成本并提升監測效率的目的是需解決的首要問題。

1 問題模型

探針監測數據包具體發送與接收過程如圖1所示。

圖1 故障監測過程示意圖

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

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

2 經改進的蟻群算法

2.1 算法原理及步驟

通常將傳統蟻群算法進行改進設計出一種經改進的蟻群算法以實現對無向圖G=(V,E)中S集的求解，該算法首先對無向圖中各頂點以及邊賦予權值，構建點邊賦權圖Gc=(V,Ec)，如圖2所示。

圖2 點邊賦權圖構建過程示意圖

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

(1)

假定選擇頂點a1為所求解最小點覆蓋集S1的初始頂點，則令與其關聯所有邊的連接函數值ψk(i,j)均歸0，然后計算a1的各相鄰頂點動態啟發因子ηkj，并結合該因子確定最小點覆蓋集中的下一頂點，當各相鄰頂點動態啟發因子均為0時停止計算，動態啟發因子ηkj的計算式為：

(2)

(3)

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

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

(4)

2.2 問題描述

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

圖3 點邊賦權圖

結合上述經改進蟻群算法步驟對圖3中不同初始節點的最小點覆蓋集進行計算，可得不同初始點下的最小點覆蓋集，即：

(5)

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

問題2：由于在結合上述經改進蟻群算法進行各個覆蓋集的下一頂點計算過程中，若各相鄰頂點的動態啟發因子ηkj值均為0，則停止計算，導致各最小點覆蓋集的運算陷入一個局部區域的求解，從而使得計算結果無法同時兼顧局部最優與全局最優[7]，探針部署方案有待改進。

3 算法設計

3.1 構造點賦權圖與初始解

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

圖4 點賦權圖

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

(6)

式中：Wtotal為所有頂點權值和，且滿足：

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

(7)

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

3.2 快速鄰域切換與禁忌表構建

通過鄰域動作MV(vi)將初始解頂點集合V′進行有效解變換，以增強局部最優解[10]尋優能力，即：將上述初始解頂點集合V′中關鍵頂點vi切換為非關鍵頂點，并將頂點vi鄰近節點中屬于集合Vr(vi)的頂點全部切換為關鍵頂點，具體過程如圖5所示。

圖5 鄰域動作過程示意圖

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

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

(8)

結合圖6中鄰域動作MV(A)為例進行各相鄰頂點EV(vi)值的計算，如圖6所示。

圖6 鄰域動作示意圖

在上述應用鄰域動作對始解頂點集合V′進行優化的過程中，為防止在局部區域中陷入循環搜索，可結合禁忌搜索構建禁忌表對重復的鄰域動作進行限制，以避免鄰域動作陷入循環搜索，使用禁忌搜索具體方法如下：

(9)

當鄰域動作MV(u)中涉及的關鍵頂點u與相鄰非關鍵頂點集Vr(u)中頂點同時滿足式⑼中條件時，則禁忌該鄰域動作，否則予以執行。

3.3 應用擾動策略突破空間限制

圖7 PDA-TSPS流程

4 實驗與結果分析

4.1 評價指標

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

4.2 測試環境及參數設置

測試環境：本文采用C語言進行測試實驗編寫，PC機配置為：CPU型號為AMD A6- 3400M，64位處理器，CPU主頻為1.40 GHz，內存為8 GB。

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

4.3 實驗結果對比分析

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

圖8 算法CPU計算時間統計情況

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

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

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

圖9 MPI場景下各類解集占比統計情況

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

圖10 LPI場景下各類解集占比統計情況

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

5 結 語

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