基于自組織映射網(wǎng)絡(luò)的電力最短巡檢路徑問題求解

倪 俊，李 鋒，趙 芳，韓明沖，鐘建偉

（1.國網(wǎng)湖北省電力有限公司恩施供電公司，湖北 恩施 445000；2. 湖北民族大學 信息工程學院，湖北 恩施 445000）

0 引 言

伴隨著我國經(jīng)濟的快速增長，社會各方面的發(fā)展對于電力供應(yīng)的可靠性提出了更高的要求。電力系統(tǒng)運行過程中，需要對其線路上的各種電力設(shè)備進行定期巡檢，以保證電力系統(tǒng)運行的可靠性。在以往進行電力巡檢時，普遍采用人工巡檢的方式，但隨著人們對于電力供應(yīng)方面需求的提升，巡視效率就急需進一步提升，同時還應(yīng)盡可能降低進行相關(guān)工作時的成本。從全局優(yōu)化的角度出發(fā)，對輸電網(wǎng)絡(luò)中的最優(yōu)化巡檢方案進行分析，并通過有效的巡檢方案的制定提升電力資源的配置能力。電力巡檢可分為常規(guī)巡檢、臨時巡檢以及保障巡檢三方面。其中常規(guī)巡檢主要是管理人員通過獲取方案的第一手資料，進而對其線路中的變電站、架空線、電桿以及桿上的設(shè)備進行整體性巡查。在此過程中需要配備專業(yè)人員對其路徑的選擇進行合理的規(guī)劃，但在進行巡檢車輛的調(diào)遣過程中需要充分依靠巡檢人員的工作經(jīng)驗，故此工作的開展具有較大的主觀性?，F(xiàn)階段，為了能進一步提升電力巡檢效率，需要集合電力巡檢實際業(yè)務(wù)特征對其進行抽象化分析；并結(jié)合當?shù)貙嶋H線路巡檢需求，得出相應(yīng)最優(yōu)化電力線路的巡檢路線。而巡檢的最短路徑問題可以簡單看作旅行商問題（Travelling Salesman Problem, TSP）。TSP可被簡單描述為已知某一地區(qū)上的地點以及各點之間的距離，求出遍歷所給地點的最短路徑。雖然該問題描述起來很容易，但它是一個NP完全問題。地點數(shù)目越多，求解難度越大，并且這類問題沒有通用解法。由于現(xiàn)在基本很難驗證當?shù)攸c數(shù)量過多時模型求得的解是否最優(yōu)，所以目前認為任何次優(yōu)解都是足夠好的。本文利用SOM解決TSP問題，將地點的二維坐標作為網(wǎng)絡(luò)的輸入，將地點位置之間的關(guān)系作為其學習模式，而其輸出則是一個環(huán)形結(jié)構(gòu)。

1 自組織映射

1.1 基本原理

1981年學者TeuvoKohonen從人類大腦中神經(jīng)元自組織和側(cè)抑制現(xiàn)象中尋得了靈感，并結(jié)合無監(jiān)督學習的方法提出了自組織映射網(wǎng)絡(luò)（SOM）的概念。SOM的結(jié)構(gòu)主要由如圖1所示的輸入層、輸出層（特征映射）以及全連接（權(quán)值矩陣）組成。

圖1 SOM結(jié)構(gòu)

大腦皮層分為很多區(qū)域。對于外界的刺激，大腦皮層根據(jù)刺激種類使不同的區(qū)域發(fā)起反應(yīng)。與之類似，SOM會根據(jù)其所接受到外界不同的輸入模式選擇不同的應(yīng)對區(qū)域并作出不同的響應(yīng)。所涉及分區(qū)的對應(yīng)關(guān)系是在不斷的訓練學習中明確的。另外，生物的神經(jīng)元間有著側(cè)抑制現(xiàn)象：其他神經(jīng)元離自身較遠則相互抑制，反之則相互激勵。這些神經(jīng)元中對刺激響應(yīng)最強的稱為獲勝神經(jīng)元，以獲勝神經(jīng)元為中心向周圍輻射一個范圍，距離越近則激勵越強，反之越弱。激勵作用示意圖如圖2所示。

圖2 激勵作用示意圖

