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

Abstract: Based on tabu search algorithm, the article proposes a novel model for the searching process in grid maps and proposes an improved tabu search algorithm that can use experience knowledge. This algorithm provides reference for the realization of intelligent auxiliary tools in the fields of guidance, water source detection, and post-disaster rescue. The article analyzes the key advantages of the tabu search algorithm, and proposes a map grid division method using regular hexagons as the grid cell to model the problem as an optimization that can be solved by the tabu search. The article takes the desert water source detection as an example to run experiments. Multiple desert elements are selected as relevant indicator parameters for water source detection. Experiments show that the proposed method performs well in a grid map with less than 10000 cells, and the rate of paths successfully planned can reach 91.7%, which is more than Hill Climbing strategy 36.68 percentage points, and the number of search steps is optimized by more than 88.4% compared with the traversal strategy.

Key words: optimization , algorithm, tabu search, grid map, regular hexagon cell, desert water source detection