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

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

0 引 言

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

1 自組織映射

1.1 基本原理

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

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

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

圖2 激勵(lì)作用示意圖

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

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

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

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

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

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

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

圖4 自組織映射訓(xùn)練示意圖

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

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

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

圖5 路徑計(jì)算過程

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

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

式中：為學(xué)習(xí)率；為獲勝神經(jīng)元的優(yōu)勝鄰域，它是以更新前的優(yōu)勝鄰域?yàn)闃?biāo)準(zhǔn)差，同時(shí)以獲勝神經(jīng)元作為中心的高斯函數(shù)。

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

其中，γ和γ分別為學(xué)習(xí)率和鄰域值的衰減率。

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

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

2 實(shí)例研究

2.1 仿真條件

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

圖6 實(shí)驗(yàn)數(shù)據(jù)來源

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

3 結(jié) 語(yǔ)

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