王培良，張 婷，肖英杰

（1.上海海事大學 商船學院，航運仿真技術教育部工程研究中心，上海 201306；2.山東交通職業(yè)學院 航海學院，濰坊 261206；3.濰坊科技學院，濰坊 262700）

0 引言

上世紀90年代初，意大利學者M.DORIGO等人提出了具有正反饋機制和魯棒性的螞蟻算法，此后國內(nèi)外學者充分利用并優(yōu)化該算法解決諸如旅行商、路徑規(guī)劃等問題，均取得良好效果。同時蟻群算法（Ant ColonyOptimization，ACO）的參數(shù)選取與組合對算法性能的影響問題亦成為專家學者們的研究對象。

王旭[1]通過研究提出蟻群算法與Dijkstra算法相比，搜索近似最優(yōu)路徑的能力更強，時間更快，但地圖離散化未能最優(yōu)。胡啟國[2]通過優(yōu)化信息素更新和狀態(tài)轉(zhuǎn)移規(guī)則，解決了算法容易陷入局部最優(yōu)解的問題，但其旨在優(yōu)化最優(yōu)冗余分配問題。尹宇潔[3]通過研究優(yōu)化啟發(fā)函數(shù)和禁忌表提出，基于蟻群優(yōu)化算法的元胞自動機模型（Cellular Automata，CA）能夠獲得比基于經(jīng)典CA模型更優(yōu)的最佳疏散路徑，但CA的鄰域選擇問題未能優(yōu)化，同時也未能對時間標準進行統(tǒng)一[4]。馮韋韋[5]提出將ACO算法的信息素采用遺傳算法的復制思想進行更新，結(jié)合單一的禁忌規(guī)則，可得到指定個體的最優(yōu)疏散路徑。李東妮[6]將蟻群算與遺傳算法相結(jié)合，加入交叉、變異算子，增加了獲得全局最優(yōu)解的概率?？傊F(xiàn)有研究主要依據(jù)傳統(tǒng)的ACO算法的更新規(guī)則等進行優(yōu)化[7,8]，無法做到參數(shù)的自適應調(diào)整。

鑒于上述[9]，筆者將元胞螞蟻算法與粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）相結(jié)合[10,11]，在同一時間坐標的基礎上[12～15]，對算法參數(shù)進行優(yōu)化設計[16～18]。最終通過仿真，驗證該方法對解決路徑規(guī)劃問題的科學性與有效性。

1 元胞螞蟻算法描述與構(gòu)建

1.1 柵格地圖的描述

傳統(tǒng)ACO算法對旅行商、路徑規(guī)劃等問題進行仿真求解時，均使用四邊形柵格地圖背景，其鄰域使用Moore型，如圖1所示。

其中，灰色為中心元胞即螞蟻當前所在位置，其鄰域元胞可表示為N={s1，s2，…，si}，i∈[1，8]，si∈[0，1]，i和si均取整數(shù)，i表示鄰域元胞編號，si表示鄰域元胞是否被選中，取1時表示被選中。

圖1 moore型鄰域

在使用四邊形柵格地圖進行仿真時，假設柵格的邊長為e，如若當前螞蟻下一步移動的位置選擇極軸方向柵格，則其移動距離為e，但若選擇斜向方向柵格，則移動距離為，如圖2(a)所示。假設螞蟻移動速度v不變，則螞蟻每次移動時所需時間為e/v或者，導致求解時單步運行時間無法確定，時間標準無法統(tǒng)一，從而影響仿真的科學性。

為解決上述問題，筆者研究使用六邊形柵格作為仿真地圖背景。在柵格邊長和螞蟻移動速度均不變的情況下，則螞蟻每次選擇各方向的移動距離均為，如圖2(b)所示，每次移動的時間步長是確定、統(tǒng)一的。同時六邊形柵格能夠有效避免出現(xiàn)與實際情況不符合的“斜向穿墻”現(xiàn)象。柵格地圖中黑色元胞表示障礙物或者邊界。

圖2 四邊形柵格與六邊形柵格對比

因此，以豎直方向為Y軸、原點在左下角的笛卡爾坐標系建立仿真地圖，同時設每個柵格的內(nèi)切圓心為中心坐標點，則仿真地圖網(wǎng)格坐標點（xi，yi）與網(wǎng)格序號i可通過公式進行轉(zhuǎn)換：

其中，Ni為地圖尺寸即每行包含柵格的個數(shù)，ceil為朝正無窮大方向取整函數(shù)，mod為取模（取余）運算函數(shù)。

1.2 算法描述

元胞螞蟻算法表達式為A=（Gm×n，Qm×n，S，Cw，N，R），其中：

A：單蟻元胞模型；

