基于改進蟻群算法的光纖光纜鋪設路徑規劃?

王 帥 孫曉偉 劉家旭 劉 洋

（1.青島科技大學信息科學技術學院 青島 266061）

（2.中國礦業大學煤炭資源與安全開采國家重點實驗室 徐州 221116）

1 引言

近些年來，由于科技進步，電力通訊行業發展迅速，當今社會對電力通信的需求也越日益增加，光纖光纜［1］成為了電力通信的主要部分，所以對光纖光纜的路徑規劃問題是最先需要解決的，要合理地規劃路徑，使前期便于光纖光纜布設后期維護方便，同時還要兼顧其成本。光纖光纜鋪設有架空和地線傳輸等幾種鋪設方式，根據不同地形合理布設不同類型的光纖光纜，蟻群算法［2］是一種啟發式的仿生優化算法，由Dorigo 等提出［3］，主要為了搜尋螞蟻窩和食物之間的距離最小的路徑［4］。因此我們能夠將蟻群算法應用于光纖光纜的鋪設路徑當中。蟻群算法不但與別的算法更好搭配［5］，也有精確度高、運行速度快［6］等優點，但同時也存在迭代時間長次數多，隨機性高，死鎖概率高等弊端，使其在尋優過程中還有進步的空間。所以應該改良基礎蟻群算法來改善上述問題。

對路徑規劃問題，相關研究人員做了很多工作，獲得了優異的成績。陳鑫等［7］為了增強無人機的安全飛行性能，首先，提取地形地貌特征點作為無人機飛行航跡點，將航跡規劃問題轉化為旅行商問題。其次，提出了一種自適應信息素更新方法和局部信息素的改進蟻群算法，實驗顯示改進后的蟻群算法具有實用性和優越性，有效地解決無人機路線規劃的問題。但是，優化過程中仍有收斂時間過久的問題。劉學芳［8］通過建立信息素矩陣，分別加入激勵函數，改進信息素更新方式，用不同的刺激情況分析信息素和揮發系數對算法的影響，最后提出全局性人工勢場算法。但是該算法對復雜環境的適應性仍需提高。貝前程等［9］提出了自適應度函數，在不改變蟻群初始參數的條件下，通過改進蟻群啟發函數改進蟻群算法，改良后的蟻群算法收斂速度較快，路徑距離較小，但是最終的仿真結果仍然存在迭代次數過多的問題，并且該實驗僅在一種環境下進行，缺少對比試驗。

結合以上算法的結果分析，對蟻群算法改進以下方面。首先運用柵格法構建光纖光纜鋪設圖，找出當前點與終點的連線h1跟當前點與下個節點的連線h2的角度差?，根據角度差?的大小，引入環境因子A 來調整啟發函數，提高了螞蟻搜索的目的性，解決了隨機性強的弊端。其次通過改進揮發系數的揮發機制，使剛開始揮發系數較大，增加初始階段螞蟻搜索全局性［10］，到收斂后期，伴隨迭代次數的增多，揮發系數慢慢減小，不僅避免了算法的停滯，而且使算法的迭代速度增加，從而得到最優解。

2 問題描述及環境建模

2.1 問題描述

本文光纖光纜的鋪設路徑規劃問題可以描述為從起始點開始通過地下或架空的方式向目標點布設光纖光纜，該路徑要避免與地上和地下建筑物沖突，同時要兼顧工程成本和完成質量，則必須合理地規劃光纖光纜布設路線。

2.2 模型構建

光纖光纜鋪設路徑規劃系統對于大型建筑物以及周圍植被山川河流是已知的，這時可以把建筑物、植被、河流、山川統一視作光纖光纜鋪設地圖的障礙物，光纖光纜到障礙物的不同距離對動態光纖光纜鋪設路徑規劃系統的影響不同，光纖光纜到障礙物的距離見表1。

表1 光纖光纜到障礙物距離對鋪設的影響

2）光纖光纜到各障礙物距離可行參數不能超過1且之和不能超過4。

3）所有基站都必須連接完畢。

因此，本文光纖光纜鋪設最優路徑目標值為

運用柵格法構建光纖光纜鋪設的地圖，如圖1所示，淺色柵格意為該柵格可鋪設，深色柵格意為該柵格不可鋪設。

圖1 障礙物柵格圖

3 蟻群算法原理

α是該算法的信息素因子［13］，代表著（i，j）這條路徑上信息素的重要程度。β是該算法的期望啟發函數因子［14］，dk為螞蟻k 未訪問的節點集合，τij、τis分別為路徑（i，j）、（i，s）上的信息素濃度，ηij、ηis分別為從i 點到j 點和s 點的啟發式因子［15］，公式為

其中dij、dis是i點到j和s點的最短直線距離，其公式為

Q 是信息素增強系數［21］，是常數，該系數能左右算法的收斂速度。Lk是螞蟻k 經過每一個節點所走的路線長度。

