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

发布时间：2021-11-13 15:19所属平台：学报论文发表咨询网浏览： 次

摘要:以禁忌搜索算法为基础，对栅格地图搜索过程进行建模，提出一种能够利用经验知识的改良禁忌搜索算法，为航向指引、水源探测、灾后搜救等领域的智能辅助工具实现提供算法参考。对禁忌搜索算法的关键优势进行分析，提出以正六边形为单元的地图栅格划分方法，将问题建

　　摘要:以禁忌搜索算法为基础，对栅格地图搜索过程进行建模，提出一种能够利用经验知识的改良禁忌搜索算法，为航向指引、水源探测、灾后搜救等领域的智能辅助工具实现提供算法参考。对禁忌搜索算法的关键优势进行分析，提出以正六边形为单元的地图栅格划分方法，将问题建模为禁忌搜索可求解的最优化问题。以沙漠水源搜索为实例，选取多个沙漠元素作为水源探测相关指示参数，进行仿真实验。实验表明，本文所提出的方法可以在10000以内单元格数目的栅格地图中，搜索路径的成功规划次数占比达到91.7%以上，相比于“爬山法”策略提高至少36.68个百分点，搜索耗费的步数相比于遍历策略优化88.4%以上。

　　关键词:最优化算法;禁忌搜索;栅格地图;正六边形单元;沙漠水源搜索

　　0引言在计算机程序模拟的二维栅格地图中，通常采用遍历的方式来找寻有特殊值的网格位置坐标。而在现实世界中，受限于客观条件，遍历搜索的方式不可行，例如旅行人员在沙漠之中寻找水源时，储备物资不足以支撑遍历式的探索。现实中解决上述问题的常用方法为，通过观察与搜索目标相关的自然现象或指示性标志从而确定大致的搜索方向，以此来达到快速、高效找寻目标的目的。

　　此类问题的现实应用场景包括海上航行、丛林穿越、灾后搜救等工作。在上述紧急情况下，迷路者或搜救者受限于网络覆盖范围，缺乏先进电子设备辅助，无法获得地理定位与地图信息，只能收集周围环境信息并通过经验判断的方式决定前进路线，并且需要在有限的移动距离内找到目标。

　　合理地利用人类常识与生活经验，对紧急情况下的路径找寻以及目标搜索有极大帮助。因此通过人工智能方法的建模应用，实现经验知识的有效利用，并研究相关算法模型作为寻路工具的实现参考，有着重要的理论和现实意义。目前，基于栅格地图的目标搜索与路径搜索研究，是在地图全局信息已知的情况下，针对栅格划分方式或搜索算法进行优化。一方面，现有研究是依赖新颖的地图栅格划分方式，使得原有算法的表现更为出色[1-4];另一方面是通过结合其他算法、公式等对算法进行改进[5-6]，但均是在地图全局信息已知的情况下实现的。

　　禁忌搜索算法研究中，搜索目标一般为最短路径或最佳的网络结构等，属于车辆路径问题(VehicleRoutingProblem，VRP)[7-9]，不能完全覆盖本文提出的问题场景。本文所解决的问题中，现实环境处于未知状态，为了模拟传感器、探测器收集信息能力有限的情况，本文假设搜索者只能获悉周围环境信息。这与同步定位与建图(SimultaneousLocalizationandMapping，SLAM)任务类似，该方面的现有研究目标普遍为地图构建的全面性[10-11]，不针对单独的目标搜索。并且研究均面向以机器人为搜索者的场景[10-13]，对搜索的迭代次数没有限制。因此，现有各方面研究普遍缺乏对本文所提出任务相关因素的考虑。

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

　　1禁忌搜索

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

　　1.1.1算法原理

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

　　1.1.2算法步骤

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

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

　　1)基于一定方法产生初始解。2)计算当前解的价值函数，对最优记录进行更新。判断是否满足停止条件，若满足停止条件，则算法终止;否则，继续执行。3)使用当前解根据邻域变换方式，计算全部候选解，根据候选解表长度对全部候选解进行筛选，并按价值函数排序。4)按顺序依次选择候选解，查看该解是否在禁忌表中，若不在禁忌表中，则选择当前邻域解，并按照禁忌表策略更新禁忌表，回到步骤2;否则，需判断是否满足特赦准则，若满足，选择该邻域解，并对禁忌表更新，同时更新最优记录，回到步骤2;若不满足，则依次选择其他解，重复步骤4。

　　1.2禁忌搜索算法优势分析

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

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

　　2.1正六边形栅格地图建模

　　2.1.1搜索问题建模

　　为了简化问题，本文方法不考虑现实世界的地形起伏、海拔高度等问题，以二维平面栅格地图对搜索区域进行描述，以俯视图的视角来对问题进行分析。对于实际情况中地形边界的不规则情况可以对规则二维栅格地图进行修改，通过增补、删除栅格以尽可能模拟实际的地形。地图建模的比例尺需要根据实际问题的情况确定，每个栅格单元的边长应该对应实际情况中对搜索目标的可观察范围或探测范围，例如以人眼观察目标时，人眼可发现目标的最远距离对应栅格地图中相邻单元的距离，从而建立比例尺。目标的搜索过程还需要定义搜索目标、搜索者初始位置和指示元素。

