刁 說

(華北計算技術(shù)研究所系統(tǒng)八部，北京 100083)

0 引 言

在計算機(jī)程序模擬的二維柵格地圖中，通常采用遍歷的方式來找尋有特殊值的網(wǎng)格位置坐標(biāo)。而在現(xiàn)實(shí)世界中，受限于客觀條件，遍歷搜索的方式不可行，例如旅行人員在沙漠之中尋找水源時，儲備物資不足以支撐遍歷式的探索。現(xiàn)實(shí)中解決上述問題的常用方法為，通過觀察與搜索目標(biāo)相關(guān)的自然現(xiàn)象或指示性標(biāo)志從而確定大致的搜索方向，以此來達(dá)到快速、高效找尋目標(biāo)的目的。此類問題的現(xiàn)實(shí)應(yīng)用場景包括海上航行、叢林穿越、災(zāi)后搜救等工作。在上述緊急情況下，迷路者或搜救者受限于網(wǎng)絡(luò)覆蓋范圍，缺乏先進(jìn)電子設(shè)備輔助，無法獲得地理定位與地圖信息，只能收集周圍環(huán)境信息并通過經(jīng)驗(yàn)判斷的方式?jīng)Q定前進(jìn)路線，并且需要在有限的移動距離內(nèi)找到目標(biāo)。合理地利用人類常識與生活經(jīng)驗(yàn)，對緊急情況下的路徑找尋以及目標(biāo)搜索有極大幫助。因此通過人工智能方法的建模應(yīng)用，實(shí)現(xiàn)經(jīng)驗(yàn)知識的有效利用，并研究相關(guān)算法模型作為尋路工具的實(shí)現(xiàn)參考，有著重要的理論和現(xiàn)實(shí)意義。

目前，基于柵格地圖的目標(biāo)搜索與路徑搜索研究，是在地圖全局信息已知的情況下，針對柵格劃分方式或搜索算法進(jìn)行優(yōu)化。一方面，現(xiàn)有研究是依賴新穎的地圖柵格劃分方式，使得原有算法的表現(xiàn)更為出色[1-4]；另一方面是通過結(jié)合其他算法、公式等對算法進(jìn)行改進(jìn)[5-6]，但均是在地圖全局信息已知的情況下實(shí)現(xiàn)的。禁忌搜索算法研究中，搜索目標(biāo)一般為最短路徑或最佳的網(wǎng)絡(luò)結(jié)構(gòu)等，屬于車輛路徑問題(Vehicle Routing Problem, VRP)[7-9]，不能完全覆蓋本文提出的問題場景。本文所解決的問題中，現(xiàn)實(shí)環(huán)境處于未知狀態(tài)，為了模擬傳感器、探測器收集信息能力有限的情況，本文假設(shè)搜索者只能獲悉周圍環(huán)境信息。這與同步定位與建圖(Simultaneous Localization and Mapping, SLAM)任務(wù)類似，該方面的現(xiàn)有研究目標(biāo)普遍為地圖構(gòu)建的全面性[10-11]，不針對單獨(dú)的目標(biāo)搜索。并且研究均面向以機(jī)器人為搜索者的場景[10-13]，對搜索的迭代次數(shù)沒有限制。因此，現(xiàn)有各方面研究普遍缺乏對本文所提出任務(wù)相關(guān)因素的考慮。

針對上述問題與研究背景，本文提出一種基于禁忌搜索(Tabu Search, TS)策略的、能夠利用經(jīng)驗(yàn)知識與環(huán)境信息的智能搜索方法。本文方法通過以正六邊形為單元建立柵格地圖模型，并選取若干與搜索目標(biāo)相關(guān)的指示變量，進(jìn)而對禁忌搜索算法中的候選解、鄰域解、鄰域解變換方式、禁忌表策略、價值函數(shù)與特赦條件等關(guān)鍵元素進(jìn)行建模，將問題轉(zhuǎn)化為禁忌搜索可求解的最優(yōu)化問題，從而實(shí)現(xiàn)一種能利用相關(guān)經(jīng)驗(yàn)知識，在地圖全局信息未知情況下使用的智能搜索方法。

1 禁忌搜索

1.1 禁忌搜索算法原理與步驟

1.1.1 算法原理

