本发明涉及一种基于分解的异构群智感知任务多目标进化分配方法，适用于同时考虑感知质量和经济性的由不同类型移动用户组成的异构群智感知系统的任务分配，属于无线传感网络。
背景技术：
1、传统无线传感网络通过在若干目标地点部署成本高昂的专业监测设备，实现环境数据的监测。然而，固定在特定位置的监测设备只能覆盖有限范围，一旦感知区域发生变化，现有感知网络就无法满足监测要求。随着集成了众多传感器的移动智能终端爆炸式普及，移动群智感知成为一种新型感知范式，它利用手持移动智能终端的移动用户作为基本感知单元，通过移动互联网随时随地形成感知网络完成环境信息收集。相比于传统感知模式，移动群智感知网络具有部署方便、维护成本低、扩展性强等优点。
2、在移动群智感知系统中，从大量具有不同感知能力和奖励成本的移动用户中选取合适的任务执行者，是影响感知任务完成质量和成本的关键。显然，合适的群智感知任务分配方法是移动群智感知系统被广泛应用的前提。然而，现有研究主要针对由仅有普通人员组成的群智感知系统任务分配问题，而这类人员无法到达高速公路、湖泊等区域，进而导致这些区域的监测数据缺失。考虑到无人机可以作为补充感知单元，前往人员步行难以到达的区域收集数据，有必要针对由人员和无人机共同组成的异构群智感知系统，考虑感知任务的完成质量和成本，开展其任务多目标分配方法研究。
3、对于多目标优化问题，分解是一种简单而有效的方法。它将多目标优化问题分解成多个单目标子问题。基于此，可以将遗传算法用于求解每个子问题的最优分配方案，然后通过合并所有子问题的最优分配方案就可以得到原多目标问题的pareto分配方案集合。此外，考虑到随机配置网络是学习移动用户特征，进而给出移动用户分配概率的一种有利方法，可以利用训练好的随机配置网络提供的移动用户分配概率来生成多样化且有潜力的初始种群。相比于随机生成的初始种群，基于随机配置网络生成的初始种群显然能够加快收敛速度、增强收敛性能，帮助找到更优秀的分配方案。
技术实现思路
1、技术问题：本发明的目的是要克服现有技术的不足，提供一种易实现、搜索效率高、收敛性能好，能够更好更快捷对目标区域的环境信息进行收集的异构群智感知任务多目标进化分配方法。
2、技术方案：本发明提供的一种基于分解的异构群智感知任务多目标进化分配方法，使用异构群智感知系统对目标感知区域进行感知数据收集，异构群智感知系统的基本感知单元为移动用户，包括多个无人机和手持终端设备的人员，其中无人机可以到达人员无法抵达的地理位置；
3、包括以下步骤：
4、(1)将基础单元需要抵达的目标感知区域构建为异构群智感知图，将异构群智感知图进行网格划分，并根据其实际情况对划分的网格进行标注，包括禁飞网格区域、人员不可达网格区域、普遍可达网格区域；感知系统根据各感知网格区域的标注类型，将位于不同感知网格区域的感知任务分配给合适的移动用户去完成；
5、(2)综合考虑感知任务的完成质量和经济性、相关资源约束限制、最大化所有感知任务的平均感知质量、平均剩余执行成本为优化目标，以移动用户对感知区域的可达性、感知任务执行成本不得超出预算，每个移动用户被分配任务数量不超过该移动用户最大任务承载量，定义每个任务所需移动用户数量为约束条件，建立异构群智感知任务多目标分配问题模型；
6、(3)将异构群智感知任务多目标分配问题分解为l个标量子问题；
7、(4)采用基于随机配置网络scn的初始化策略，针对每个标量子问题生成高质量的初始种群，基于所得到的初始种群，利用遗传算法迭代搜索标量子问题的最优分配方案；
8、(5)将l个标量子问题的最优分配方案合并成一个集合，并利用非支配排序法对集合中所有分配方案进行排序，得到原多目标任务分配问题的最优分配方案集合。
9、进一步，目标感知区域sa被划分为p个子区域，表示为sa＝{sa1,sa2,...,sap}，根据无人机和人员对子区域的可达性，将子区域分为三种类型，包括：1)禁飞区域；2)人员不可达区域；3)普遍可达区域，表示为styi＝{1,2,3}；现有待分配感知任务m个，表示为ta＝{ta1,ta2,...,tam}，移动用户n个，表示为u＝{u1,u2,...,un}，将第k个移动用户uk的类型表示为utyk；利用utyk＝1表示该移动用户类型为人员，能够执行位于禁飞区域或者普遍可达区域的任务，利用utyk＝0表示该移动用户为无人机，能够执行位于人员不可达区域以及普遍可达区域的任务；第j个子区域saj的可用移动用户集合表示为：
10、
11、进一步，构群智感知任务多目标分配问题模型的建立方法为：
12、定义第i个感知任务tai在第j个子区域saj中的感知数据收集为子任务taij，usijk为第k个移动用户uk对子任务taij的感知能力：
13、usijk＝prjk×reik
14、式中，prjk表示第k个移动用户uk对第j个子区域saj的偏好程度，也即uk前往saj执行任务的概率，reik表示uk为第i个感知任务tai收集有效数据的可信度；
15、定义aijk为第k个移动用户uk执行子任务taij的奖励，aijk由基础奖励和旅途成本补偿奖励两部分共同组成：
16、aijk＝a0+dsjk×au
17、式中，a0表示基础奖励，dsjk表示uk从当前所在位置前往子任务taij所在子区域的旅途距离，au为单位旅途成本补偿奖励；
18、优化目标为最大化所有感知任务的平均感知质量以及平均剩余执行成本，其定义为：
19、
20、其中，uti为第i个感知任务tai的感知质量，定义为所有被分配给tai的移动用户感知能力平均值：
21、
22、cok为第k个移动用户uk完成所有分配给他的子任务的总激励成本：
23、
24、此外，b为每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算，m为待分配感知任务数量，p为子区域的个数，ξ为每个子任务taij所需分配的移动用户数量；当子任务taij被分配给第k个移动用户uk时，xijk＝1，反之，xijk＝0；
25、进一步，约束条件包括以下四点：移动用户对感知网格区域的可达性，感知任务执行成本不得超出预算，每个移动用户被分配任务数量不超过该移动用户最大任务承载量，每个任务所需移动用户数量；
26、由于无人机和人员能够到达的感知网格区域不同，不同类型感知网格区域的可用移动用户集合存在差异，第j个子区域saj中的感知任务不能分配给不属于其可用移动用户集合uj中的移动用户：
27、
28、子任务执行成本不得超出预算：
29、
30、设第k个移动用户uk的最大任务承载量为ζk，则uk被分配子任务数量不得大于ζk：
31、
32、每个子任务taij被分配的工作者数量等于ξ：
33、
34、式中，b表示每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算，m表示待分配感知任务数量，p表示子区域的个数，ξ为每个子任务taij所需分配的移动用户数量；当子任务taij被分配给第k个移动用户uk时，xijk＝1，反之，xijk＝0。
35、进一步，将异构群智感知任务多目标分配问题分解为l个标量子问题，具体方法如下：
36、定义一组均匀分布的权重向量，表示为λ＝{λ1,λ2,...,λl}，利用切比雪夫分解法将多目标优化问题分解成l个标量子问题，则第l个子问题的目标函数为：
37、
38、式中，m为多目标优化问题中的目标个数，z＝(z1,...,zm)为参考点，zi为第i个目标的最好取值，设m＝2，z设置为[1,1]。
39、进一步，针对第l个标量子问题，训练随机配置网络scn的步骤如下：
40、(4.1.1)收集历史移动用户执行感知任务的感知能力和奖励成本记录；
41、(4.1.2)根据每个历史移动用户执行子任务taij的感知能力usijk和奖励成本aijk，计算该历史移动用户在第l个标量子问题中对子任务taij的效用ucijk：
42、
43、式中，为奖励成本aijk的归一化取值；
44、(4.1.3)对所有历史移动用户根据效用从高到低进行排序，以indijk表示第k个移动用户uk在所有历史移动用户中的排名；
45、(4.1.4)根据排名indijk计算移动用户uk在第l个标量子问题中对感知子任务taij的分配概率pbijk：
46、
47、式中，pbmin表示移动用户uk被分配给子任务taij的最小概率，取值0.05，pbmax表示移动用户uk被分配给子任务taij的最大概率，取值0.95；
48、(4.1.5)以历史移动用户的感知能力usijk和奖励成本aijk的归一化取值aijk作为样本输入随机配置网络scn，将对感知子任务taij的分配概率pbijk作为随机配置网络scn的输出，获得与历史移动用户数量相同的训练样本，用于训练第l个标量子问题的scn；
49、进一步，为第l个标量子问题初始化规模为num的种群过程为：
50、(4.2.1)计算当前时刻每个可用移动用户uk执行感知子任务taij的感知能力usijk和奖励成本aijk的归一化取值
51、(4.2.2)将当前时刻每个可用移动用户uk的感知能力usijk和奖励成本输入第l个标量子问题对应的scn模型，获取移动用户uk对感知子任务taij的分配概率pbijk；
52、(4.2.3)利用贪婪选择方法，基于当前所有可用移动用户的分配概率为每个感知子任务taij选取分配概率pbijk最大的移动用户uk作为任务执行者，直到感知子任务taij的任务执行者数量达到要求，获得1个分配方案，即1个个体；
53、(4.2.4)利用轮盘赌选择方法，基于当前所有可用移动用户的分配概率为每个感知子任务选取任务执行者，直到感知子任务taij的任务执行者数量达到要求，获得1个分配方案；循环执行上述轮盘赌选择操作获得num-1个分配方案；
54、(4.2.5)将(4.2.3)和(4.2.4)分别得到的分配方案合并成一个包含num个分配方案的集合，作为第l个标量子问题的初始种群popl。
55、进一步，将初始种群popl作为初始父代种群，利用遗传算法迭代搜索第l个标量子问题的最优分配方案，
56、(4.3.1)使用考虑感知能力的交叉算子和考虑综合实力的变异算子，基于popl生成num个子代个体，记为子代种群offl：
57、考虑感知能力的交叉算子中，从popl中任选两个父代个体，先将两个父代个体中出现的相同移动用户直接保留到子代个体中；再从剩余的移动用户中选取感知能力最强的保留到子代个体中；通过循环执行上述交叉操作，生成num个子代个体，记为子代种群offl；
58、对子代种群offl执行考虑综合实力的变异算子，定义移动用户的综合实力为用户对感知任务的感知能力和奖励成本名次之和；对子代种群offl中每个个体，将个体中对感知任务执行成本第一的移动用户，替换为对感知任务综合实力排名第一的移动用户；
59、(4.3.2)基于子代种群offl，采用可行性准则和收敛性准则更新父代种群popl的位置：
60、将父代种群popl和子代种群offl合并成种群mpopl，对合并后的种群mpopl中的个体基于deb可行性准则进行排序，选取前num/2个个体组成临时种群pop1，并从mpopl中移除pop1中的所有个体，表示为mpopl＝mpopl/popl；
61、对mpopl中剩余个体，计算每个个体对子问题的目标函数值fdte(x|λl,z)，根据该目标函数值对剩余个体进行升序排列，并选择前num/2个个体组成临时种群pop2；
62、将临时种群pop1和临时种群pop2合并，作为下一次迭代的父代种群popl；
63、(4.3.3)判断是否满足终止条件，设置终止条件为进化迭代次数达到最大迭代次数g，若满足，则终止遗传算法，并输出种群中目标函数值fdte(x|λl,z)最小的可行个体作为第l个标量子问题的最优分配方案否则，返回步骤(4.3.1)。
64、进一步，得到原多目标任务分配问题的pareto最优分配方案集合，具体方法如下：
65、将l个标量子问题最优分配方案合并生成集合archive，即利用非支配排序法对空间如archive中所有个体进行排序，从中选取不被archive中任何其他解支配的个体集合ps，表示为作为原多目标任务分配问题的最优分配方案集合。
66、一种计算机设备，包括处理器和存储器，所述处理器与存储器电性连接，存储器用于存储指令和数据，处理器用于执行所述的基于分解的异构群智感知任务多目标进化分配方法。
67、有益效果：
68、本发明与现有技术相比的优点在于：本发明针对仅由普通人员组成的传统群智感知系统覆盖区域有限的问题，使用由多个无人机和手持终端设备的人员共同组成的异构群智感知系统对目标感知区域进行感知数据收集，据此构建了异构群智感知系统的多目标任务分配模型，并利用进化优化算法搜索问题的最优分配方案解集，保证感知任务的完成质量和执行成本。相比于传统的基于进化优化的任务分配方法，首先将多目标问题分解为多个单目标子问题，然后对每个子问题，利用随机配置网络输出的移动用户对感知任务的分配概率生成分配方案集合，提高初始种群的质量。与现有技术相比，将多目标问题分解降低了问题求解难度，同时采用基于随机配置网络的初始化策略为每个子问题生成初始种群，能够显著增强种群的收敛性能，帮助算法为每个子问题找到更优秀的分配方案，进而为原多目标问题提供分布均匀、收敛性能好的最优分配方案集合，在本技术领域内具有广泛的实用性。
1.一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，使用异构群智感知系统对目标感知区域进行感知数据收集，异构群智感知系统的基本感知单元为移动用户，包括多个无人机和手持终端设备的人员，其中无人机可以到达人员无法抵达的地理位置；
2.根据权利要求1所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于：目标感知区域sa被划分为p个子区域，表示为sa＝{sa1,sa2,...,sap}，根据无人机和人员对子区域的可达性，将子区域分为三种类型，包括：1)禁飞区域；2)人员不可达区域；3)普遍可达区域，表示为styi＝{1,2,3}；现有待分配感知任务m个，表示为ta＝{ta1,ta2,...,tam}，移动用户n个，表示为u＝{u1,u2,...,un}，将第k个移动用户uk的类型表示为utyk；利用utyk＝1表示该移动用户类型为人员，能够执行位于禁飞区域或者普遍可达区域的任务，利用utyk＝0表示该移动用户为无人机，能够执行位于人员不可达区域以及普遍可达区域的任务；第j个子区域saj的可用移动用户集合表示为：
3.根据权利要求1所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，构群智感知任务多目标分配问题模型的建立方法为：
4.根据权利要求3所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，约束条件包括以下四点：移动用户对感知网格区域的可达性，感知任务执行成本不得超出预算，每个移动用户被分配任务数量不超过该移动用户最大任务承载量，每个任务所需移动用户数量；
5.根据权利要求1所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，将异构群智感知任务多目标分配问题分解为l个标量子问题，具体方法如下：
6.根据权利要求5所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，针对第l个标量子问题，训练随机配置网络scn的步骤如下：
7.根据权利要求6所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，为第l个标量子问题初始化规模为num的种群过程为：
8.根据权利要求7所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，将初始种群popl作为初始父代种群，利用遗传算法迭代搜索第l个标量子问题的最优分配方案，
9.根据权利要求8所述的一种基于分解的异构群智感知任务多目标进化分配方法，其特征在于，得到原多目标任务分配问题的pareto最优分配方案集合，具体方法如下：
10.一种计算机设备，其特征在于，包括处理器和存储器，所述处理器与存储器电性连接，存储器用于存储指令和数据，处理器用于执行权利要求1-9任一所述的基于分解的异构群智感知任务多目标进化分配方法。
