基于多約束場(chǎng)景的BFO-ACO漫游路徑規(guī)劃

林曉玲，王志強(qiáng)，，郭巖巖，朱澤軒

1）深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東深圳 518060；2）深圳大學(xué)信息中心，廣東深圳 518060

在虛擬漫游中，路徑規(guī)劃是直接影響用戶場(chǎng)景探索和沉浸感的關(guān)鍵問題.路徑規(guī)劃目的是在指定起點(diǎn)到終點(diǎn)之間尋找一條最優(yōu)路徑.與其他的路徑規(guī)劃環(huán)境不同，漫游環(huán)境中不僅要求規(guī)劃路徑最短，還要考慮路徑經(jīng)過景點(diǎn)可見區(qū)域的數(shù)量、路徑的平滑性和路徑與障礙物的安全距離等約束條件，這都給漫游路線規(guī)劃設(shè)計(jì)帶來一定的困難.現(xiàn)有的路徑規(guī)劃算法大多僅關(guān)注性能的改進(jìn)，而常常忽略了多約束條件的影響，不適用于具有多約束條件的漫游環(huán)境.因此，針對(duì)漫游環(huán)境的多約束條件進(jìn)行路徑的評(píng)價(jià)和規(guī)劃的研究十分必要.

當(dāng)前常用的路徑規(guī)劃算法主要有蟻群優(yōu)化（ant colony optimization，ACO）算法［1-3］、遺傳算法［4-5］、粒子群算法［6-7］和A*算法［8-9］等.其中，ACO 算法［10］因具有良好的分布式計(jì)算能力、強(qiáng)魯棒性和全局收斂等優(yōu)點(diǎn)被廣泛用于路徑規(guī)劃，但也存在收斂速度慢、易陷入局部最優(yōu)和死鎖的問題，因此也衍生出許多改進(jìn)算法.JIAO 等［11］通過改進(jìn)信息素增量使其能夠?qū)崿F(xiàn)自適應(yīng)更新，提高了算法的運(yùn)行效率，減小陷入局部最優(yōu)的可能性.辛建霖等［12］采用基于ACO 算法的多算法融合方式，在搜索初期使用Dijkstra 算法初始化路徑以提高搜索效率，再用Logistic 混沌映射初始化信息素來提高算法的收斂速度，最后采用多選擇策略和模擬退火機(jī)制提高全局搜索能力.MIAO 等［13］在啟發(fā)式信息中考慮待選網(wǎng)格距離和目標(biāo)網(wǎng)格之間的距離，使啟發(fā)式信息能夠自適應(yīng)調(diào)節(jié)，并在傳遞概率中引入障礙排除因子和角度引導(dǎo)因子，從而增加了路徑搜索的多樣性，提高路徑規(guī)避能力和搜索效率.CHEN等［14］在啟發(fā)式信息中加入A*算法的估值函數(shù)思想，讓螞蟻在連接起始點(diǎn)的直線上找到移動(dòng)點(diǎn)，從而提高尋找最優(yōu)路徑的準(zhǔn)確性.陳志等［15］通過信息素值非均勻初始化，減少初期搜索的盲目性，用偽隨機(jī)方式選擇路徑，強(qiáng)化最優(yōu)解的引導(dǎo)，同時(shí)利用動(dòng)態(tài)懲罰的方法解決死鎖問題，提高搜索速度和解的質(zhì)量.張恒等［16］針對(duì)死鎖問題設(shè)計(jì)了自由尋路-剪枝策略，通過隨機(jī)選擇非障礙物柵格跳出死鎖，并將死鎖柵格加入禁忌表，以便生成優(yōu)質(zhì)路徑.孫功武等［17］采用特殊的回退策略解除死鎖，并將死鎖柵格儲(chǔ)存在全局禁忌表，對(duì)整個(gè)螞蟻群體后續(xù)的尋路進(jìn)行約束，從而降低后續(xù)迭代中陷入死鎖的概率.然而，隨著場(chǎng)景約束條件增多和場(chǎng)景規(guī)模變大，約束條件之間難以達(dá)到平衡，路徑的計(jì)算成本指數(shù)性增長，蟻群算法死鎖次數(shù)更多，收斂速度慢和局部最優(yōu)問題更加突出.