禁忌搜索算法是啟發(fā)式搜索算法中的經(jīng)典算法，主要應(yīng)用于組合優(yōu)化的問題場景中，屬于最優(yōu)化算法的一種。TS算法在1986年首次由Glover提出[14]，是基于局部搜索算法的改進(jìn)算法，主要思想為：通過模擬記憶的過程[15]，記錄局部搜索過程中遇到的解，即添加禁忌限制，在產(chǎn)生新解時需要查看禁忌表，從而在一定程度上避免了搜索陷入局部最優(yōu)的情況；另外，算法通過維持最佳記錄并引入特赦準(zhǔn)則，保證了在出現(xiàn)全局最優(yōu)解時能夠正常接納。

1.1.2 算法步驟

算法的主要參數(shù)包括候選解表長度、禁忌表長度、最大迭代次數(shù)、可接受偏差閾值。其中候選解表長度和禁忌表長度用于規(guī)定能夠產(chǎn)生的新解的最大值和能夠記憶的禁忌鄰域變換解的個數(shù)；最大迭代次數(shù)與可接受偏差閾值二者都是檢驗(yàn)程序是否滿足結(jié)束標(biāo)準(zhǔn)的參數(shù)，在算法實(shí)現(xiàn)過程中可以都采用，也可采用自定義的停止準(zhǔn)則。

實(shí)現(xiàn)算法的主要環(huán)節(jié)包括解的表示方法、鄰域解變換方式、禁忌表策略和價值函數(shù)。解的表示方法取決于所要解決的問題特點(diǎn)，合理的解的編碼方式能夠影響鄰域變換的效果與整個算法運(yùn)行表現(xiàn)；鄰域解的變換方式也需要根據(jù)實(shí)際問題進(jìn)行建模和定義；禁忌表策略一般采取的是將當(dāng)前解作為禁忌條目添加到禁忌表中，但隨問題情況不同也可做合理的調(diào)整；價值函數(shù)需要明確且有效反應(yīng)所要解決問題的程度，一般通過量化的方式以數(shù)值來衡量。

目前禁忌搜索算法流程較為通用的表示為：

1)基于一定方法產(chǎn)生初始解。

2)計算當(dāng)前解的價值函數(shù)，對最優(yōu)記錄進(jìn)行更新。判斷是否滿足停止條件，若滿足停止條件，則算法終止；否則，繼續(xù)執(zhí)行。

3)使用當(dāng)前解根據(jù)鄰域變換方式，計算全部候選解，根據(jù)候選解表長度對全部候選解進(jìn)行篩選，并按價值函數(shù)排序。

4)按順序依次選擇候選解，查看該解是否在禁忌表中，若不在禁忌表中，則選擇當(dāng)前鄰域解，并按照禁忌表策略更新禁忌表，回到步驟2；否則，需判斷是否滿足特赦準(zhǔn)則，若滿足，選擇該鄰域解，并對禁忌表更新，同時更新最優(yōu)記錄，回到步驟2；若不滿足，則依次選擇其他解，重復(fù)步驟4。

算法流程如圖1所示。

圖1 禁忌搜索算法流程圖

1.2 禁忌搜索算法優(yōu)勢分析

禁忌搜索算法與其他啟發(fā)式搜索算法之所以擁有在一定程度上擺脫局部最優(yōu)的能力，其本質(zhì)是依賴于算法在執(zhí)行過程中會存在接受非最優(yōu)解的情況，因此拓展了當(dāng)前解的可搜索鄰域，能更全面地對解空間進(jìn)行搜索[15-16]。禁忌表與特赦準(zhǔn)則也毋庸置疑是禁忌搜索算法的核心所在，因此本文所提出的方法中，對問題建模的最主要部分為禁忌策略的制定與特赦準(zhǔn)則的定義。除此之外，應(yīng)用禁忌搜索算法也需要將解、解空間、鄰域變換方式等根據(jù)實(shí)際問題合理定義，模型建立的合理性決定禁忌搜索算法優(yōu)勢發(fā)揮的程度。

2 問題建模與禁忌搜索應(yīng)用方法

2.1 正六邊形柵格地圖建模

2.1.1 搜索問題建模

