一種基于改進(jìn)蟻群算法的港內(nèi)尋跺應(yīng)用

摘 要：如何尋找最優(yōu)路徑是港區(qū)內(nèi)交通誘導(dǎo)系統(tǒng)研究解決的核心問題。本文就如何尋找最優(yōu)路徑引入了基于群體仿生理念的改進(jìn)的自適應(yīng)蟻群算法，通過對信息濃度更新規(guī)則加以改進(jìn)來加快收斂，不但能夠降低蟻群算法的時(shí)間復(fù)雜度，還能克服尋找最優(yōu)路徑的難題，為進(jìn)入港區(qū)的外來車輛順利到達(dá)目的地提供了技術(shù)保障。

關(guān)鍵詞：信息素；自適應(yīng)蟻群算法；最優(yōu)路徑

中圖分類號：TP391

1 背景

某港口因管理不善等因素的影響，致使港內(nèi)貨物堆放區(qū)域沒有一定的規(guī)律，造成區(qū)域內(nèi)跺位混亂，比如跺位位置不固定、大小不一，跺號更新變化頻繁，貨種堆放時(shí)間變化不一等一系列問題。這種環(huán)境下，外埠車輛疏港或集港時(shí)，需要先到離貨物堆場最近的磅房過磅（過空或過重），然后再進(jìn)入封閉區(qū)域，根據(jù)理貨員的指引到達(dá)裝卸現(xiàn)場跺位處，裝載機(jī)才能對其進(jìn)行作業(yè)。由于汽運(yùn)司機(jī)大多來自外地，不經(jīng)常進(jìn)港，對港內(nèi)環(huán)境陌生，他們經(jīng)常忙無目的的在港內(nèi)亂跑，等真正找到跺位后，已經(jīng)浪費(fèi)了很多時(shí)間和油耗，這對他們造成了很大的困擾，也對港口的管理帶來了諸多不便。為了解決這個(gè)問題，我們可以采用現(xiàn)代化智能技術(shù)進(jìn)行管理，開發(fā)相應(yīng)的軟件系統(tǒng)，來提升港口的管理水平和效益。

近些年來，隨著群智能技術(shù)的逐漸成熟，我們可以將群智能技術(shù)引入到蟻群算法中，從而為最優(yōu)路徑選擇問題提供了一個(gè)全新的解決思路。但在實(shí)際應(yīng)用過程中，蟻群算法有它本身的局限性，其道路信息素初始值是固定的，使得這種算法在收斂過程中速度較慢。為了克服這個(gè)難題，我們可以在蟻群算法中引入改進(jìn)的自適應(yīng)蟻群算法，對信息濃度更新規(guī)則進(jìn)行改進(jìn)以加快收斂速度，并根據(jù)平均節(jié)點(diǎn)分支數(shù)動態(tài)地調(diào)整轉(zhuǎn)移概率，這樣就可以在很大程度上提高算法搜索最優(yōu)解的能力。

2 具體解決措施

在辦卡大廳，設(shè)立一臺觸摸屏，屏幕內(nèi)植入港區(qū)內(nèi)電子地圖，汽運(yùn)客戶在掃描派車單后，系統(tǒng)便可根據(jù)派車單信息自動搜尋出從入港大門到達(dá)指定跺位區(qū)域所經(jīng)過的最優(yōu)路徑，客戶打印最優(yōu)路徑單后，便可順利駕駛車輛到達(dá)目的地，這極大的滿足了客戶的需求，提高了港口吞吐效率。

3 算法模型選擇

對最優(yōu)路徑的選擇，我們將一種改進(jìn)的蟻群算法引入到路徑選擇中來。

3.1 蟻群算法的來源

蟻群算法是一種啟發(fā)式搜索算法，它是模擬自然界螞蟻覓食行為而生成的算法，智能化程度比較高，它以離散時(shí)空、具有一定記憶功能的人工螞蟻替代真實(shí)自然界的螞蟻。蟻群算法中最重要的環(huán)節(jié)就是信息素的產(chǎn)生、增長和尋覓。螞蟻在沿路徑尋找食物時(shí)，下意識的會在所爬行的路線上分泌留下一種特殊的物質(zhì)，我們稱這種物質(zhì)為信息素。其它螞蟻可以利用前面螞蟻留下的信息素來確定下一步要走的路線，同時(shí)根據(jù)這些路線上信息素強(qiáng)弱并行的去跟蹤爬行尋找食物。為了確定蟻穴和食物位置之間的距離遠(yuǎn)近，一般根據(jù)爬行的次數(shù)來衡量是否是最優(yōu)路徑。大多數(shù)螞蟻會選擇近的有信息素的路徑爬行，久而久之，近的路徑上螞蟻爬行的次數(shù)會逐漸增多，自然而然的這種路徑上的信息素濃度就會隨之增大，被其他螞蟻選中的概率也會增大，這樣，通過帶頭螞蟻的隨機(jī)爬行，到多數(shù)螞蟻集中到最優(yōu)路徑上爬行，后邊的螞蟻便得到了最優(yōu)尋食路徑。因此，我們可以將蟻群算法應(yīng)用到港區(qū)內(nèi)尋垛路徑優(yōu)化問題中。