本研究根據(jù)漫游中對(duì)景點(diǎn)有效區(qū)域、障礙物距離、路徑平滑度和路徑長度等多個(gè)約束條件，構(gòu)造評(píng)價(jià)路線的適應(yīng)度函數(shù)模型，在蟻群算法中引入細(xì)菌覓食算法的復(fù)制和驅(qū)散機(jī)制，提出混合細(xì)菌覓食優(yōu)化思想的改進(jìn)蟻群優(yōu)化（bacterial foraging optimi?zation and ant colony optimization，BFO-ACO）算法.個(gè)體螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則生成概率來選擇移動(dòng)的鄰接點(diǎn)，并根據(jù)適應(yīng)度函數(shù)模型實(shí)時(shí)評(píng)價(jià)路徑的優(yōu)劣性.在適應(yīng)度達(dá)到一定條件后，對(duì)種群中路徑適應(yīng)度最高的螞蟻進(jìn)行復(fù)制以提高搜索速度，同時(shí)淘汰適應(yīng)度最小的螞蟻，減少劣質(zhì)路徑對(duì)正反饋機(jī)制的影響；優(yōu)化禁忌表更新方式，對(duì)陷入死鎖狀態(tài)的螞蟻進(jìn)行解鎖，提高有效蟻群數(shù)量并保持種群多樣性；在搜索過程中對(duì)搜索螞蟻進(jìn)行一定概率的驅(qū)散，避免陷入局部最優(yōu).

1 多約束環(huán)境路徑規(guī)劃

1.1 地圖模型構(gòu)建

地圖模型的構(gòu)建是路徑規(guī)劃的重要前提，需要將漫游環(huán)境抽象為便于計(jì)算的模型.本研究采用柵格模型表示地圖環(huán)境.虛擬漫游環(huán)境及其柵格化地圖如圖1.

圖1 （a）虛擬漫游環(huán)境及其（b）俯視圖與（c）柵格地圖Fig.1 (a)Virtual roaming environment and it's(b)top view and(c)grid map.

柵格地圖環(huán)境用二進(jìn)制表示.其中，黑色方格（記為1）表示不能通過區(qū)域，如建筑物和障礙物等；白色方格（記為0）是可自由通過區(qū)域.為方便查找，柵格內(nèi)的所有方格采用由左至右，由上至下的順序進(jìn)行編碼.

1.2 多約束條件及路徑適應(yīng)度函數(shù)模型

一般環(huán)境的路徑規(guī)劃常以路徑的長度評(píng)價(jià)路徑優(yōu)劣，路徑越短則路徑質(zhì)量越高.漫游環(huán)境下的路徑要求更高，需權(quán)衡多個(gè)約束條件后再對(duì)路徑進(jìn)行評(píng)價(jià).為準(zhǔn)確評(píng)價(jià)路徑質(zhì)量，提出路徑適應(yīng)度函數(shù)模型，根據(jù)適應(yīng)度值判定路徑的優(yōu)劣程度.考慮漫游路徑的長度、經(jīng)過景物有效可見區(qū)域的數(shù)量、路徑平滑性和障礙物距離的要求，建立適應(yīng)度函數(shù)模型為

其中，s為路徑的步數(shù)；i為路徑位置指標(biāo)；（xi，yi）和（xi-1，yi-1）分別為路徑兩個(gè)連續(xù)節(jié)點(diǎn)的坐標(biāo).

路徑中景物的可見性決定了體驗(yàn)者的沉浸感.在起點(diǎn)到終點(diǎn)的漫游過程中，漫游中看見的景點(diǎn)越多，體驗(yàn)者的視覺體驗(yàn)感越好.通常來講，從景點(diǎn)的正面經(jīng)過更能吸引體驗(yàn)者的注意力，使其不容易感覺到視覺疲勞.因此，景點(diǎn)的正面區(qū)域是景點(diǎn)的有效可見區(qū)域.將路徑經(jīng)過景點(diǎn)可見區(qū)域的平均個(gè)數(shù)作為路徑評(píng)價(jià)標(biāo)準(zhǔn)之一，經(jīng)過區(qū)域數(shù)量越多，路徑的適應(yīng)度值越高.景點(diǎn)可見區(qū)域的適應(yīng)度分量為