上述提及的范圍在SOM中被稱為優(yōu)勝鄰域，這種范圍可以促使周圍神經(jīng)元興奮。SOM有兩層神經(jīng)網(wǎng)絡(luò)，分別是輸入層（IL）和輸出層（OL）。網(wǎng)絡(luò)中的OL一般為一個二維神經(jīng)元網(wǎng)格，而代表現(xiàn)實世界中模式的數(shù)據(jù)作為IL的輸入，SOM的任務(wù)就是將輸入數(shù)據(jù)的模式在OL中映射出來。在模型訓練過程中，OL神經(jīng)元中的權(quán)值向量會不斷更迭變化，從而使得OL神經(jīng)元“學會”輸入至IL中數(shù)據(jù)所蘊含的模式。對旅行商問題而言，將地點的二維坐標作為網(wǎng)絡(luò)的輸入，將地點位置之間的關(guān)系作為其學習模式，而其輸出則是一個環(huán)形結(jié)構(gòu)。

進行訓練時首先應(yīng)選擇出獲勝神經(jīng)元，選擇依據(jù)就是輸入向量和神經(jīng)元權(quán)值向量之間的相似程度。之后根據(jù)式（1）對獲勝神經(jīng)元附近的神經(jīng)元權(quán)值向量進行更新，從而使其值逐漸接近IL的輸入向量與獲勝神經(jīng)元的權(quán)值向量。

式中：n和n+1分別為更新前和更新后的神經(jīng)元；為獲勝神經(jīng)元對其優(yōu)勝鄰域內(nèi)的神經(jīng)元作用大小的鄰域分布；為神經(jīng)元距離其附近獲勝神經(jīng)元的長度。

近鄰神經(jīng)元為處于獲勝神經(jīng)元優(yōu)勝鄰域中的神經(jīng)元，用表示兩種神經(jīng)元間的距離，則獲勝神經(jīng)元對其近鄰神經(jīng)元的作用強弱近似為正態(tài)分布。

優(yōu)勝鄰域如圖3中所示氣泡部分，氣泡外的神經(jīng)元則不會更新，而氣泡內(nèi)的神經(jīng)元將會更新。當OL神經(jīng)元的排列情況為二維網(wǎng)格狀時，屬于優(yōu)勝鄰域這個“氣泡”內(nèi)的神經(jīng)元的權(quán)值向量值將會得到更新。

圖3 近鄰神經(jīng)元

圖4為SOM訓練過程的示意圖。訓練數(shù)據(jù)的分布情況用陰影表示，從該分布中選出目前的訓練數(shù)據(jù)并用白色斑點表示。首先如圖4左側(cè)部分隨機在數(shù)據(jù)空間中定位SOM節(jié)點，然后將最靠近訓練數(shù)據(jù)的節(jié)點定為獲勝節(jié)點并將其標記。該節(jié)點網(wǎng)格上的相鄰節(jié)點與其自身將逐步向訓練數(shù)據(jù)移動，多次迭代后結(jié)果如圖4中右側(cè)圖所示，網(wǎng)格已接近數(shù)據(jù)的分布。

圖4 自組織映射訓練示意圖

1.2 利用自組織映射解決旅行商問題

由式（1）已知神經(jīng)元的更新方式，下一步還須明確哪一個神經(jīng)元為獲勝神經(jīng)元。首先應(yīng)測出輸入向量與神經(jīng)元權(quán)值向量之間的歐氏距離，若與某一神經(jīng)元距離最小，則說明兩者之間最接近，將其定為獲勝神經(jīng)元。由于本文對于SOM模型的輸入數(shù)據(jù)為地區(qū)地點二維坐標，所以地圖中地區(qū)地點應(yīng)與獲勝神經(jīng)元的位置最為接近。

在每次訓練過程中獲勝神經(jīng)元與其近鄰神經(jīng)元的權(quán)值向量都將不斷更新變化，SOM經(jīng)過足夠次數(shù)的競爭，會逐漸學會輸入數(shù)據(jù)的模式，在本應(yīng)用中即為地區(qū)各地點之間的空間關(guān)系，這種關(guān)系將會被保存為神經(jīng)元權(quán)值向量的形式。圖5為路徑計算過程示意圖，神經(jīng)元和地區(qū)地點分別用圓圈和正方形表示，神經(jīng)元不斷接近地區(qū)的地點直至與其重合，最后形成的環(huán)狀結(jié)構(gòu)就是利用SOM所求得的最短路徑。

圖5 路徑計算過程

將SOM應(yīng)用于TSP問題的關(guān)鍵在于優(yōu)勝鄰域的調(diào)整。本文將SOM的OL神經(jīng)元排成環(huán)形陣列的形式，使每個節(jié)點只與其前后的兩個神經(jīng)元進行競爭。然后SOM的輸出路徑一邊控制路徑總長，一邊向地區(qū)地點靠近，最終得到一條最短的路徑。

