禁忌搜索在栅格地图中的应用

刁 说

(华北计算技术研究所系统八部，北京 100083)

0 引 言

在计算机程序模拟的二维栅格地图中，通常采用遍历的方式来找寻有特殊值的网格位置坐标。而在现实世界中，受限于客观条件，遍历搜索的方式不可行，例如旅行人员在沙漠之中寻找水源时，储备物资不足以支撑遍历式的探索。现实中解决上述问题的常用方法为，通过观察与搜索目标相关的自然现象或指示性标志从而确定大致的搜索方向，以此来达到快速、高效找寻目标的目的。此类问题的现实应用场景包括海上航行、丛林穿越、灾后搜救等工作。在上述紧急情况下，迷路者或搜救者受限于网络覆盖范围，缺乏先进电子设备辅助，无法获得地理定位与地图信息，只能收集周围环境信息并通过经验判断的方式决定前进路线，并且需要在有限的移动距离内找到目标。合理地利用人类常识与生活经验，对紧急情况下的路径找寻以及目标搜索有极大帮助。因此通过人工智能方法的建模应用，实现经验知识的有效利用，并研究相关算法模型作为寻路工具的实现参考，有着重要的理论和现实意义。

目前，基于栅格地图的目标搜索与路径搜索研究，是在地图全局信息已知的情况下，针对栅格划分方式或搜索算法进行优化。一方面，现有研究是依赖新颖的地图栅格划分方式，使得原有算法的表现更为出色[1-4]；另一方面是通过结合其他算法、公式等对算法进行改进[5-6]，但均是在地图全局信息已知的情况下实现的。禁忌搜索算法研究中，搜索目标一般为最短路径或最佳的网络结构等，属于车辆路径问题(Vehicle Routing Problem, VRP)[7-9]，不能完全覆盖本文提出的问题场景。本文所解决的问题中，现实环境处于未知状态，为了模拟传感器、探测器收集信息能力有限的情况，本文假设搜索者只能获悉周围环境信息。这与同步定位与建图(Simultaneous Localization and Mapping, SLAM)任务类似，该方面的现有研究目标普遍为地图构建的全面性[10-11]，不针对单独的目标搜索。并且研究均面向以机器人为搜索者的场景[10-13]，对搜索的迭代次数没有限制。因此，现有各方面研究普遍缺乏对本文所提出任务相关因素的考虑。

针对上述问题与研究背景，本文提出一种基于禁忌搜索(Tabu Search, TS)策略的、能够利用经验知识与环境信息的智能搜索方法。本文方法通过以正六边形为单元建立栅格地图模型，并选取若干与搜索目标相关的指示变量，进而对禁忌搜索算法中的候选解、邻域解、邻域解变换方式、禁忌表策略、价值函数与特赦条件等关键元素进行建模，将问题转化为禁忌搜索可求解的最优化问题，从而实现一种能利用相关经验知识，在地图全局信息未知情况下使用的智能搜索方法。

1 禁忌搜索

1.1 禁忌搜索算法原理与步骤

1.1.1 算法原理

禁忌搜索算法是启发式搜索算法中的经典算法，主要应用于组合优化的问题场景中，属于最优化算法的一种。TS算法在1986年首次由Glover提出[14]，是基于局部搜索算法的改进算法，主要思想为：通过模拟记忆的过程[15]，记录局部搜索过程中遇到的解，即添加禁忌限制，在产生新解时需要查看禁忌表，从而在一定程度上避免了搜索陷入局部最优的情况；另外，算法通过维持最佳记录并引入特赦准则，保证了在出现全局最优解时能够正常接纳。

1.1.2 算法步骤

算法的主要参数包括候选解表长度、禁忌表长度、最大迭代次数、可接受偏差阈值。其中候选解表长度和禁忌表长度用于规定能够产生的新解的最大值和能够记忆的禁忌邻域变换解的个数；最大迭代次数与可接受偏差阈值二者都是检验程序是否满足结束标准的参数，在算法实现过程中可以都采用，也可采用自定义的停止准则。

