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循環→條件

→條件

                                                      →

是通過交換

的第

個子區域和第

個子區域得到的鄰域

指派給

        将

添加到禁忌表

中

        如果

→講第一個元素從

中移除

        如果

→

指派給

算法最終的結果是傳回一個新的搜尋路徑

個人學習筆記，後續可能會對這部分代碼進行複現