電力數據網探針部署算法的優化改進研究

張志生

（云南電網有限責任公司信息中心，云南 昆明 650200）

0 前言

現行的電力信息系統更多將關注點集中于系統整體可用性、設備運行狀況和整體性能等方面，系統無法實現主動測量，無法主動發現運行過程中可能出現的各類狀態問題。這種情況的存在導致電力系統的整體運行并不穩定，系統在運行過程中經常會出現系統延時以及其他故障問題，此類問題出現的主要原因是系統運行中缺少必要的主動探測技術，另一方面，從業務系統的使用角度看，監控對象和監控內容不足，不能有效的評判電力信息系統的實際使用情況。在電力系統中部署探針后，系統探針可以主動獲取運行狀態信息，實現系統各項業務的快速監控和有效故障定位，通過采集系統應用數據，實現有效定位，對電力信息系統的穩定運行及實用化應用意義重大。

在互聯網信息技術的發展下，我國電力系統實現了自動化與信息化發展。我國電力數據網在規劃上有著較高的一致性，系統在建設及后期應用過程中始終堅持保障性、安全性、先進性、經濟性的基本原則內容[1]。電力數據網中常見的結構形式有星型、環形以及雙星型結構[2]。電力數據網為了處理電力系統中龐大的業務工作具備了網絡范圍大、網絡覆蓋廣、業務多樣化的基本特性。其在一些特殊性的業務工作中有著更高的要求標準，此類工作主要為電力系統中的網絡性能測量工作、拓撲結構測量工作、服務質量測量工作、多協議標簽交換工作（QoS）及VPN通道測量工作等[3]。

電力數據網探針部署問題主要集中在多目標多約束優化上，技術的應用需要全面分析技術的實際價值、部署成本以及系統后期可靠性等[4]。針對此類問題我國學者進行了綜合性的研究。文獻[5]為了解決系統的不確定與不穩定問題，應用貪心策略，經過仿真驗證發現系統的穩定性有所提高并得到了一定優化，但在運行中仍然會出現冗余解的情況。文獻[6-7]在研究過程中運用遺傳算法有效消除了無效解問題，但由于研究中忽略了可靠性及探針部署成本等主要因素，導致結果中出現了冗余解情況，探針數目仍無法實現最小化處理。本次研究中基于上述研究內容，運用貪心策略和遺傳算法思想改進探針部署算法。

1 探針部署優化問題建模分析

隨著電網智能化與自動化水平的提高，憑借工作經驗以及部分內容進行推斷部署的方式已儼然無法適應當前探針部署工作基本要求。本次研究中將電力數據網線路與業務進行有機結合，以此轉變為數學模型，實現電力業務的抽象化與簡便化。無向圖的最小頂點覆蓋問題為探針部署中的核心問題，研究中設定無向圖G=(V,E)，其中頂點的集合表示為V，邊集合表示為E。如果頂點覆蓋中存在集合S使得G中的各個邊與之關聯，即在所有G中的E都至少有一個在頂點S中。此時則成S集合為圖G的一個頂點覆蓋。如果存在某一個S為G的一個頂點覆蓋并且不存在其他包含更少頂點的集合可以覆蓋全圖，則稱S為圖G的一個最小頂點覆蓋[8]。

圖1所示的無向圖中包含8個頂點與10條邊。圖中的頂點集合為S=(2,4,6,8)，從圖中可以明顯看出每條邊都至少有一個頂點處于S中，因為其中并未存在其他集合可以包含更少的頂點覆蓋全圖，由此確定S為是其頂點覆蓋，并且S是其最小頂點覆蓋。

2 電力數據網探針部署優化

2.1 改進貪心算法的基本原理

本次研究中從無向圖最小頂點覆蓋角度出發，研究電力數據網中探針部署優化問題。由于傳統貪心算法策略中存在著節點隨機選取的情況，因此無法有效解決最小頂點覆蓋的問題，并且電力數據網中存在著多種拓撲結構類型，應用傳統貪心算法策略很可能會出現覆蓋頂點過多和冗余節點的問題。基于上述問題，結合電力數據網拓撲結構類型，在無靠性約束條件下提出一種改進貪心算法策略，以實現無向圖中限定覆蓋頂點方向選取，消除矩陣中的冗余節點[9]。

根據上文所述，可以將電力數據網中的探針部署問題轉化為無向圖最小頂點覆蓋問題，本次研究中提出無可靠性條件下的電力數據網探針部署的數據模型：

求得：

滿足：

式中，S表示頂點覆蓋集合，D表示探針部署的開銷，其中xi∈S,x=[x1,x2,x3,...,xn]為v=|V|的向量，A=(aij)n×n是圖的鄰接矩陣。

