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

地圖模型的構(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）表示不能通過(guò)區(qū)域，如建筑物和障礙物等；白色方格（記為0）是可自由通過(guò)區(qū)域．為方便查找，柵格內(nèi)的所有方格采用由左至右，由上至下的順序進(jìn)行編碼．

一般環(huán)境的路徑規(guī)劃常以路徑的長(zhǎng)度評(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)劣程度．考慮漫游路徑的長(zhǎng)度、經(jīng)過(guò)景物有效可見(jiàn)區(qū)域的數(shù)量、路徑平滑性和障礙物距離的要求，建立適應(yīng)度函數(shù)模型為

其中，w₁，w₂，w₃，w₄∈[ 0，1]，分別表示4個(gè)約束條件的平衡系數(shù)；f_i為第i個(gè)約束條件的適應(yīng)度分量．路徑長(zhǎng)度是評(píng)價(jià)路徑優(yōu)劣中的關(guān)鍵指標(biāo)，路徑越短，其綜合性能越好．路徑長(zhǎng)度適應(yīng)度分量為其中， s為路徑的步數(shù)； i為路徑位置指標(biāo)；（x_i ， y_i）和（x_i-1 ， y_i-1）分別為路徑兩個(gè)連續(xù)節(jié)點(diǎn)的坐標(biāo)．路徑中景物的可見(jiàn)性決定了體驗(yàn)者的沉浸感．在起點(diǎn)到終點(diǎn)的漫游過(guò)程中，漫游中看見(jiàn)的景點(diǎn)越多，體驗(yàn)者的視覺(jué)體驗(yàn)感越好．通常來(lái)講，從景點(diǎn)的正面經(jīng)過(guò)更能吸引體驗(yàn)者的注意力，使其不容易感覺(jué)到視覺(jué)疲勞．因此，景點(diǎn)的正面區(qū)域是景點(diǎn)的有效可見(jiàn)區(qū)域．將路徑經(jīng)過(guò)景點(diǎn)可見(jiàn)區(qū)域的平均個(gè)數(shù)作為路徑評(píng)價(jià)標(biāo)準(zhǔn)之一，經(jīng)過(guò)區(qū)域數(shù)量越多，路徑的適應(yīng)度值越高．景點(diǎn)可見(jiàn)區(qū)域的適應(yīng)度分量為

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

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

其中，?θ_i為第i步轉(zhuǎn)彎的角度．

沿著路徑進(jìn)行漫游時(shí)，若過(guò)于貼近某一側(cè)的障礙物，會(huì)造成視覺(jué)空間不協(xié)調(diào)．因此，路徑的每一個(gè)位置與障礙物的最小距離都應(yīng)該盡可能大，且平均障礙距離越大，視覺(jué)協(xié)調(diào)性越高．路徑的障礙物距離適應(yīng)度分量為

其中，d _av為全局平均最小障礙物距離；d_i為路徑在i位置的最小障礙物距離．

為解決ACO算法在路徑規(guī)劃中收斂速度慢和易陷入局部最優(yōu)問(wèn)題，本研究提出混合細(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ū)散操作．BFO-ACO算法的基本思想是在每次迭代搜索的過(guò)程中，計(jì)算當(dāng)前路徑的適應(yīng)度值，當(dāng)達(dá)到設(shè)定的閾值時(shí)，復(fù)制適應(yīng)度值高的路徑，提高最佳路徑的搜索速度；多次迭代后，蟻群搜索會(huì)集中在幾條路徑中，此時(shí)對(duì)路徑中某些位置的螞蟻進(jìn)行隨機(jī)驅(qū)散，增加路徑跳出局部最優(yōu)的概率．另外，為解決傳統(tǒng)蟻群算法的死鎖問(wèn)題，對(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<F (m)<1；常數(shù)Q為信息素總量，路徑的適應(yīng)度越大，留下的信息素就越多． i，j∈path (m)表示路徑m經(jīng)過(guò)i點(diǎn)和j點(diǎn)．

ACO算法為避免形成環(huán)路和重復(fù)路徑，在移動(dòng)策略中使用了禁忌表，但禁忌表策略常使螞蟻在搜索路徑時(shí)陷入死鎖狀態(tài)，導(dǎo)致螞蟻不能到達(dá)終點(diǎn)，此路徑被標(biāo)注為無(wú)效路徑，不更新信息素，這降低了路徑的多樣性．特別是在規(guī)模較大的地圖環(huán)境下，死鎖會(huì)導(dǎo)致無(wú)效螞蟻過(guò)多，在多次迭代之后才會(huì)出現(xiàn)少數(shù)有效路徑，信息素迅速積累，后續(xù)迭代的螞蟻群體大量集中在此有效路徑中，極易導(dǎo)致局部最優(yōu)解，甚至出現(xiàn)迭代終止之后仍無(wú)法搜索到有效路徑的情況．為解決此問(wèn)題，本研究提出優(yōu)化禁忌表策略進(jìn)行解鎖．禁忌表記錄螞蟻經(jīng)過(guò)的次數(shù)，移動(dòng)時(shí)優(yōu)先選擇螞蟻經(jīng)過(guò)次數(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)過(guò)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)化禁忌表解鎖的策略下，螞蟻在單次迭代過(guò)程中陷入死鎖的概率越來(lái)越小，從而在保證迭代前期就能找到有效路徑，提高了路徑的多樣性．

圖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.

為提升算法初期的搜索速度，使整體算法快速收斂，本研究引入BFO算法的復(fù)制機(jī)制．復(fù)制操作在尋路過(guò)程中的應(yīng)用如圖3所示，黑色圓圈為起點(diǎn)，紅色圓圈為終點(diǎn)，①至④是4只螞蟻的實(shí)時(shí)搜索路徑．在蟻群進(jìn)行路徑搜索的過(guò)程中，對(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)行搜索．

當(dāng)?shù)螖?shù)較大時(shí)，信息素基本集中在一條路徑中，若這條路徑不是最優(yōu)路徑，螞蟻卻以較大的概率沿著這條路徑進(jìn)行搜索，就難以跳出局部最優(yōu)解．為使算法具有跳出局部最優(yōu)的能力，在搜索中加入驅(qū)散機(jī)制．當(dāng)鄰接點(diǎn)的移動(dòng)選擇概率超過(guò)一定的閾值時(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)的概率極大，超過(guò)了0. 94，陷入局部最優(yōu)．對(duì)螞蟻進(jìn)行隨機(jī)驅(qū)散到C點(diǎn)，使驅(qū)散后的路徑更短，適應(yīng)度值更大，得到最優(yōu)解．

圖3 BFO-ACO算法的復(fù)制過(guò)程（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.

圖4 BFO-ACO算法的驅(qū)散過(guò)程示例（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.

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

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

為驗(yàn)證本研究構(gòu)造的適應(yīng)度函數(shù)模型及BFO-ACO算法在多約束環(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ū)散閾值P_ed=0.9，狀態(tài)轉(zhuǎn)移系數(shù)α=1、β=1，每個(gè)個(gè)體解除死鎖的次數(shù)上限為100次，超過(guò)此限值視為無(wú)效路徑，適應(yīng)度函數(shù)模型的平衡系數(shù)w₁=0.63、w₂=0.04、w₃=0.10、w₄=0 . 2 3．漫游路徑的質(zhì)量使用式（1）的適應(yīng)度函數(shù)模型進(jìn)行評(píng)價(jià)．