Gm×n：柵格地圖信息矩陣；

Qm×n：信息素矩陣；

m和n表示矩陣的行列數(shù)，m一般與單次迭代螞蟻數(shù)量相同；

S：元胞狀態(tài)，其值為{0，1}，1表示此元胞被占用；

Cw：C為元胞空間，w表示空間維數(shù)，C要從G中獲取，故w取2維；

N：元胞鄰域；

R：元胞規(guī)則，即螞蟻移動的基本依據(jù)，其規(guī)則主要取決于以下三點：

1）所選元胞不能為障礙物或邊界；

2）所選元胞與目的元胞的距離應不大于當前元胞與目的元胞的距離；

3）各備選元胞被選中的概率由信息素計算公式?jīng)Q定，如下式：

其中，（x，y）為某時刻中心元胞在元胞空間中的坐標,a和b表示矩陣的行號、列號，no表示可選元胞編號。

2 基于PSO的參數(shù)優(yōu)化設計

2.1 PSO算法描述

PSO算法是上世紀90年代，學者Eberhart與Kennedy借鑒鳥類的覓食行為，提出一種基于種群的全局隨機優(yōu)化算法。該算法中的每個粒子都為目標問題的可行解，其粒子質(zhì)量優(yōu)劣適應度函數(shù)評價。每個粒子根據(jù)自身及其他粒子的位置信息不斷調(diào)整移動速度，同時調(diào)整移動的方向和距離，從而實現(xiàn)粒子在解空間內(nèi)的全局尋優(yōu)。在算法求解的迭代過程中，粒子通過個體極值和全局極值調(diào)整自身的速度與位置，其公式如下：

其中，V表示粒子速度；X=（X1，X2，X3，… Xn）為D維空間n個粒子組成的種群，分別代表粒子當前位置；ω為慣性權(quán)重；d=1，2，…，D；i=1，2，…，n表示粒子編號；k為當前迭代次數(shù)；Pid為個體極值；Pgd為全局極值；c1和c2為非負常數(shù)，稱為加速度因子；r1和r2為介于[0，1]之間的隨機數(shù)。

同時為了有效克服PSO算法存在的易早熟收斂、后期迭代效率低等缺點，本文節(jié)點遺傳算法中的變異思想，在傳統(tǒng)PSO算法中引入變異操作，即以一定的概率值對重新初始化某些粒子，從而產(chǎn)生自適應變異粒子。

2.2 適應度評價函數(shù)設計

在PSO算法進行參數(shù)優(yōu)化過程中，適應度函數(shù)作為評價所選粒子即元胞螞蟻算法參數(shù)的標準，因此，適應度函數(shù)的設計至關重要。綜合考慮元胞螞蟻算法在求解路徑規(guī)劃時的尋優(yōu)能力、運行時間、收斂速度、穩(wěn)定性等影響因素，筆者設計的適應度函數(shù)如下：

其中，F(xiàn)i（x）為第i個粒子代表的參數(shù)所對應的適應度函數(shù)值；λ1、λ2、λ3、λ4為權(quán)重系數(shù)，且滿足λ1+λ2+λ3+λ4=1；Li（x）表示使用粒子i運算所得的參數(shù)，元胞螞蟻算法搜索最優(yōu)路徑的能力；Lbest表示每次PSO迭代所得到的最優(yōu)路徑的元胞數(shù)量；Si（x）表示使用粒子i運算所得的參數(shù)，元胞螞蟻算法收的斂速度；Nbest為元胞螞蟻算法搜索到當前最優(yōu)路徑時自身的迭代次數(shù)；Nmax為元胞螞蟻的最大迭代次數(shù)；Qi（x）表示使用粒子i運算所得的參數(shù)，元胞螞蟻算法的穩(wěn)定性；Lstd為每次PSO迭代過程中，元胞螞蟻算法搜索到的路徑的方差；Ti（x）表示使用粒子i運算所得的參數(shù)，元胞螞蟻算法的運行時間；Dis表示元每次PSO迭代過程中，元胞螞蟻算法搜索路徑總和。

2.3 參數(shù)優(yōu)化設計流程

元胞螞蟻算法參數(shù)優(yōu)化方法的思想是將參數(shù)作為PSO算法的位置信息進行迭代優(yōu)化求解，將迭代得到的位置信息結(jié)果作為元胞螞蟻算法求解路徑規(guī)劃問題的一個解，并利用適應度函數(shù)對解的性能做出評價，從而引導PSO算法的粒子趨向于適應度值更高位置。其算法步驟如圖3所示。

圖3 算法流程圖

3 仿真結(jié)果及分析