其中：

電力數據網的網絡結構包含核心層、匯聚層、接入層。在電力數據網拓撲結構抽象化分析中，各個層級節點都是相互獨立的，三層結構中形成了獨立的節點集合[10]。電力數據網中核心層的分布結構為網狀結構，如圖2所示。而匯聚層與接入層中的節點呈現出二分圖分布特征，如圖3所示。

圖2 網狀圖結構形態

圖3 二分圖結構形態

在傳統貪心策略中通常選取度數最大的節點來解決最小頂點覆蓋的問題。此方法下可以實現最佳覆蓋定選取工作，但同樣會造成全局性問題。

上圖中所應用的貪心策略可以實現每次最大度數節點的多種選擇。由于選擇是隨機進行的，因此選擇結果存在最壞情形，如果在隨機選擇中所選取節點為{11,12,13,14,15,16,17,18,31,32,33,34,35,36}時，圖中的覆蓋頂點共計有14個。如果隨機選取節點為{21,22,23,24,25,26}，則說明覆蓋頂點結果最佳，此時覆蓋頂點數量為6個。此時所出現的情況為隨機選取性所帶來的頂點過多問題。而在核心層的網狀結構中，可實現選取度數最大節點，首次選擇必然會選取節點1，而在第二次選擇中便增加了一定的隨機性[11]。如果在網狀圖中首次與后續隨機選取的節點為{1,2,3,4,5}時，可以得到網狀圖的頂點覆蓋集合。在該類型選取中，若將首次選取結果的頂點1去除，剩余頂點仍然可以覆蓋全圖，則網狀圖中的頂點1可以被看作一個冗余節點。這種情況的出現就是覆蓋頂點選取中的冗余節點問題。

通過分析了解到，在電力數據網探針部署問題中借助傳統貪心算法策略，仍然會存在探針部署數量確定困難、數量開銷成本增加的問題。此問題主要是由于網絡拓撲結構特征所造成的。

根據電力數據網中現存問題，本次研究選擇網絡拓撲結構特征為入手點分析，根據二分圖和網狀圖的特征弊端進行改進說明。

為了解決二分圖節點選取中所出現的最壞情況，確定了如下改進方法：每次刪除最大度數頂點的相關邊時，應同時去除度數為1節點的影響。在算法運行中對選取最大度數頂點進行了改進變化，其中規定在選取中如果出現相同情況則需優先選取存在度為1鄰接點的節點，以此最大限度上減少度為1節點所產生的影響。

網狀圖在節點選擇過程中存在冗余節點問題，在解決此問題上選擇采用標記矩陣形式，迅速確定冗余節點[12]。在改進算法通過生成標記矩陣分析記錄頂點覆蓋集是否存在均被重復覆蓋的頂點，以此最終確定冗余節點。

2.2 改進貪心算法策略流程內容

電力數據網探針部署應用改進貪心算法策略方法步驟如下所示：

第一步：初始化階段。確定無向圖的鄰接矩陣A與完全相同標記矩陣B，確定其頂點覆蓋集為S。

第二步：如果鄰接矩陣A為0，直接執行第三步，否則執行第三步。

第三步：選擇矩陣中度數最大的節點，如果最大節點唯一存在，直接將其歸屬于頂點覆蓋集合S中，記錄頂點標號i，并執行第五步，否則執行第四步。

第四步：確定度數最大的節點組中是否存在度為1的鄰接點，如果存在將其加入到覆蓋頂點集S中，記錄頂點標號為i，并繼續執行第五步，否則隨機選擇其中一個節點加入到集S中，記錄頂點標號為i，并繼續執行第五步。

第五步：去除節點i的相關邊，將鄰接矩陣中第i行與第i列全部重置為0，并執行第六步。

第六步：標記矩陣B中的第i行與第i列中每個元素減去原來鄰接矩陣相同位置所對應的元素，并執行第二步。

第七步：無向圖的原鄰接矩陣與標記矩陣相加，確定行（列）情況，如果結果不存在行（列）全部為0，則算法結束，此S即為結果。否則將全為0的行（列）號進行記錄，此為冗余節點標號，將其從S中刪除，算法結束，刪除冗余節點后的集S即為結果。

圖4 改進貪心算法策略流程內容

2.3 仿真實驗

基于改進貪心算法策略的探針部署效果需要通過仿真實驗進行驗證分析。驗證中使用GT-ITM拓撲生成器，生成器可以根據兩點間存在的概率來隨機生成平面拓撲圖，平面拓撲圖的機電數量不同，其復雜程度也存在差異[13]。本次仿真實驗中生成Waxman2模型，仿真實驗模型中的頂點間存在邊的概率為：