实现算法的主要环节包括解的表示方法、邻域解变换方式、禁忌表策略和价值函数。解的表示方法取决于所要解决的问题特点，合理的解的编码方式能够影响邻域变换的效果与整个算法运行表现；邻域解的变换方式也需要根据实际问题进行建模和定义；禁忌表策略一般采取的是将当前解作为禁忌条目添加到禁忌表中，但随问题情况不同也可做合理的调整；价值函数需要明确且有效反应所要解决问题的程度，一般通过量化的方式以数值来衡量。

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

1)基于一定方法产生初始解。

2)计算当前解的价值函数，对最优记录进行更新。判断是否满足停止条件，若满足停止条件，则算法终止；否则，继续执行。

3)使用当前解根据邻域变换方式，计算全部候选解，根据候选解表长度对全部候选解进行筛选，并按价值函数排序。

4)按顺序依次选择候选解，查看该解是否在禁忌表中，若不在禁忌表中，则选择当前邻域解，并按照禁忌表策略更新禁忌表，回到步骤2；否则，需判断是否满足特赦准则，若满足，选择该邻域解，并对禁忌表更新，同时更新最优记录，回到步骤2；若不满足，则依次选择其他解，重复步骤4。

算法流程如图1所示。

图1 禁忌搜索算法流程图

1.2 禁忌搜索算法优势分析

禁忌搜索算法与其他启发式搜索算法之所以拥有在一定程度上摆脱局部最优的能力，其本质是依赖于算法在执行过程中会存在接受非最优解的情况，因此拓展了当前解的可搜索邻域，能更全面地对解空间进行搜索[15-16]。禁忌表与特赦准则也毋庸置疑是禁忌搜索算法的核心所在，因此本文所提出的方法中，对问题建模的最主要部分为禁忌策略的制定与特赦准则的定义。除此之外，应用禁忌搜索算法也需要将解、解空间、邻域变换方式等根据实际问题合理定义，模型建立的合理性决定禁忌搜索算法优势发挥的程度。

2 问题建模与禁忌搜索应用方法

2.1 正六边形栅格地图建模

2.1.1 搜索问题建模

为了简化问题，本文方法不考虑现实世界的地形起伏、海拔高度等问题，以二维平面栅格地图对搜索区域进行描述，以俯视图的视角来对问题进行分析。对于实际情况中地形边界的不规则情况可以对规则二维栅格地图进行修改，通过增补、删除栅格以尽可能模拟实际的地形，常见情况如图2所示。

图2 搜索问题栅格建模方式

地图建模的比例尺需要根据实际问题的情况确定，每个栅格单元的边长应该对应实际情况中对搜索目标的可观察范围或探测范围，例如以人眼观察目标时，人眼可发现目标的最远距离对应栅格地图中相邻单元的距离，从而建立比例尺。

目标的搜索过程还需要定义搜索目标、搜索者初始位置和指示元素。以上3个因素是整个搜索过程中的主要部分，均在栅格地图中占据一个单元格。搜索目标应以随机的方式在地图中产生，以此来模拟位置的未知；初始位置应表示搜救人员或旅行队伍的位置，并通过以单元格为移动单位的方式对整个地图进行搜索；指示元素则是与搜索目标相关的自然现象或现实事物，对搜索方向起到指示作用。

由此将原问题建模为以一个初始单元为起点，逐格移动，直到到达搜索目标所在的单元格的过程。由于比例尺定义中将能够探测到目标的最远距离定义为单元格之间的距离，因此可以合理假设，当搜索者位置和搜索目标处于同一单元格时，能够发现搜索目标。搜索过程的举例如图2中箭头所示。

2.1.2 正六边形栅格建模

上述建模过程中，栅格单元的形状为正四边形。该方式不能很贴切地对现实情况进行模拟，由于每个单元格周围存在8个单元格，而对角方向与非对角方向的单元格距离不同。因此采用以正四边形为单元的栅格地图建模方式，会出现搜索距离不统一、搜索方向过少以及路径锯齿化[17]的问题。

