基于自適應NSGA-Ⅱ算法的配電網多故障搶修優化決策

陳楚昭， 孫云蓮

(武漢大學電氣與自動化學院，湖北 武漢 430072)

0 引言

當配電系統由于自然因素或者人為因素發生停電事故時，各級對應的搶修部門應當快速反應，及時組織人員以及物資前往故障點進行搶修工作[1]。但是，當自然災害或者某些人為因素引發的區域性多故障點、大面積的停電事件發生時，依據人工經驗分派搶修任務的方式很難真正合理有效地在最短的時間、盡可能小的停電影響范圍內完成搶修任務。

目前，對配電網故障搶修的研究主要集中在對搶修路徑優化，搶修任務分配和優化算法的改進，以及對模型和目標等的改進[2—3]。文獻[4]提出通過遺傳算法尋優和拓撲分析算法判斷故障失電區域相關信息，綜合迭代得到最佳搶修方案，但僅考慮了單搶修小隊的情況而未考慮多小隊同時搶修的情況。文獻[5]利用電網應急指揮系統的信息，以增強電網運行穩定的裕度和減少停電損失為目標，考慮資源保障率，建立對電網應急搶修資源的調度方案。文獻[6]將故障搶修與故障恢復相結合，考慮了多搶修小隊協同搶修的工作模式，采用改進的多目標細菌群體趨藥性(bacterial colony che￣mo￣taxis,BCC)算法研究計算應急搶修策略。文獻[7]考慮到搶修小隊不能滿足每個故障點對搶修資源的需求，提出將適應度作為外化指標，根據各搶修小隊與各故障點之間的匹配程度進行最優任務分配。文獻[8]考慮了搶修小隊初始位置不同和協作效用，以輪盤賭的選擇方式得到搶修方案集合，并采用改進的BBC算法，得出最佳方案和搶修順序。文獻[9]提出了多故障同時出現的應急情況下，單個資源中心無法滿足當前資源需求的問題，并以最短的維修啟動時間和最少的資源中心為目標建立多資源、多中心調度模型，得到最優的資源調度方案。

文中在配電網多故障搶修過程中考慮了任務分配和各隊協同搶修等問題，建立了故障搶修的多目標數學模型。在多目標的處理方法上，考慮到不同地區的配電系統對各個目標的重要性存在差異，因此不預先設置各目標的權重，而是采用非劣解生成法得到Pareto集，避免因權重設置不合適而錯過最優策略。算法上采用自適應參數的非支配排序遺傳算法(non dominated sorting genetic algorithm,NSGA)-Ⅱ進行求解，同時為了方便決策者從一系列方案中選出最優方案，文中設計了基于角度選擇的拐點決策算法，使得多目標優化算法能夠直接輸出一個比較優秀的解。

1 配電網多故障搶修模型

1.1 配電網多故障搶修問題描述

配電網多故障搶修是一個以各班組的故障任務分配和故障搶修順序為決策變量的多目標、多約束的非線性混合整數優化問題[10]。配電網多故障搶修問題描述如下：某地區有1個搶修中心，搶修中心有M個搶修班組(s1,s2,…,sM)，搶修中心負責的區域內有N個故障點(r1,r2,…,rN)。設Cm為帶有搶修順序的搶修班組sm所需要搶修的故障點集合，該搶修班組需要從搶修中心出發，順次經過集合中的所有故障點進行搶修工作，最后返回搶修中心。如Cm={Cm1,Cm2,…,Cmh}，則搶修班組sm須按照o→Cm1→Cm2→…→Cmh→o的順序進行搶修工作，其中，起點和終點o為搶修中心。每個故障點的搶修任務都可以任意分配給1個搶修班組，每個班組在任務分配后都可以任意安排完成搶修任務的順序。