為了簡化問題，本文方法不考慮現(xiàn)實(shí)世界的地形起伏、海拔高度等問題，以二維平面柵格地圖對搜索區(qū)域進(jìn)行描述，以俯視圖的視角來對問題進(jìn)行分析。對于實(shí)際情況中地形邊界的不規(guī)則情況可以對規(guī)則二維柵格地圖進(jìn)行修改，通過增補(bǔ)、刪除柵格以盡可能模擬實(shí)際的地形，常見情況如圖2所示。

圖2 搜索問題柵格建模方式

地圖建模的比例尺需要根據(jù)實(shí)際問題的情況確定，每個柵格單元的邊長應(yīng)該對應(yīng)實(shí)際情況中對搜索目標(biāo)的可觀察范圍或探測范圍，例如以人眼觀察目標(biāo)時，人眼可發(fā)現(xiàn)目標(biāo)的最遠(yuǎn)距離對應(yīng)柵格地圖中相鄰單元的距離，從而建立比例尺。

目標(biāo)的搜索過程還需要定義搜索目標(biāo)、搜索者初始位置和指示元素。以上3個因素是整個搜索過程中的主要部分，均在柵格地圖中占據(jù)一個單元格。搜索目標(biāo)應(yīng)以隨機(jī)的方式在地圖中產(chǎn)生，以此來模擬位置的未知；初始位置應(yīng)表示搜救人員或旅行隊(duì)伍的位置，并通過以單元格為移動單位的方式對整個地圖進(jìn)行搜索；指示元素則是與搜索目標(biāo)相關(guān)的自然現(xiàn)象或現(xiàn)實(shí)事物，對搜索方向起到指示作用。

由此將原問題建模為以一個初始單元為起點(diǎn)，逐格移動，直到到達(dá)搜索目標(biāo)所在的單元格的過程。由于比例尺定義中將能夠探測到目標(biāo)的最遠(yuǎn)距離定義為單元格之間的距離，因此可以合理假設(shè)，當(dāng)搜索者位置和搜索目標(biāo)處于同一單元格時，能夠發(fā)現(xiàn)搜索目標(biāo)。搜索過程的舉例如圖2中箭頭所示。

2.1.2 正六邊形柵格建模

上述建模過程中，柵格單元的形狀為正四邊形。該方式不能很貼切地對現(xiàn)實(shí)情況進(jìn)行模擬，由于每個單元格周圍存在8個單元格，而對角方向與非對角方向的單元格距離不同。因此采用以正四邊形為單元的柵格地圖建模方式，會出現(xiàn)搜索距離不統(tǒng)一、搜索方向過少以及路徑鋸齒化[17]的問題。

基于上述情況，本文采取正六邊形的單元格[2,4,18]對原地圖模型進(jìn)行修改，可以實(shí)現(xiàn)6個方向的等距離移動，既保證了移動距離的統(tǒng)一，也增加了可選的前進(jìn)方向，對實(shí)際情況能達(dá)到更真實(shí)的模擬。修改后的地圖建模如圖3所示。雖然更為精細(xì)的模型可以采取邊數(shù)更多的多邊形結(jié)構(gòu)，但是會導(dǎo)致不能使用單一形狀平鋪整個柵格地圖，需要使用2種以上的多邊形平鋪地圖，會極大增加模型的復(fù)雜度，在本文中不做深入研究。

圖3 正六邊形柵格地圖建模

為便于后續(xù)研究，對柵格地圖中正六邊形單元的一些屬性進(jìn)行定義。

如圖3中所示，對單元格周圍的6個單元格按照順時針方向進(jìn)行編號，使用數(shù)字1～6表示當(dāng)前單元可以選擇的移動方向。

每個單元可以經(jīng)過一步移動到相鄰的單元格，將此定義為一個步長即單位距離[2,19-20]。由此可以定義任意2個單元格之間的距離為，從一個單元經(jīng)過最少的移動次數(shù)到達(dá)另一個單元格所使用的步數(shù)。例如，如圖3中所示搜索者所在單元與目標(biāo)所在單元的距離為3個單位。

2.2 禁忌搜索應(yīng)用方法

2.2.1 初始解與搜索目標(biāo)