在未訪問之前，節點間的初始信息素相等，在螞蟻走完每個節點之后，會重新更新該路線上的信息素，根據蟻周模型運算每個螞蟻發出的信息素，算出增加的信息素大小。與此同時也要考慮揮發的信息素大小，通過運算得到最終的信息素量。由于螞蟻對下一節點的轉移概率受啟發式因子和更新信息素共同影響，因此也要考慮啟發式因子對轉移概率的影響，兩者共同作用指導螞蟻到達目標點。然后進行數次循環，得到最優解。

4 改進蟻群算法

4.1 改進啟發函數

路徑規劃初始階段，螞蟻會通過輪盤賭的形式選取下一節點，由于螞蟻不清楚目標點的具體位置，這會造成螞蟻在找尋路徑時，表現得不知所措，隨機性比較強，增加了收斂時間，針對這個問題我們對啟發函數進行調整，引入環境因子A，使得目標點對螞蟻有一個向導作用，具體方法如下：

假設螞蟻在i 點，下一個要到的節點為j，目標點為e。i點與下一個要訪問的節點j之間的角度為θij，θij的取值范圍為｛0，45，90，135，180，-135，-90，-45｝，i點與目標點e的夾角為γie：

此時引入環境因子A，對啟發函數按下式進行調整。當?在區間（-45，45）時，則A≤1。當?在區間（-45，45）以外時，A ＞1。更有利于算法的調整，如下式：

當角度?在設置的范圍區間（-45，45）時，說明螞蟻k 在朝著目標點的方向前進，此時環境因子A≤1，螞蟻在訪問下一節點時朝該方向前進的幾率會越來越高，反之亦然。

此時狀態轉移函數為

4.2 改進信息素揮發系數

隨算法循環次數增加，路線上的信息素會揮發減小，用ρ來表示，揮發系數ρ的高低會左右搜索能力和運行時間。假如ρ太小，說明揮發速度很慢，導致螞蟻重復選擇已經訪問的路線，改變全局搜索能力。反之ρ太大，導致收斂時間過長。所以本文找到隨迭代次數大小進行調整的信息素揮發系數關系式，如下式：

K 為螞蟻迭代次數，B 為一個常數。在算法初級階段為了快速得到最優解，提高蟻群的搜尋能力，ρ的取值應該比較大；到了后期，隨著迭代次數越來越大，揮發系數ρ的取值慢慢變小，減小了信息素對蟻群的影響，防止了算法停滯不前，減少了收斂時間，從而取得更優的解。

5 仿真實驗與分析

本實驗在Matlab R2018a 平臺下，構建簡單環境和復雜環境兩種實驗環境，文中設置兩個路徑規劃環境分別為20×20 個柵格的簡單環境，障礙物比較少；30×30個柵格的復雜環境，障礙物比較多。

實驗一建立一個20×20 的隨機柵格地圖環境，圖2 所示。該蟻群算法的參數設置：螞蟻的個數m為50，迭代次數100 代，初始信息素揮發系數ρ為0.4，α為1，β為5，Q為1，A取0.9或1.1，B為0.4。

圖2 簡單環境下兩種蟻群算法路徑軌跡對比

兩種算法在簡單環境下進行50 次實驗，并分別記錄路線長度與迭代數目，算出平均路徑長度，從圖3 可以看出，迭代數目明顯減少，且收斂速度更快，由表2 得到平均路徑長度減少1.5297m，迭代次數減少24 次，收斂時間減小了16.78s，路徑長度得到減小，迭代次數相比于未改進的也減少了很多。

圖3 簡單環境下兩種蟻群算法收斂曲線對比

表2 簡單環境下兩種蟻群算法對比

實驗二，現實光纖布設情況比較復雜，簡單環境下光纖鋪設軌跡路徑并不能反映改進蟻群算法的適應性，因此構造一個30×30 復雜環境的隨機柵格地圖，如圖4 所示，該蟻群算法參數設置：螞蟻的個數m 為50，迭代次數100 代，初始信息素揮發系數ρ為0.4，α為1.4，β為5，Q為1，A取0.9或1.1，B為0.4。

圖4 復雜環境下兩種蟻群算法路徑軌跡對比

兩種算法在該復雜環境下進行50 次實驗，并分別記錄路線長度和迭代數目，算出平均路徑長度。從圖5 可以看出，迭代數目明顯減少，且收斂速度更快，由表3 可以得到，復雜環境下，平均路徑長度減少了3.936m左右，迭代次數減少了69次，收斂時間減少了3.44s左右，路徑長度得到減小，迭代次數相比于未改進的也減少了很多，并且能很好地適應復雜環境。

圖5 復雜環境下兩種蟻群算法收斂曲線對比

表3 復雜環境下兩種蟻群算法對比

6 結語

本文從光纖光纜鋪設路徑優化問題出發，結合改進蟻群算法，來求得鋪設過程中最優路徑問題，文中引入環境因子來調整啟發函數，降低了螞蟻搜尋的盲目性，解決了隨機性強的弊端。通過改變信息素揮發系數，增加初始階段螞蟻搜索的全局性，使收斂次數明顯減少。最后仿真結果顯示，改進后的蟻群算法，收斂速度明顯增加，具有較強的路徑搜索能力和適應能力，使光纖光纜的鋪設成本大大降低。