[發(fā)明專利]一種群智感知的多任務(wù)動(dòng)態(tài)多目標(biāo)進(jìn)化分配方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202310509245.6
• 申請(qǐng)日: 2023-05-08
• 公開（公告）號(hào): CN116541148A
• 公開（公告）日: 2023-08-04
• 發(fā)明（設(shè)計(jì)）人: 吉建嬌;郭一楠;楊瀟;陳國玉
• 申請(qǐng)（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06N3/006
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 張聯(lián)群

本發(fā)明公開了一種群智感知多任務(wù)的動(dòng)態(tài)多目標(biāo)進(jìn)化分配方法，步驟如下：(1)收集任務(wù)發(fā)布者對(duì)感知數(shù)據(jù)的時(shí)空粒度要求，對(duì)目標(biāo)感知時(shí)間段、區(qū)域進(jìn)行分割；(2)考慮感知任務(wù)需求和移動(dòng)用戶可用性的時(shí)變特性、資源約束限制，以每個(gè)時(shí)段中所有感知任務(wù)的平均感知質(zhì)量和平均剩余預(yù)算最大化為優(yōu)化目標(biāo)，構(gòu)建群智感知多任務(wù)動(dòng)態(tài)多目標(biāo)分配模型；(3)執(zhí)行任務(wù)相似性引導(dǎo)的種群初始化策略，生成有潛力的初始種群；(4)基于多目標(biāo)進(jìn)化算法迭代搜索感知質(zhì)量好、執(zhí)行成本低的Pareto最優(yōu)解集；本發(fā)明通過提高進(jìn)化算法初始種群的質(zhì)量，顯著加強(qiáng)了種群的收斂性能；提供更多的感知任務(wù)完成質(zhì)量高、執(zhí)行成本低的分配方案供感知平臺(tái)選擇。

技術(shù)領(lǐng)域

本發(fā)明涉及一種群智感知多任務(wù)的動(dòng)態(tài)多目標(biāo)進(jìn)化分配方法，具體適用于動(dòng)態(tài)并發(fā)多任務(wù)的分配。

背景技術(shù)

群智感知利用廣大普通群眾隨身攜帶的移動(dòng)智能終端作為基本感知單元，通過移動(dòng)互聯(lián)網(wǎng)形成大規(guī)模的感知網(wǎng)絡(luò)，從而完成復(fù)雜的社會(huì)感知任務(wù)，比如城市環(huán)境質(zhì)量數(shù)據(jù)收集、交通擁堵情況收集等。由于其易部署、擴(kuò)展性強(qiáng)、成本低等優(yōu)點(diǎn)，已成為傳統(tǒng)無線傳感網(wǎng)絡(luò)的一種重要替代或補(bǔ)充方式。一個(gè)典型的群智感知系統(tǒng)通常由感知平臺(tái)、任務(wù)發(fā)布者和移動(dòng)用戶三方組成。任務(wù)發(fā)布者在感知平臺(tái)上發(fā)布感知任務(wù)，并給出相應(yīng)的預(yù)算和質(zhì)量要求等條件；感知平臺(tái)將任務(wù)分解，并從所有可用移動(dòng)用戶中選擇一組最合適的執(zhí)行者，為分解后的感知任務(wù)收集感知數(shù)據(jù)。顯然，如何將感知任務(wù)分配給合適的執(zhí)行者，是群智感知系統(tǒng)的一個(gè)關(guān)鍵問題，顯著影響感知任務(wù)的完成質(zhì)量和執(zhí)行成本。

