試論雙種群協同目標搜索

何凱迪

四川大學電子信息學院 四川 成都 610065

引言

智能體集群有著廣泛的運用，如測繪、監視或周邊巡邏[1-4]。在目標搜索領域中，啟發式搜索算法有著廣泛的運用。其中比較廣泛的運用就是以Voronoi圖劃分為基礎的搜索算法。

1 問題背景和建模

本文針對靜態目標搜索領域。目標是多個不可移動的目標。

地圖使用建立在離散地圖上的概率圖建模，地圖被離散柵格化。每個柵格區域對應一塊地圖，對于每個柵格區域建立了一個數字，例如概率值，用來輔助搜索的進行。

高概率區域，用來指引無人機優先搜索，低概率區域指引無人機低優先級搜索。

對于無人機，沒有移動模型限制，無人機可以移動到地圖任意位置，不局限于柵格中心。

每次探測區域是否會被探測，取決于柵格中心是否位于智能體探測范圍內。

對于離散地圖，可以使用矩陣存儲。

2 雙種群算法

雙種群算法主要包含了兩個種群。

第一種群，仍然以Voronoi圖劃分為基礎進行區域搜索。

即，進行Voronoi圖劃分后，質心計算公式使用：

在通過Voronoi圖劃分之后，計算每個Voronoi圖區域的質心，作為無人機的引導位置。

第一種群搜索完畢之后，進行地圖更新。地圖更新主要使用貝葉斯更新公式為基礎的延伸公式：

其中Pi,j,k是區域j在第k次迭代時的第i個智能體搜索結果的概率，Di,j,k代表著第k次迭代時的對該區域的探測結果，Di,j,k=1表示探測到了目標，Di,j,k=0表示沒有探測到目標。

此外，p是探測概率，是智能體攜帶傳感器精度決定。q是誤報的概率，表示識別錯誤，也是由智能體攜帶傳感器決定。

在第一種群搜索的過程中，維護最優集合，也就是適應度值最高的集合。然后將最優集合和檔案集一并通信給第二種群。第二種群個體根據最近位置執行搜索。

3 實驗

實驗設置參數如下：

表1 實驗環境參數

在衡量指標上，使用：

來衡量，也就是柵格區域的平均概率值。

實驗效果如下：

圖1 實驗效果指標對比

圖1中，藍色線是雙種群算法，紅色線是Voronoi圖基礎搜索算法。

從圖中可以看出雙種群算法，對于地圖的搜索效率顯著高于Voronoi圖基礎搜索算法。并且在一定迭代次數之后，Voronoi圖基礎算法陷入卡死，智能體集群陷入原地時候，雙種群算法仍然能夠實現搜索。

4 結束語

在智能體集群控制算法上仍然有發展的巨大前景，除了考慮近些年比較前沿的多種群算法之外，也可以考慮引入多目標優化算法，或者以機器學習算法為基礎的新方法都是本領域的前進方向。