上式中a,b∈(0,1)，且圖中的邊數會隨著a的變化而改變，二者存在顯著的正比例關系，而圖中的長短邊比值會也與b之間存在著正比例關系。

本次仿真實驗中分別選取a=0.3，b=0.4和a=0.4，b=0.3進行分析，在不同復雜程度下的拓撲圖中分別應用傳統貪心算法策略（TGS）與改進貪心算法策略（IGA）分析無向圖的最小頂點覆蓋問題，其結果如圖5、圖6所示。由圖可知，在不同復雜程度、規模下改進貪心算法與傳統貪心算法相較仍具有明顯的優勢，在拓撲圖上解決最小頂點覆蓋問題上效果比較明顯。

圖5 a=0.3，b=0.4

圖6 a=0.4，b=0.3

3 混合遺傳算法的探針部署

3.1 混合遺傳算法的基本原理

基于抽象條件與可靠性因素建立數學模型，本次研究中所提到的可靠性體現于主動探測的可靠性與重合率上[14]。

電力數據網中的主動探測可靠性即為探針可靠性，其主要為系統探針工作時間與系統站點應用時間比值。探針可靠性通常情況下維持在80%～90%。

可靠性由以此對系統網絡探測所包含探針可靠性乘積表示為：

上式中，r為以此對系統網絡探測中所包含的探針集，φ為閾值。

在頂點覆蓋問題中，重合覆蓋率是探測可靠性的重要保證，覆蓋的重合率為探針探測中被多次探測的節點數據與被探測總數目之間的比值[15]。通過計算重合率情況可以判斷探針部署是否緊密。若重合率越高表明探針部署越緊密。此情況下如果探針出現問題無法使用，系統網絡仍然可以實現完全探測，并同時兼具一定的探測效率。重合率雖然對探測效率意義重大，但與探針部署開銷之間卻存在著顯著負相關關系，此項關系也是日后改進的一個重要方向。

重合覆蓋率公式為：

上式中，N為被探測節點的總數，C為能夠被多次探測的節點數目。由此可以得到可靠性與重合覆蓋率相結合的綜合可靠性計算方法：

公式為：

上式中的λ1，λ2分別表示探測可靠性與重合覆蓋率所占權重，二者的和為1。

研究中同樣給出了探針開銷函數。電力數據網的探針部署工作并不是一項簡單的一次性工作，此項工作完成后需要完成后期的運營管理與長期維護工作。這兩部分也是電力數據網探針開銷的主要構成，本次研究的開銷函數為：

上式中，xi為遺傳算法中染色體的位數，其中i只能為1或0，代表節中是否部署了探針，v代表染色體基因位數，是無向圖節點數目。由此確定電力數據網探針部署數學模型如下：

電力數據網探針部署數學模型滿足：

由上述部署數學模型可知，探針部署模型可以覆蓋全圖，且確定的模型具有較高的可靠性。此條件下需要實現無向圖的有效聯通，實現部署開銷函數的最小化，完成函數最小求解。

本次研究中在傳統混合遺傳算法探針部署數學模型基礎上，進行了優化改進。研究中在傳統算法的選擇算子中加入了可靠性約束參數條件，完成輪賭選擇的重新設計，其選擇部署個體的概率函數如下：

通過上式可以實現個體可靠性與個體適應性的有效結合，整體中可靠性越高的個體被選擇的幾率會明顯提高，則更有利于部署整體朝著高度可靠性方向發展。

在遺傳算法改進中，根據部署情況重新設置了變異概率。通過優化變異概率可以有效減低模擬自然環境下受偶然原因出現的基因突變問題，并且算法的整體性也會有所提升。在遺傳算法模型中，變異算子主要承擔了算法全局搜索功能的作用，算法可以在變異算子的引導下搜索到模型中的每個個體單位[16]。在模型應用中，變異算子會將個體中某一基因位xi以概率p(xi)取反。模型應用中每個基因被取反的概率是完全相同的。在電力數據網部署探針過程中，外層的作用會低于內層的作用，因此便更利于確定無向圖的最小頂點覆蓋。改進遺傳算法中設定了不同的取反率：

上式中，下標表示基因位數，上標表示節點類型。

其中的個體變異表示為：

完成算法修正后，需要借助標記矩陣輔助消除冗余節點，提高改進遺傳算法的收斂速度。

3.2 混合遺傳算法的算法流程

本次應用改進遺傳算法解決最小頂點覆蓋問題時，充分考慮到了傳統遺傳算法的弊端，在初始種群中，以及正常的選擇、交叉、變異操作過程中都會出現不可行解的問題，此時應用傳統遺傳算法則無法實現全圖解的有效覆蓋，所確定的解也將直接影響遺傳算法的收斂速度和結果準確性。