由于問題場景為實(shí)際的人員在一定區(qū)域內(nèi)進(jìn)行搜索，因此不能通過蒙特卡洛隨機(jī)等方法產(chǎn)生初始解，應(yīng)由實(shí)際問題確定，不能進(jìn)行優(yōu)化。

在程序模擬中，采取初始解與搜索目標(biāo)隨機(jī)產(chǎn)生的方式進(jìn)行實(shí)驗(yàn)。

2.2.2 解與鄰域解

基于正六邊形的柵格地圖建模方式，柵格地圖中的每個單元格都是問題的一個解，最優(yōu)解即為目標(biāo)所在單元格。對每個單元格定義單元價值函數(shù)，用于衡量單元格的優(yōu)劣。

搜索的過程對應(yīng)在單元格之間移動的過程，每次移動的方向可以用圖3中所示的方法進(jìn)行編碼，每個方向?qū)?yīng)1～6中的一個數(shù)字。產(chǎn)生鄰域解時，需要對當(dāng)前單元格的6個方向分別計算方向價值函數(shù)，用于衡量方向的優(yōu)劣。

2.2.3 禁忌策略

禁忌策略設(shè)計是本文方法的核心部分，禁忌搜索的優(yōu)勢在于能夠避免迂回搜索，跳出局部最優(yōu)的區(qū)域，充分拓展鄰域搜索范圍。為保證上述優(yōu)勢的發(fā)揮，本文提出一種“雙禁忌表”的創(chuàng)新思路，定義2個禁忌表分別對應(yīng)存放單元格禁忌和搜索方向禁忌，命名為路徑禁忌表和方向禁忌表。

1)方向禁忌。

方向禁忌表用于實(shí)現(xiàn)搜索過程中對指示元素分布的記憶能力。在一般的禁忌搜索算法中，通常將問題的解表示為字符串，通過相鄰字符對換產(chǎn)生鄰域解，同時在禁忌表中添加對換的字符。但根據(jù)本文方法的建模方式，鄰域解的產(chǎn)生過程依賴搜索方向的選擇，搜索方向比單元格本身更具有參考價值，因此使用方向禁忌表來記憶搜索方向。

搜索方向由數(shù)字1～6來表示，為防止迂回搜索，禁忌表的添加方式為，將當(dāng)前移動方向的相反方向的數(shù)字添加到禁忌表中，對應(yīng)規(guī)則為1與4、2與5、3與6分別對應(yīng)。在正六邊形單元組成的柵格地圖中，當(dāng)目前所有移動的方向矢量和為零向量時，搜索過程陷入了一個由若干單元格組成的循環(huán)，即迂回搜索。為減少循環(huán)的產(chǎn)生，在更新方向禁忌表時，需要將與移動方向相反的數(shù)字與該數(shù)字兩側(cè)的數(shù)字，共3個數(shù)字同時添加到禁忌表中，否則搜索過程可能會陷入1-3-5-1或2-4-6-2這樣的循環(huán)中。通過將相反3個方向都添加到禁忌表中，限制了搜索的整體方向，實(shí)現(xiàn)了對上一步的搜索方向保持一定的記憶。禁忌條目添加的順序應(yīng)該為先添加相反方向兩側(cè)的數(shù)字，再添加相反方向正對的數(shù)字，使得正對方向的禁忌最后解除。兩側(cè)方向的添加順序可以由方向價值函數(shù)比較得出。

2)路徑禁忌。

為實(shí)現(xiàn)對搜索過的單元格的記憶，使用路徑禁忌表限制搜索路徑。禁忌添加策略與一般禁忌搜索策略相同，將到達(dá)的單元格位置進(jìn)行記錄。路徑禁忌還能在一定程度上防止陷入周期較長的循環(huán)中，方向禁忌受限于禁忌表長度必須小于6，不能夠有效避免長周期的循環(huán)搜索產(chǎn)生。通過路徑禁忌與方向禁忌結(jié)合的方式，可以有效減少迂回搜索的出現(xiàn)。路徑禁忌表長度不宜過長，防止出現(xiàn)搜索路徑分割地圖，導(dǎo)致地圖一側(cè)單元格不能被搜索。特赦準(zhǔn)則可以對方向禁忌表中的記錄生效，但對路徑禁忌表不適用。

2.2.4 價值函數(shù)與最優(yōu)記錄