　　以上3个因素是整个搜索过程中的主要部分，均在栅格地图中占据一个单元格。搜索目标应以随机的方式在地图中产生，以此来模拟位置的未知;初始位置应表示搜救人员或旅行队伍的位置，并通过以单元格为移动单位的方式对整个地图进行搜索;指示元素则是与搜索目标相关的自然现象或现实事物，对搜索方向起到指示作用。由此将原问题建模为以一个初始单元为起点，逐格移动，直到到达搜索目标所在的单元格的过程。由于比例尺定义中将能够探测到目标的最远距离定义为单元格之间的距离，因此可以合理假设，当搜索者位置和搜索目标处于同一单元格时，能够发现搜索目标。搜索过程的举例如图2中箭头所示。

　　2.2禁忌搜索应用方法

　　2.2.1初始解与搜索目标由于问题场景为实际的人员在一定区域内进行搜索，因此不能通过蒙特卡洛随机等方法产生初始解，应由实际问题确定，不能进行优化。在程序模拟中，采取初始解与搜索目标随机产生的方式进行实验。

　　2.2.2解与邻域解基于正六边形的栅格地图建模方式，栅格地图中的每个单元格都是问题的一个解，最优解即为目标所在单元格。对每个单元格定义单元价值函数，用于衡量单元格的优劣。搜索的过程对应在单元格之间移动的过程，每次移动的方向可以用图3中所示的方法进行编码，每个方向对应1～6中的一个数字。产生邻域解时，需要对当前单元格的6个方向分别计算方向价值函数，用于衡量方向的优劣。

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

　　2.3仿真实验算法设计

　　运用以上算法进行仿真实验，本文对仿真实验的流程进行描述。实验之前需要设置栅格地图大小，随机生成起始位置、目标位置、指示元素，并对价值函数与特赦准则进行定义。算法主要包括以下步骤:1)根据地图大小，合理设置禁忌表长度、迭代次数等参数。2)计算当前单元格的单元价值函数，对最优记录进行更新。判断停止条件，满足则停止;否则继续执行。3)在路径禁忌表中添加当前单元格。计算6个方向的方向价值函数作为候选解，根据方向价值函数排序。4)依次查看候选解，查询路径禁忌表与方向禁忌表，若在禁忌表中，且不满足特赦准则，则查看下一候选解，重复步骤4，直到尝试过所有解;否则，采用该解，并将与该解所对应方向相反的3个方向添加到方向禁忌表中，回到步骤2。5)若候选解全部不满足条件，则进行回溯，将当前单元格添加到路径禁忌表中，回退到前一单元格，回到步骤2。

　　3案例设计与实验结果

　　3.1案例描述

　　基于上述模型与算法，本文以沙漠水源搜索为案例背景进行实验。水资源在沙漠旅行中尤其重要，但由于携带负担问题和沙漠中恶劣情况频发的特点，水物资短缺是常出现的情况。在旅途中一般借助当地经验与自然信息来搜寻沙漠中的水源，对储备进行补充。沙漠中常见的水源包括地下水、蒸馏水、植物或小型绿洲。根据相关研究[21-24]，沙漠中水源地周围会出现动、植物相对密集的情况，是对水源搜索有力的经验判断依据，湿度、云层、风向等也对判断有一定参考作用。本文以小型绿洲为搜索目标，以昆虫、植被、小型动物、土壤湿度为指示元素对价值函数进行定义，上述4个指示元素对单元价值函数与方向价值函数的计算结果都有正面的影响。

　　3.2实验设计

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

　　4结束语

　　本文基于常见现实场景，提出了一种依赖经验知识辅助的目标搜索问题，并对该问题进行地图建模与算法建模，通过以正六边形为单元建立栅格地图模型，对实际搜索状态进行贴切模拟，使用基于“双禁忌表”的改良禁忌搜索算法对该问题进行解决，提出了一套完整的建模方法与算法思路。以沙漠水源搜索为实际案例，对本文的算法进行编程实验，实验结果表明，本文的方法在少于2500个单元格规模的场景中，均能够起到较好的优化效果，对现有智能辅助工具的实现有参考价值。相比于“爬山法”和单禁忌表的2种禁忌搜索方法，本文的算法可以避免多数局部最优解，并且优化搜索步数。但当问题规模超过上万个单元格时，算法在成功率上表现欠佳。本文所提出的方法属于较抽象的算法模型，泛化能力较强，但针对不同的实际问题需要具体且严谨的分析过程，存在较多开放性的应用场景，并且方法中的地图模型与算法策略仍可针对问题进行细致优化，本文为相关研究提供了一定的基础思路。

　　参考文献:

　　[1]曾辰，许瑛.一种蜂巢栅格下机器人路径规划的蚁群算法[J].机械科学与技术，2016，35(8):1308-1312.

　　[2]陶哲，高跃飞，郑天江，等.基于A*算法在蜂巢栅格地图中的路径规划研究[J].中北大学学报(自然科学版)，2020，41(4):310-317.

　　[3]朱昌龙，刘黎志.基于多边形导航网格地图的改进A*算法[J].软件导刊，2019，18(1):17-21.

　　[4]程杰，陈姚节.基于正六边形建模的无人水面艇路径规划[J].计算机技术与发展，2020，30(11):37-41.

　　[5]黄海威，邓开发.改进的A*算法在游戏地图寻路中的应用[J].信息技术，2015(4):188-191.

　　[6]葛少云，刘自发，余贻鑫.基于改进禁忌搜索的配电网重构[J].电网技术，2004，28(23):22-26.

　　作者：刁说

转载请注明来源。原文地址：http://www.xuebaoqk.com/xblw/7024.html

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

• 上一篇：大跨越脱贫建设全面小康
• 下一篇：聚丙烯熔喷非织造布对油性颗粒物的过滤性能