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

王 帥 孫曉偉 劉家旭 劉 洋

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

（2.中國(guó)礦業(yè)大學(xué)煤炭資源與安全開(kāi)采國(guó)家重點(diǎn)實(shí)驗(yàn)室 徐州 221116）

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

2.2 模型構(gòu)建

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

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

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

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

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

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

圖1 障礙物柵格圖

3 蟻群算法原理

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

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

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

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

4 改進(jìn)蟻群算法

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

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

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

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

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

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

4.2 改進(jìn)信息素?fù)]發(fā)系數(shù)

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

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

5 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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