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

地圖模型的構(gòu)建是路徑規(guī)劃的重要前提，需要將漫游環(huán)境抽象為便于計算的模型．本研究采用柵格模型表示地圖環(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)境用二進制表示．其中，黑色方格（記為1）表示不能通過區(qū)域，如建筑物和障礙物等；白色方格（記為0）是可自由通過區(qū)域．為方便查找，柵格內(nèi)的所有方格采用由左至右，由上至下的順序進行編碼．

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

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

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

在漫游過程中，若路徑出現(xiàn)急轉(zhuǎn)或多次轉(zhuǎn)彎，會給體驗者帶來明顯的眩暈感，因此路徑的轉(zhuǎn)彎幅度應(yīng)盡可能減?。窂降钠交m應(yīng)度分量為

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

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

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

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

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

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

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

其中，t為迭代次數(shù)；ρ為揮發(fā)系數(shù)；Δτ為每次迭代中的信息素增量；Δτ _ij為每次迭代中從i點到j(luò)點路徑的信息素增量；Δτ _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)過i點和j點．

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

圖2（a）是螞蟻在7號柵格發(fā)生死鎖的示例．此時7號柵格的鄰接點禁忌表都記為1，表示在此次迭代中螞蟻已經(jīng)過1次．按照禁忌表中記錄次數(shù)的倒數(shù)產(chǎn)生概率進行解鎖，則此時7號柵格的所有鄰接點的選擇概率都相等．假設(shè)選擇3號柵格解鎖并更新路徑，如圖2（b），此時3號柵格在禁忌表中記為2．繼續(xù)移動時，優(yōu)先選擇在禁忌表中記錄為0的鄰接點隨機進行移動，即4號和9號柵格，避免了螞蟻因選擇2、7和8號柵格而再次陷入死鎖．在圖2（c）中，螞蟻在9號柵格再次陷入死鎖時，按禁忌表記數(shù)的倒數(shù)生成移動選擇概率，螞蟻選擇3號柵格跳出的概率比其他鄰接點要小，減少了后續(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.

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

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

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

圖4 BFO-ACO算法的驅(qū)散過程示例（a）局部最優(yōu)路徑；（b）在A處進行驅(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)移概率，然后通過解鎖、驅(qū)散和復(fù)制等操作擴大路徑多樣性，加快搜索過程，最后根據(jù)路徑適應(yīng)度大小進行信息素更新，進入下一次迭代，重復(fù)此過程直至達到最大迭代次數(shù)K，最后輸出最佳路徑．圖5是BFO-ACO算法流程圖．

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

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

實驗參數(shù)設(shè)置：最大迭代次數(shù)K=200，群體

規(guī)模M=20，信息素揮發(fā)系數(shù)ρ=0.3，信息素增加強度系數(shù)Q=1，驅(qū)散閾值P_ed=0.9，狀態(tài)轉(zhuǎn)移系數(shù)α=1、β=1，每個個體解除死鎖的次數(shù)上限為100次，超過此限值視為無效路徑，適應(yīng)度函數(shù)模型的平衡系數(shù)w₁=0.63、w₂=0.04、w₃=0.10、w₄=0 . 2 3．漫游路徑的質(zhì)量使用式（1）的適應(yīng)度函數(shù)模型進行評價．