其中，N為地圖中關(guān)鍵景點(diǎn)的個(gè)數(shù)；Sn= 1 表示路徑在n景點(diǎn)的可見區(qū)域內(nèi)經(jīng)過；Sn= 0表示不經(jīng)過.

在漫游過程中，若路徑出現(xiàn)急轉(zhuǎn)或多次轉(zhuǎn)彎，會(huì)給體驗(yàn)者帶來明顯的眩暈感，因此路徑的轉(zhuǎn)彎幅度應(yīng)盡可能減小.路徑的平滑適應(yīng)度分量為

2 BFO-ACO算法

2.1 BFO-ACO算法原理

為解決ACO 算法在路徑規(guī)劃中收斂速度慢和易陷入局部最優(yōu)問題，本研究提出混合細(xì)菌覓食優(yōu)化思想的改進(jìn)蟻群優(yōu)化算法.細(xì)菌覓食優(yōu)化（bacte?rial foraging optimization，BFO）算法是PASSINO［18］基于大腸桿菌在人體腸道內(nèi)的覓食行為提出的新型智能仿生算法，具有快速搜索的特點(diǎn)和較高的優(yōu)化能力，其關(guān)鍵步驟是趨向、復(fù)制和驅(qū)散操作.BFOACO 算法的基本思想是在每次迭代搜索的過程中，計(jì)算當(dāng)前路徑的適應(yīng)度值，當(dāng)達(dá)到設(shè)定的閾值時(shí)，復(fù)制適應(yīng)度值高的路徑，提高最佳路徑的搜索速度；多次迭代后，蟻群搜索會(huì)集中在幾條路徑中，此時(shí)對(duì)路徑中某些位置的螞蟻進(jìn)行隨機(jī)驅(qū)散，增加路徑跳出局部最優(yōu)的概率.另外，為解決傳統(tǒng)蟻群算法的死鎖問題，對(duì)禁忌表進(jìn)行優(yōu)化改進(jìn)，使螞蟻根據(jù)個(gè)體選擇概率隨機(jī)選擇鄰接點(diǎn)解除死鎖，保證算法前期路徑的多樣性.

BFO-ACO 算法基于傳統(tǒng)蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則進(jìn)行路徑搜索，并按照路徑的適應(yīng)度值更新信息素.狀態(tài)轉(zhuǎn)移規(guī)則由每個(gè)位置的信息素濃度和距離啟發(fā)因子決定.因此，從當(dāng)前位置移動(dòng)到方向j的概率為

其中，allowed 為可移動(dòng)的方向集合；α和β為正整數(shù)，是信息素和啟發(fā)因子的權(quán)重；τj為移動(dòng)到方向j的信息素強(qiáng)度；ηj為移動(dòng)到方向j的啟發(fā)式因子，取當(dāng)前位置到終點(diǎn)距離的倒數(shù).信息素濃度越大，啟發(fā)式因子越小，則選擇該方向的概率就越大.

當(dāng)所有螞蟻都到達(dá)終點(diǎn)時(shí)，即完成1 次迭代.此時(shí)整個(gè)信息素表以固定系數(shù)ρ揮發(fā)掉一部分，當(dāng)次迭代產(chǎn)生的路徑信息素增加.信息素更新規(guī)則如式（7）至式（9）.

其中，t為迭代次數(shù)；ρ為揮發(fā)系數(shù)；Δτ為每次迭代中的信息素增量；Δτij為每次迭代中從i點(diǎn)到j(luò)點(diǎn)路徑的信息素增量；Δτij(m)為路徑m釋放的信息素量；M為螞蟻的種群數(shù)量；F(m)為第m條路徑的適應(yīng)度，且0

