一种群智感知的多任务动态多目标进化分配方法

1.本发明涉及一种群智感知多任务的动态多目标进化分配方法，具体适用于动态并发多任务的分配。


背景技术：

2.群智感知利用广大普通群众随身携带的移动智能终端作为基本感知单元，通过移动互联网形成大规模的感知网络，从而完成复杂的社会感知任务，比如城市环境质量数据收集、交通拥堵情况收集等。由于其易部署、扩展性强、成本低等优点，已成为传统无线传感网络的一种重要替代或补充方式。一个典型的群智感知系统通常由感知平台、任务发布者和移动用户三方组成。任务发布者在感知平台上发布感知任务，并给出相应的预算和质量要求等条件；感知平台将任务分解，并从所有可用移动用户中选择一组最合适的执行者，为分解后的感知任务收集感知数据。显然，如何将感知任务分配给合适的执行者，是群智感知系统的一个关键问题，显著影响感知任务的完成质量和执行成本。
3.随着越来越多的任务发布者开始收集多元群智感知信息，感知平台需要在共享的有限资源(比如：可用移动用户池、感知成本预算等)下，为多个并发的感知任务选择合适的移动用户。现有研究多聚焦于静态多任务分配问题，假设感知平台预先知道所有待分配的感知任务和可用移动用户信息。然而，在现实世界中，任务发布者发布的感知任务需求以及移动用户的可用性可能会随着时间发生变化。比如，一般情况下，城市管理者会不断地收集空气质量、噪音水平、交通拥堵情况等数据以辅助城市管理。但是，当暴雨来临时，每个区域的街道水淹程度、河流水位就需要被监测。另外，部分可用移动用户可能因故离开感知平台，而同时一些新移动用户会出现。此时，感知任务的分配方案也必须做出相应调整，以保证完成质量和执行成本。因此，有必要在有限资源限制下，对群智感知的多任务动态多目标分配问题进行研究。
4.此外，针对群智感知任务分配问题，目前已经研究了多种智能优化方法，贪心算法是一种被广泛使用的求解途径，这类方法共同特点是使用某些度量对移动用户进行排序，具有操作简单、计算速度快的优点，但同时也存在易于陷入局部最优、无法处理多目标优化问题的缺点。进化算法作为一种具有隐式并行性的全局优化方法，近年来也被研究者们尝试用来解决移动群智感知任务分配问题，从而在静态环境中帮助感知平台寻找最优分配方案。然而，现有针对静态任务分配问题设计的进化群智感知任务分配算法，存在无法帮助种群在动态环境中快速追踪最优解的问题，影响种群的收敛性能。


技术实现要素：