為驗證所構(gòu)建模型的性能，筆者以某大型郵輪的B甲板上的展廳為工程背景進行仿真，計算對比蟻群元胞算法與傳統(tǒng)算法的優(yōu)劣，郵輪B甲板構(gòu)造詳情如圖4所示。

甲板中間位置展廳面積為20m×20m的封閉空間，其構(gòu)造詳情如圖5(a)所示，仿真環(huán)境為20×20的柵格地圖，如圖5(b)所示。

圖4 某郵輪B甲板構(gòu)造圖

圖5 展廳構(gòu)造與仿真圖

3.1 參數(shù)優(yōu)化仿真

將元胞螞蟻算法的參數(shù)作為PSO算法的優(yōu)化對象，其中包括信息素啟發(fā)因子α、期望啟發(fā)因子β、信息素揮發(fā)因子ρ，其取值范圍如表1所示，其余參數(shù)根據(jù)專家經(jīng)驗法進行設置，螞蟻個數(shù)設置為30，信息素強度為14。具有自適應變異粒子的PSO算法的參數(shù)取值分別為：

c1=c2=1.49445；ω=0.5×（Tmax-t）/Tmax+0.2，Tmax=50為算法最大迭代次數(shù)，t為當前迭代次數(shù)；粒子個數(shù)為20；λ1、λ2、λ3、λ4分別為0.7、0.1、0.1、0.1。

根據(jù)仿真環(huán)境分別進行兩次運算，所得結(jié)果如表2所示。

表1 元胞螞蟻算法參數(shù)取值范圍

表2 仿真運算結(jié)果

為形象展現(xiàn)兩組參數(shù)所對應粒子的適應度值的變化趨勢與過程，繪制適應度值曲線如圖6所示：

圖6 粒子適應度值曲線

由圖6可知，在PSO算法迭代過程中，兩組粒子的適應度值存在一定的隨機波動，但是從整個運行過程分析，其適應度值均表現(xiàn)出上升趨勢，因此說明通過不斷的迭代過程，粒子趨向于適應度值更優(yōu)的位置。

3.2 路徑規(guī)劃結(jié)果

為四邊形柵格地圖與六邊形柵格地圖的有效性，分別對仿真環(huán)境進行路徑規(guī)劃，其結(jié)果如下：

圖7 仿真效果圖

圖中S表示起始節(jié)點，E表示目的節(jié)點。從上圖中可知，傳統(tǒng)模型與元胞螞蟻算法均可進行有效路徑規(guī)劃。

3.3 路徑規(guī)劃性能分析

為進一步凸顯本文研究方法的優(yōu)勢，分別使用基于四邊形柵格地圖的傳統(tǒng)ACO算法、基于經(jīng)驗參數(shù)值的元胞螞蟻算法以及基于PSO算法的元胞螞蟻算法（兩組參數(shù)結(jié)果）進行仿真對比，使用算法在進行路徑搜索時所經(jīng)過的元胞總數(shù)進行對比分析，其結(jié)果如圖8所示。

由圖8(a)與圖8(b)對比分析可知，在搜索路徑時，傳統(tǒng)ACO算法與元胞螞蟻算法所經(jīng)過的元胞總數(shù)隨著迭代次數(shù)的增加而逐漸減少；在算法迭代次數(shù)相同的情況下，元胞螞蟻算法經(jīng)過的元胞總數(shù)明顯小于傳統(tǒng)算法，表明元胞螞蟻算法的搜索速度較快；隨著迭代的不斷進行，傳統(tǒng)算法的搜索已基本停滯，而元胞螞蟻算法仍在進行，表明元胞螞蟻算法的搜索能力較強。對比分析圖8(b)、圖8(c)、圖8(d)可知，基于經(jīng)驗值的元胞螞蟻算法的收斂速度和搜索速度明顯弱于參數(shù)組1、2，但是收斂性比參數(shù)組1強，參數(shù)組2 在收斂速度、搜索能力以及收斂性方面均表現(xiàn)出明顯優(yōu)勢。

圖8 算法性能對比圖

4 結(jié)語

為求解路徑規(guī)劃問題，在傳統(tǒng)ACO算法基礎上，本文以六邊形柵格為基礎的元胞螞蟻算法，提出了基于PSO算法對元胞螞蟻算法的參數(shù)進行優(yōu)化的策略。將元胞螞蟻算法的參數(shù)作為PSO算法的位置信息進行迭代求解，利用適應度函數(shù)值對求解性能做出評價，從而得到元胞螞蟻算法的最優(yōu)參數(shù)組合。仿真結(jié)果表明；該方法能夠有效實現(xiàn)對元胞螞蟻算法的參數(shù)選取，對元胞螞蟻算法應用于路徑規(guī)劃具有一定的實用意義。