2.2 優(yōu)化禁忌表解鎖策略

ACO算法為避免形成環(huán)路和重復(fù)路徑，在移動(dòng)策略中使用了禁忌表，但禁忌表策略常使螞蟻在搜索路徑時(shí)陷入死鎖狀態(tài)，導(dǎo)致螞蟻不能到達(dá)終點(diǎn)，此路徑被標(biāo)注為無效路徑，不更新信息素，這降低了路徑的多樣性.特別是在規(guī)模較大的地圖環(huán)境下，死鎖會(huì)導(dǎo)致無效螞蟻過多，在多次迭代之后才會(huì)出現(xiàn)少數(shù)有效路徑，信息素迅速積累，后續(xù)迭代的螞蟻群體大量集中在此有效路徑中，極易導(dǎo)致局部最優(yōu)解，甚至出現(xiàn)迭代終止之后仍無法搜索到有效路徑的情況.為解決此問題，本研究提出優(yōu)化禁忌表策略進(jìn)行解鎖.禁忌表記錄螞蟻經(jīng)過的次數(shù)，移動(dòng)時(shí)優(yōu)先選擇螞蟻經(jīng)過次數(shù)為0的鄰接點(diǎn).當(dāng)所有鄰接點(diǎn)禁忌值非0時(shí)，表示陷入死鎖，此時(shí)按照禁忌表次數(shù)的倒數(shù)生成概率，隨機(jī)選擇鄰接點(diǎn)跳出死鎖.

圖2（a）是螞蟻在7號(hào)柵格發(fā)生死鎖的示例.此時(shí)7 號(hào)柵格的鄰接點(diǎn)禁忌表都記為1，表示在此次迭代中螞蟻已經(jīng)過1次.按照禁忌表中記錄次數(shù)的倒數(shù)產(chǎn)生概率進(jìn)行解鎖，則此時(shí)7號(hào)柵格的所有鄰接點(diǎn)的選擇概率都相等.假設(shè)選擇3號(hào)柵格解鎖并更新路徑，如圖2（b），此時(shí)3號(hào)柵格在禁忌表中記為2.繼續(xù)移動(dòng)時(shí)，優(yōu)先選擇在禁忌表中記錄為0的鄰接點(diǎn)隨機(jī)進(jìn)行移動(dòng)，即4 號(hào)和9 號(hào)柵格，避免了螞蟻因選擇2、7和8號(hào)柵格而再次陷入死鎖.在圖2（c）中，螞蟻在9號(hào)柵格再次陷入死鎖時(shí)，按禁忌表記數(shù)的倒數(shù)生成移動(dòng)選擇概率，螞蟻選擇3號(hào)柵格跳出的概率比其他鄰接點(diǎn)要小，減少了后續(xù)搜索中又陷入死鎖的概率.因此，在優(yōu)化禁忌表解鎖的策略下，螞蟻在單次迭代過程中陷入死鎖的概率越來越小，從而在保證迭代前期就能找到有效路徑，提高了路徑的多樣性.

圖2 死鎖解鎖步驟（a）第1次死鎖；（b）第1次按概率解鎖；（c）第2次死鎖；（d）第2次按概率解鎖Fig.2 Deadlock unlocking steps.(a)The first time deadlock,(b)the first time unlock by probability,(c)the second time deadlock,(d)the second time unlock by probability.

2.3 引入復(fù)制機(jī)制