基于上述情况，本文采取正六边形的单元格[2,4,18]对原地图模型进行修改，可以实现6个方向的等距离移动，既保证了移动距离的统一，也增加了可选的前进方向，对实际情况能达到更真实的模拟。修改后的地图建模如图3所示。虽然更为精细的模型可以采取边数更多的多边形结构，但是会导致不能使用单一形状平铺整个栅格地图，需要使用2种以上的多边形平铺地图，会极大增加模型的复杂度，在本文中不做深入研究。

图3 正六边形栅格地图建模

为便于后续研究，对栅格地图中正六边形单元的一些属性进行定义。

如图3中所示，对单元格周围的6个单元格按照顺时针方向进行编号，使用数字1～6表示当前单元可以选择的移动方向。

每个单元可以经过一步移动到相邻的单元格，将此定义为一个步长即单位距离[2,19-20]。由此可以定义任意2个单元格之间的距离为，从一个单元经过最少的移动次数到达另一个单元格所使用的步数。例如，如图3中所示搜索者所在单元与目标所在单元的距离为3个单位。

2.2 禁忌搜索应用方法

2.2.1 初始解与搜索目标

由于问题场景为实际的人员在一定区域内进行搜索，因此不能通过蒙特卡洛随机等方法产生初始解，应由实际问题确定，不能进行优化。

在程序模拟中，采取初始解与搜索目标随机产生的方式进行实验。

2.2.2 解与邻域解

基于正六边形的栅格地图建模方式，栅格地图中的每个单元格都是问题的一个解，最优解即为目标所在单元格。对每个单元格定义单元价值函数，用于衡量单元格的优劣。

搜索的过程对应在单元格之间移动的过程，每次移动的方向可以用图3中所示的方法进行编码，每个方向对应1～6中的一个数字。产生邻域解时，需要对当前单元格的6个方向分别计算方向价值函数，用于衡量方向的优劣。

2.2.3 禁忌策略

禁忌策略设计是本文方法的核心部分，禁忌搜索的优势在于能够避免迂回搜索，跳出局部最优的区域，充分拓展邻域搜索范围。为保证上述优势的发挥，本文提出一种“双禁忌表”的创新思路，定义2个禁忌表分别对应存放单元格禁忌和搜索方向禁忌，命名为路径禁忌表和方向禁忌表。

1)方向禁忌。

方向禁忌表用于实现搜索过程中对指示元素分布的记忆能力。在一般的禁忌搜索算法中，通常将问题的解表示为字符串，通过相邻字符对换产生邻域解，同时在禁忌表中添加对换的字符。但根据本文方法的建模方式，邻域解的产生过程依赖搜索方向的选择，搜索方向比单元格本身更具有参考价值，因此使用方向禁忌表来记忆搜索方向。

搜索方向由数字1～6来表示，为防止迂回搜索，禁忌表的添加方式为，将当前移动方向的相反方向的数字添加到禁忌表中，对应规则为1与4、2与5、3与6分别对应。在正六边形单元组成的栅格地图中，当目前所有移动的方向矢量和为零向量时，搜索过程陷入了一个由若干单元格组成的循环，即迂回搜索。为减少循环的产生，在更新方向禁忌表时，需要将与移动方向相反的数字与该数字两侧的数字，共3个数字同时添加到禁忌表中，否则搜索过程可能会陷入1-3-5-1或2-4-6-2这样的循环中。通过将相反3个方向都添加到禁忌表中，限制了搜索的整体方向，实现了对上一步的搜索方向保持一定的记忆。禁忌条目添加的顺序应该为先添加相反方向两侧的数字，再添加相反方向正对的数字，使得正对方向的禁忌最后解除。两侧方向的添加顺序可以由方向价值函数比较得出。

2)路径禁忌。

为实现对搜索过的单元格的记忆，使用路径禁忌表限制搜索路径。禁忌添加策略与一般禁忌搜索策略相同，将到达的单元格位置进行记录。路径禁忌还能在一定程度上防止陷入周期较长的循环中，方向禁忌受限于禁忌表长度必须小于6，不能够有效避免长周期的循环搜索产生。通过路径禁忌与方向禁忌结合的方式，可以有效减少迂回搜索的出现。路径禁忌表长度不宜过长，防止出现搜索路径分割地图，导致地图一侧单元格不能被搜索。特赦准则可以对方向禁忌表中的记录生效，但对路径禁忌表不适用。