由于需要搶修的故障點較多，能夠派遣的搶修班組數量有限，因此，須依靠構建的模型合理安排每個搶修班組對應的任務以及搶修的先后順序，以提升配電網搶修效率，提高供電可靠性。實際搶修中，常對不同的目標進行優化，如最大完工時間、搶修成本、停電損失等，這些目標需要同時進行優化處理，而這些目標又往往是互相沖突的。在各種約束條件下，如何對多目標同時實現優化，合理安排任務分配和完成順序，就是配電網多故障搶修需要解決的問題[11—13]。

1.2 目標函數的確定

根據上述分析，指定最終的優化目標為完成所有任務所需要的時間最短和故障引發的社會經濟損失最小。

目標函數f1(X)為完成所有搶修任務需要的時間最短：

f1(X)=min{maxTm}m=1,2,…,M

(1)

式中：Tm為搶修班組sm完成故障搶修任務所需要的時間，是搶修班組完成任務在路上耗費的時間Tml與各故障點預估的搶修時間Tmy之和。

Tm=Tml+Tmy

(2)

目標函數f2(X)為故障引發的社會經濟損失最?。?/p>

(3)

式中：K為受故障影響發生停電的負荷數量；bk為負荷k的停電時間；Lk為負荷k的功率；wk為負荷k的重要性權重系數。根據電力負荷的用電設施安全性及整體的供電可依賴性對負荷的重要性作出具體評估，根據其緊要程度分別為一、二、三級負荷，分別設置其權重為w1，w2，w3，則wk可表示為：

(4)

1.3 約束條件的確定

(1) 搶修任務約束。VMN為一個M×N的矩陣，vmn為矩陣中第m行第n列的元素，表示第m個搶修班組是否負責搶修第n個故障點。第m個班組被分配到搶修第n個故障點時，vmn的值為1，其他情況為0，即：

(5)

為滿足每個故障點的搶修任務只分配給一個班組，將約束條件定為：

(6)

(2) 搶修時間約束。每個班組的搶修時間應當在合理范圍內：

Tm≤TSmm=1,2,…,M

(7)

式中：TSm為班組最大允許搶修時間。

(3) 故障時間約束。每個故障點的修復時間應當在合理范圍內：

tn≤tSnn=1,2,…,N

(8)

式中：tn為故障點rn從故障開始到完成修復的時間；tSn為系統規定的最大允許停電時間。

(4) 搶修資源及其他約束。搶修班組提供的搶修資源應當能夠覆蓋故障點的搶修資源需求，且滿足搶修對時間、天氣、路況等自然條件的要求。

1.4 模型假設

假設一：每個搶修班組都具備獨立處理各類配電網中電力故障的能力，不需要別的搶修班組進行協助；

假設二：每個搶修班組的搶修效率相同，即處理相同故障所耗費的時間相同，且每個搶修班組在同一時間只能處理一個故障任務；

假設三：所有班組擁有的搶修物資相同，并假設搶修物資多數為耐用物資，而易損耗的搶修物資數量足夠支持搶修班組不回調度中心連續搶修多處故障點；

假設四：多故障同時發生的情況下，在進行派單調度搶修班組之前，所有故障的地址、故障類型、所需搶修物資都是已知的；

假設五：故障點之間的距離以及故障點和供電所調度距離都按最短直線距離計算，且路上行駛的時間只與距離成正比，沒有方向性；

假設六：各故障點的位置、故障原因及故障搶修預估時間都可以在搶修調度前估算得到。

2 基于角度選擇的自適應參數NSGA-Ⅱ算法

2.1 NSGA-Ⅱ算法

進化計算是模擬自然界物種演化過程的優化方法，遵循適者生存的規則，目前已被大量應用到各類優化問題中。由于其并行計算的特點，多目標優化算法一般都是基于進化計算設計的。常用的優化算法有多目標遺傳算法(multi objective genetic algorithm,MOGA)、小生境Pareto遺傳算法(niche Pareto genetic algorithm,NPGA)和NSGA等。其中，NSGA基于Pareto最優的思想來解決多目標優化問題，已有學者引入精英策略和擁擠度計算對NSGA進行了改進，形成了NSGA-Ⅱ算法[14]。