為提升算法初期的搜索速度，使整體算法快速收斂，本研究引入BFO算法的復(fù)制機(jī)制.復(fù)制操作在尋路過程中的應(yīng)用如圖3 所示，黑色圓圈為起點(diǎn)，紅色圓圈為終點(diǎn)，①至④是4只螞蟻的實(shí)時(shí)搜索路徑.在蟻群進(jìn)行路徑搜索的過程中，對(duì)每只螞蟻的當(dāng)前路徑使用式（1）的適應(yīng)度函數(shù)模型進(jìn)行評(píng)價(jià)，路徑的適應(yīng)度值越高，該路徑是優(yōu)質(zhì)路徑的概率越高，對(duì)優(yōu)質(zhì)路徑進(jìn)行復(fù)制，增加優(yōu)質(zhì)路徑的搜索概率.如圖3（a），當(dāng)前時(shí)刻路徑①適應(yīng)度值最大，對(duì)該路段進(jìn)行復(fù)制，提高路徑①的搜索概率.同時(shí)為了保持種群數(shù)量一致性，淘汰適應(yīng)度最差的路徑③，復(fù)制的路徑對(duì)淘汰的路徑進(jìn)行替換，如圖3（b）所示.隨后，蟻群如圖3（c）所示繼續(xù)進(jìn)行搜索.

圖3 BFO-ACO算法的復(fù)制過程（a）復(fù)制前；（b）復(fù)制路徑①，淘汰路徑③；（c）下一步搜索Fig.3 Example of the replication process of the BFO-ACO algorithm.(a)Before replication,(b)replication path ①and elimination path ③,(c)next search.

2.4 引入驅(qū)散機(jī)制

當(dāng)?shù)螖?shù)較大時(shí)，信息素基本集中在一條路徑中，若這條路徑不是最優(yōu)路徑，螞蟻卻以較大的概率沿著這條路徑進(jìn)行搜索，就難以跳出局部最優(yōu)解.為使算法具有跳出局部最優(yōu)的能力，在搜索中加入驅(qū)散機(jī)制.當(dāng)鄰接點(diǎn)的移動(dòng)選擇概率超過一定的閾值時(shí)，對(duì)螞蟻采取隨機(jī)概率驅(qū)散，選擇其他鄰接點(diǎn)進(jìn)行移動(dòng)，從而令每只螞蟻都有可能跳出局部最優(yōu)找到更優(yōu)路徑.假設(shè)在多次迭代后螞蟻的最佳路徑如圖4（a），螞蟻當(dāng)前位于A點(diǎn)，其鄰接表轉(zhuǎn)移概率如圖4（b），此時(shí)螞蟻向B點(diǎn)移動(dòng)的概率極大，超過了0.94，陷入局部最優(yōu).對(duì)螞蟻進(jìn)行隨機(jī)驅(qū)散到C點(diǎn)，使驅(qū)散后的路徑更短，適應(yīng)度值更大，得到最優(yōu)解.

圖4 BFO-ACO算法的驅(qū)散過程示例（a）局部最優(yōu)路徑；（b）在A處進(jìn)行驅(qū)散Fig.4 Example of the dispersion process of BFO-ACO algorithm.(a)The local optimal path,(b)dispersed at A.

2.5 BFO-ACO算法流程

BFO-ACO 算法根據(jù)信息素濃度生成狀態(tài)轉(zhuǎn)移概率，然后通過解鎖、驅(qū)散和復(fù)制等操作擴(kuò)大路徑多樣性，加快搜索過程，最后根據(jù)路徑適應(yīng)度大小進(jìn)行信息素更新，進(jìn)入下一次迭代，重復(fù)此過程直至達(dá)到最大迭代次數(shù)K，最后輸出最佳路徑.圖5是BFO-ACO算法流程圖.

圖5 BFO-ACO算法流程圖Fig.5 Flow chart of BFO-ACO algorithm

3 仿真及實(shí)驗(yàn)

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證本研究構(gòu)造的適應(yīng)度函數(shù)模型及BFOACO算法在多約束環(huán)境中的有效性，使用3種不同規(guī)模的靜態(tài)柵格環(huán)境分別為20 × 20 柵格的簡(jiǎn)單環(huán)境、30 × 30柵格的陷阱環(huán)境，以及40 × 40柵格的多分支復(fù)雜環(huán)境，各進(jìn)行50 次實(shí)驗(yàn)測(cè)試，并將實(shí)驗(yàn)結(jié)果與傳統(tǒng)ACO 算法、BFO 算法和雙向ACO［19］進(jìn)行比較，所有算法均采用相同的實(shí)驗(yàn)參數(shù)和適應(yīng)度函數(shù)模型.

