基于蟻群算法的光纜巡檢最短路徑規(guī)劃研究

國網(wǎng)湖北省電力有限公司恩施供電公司 李 鋒 趙 芳 湖北民族大學(xué)信息工程學(xué)院 王新磊 鐘建偉

電力系統(tǒng)通信是電力系統(tǒng)的重要組成部分，是電網(wǎng)智能調(diào)度、生產(chǎn)管理現(xiàn)代化，以及保障電網(wǎng)安全、穩(wěn)定、經(jīng)濟(jì)運(yùn)行的基礎(chǔ)。電力通信光纜承載著電力系統(tǒng)通信的安全穩(wěn)定運(yùn)行，因此，為了保證光纜的可靠性，定期對光纜進(jìn)行巡檢是重中之重［1］。每個地區(qū)都有多個巡檢點(diǎn)需要檢查，巡檢人員需要遍歷每一個巡檢地點(diǎn)，因此為了提高巡檢效率，要盡可能地保證巡檢人員到達(dá)所有巡檢點(diǎn)時經(jīng)過的路線最短。此問題明顯是一個的旅行商問題（Travelling salesman problem,TSP），已經(jīng)有很多解決方法［2-4］。本文將主要用蟻群算法和遺傳算法、模擬退火算法對比，以三個巡檢點(diǎn)數(shù)目不同的地區(qū)為實(shí)例，結(jié)果表明蟻群算法在求解質(zhì)量和收斂速度上都具有優(yōu)越性。

1 解決TSP問題的相關(guān)算法

TSP問題的解決方法有很多，本節(jié)主要介紹遺傳算法、模擬退火算法與蟻群算法解決巡檢最短路徑規(guī)劃問題的步驟。

1.1 遺傳算法

遺傳算法以“物競天擇，適者生存”為算法進(jìn)化原則，結(jié)合生物進(jìn)化過程，通過遺傳、交叉、變異、自然選擇等操作找到適應(yīng)度高的解，其解決巡檢最短路徑規(guī)劃問題的步驟如下：

步驟一：初始種群。設(shè)置巡檢點(diǎn)個數(shù)、種群數(shù)量、最大迭代次數(shù)、交叉概率、變異概率、迭代次數(shù)等參數(shù)，隨機(jī)生成初始種群；步驟二：個體評價。寫出適應(yīng)度函數(shù)，本文的目標(biāo)是巡檢距離最短，巡檢距離越短，適應(yīng)度越高；步驟三：選擇運(yùn)算。將選擇算子作用于群體，把適應(yīng)度最高的個體選擇出來；步驟四：交叉運(yùn)算。這是遺傳算法的核心，能夠防止過早陷入局部最優(yōu)；步驟五：變異運(yùn)算。由之前設(shè)置好的變異概率值進(jìn)行變異操作。群體經(jīng)過步驟三至五后，得到下一代群體；步驟六：終止條件判斷。在達(dá)到最大迭代次數(shù)時，適應(yīng)度最高的個體即為最優(yōu)解，即可求出最短路徑。

1.2 模擬退火算法

本小節(jié)利用偽程序表示模擬退火算法求解巡檢最短路徑規(guī)劃問題的過程，如圖1所示：

圖1 模擬退火算法偽程序

1.3 蟻群算法

蟻群算法解決巡檢最短路徑規(guī)劃問題的流程圖如圖2所示：

圖2 蟻群算法流程圖

2 實(shí)例分析

不同地區(qū)光纜巡檢點(diǎn)數(shù)量有所差別，本文分別選取湖北省恩施州3個不同地區(qū)（分別有待巡檢點(diǎn)12、32、50個）進(jìn)行最短路徑規(guī)劃，實(shí)驗(yàn)結(jié)果如下：地區(qū)一12個待巡檢點(diǎn)，圖3～圖5；地區(qū)二32個待巡檢點(diǎn)，圖6～圖8；地區(qū)三50個待巡檢點(diǎn)，圖9～圖11。三種不同算法的仿真結(jié)果對比見表1。

圖3 遺傳算法仿真結(jié)果圖

圖4 模擬退火算法仿真結(jié)果圖

圖5 蟻群算法仿真結(jié)果圖

圖6 遺傳算法仿真結(jié)果圖

圖7 模擬退火算法仿真結(jié)果圖

圖8 蟻群算法仿真結(jié)果圖

圖9 遺傳算法仿真結(jié)果圖

圖10 模擬退火算法仿真結(jié)果圖

圖11 蟻群算法仿真結(jié)果圖

從表1可以看出，隨著城市數(shù)量的增加，遺傳算法的迭代次數(shù)明顯增加，在仿真過程中模擬退火算法的程序執(zhí)行時間明顯最長。在32和50個巡檢點(diǎn)時，蟻群算法求解出的最短路徑都是最小的，即求解質(zhì)量高。同時蟻群算法的迭代次數(shù)一直都是最少的，即收斂速度最快。

表1 種不同算法的仿真結(jié)果對比

3 結(jié)語

光纜巡檢最短路徑的規(guī)劃是巡檢工作中的重要一環(huán)，本文提出的一種基于蟻群算法的光纜巡檢最短路徑規(guī)劃方案可為解決此問題提供參考。由湖北省恩施州三個不同地區(qū)的實(shí)例分析，遺傳算法迭代次數(shù)多，模擬退火算法程序執(zhí)行時間過長，而隨著巡檢點(diǎn)增加蟻群算法求解質(zhì)量高、收斂速度快的優(yōu)勢體現(xiàn)的更加明顯。不過，算法間可以相互融合、也可與其他啟發(fā)式算法融合，改善算法的性能。