基于解的定義和鄰域解的產(chǎn)生方式，定義2種價值函數(shù)。其中單元價值函數(shù)用于衡量單元格優(yōu)劣程度，方向價值函數(shù)用于衡量移動方向的優(yōu)劣程度，具體計算方式的得出，需要根據(jù)實(shí)際問題中指示元素的特點(diǎn)進(jìn)行設(shè)計并建模。

2種價值函數(shù)對應(yīng)的最優(yōu)記錄也包括2個，最優(yōu)方向記錄和最優(yōu)單元記錄，用于特赦準(zhǔn)則的實(shí)現(xiàn)。

2.2.5 特赦準(zhǔn)則

當(dāng)某個方向價值函數(shù)優(yōu)于最優(yōu)方向記錄或某個方向的單元格價值函數(shù)值優(yōu)于最優(yōu)單元記錄，二者滿足其一即可，此時特赦準(zhǔn)則生效。但特赦準(zhǔn)則只能針對方向禁忌表，不能夠特赦路徑禁忌表中的限制。

當(dāng)?shù)竭_(dá)邊界且無可用候選解時，將方向禁忌表中的第一條記錄解禁，直到存在可用候選解；如果方向禁忌表已為空，但仍無可用候選解，則進(jìn)行回溯，回到之前的單元格，并將該邊界單元格添加到路徑禁忌表中。

2.2.6 停止條件

當(dāng)搜索達(dá)到目標(biāo)單元格時，滿足停止條件，程序返回成功。

當(dāng)?shù)螖?shù)超過設(shè)定參數(shù)時，滿足停止條件，程序返回失敗。

2.3 仿真實(shí)驗(yàn)算法設(shè)計

運(yùn)用以上算法進(jìn)行仿真實(shí)驗(yàn)，本文對仿真實(shí)驗(yàn)的流程進(jìn)行描述。實(shí)驗(yàn)之前需要設(shè)置柵格地圖大小，隨機(jī)生成起始位置、目標(biāo)位置、指示元素，并對價值函數(shù)與特赦準(zhǔn)則進(jìn)行定義。

算法主要包括以下步驟：

1)根據(jù)地圖大小，合理設(shè)置禁忌表長度、迭代次數(shù)等參數(shù)。

2)計算當(dāng)前單元格的單元價值函數(shù)，對最優(yōu)記錄進(jìn)行更新。判斷停止條件，滿足則停止；否則繼續(xù)執(zhí)行。

3)在路徑禁忌表中添加當(dāng)前單元格。計算6個方向的方向價值函數(shù)作為候選解，根據(jù)方向價值函數(shù)排序。

4)依次查看候選解，查詢路徑禁忌表與方向禁忌表，若在禁忌表中，且不滿足特赦準(zhǔn)則，則查看下一候選解，重復(fù)步驟4，直到嘗試過所有解；否則，采用該解，并將與該解所對應(yīng)方向相反的3個方向添加到方向禁忌表中，回到步驟2。

5)若候選解全部不滿足條件，則進(jìn)行回溯，將當(dāng)前單元格添加到路徑禁忌表中，回退到前一單元格，回到步驟2。

3 案例設(shè)計與實(shí)驗(yàn)結(jié)果

3.1 案例描述

基于上述模型與算法，本文以沙漠水源搜索為案例背景進(jìn)行實(shí)驗(yàn)。

水資源在沙漠旅行中尤其重要，但由于攜帶負(fù)擔(dān)問題和沙漠中惡劣情況頻發(fā)的特點(diǎn)，水物資短缺是常出現(xiàn)的情況。在旅途中一般借助當(dāng)?shù)亟?jīng)驗(yàn)與自然信息來搜尋沙漠中的水源，對儲備進(jìn)行補(bǔ)充。沙漠中常見的水源包括地下水、蒸餾水、植物或小型綠洲。根據(jù)相關(guān)研究[21-24]，沙漠中水源地周圍會出現(xiàn)動、植物相對密集的情況，是對水源搜索有力的經(jīng)驗(yàn)判斷依據(jù)，濕度、云層、風(fēng)向等也對判斷有一定參考作用。