實(shí)驗(yàn)參數(shù)設(shè)置：最大迭代次數(shù)K= 200，群體規(guī)模M= 20，信息素?fù)]發(fā)系數(shù)ρ= 0.3，信息素增加強(qiáng)度系數(shù)Q= 1，驅(qū)散閾值Ped= 0.9，狀態(tài)轉(zhuǎn)移系數(shù)α= 1、β= 1，每個(gè)個(gè)體解除死鎖的次數(shù)上限為100次，超過此限值視為無效路徑，適應(yīng)度函數(shù)模 型 的 平 衡 系 數(shù)w1= 0.63、w2= 0.04、w3= 0.10、w4= 0.23.漫游路徑的質(zhì)量使用式（1）的適應(yīng)度函數(shù)模型進(jìn)行評(píng)價(jià).

3.2 實(shí)驗(yàn)仿真

3.2.1 路徑規(guī)劃結(jié)果分析

不同算法在3種不同規(guī)模環(huán)境下的路徑規(guī)劃結(jié)果如圖6.其中，藍(lán)色方格表示路徑起點(diǎn)，紅色方格表示路徑終點(diǎn)，黑色方格表示不可行的障礙物，灰色方格為景點(diǎn)可見區(qū)域并分塊標(biāo)號(hào)，白色和灰色方格都可以自由通行.由圖6（a）可見，20 × 20 柵格的簡(jiǎn)單環(huán)境規(guī)模較小，有效景點(diǎn)區(qū)域比較集中，路徑分支較為簡(jiǎn)單，4種算法規(guī)劃的路徑都比較集中，路徑長度、彎折程度和障礙距離相近，BFO和雙向ACO 算法都經(jīng)過4 個(gè)景點(diǎn)區(qū)域，BFO-ACO 算法經(jīng)過5個(gè)景點(diǎn)，而ACO算法只能經(jīng)過3個(gè)景點(diǎn)區(qū)域.由圖6（b）可見，30 × 30 柵格的地圖環(huán)境不僅擴(kuò)大了規(guī)模，還設(shè)計(jì)了凹陷和繞遠(yuǎn)陷阱，令尋路環(huán)境更復(fù)雜.其中，ACO 算法的回折現(xiàn)象比較突出，BFO 和雙向ACO 算法則出現(xiàn)不同程度的繞遠(yuǎn)和凹陷，本研究算法得到的路徑相比其他算法，路徑更短，彎折更少，且經(jīng)過的有效景點(diǎn)區(qū)域最多.40 ×40柵格的地圖環(huán)境進(jìn)一步擴(kuò)大了規(guī)模，并設(shè)計(jì)障礙物均勻分散，從而使尋路過程中分支較多.由于ACO 和雙向ACO 算法在整個(gè)迭代過程中極易因陷入死鎖而無法得到有效路徑，在此環(huán)境下對(duì)所有算法均采取與BFO-ACO 算法相同的優(yōu)化解鎖策略來進(jìn)行解鎖.從圖6（c）可見，BFO-ACO 和BFO 算法都經(jīng)過3個(gè)景點(diǎn)區(qū)域且路徑的彎折較少，但BFO算法所得路徑較長；ACO算法所得路徑繞遠(yuǎn)、彎折多且不經(jīng)過景點(diǎn)，路徑質(zhì)量較差；雙向ACO 算法所得路徑則出現(xiàn)較多的彎折.

圖6 （a）20×20柵格的簡(jiǎn)單環(huán)境、（b）30×30柵格的陷阱環(huán)境、（c）40×40柵格的多分支復(fù)雜規(guī)模環(huán)境下不同算法的路徑規(guī)劃結(jié)果Fig.6 Path planning results of different algorithms in scale environments of(a)a simple environment for a 20×20 grid,(b)a trap environment for a 30×30 grid,(c)a multi-branch complex environment for a 40×40 grid.

3.2.2 迭代收斂曲線分析

