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

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

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

1 解決TSP問題的相關算法

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

1.1 遺傳算法

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

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

1.2 模擬退火算法

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

圖1 模擬退火算法偽程序

1.3 蟻群算法

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

圖2 蟻群算法流程圖

2 實例分析

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

圖3 遺傳算法仿真結果圖

圖4 模擬退火算法仿真結果圖

圖5 蟻群算法仿真結果圖

圖6 遺傳算法仿真結果圖

圖7 模擬退火算法仿真結果圖

圖8 蟻群算法仿真結果圖

圖9 遺傳算法仿真結果圖

圖10 模擬退火算法仿真結果圖

圖11 蟻群算法仿真結果圖

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

表1 種不同算法的仿真結果對比

3 結語

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