本文以小型綠洲為搜索目標(biāo)，以昆蟲、植被、小型動物、土壤濕度為指示元素對價值函數(shù)進(jìn)行定義，上述4個指示元素對單元價值函數(shù)與方向價值函數(shù)的計算結(jié)果都有正面的影響。

3.2 實(shí)驗(yàn)設(shè)計

實(shí)驗(yàn)算法代碼依據(jù)2.3節(jié)中的算法流程進(jìn)行實(shí)現(xiàn)與編寫，并命名為“路徑-方向禁忌搜索”(Path-Direction Tabu Search, PDTS)策略。除算法外，還需要具體明確的部分包括實(shí)驗(yàn)規(guī)模、實(shí)驗(yàn)評價標(biāo)準(zhǔn)與價值函數(shù)的定義方式。

實(shí)驗(yàn)采取3種不同規(guī)模的柵格地圖，均使用規(guī)則地形對沙漠地形環(huán)境進(jìn)行模擬，地圖規(guī)模分別為23×23、50×50以及100×100大小的地圖柵格。每種地圖情況分別進(jìn)行50萬次隨機(jī)模擬，統(tǒng)計成功找到搜索目標(biāo)的運(yùn)行次數(shù)占比(成功率)與平均搜索所用步數(shù)(平均搜索步數(shù))作為衡量算法能力的指標(biāo)。

為驗(yàn)證本文所提出的PDTS策略的有效性與合理性，本文采取了3種算法作為對照實(shí)驗(yàn)組，分別為無禁忌策略的“爬山法”(Hill Climbing, HC)以及2種僅使用一個禁忌表的“路徑禁忌”(Path Tabu Search, PTS)策略方法與“方向禁忌”(Direction Tabu Search, DTS)策略方法。

為了簡單、合理地定義價值函數(shù)，本文中對沙漠水源相關(guān)的指示元素做出了若干假設(shè)，便于描述價值函數(shù)的定義方式。

3.2.1 指示元素設(shè)計

假設(shè)1 指示元素分布在搜索目標(biāo)的周圍，并且越靠近目標(biāo)，分布得越密集。

假設(shè)1是為了模擬昆蟲、植物與小型動物在水源豐富的區(qū)域會更加密集的經(jīng)驗(yàn)結(jié)論。實(shí)現(xiàn)方式為，通過對水源目標(biāo)周圍的單元格依照距離的遠(yuǎn)近賦予不同的權(quán)重，將若干指示元素按照權(quán)重分布到搜索目標(biāo)周圍的單元格中。為了保證實(shí)驗(yàn)的合理性，對指示元素的數(shù)量進(jìn)行設(shè)計，規(guī)定各個指示元素占據(jù)的單元格比例，以更好地模擬沙漠貧瘠環(huán)境。

假設(shè)2 每種指示元素存在一個可被觀察到的距離，稱為輻射范圍。不同指示元素輻射范圍不同。

假設(shè)2是基于不同的生物活動范圍不同、留下的痕跡不同所做出的假設(shè)。小型動物的活動范圍大、痕跡易于觀察；植物則依賴于其茂盛程度決定；昆蟲則沒有明顯痕跡，且位置較為隱蔽?；谝陨霞僭O(shè)，賦予每個指示元素輻射范圍距離屬性，在其輻射距離內(nèi)的單元格，可以觀察到該指示元素。

3.2.2 價值函數(shù)定義

假設(shè)3 指示元素對輻射范圍內(nèi)的單元格，在指示元素所在方向上提供方向價值函數(shù)的貢獻(xiàn)。

假設(shè)3中的方向由圖4所示定義[18,20]。每個單元格有6個方向，每個方向?qū)?yīng)一個60°角，在其角度涵蓋的范圍內(nèi)的指示元素，對該方向的方向價值函數(shù)計算有正向貢獻(xiàn)。

圖4 方向定義方式說明

基于以上假設(shè)與規(guī)則，對所有參數(shù)進(jìn)行具體定義，得出價值函數(shù)的計算方式。具體參數(shù)設(shè)計見表1。

表1 指示元素參數(shù)設(shè)計表

表1中的水源即為搜索目標(biāo)。水源附近的土壤濕度一般會遠(yuǎn)高于普通地區(qū)，因此當(dāng)靠近水源地時，土壤濕度的影響尤為重要。因此對水源附近的單元格，依據(jù)距離遠(yuǎn)近，按照等差數(shù)列的方式，分別賦予距離在5以內(nèi)的單元格1500～9000的貢獻(xiàn)參數(shù)。