圖7比較了ACO、雙向ACO、BFO和BFO-ACO算法在3 種環(huán)境下的路徑適應(yīng)度迭代曲線.由圖7（a）可見，在小規(guī)模環(huán)境中，4 種算法都能達(dá)到收斂.其中，BFO算法在驅(qū)散作用下不斷尋找適應(yīng)度更高的路徑，收斂較慢；ACO算法前期無效路徑較多，適應(yīng)度小，在迭代約110次后收斂；雙向ACO算法收斂速度較快，迭代約39 次就能收斂，這是因?yàn)殡p向搜索加快了蟻群的尋路效率，能夠快速積累信息素達(dá)到收斂，但所得路徑適應(yīng)度不高，陷入了局部最優(yōu)情況.BFO-ACO 算法在解鎖策略下保證了迭代前期能夠找到有效路徑，從而保證了搜索的多樣性，避免了出現(xiàn)局部最優(yōu)的情況，在復(fù)制機(jī)制的驅(qū)動(dòng)下快速搜索到較優(yōu)路徑，并及時(shí)進(jìn)行驅(qū)散，得到適應(yīng)度最優(yōu)的路徑，收斂速度快.

圖7 （a）20×20柵格的簡(jiǎn)單環(huán)境、（b）30×30柵格的陷阱環(huán)境、（c）40×40柵格的多分支復(fù)雜規(guī)模環(huán)境下不同算法的適應(yīng)度與迭代次數(shù)關(guān)系Fig.7 Iterative curves of adaptability of different algorithms in scale environments of(a)a simple environment for a 20×20 grid,(b)a trap environment for a 30×30 grid,(c)a multi-branch complex environment for a 40×40 grid.

在如圖7（b）所示的30 × 30柵格的規(guī)模環(huán)境中，ACO算法由于地圖規(guī)模較大和凹陷陷阱問題，令多數(shù)螞蟻個(gè)體陷入死鎖無法到達(dá)終點(diǎn)，因此在迭代了約25次后才找到第1條有效路徑.之后，信息素在這條路徑上迅速積累，局部最優(yōu)情況較為突出.BFO 算法的驅(qū)散機(jī)制可以得到適應(yīng)度更高的路徑，但由于沒有信息素的引導(dǎo)作用，驅(qū)散的隨機(jī)性較高，因此仍陷入局部最優(yōu).雙向ACO 算法避免了陷入死鎖的無效路徑過多的問題，但由于多約束條件的影響，信息素?zé)o法集中，適應(yīng)度難以收斂.BFO-ACO 算法在搜索過程中融入復(fù)制機(jī)制，加強(qiáng)了信息素在較優(yōu)路徑上的積累，可令路徑適應(yīng)度迅速收斂.在迭代到60～70 次后，路徑選擇較為集中，此時(shí)啟動(dòng)驅(qū)散機(jī)制，可進(jìn)一步提高路徑質(zhì)量，最終在迭代約110次時(shí)達(dá)到收斂.

在如圖7（c）所示40 × 40柵格的大規(guī)模環(huán)境中，ACO 和雙向ACO 算法在多分支條件下不斷找到適應(yīng)度相近的不同路徑，因此信息素?zé)o法在一處積累，這令適應(yīng)度無法收斂.但是，雙向策略可獲得比ACO 算法質(zhì)量更好的路徑.ACO 算法在迭代后期仍會(huì)出現(xiàn)單次迭代中無有效路徑的情況.BFO算法在大規(guī)模環(huán)境下驅(qū)散作用效果不大，這是由于驅(qū)散的隨機(jī)性導(dǎo)致的.BFO-ACO 算法在完成驅(qū)散得到較優(yōu)路徑之后，信息素積累幫助迭代收斂，可保持較好的路徑質(zhì)量和搜索速度.

3.2.3 性能分析