2.2.4 价值函数与最优记录

基于解的定义和邻域解的产生方式，定义2种价值函数。其中单元价值函数用于衡量单元格优劣程度，方向价值函数用于衡量移动方向的优劣程度，具体计算方式的得出，需要根据实际问题中指示元素的特点进行设计并建模。

2种价值函数对应的最优记录也包括2个，最优方向记录和最优单元记录，用于特赦准则的实现。

2.2.5 特赦准则

当某个方向价值函数优于最优方向记录或某个方向的单元格价值函数值优于最优单元记录，二者满足其一即可，此时特赦准则生效。但特赦准则只能针对方向禁忌表，不能够特赦路径禁忌表中的限制。

当到达边界且无可用候选解时，将方向禁忌表中的第一条记录解禁，直到存在可用候选解；如果方向禁忌表已为空，但仍无可用候选解，则进行回溯，回到之前的单元格，并将该边界单元格添加到路径禁忌表中。

2.2.6 停止条件

当搜索达到目标单元格时，满足停止条件，程序返回成功。

当迭代次数超过设定参数时，满足停止条件，程序返回失败。

2.3 仿真实验算法设计

运用以上算法进行仿真实验，本文对仿真实验的流程进行描述。实验之前需要设置栅格地图大小，随机生成起始位置、目标位置、指示元素，并对价值函数与特赦准则进行定义。

算法主要包括以下步骤：

1)根据地图大小，合理设置禁忌表长度、迭代次数等参数。

2)计算当前单元格的单元价值函数，对最优记录进行更新。判断停止条件，满足则停止；否则继续执行。

3)在路径禁忌表中添加当前单元格。计算6个方向的方向价值函数作为候选解，根据方向价值函数排序。

4)依次查看候选解，查询路径禁忌表与方向禁忌表，若在禁忌表中，且不满足特赦准则，则查看下一候选解，重复步骤4，直到尝试过所有解；否则，采用该解，并将与该解所对应方向相反的3个方向添加到方向禁忌表中，回到步骤2。

5)若候选解全部不满足条件，则进行回溯，将当前单元格添加到路径禁忌表中，回退到前一单元格，回到步骤2。

3 案例设计与实验结果

3.1 案例描述

基于上述模型与算法，本文以沙漠水源搜索为案例背景进行实验。

水资源在沙漠旅行中尤其重要，但由于携带负担问题和沙漠中恶劣情况频发的特点，水物资短缺是常出现的情况。在旅途中一般借助当地经验与自然信息来搜寻沙漠中的水源，对储备进行补充。沙漠中常见的水源包括地下水、蒸馏水、植物或小型绿洲。根据相关研究[21-24]，沙漠中水源地周围会出现动、植物相对密集的情况，是对水源搜索有力的经验判断依据，湿度、云层、风向等也对判断有一定参考作用。

本文以小型绿洲为搜索目标，以昆虫、植被、小型动物、土壤湿度为指示元素对价值函数进行定义，上述4个指示元素对单元价值函数与方向价值函数的计算结果都有正面的影响。

3.2 实验设计

实验算法代码依据2.3节中的算法流程进行实现与编写，并命名为“路径-方向禁忌搜索”(Path-Direction Tabu Search, PDTS)策略。除算法外，还需要具体明确的部分包括实验规模、实验评价标准与价值函数的定义方式。

实验采取3种不同规模的栅格地图，均使用规则地形对沙漠地形环境进行模拟，地图规模分别为23×23、50×50以及100×100大小的地图栅格。每种地图情况分别进行50万次随机模拟，统计成功找到搜索目标的运行次数占比(成功率)与平均搜索所用步数(平均搜索步数)作为衡量算法能力的指标。

