禁忌搜索在柵格地圖中的應用

刁 說

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

0 引 言

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

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

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

1 禁忌搜索

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

1.1.1 算法原理

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

1.1.2 算法步驟

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

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

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

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

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

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

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

算法流程如圖1所示。

圖1 禁忌搜索算法流程圖

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

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

2 問題建模與禁忌搜索應用方法

2.1 正六邊形柵格地圖建模

2.1.1 搜索問題建模

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

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

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

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

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

2.1.2 正六邊形柵格建模

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

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

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

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

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

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

2.2 禁忌搜索應用方法

2.2.1 初始解與搜索目標

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

在程序模擬中，采取初始解與搜索目標隨機產(chǎn)生的方式進行實驗。

2.2.2 解與鄰域解

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

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

2.2.3 禁忌策略

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

1)方向禁忌。

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

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

2)路徑禁忌。

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

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

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

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

2.2.5 特赦準則

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

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

2.2.6 停止條件

當搜索達到目標單元格時，滿足停止條件，程序返回成功。

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

2.3 仿真實驗算法設(shè)計

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

算法主要包括以下步驟：

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

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

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

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

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

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

3.1 案例描述

基于上述模型與算法，本文以沙漠水源搜索為案例背景進行實驗。

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

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

3.2 實驗設(shè)計

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

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

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

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

3.2.1 指示元素設(shè)計

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

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

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

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

3.2.2 價值函數(shù)定義

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

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

圖4 方向定義方式說明

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

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

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

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

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

fu=hu+∑pu

(1)

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

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

fd=hd+∑pd

(2)

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

3.3 實驗結(jié)果與方法對比

3.3.1 實驗結(jié)果

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

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

表2 PDTS算法實驗結(jié)果

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

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

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

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

3.3.2 方法對比

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

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

表3 HC算法實驗結(jié)果

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

PTS算法實驗結(jié)果如表4所示。

表4 PTS算法實驗結(jié)果

DTS算法實驗結(jié)果如表5所示。

表5 DTS算法實驗結(jié)果

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

圖5 算法對比

通過圖5(a)的比較結(jié)果可以看出，HC相比于PDTS在搜索成功率上低36.68個百分點以上，在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個百分點，因此“雙禁忌表”的策略依然有一定合理性和較好的優(yōu)化效果。

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

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

4 結(jié)束語

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

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

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