NEH启发式算法+Tabu搜索算法

该算法来源于文章2019-IEEE Access-Evolutionary Planning of Multi-UAV Search for Missing Tourists

假设已经为无人机

随机分配了一个子区域的集合

作为其搜索路径

其中

→无人机

将要搜索的子区域序列

→无人机

搜索子区域

时所用的搜索模式

路径

的适应度可以通过总探测概率与消耗的总搜索时间之比来进行评估：

其中

表示无人机

开始在其搜索路径上的第i个子区域进行搜索的时间，可被计算为：

→飞行时间

→搜索时间 

具体步骤如Algorithm 1所示，先通过NEH启发式算法构建无人机的初始搜索路径，然后通过紧急搜索算法迭代地改进初始路径。

1. NEH启发式算法

1) 将

中的子区域按目标定位概率与到无人机

的距离之比递减排序

N：计算目标定位概率，目标到无人机之间的距离

2) 构建

中前两个子区域的局部调度

，使当前适应度最大

N：初始路径，路径的适应度计算

3) 

4) while循环→条件

        在

个可能的子区域中，将第

个子区域插入路径

，使当前的适应度最大化

2. Tabu搜索算法 

Tabu迭代地将当前解移动到没有被禁忌表禁止的最佳领域解，其中的领域解是通过在搜索路径

中交换两个相邻的子区域来获得的。

此外通过将被交换子区域的搜索模式

更改为

，再在每个领域解上进行一次局部搜索

禁忌搜索操作的最大次数

被设置为

，禁忌长度

被设置为6

1) 初始化一个空的禁忌表

2) 

=

3) while循环→条件

→条件

                                                      →

是通过交换

的第

个子区域和第

个子区域得到的邻域

赋值给

        将

添加到禁忌表

中

        如果

→讲第一个元素从

中移除

        如果

→

赋值给

算法最终的结果是返回一个新的搜索路径

个人学习笔记，后续可能会对这部分代码进行复现