NSGA-Ⅱ算法提出了快速非支配排序策略，簡化了運算的復雜程度，并加入了精英策略和擁擠度的比較因子，保證了種群的優良性和多樣性，適用于求解多目標優化問題。

2.2 基于角度選擇的拐點決策算法

求解優化問題都是為了得出問題的最終方案。利用NSGA-Ⅱ算法往往可以得到多個可行方案，對于多目標優化問題而言，為了得出最終的解決方案，決策者可以根據自己的偏好以及不同目標的重要性做出選擇。但研究發現，拐點在多目標優化問題求解得到的Pareto前沿中具有獨特的意義[15]，通常被描述為各個區域內的最優解決方案，其主要特點是：從幾何角度看，如果Pareto前沿的形狀是彎曲的，那么拐點解決方案代表的是那些可以改善整體性能同時又在某些標準上作出微不足道的犧牲的方案[16]。換言之，拐點解決方案可以在某些目標上表現出顯著的改進，而在其他目標上卻沒有明顯的降低[17]。拐點的選擇策略中比較有代表性的是基于角度的選擇[18]，在只有2個目標的情況下，穿過每一個解及其2個鄰域解的2條直線之間所形成的角可以作為解是否處于拐點的一個衡量指標，如圖1所示。由圖1可知，2條線之間的角度α越大，則該方案越趨向于拐點[19]。

圖1 基于角度選擇的拐點Fig.1 Inflection point based on angle selection

因此，在沒有任何先驗知識的前提下，可以將拐點處的解決方案當作多目標決策的最佳方案，這樣能夠使算法最終輸出一個滿意解，而無需決策者的參與。

2.3 自適應參數的調整策略

文中采用基于進化階段的自適應方法作為個體交叉率與變異率的調整方法[20—22]。將種群的整個進化過程分為3個階段，不同階段個體交叉率與變異率都隨進化代數的增加呈線性下降走向，直至在數值上與下一階段的初始交叉率和變異率相等。自適應交叉率和變異率的模型具體如下。

(1) 當非支配解個數小于20時，個體交叉率和變異率的模型分別為：

(9)

(10)

(2) 當非支配解個數大于等于20時，個體交叉率不變，而變異率模型為：

(11)

式中：Pc為個體交叉率；Pc1，Pc2，Pc3分別為設定的各階段的交叉率參數；Pm為個體變異率；Pm1，Pm2，Pm3，Pm4分別為設定的各階段的變異率參數；β為變異率模型調節參數；K為算法的最大進化代數，K1=αK，K2=(1-α)K。0～K1為進化初期階段，K1～K2為進化中期階段，K2～K為進化后期階段。

在種群進化前期，優秀解距離Pareto最優前沿較遠，為保證群體的參與性，需要采用較大的變異率Pm，提高全局搜索能力，防止種群早熟；在進化中期，需要兼顧全局與局部的搜索特性，以便提高收斂的速度；在進化后期，種群中優秀解的數量居多，采用較大的交叉概率Pc，以提高局部搜索能力[23]。算法的詳細流程如圖2所示。

圖2 改進的自適應NSGA-Ⅱ算法流程Fig.2 Process of improved adaptive NSGA-Ⅱ algorithm

3 算例分析

3.1 算例參數

以某鎮某條實際配電線路為算例，圖3為該線路簡化圖。假設某時間段配電網絡中共發生10起故障，C1～C10為故障點所在位置，0為電源點，1～32為負荷節點。由于只有1個電源點，因此故障點后的節點將完全失電，各節點失電負荷功率和等級如表1、表2所示[24—25]。

圖3 某鎮實際配電線路簡化圖Fig.3 Simplified diagram of actual distribution network in a town

對于各故障點后的負荷等級，按一級負荷權重w1=100，二級負荷權重w2=10，三級負荷權重w3=1設置。各故障點故障類型和預計搶修時間如表3所示[26]，故障點的地理坐標如表4所示，搶修中心o的地理坐標為(113.244 164,24.263 363)。

表1 各失電節點負荷功率Table 1 Load power of each power loss node kW