普通單元格內(nèi)的濕度應(yīng)有小幅度的隨機(jī)，設(shè)定為1～5的隨機(jī)值。

單元價值函數(shù)的計算方式為，該單元的土壤濕度貢獻(xiàn)值與該單元內(nèi)所有指示元素貢獻(xiàn)值之和。若單元格內(nèi)無指示元素，則第2項(xiàng)值為0，計算方法如公式(1)所示。

fu=hu+∑pu

(1)

其中，fu表示單元價值函數(shù)，hu表示單元格濕度貢獻(xiàn)值，pu表示在該單元格內(nèi)的某一個指示元素貢獻(xiàn)值。

方向價值函數(shù)的計算方式為，該方向的相鄰單元格的土壤濕度貢獻(xiàn)值與該方向上角度涵蓋內(nèi)且在輻射范圍內(nèi)的所有指示元素貢獻(xiàn)值之和,如公式(2)所示。

fd=hd+∑pd

(2)

其中，fd表示方向價值函數(shù)，hd表示該方向相鄰單元格的濕度貢獻(xiàn)值，pd表示該方向上在輻射范圍內(nèi)的某一個指示元素貢獻(xiàn)值。

3.3 實(shí)驗(yàn)結(jié)果與方法對比

3.3.1 實(shí)驗(yàn)結(jié)果

本文以C++為編程語言對上述模型與算法進(jìn)行編碼實(shí)現(xiàn)，經(jīng)過對參數(shù)的修正與調(diào)整，分別在3種不同的地圖規(guī)模下對原問題進(jìn)行仿真模擬實(shí)驗(yàn)。在不同的柵格地圖規(guī)模下對本文所提出的“路徑-方向禁忌搜索”(PDTS)算法進(jìn)行50萬次的隨機(jī)模擬，3種指示元素生成的占比分別為，15%的單元格為植物，1%的單元格為小型動物，10%的單元格為昆蟲。由于多個指示元素可能重合，理論上指示元素所占據(jù)的單元格數(shù)目在15%～26%之間。將搜索的最大次數(shù)限制定義為柵格總單元格數(shù)的一半左右，即遍歷查詢方式搜索次數(shù)的平均期望。

經(jīng)實(shí)驗(yàn)得出不同規(guī)模下，PDTS方法的運(yùn)行結(jié)果如表2所示。

表2 PDTS算法實(shí)驗(yàn)結(jié)果

23×23大小柵格地圖，搜索成功率為97.28%，平均搜索步數(shù)為29步。

50×50大小柵格地圖，搜索成功率為91.70%，平均搜索步數(shù)為90步。

100×100大小柵格地圖，搜索成功率為74.43%，平均搜索步數(shù)為293步。

當(dāng)?shù)貓D規(guī)模在103數(shù)量級或以下時，本文所提出的方法可以達(dá)到91.7%以上成功率，對于上萬級別的柵格數(shù)量的情況，算法的表現(xiàn)會隨地圖規(guī)模增大而顯著下降。對2500個以內(nèi)的單元格數(shù)量的柵格地圖搜索，本文所提出的方法有較好的表現(xiàn)與參考價值。平均搜索步數(shù)與地圖規(guī)模的邊長在同一數(shù)量級，相比于遍歷查找的方式顯著地降低了搜索所需經(jīng)過的單元格，在保證一定成功率的情況下，極大優(yōu)化了搜索效率。

3.3.2 方法對比

基于上述實(shí)驗(yàn)的地圖模型參數(shù)與價值函數(shù)計算方式，本文分別編碼實(shí)現(xiàn)了“爬山法”(HC)[25]、“路徑禁忌搜索”(PTS)與“方向禁忌搜索”(DTS)算法作為PDTS的對比算法，同樣進(jìn)行50萬次的模擬實(shí)驗(yàn)。

將2個禁忌表的策略省略，僅計算方向價值函數(shù)，選擇最優(yōu)方向作為搜索依據(jù)，即以HC算法思路進(jìn)行實(shí)驗(yàn)，得到各項(xiàng)實(shí)驗(yàn)結(jié)果如表3所示。

