試論雙種群協(xié)同目標(biāo)搜索

何凱迪

四川大學(xué)電子信息學(xué)院 四川 成都 610065

引言

智能體集群有著廣泛的運(yùn)用，如測(cè)繪、監(jiān)視或周邊巡邏[1-4]。在目標(biāo)搜索領(lǐng)域中，啟發(fā)式搜索算法有著廣泛的運(yùn)用。其中比較廣泛的運(yùn)用就是以Voronoi圖劃分為基礎(chǔ)的搜索算法。

1 問(wèn)題背景和建模

本文針對(duì)靜態(tài)目標(biāo)搜索領(lǐng)域。目標(biāo)是多個(gè)不可移動(dòng)的目標(biāo)。

地圖使用建立在離散地圖上的概率圖建模，地圖被離散柵格化。每個(gè)柵格區(qū)域?qū)?yīng)一塊地圖，對(duì)于每個(gè)柵格區(qū)域建立了一個(gè)數(shù)字，例如概率值，用來(lái)輔助搜索的進(jìn)行。

高概率區(qū)域，用來(lái)指引無(wú)人機(jī)優(yōu)先搜索，低概率區(qū)域指引無(wú)人機(jī)低優(yōu)先級(jí)搜索。

對(duì)于無(wú)人機(jī)，沒(méi)有移動(dòng)模型限制，無(wú)人機(jī)可以移動(dòng)到地圖任意位置，不局限于柵格中心。

每次探測(cè)區(qū)域是否會(huì)被探測(cè)，取決于柵格中心是否位于智能體探測(cè)范圍內(nèi)。

對(duì)于離散地圖，可以使用矩陣存儲(chǔ)。

2 雙種群算法

雙種群算法主要包含了兩個(gè)種群。

第一種群，仍然以Voronoi圖劃分為基礎(chǔ)進(jìn)行區(qū)域搜索。

即，進(jìn)行Voronoi圖劃分后，質(zhì)心計(jì)算公式使用：

在通過(guò)Voronoi圖劃分之后，計(jì)算每個(gè)Voronoi圖區(qū)域的質(zhì)心，作為無(wú)人機(jī)的引導(dǎo)位置。

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

其中Pi,j,k是區(qū)域j在第k次迭代時(shí)的第i個(gè)智能體搜索結(jié)果的概率，Di,j,k代表著第k次迭代時(shí)的對(duì)該區(qū)域的探測(cè)結(jié)果，Di,j,k=1表示探測(cè)到了目標(biāo)，Di,j,k=0表示沒(méi)有探測(cè)到目標(biāo)。

此外，p是探測(cè)概率，是智能體攜帶傳感器精度決定。q是誤報(bào)的概率，表示識(shí)別錯(cuò)誤，也是由智能體攜帶傳感器決定。

在第一種群搜索的過(guò)程中，維護(hù)最優(yōu)集合，也就是適應(yīng)度值最高的集合。然后將最優(yōu)集合和檔案集一并通信給第二種群。第二種群個(gè)體根據(jù)最近位置執(zhí)行搜索。

3 實(shí)驗(yàn)

實(shí)驗(yàn)設(shè)置參數(shù)如下：

表1 實(shí)驗(yàn)環(huán)境參數(shù)

在衡量指標(biāo)上，使用：

來(lái)衡量，也就是柵格區(qū)域的平均概率值。

實(shí)驗(yàn)效果如下：

圖1 實(shí)驗(yàn)效果指標(biāo)對(duì)比

圖1中，藍(lán)色線是雙種群算法，紅色線是Voronoi圖基礎(chǔ)搜索算法。

從圖中可以看出雙種群算法，對(duì)于地圖的搜索效率顯著高于Voronoi圖基礎(chǔ)搜索算法。并且在一定迭代次數(shù)之后，Voronoi圖基礎(chǔ)算法陷入卡死，智能體集群陷入原地時(shí)候，雙種群算法仍然能夠?qū)崿F(xiàn)搜索。

4 結(jié)束語(yǔ)

在智能體集群控制算法上仍然有發(fā)展的巨大前景，除了考慮近些年比較前沿的多種群算法之外，也可以考慮引入多目標(biāo)優(yōu)化算法，或者以機(jī)器學(xué)習(xí)算法為基礎(chǔ)的新方法都是本領(lǐng)域的前進(jìn)方向。