表2 各失電節點負荷等級Table 2 Load level of each power loss node

表3 各故障點故障類型和預計搶修時間Table 3 Fault types and expected repair time of each fault point

表4 各故障點地理坐標Table 4 Geographical coordinates of each fault point

3.2 算例求解

假設共有3個搶修能力相同的搶修班組，搶修班組在故障點間的行程速度為60 km/h，設置NSGA-Ⅱ算法的參數為[27—28]：種群規模100，最大進化代數200，自適應參數Pc1=0.6，Pc2=0.7，Pc3=0.9，Pm1=0.2，Pm2=0.4，Pm3=0.3，Pm4=0.1，α=0.25，β=0.6。運行算法程序，得到結果如圖4所示。

圖4 使用自適應參數策略的算法結果Fig.4 Results of algorithm using adaptive parameter strategy

圖4(b)中，每一個點都代表一個Pareto最優解，每個最優解代表的搶修方案如表5所示。

表5 搶修方案展示Table 5 Emergency repair scheme

為得到最終的搶修方案，首先對表5中的2個目標函數值按式(12)進行標準化，標準化后的結果及每個方案的角度α如表6所示。

(12)

表6 標準化后的方案角度Table 6 The angle of schemes after standardization

根據前文所述的基于角度選擇的拐點決策算法，顯然點4為該優化問題的拐點，因此最終選擇方案4為該搶修優化問題的最佳方案。

3.3 結果驗證

3.3.1 基于角度選擇的拐點決策的驗證

從實際搶修經驗來看，對高級別負荷的搶修程度更緊急。如圖3和表2所示，故障點3、4、5、6、7、9的故障造成了一級負荷8、10、12、15、27失電，需要盡早修復。表5所示的7個可行方案中，方案1、2、3、4都將故障點3、4、5、6、7、9放入了各班組搶修順序的前列，而方案5、6、7出于縮短搶修時間的考慮，都制定出了4→5→6→7的搶修順序。

算例中最終選擇方案4作為最佳搶修方案，與“對高級別負荷的搶修程度更緊急”這一實際搶修經驗相符合。因此，文中所提基于角度選擇的拐點決策算法適用于實際搶修工作，可以減輕決策人員的負擔。

3.3.2 自適應參數調整策略的驗證

若不采用自適應參數的調整策略，設置Pc=0.9，Pm=0.1，仿真結果如圖5所示。由圖5(b)可知，得到的Pareto最優解較少，分析圖5(c)和圖5(d)可知該算法早熟收斂，由于始終采用較大的交叉率和較小的變異率，容易陷入局部最優從而丟失部分Pareto最優解(與表5相比丟失方案1、2、3)。

圖5 早熟收斂的算法結果Fig.5 Results of algorithm with premature convergence

設置Pc=0.6，Pm=0.4，仿真結果如圖6所示。與表5相比丟失方案1、3，由于始終采用較小的交叉率和較大的變異率，搜索范圍較大但是局部搜索性能不好，容易丟失某些Pareto最優解(得到了方案2、4，但丟失了方案3)。

圖6 局部搜索能力差的算法結果Fig.6 Results of algorithm with poor local search ability

根據2.3節所述，采用自適應參數的調整策略的搜索算法，在種群進化前期可具備較高的全局搜索能力，在進化中期可具備較高的收斂速度，在進化后期可具備較高的局部搜索能力。

4 結論

(1) 故障搶修任務中，不同地區的配電系統對各個目標的重要性存在差異。因此，不使用加權法而是采用非劣解生成法得到Pareto集，可以避免因權重設置的不合適而錯過最優策略。

(2) NSGA-Ⅱ算法中引入自適應參數的調整策略，能提高種群進化前期的全局搜索能力以及進化后期的局部搜索能力，完成可行解的全面搜索。

(3) 在多目標優化中引入基于角度選擇的拐點決策算法，可以直接從多個可行方案中選擇最終的決策方案，從而減輕決策人員的負擔，并且適用于實際搶修工作。