元胞螞蟻算法的參數(shù)優(yōu)化方法及其仿真研究

王培良，張 婷，肖英杰

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

0 引言

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

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

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

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

1.1 柵格地圖的描述

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

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

圖1 moore型鄰域

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

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

圖2 四邊形柵格與六邊形柵格對(duì)比

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

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

1.2 算法描述

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

A：?jiǎn)蜗佋Ｐ停?/p>

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ī)則，即螞蟻移動(dòng)的基本依據(jù)，其規(guī)則主要取決于以下三點(diǎn)：

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

2）所選元胞與目的元胞的距離應(yīng)不大于當(dāng)前元胞與目的元胞的距離；

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

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

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

2.1 PSO算法描述

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

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

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

2.2 適應(yīng)度評(píng)價(jià)函數(shù)設(shè)計(jì)

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

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

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

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

圖3 算法流程圖

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

為驗(yàn)證所構(gòu)建模型的性能，筆者以某大型郵輪的B甲板上的展廳為工程背景進(jìn)行仿真，計(jì)算對(duì)比蟻群元胞算法與傳統(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)化對(duì)象，其中包括信息素啟發(fā)因子α、期望啟發(fā)因子β、信息素?fù)]發(fā)因子ρ，其取值范圍如表1所示，其余參數(shù)根據(jù)專家經(jīng)驗(yàn)法進(jìn)行設(shè)置，螞蟻個(gè)數(shù)設(shè)置為30，信息素強(qiáng)度為14。具有自適應(yīng)變異粒子的PSO算法的參數(shù)取值分別為：

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

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

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

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

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

圖6 粒子適應(yīng)度值曲線

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

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

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

圖7 仿真效果圖

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

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

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

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

圖8 算法性能對(duì)比圖

4 結(jié)語

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