本文的SOM算法因在時間上不會自動進行收斂，但又需要算法不斷地對優(yōu)勝鄰域進行調(diào)整，所以需要設(shè)置學習率，用控制算法模型的探索過程以保證模型良好的收斂性。同時，還需要讓和鄰域值隨著時間而衰減，以達到模型探索充分的目的。前者會使模型計算過程收斂，后者能使離地區(qū)地點相對較遠的神經(jīng)元也加入探索的過程。將算法收斂考慮進去，模型OL神經(jīng)元的權(quán)值將按式（2）進行更新。

式中：為學習率；為獲勝神經(jīng)元的優(yōu)勝鄰域，它是以更新前的優(yōu)勝鄰域為標準差，同時以獲勝神經(jīng)元作為中心的高斯函數(shù)。

式（3）和式（4）分別表示學習率和優(yōu)勝鄰域隨時間衰減。

其中，γ和γ分別為學習率和鄰域值的衰減率。

對SOM模型設(shè)置初始的優(yōu)勝鄰域和學習率以及兩者各自所對應(yīng)的衰減率，之后按上述步驟運行。優(yōu)勝鄰域和學習率都會隨著模型的不斷迭代而減小，最后收斂。

將某一地區(qū)地點與其相應(yīng)的獲勝神經(jīng)元連接起來，隨機選擇一點開始，然后按照獲勝神經(jīng)元的順序?qū)Φ貐^(qū)地點排序。另外，若SOM沒有考慮穿越某些地區(qū)地點的順序，或者因為穿越順序與總距離的相關(guān)性太低，又或者因為精確度太低，以至于在這個過程中可能會出現(xiàn)若干個地區(qū)的地點映射到了同一神經(jīng)元的情況。這時就需要考慮這些地區(qū)地點的各種可能的排序情況。

2 實例研究

2.1 仿真條件

本文實驗程序采用Python語言編寫，所編寫程序于PyCharm軟件Python3.8環(huán)境下進行。實驗數(shù)據(jù)源自如圖6所示的滑鐵盧大學在“National Traveling Salesman Problem instances”項目中的數(shù)據(jù)庫，其中的數(shù)據(jù)包含地區(qū)地點的位置以及目前得到的最短路徑。

圖6 實驗數(shù)據(jù)來源

另外，評估過程中對所用的參數(shù)做了調(diào)整。首先，SOM網(wǎng)絡(luò)規(guī)模（神經(jīng)元數(shù)量）是地區(qū)地點總數(shù)的8倍；其次，初始學習率設(shè)置為0.8，衰減率設(shè)置為0.999 97；最后，初始優(yōu)勝鄰域值為地區(qū)地點總數(shù)，且將衰減率設(shè)置為0.999 7。

2.2 實驗結(jié)果

對于SOM模型中的某些參數(shù)本文設(shè)置了閾值，在計算過程中若其參數(shù)數(shù)值低于本文所設(shè)置的有效閾值時，模型將停止迭代并輸出結(jié)果。雖然SOM模型可以為實驗選取的五個實例尋到更精確的參數(shù)，但本文還是采用了統(tǒng)一的方法對這五個地區(qū)進行了測試。表1為使用模型對每個實例計算五次所得的數(shù)據(jù)。

表1 實例計算數(shù)據(jù)

圖7為對卡塔爾地區(qū)194個地點的最短路徑計算分別迭代1 000、5 000、11 000次以及最終的輸出情況。

圖7 卡塔爾地區(qū)路線變化情況

表2中的運行結(jié)果是對每個實例計算五次后去掉最大和最小數(shù)值后所求取的平均值。

表2 實例數(shù)據(jù)詳情

從表2中的數(shù)據(jù)可以發(fā)現(xiàn)，模型運行時間隨著地區(qū)地點數(shù)目的增加而增加。除了Uruguay地區(qū)外，當?shù)貐^(qū)地點數(shù)目較低時，誤差通常會更??；反之，誤差將會變大。但Uruguay地區(qū)比Qatar地區(qū)多了五百多個地點，其誤差反而更小，猜測Qatar地區(qū)總距離和穿越順序的相關(guān)性不高，因此對計算的精度有了影響。

3 結(jié) 語

電力巡檢過程中的巡檢點可以近似看作TSP問題中的地點。為求出各地點間的最短路徑，提高電力巡檢效率，本文將SOM應(yīng)用于該問題中，并通過五個地區(qū)的實例驗證了該方案的可行性。實驗數(shù)據(jù)表明，該方法收斂速度較快。同時，當?shù)攸c數(shù)目較少時模型計算結(jié)果誤差較小，反之則較大。又因巡檢任務(wù)中的巡檢點數(shù)量一般不會太多，所以使用該模型求解電力巡檢最短路徑問題有著較高實用價值。