5.技术问题：本发明的目的是要克服现有技术中的不足之处，提供一种具有操作简单、易实现、收敛性能好的群智感知多任务动态多目标进化分配方法。
6.技术方案：本发明的一种群智感知多任务的动态多目标进化分配方法，包括以下步骤：
7.(1)按任务发布者对感知数据的时空粒度要求，将目标感知时段、目标感知区域sa分割为多个时段和一组子区域，让每个感知任务由移动用户们通过在不同时段前往各个子区域收集感知数据协作完成；
8.(2)给出移动用户执行任务的奖励计算方法，定义群智感知多任务动态多目标分配问题的优化目标、约束条件，构建群智感知多任务动态多目标分配模型；所述群智感知多任务动态多目标分配问题的优化目标：就是最大化所有感知任务的平均感知质量以及所有感知任务的平均剩余预算，所述约束条件包括每个感知任务的感知质量必须大于该感知任务对应可接受的最低质量阈值，每个移动用户在每个时段内承载的任务数量不超过该移动用户对应最大任务承载量，每个感知任务在每个子区域内被分配的移动用户满足数量要求；
9.(3)对步骤(2)中的群智感知多任务动态多目标分配模型，基于历史pareto最优解集pos
t-1
，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop；
10.(4)基于所得初始种群pop，多目标进化算法采用问题特定的进化算子生成子代种群，并综合考虑可行性和多样性更新种群位置，迭代执行生成子代种群、更新种群位置，直到满足最大迭代次数g，输出第t个时段的pareto最优解集pos
t
。
11.进一步的，所述步骤(1)具体包括：目标感知区域sa按空间粒度要求被分割为互不重叠的p个子区域，表示为sa＝{sa1,sa2,
…
,sa
p
}，满足∪isai＝sa且sai∩saj＝φ；同时，目标感知时段按时间粒度要求被划分为多个等长的时段，第t个时段有m
t
个待分配感知任务，表示为ta(t)＝{ta1,ta2,
…
,ta
mt
}，有n
t
个可用移动用户，记为u(t)＝{u1,u2,
…
,u
nt
}。
12.进一步的，所述步骤(2)具体包括：给出移动用户执行任务的奖励计算方法，定义动态群智感知任务分配问题的优化目标、约束条件。具体方法如下：
13.定义感知任务tai在子区域saj中的数据收集为子任务ta
ij
，a
ijk
为移动用户uk执行ta
ij
的奖励；综合考虑移动用户执行子任务所付出的精力成本和从当前所在位置前往目标地点的旅途成本，a
ijk
由基础奖励和旅途成本补偿共同组成：
14.a
ijk
＝bk+d
jk
×
c0ꢀꢀꢀꢀ
(1)
15.式中：bk表示基础奖励，d
jk
为用户uk执行子任务ta
ij
的旅途距离，c0则为单位旅途成本补偿；
16.(2.2)记us
ijk
为移动用户uk对子任务ta
ij
的感知能力；感知任务tai根据完成方式，归为主观感受型、基于技能型，以及设备依赖型三类，移动用户uk在子区域saj中对不同类型子任务的感知能力不同，反之则相同；
17.(2.3)记感知任务tai的感知质量为uti，则uti被定义为所有被分配给tai的移动用户感知能力平均值：
[0018][0019]
式中：p为子区域个数，也即感知任务tai在目标感知区域sa内的子任务数量，ξ为每个子任务ta
ij
所需分配的移动用户数量；当子任务ta
ij
被分配给移动用户uk时，x
ijk
＝1，否则x
ijk
＝0；
[0020]
(2.4)以最大化t时段中所有感知任务的平均感知质量以及平均剩余预算为优化目标，群智感知系统的多任务动态分配问题可被构建为如下动态多目标优化模型；
[0021][0022]
式中：m
t
表示第t个时段内的感知任务数量，b
t
表示第t个时段内的所有感知任务总预算；
[0023]
(2.5)记感知任务tai可接受的最低质量阈值为δi，则tai的感知质量uti必须大于δi，以保证感知数据的可用性：
[0024]
uti≥δi,i＝1,2,...,m
t
ꢀꢀꢀꢀ
(4)
[0025]
(2.6)记移动用户uk在t时段内的最大任务承载量为εk，则uk在t时段内被分配的所有子任务数量不能大于εk：
[0026][0027]
式中：n
t
表示第t个时段内的移动用户数量；
[0028]
(2.7)给每个子任务ta
ij
分配的移动用户数量需要达到ξ：
[0029][0030]
进一步的，所述步骤(3)具体包括：基于历史pareto最优解集，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop，具体方法如下：
[0031]
(3.1)pos
t-1
←
基于非支配准则从t-1时段的pareto最优解集中选取n/2个个体；
[0032]
(3.2)ta
′
(t)
←
基于每个感知任务可接受的最低质量阈值δi对ta(t)中所有感知任务进行降序排列；
[0033]
(3.3)对感知任务tai∈ta
′
(t)执行步骤3.4～3.11：
[0034]
(3.4)从t-1时段的任务集合ta(t-1)中识别和tai∈ta
′
(t)最相似的任务ta
l
∈ta(t-1)，其中ta
l
和tai属于同一类型且可接受的最低质量阈值之差最小；记ty
l
和tyi分别为ta
l
和tai的任务类型，则
[0035]
(3.5)对子区域saj∈sa执行步骤3.6～3.9：
[0036]
(3.6)uh←
找到历史解ys∈pos
t-1
为子任务ta
lj
雇佣的移动用户集合；
[0037]
(3.7)保留uh中在t时段内仍然可用的移动用户uk，即
[0038]
(3.8)若子任务ta
ij
没有雇佣到足够数量的移动用户，即时，执行步骤3.8.1～3.8.3：
[0039]
(3.8.1)uc←
随机从u(t)中选取num个移动用户；
[0040]
(3.8.2)计算uc中每个移动用户的效用ra
ijk
＝us
ijk
/a
ijk
；
[0041]
(3.8.3)找到uc中效用最好的移动用户uv，其中让子任务ta
ij
雇佣uv，即
[0042]
(3.9)若个体计数器s小于n/2，则s＝s+1，返回步骤3.6；否则前往步骤3.10；
[0043]
(3.10)若子区域计数器j小于p，则j＝j+1，返回步骤3.5；否则前往步骤3.11；
[0044]
(3.11)若任务计数器i小于m
t
，则i＝i+1，返回步骤3.3；否则前往步骤3.12；
[0045]
(3.12)随机初始化剩余n/2的个体；
[0046]
(3.13)输出规模为n的初始种群pop。
[0047]
进一步的，所述步骤(4)中，多目标进化算法利用问题特定的进化算子生成子代种群，并综合考虑可行性和多样性更新种群位置，迭代循环上述生成子代、更新种群位置两步骤，直到满足终止准则，输出t时段的pareto最优解集，具体方法如下：
[0048]
(4.1)采用考虑感知能力的交叉算子和考虑综合排名的变异算子依次生成n个子代个体，执行方法如下：
[0049]
(4.1.1)在考虑感知能力的交叉算子中，对于子任务ta
ij
，将两个父代个体中出现的相同用户直接保留到子代个体中；然后，从剩下的不同用户中每次随机选择两个，并将感知能力较强的保留；重复前一个步骤，直到子代个体中ta
ij
被分配的用户达到所需数量；对每个子任务执行上述操作，直到所有子任务都雇佣到足够的用户；通过上述方式生成n个子代个体，从而引导种群向感知质量较高的空间进行探索；
[0050]
(4.1.2)在考虑综合排名的变异算子中，对于子任务ta
ij
，分别按照感知能力和执行成本将移动用户进行排序；综合排名被定义为用户对ta
ij
的感知能力和执行成本名次之和；随机选择分配给子任务ta
ij
的两个用户，并将感知成本较高的那个替换为对ta
ij
综合排名第一的用户；对每个子任务以一定的概率执行上述操作，即随机生成数rand满足rand《0.5时，则对子任务执行上述变异；否则保持不变；通过上述方式生成n个子代个体，从而实现在降低种群感知成本的同时，尽可能地保证满意的感知质量；
[0051]
(4.2)更新种群位置时，首先考虑可行性选取n/2个个体，然后基于收敛性选取另外n/2个个体，共同组成下一次迭代的父代种群，执行方法如下：
[0052]
(4.2.1)将父代种群pop(g)和子代种群off(g)合并得到pop’，从中获取所有可行解并加入sc；若sc中解的数量等于n/2，则直接保留sc中所有个体；若sc中解的数量大于n/2，则基于非支配排序准则选取其中n/2个个体保留；否则，从合并种群去除sc中个体pop’＝pop’\sc，从剩余合并种群pop’中选取约束违反少的若干个体tc，由tc和sc共同组成n/2个可行性好的下一代父代种群pop(g+1)；从合并种群去除tc中个体pop’＝pop’\tc；
[0053]
(4.2.2)不考虑个体的约束违反，直接基于非支配排序准则对剩余合并种群pop’进行个体排序，并选择前n/2个个体加入下一代父代种群pop(g+1)；
[0054]
(4.3)若迭代循环计数器g小于上限次数g，则g＝g+1,返回步骤(4.1)；否则，结束程序，从pop中选取pareto最优解集并输出。
[0055]
有益效果：本发明针对传统静态群智感知多任务分配方法无法处理感知任务需求以及移动用户的可用性随时间变化的问题，构建了群智感知多任务的动态多目标分配模型，并利用具有全局搜索能力的进化算法寻找每个时段的pareto最优分配方案集合，使得分配方案能够根据当前可用资源做出相应调整，进而保证感知任务的完成质量和执行成本。另一方面，相对传统的基于进化优化的任务分配方法，利用任务相似性引导的种群初始化策略，先从历史时刻中寻找和当前任务最相似的任务，基于其雇佣的执行者生成当前任务的分配方案，极大提高了初始种群的质量，与现有技术相比，提高了种群的收敛性能，解决了无法帮助种群在动态环境中快速追踪最优解的影响种群收敛性能的问题，在本技术领域内具有广泛的实用性。
附图说明
[0056]
图1是本发明的各步骤之间的逻辑结构流程框图。
[0057]
图2是本发明设计的进化分配算法的流程图。
具体实施方式
[0058]
下面结合具体附图对本发明的实施例作进一步的描述：
[0059]
以为城市管理者提供数据服务的移动群智感知平台为例，城市管理者作为任务发布者要求感知平台在目标感知区域内按照时间粒度1小时、空间粒度1km*1km进行数据收集。城市管理者初始发布了设备依赖型任务：空气质量、噪音水平、环境温度检测，基于技能型任务：拍摄人群密度、交通拥堵情况，以及主观感受型任务：根据自身感受标记居住环境的宜居水平；每个感知任务在每个子区域内(即每个子任务)需要5个移动用户执行，各感知任务的感知质量需要达到可接受的最小质量分别为0.6、0.8、0.6、0.7、0.8、0.7；此外，当前感知平台上可用移动用户数量为800。当暴雨来临时，城市管理者取消了设备依赖型任务：空气质量、噪音水平检测，但额外增加了基于技能型任务：拍摄街道水淹程度、河流水位，对应可接受的最小质量分别为0.8、0.7；且部分可用移动用户因故离开，而一些新移动用户出现，感知平台上可用移动用户数量变为490。而暴雨离开时，城市管理者这恢复了设备依赖型任务：空气质量、噪音水平检测，并增加了主观感受型任务：标记道路损坏情况，对应可接受的最小质量为0.8；同时可用移动用户数量也变为792。城市管理者要求感知平台在每个时段中，考虑每个感知任务对应可接受的最小质量要求，从可用移动用户中选取合适执行者，从而以尽量小的感知成本收集感知质量尽量好的数据。
[0060]
图1为感知平台的多任务动态多目标进化分配方法的逻辑结构。针对上述动态多任务分配实例，感知平台首先按城市管理者对数据的时空粒度要求，将目标感知时段、目标感知区域sa分割为多个时段和一组子区域；接着，定义群智感知多任务动态多目标分配问题的优化目标、约束条件，构建群智感知多任务动态多目标分配模型；然后，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop；最后，利用多目标进化算法迭代搜索当前时段的pareto最优解集。其中，任务相似性引导的种群初始化和多目标进化算法共同构成了多目标进化分配算法，其具体流程如图2所示。首先，任务相似性引导的种群初始化策略基于t-1时段的pareto最优解集pos
t-1
，生成有潜力的初始种群pop；接着，多目标进化算法利用问题特定的考虑感知能力的交叉算子和考虑综合排名的变异算子生成子代种群off；然后，综合考虑可行性和多样性更新种群位置；最后，迭代循环上述生成子代、更新种群位置两步骤，直到满足终止准则，输出t时段的pareto最优解集。
[0061]
基于上述举例，设置了具有不同时段数量的20个动态多任务分配实例，每个时段的感知任务数量和可用移动用户的数量如表1所示。
[0062]
表1动态实例
[0063]
[0064][0065]
任务需求和移动用户相关参数设置如表2所示，每个实例在每个时段中的预算根据m
t
×
p
×
ξ
×
(max(bk)+c0)计算得到。移动用户对某个子区域中每种类型任务的感知能力通过模拟生成。在每个时段结束时，感知平台都会以小概率改变移动用户的位置。
[0066]
表2参数设置
[0067][0068]
使用本发明提出的群智感知多任务动态多目标进化分配方法求解上述20个实例的分配方案，包括以下步骤：
[0069]
步骤(1)：目标感知区域sa按空间粒度要求被分割为互不重叠的p个子区域，表示为sa＝{sa1,sa2,
…
,sa
p
}，满足∪isai＝sa且sai∩saj＝φ；同时，目标感知时段按时间粒度要求被划分为多个等长的时段，第t个时段有m
t
个待分配感知任务，表示为ta(t)＝{ta1,ta2,
…
,ta
mt
}，有n
t
个可用移动用户，记为u(t)＝{u1,u2,
…
,u
nt
}；
[0070]
步骤(2)：所述给出移动用户执行任务的奖励计算方法，定义群智感知多任务动态多目标分配问题的优化目标、约束条件，具体方法如下：
[0071]
(2.1)定义感知任务tai在子区域saj中的数据收集为子任务ta
ij
，a
ijk
为移动用户uk执行ta
ij
的奖励；综合考虑移动用户执行子任务所付出的精力成本和从当前所在位置前往目标地点的旅途成本，a
ijk
由基础奖励和旅途成本补偿共同组成：
[0072]aijk
＝bk+d
jk
×
c0ꢀꢀꢀꢀ
(1)
[0073]
式中：bk表示基础奖励，d
jk
为用户uk执行子任务ta
ij
的旅途距离，c0则为单位旅途成本补偿；
[0074]
(2.2)记us
ijk
为移动用户uk对子任务ta
ij
的感知能力；感知任务tai根据完成方式，归为主观感受型、基于技能型，以及设备依赖型三类，移动用户uk在子区域saj中对不同类型子任务的感知能力不同，反之则相同；
[0075]
(2.3)记感知任务tai的感知质量为uti，则uti被定义为所有被分配给tai的移动用户感知能力平均值：
[0076][0077]
式中：p为子区域个数，也即感知任务tai在目标感知区域sa内的子任务数量，ξ为每个子任务ta
ij
所需分配的移动用户数量；当子任务ta
ij
被分配给移动用户uk时，x
ijk
＝1，否则x
ijk
＝0；
[0078]
(2.4)以最大化t时段中所有感知任务的平均感知质量以及平均剩余预算为优化目标，群智感知系统的多任务动态分配问题可被构建为如下动态多目标优化模型；
[0079][0080]
式中：m
t
表示第t个时段内的感知任务数量，b
t
表示第t个时段内的所有感知任务总预算；
[0081]
(2.5)记感知任务tai可接受的最低质量阈值为δi，则tai的感知质量uti必须大于δi，以保证感知数据的可用性：
[0082]
uti≥δi,i＝1,2,...,m
t
ꢀꢀꢀꢀ
(4)
[0083]
(2.6)记移动用户uk在t时段内的最大任务承载量为εk，则uk在t时段内被分配的所有子任务数量不能大于εk：
[0084][0085]
式中：n
t
表示第t个时段内的移动用户数量；
[0086]
(2.7)给每个子任务ta
ij
分配的移动用户数量需要达到ξ：
[0087][0088]
步骤(3)：基于历史pareto最优解集，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop，具体方法如下：：
[0089]
(3.1)pos
t-1
←
基于非支配准则从t-1时段的pareto最优解集中选取n/2个个体；
[0090]
(3.2)ta
′
(t)
←
基于每个感知任务可接受的最低质量阈值δi对ta(t)中所有感知任务进行降序排列；
[0091]
(3.3)对感知任务tai∈ta
′
(t)执行步骤3.4～3.11：
[0092]
(3.4)从t-1时段的任务集合ta(t-1)中识别和tai∈ta
′
(t)最相似的任务ta
l
∈ta(t-1)，其中ta
l
和tai属于同一类型且可接受的最低质量阈值之差最小；记ty
l
和tyi分别为ta
l
和tai的任务类型，则
[0093]
(3.5)对子区域saj∈sa执行步骤3.6～3.9：
[0094]
(3.6)uh←
找到历史解ys∈pos
t-1
为子任务ta
lj
雇佣的移动用户集合；
[0095]
(3.7)保留uh中在t时段内仍然可用的移动用户uk，即
[0096]
(3.8)若子任务ta
ij
没有雇佣到足够数量的移动用户，即时，执行步骤
3.8.1～3.8.3：
[0097]
(3.8.1)uc←
随机从u(t)中选取num个移动用户；
[0098]
(3.8.2)计算uc中每个移动用户的效用ra
ijk
＝us
ijk
/a
ijk
；
[0099]
(3.8.3)找到uc中效用最好的移动用户uv，其中让子任务ta
ij
雇佣uv，即
[0100]
(3.9)若个体计数器s小于n/2，则s＝s+1，返回步骤3.6；否则前往步骤3.10；
[0101]
(3.10)若子区域计数器j小于p，则j＝j+1，返回步骤3.5；否则前往步骤3.11；
[0102]
(3.11)若任务计数器i小于m
t
，则i＝i+1，返回步骤3.3；否则前往步骤3.12；
[0103]
(3.12)随机初始化剩余n/2的个体；
[0104]
(3.13)输出规模为n的初始种群pop。
[0105]
步骤(4)：多目标进化算法利用问题特定的进化算子生成子代种群，并综合考虑可行性和多样性更新种群位置，迭代循环上述生成子代、更新种群位置两步骤，直到满足终止准则，输出t时段的pareto最优解集，详细说明如下：
[0106]
(4.1)采用考虑感知能力的交叉算子和考虑综合排名的变异算子依次生成n个子代个体，执行方法如下：
[0107]
(4.1.1)在考虑感知能力的交叉算子中，对于子任务ta
ij
，将两个父代个体中出现的相同用户直接保留到子代个体中；然后，从剩下的不同用户中每次随机选择两个，并将感知能力较强的保留；重复前一个步骤，直到子代个体中ta
ij
被分配的用户达到所需数量；对每个子任务执行上述操作，直到所有子任务都雇佣到足够的用户；通过上述方式生成n个子代个体，从而引导种群向感知质量较高的空间进行探索；
[0108]
(4.1.2)在考虑综合排名的变异算子中，对于子任务ta
ij
，分别按照感知能力和执行成本将移动用户进行排序；综合排名被定义为用户对ta
ij
的感知能力和执行成本名次之和；随机选择分配给子任务ta
ij
的两个用户，并将感知成本较高的那个替换为对ta
ij
综合排名第一的用户；对每个子任务以一定的概率执行上述操作，即随机生成数rand满足rand《0.5时，则对子任务执行上述变异；否则保持不变；通过上述方式生成n个子代个体，从而实现在降低种群感知成本的同时，尽可能地保证满意的感知质量；
[0109]
(4.2)更新种群位置时，首先考虑可行性选取n/2个个体，然后基于收敛性选取另外n/2个个体，共同组成下一次迭代的父代种群，执行方法如下：
[0110]
(4.2.1)将父代种群pop(g)和子代种群off(g)合并得到pop’，从中获取所有可行解并加入sc；若sc中解的数量等于n/2，则直接保留sc中所有个体；若sc中解的数量大于n/2，则基于非支配排序准则选取其中n/2个个体保留；否则，从合并种群去除sc中个体pop’＝pop’\sc，从剩余合并种群pop’中选取约束违反少的若干个体tc，由tc和sc共同组成n/2个可行性好的下一代父代种群pop(g+1)；从合并种群去除tc中个体pop’＝pop’\tc；
[0111]
(4.2.2)不考虑个体的约束违反，直接基于非支配排序准则对剩余合并种群pop’进行个体排序，并选择前n/2个个体加入下一代父代种群pop(g+1)；
[0112]
(4.3)若迭代循环计数器g小于上限次数g，则g＝g+1,返回步骤(4.1)；否则，结束程序，从pop中选取pareto最优解集并输出。
[0113]
本发明的效果通过以下仿真实验说明：
[0114]
实验内容
[0115]
针对表1所示的20个动态多任务分配实例，在表2中的参数设置下，采用所提进化算法和传统多目标进化算法分别对问题进行求解。其中，两种算法的种群规模均设置为20，迭代次数为100。
[0116]
实验结果
[0117]
将两种方法在20个动态多任务分配实例中分别运行30次，并记录每个实例中所有时段的pareto最优解集的hv平均值。由表3可以看出，本发明所提方法在20个动态实例中的17个上获得了更高的hv平均值，而且所有实例的hv平均值是高于传统进化算法的。显然，所提方法相比传统进化算法能够找到多样性和收敛性相对更好的pareto最优解集，即可以给感知平台提供感知质量更好或执行成本更低的分配方案。
[0118]
表3两种算法在20个动态多任务分配实例中所有时段获得的pareto最优解集的hv平均值
[0119][0120]
虽然，上文中已经用一般性说明及具体实施例对本发明作了详尽的描述，但在本发明基础上，可以对之作一些修改或改进，这对本领域技术人员而言是显而易见的。因此，在不偏离本发明精神的基础上所做的这些修改或改进，均属于本发明要求保护的范围。