表3 HC算法實(shí)驗(yàn)結(jié)果

對本文提出的PDTS算法進(jìn)行部分修改，分別省略路徑禁忌表與方向禁忌表，即可實(shí)現(xiàn)DTS與PTS的算法流程。

PTS算法實(shí)驗(yàn)結(jié)果如表4所示。

表4 PTS算法實(shí)驗(yàn)結(jié)果

DTS算法實(shí)驗(yàn)結(jié)果如表5所示。

表5 DTS算法實(shí)驗(yàn)結(jié)果

綜合上述4個算法的實(shí)驗(yàn)數(shù)據(jù)，在搜索成功率與算法平均搜索步數(shù)2個方面對其進(jìn)行對比，如圖5所示。

圖5 算法對比

通過圖5(a)的比較結(jié)果可以看出，HC相比于PDTS在搜索成功率上低36.68個百分點(diǎn)以上，在10000以上單元格數(shù)目的柵格地圖中，HC算法基本失效，而PDTS方法在此規(guī)模的柵格地圖中仍有一定的可行性與有效性。

基于“雙禁忌表”的PDTS方法，相比于2種采用單一禁忌表的方法，在較大規(guī)模柵格地圖中有更高的成功率，表明2個禁忌表策略可以同時生效，避免算法陷入局部最優(yōu)。但在小規(guī)模地圖中，PTS算法的表現(xiàn)更佳，說明在小規(guī)模地圖中雙禁忌表會產(chǎn)生沖突從而影響算法性能，但隨著問題規(guī)模增大，PDTS的成功率相比于PTS與DTS方法會顯著提高，在2500以上單元格的柵格地圖中，成功率至少提高3.12個百分點(diǎn)，因此“雙禁忌表”的策略依然有一定合理性和較好的優(yōu)化效果。

如圖5(b)所示，在小規(guī)模地圖中各個算法的平均搜索步數(shù)基本一致，在大規(guī)模地圖中，HC算法失效，因此其平均搜索步數(shù)不具備好的參考價值(圖中虛線表示)。PDTS方法在地圖規(guī)模增大時，平均搜索步數(shù)相比于其他方法有所減少，在保證搜索成功率的同時，可以通過更少的迭代次數(shù)使算法終止，相比于其他算法步數(shù)優(yōu)化比例能夠提高0.8個百分點(diǎn)。

綜上，本文所提出的基于“雙禁忌表”的智能搜索方法相比于單一禁忌策略的算法和“爬山法”有更高的搜索成功率，并且在搜索步數(shù)上也能夠?qū)崿F(xiàn)優(yōu)化效果。

4 結(jié)束語

本文基于常見現(xiàn)實(shí)場景，提出了一種依賴經(jīng)驗(yàn)知識輔助的目標(biāo)搜索問題，并對該問題進(jìn)行地圖建模與算法建模，通過以正六邊形為單元建立柵格地圖模型，對實(shí)際搜索狀態(tài)進(jìn)行貼切模擬，使用基于“雙禁忌表”的改良禁忌搜索算法對該問題進(jìn)行解決，提出了一套完整的建模方法與算法思路。

以沙漠水源搜索為實(shí)際案例，對本文的算法進(jìn)行編程實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文的方法在少于2500個單元格規(guī)模的場景中，均能夠起到較好的優(yōu)化效果，對現(xiàn)有智能輔助工具的實(shí)現(xiàn)有參考價值。相比于“爬山法”和單禁忌表的2種禁忌搜索方法，本文的算法可以避免多數(shù)局部最優(yōu)解，并且優(yōu)化搜索步數(shù)。但當(dāng)問題規(guī)模超過上萬個單元格時，算法在成功率上表現(xiàn)欠佳。

本文所提出的方法屬于較抽象的算法模型，泛化能力較強(qiáng)，但針對不同的實(shí)際問題需要具體且嚴(yán)謹(jǐn)?shù)姆治鲞^程，存在較多開放性的應(yīng)用場景，并且方法中的地圖模型與算法策略仍可針對問題進(jìn)行細(xì)致優(yōu)化，本文為相關(guān)研究提供了一定的基礎(chǔ)思路。