基于傳統遺傳算法的應用情況，本次研究對此問題進行優化處理，提出修正算法，其算法流程步驟如下：

第一步：如果所求解合法，停止。

第二步：依據鄰接矩陣A與染色體x，對染色體中的基因進行掃描，設定鄰接矩陣A中與x為1位相關的邊為0。

第三步：將A中存在為1的邊相關頂點直接加入到染色體x中，并設置為1，完成修正。

第四步：完成初始群體中染色體處理后，停止，否則返回第二步。

上述修正算法，促進了傳統遺傳算法的應用進度，但在應用中仍存在一定不足，修正算法在應用中僅將其中的個體進行合法化，而忽略了冗余節點的問題。在此條件下，本次研究中提出了基于混合遺傳算法的探針部署方法，其算法流程如下所示：

第一步：依據電力數據網探針部署的基本情況，確定探針部署中探測可靠性、部署和成本參數。選用初始解集完成網絡部署工作，并將其作為遺傳算法的種群P(t)，確定為第一代解，規模為S。

第二步：以是否部署探針為判斷依據，確定編碼1,0，保證其中每個解都是一組二進制數。

第三步：運用適應度函數評價解集，在合法性與可靠性條件滿足下，確定目標函數所對應的適應度函數值。

第四步：如果滿足條件，輸出最優解，終止算法。

第五步：集合選擇算子、交叉算子和變異算子，進化得出下一代解集P(t+1)。

第六步：運用修正算法修正不合法解，提升算法加速進程。

第七步：運用消除算法消除局部不足，實現局部最優與全局最優。

第八步：從第三步開始評價局部改進解集。

圖7 混合遺傳算法流程圖

3.3 仿真實驗

本次研究中通過數據網絡拓撲模型檢驗改進后的混合遺傳算法在電力數據網探針部署中的實際效果。檢驗中所應用的數據拓撲網中由160個節點和190條鏈路組成。

仿真實驗中電力數據網中所使用的探針品牌及各項成本具有較高一致性，因此可以通過探針部署的實際數目確定部署的實際開銷成本。本次所選用數據網拓撲結構中的鄰接矩陣長寬相等均為160，其中所共計包含160位基因數。仿真實驗中設置初代種群規模為64，接入層、匯聚層與核心層的基因異變率分別為：1%、2%和3%。其中的最大進化代數為100。仿真實驗中探測可靠性、重合覆蓋率可靠性的比重分別為：,λ1=0.4，λ2=0.6，二者的閾分別為：φ=0.8，θ=0.9。實驗中可靠性指標隨進化代數變化情況如圖8所示。

圖8 可靠性隨進化代數變化情況

實驗中探針部署開銷成本歲進化代數變化情況如圖9所示。

圖9 探針部署隨開銷成本進化代數變化情況

由上圖可知，在可靠性條件下，應用混合型遺傳算法求解可以實現最低開銷，探針部署中數目越多可靠性越高，但部署的開銷成本會明顯增加。仿真實驗中，在假定探測可靠性與重合覆蓋可靠性指標保持不變情況下，將探測可靠性提升到0.85、整體可靠性閾值提升到0.95。不同閾值 下的適應度對比情況如圖10所示。

圖10 不同閾值條件下適應度變化情況

從上圖變化情況可以看出，在可靠性水平提升下，目標函數隨之變大，此時的適應度逐漸下降。為了提高電力數據網的可靠性水平需要提高探針部署數量，與此同時，也需要注意到隨數量增加而出現的開銷成本增加問題。

應用傳統遺傳算法和改進混合遺傳算法對閾值在0.8～0.9范圍內的拓撲進行求解分析，其結果如表1所示。

表1 傳統遺傳算法與混合遺傳算法對比

由表1可知，在可靠性條件下，混合型遺傳算法在探針部署中效果更佳，與傳統遺傳算法相比有著更快的收斂速度。

4 結束語

信息業務系統在智能電網建設中發揮了關鍵性作用，本文從系統探針部署問題入手，以提高探測覆蓋率及可靠性研究的主要方向。研究中通過算法改進實現了系統探針部署的優化。文中通過抽象化思維通過研究最小頂點覆蓋問題分析探針部署優化問題[17]。此問題解決中以電力信息系統實際情況為依據建立探針部署數學模型，結合貪心算法提出了改進貪心算法策略，以遺傳算法為基礎提出了混合遺傳算法，并通過仿真實驗驗證確定了兩種算法模型均具有較好的可行性及收斂性。算法改進工作對系統探針部署優化子系統的建設意義重大。