隨著越來越多的任務(wù)發(fā)布者開始收集多元群智感知信息，感知平臺(tái)需要在共享的有限資源(比如：可用移動(dòng)用戶池、感知成本預(yù)算等)下，為多個(gè)并發(fā)的感知任務(wù)選擇合適的移動(dòng)用戶。現(xiàn)有研究多聚焦于靜態(tài)多任務(wù)分配問題，假設(shè)感知平臺(tái)預(yù)先知道所有待分配的感知任務(wù)和可用移動(dòng)用戶信息。然而，在現(xiàn)實(shí)世界中，任務(wù)發(fā)布者發(fā)布的感知任務(wù)需求以及移動(dòng)用戶的可用性可能會(huì)隨著時(shí)間發(fā)生變化。比如，一般情況下，城市管理者會(huì)不斷地收集空氣質(zhì)量、噪音水平、交通擁堵情況等數(shù)據(jù)以輔助城市管理。但是，當(dāng)暴雨來臨時(shí)，每個(gè)區(qū)域的街道水淹程度、河流水位就需要被監(jiān)測(cè)。另外，部分可用移動(dòng)用戶可能因故離開感知平臺(tái)，而同時(shí)一些新移動(dòng)用戶會(huì)出現(xiàn)。此時(shí)，感知任務(wù)的分配方案也必須做出相應(yīng)調(diào)整，以保證完成質(zhì)量和執(zhí)行成本。因此，有必要在有限資源限制下，對(duì)群智感知的多任務(wù)動(dòng)態(tài)多目標(biāo)分配問題進(jìn)行研究。

此外，針對(duì)群智感知任務(wù)分配問題，目前已經(jīng)研究了多種智能優(yōu)化方法，貪心算法是一種被廣泛使用的求解途徑，這類方法共同特點(diǎn)是使用某些度量對(duì)移動(dòng)用戶進(jìn)行排序，具有操作簡(jiǎn)單、計(jì)算速度快的優(yōu)點(diǎn)，但同時(shí)也存在易于陷入局部最優(yōu)、無法處理多目標(biāo)優(yōu)化問題的缺點(diǎn)。進(jìn)化算法作為一種具有隱式并行性的全局優(yōu)化方法，近年來也被研究者們嘗試用來解決移動(dòng)群智感知任務(wù)分配問題，從而在靜態(tài)環(huán)境中幫助感知平臺(tái)尋找最優(yōu)分配方案。然而，現(xiàn)有針對(duì)靜態(tài)任務(wù)分配問題設(shè)計(jì)的進(jìn)化群智感知任務(wù)分配算法，存在無法幫助種群在動(dòng)態(tài)環(huán)境中快速追蹤最優(yōu)解的問題，影響種群的收斂性能。

發(fā)明內(nèi)容

技術(shù)問題：本發(fā)明的目的是要克服現(xiàn)有技術(shù)中的不足之處，提供一種具有操作簡(jiǎn)單、易實(shí)現(xiàn)、收斂性能好的群智感知多任務(wù)動(dòng)態(tài)多目標(biāo)進(jìn)化分配方法。

技術(shù)方案：本發(fā)明的一種群智感知多任務(wù)的動(dòng)態(tài)多目標(biāo)進(jìn)化分配方法，包括以下步驟：

(1)按任務(wù)發(fā)布者對(duì)感知數(shù)據(jù)的時(shí)空粒度要求，將目標(biāo)感知時(shí)段、目標(biāo)感知區(qū)域Sa分割為多個(gè)時(shí)段和一組子區(qū)域，讓每個(gè)感知任務(wù)由移動(dòng)用戶們通過在不同時(shí)段前往各個(gè)子區(qū)域收集感知數(shù)據(jù)協(xié)作完成；

(2)給出移動(dòng)用戶執(zhí)行任務(wù)的獎(jiǎng)勵(lì)計(jì)算方法，定義群智感知多任務(wù)動(dòng)態(tài)多目標(biāo)分配問題的優(yōu)化目標(biāo)、約束條件，構(gòu)建群智感知多任務(wù)動(dòng)態(tài)多目標(biāo)分配模型；所述群智感知多任務(wù)動(dòng)態(tài)多目標(biāo)分配問題的優(yōu)化目標(biāo)：就是最大化所有感知任務(wù)的平均感知質(zhì)量以及所有感知任務(wù)的平均剩余預(yù)算，所述約束條件包括每個(gè)感知任務(wù)的感知質(zhì)量必須大于該感知任務(wù)對(duì)應(yīng)可接受的最低質(zhì)量閾值，每個(gè)移動(dòng)用戶在每個(gè)時(shí)段內(nèi)承載的任務(wù)數(shù)量不超過該移動(dòng)用戶對(duì)應(yīng)最大任務(wù)承載量，每個(gè)感知任務(wù)在每個(gè)子區(qū)域內(nèi)被分配的移動(dòng)用戶滿足數(shù)量要求；