为验证本文所提出的PDTS策略的有效性与合理性，本文采取了3种算法作为对照实验组，分别为无禁忌策略的“爬山法”(Hill Climbing, HC)以及2种仅使用一个禁忌表的“路径禁忌”(Path Tabu Search, PTS)策略方法与“方向禁忌”(Direction Tabu Search, DTS)策略方法。

为了简单、合理地定义价值函数，本文中对沙漠水源相关的指示元素做出了若干假设，便于描述价值函数的定义方式。

3.2.1 指示元素设计

假设1 指示元素分布在搜索目标的周围，并且越靠近目标，分布得越密集。

假设1是为了模拟昆虫、植物与小型动物在水源丰富的区域会更加密集的经验结论。实现方式为，通过对水源目标周围的单元格依照距离的远近赋予不同的权重，将若干指示元素按照权重分布到搜索目标周围的单元格中。为了保证实验的合理性，对指示元素的数量进行设计，规定各个指示元素占据的单元格比例，以更好地模拟沙漠贫瘠环境。

假设2 每种指示元素存在一个可被观察到的距离，称为辐射范围。不同指示元素辐射范围不同。

假设2是基于不同的生物活动范围不同、留下的痕迹不同所做出的假设。小型动物的活动范围大、痕迹易于观察；植物则依赖于其茂盛程度决定；昆虫则没有明显痕迹，且位置较为隐蔽。基于以上假设，赋予每个指示元素辐射范围距离属性，在其辐射距离内的单元格，可以观察到该指示元素。

3.2.2 价值函数定义

假设3 指示元素对辐射范围内的单元格，在指示元素所在方向上提供方向价值函数的贡献。

假设3中的方向由图4所示定义[18,20]。每个单元格有6个方向，每个方向对应一个60°角，在其角度涵盖的范围内的指示元素，对该方向的方向价值函数计算有正向贡献。

图4 方向定义方式说明

基于以上假设与规则，对所有参数进行具体定义，得出价值函数的计算方式。具体参数设计见表1。

表1 指示元素参数设计表

表1中的水源即为搜索目标。水源附近的土壤湿度一般会远高于普通地区，因此当靠近水源地时，土壤湿度的影响尤为重要。因此对水源附近的单元格，依据距离远近，按照等差数列的方式，分别赋予距离在5以内的单元格1500～9000的贡献参数。

普通单元格内的湿度应有小幅度的随机，设定为1～5的随机值。

单元价值函数的计算方式为，该单元的土壤湿度贡献值与该单元内所有指示元素贡献值之和。若单元格内无指示元素，则第2项值为0，计算方法如公式(1)所示。

fu=hu+∑pu

(1)

其中，fu表示单元价值函数，hu表示单元格湿度贡献值，pu表示在该单元格内的某一个指示元素贡献值。

方向价值函数的计算方式为，该方向的相邻单元格的土壤湿度贡献值与该方向上角度涵盖内且在辐射范围内的所有指示元素贡献值之和,如公式(2)所示。

fd=hd+∑pd

(2)

其中，fd表示方向价值函数，hd表示该方向相邻单元格的湿度贡献值，pd表示该方向上在辐射范围内的某一个指示元素贡献值。

3.3 实验结果与方法对比

3.3.1 实验结果

本文以C++为编程语言对上述模型与算法进行编码实现，经过对参数的修正与调整，分别在3种不同的地图规模下对原问题进行仿真模拟实验。在不同的栅格地图规模下对本文所提出的“路径-方向禁忌搜索”(PDTS)算法进行50万次的随机模拟，3种指示元素生成的占比分别为，15%的单元格为植物，1%的单元格为小型动物，10%的单元格为昆虫。由于多个指示元素可能重合，理论上指示元素所占据的单元格数目在15%～26%之间。将搜索的最大次数限制定义为栅格总单元格数的一半左右，即遍历查询方式搜索次数的平均期望。

经实验得出不同规模下，PDTS方法的运行结果如表2所示。

表2 PDTS算法实验结果

23×23大小栅格地图，搜索成功率为97.28%，平均搜索步数为29步。

50×50大小栅格地图，搜索成功率为91.70%，平均搜索步数为90步。

