基于改進蟻群算法的光纖光纜鋪設(shè)路徑規(guī)劃?

王 帥 孫曉偉 劉家旭 劉 洋

（1.青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院 青島 266061）

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

1 引言

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

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

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

2 問題描述及環(huán)境建模

2.1 問題描述

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

2.2 模型構(gòu)建

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

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

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

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

因此，本文光纖光纜鋪設(shè)最優(yōu)路徑目標(biāo)值為

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

圖1 障礙物柵格圖

3 蟻群算法原理

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

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

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

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

4 改進蟻群算法

4.1 改進啟發(fā)函數(shù)

路徑規(guī)劃初始階段，螞蟻會通過輪盤賭的形式選取下一節(jié)點，由于螞蟻不清楚目標(biāo)點的具體位置，這會造成螞蟻在找尋路徑時，表現(xiàn)得不知所措，隨機性比較強，增加了收斂時間，針對這個問題我們對啟發(fā)函數(shù)進行調(diào)整，引入環(huán)境因子A，使得目標(biāo)點對螞蟻有一個向?qū)ё饔茫唧w方法如下：

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

此時引入環(huán)境因子A，對啟發(fā)函數(shù)按下式進行調(diào)整。當(dāng)?在區(qū)間（-45，45）時，則A≤1。當(dāng)?在區(qū)間（-45，45）以外時，A ＞1。更有利于算法的調(diào)整，如下式：

當(dāng)角度?在設(shè)置的范圍區(qū)間（-45，45）時，說明螞蟻k 在朝著目標(biāo)點的方向前進，此時環(huán)境因子A≤1，螞蟻在訪問下一節(jié)點時朝該方向前進的幾率會越來越高，反之亦然。

此時狀態(tài)轉(zhuǎn)移函數(shù)為

4.2 改進信息素揮發(fā)系數(shù)

隨算法循環(huán)次數(shù)增加，路線上的信息素會揮發(fā)減小，用ρ來表示，揮發(fā)系數(shù)ρ的高低會左右搜索能力和運行時間。假如ρ太小，說明揮發(fā)速度很慢，導(dǎo)致螞蟻重復(fù)選擇已經(jīng)訪問的路線，改變?nèi)炙阉髂芰Α７粗烟?，?dǎo)致收斂時間過長。所以本文找到隨迭代次數(shù)大小進行調(diào)整的信息素揮發(fā)系數(shù)關(guān)系式，如下式：

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

5 仿真實驗與分析

本實驗在Matlab R2018a 平臺下，構(gòu)建簡單環(huán)境和復(fù)雜環(huán)境兩種實驗環(huán)境，文中設(shè)置兩個路徑規(guī)劃環(huán)境分別為20×20 個柵格的簡單環(huán)境，障礙物比較少；30×30個柵格的復(fù)雜環(huán)境，障礙物比較多。

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

圖2 簡單環(huán)境下兩種蟻群算法路徑軌跡對比

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

圖3 簡單環(huán)境下兩種蟻群算法收斂曲線對比

表2 簡單環(huán)境下兩種蟻群算法對比

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

圖4 復(fù)雜環(huán)境下兩種蟻群算法路徑軌跡對比

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

圖5 復(fù)雜環(huán)境下兩種蟻群算法收斂曲線對比

表3 復(fù)雜環(huán)境下兩種蟻群算法對比

6 結(jié)語

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