技术特征：
1.一种群智感知多任务的动态多目标进化分配方法，其特征在于，包括以下步骤：(1)按任务发布者对感知数据的时空粒度要求，将目标感知时段、目标感知区域sa分割为多个时段和一组子区域，让每个感知任务由移动用户们通过在不同时段前往各个子区域收集感知数据协作完成；(2)给出移动用户执行任务的奖励计算方法，定义群智感知多任务动态多目标分配问题的优化目标、约束条件，构建群智感知多任务动态多目标分配模型；所述群智感知多任务动态多目标分配问题的优化目标：就是最大化所有感知任务的平均感知质量以及所有感知任务的平均剩余预算，所述约束条件包括每个感知任务的感知质量必须大于该感知任务对应可接受的最低质量阈值，每个移动用户在每个时段内承载的任务数量不超过该移动用户对应最大任务承载量，每个感知任务在每个子区域内被分配的移动用户满足数量要求；(3)对步骤(2)中的群智感知多任务动态多目标分配模型，基于历史pareto最优解集pos
t-1
，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop；(4)基于所得初始种群pop，多目标进化算法采用问题特定的进化算子生成子代种群，并综合考虑可行性和多样性更新种群位置，迭代执行生成子代种群、更新种群位置，直到满足最大迭代次数g，输出第t个时段的pareto最优解集pos
t
。2.根据权利要求1所述的一种群智感知多任务的动态多目标进化分配方法，其特征在于：步骤(1)中：所述目标感知区域sa按空间粒度要求被分割为互不重叠的p个子区域，表示为sa＝{sa1,sa2,
…
,sa
p
}，满足∪
i
sa
i
＝sa且sa
i
∩sa
j
＝φ；同时，目标感知时段按时间粒度要求被划分为多个等长的时段，第t个时段有m
t
个待分配感知任务，表示为ta(t)＝{ta1,ta2,
…
,ta
mt
}，有n
t
个可用移动用户，记为u(t)＝{u1,u2,
…
,u
nt
}。3.根据权利要求1所述的一种群智感知多任务的动态多目标进化分配方法，其特征在于：步骤(2)中，所述给出移动用户执行任务的奖励计算方法，定义群智感知多任务动态多目标分配问题的优化目标、约束条件，具体方法如下：(2.1)定义感知任务ta
i
在子区域sa
j
中的数据收集为子任务ta
ij
，a
ijk
为移动用户u
k
执行ta
ij
的奖励；综合考虑移动用户执行子任务所付出的精力成本和从当前所在位置前往目标地点的旅途成本，a
ijk
由基础奖励和旅途成本补偿共同组成：a
ijk
＝b
k
+d
jk
×
c0ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)式中：b
k
表示基础奖励，d
jk
为用户u
k
执行子任务ta
ij
的旅途距离，c0则为单位旅途成本补偿；(2.2)记us
ijk
为移动用户u
k
对子任务ta
ij
的感知能力；感知任务ta
i
根据完成方式，归为主观感受型、基于技能型，以及设备依赖型三类，移动用户u
k
在子区域sa
j
中对不同类型子任务的感知能力不同，反之则相同；(2.3)记感知任务ta
i
的感知质量为ut
i
，则ut
i
被定义为所有被分配给ta
i
的移动用户感知能力平均值：式中：p为子区域个数，即感知任务ta
i
在目标感知区域sa内的子任务数量，ξ为每个子任务ta
ij
所需分配的移动用户数量；当子任务ta
ij
被分配给移动用户u
k
时，x
ijk
＝1，否则x
ijk
＝0；
(2.4)以最大化t时段中所有感知任务的平均感知质量以及平均剩余预算为优化目标，群智感知系统的多任务动态分配问题可被构建为如下动态多目标优化模型；式中：m
t
表示第t个时段内的感知任务数量，b
t
表示第t个时段内的所有感知任务总预算；(2.5)记感知任务ta
i
可接受的最低质量阈值为δ
i
，则ta
i
的感知质量ut
i
必须大于δ
i
，以保证感知数据的可用性：ut
i
≥δ
i
,i＝1,2,...,m
t
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)(2.6)记移动用户u
k
在t时段内的最大任务承载量为ε
k
，则u
k
在t时段内被分配的所有子任务数量不能大于ε
k
：式中：n
t
表示第t个时段内的移动用户数量；(2.7)给每个子任务ta
ij
分配的移动用户数量需要达到ξ：4.根据权利要求1所述的一种群智感知多任务的动态多目标进化分配方法，其特征在于：步骤(3)中，基于历史pareto最优解集pos
t-1
，执行任务相似性引导的种群初始化策略，生成有潜力的初始种群pop的具体方法如下：(3.1)ta
′
(t)
←
基于每个感知任务可接受的最低质量阈值δ
i
对ta(t)中所有感知任务进行降序排列；(3.2)pop＝φ，设置感知任务计数器i＝1，子区域计数器j＝1；(3.3)对感知任务ta
i
∈ta
′
(t)执行步骤3.4～3.10：(3.4)从t-1时段的任务集合ta(t-1)中识别和ta
i
∈ta
′
(t)最相似的任务ta
l
∈ta(t-1)，其中ta
l
和ta
i
属于同一类型且可接受的最低质量阈值之差最小；记ty
l
和ty
i
分别为ta
l
和ta
i
的任务类型，则(3.5)对子区域sa
j
∈sa执行步骤3.6～3.9：(3.6)u
h
←
找到历史解y∈pos
t-1
中为子任务ta
lj
雇佣的移动用户集合；(3.7)保留u
h
中在t时段内仍然可用的移动用户u
k
，即x
ijk
＝1,ifu
k
∈u(t),u
k
∈u
h
；(3.8)若子任务ta
ij
没有雇佣到足够数量的移动用户，即∑x
ijk
＜ξ时，执行步骤3.8.1～3.8.3：(3.8.1)u
c
←
随机从u(t)中选取num个移动用户；(3.8.2)计算u
c
中每个移动用户的效用ra
ijk
＝us
ijk
/a
ijk
；(3.8.3)找到u
c
中效用最好的移动用户u
v
，其中
让子任务ta
ij
雇佣u
v
，即x
ijv
＝1；(3.9)当子区域计数器j小于子区域个数p时，则j＝j+1，返回步骤3.5；否则前往步骤3.10；(3.10)当感知任务计数器i小于感知任务数量m
t
时，则i＝i+1，返回步骤3.3；否则pop＝pop∪x；(3.11)重复步骤3.1～3.10生成n/2个个体，并和随机生成的n/2个个体，共同组成规模为n的初始种群pop。5.根据权利要求1所述的一种群智感知多任务的动态多目标进化分配方法，其特征在于：步骤(4)中，所述多目标进化算法利用问题特定的进化算子生成子代种群，并综合考虑可行性和多样性更新种群位置，迭代执行生成子代、更新种群位置，直到满足最大迭代次数g，输出第t个时段的pareto最优解集pos
t
，具体方法如下：(4.1)基于父代种群pop利用考虑感知能力的交叉算子生成子代种群off，引导种群向感知质量较高的空间进行探索，执行方法如4.1.1～4.1.6：(4.1.1)从pop中任选两个父代个体，执行步骤4.1.1～4.1.5：(4.1.2)对于子任务ta
ij
，将两个父代个体中出现的相同移动用户直接保留到子代个体中；(4.1.3)从剩余的不同移动用户中随机选择两个，并将感知能力较强的保留到子代个体中；(4.1.4)当子任务ta
ij
没有雇佣到足够数量的移动用户时，返回步骤4.1.3，否则前往步骤4.1.5；(4.1.5)对每个子任务执行步骤4.1.2～4.1.4，获得一个子代个体；(4.1.6)重复步骤4.1.1～4.1.5生成n个子代个体，共同组成子代种群off；(4.2)对子代种群off执行考虑综合排名的变异算子，从而实现在降低种群感知成本的同时，保证满意的感知质量，执行方法如4.2.1～4.2.5：(4.2.1)对off中的每个父代个体，执行步骤4.2.2～4.2.7：(4.2.2)对于子任务ta
ij
，当随机生成数rand满足rand<0.5时，则执行步骤4.2.2～4.2.5：(4.2.3)按照移动用户的感知能力由强到弱对其进行排序，获得各移动用户的感知能力名次；(4.2.4)按照移动用户的执行成本由少到多对其进行排序，获得各移动用户的执行成本名次；(4.2.5)定义综合排名为移动用户对ta
ij
的感知能力和执行成本名次之和，基于此计算每个移动用户的综合排名；(4.2.6)随机选择分配给子任务ta
ij
的两个移动用户，并将其中感知成本较高的替换为对ta
ij
综合排名第一的移动用户；(4.2.7)对每个子任务执行步骤4.2.2～4.2.6；(4.3)综合考虑可行性和多样性更新种群位置，执行方法如4.3.1～4.3.4：(4.3.1)将父代种群pop和子代种群off合并得到pop’；
(4.3.2)基于deb可行性准则对pop’中个体进行排序，选取前n/2个个体组成临时种群pop1，并从pop’移除pop1中所有个体；(4.3.3)不考虑个体的约束违反，基于非支配排序准则对pop’中个体进行排序，选取前n/2个个体组成临时种群pop2；(4.3.4)合并pop1和pop2得到下一次迭代的父代种群pop，即pop＝pop1∪pop2；(4.4)迭代执行步骤4.1～4.3，直到满足最大迭代次数g，则输出pop；(4.5)从pop中选取可行非支配解集，组成第t个时段的pareto最优解集pos
t
。

技术总结
本发明公开了一种群智感知多任务的动态多目标进化分配方法，步骤如下：(1)收集任务发布者对感知数据的时空粒度要求，对目标感知时间段、区域进行分割；(2)考虑感知任务需求和移动用户可用性的时变特性、资源约束限制，以每个时段中所有感知任务的平均感知质量和平均剩余预算最大化为优化目标，构建群智感知多任务动态多目标分配模型；(3)执行任务相似性引导的种群初始化策略，生成有潜力的初始种群；(4)基于多目标进化算法迭代搜索感知质量好、执行成本低的Pareto最优解集；本发明通过提高进化算法初始种群的质量，显著加强了种群的收敛性能；提供更多的感知任务完成质量高、执行成本低的分配方案供感知平台选择。成本低的分配方案供感知平台选择。成本低的分配方案供感知平台选择。


技术研发人员：吉建娇 郭一楠 杨潇 陈国玉
受保护的技术使用者：中国矿业大学
技术研发日：2023.05.08
技术公布日：2023/8/6