基于自組織映射網絡的電力最短巡檢路徑問題求解

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

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

0 引 言

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

1 自組織映射

1.1 基本原理

1981年學者TeuvoKohonen從人類大腦中神經元自組織和側抑制現象中尋得了靈感，并結合無監督學習的方法提出了自組織映射網絡（SOM）的概念。SOM的結構主要由如圖1所示的輸入層、輸出層（特征映射）以及全連接（權值矩陣）組成。

圖1 SOM結構

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

圖2 激勵作用示意圖

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

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

式中：n和n+1分別為更新前和更新后的神經元；為獲勝神經元對其優勝鄰域內的神經元作用大小的鄰域分布；為神經元距離其附近獲勝神經元的長度。

近鄰神經元為處于獲勝神經元優勝鄰域中的神經元，用表示兩種神經元間的距離，則獲勝神經元對其近鄰神經元的作用強弱近似為正態分布。

優勝鄰域如圖3中所示氣泡部分，氣泡外的神經元則不會更新，而氣泡內的神經元將會更新。當OL神經元的排列情況為二維網格狀時，屬于優勝鄰域這個“氣泡”內的神經元的權值向量值將會得到更新。

圖3 近鄰神經元

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

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

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

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

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

圖5 路徑計算過程

將SOM應用于TSP問題的關鍵在于優勝鄰域的調整。本文將SOM的OL神經元排成環形陣列的形式，使每個節點只與其前后的兩個神經元進行競爭。然后SOM的輸出路徑一邊控制路徑總長，一邊向地區地點靠近，最終得到一條最短的路徑。

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

式中：為學習率；為獲勝神經元的優勝鄰域，它是以更新前的優勝鄰域為標準差，同時以獲勝神經元作為中心的高斯函數。

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

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

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

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

2 實例研究

2.1 仿真條件

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

圖6 實驗數據來源

另外，評估過程中對所用的參數做了調整。首先，SOM網絡規模（神經元數量）是地區地點總數的8倍；其次，初始學習率設置為0.8，衰減率設置為0.999 97；最后，初始優勝鄰域值為地區地點總數，且將衰減率設置為0.999 7。

2.2 實驗結果

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

表1 實例計算數據

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

圖7 卡塔爾地區路線變化情況

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

表2 實例數據詳情

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

3 結 語

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