一種改進的蟻群算法求解TSP問題及實驗結果分析

一種改進的蟻群算法求解TSP問題及實驗結果分析（完整版）實用資料(可以直接使用，可編輯完整版實用資料，歡迎下載）

一種改進的蟻群算法求解TSP問題及實驗結果分析一種改進的蟻群算法求解TSP問題及實驗結果分析（完整版）實用資料(可以直接使用，可編輯完整版實用資料，歡迎下載）何開成（四川大學電子信息學院四川成都610064）摘要：首先對蟻群算法的基本模型進行介紹，其次針對算法容易陷入局部最優(yōu)解，在算法中加入擾動量，擴大搜索范圍，從而有效控制算法陷入局部最優(yōu)解。針對蟻群算法收斂速度慢，利用蟻群在最差路徑上的信息，對蟻群算法信息素更新規(guī)則上進行改進。實驗結果表明，提出的改進蟻群算法有效的避免程序過早的陷入局部最優(yōu)解，同時提高蟻群算法的速度。關鍵詞：蟻群算法；擾動量；算法改進；局部最優(yōu)解中圖分類號：TP301文獻標識碼：A文章編號：1671－7597（2021）0820071－021蟻群算法基本模型許多種類的螞蟻在食物搜索過程中都存在釋放信息素和信息素引導的現(xiàn)象。Deneubourg利用一個簡單的試驗模型說明了這種以自組織為基礎的路徑選擇方式。在此模型中，蟻穴和食物之間被一座有兩個等長支路的橋所分離。開始時，由于兩條支路上都沒有信息素分布，螞蟻們將按照相同的概率進行路徑選擇。引入隨機波動后，將有一條路徑上通過的螞蟻會更多一些，這將增加該路徑上的信息素濃度，于是就會引導更多的螞蟻選擇這條路徑。在Deneubourg設計的試驗中，遺留在路徑上的信息素濃度與經(jīng)過的螞蟻數(shù)量成正比，而且不考慮信息素的揮發(fā)問題。在這種簡化的模型中，螞蟻選擇路徑的依據(jù)就是己經(jīng)過該路徑的螞蟻總數(shù)。設減和盡雙為第i個螞蟻經(jīng)過橋之后，分別選擇了路徑A和B的螞蟻數(shù)。則第i+l只螞蟻選擇路徑A和B是，由于構造型算法優(yōu)化質量較差，迄今為止已開發(fā)了許多性能較好的改進型搜索算法，主要有：模擬退火算法，禁忌搜索算法，Hopfield神經(jīng)網(wǎng)絡優(yōu)化算法，蟻群算法，遺傳算法，混合優(yōu)化策略。3蟻群算法求解旅行商問題模型以求解平面上n個城市的旅行商問題為例說明蟻群系統(tǒng)的基本模型。旅行商問題就是給定n個城市的位置和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當一次且只有一次的最短路線。其圖論描述為：給定圖（V，A），其中v為頂點集，A為各頂點相互連接組成的邊集，已知各頂點間的連接距離，要求確定一條長度最短的回路，即遍歷所有頂點一次且只有一次的最短回路。為了更好地說明問題，首先引入如下記號M：蟻群中螞蟻數(shù)量；bi（t）：t時刻位于城市i的螞蟻的個數(shù)，i和j之間的距離；nij：邊（i，j）的能見度，城市i和j之1/diji，j）上的信息素軌跡強度；k在邊（i，jk的轉移概率，j是尚未訪問的城市。每只螞蟻都是具有如下特征的簡單實體；1）在從城市派到城市j的運動過程中或是在完成一次循環(huán)后，螞蟻在邊（i，j）上釋放一種物質，成為信息素軌跡；2）螞蟻按概率選擇下一個將要訪問地城市，這個概率是城市間的距離和連接兩城市的路徑上存有的軌跡量的函數(shù)；3）為了滿足問題的約束條件，在完成一次循環(huán)以前，不允許螞蟻選擇己經(jīng)選擇過的城市。=C（C為常數(shù)）。螞蟻k（k=1，2，3，…，m）在運動過程中根據(jù)各條路徑上的信息素量決定轉移方向。蟻群系統(tǒng)使用隨機比例轉移規(guī)則進行狀態(tài)的轉移。轉移規(guī)則給出了位于城市i的螞蟻kk在城市i選擇城市j的轉移概率式中：allowed={0，1，k下一步允許選擇的城市。經(jīng)過n個時刻，當m只螞蟻都經(jīng)過一次搜索周期后，在路徑上的信息素量的改變根據(jù)下面式子進行更新：上述公式對這種選擇方式進行了量化。參數(shù)n決定了選擇函數(shù)的非線性度，n較大時，只要一條路徑上的信息素濃度稍高于另外一條路徑，則下一只螞蟻選擇前一路徑的概率就會更大。參數(shù)k反映了未標記路徑的吸引力，k越大，則進行非隨機化選擇所需的信息素濃度要求越高。這種概率表達方式是實際的螞蟻路徑選擇試驗推導而來的。比較適合試驗需要的參數(shù)設置是n=2和k=20。2旅行商問題旅行商問題（TravelingSalesmanProblem，簡稱TSP）即給定n個城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當且僅當一次的最短路線。其圖論描述為：給定圖G=（V，A），其中V為頂點集，A為各頂點相互連接組成的邊集，設D=（dij）是由頂點i和頂點j之間的距離所組成的距離矩陣，要求確定一條長度最短的Hamilton回路，即遍歷所有頂點當且僅當一次的最短距離。旅行商問題可分為如下兩類：1）對稱旅行商問題（dij=diji，j=1，2，3，…，n）；2）非對稱旅行商問題（dijdiji，j=1，2，3，…，n）。非對稱旅行商問題較難求解，我們一般是探討對稱旅行商問題的求解。若對于城市V={v1，v2，v3，…，vn}的一個訪問順序為T={t1，t2，t3，…ti，…，tn}，其中tiV（i=1，2，3，…，n），且記tn+1=t1，則旅行商問題的數(shù)學模型為：4蟻群算法的缺點旅行商問題是一個典型的組合優(yōu)化問題，并且是一個NP完全難題，是諸多領域內(nèi)出現(xiàn)的多種復雜問題的集中概括和簡化形式，并且已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標準。因此，快速、有效地解決旅行商問題有著重要的理論價值和極高的實際應用價值?；诼眯猩痰膯栴}特性，構造型算法成為最先開發(fā)的求解算法，如最近鄰點、最近合并、最近插入、最遠插入、最近添加、貪婪插入等。但蟻群算法最主要的缺點是求解速度慢。很多學者對此進行了研究，提出了多種改進方法，但不論采用那種具體方法，都可歸結為通過提高螞蟻每次周游的質量來提高蟻群算法的求解速度。之所以都采用這種方法，就是由于基本蟻群算法求解速度慢的一個重要原因是螞蟻每次周游得到的信息沒有被充分地利用起來。這主要體現(xiàn)在各條路徑上的信息量更新規(guī)則上。由上面對蟻群算法的介紹可知，螞蟻在周游過程中，會使它經(jīng)過的路徑上的信息量減少，同時，增強螞蟻周游的信息沒有充分地利用起來。實際上，每只螞蟻周游的信息也是很有用的。蟻群算法求解速度慢的另一個重要原因是螞蟻獲取的信息與實際情況會有一些差異，這會對螞蟻產(chǎn)生誤導，而蟻群算法排除誤導的速度較慢。蟻群算法求解過程是一個正反饋過程。螞蟻的第一次周游時，由于各路徑上的信息量相同，螞蟻選擇城市是隨機的。這一次選擇會使一些不是最優(yōu)的路徑上的信息量偏大。以后的螞蟻就會根據(jù)這個不正確的信息選擇以后的路徑，這些不是最優(yōu)的路徑被螞蟻選擇的可能性將很大，這會導致這些較差的路徑上的信息量不斷增大。經(jīng)過這樣一個正反饋過程，路徑上的信息量就具有了很大的誤差而導致算法難以找到較優(yōu)解。蟻群算法在一定程度上可通過信息量的揮發(fā)過程以及螞蟻周游的下一個城市的隨機選擇過程來排除具有較大誤差的信息。但是，信息量揮發(fā)過程是緩慢的。而且在揮發(fā)過程中，很可能會有許多螞蟻再次經(jīng)過這條路徑，并有可能使這條路徑上的信息量增大。一次通過選擇城市隨機性來削減誤差僅在算法剛運行不久，各條路徑上的信息量相差不是很大的情況下才可能起到一定作用。由于這兩種排除誤差的方法均不能較快地排除誤差，也導致了蟻群算法求解速度慢，并且增加了算法陷入局部最優(yōu)的可能性。5蟻群算法的改進1）加入擾動的改進針對蟻群算法容易陷入局部最優(yōu)解，這里引入?yún)?shù)q0，螞蟻k從i城市選擇下一個城市j時，首先產(chǎn)生一個[0，l]均勻分布的隨機數(shù)q，當q小于常數(shù)q0時，螞蟻根據(jù)先驗知識即：能見度選擇下一個城市。公式（1）改進為：③依狀態(tài)轉移規(guī)則選擇下一結點；④重復步驟③，直至每只螞蟻均形成一條完整路徑，即遍歷所有結點；⑤更新最優(yōu)解；⑥進行信息素更新；⑦判斷是否滿足算法終止條件：若滿足，則算法終止；否則，轉步驟②。6實驗結果及分析本文利用MATLAB仿真平臺對典型的旅行商問題OdysseyofUlysses進行進行了仿真實驗，已知OdysseyofUlysses問題的最優(yōu)解是75.6651。我們分別取NC=10，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1。a=l；NC=50，m=50，a=l=2，p=0.3，Q=1，W=4，q0=0.1，。a=l；NC=100，m=50，a=l，p=0.3，Q=1，W=4，q0=0.1a=l，原始蟻群算法與改進蟻群算法分別周游10次，50次，100次所得到的最優(yōu)解對比如下表：加入擾動參數(shù)q，每隔一定時間，螞蟻在選擇下一個城市時，只根據(jù)能見度選擇，這樣可以排除因為蟻群算法正反饋導致的較大誤差解，擴大了解的搜索范圍，有效避免了蟻群算法過早陷入局部最優(yōu)解。2）信息素更新規(guī)則的改進蟻群算法最主要的缺點是求解速度慢。由于基本蟻群算法求解速度慢的一個重要原因是螞蟻每次周游得到的信息沒有被充分地利用起來。這主要體現(xiàn)在各條路徑上的信息量更新規(guī)則上。由上面對蟻群算法的介紹可知，螞蟻在周游過程中，會使它經(jīng)過的路徑上的信息量減少，同時，增強螞蟻在最短路徑上的信息。這一過程利用了螞蟻周游最短路徑的信息。但其它螞蟻周游的信息沒有充分地利用起來。實際上，每只螞蟻周游的信息也是很有用的。本文充分利用螞蟻在最差路徑上的信息對蟻群算法的信息素更新規(guī)則做了改進，在規(guī)則中引入了最差路徑信息量減少參數(shù)w，改進后公式（2）調(diào)整為：從實驗結果對比來看，改進后的蟻群算法在100次周游下已經(jīng)找到問題的最優(yōu)解，而原始的蟻群算法雖然在加大周游次數(shù)可以逐步接近最優(yōu)解，但是他的收斂性不好，容易陷入局部最優(yōu)解，所以，加大周游次數(shù)對求解旅行商最優(yōu)解的意義不大。而改進的蟻群算法正是對原始蟻群算法的收斂速度慢，容易陷入最優(yōu)解這兩個方面進行了改進，改進后的蟻群算法能夠擴大最優(yōu)解的搜索范圍，有效地避免算法過早陷入局部最優(yōu)的情況的出現(xiàn)。實驗結果證明：改進后的蟻群算法無論是最優(yōu)解的方面還是在收斂速度方面都比原始蟻群算法要好。7結論蟻群算法最大的缺點就是收斂速度慢，容易陷入最優(yōu)解，這也是限制它應用的最大瓶頸。本文針對蟻群算法收斂速度慢、容易過早陷入局部最優(yōu)的缺點提出了一種新的改進算法。實驗證明了這種改進的有效性和正確性。表示揮發(fā)系數(shù)，Q為信息量增加常數(shù)，w為信息量減少常數(shù)。3）算法實現(xiàn)MATLAB是一個可視化的計算程序，被廣泛地使用于從個人計算機到超級計算機范圍內(nèi)的各種計算機上。它包括命令控制、可編程，有上百個預先定義好的命令和函數(shù)。這些函數(shù)能通過用戶自定義函數(shù)進一步擴展。MATLAB有許多強有力的命令。正因為MATLAB具有這么多的優(yōu)點，特別是在數(shù)值計算方面的獨到性，本文利用MATLAB平臺進行仿真實驗。其程序步驟如下：①初始化信息素分布；②將每只螞蟻隨機置于任一個結點上；參考文獻：[1]吳斌、傅偉鵬、鄭毅、劉少輝，史忠植一種基于群體智能的Web文檔聚類算法計算，機研究與發(fā)展，2021，39（11）：1429～1435.[2]吳啟迪、汪鐳，智能蟻群算法及應用[M].上海：上?？萍冀逃霭嫔纾?021.4.[3]黎鎖平、張秀媛、楊海波，人工蟻群算法理論及其在經(jīng)典TSP問題中的實現(xiàn)[J].交通運輸系統(tǒng)工程與信息，2007，2（2）：73～76.一種基于新的相模變換矩陣的輸電線路故障測距改進算法郭亮1,呂飛鵬1,羅長亮1,蔣科1,李鵬飛2(1.四川大學電氣信息學院,四川成都610065;2.山東電力工程咨詢院,山東濟南250013摘要:針對已有電力系統(tǒng)行波故障測距算法中采用的相模變換、小波變換存在的不足,提出了一種結合新的相模變換矩陣和提升小波的行波故障測距改進算法,實現(xiàn)了單一模量反映所有故障類型,簡化了高頻小波系數(shù)的計算,提高了計算速度。通過Matlab仿真實驗,驗證了與普通小波測距相比,算法具有較高的測距精度。關鍵詞:相模變換;提升小波;故障測距;輸電線路;暫態(tài)行波Abstract:Consideringthedeficienciesoftheusedphase-modetransformationandwavelettransformintheavailabletransmis2sionlinefaultlocationalgorithms,animprovedalgorithmforthefaultlocationbasedonanewphase-modetransformationma2trixandliftingwaveletisproposed.Alltypesoffaultcanbereflectedbyasinglemodulus,thecalculationforthewaveletcoef2ficientswithhighfrequencyissimplified,andthecalculationspeedisenhanced.Matlabsimulationshowsthatthealgorithmhasahigheraccuracycomparedwiththetraditionalwaveletlocationmethods.Keywords:phase-modetransformation;liftingwavelet;faultlocation;transmissionline;transienttravelingwave中圖分類號:TM755文獻標志碼:A文章編號:1003-6954(202106-0038-040引言故障測距是電力系統(tǒng)查找輸電線路故障點的重要依據(jù)。在輸電線路故障后及時、準確地找到故障點,對修復線路,保證可靠供電以及電力系統(tǒng)的安全穩(wěn)定、經(jīng)濟運行具有非常重要的作用。行波故障測距法因其原理簡單,近年來受到了國內(nèi)外學者的關注,得到了廣泛的研究[1~11]?，F(xiàn)有的行波故障測距法多采用相模變換與小波變換相結合對暫態(tài)行波信號進行分析。目前常用的Clark、Karrenbauer、Wedpohl等變換矩陣在分析時域問題時應用最多,但其在繼電保護應用中的最大缺陷是單模量不能適用于所有類型故障。若要使模量能反映所有類型故障,必須使用雙模量或選相配合,從而使計算量大大增加[12]。傳統(tǒng)的基于卷積的離散小波變換計算量大,計算復雜度高,對存儲空間的要求高,不利于硬件實現(xiàn)[14]。針對已有行波故障測距算法存在的不足,提出了一種結合新的相模變換矩陣和提升小波的行波故障測距法。該算法通過對電流行波進行相模變換,再利用提升小波分析線路兩端電流行波線模量來實現(xiàn)高精度故障測距。與已有的行波測距法相比,該方法不僅解決了單一模量不能反映所有故障類型的問題,還具備運算所需儲存空間小,計算量小和計算效率高等優(yōu)點。最后將其仿真結果與普通小波測距結果進行了對比。1新的相模變換矩陣的分析相模變換的數(shù)學本質就是將參數(shù)矩陣化為對角陣。對于三相均勻換位線路,根據(jù)其相模變換矩陣的構造原則,即第一列各元素相等,第二、三列元素之和均為零,文獻[13]構造出一種新的相模變換矩陣,其原始陣為S=1155555-1-45-4-1(1S-1=11112-31-32(2對故障暫態(tài)相電流進行相模變換,可以提取線模分量,即1模量和2模量。表1給出了各種類型故障下使用該相模變換矩陣所得到的1模量和2模量的值。通過表1可知,運用該相模變換矩陣得到的模量?83?表1各種故障類型下的電流量模值故障類型邊界條件1模量2模量BGib=ic=0iaiaBGia=ic=02ib-3ibCGia=ib=0-3ic2icABic=0,ia=-ibib-4ibBCia=0,ib=-ic5ib-5ibCAib=0,ia=-ic4ia-iaABGic=0ia+2ibia-3ibBCGia=02ib-3ic2ic-3ibCAGib=0ia-3icia+2IcABCia+ib+ic=0ia+2ib-3icia-3ib+2ic值在所有類型故障下均為非零值,即1模量和2模量均能單獨反映所有類型故障[13],因此可以任意選取其中之一作為仿真分析對象。2提升小波變換提升小波于1996年由Sweldens提出,其算法的基本思想是,將現(xiàn)有的小波濾波器分解成基本的構造模塊,分步驟完成小波變換[14]。傳統(tǒng)的小波都可以找到等效的提升方案。如圖1,由提升算法構成的小波變換過程可以分為以下3個階段。圖1提升算法的分解和重構(1分解。將輸入信號Si分為兩個子集Si-1和di-1,最簡單的方法是按奇偶性分,分解過程F(Si=(Si-1,di-1;(2預測。在基于原始數(shù)據(jù)相關性的基礎上,用偶數(shù)序列Si-1的預測值去預測奇數(shù)序列di-1,即將濾波器P對偶數(shù)信號作用后作為奇數(shù)信號的預測值,奇數(shù)信號的實際值與預測值相減得到殘差信號,重復分解和預測過程,經(jīng)n步后原信號集可用{Sn,dn,…,S1,d1}來表示;(3更新。更新的基本思想是找出一個更好的子數(shù)據(jù)集Si-1,使之保持原始數(shù)據(jù)集的一些特性。構造一個更新算子U,Si-1=Si-1+U(di-1。綜上所述,提升算法可以實現(xiàn)原位運算,在每個點都可以用新的數(shù)據(jù)流替換舊的數(shù)據(jù)流。當重復使用原位提升濾波器組時,即可得交織的小波變換系數(shù)。電力暫態(tài)信號分析處理中的小波基的選擇目前主要傾向于經(jīng)驗性選擇。因為對故障暫態(tài)信號進行研究需要提取的是非平穩(wěn)信號的瞬時、突變成分,即提取有限頻帶上的信息,所以在小波基的選取上,需要考慮其在時、頻兩域的緊支撐性和帶通濾波性能,又為了能準確檢測出信號中的奇異點,該小波函數(shù)必須具有正則性[7、15]。綜合考慮,這里選擇db4小波作為提升小波的小波基。圖2仿真模型3算例仿真為了驗證所提出的算法,用Matlab/Simulink建立一個500kV雙電源系統(tǒng)模型,如圖2。設定仿真時間為0.05s,采樣頻率為1MHz,分布參數(shù)線路PM、MN、NQ的長度皆為300km,故障起始時間為0.025s,接地電阻為10Ω,線路參數(shù)為R1=0.01273Ω/kmR0=0.3864Ω/kmL1=0.9337×10-3H/kmL0=4.1264×10-3H/kmC1=12.74×10-3μH/kmC0=7.751×10-3μH/km以線路MN為研究對象,其區(qū)內(nèi)故障點為f。先以A相單相接地故障為例,設定故障點f距母線M端45km,運行仿真可得M端和N端的1模量暫態(tài)電流波形及其高頻小波系數(shù)如圖3所示。再以CA兩相相間短路為例,設定故障點f距母線M端135km,運行仿真可得M端和N端的1模量暫態(tài)電流波形及其高頻小波系數(shù)如圖4所示。測距算法采用不受波速影響的雙端行波測距[5]。故障距離采用以下公式進行計算。X=(t2-t1×l2(t3-2t1+t2(3其中l(wèi)為線路全長,t1為故障初始行波從故障點?93?到達測量端母線的時刻,t2為故障點反射波到達測量端母線的時刻,t3為故障初始行波從故障點到達對端母線的時刻。分別對M、N兩端的提升小波系數(shù)進行測量得到3個波頭的時間,再代入式(3計算可得測距結果。以上兩個例子的仿真結果如表2所示,可見該算法能夠比較準確地確定故障地點。為了進一步驗證該算法,表3給出了各種類型故障下分別采用提升小波和普通小波所得的部分測距結果。通過比較可以看出,采用提升算法后大多數(shù)故障測距結果精度比普通小波測距高,能夠滿足精確故障定位的要求。表2算例的仿真結果故障t1/mst2/mst3/msX/kmε/kmAG45km25.15725.46725.88344.8840.116CA135km25.46926.39925.571135.1740.174注:ε為絕對誤差,其他符號意義同式(3。圖31模量波形及其提升小波變換(45km,A相圖41模量波形及其提升小波變換(135km,CA相間表3各種故障類型下的仿真故障類型故障仿真距離/km提升小波測距/km絕對誤差/m普通小波測距/km絕對誤差/m單相接地短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271兩相相間短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271兩相接地短路4040.0686839.99919090.0585890.231231180180.0000179.97129220220.0000219.93268280280.271271280.271271三相接地短路40280.271271280.271271?04?4結論針對傳統(tǒng)相模變換矩陣的不足,提出了一種采用新的相模變換矩陣,并結合提升小波的故障測距改進算法。通過分析與仿真得出以下結論:所提出的算法,不僅能反映所有類型的故障,減小計算的工作量,而且相較于普通小波測距,多數(shù)情況下測距結果精度較高。參考文獻[1]陳平,葛耀中,索南加樂,等.基于故障開斷暫態(tài)行波信息的輸電線路故障測距研究[J].中國電機工程學報,2000,20(8:56-59,64.[2]覃劍,陳祥訓,鄭健超,等.利用小波變換的雙端行波測距新方法[J].中國電機工程學報,2000,20(8:6-10.[3]李友軍,王俊生,鄭玉平,等.幾種行波測距算法的比較[J].電力系統(tǒng)自動化,2001,(14:36-39.[4]蔣濤,陸于平.不受波速影響的輸電線路單端行波故障測距研究[J].電力系統(tǒng)自動化,2004,24(12:29-32.[5]李澤文,曾翔君,徐小箐,等.輸電線路雙端行波故障定位新算法[J].電力系統(tǒng)自動化,2006,30(15:40-43.[6]董杏麗,葛耀中,董新洲,等.基于小波變換的行波測距式距離保護原理的研究[J].電網(wǎng)技術,2001,25(7:9-13.[7]熊小伏,林金洪.基于小波重構的電力電纜故障測距方法[J].電網(wǎng)技術,2003,27(6:36-38.[8]范春菊,張兆寧,郁惟鏞.小波方法在超高壓輸電線路故障測距中的應用[J].電網(wǎng)技術,2003,27(8:50-53.[9]黃雄,王志華,尹項根等.高壓輸電線路行波測距的行波波速確定方法[J].電網(wǎng)技術,2004,28(19:34-37.[10]覃劍,葛維春,邱金輝,等.影響輸電線路行波故障測距精度的主要因素分析[J].電網(wǎng)技術,2007,31(2:28-35.[11]徐丙垠.利用暫態(tài)行波的輸電線路故障測距技術[D].西安:西安交通大學,1991.[12]王安定,葛耀中.模量變換技術在反應故障分量的微機保護中的應用研究[J].電力系統(tǒng)自動化,1988,12(3:17-27.[13]宋國兵,李森,康小寧,等.一種新相模變換矩陣[J].電力系統(tǒng)自動化,2007,31(14:57-60.[14]葛哲學,沙威.小波分析理論與MATLAB7實現(xiàn)[M].北京:電子工業(yè)出版社,2005.3.[15]MognagoFH,AburA.Faultlocationusingwavelets[J].IEEETrans.OnPWRD,1998,13(4:1475-1480.作者簡介:郭亮(1982-,男,碩士研究生,從事電力系統(tǒng)繼電保護研究。呂飛鵬(1968-,男,博士,教授,從事電力系統(tǒng)繼電保護和故障信息處理智能系統(tǒng)研究。羅長亮(1983-,男,碩士研究生,從事電力系統(tǒng)繼電保護研究。蔣科(1983-,男,碩士研究生,從事電力系統(tǒng)繼電保護研究。李鵬飛(1981-,男,碩士,從事電力系統(tǒng)繼電保護研究。(收稿日期:2021-09-01(上接第25頁一級母線接地判斷方式為:二級支路均無不平衡電流但一級母線傳感器有不平衡電流;由于母線和負荷支路同時接地的情況非常少,所以可以只定義為上述方式,并且多個繼電器室發(fā)生多負荷支路接地時,絕緣監(jiān)測裝置仍可上傳信號。4結束語通過對變電站直流系統(tǒng)接地告警方式的設計,可以使運行人員直觀地監(jiān)視到直流系統(tǒng)故障狀況,鎖定故障點,及時排除故障,當然由于直流饋線并未最終的負荷端,運行人員可以繪制更為詳細的二級接線圖,以方便下級支路的查找。參考文獻[1]賈秀芳.直流系統(tǒng)絕緣監(jiān)測綜合判據(jù)[J].電力系統(tǒng)自動化,1999,23(16:47-49.作者簡介:李俊儒(1982-,女,助理工程師,德陽電業(yè)局。劉玲(1982-,女,助理工程師,德陽電業(yè)局。賴民昊(1981-,男,助理工程師,成都電業(yè)局。(收稿日期:2021-07-08?14?第36卷第9期2006年9月數(shù)學的實踐與認識Vol.36No.9Sep.,2006用矩陣和積求最短路的一種新算法詹棠森,張三強,唐敏(景德鎮(zhèn)陶瓷學院信息工程學院,江西景德333001)摘要:先定義了矩陣和積的概念和運算,在求最短路中,這種方法和線性代數(shù)中的矩陣運算相似,通過這種方法,把求最短路轉化為矩陣的運算,計算簡便,有效.關鍵詞:最短路;矩陣和積;多階段決策;不完全關聯(lián);距離陣1引言求最短路的方法很多,有動態(tài)規(guī)劃的多階段決策方法[1],在動態(tài)規(guī)劃算法中,利用問題的最優(yōu)子結構性質,以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解,而Disjkstra算法是解單源最短路徑問題的貪心算法,其基本思想是設置頂點集合S并不斷地做貪心選擇來擴充這個集合[2,3].等.2定義矩陣和積及運算1)符號意義表示和運算⊕表示或運算[4,5]2⊕3表示2和32)運算形式和運算律交換律ab=ba分配律a(b⊕c=)(ab)⊕(ac)例23=32=5,2(3⊕4)=(23)⊕(24)=5⊕6.記∞(a⊕b⊕…⊕c=(∞).3)兩矩陣和積的算法設矩陣Am×s=(aij)m×s,Bs×n=(bij)s×nAm×sBs×n=Cm×n=(cij)m×n其中cij=s∑k=1⊕aikbkj=ai1b1j⊕…⊕aisbsj.3構造多階段決策最短路算法1.完全關聯(lián)的多階段問題及距離陣多階段的決策問題的特點是先將一個復雜問題分解成相互聯(lián)系的若干階段,每一個階段的點(事件點)與后一階段的點完全相互聯(lián)系,這種問題稱為完全關聯(lián)的多階段問題.[6]9期詹棠森,等:用矩陣和積求最短路的一種新算法171如右圖1B1C2=7,B1C3=4B2C1=3,B2C3=2B3C1=5,B3C2=1對于四個階段的決策問題,若第一階段只有一個點,第二,三,四階段分別有n,m,1個點.構造矩陣,矩陣的元素由這些距離組成第1,2,3階段的矩陣為k=A2以kk為列向量構成權矩陣(2)(2)(2)W(2)=(k1,k2,…,kn)(1)(1)1,k1,…k1)=(k(1)(2)(n)T(2)(2)(2)(2)Tkk=(kk1,kk2,…,kkm),k=1,2,…n[7].圖1W(1)W(s-1)W(s-2)W(2)k.(3)=(k1,k2,…,km)(3)(3)(3)(3)(1)(s-1)最后得A到T的距離行陣(或稱為權陣)k=W(3)W(2)k更一般S階段的距離為k=2.求A到T的最短路按上圖1,利用上面計算權重的方法,可得6k=(6,3,2)7(3)32=(12⊕10⊕6,9⊕5⊕4,11⊕4⊕6)42=14⊕12⊕8⊕12⊕8⊕7⊕15⊕8⊕10從這些數(shù)字中,我們很快找到A到T最短路是7,并按逆推過程可得取得最短路徑是A→B2→C3→T,從中可看出距離為8的有3條,距離為10,14,15的各一條,距離為12的有二條.A到T最長距離為15,且路徑是A→B