3.2 改進(jìn)算法

針對上述蟻群算法的優(yōu)缺點(diǎn)，我們提出了改進(jìn)算法，主要是圍繞選擇概率模型和信息素問題進(jìn)行改進(jìn)。

3.2.1 首先將港口大門初始化，配備好相關(guān)設(shè)備，再就是將所有過磅房間初始化并配備相關(guān)設(shè)備。同時(shí)，將區(qū)域卡口封閉，各跺位重心點(diǎn)、出港大門口以及不同路的十字路口以經(jīng)緯度方式進(jìn)行采集。

3.2.2 根據(jù)需要引入自適應(yīng)蟻群算法（Adaptive Ant Colony Algorithm，簡稱AACA），可以很好的避免算法在執(zhí)行過程中出現(xiàn)的停滯現(xiàn)象。AACA算法跟其它的算法相比，優(yōu)點(diǎn)就是能夠很快的計(jì)算出平均節(jié)點(diǎn)分支數(shù)，并自適應(yīng)的動態(tài)調(diào)整轉(zhuǎn)移概率來達(dá)到最終目的，這樣能夠很大程度上提高算法搜索最優(yōu)解的能力，即使在運(yùn)行后期也能以極大的概率取得最優(yōu)解。

自適應(yīng)蟻群算法在路徑選擇時(shí)使用的是自適應(yīng)偽隨機(jī)比率選擇規(guī)則（adaptive pseudo random proportional action choice rule），在這種算法規(guī)則環(huán)境下，我們可以確保整個(gè)蟻群始終在“搜索”和“利用”之間活動，不會游離到其它的點(diǎn)，很好的避免了停滯現(xiàn)象的出現(xiàn)。我們可以通過對位于節(jié)點(diǎn)i的螞蟻k，按下面公式（1）選擇進(jìn)入下一個(gè)節(jié)j。

（1）

q（λ（t））=λ（t）/N （2）

其中λ（t）∈[2，N]表示第t次迭代時(shí)的平均節(jié)點(diǎn)分支數(shù)ANB，N代表所有的節(jié)點(diǎn)數(shù)，通過公式（2）來看，顯然有 ，其中q為閉區(qū)間[0，1]上一致分布的隨機(jī)數(shù)目，τ（i，u）的節(jié)點(diǎn)i和節(jié)點(diǎn)iu之間的信息素的值，η（i，u）是節(jié)點(diǎn)i和節(jié)點(diǎn)iu間的啟發(fā)因子，β代表啟發(fā)因子的強(qiáng)弱程度。螞蟻在選擇下一個(gè)節(jié)點(diǎn)前隨機(jī)生產(chǎn)q，若q≤q（λ（t）），則說明可以從節(jié)點(diǎn)i遍歷到其它可行的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)能夠使﹛τ（t，u）.ηβ（i，u）﹜的值達(dá)到最大，即下一步要到達(dá)的節(jié)點(diǎn)。若q>q（λ（t）），則按下面公式（3）選擇下一節(jié)點(diǎn)。

公式（3）

從公式（2）中可以看出平均節(jié)點(diǎn)分支數(shù)直接影響函數(shù)q（λ（t））的最終結(jié)果，它們之間形成正比例函數(shù)關(guān)系。當(dāng)自適應(yīng)蟻群算法要出現(xiàn)停滯趨勢時(shí)，q（λ（t））的結(jié)果也會隨之變小，平均節(jié)點(diǎn)分支數(shù)λ（t）的結(jié)果也變小，我們可以利用公式（3）來提高自適應(yīng)蟻群算法的隨機(jī)搜索能力，增大搜索空間。當(dāng)ANB變大接近節(jié)點(diǎn)數(shù)N時(shí)，則按照公式（1）選擇最優(yōu)路徑。通過以上分析來看，自適應(yīng)蟻群算法能夠根據(jù)情況自適應(yīng)地選擇最優(yōu)路徑，既能避免停滯現(xiàn)象的發(fā)生，又能保持較高的搜索能力。

3.2.3 局部信息素的更新辦法

在實(shí)際尋找路徑過程中，螞蟻先從節(jié)點(diǎn)i開始，然后逐步轉(zhuǎn)移到節(jié)點(diǎn)j，這樣在路徑ij上的信息素就會按照公式（4）完成更新。

τν=（1-ζ）.τν+ζ.τ0， 公式（4）

（τ0是常數(shù)，ζ∈（0，1）是可改變的參數(shù)）