表1對(duì)比了ACO、雙向ACO、BFO和BFO-ACO算法在3種環(huán)境下的性能.由表1可見，在20 × 20柵格的環(huán)境中，ACO 算法路徑較長，平均轉(zhuǎn)角大，平均障礙距離偏?。籅FO 算法的平均障礙距離大，景點(diǎn)數(shù)較多，路徑長度和平均轉(zhuǎn)角較小，但收斂慢；雙向ACO 算法運(yùn)行時(shí)間短、收斂快，但路徑的各項(xiàng)性能不高.運(yùn)行時(shí)間上4種算法則差別不明顯.可見，以上3種算法都無法平衡多個(gè)約束條件得到一條最佳的路徑，而BFO-ACO 算法在路徑長度、景點(diǎn)數(shù)量、平均轉(zhuǎn)角和平均障礙距離上都能保持較好效果，同時(shí)具有較快的運(yùn)算速度.

表1 不同算法在3種環(huán)境的路徑規(guī)劃仿真結(jié)果Table 1 Simulation results of path planning for different algorithms in three environments

在30 × 30 柵格的中等規(guī)模環(huán)境中，BFO-ACO算法的各項(xiàng)性能依舊保持較好，在迭代至113次時(shí)達(dá)到收斂.ACO算法雖然收斂速度快，但這是由于該算法的有效螞蟻數(shù)量過少，有效路徑出現(xiàn)后搜索變得集中，易陷入局部最優(yōu)，因而其路徑整體質(zhì)量差，路徑適應(yīng)度值小；BFO 和雙向ACO 算法在搜索過程中易陷入凹陷陷阱，且運(yùn)行時(shí)間長，適應(yīng)度不收斂，最終得到的路徑各項(xiàng)數(shù)值都不佳.

在40 × 40 柵格環(huán)境下，BFO-ACO 算法在大規(guī)模環(huán)境下仍舊可保持較快的運(yùn)算速度，多項(xiàng)約束性能較為平衡，在路長、景點(diǎn)數(shù)和平均轉(zhuǎn)角上的表現(xiàn)都明顯比其他算法效果更佳，而平均障礙距離雖略小于BFO 和雙向ACO 算法，但整體路徑適應(yīng)度遠(yuǎn)大于其他算法，即使在多約束條件的限制下，適應(yīng)度仍可收斂，而其他算法直至迭代終止仍無法收斂.

結(jié) 語

提出一種基于多約束漫游環(huán)境的BFO-ACO 路徑規(guī)劃算法，針對(duì)多約束條件構(gòu)造用于評(píng)價(jià)路徑質(zhì)量的適應(yīng)度函數(shù)模型，提出優(yōu)化禁忌表的解鎖方案，并將BFO算法中的復(fù)制和驅(qū)散思想融入路徑搜索過程.解鎖保證了路徑搜索的多樣性，以禁忌表中的螞蟻經(jīng)過次數(shù)生成概率解鎖可以逐漸減小死鎖發(fā)生的概率，提高搜索效率.路徑搜索中引入復(fù)制機(jī)制，提高了算法前期的搜索速度，使算法全局更快收斂.引入驅(qū)散機(jī)制，使算法能夠跳出局部最優(yōu)，且驅(qū)散過程融入到搜索過程，不會(huì)增加額外的搜索時(shí)間.適應(yīng)度函數(shù)模型在路徑搜索過程中對(duì)路徑的質(zhì)量進(jìn)行實(shí)時(shí)評(píng)價(jià)，是判斷復(fù)制的重要評(píng)價(jià)標(biāo)準(zhǔn)，也是決定信息素更新的關(guān)鍵規(guī)則.通過與ACO、雙向ACO、BFO算法在不同環(huán)境下仿真實(shí)驗(yàn)的結(jié)果進(jìn)行比較，驗(yàn)證了BFO-ACO 算法的可行性與有效性.

由于BFO-ACO 算法是基于柵格地圖對(duì)路徑進(jìn)行規(guī)劃，應(yīng)用到漫游環(huán)境中還需要進(jìn)一步進(jìn)行曲線平滑處理.因此，未來可針對(duì)非規(guī)范化地圖環(huán)境進(jìn)行研究并得到曲線路徑，或者考慮對(duì)路徑適應(yīng)度評(píng)價(jià)模型進(jìn)行進(jìn)一步優(yōu)化.