100×100大小栅格地图，搜索成功率为74.43%，平均搜索步数为293步。

当地图规模在103数量级或以下时，本文所提出的方法可以达到91.7%以上成功率，对于上万级别的栅格数量的情况，算法的表现会随地图规模增大而显著下降。对2500个以内的单元格数量的栅格地图搜索，本文所提出的方法有较好的表现与参考价值。平均搜索步数与地图规模的边长在同一数量级，相比于遍历查找的方式显著地降低了搜索所需经过的单元格，在保证一定成功率的情况下，极大优化了搜索效率。

3.3.2 方法对比

基于上述实验的地图模型参数与价值函数计算方式，本文分别编码实现了“爬山法”(HC)[25]、“路径禁忌搜索”(PTS)与“方向禁忌搜索”(DTS)算法作为PDTS的对比算法，同样进行50万次的模拟实验。

将2个禁忌表的策略省略，仅计算方向价值函数，选择最优方向作为搜索依据，即以HC算法思路进行实验，得到各项实验结果如表3所示。

表3 HC算法实验结果

对本文提出的PDTS算法进行部分修改，分别省略路径禁忌表与方向禁忌表，即可实现DTS与PTS的算法流程。

PTS算法实验结果如表4所示。

表4 PTS算法实验结果

DTS算法实验结果如表5所示。

表5 DTS算法实验结果

综合上述4个算法的实验数据，在搜索成功率与算法平均搜索步数2个方面对其进行对比，如图5所示。

图5 算法对比

通过图5(a)的比较结果可以看出，HC相比于PDTS在搜索成功率上低36.68个百分点以上，在10000以上单元格数目的栅格地图中，HC算法基本失效，而PDTS方法在此规模的栅格地图中仍有一定的可行性与有效性。

基于“双禁忌表”的PDTS方法，相比于2种采用单一禁忌表的方法，在较大规模栅格地图中有更高的成功率，表明2个禁忌表策略可以同时生效，避免算法陷入局部最优。但在小规模地图中，PTS算法的表现更佳，说明在小规模地图中双禁忌表会产生冲突从而影响算法性能，但随着问题规模增大，PDTS的成功率相比于PTS与DTS方法会显著提高，在2500以上单元格的栅格地图中，成功率至少提高3.12个百分点，因此“双禁忌表”的策略依然有一定合理性和较好的优化效果。

如图5(b)所示，在小规模地图中各个算法的平均搜索步数基本一致，在大规模地图中，HC算法失效，因此其平均搜索步数不具备好的参考价值(图中虚线表示)。PDTS方法在地图规模增大时，平均搜索步数相比于其他方法有所减少，在保证搜索成功率的同时，可以通过更少的迭代次数使算法终止，相比于其他算法步数优化比例能够提高0.8个百分点。

综上，本文所提出的基于“双禁忌表”的智能搜索方法相比于单一禁忌策略的算法和“爬山法”有更高的搜索成功率，并且在搜索步数上也能够实现优化效果。

4 结束语

本文基于常见现实场景，提出了一种依赖经验知识辅助的目标搜索问题，并对该问题进行地图建模与算法建模，通过以正六边形为单元建立栅格地图模型，对实际搜索状态进行贴切模拟，使用基于“双禁忌表”的改良禁忌搜索算法对该问题进行解决，提出了一套完整的建模方法与算法思路。

以沙漠水源搜索为实际案例，对本文的算法进行编程实验，实验结果表明，本文的方法在少于2500个单元格规模的场景中，均能够起到较好的优化效果，对现有智能辅助工具的实现有参考价值。相比于“爬山法”和单禁忌表的2种禁忌搜索方法，本文的算法可以避免多数局部最优解，并且优化搜索步数。但当问题规模超过上万个单元格时，算法在成功率上表现欠佳。

本文所提出的方法属于较抽象的算法模型，泛化能力较强，但针对不同的实际问题需要具体且严谨的分析过程，存在较多开放性的应用场景，并且方法中的地图模型与算法策略仍可针对问题进行细致优化，本文为相关研究提供了一定的基础思路。