3.2.4 全局信息素更新辦法

解決全局最優(yōu)解所屬的邊的選擇問題，我們可以按照公式（5）進(jìn)行信息素的更新。

τu（t+1）=（1-Ρ）*τu（t）+Ρ.Δτugb（t） 公式（5）

（ ，Lgb為全局最優(yōu)解長度值，Ρ∈（0，1）為信息素的蒸發(fā)系數(shù)）

3.2.5 為了加快收斂，我們在此基礎(chǔ)上對局部和全局信息濃度更新規(guī)則進(jìn)行改進(jìn)，改進(jìn)后的算法能夠很大程度上增加全局最優(yōu)解對整個(gè)尋徑過程的影響度。按照公式的計(jì)算方法，在每次迭代后，全局較優(yōu)的k個(gè)解所在路徑上的信息素濃度會得到及時(shí)的更新，具體規(guī)則如下：

公式（6）

（p為信息素?fù)]發(fā)后所剩的濃度值，1-p為揮發(fā)度，k為較優(yōu)解的數(shù)量，Lμ為第μ最優(yōu)的目標(biāo)值，λ為更新系數(shù)）

3.2.6 結(jié)果對比

結(jié)果對比我們可以通過基本蟻群算法和改進(jìn)蟻群算法仿真實(shí)驗(yàn)完成。本仿真實(shí)驗(yàn)采用當(dāng)今流行的高性能數(shù)值計(jì)算軟件Matlab7.0作為編程工具，在操作系統(tǒng)為Windows7的計(jì)算機(jī)上進(jìn)行求解。為了增加實(shí)驗(yàn)的準(zhǔn)確度，我們選用了AS算法和改進(jìn)的AACA算法，這兩種算法各自參數(shù)設(shè)置見下表：

表1 算法參數(shù)設(shè)置

AS算法參數(shù)AACA算法參數(shù)

α β ρ Qβ ξ ρ

1 4 0.45 1002 0.8 0.8

（以上兩種算法中的螞蟻數(shù)都為50，最大迭代次數(shù)為3000次）

表2 CHC14TSP問題的基本蟻群算法和改進(jìn)蟻群算法仿真計(jì)算結(jié)果比較

算法類型平均最優(yōu)解時(shí)間/s實(shí)際最優(yōu)解相對誤差/%

基本蟻群算法40235208303471.674

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

從以上實(shí)驗(yàn)結(jié)果可以清晰的看出，AACA算法相比較AS算法具有更強(qiáng)的發(fā)現(xiàn)較好解的能力，其計(jì)算平均結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于AS算法，并且具有更強(qiáng)的穩(wěn)定性。AACA算法在搜索最優(yōu)解的過程中，ANB雖然在不斷的變化，但總是能保持在一定的水平，能夠動態(tài)調(diào)節(jié)自己的搜索能力，可避免出現(xiàn)停滯現(xiàn)象。從使用時(shí)間方面來看，基本蟻群算法是208s，改進(jìn)的蟻群算法是118s，改進(jìn)后算法對尋到全局最優(yōu)解的時(shí)間少了近一半，相對誤差也會隨之大大減小，全局搜索速度和優(yōu)化性能均得到了明顯提升。

4 結(jié)束語

本文提出了一種改進(jìn)的基于AACA蟻群算法的新思路，通過實(shí)例仿真驗(yàn)證了這種改進(jìn)對蟻群算法在全局優(yōu)化性能的改善方面具有很強(qiáng)的可行性。實(shí)驗(yàn)結(jié)果表明，該算法尋優(yōu)效果好、求解效率高、性能穩(wěn)定，一定會在車輛進(jìn)港尋垛應(yīng)用中取得很好的效果。

參考文獻(xiàn)：

[1]王超.碼頭集卡運(yùn)輸線路的模型研究及設(shè)計(jì)[J].港口科技，2009（11）.

[2]張莉，霍佳震.基于單船裝卸運(yùn)輸模型的集卡配置仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2006（12）.

[3]楊靜蕾.集裝箱碼頭物流路徑優(yōu)化研究[J].水運(yùn)工程，2006（01）.

[4]齊信，楊泰平，段永坤.基于MapX的Dijkstra算法在城市交通查詢中的實(shí)現(xiàn)[J].測繪與空間地理信息，2010（02）.

[5]桑國珍，何小虎.基于自適應(yīng)蟻群算法的研究[J].科技信息，2010（10）.

[6]韓芳，周忠勛，孫毅.基于改進(jìn)雙種群蟻群算法的無功優(yōu)化研究[J].東北電力大學(xué)學(xué)報(bào)，2010（04）.

作者簡介：高江華（1978.10-），男，山東日照人，講師，碩士，研究方向：計(jì)算機(jī)技術(shù)應(yīng)用。

作者單位：日照職業(yè)技術(shù)學(xué)院，山東日照 276826