CN117933662B - 基于分解的异构群智感知任务多目标进化分配方法 - Google Patents
基于分解的异构群智感知任务多目标进化分配方法 Download PDFInfo
- Publication number
- CN117933662B CN117933662B CN202410155545.3A CN202410155545A CN117933662B CN 117933662 B CN117933662 B CN 117933662B CN 202410155545 A CN202410155545 A CN 202410155545A CN 117933662 B CN117933662 B CN 117933662B
- Authority
- CN
- China
- Prior art keywords
- perception
- task
- mobile user
- allocation
- sensing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 230000008447 perception Effects 0.000 title claims abstract description 126
- 238000000034 method Methods 0.000 title claims abstract description 40
- 238000000354 decomposition reaction Methods 0.000 title claims abstract description 15
- 238000005457 optimization Methods 0.000 claims abstract description 17
- 230000002068 genetic effect Effects 0.000 claims abstract description 12
- 230000006870 function Effects 0.000 claims description 9
- 230000035772 mutation Effects 0.000 claims description 6
- 230000000717 retained effect Effects 0.000 claims description 6
- 238000012549 training Methods 0.000 claims description 6
- 238000010187 selection method Methods 0.000 claims description 5
- 101100517651 Caenorhabditis elegans num-1 gene Proteins 0.000 claims description 3
- 230000001174 ascending effect Effects 0.000 claims description 3
- 238000013480 data collection Methods 0.000 claims description 3
- 230000008569 process Effects 0.000 claims description 3
- 239000013598 vector Substances 0.000 claims description 3
- 238000002372 labelling Methods 0.000 claims description 2
- 230000007613 environmental effect Effects 0.000 description 5
- 238000012544 monitoring process Methods 0.000 description 5
- 238000010586 diagram Methods 0.000 description 4
- 101001121408 Homo sapiens L-amino-acid oxidase Proteins 0.000 description 2
- 102100026388 L-amino-acid oxidase Human genes 0.000 description 2
- 101100012902 Saccharomyces cerevisiae (strain ATCC 204508 / S288c) FIG2 gene Proteins 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 238000000585 Mann–Whitney U test Methods 0.000 description 1
- 101100233916 Saccharomyces cerevisiae (strain ATCC 204508 / S288c) KAR5 gene Proteins 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000001514 detection method Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 239000002360 explosive Substances 0.000 description 1
- 230000002349 favourable effect Effects 0.000 description 1
- 238000012423 maintenance Methods 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 238000000528 statistical test Methods 0.000 description 1
- 238000009827 uniform distribution Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G06Q10/063—Operations research, analysis or management
- G06Q10/0631—Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G06Q10/06311—Scheduling, planning or task assignment for a person or group
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/04—Architecture, e.g. interconnection topology
- G06N3/047—Probabilistic or stochastic networks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/08—Learning methods
- G06N3/086—Learning methods using evolutionary algorithms, e.g. genetic algorithms or genetic programming
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N5/00—Computing arrangements using knowledge-based models
- G06N5/04—Inference or reasoning models
- G06N5/042—Backward inferencing
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- General Physics & Mathematics (AREA)
- Evolutionary Computation (AREA)
- General Engineering & Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Health & Medical Sciences (AREA)
- Life Sciences & Earth Sciences (AREA)
- Computational Linguistics (AREA)
- Artificial Intelligence (AREA)
- Biomedical Technology (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Biophysics (AREA)
- General Health & Medical Sciences (AREA)
- Molecular Biology (AREA)
- Entrepreneurship & Innovation (AREA)
- Educational Administration (AREA)
- Evolutionary Biology (AREA)
- Development Economics (AREA)
- Bioinformatics & Computational Biology (AREA)
- Physiology (AREA)
- Probability & Statistics with Applications (AREA)
- Game Theory and Decision Science (AREA)
- Bioinformatics & Cheminformatics (AREA)
- Marketing (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- General Business, Economics & Management (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
本发明公开了一种基于分解的异构群智感知任务多目标进化分配方法,属于无线传感网络技术领域。首先利用无人机和人员组成异构群智感知系统;考虑无人机和人员各自可到达的区域、成本预算限制,以感知任务的感知质量以及剩余执行成本最大化为优化目标,建立异构群智感知任务多目标分配模型;将该多目标任务分配模型分解为一组标量子问题;利用遗传算法迭代搜索该标量子问题的最优分配方案;将所有标量子问题的最优分配方案合并后得到原多目标任务分配问题的最优解集。有效解决了异构群智感知系统的任务分配问题,所提算法能够高效搜索到收敛性和多样性好的分配方案集合,能够极大的提高对不同环境数据获取的手段和效率。
Description
技术领域
本发明涉及一种基于分解的异构群智感知任务多目标进化分配方法,适用于同时考虑感知质量和经济性的由不同类型移动用户组成的异构群智感知系统的任务分配,属于无线传感网络技术领域。
背景技术
传统无线传感网络通过在若干目标地点部署成本高昂的专业监测设备,实现环境数据的监测。然而,固定在特定位置的监测设备只能覆盖有限范围,一旦感知区域发生变化,现有感知网络就无法满足监测要求。随着集成了众多传感器的移动智能终端爆炸式普及,移动群智感知成为一种新型感知范式,它利用手持移动智能终端的移动用户作为基本感知单元,通过移动互联网随时随地形成感知网络完成环境信息收集。相比于传统感知模式,移动群智感知网络具有部署方便、维护成本低、扩展性强等优点。
在移动群智感知系统中,从大量具有不同感知能力和奖励成本的移动用户中选取合适的任务执行者,是影响感知任务完成质量和成本的关键。显然,合适的群智感知任务分配方法是移动群智感知系统被广泛应用的前提。然而,现有研究主要针对由仅有普通人员组成的群智感知系统任务分配问题,而这类人员无法到达高速公路、湖泊等区域,进而导致这些区域的监测数据缺失。考虑到无人机可以作为补充感知单元,前往人员步行难以到达的区域收集数据,有必要针对由人员和无人机共同组成的异构群智感知系统,考虑感知任务的完成质量和成本,开展其任务多目标分配方法研究。
对于多目标优化问题,分解是一种简单而有效的方法。它将多目标优化问题分解成多个单目标子问题。基于此,可以将遗传算法用于求解每个子问题的最优分配方案,然后通过合并所有子问题的最优分配方案就可以得到原多目标问题的Pareto分配方案集合。此外,考虑到随机配置网络是学习移动用户特征,进而给出移动用户分配概率的一种有利方法,可以利用训练好的随机配置网络提供的移动用户分配概率来生成多样化且有潜力的初始种群。相比于随机生成的初始种群,基于随机配置网络生成的初始种群显然能够加快收敛速度、增强收敛性能,帮助找到更优秀的分配方案。
发明内容
技术问题:本发明的目的是要克服现有技术的不足,提供一种易实现、搜索效率高、收敛性能好,能够更好更快捷对目标区域的环境信息进行收集的异构群智感知任务多目标进化分配方法。
技术方案:本发明提供的一种基于分解的异构群智感知任务多目标进化分配方法,使用异构群智感知系统对目标感知区域进行感知数据收集,异构群智感知系统的基本感知单元为移动用户,包括多个无人机和手持终端设备的人员,其中无人机可以到达人员无法抵达的地理位置;
包括以下步骤:
(1)将基础单元需要抵达的目标感知区域构建为异构群智感知图,将异构群智感知图进行网格划分,并根据其实际情况对划分的网格进行标注,包括禁飞网格区域、人员不可达网格区域、普遍可达网格区域;感知系统根据各感知网格区域的标注类型,将位于不同感知网格区域的感知任务分配给合适的移动用户去完成;
(2)综合考虑感知任务的完成质量和经济性、相关资源约束限制、最大化所有感知任务的平均感知质量、平均剩余执行成本为优化目标,以移动用户对感知区域的可达性、感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,定义每个任务所需移动用户数量为约束条件,建立异构群智感知任务多目标分配问题模型;
(3)将异构群智感知任务多目标分配问题分解为L个标量子问题;
(4)采用基于随机配置网络SCN的初始化策略,针对每个标量子问题生成高质量的初始种群,基于所得到的初始种群,利用遗传算法迭代搜索标量子问题的最优分配方案;
(5)将L个标量子问题的最优分配方案合并成一个集合,并利用非支配排序法对集合中所有分配方案进行排序,得到原多目标任务分配问题的最优分配方案集合。
进一步,目标感知区域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的可用移动用户集合表示为:
进一步,构群智感知任务多目标分配问题模型的建立方法为:
定义第i个感知任务tai在第j个子区域saj中的感知数据收集为子任务taij,usijk为第k个移动用户uk对子任务taij的感知能力:
usijk=prjk×reik
式中,prjk表示第k个移动用户uk对第j个子区域saj的偏好程度,也即uk前往saj执行任务的概率,reik表示uk为第i个感知任务tai收集有效数据的可信度;
定义aijk为第k个移动用户uk执行子任务taij的奖励,aijk由基础奖励和旅途成本补偿奖励两部分共同组成:
aijk=a0+dsjk×au
式中,a0表示基础奖励,dsjk表示uk从当前所在位置前往子任务taij所在子区域的旅途距离,au为单位旅途成本补偿奖励;
优化目标为最大化所有感知任务的平均感知质量以及平均剩余执行成本,其定义为:
其中,uti为第i个感知任务tai的感知质量,定义为所有被分配给tai的移动用户感知能力平均值:
cok为第k个移动用户uk完成所有分配给他的子任务的总激励成本:
此外,B为每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M为待分配感知任务数量,P为子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0;
进一步,约束条件包括以下四点:移动用户对感知网格区域的可达性,感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,每个任务所需移动用户数量;
由于无人机和人员能够到达的感知网格区域不同,不同类型感知网格区域的可用移动用户集合存在差异,第j个子区域saj中的感知任务不能分配给不属于其可用移动用户集合Uj中的移动用户:
子任务执行成本不得超出预算:
设第k个移动用户uk的最大任务承载量为ζk,则uk被分配子任务数量不得大于ζk:
每个子任务taij被分配的工作者数量等于ξ:
式中,B表示每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M表示待分配感知任务数量,P表示子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0。
进一步,将异构群智感知任务多目标分配问题分解为L个标量子问题,具体方法如下:
定义一组均匀分布的权重向量,表示为Λ={λ1,λ2,...,λL},利用切比雪夫分解法将多目标优化问题分解成L个标量子问题,则第l个子问题的目标函数为:
式中,m为多目标优化问题中的目标个数,z=(z1,...,zm)为参考点,zi为第i个目标的最好取值,设m=2,z设置为[1,1]。
进一步,针对第l个标量子问题,训练随机配置网络SCN的步骤如下:
(4.1.1)收集历史移动用户执行感知任务的感知能力和奖励成本记录;
(4.1.2)根据每个历史移动用户执行子任务taij的感知能力usijk和奖励成本aijk,计算该历史移动用户在第l个标量子问题中对子任务taij的效用ucijk:
式中,为奖励成本aijk的归一化取值;
(4.1.3)对所有历史移动用户根据效用从高到低进行排序,以indijk表示第k个移动用户uk在所有历史移动用户中的排名;
(4.1.4)根据排名indijk计算移动用户uk在第l个标量子问题中对感知子任务taij的分配概率pbijk:
式中,pbmin表示移动用户uk被分配给子任务taij的最小概率,取值0.05,pbmax表示移动用户uk被分配给子任务taij的最大概率,取值0.95;
(4.1.5)以历史移动用户的感知能力usijk和奖励成本aijk的归一化取值aijk作为样本输入随机配置网络SCN,将对感知子任务taij的分配概率pbijk作为随机配置网络SCN的输出,获得与历史移动用户数量相同的训练样本,用于训练第l个标量子问题的SCN;
进一步,为第l个标量子问题初始化规模为num的种群过程为:
(4.2.1)计算当前时刻每个可用移动用户uk执行感知子任务taij的感知能力usijk和奖励成本aijk的归一化取值
(4.2.2)将当前时刻每个可用移动用户uk的感知能力usijk和奖励成本输入第l个标量子问题对应的SCN模型,获取移动用户uk对感知子任务taij的分配概率pbijk;
(4.2.3)利用贪婪选择方法,基于当前所有可用移动用户的分配概率为每个感知子任务taij选取分配概率pbijk最大的移动用户uk作为任务执行者,直到感知子任务taij的任务执行者数量达到要求,获得1个分配方案,即1个个体;
(4.2.4)利用轮盘赌选择方法,基于当前所有可用移动用户的分配概率为每个感知子任务选取任务执行者,直到感知子任务taij的任务执行者数量达到要求,获得1个分配方案;循环执行上述轮盘赌选择操作获得num-1个分配方案;
(4.2.5)将(4.2.3)和(4.2.4)分别得到的分配方案合并成一个包含num个分配方案的集合,作为第l个标量子问题的初始种群Popl。
进一步,将初始种群Popl作为初始父代种群,利用遗传算法迭代搜索第l个标量子问题的最优分配方案,
(4.3.1)使用考虑感知能力的交叉算子和考虑综合实力的变异算子,基于Popl生成num个子代个体,记为子代种群Offl:
考虑感知能力的交叉算子中,从Popl中任选两个父代个体,先将两个父代个体中出现的相同移动用户直接保留到子代个体中;再从剩余的移动用户中选取感知能力最强的保留到子代个体中;通过循环执行上述交叉操作,生成num个子代个体,记为子代种群Offl;
对子代种群Offl执行考虑综合实力的变异算子,定义移动用户的综合实力为用户对感知任务的感知能力和奖励成本名次之和;对子代种群Offl中每个个体,将个体中对感知任务执行成本第一的移动用户,替换为对感知任务综合实力排名第一的移动用户;
(4.3.2)基于子代种群Offl,采用可行性准则和收敛性准则更新父代种群Popl的位置:
将父代种群Popl和子代种群Offl合并成种群mPopl,对合并后的种群mPopl中的个体基于Deb可行性准则进行排序,选取前num/2个个体组成临时种群Pop1,并从mPopl中移除Pop1中的所有个体,表示为mPopl=mPopl/Popl;
对mPopl中剩余个体,计算每个个体对子问题的目标函数值fdte(x|λl,z),根据该目标函数值对剩余个体进行升序排列,并选择前num/2个个体组成临时种群Pop2;
将临时种群Pop1和临时种群Pop2合并,作为下一次迭代的父代种群Popl;
(4.3.3)判断是否满足终止条件,设置终止条件为进化迭代次数达到最大迭代次数G,若满足,则终止遗传算法,并输出种群中目标函数值fdte(x|λl,z)最小的可行个体作为第l个标量子问题的最优分配方案否则,返回步骤(4.3.1)。
进一步,得到原多目标任务分配问题的Pareto最优分配方案集合,具体方法如下:
将L个标量子问题最优分配方案合并生成集合Archive,即利用非支配排序法对空间如Archive中所有个体进行排序,从中选取不被Archive中任何其他解支配的个体集合PS,表示为作为原多目标任务分配问题的最优分配方案集合。
一种计算机设备,包括处理器和存储器,所述处理器与存储器电性连接,存储器用于存储指令和数据,处理器用于执行所述的基于分解的异构群智感知任务多目标进化分配方法。
有益效果:
本发明与现有技术相比的优点在于:本发明针对仅由普通人员组成的传统群智感知系统覆盖区域有限的问题,使用由多个无人机和手持终端设备的人员共同组成的异构群智感知系统对目标感知区域进行感知数据收集,据此构建了异构群智感知系统的多目标任务分配模型,并利用进化优化算法搜索问题的最优分配方案解集,保证感知任务的完成质量和执行成本。相比于传统的基于进化优化的任务分配方法,首先将多目标问题分解为多个单目标子问题,然后对每个子问题,利用随机配置网络输出的移动用户对感知任务的分配概率生成分配方案集合,提高初始种群的质量。与现有技术相比,将多目标问题分解降低了问题求解难度,同时采用基于随机配置网络的初始化策略为每个子问题生成初始种群,能够显著增强种群的收敛性能,帮助算法为每个子问题找到更优秀的分配方案,进而为原多目标问题提供分布均匀、收敛性能好的最优分配方案集合,在本技术领域内具有广泛的实用性。
附图说明
图1是本发明实施例中生成的异构群智感知示意图。
图2是本发明实施例中基于分解的异构群智感知任务多目标进化分配方法的流程示意图。
图3是本发明实施例中使用的遗传算法流程示意图。
具体实施方式
下面结合具体附图和实例对本发明的实施方式作进一步详细说明。
本发明通过随身携带网络及监测设备的移动人员以及携带检测设备的无人机对区域环境信息进行采集监测,为了提高工作效率,同时提高可检测的区域范围,因此将被测区域进行划块,生成异构群智感知示意图,并在每个划分的网格子区域上标注移动限制条件,之后分配移动人员或者无人机对不同网格子区域的环境信息进行检测,防止将需要检测的网格子区域属于被分配单位无法移动的区域,其中包括移动人员无法检测湖泊和悬崖,无人机无法进入禁飞区域等。
如图1所示,本实施例构建的异构群智感知示意图,其中目标感知区域被划分为12个子区域,各子区域的可达性如图中所示。
选取样例3-500,3个感知任务,500个移动用户,每个感知任务需要在每个子区域中分配5个移动用户去收集相应数据,每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算为6,每个移动用户的最大任务承载量为6,移动用户对不同子区域的偏好程度是从[0,1]区间中任意取值,移动用户收集有效数据的可信度也是从[0,1]区间中任意取值,移动用户在一个子区域中为一个感知任务收集数据的基础奖励为5,单位旅行成本补偿奖励为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},将移动用户的类型表示为utyk,当utyk=1时,表示该移动用户类型为人员,可以执行位于禁飞区域或者普遍可达区域的任务,而当utyk=0时,表示该移动用户为无人机,可以执行位于人员不可达区域以及普遍可达区域的任务;基于此,第j个子区域saj的可用移动用户集合可表示为:
(2)在异构群智感知系统中,考虑感知任务的完成质量和经济性,以及相关资源约束限制,以最大化所有感知任务的平均感知质量以及平均剩余执行成本为两个优化目标,以移动用户对感知区域的可达性,感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,每个任务所需移动用户数量为约束条件,建立异构群智感知任务多目标分配问题模型;
定义第i个感知任务tai在第j个子区域saj中的感知数据收集为子任务taij,usijk为第k个移动用户uk对子任务taij的感知能力:
usijk=prjk×reik (2)
式中,prjk表示第k个移动用户uk对第j个子区域saj的偏好程度,也即uk前往saj执行任务的概率,reik表示uk为第i个感知任务tai收集有效数据的可信度;
定义aijk为第k个移动用户uk执行子任务taij的奖励,aijk由基础奖励和旅途成本补偿奖励两部分共同组成:
aijk=a0+dsjk×au (3)
式中,a0表示基础奖励,dsjk表示uk从当前所在位置前往子任务taij所在子区域的旅途距离,au为单位旅途成本补偿奖励;
优化目标为最大化所有感知任务的平均感知质量以及平均剩余执行成本,其定义为:
其中,uti为第i个感知任务tai的感知质量,定义为所有被分配给tai的移动用户感知能力平均值:
cok为第k个移动用户uk完成所有分配给他的子任务的总激励成本:
此外,B为每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M为待分配感知任务数量,P为子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0;
约束条件包括:移动用户对感知区域的可达性,感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,每个任务所需移动用户数量;
约束条件1:考虑无人机和人员能够到达的感知网格区域不同,不同类型感知网格区域的可用移动用户集合存在差异,第j个子区域saj中的感知任务不能分配给不属于其可用移动用户集合Uj中的移动用户:
约束条件2:子任务执行成本不得超出预算:
约束条件3:定义第k个移动用户uk的最大任务承载量为ζk,则uk被分配子任务数量不得大于ζk:
约束条件4:每个子任务taij被分配的工作者数量要等于ξ:
式中,B表示每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M表示待分配感知任务数量,P表示子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0。
(3)将异构群智感知任务多目标分配问题分解为L个标量子问题,具体方法如下:
定义一组均匀分布的权重向量,表示为Λ={λ1,λ2,...,λL},利用切比雪夫分解法将多目标优化问题分解成L个标量子问题,则第l个子问题的目标函数为:
式中,m为多目标优化问题中的目标个数,z=(z1,...,zm)为参考点,zi为第i个目标的最好取值,设m=2,z设置为[1,1];
(4)对于第l个标量子问题,采用基于随机配置网络(SCN)的初始化策略,生成高质量的初始种群Popl,并用遗传算法迭代搜索该种群的最优解,算法流程如图3所示,具体方法如下:
(4.1)针对第l个标量子问题,离线训练SCN模型,执行步骤4.1.1-4.1.5
(4.1.1)获取1000个历史移动用户执行感知任务的感知能力和奖励成本记录;
(4.1.2)对于每个历史移动用户,根据他执行子任务taij的感知能力usijk和奖励成本aijk,计算他在第l个标量子问题中对子任务taij的效用ucijk:
式中,为奖励成本aijk的归一化取值;
(4.1.3)对所有历史移动用户根据效用从高到低进行排序,以indijk表示第k个移动用户uk在所有历史移动用户中的排名;
(4.1.4)根据排名indijk计算移动用户uk在第l个标量子问题中对感知子任务taij的分配概率pbijk:
式中,pbmin和pbmax分别表示移动用户uk被分配给子任务taij的最小概率和最大概率,分别取为0.05和0.95;
(4.1.5)以历史移动用户的感知能力usijk和奖励成本aijk的归一化取值作为样本输入,以及他对感知子任务taij的分配概率pbijk作为样本的输出,获得1000个训练样本,用于训练第l个标量子问题的SCN;
(4.2)在线初始化第l个标量子问题的种群,执行步骤4.2.1-4.2.5:
(4.2.1)计算当前时刻每个可用移动用户uk执行感知子任务taij的感知能力usijk和奖励成本aijk的归一化取值
(4.2.2)将当前时刻每个可用移动用户uk的usijk和输入第l个标量子问题对应的SCN模型,获取移动用户uk对感知子任务taij的分配概率pbijk;
(4.2.3)利用贪婪选择方法,基于当前所有可用移动用户的分配概率为每个感知任务taij选取分配概率pbijk最大的移动用户uk作为任务执行者,直到taij的任务执行者数量达到要求,通过执行步骤4.2.3获得1个分配方案,即1个个体;
(4.2.4)利用轮盘赌方法,基于当前环境下所有可用移动用户的分配概率为每个感知子任务选取任务执行者,直到taij的任务执行者数量达到要求,通过执行4.2.4获得num-1个分配方案;
(4.2.5)将(4.2.3)和(4.2.4)分别得到的分配方案合并成一个包含num个分配方案的集合,作为第l个标量子问题的初始种群Popl;
(4.3)基于初始种群Popl,利用遗传算法迭代搜索第l个标量子问题的最优分配方案,执行步骤4.3.1-4.3.7;
(4.3.1)使用考虑感知能力的交叉算子和考虑综合实力的变异算子,基于Popl生成num个子代个体:
在考虑感知能力的交叉算子中,从Popl中任选两个父代个体,首先将两个父代个体中出现的相同移动用户直接保留到子代个体中;再从剩余的移动用户中选取感知能力最强的保留到子代个体中;通过循环执行上述交叉操作,生成num个子代个体,记为子代种群Offl;
对Offl执行考虑综合实力的变异算子,定义移动用户的综合实力为用户对感知任务的感知能力和奖励成本名次之和;对子代种群Offl中每个个体,将个体中对感知任务执行成本第一的移动用户,替换为对感知任务综合实力排名第一的移动用户;
(4.3.2)基于子代种群Offl,采用可行性准则和收敛性准则更新父代种群Popl的位置:
将父代种群Popl和子代种群Offl合并成种群mPopl,对合并后的种群mPopl中的个体基于Deb可行性准则进行排序,选取前num/2个个体组成临时种群Pop1,并从mPopl中移除Pop1中的所有个体,表示为mPopl=mPopl/Popl;
对mPopl中剩余个体,直接根据式(11)计算得到的适应度值fdte(x|λl,z)进行升序排列,并选择前num/2个个体组成临时种群Pop2;
将临时种群Pop1和临时种群Pop2合并,作为下一次迭代的父代种群Popl;
(4.3.3)判断是否满足终止条件,设置终止条件为进化迭代次数达到最大迭代次数G,若满足,则终止遗传算法,并输出种群中适应值最大的可行个体作为第l个标量子问题的最优分配方案否则,返回步骤(4.3.1);
(5)将L个标量子问题的最优分配方案合并,并利用非支配排序法进行排序,得到原多目标任务分配问题的Pareto最优分配方案集合,具体方法如下:
(5.1)将L个标量子问题最优分配方案合并到集合Archive中,即并利用非支配排序法对Archive中所有个体进行排序,从中选取不被Archive中任何其他解支配的个体集合PS,表示为作为原多目标任务分配问题的Pareto最优分配方案集合。
本发明的效果通过以下仿真实验说明:
实验内容:
针对样例3-500,3个感知任务,500个移动用户,分别利用所提进化算法采用和不采用基于SCN的初始化策略对问题进行求解,并对比他们的性能。其中,两种算法的种群规模num均设置为10,算法终止准则为迭代次数G达到100,用于分解问题的权重数量L=20。
实验结果:
将两种方法在样例上分别独立运行30次。表1列出了两种方法多次运行求得的解集在HV指标上的均值和标准差,HV越大,说明算法获得的解集多样性和收敛性越好。同时引入显著水平为0.05的Mann–Whitney U检验对结果进行统计测试,其中,“+”表示对比算法性能显著优于本发明所提算法的性能,“~”表示两者性能无明显差异,反之,“-”则表示显著劣于本发明所提算法。
由表1可以看出,本发明所提方法在样例上获得了更高的HV平均值,本发明所提基于分解的多目标进化算法相比于不采用本发明所提初始化策略的进化算法,能够显著增强Pareto最优解集的多样性和收敛性,提高了感知任务的完成质量,降低了感知任务的执行成本。
表1
样例3_500 | HV |
本发明所提基于分解的多目标进化算法 | 0.8442±0.0034 |
不采用本发明所提初始化策略的多目标进化算法 | 0.8305±0.0019(-) |
虽然,上文中已经用一般性说明及具体样例对本发明作了详尽的描述,但在本发明基础上,可以对之作一些修改或改进,这对本领域技术人员而言是显而易见的。因此,在不偏离本发明精神的基础上所做的这些修改或改进,均属于本发明要求保护的范围。
Claims (2)
1.一种基于分解的异构群智感知任务多目标进化分配方法,其特征在于,使用异构群智感知系统对目标感知区域进行感知数据收集,异构群智感知系统的基本感知单元为移动用户,包括多个无人机和手持终端设备的人员,其中无人机可以到达人员无法抵达的地理位置;
包括以下步骤:
(1)将基础单元需要抵达的目标感知区域构建为异构群智感知图,将异构群智感知图进行网格划分,并根据其实际情况对划分的网格进行标注,包括禁飞网格区域、人员不可达网格区域、普遍可达网格区域;感知系统根据各感知网格区域的标注类型,将位于不同感知网格区域的感知任务分配给合适的移动用户去完成;
(2)综合考虑感知任务的完成质量和经济性、相关资源约束限制、最大化所有感知任务的平均感知质量、平均剩余执行成本为优化目标,以移动用户对感知区域的可达性、感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,定义每个任务所需移动用户数量为约束条件,建立异构群智感知任务多目标分配问题模型;
(3)将异构群智感知任务多目标分配问题分解为L个标量子问题;
(4)采用基于随机配置网络SCN的初始化策略,针对每个标量子问题生成高质量的初始种群,基于所得到的初始种群,利用遗传算法迭代搜索标量子问题的最优分配方案;
(5)将L个标量子问题的最优分配方案合并成一个集合,并利用非支配排序法对集合中所有分配方案进行排序,得到原多目标任务分配问题的最优分配方案集合;
目标感知区域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的可用移动用户集合表示为:
构群智感知任务多目标分配问题模型的建立方法为:
定义第i个感知任务tai在第j个子区域saj中的感知数据收集为子任务taij,usijk为第k个移动用户uk对子任务taij的感知能力:
usijk=prjk×reik
式中,prjk表示第k个移动用户uk对第j个子区域saj的偏好程度,也即uk前往saj执行任务的概率,reik表示uk为第i个感知任务tai收集有效数据的可信度;
定义aijk为第k个移动用户uk执行子任务taij的奖励,aijk由基础奖励和旅途成本补偿奖励两部分共同组成:
aijk=a0+dsjk×au
式中,a0表示基础奖励,dsjk表示uk从当前所在位置前往子任务taij所在子区域的旅途距离,au为单位旅途成本补偿奖励;
优化目标为最大化所有感知任务的平均感知质量以及平均剩余执行成本,其定义为:
其中,uti为第i个感知任务tai的感知质量,定义为所有被分配给tai的移动用户感知能力平均值:
cok为第k个移动用户uk完成所有分配给他的子任务的总激励成本:
此外,B为每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M为待分配感知任务数量,P为子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0;
约束条件包括以下四点:移动用户对感知网格区域的可达性,感知任务执行成本不得超出预算,每个移动用户被分配任务数量不超过该移动用户最大任务承载量,每个任务所需移动用户数量;
由于无人机和人员能够到达的感知网格区域不同,不同类型感知网格区域的可用移动用户集合存在差异,第j个子区域saj中的感知任务不能分配给不属于其可用移动用户集合Uj中的移动用户:
子任务执行成本不得超出预算:
设第k个移动用户uk的最大任务承载量为ζk,则uk被分配子任务数量不得大于ζk:
每个子任务taij被分配的工作者数量等于ξ:
式中,B表示每个感知任务在每个子区域中可提供给一个移动用户的最大成本预算,M表示待分配感知任务数量,P表示子区域的个数,ξ为每个子任务taij所需分配的移动用户数量;当子任务taij被分配给第k个移动用户uk时,xijk=1,反之,xijk=0;
将异构群智感知任务多目标分配问题分解为L个标量子问题,具体方法如下:
定义一组均匀分布的权重向量,表示为Λ={λ1,λ2,...,λL},利用切比雪夫分解法将多目标优化问题分解成L个标量子问题,则第l个子问题的目标函数为:
式中,m为多目标优化问题中的目标个数,z=(z1,...,zm)为参考点,zi为第i个目标的最好取值,设m=2,z设置为[1,1];
针对第l个标量子问题,训练随机配置网络SCN的步骤如下:
(4.1.1)收集历史移动用户执行感知任务的感知能力和奖励成本记录;
(4.1.2)根据每个历史移动用户执行子任务taij的感知能力usijk和奖励成本aijk,计算该历史移动用户在第l个标量子问题中对子任务taij的效用ucijk:
式中,为奖励成本aijk的归一化取值;
(4.1.3)对所有历史移动用户根据效用从高到低进行排序,以indijk表示第k个移动用户uk在所有历史移动用户中的排名;
(4.1.4)根据排名indijk计算移动用户uk在第l个标量子问题中对感知子任务taij的分配概率pbijk:
式中,pbmin表示移动用户uk被分配给子任务taij的最小概率,取值0.05,pbmax表示移动用户uk被分配给子任务taij的最大概率,取值0.95;
(4.1.5)以历史移动用户的感知能力usijk和奖励成本aijk的归一化取值aijk作为样本输入随机配置网络SCN,将对感知子任务taij的分配概率pbijk作为随机配置网络SCN的输出,获得与历史移动用户数量相同的训练样本,用于训练第l个标量子问题的SCN;
为第l个标量子问题初始化规模为num的种群过程为:
(4.2.1)计算当前时刻每个可用移动用户uk执行感知子任务taij的感知能力usijk和奖励成本aijk的归一化取值
(4.2.2)将当前时刻每个可用移动用户uk的感知能力usijk和奖励成本输入第l个标量子问题对应的SCN模型,获取移动用户uk对感知子任务taij的分配概率pbijk;
(4.2.3)利用贪婪选择方法,基于当前所有可用移动用户的分配概率为每个感知子任务taij选取分配概率pbijk最大的移动用户uk作为任务执行者,直到感知子任务taij的任务执行者数量达到要求,获得1个分配方案,即1个个体;
(4.2.4)利用轮盘赌选择方法,基于当前所有可用移动用户的分配概率为每个感知子任务选取任务执行者,直到感知子任务taij的任务执行者数量达到要求,获得1个分配方案;循环执行上述轮盘赌选择操作获得num-1个分配方案;
(4.2.5)将(4.2.3)和(4.2.4)分别得到的分配方案合并成一个包含num个分配方案的集合,作为第l个标量子问题的初始种群Popl;
将初始种群Popl作为初始父代种群,利用遗传算法迭代搜索第l个标量子问题的最优分配方案,
(4.3.1)使用考虑感知能力的交叉算子和考虑综合实力的变异算子,基于Popl生成num个子代个体,记为子代种群Offl:
考虑感知能力的交叉算子中,从Popl中任选两个父代个体,先将两个父代个体中出现的相同移动用户直接保留到子代个体中;再从剩余的移动用户中选取感知能力最强的保留到子代个体中;通过循环执行上述交叉操作,生成num个子代个体,记为子代种群Offl;
对子代种群Offl执行考虑综合实力的变异算子,定义移动用户的综合实力为用户对感知任务的感知能力和奖励成本名次之和;对子代种群Offl中每个个体,将个体中对感知任务执行成本第一的移动用户,替换为对感知任务综合实力排名第一的移动用户;
(4.3.2)基于子代种群Offl,采用可行性准则和收敛性准则更新父代种群Popl的位置:
将父代种群Popl和子代种群Offl合并成种群mPopl,对合并后的种群mPopl中的个体基于Deb可行性准则进行排序,选取前num/2个个体组成临时种群Pop1,并从mPopl中移除Pop1中的所有个体,表示为mPopl=mPopl/Popl;
对mPopl中剩余个体,计算每个个体对子问题的目标函数值fdte(x|λl,z),根据该目标函数值对剩余个体进行升序排列,并选择前num/2个个体组成临时种群Pop2;
将临时种群Pop1和临时种群Pop2合并,作为下一次迭代的父代种群Popl;
(4.3.3)判断是否满足终止条件,设置终止条件为进化迭代次数达到最大迭代次数G,若满足,则终止遗传算法,并输出种群中目标函数值fdte(x|λl,z)最小的可行个体作为第l个标量子问题的最优分配方案否则,返回步骤(4.3.1);
得到原多目标任务分配问题的Pareto最优分配方案集合,具体方法如下:
将L个标量子问题最优分配方案合并生成集合Archive,即利用非支配排序法对空间如Archive中所有个体进行排序,从中选取不被Archive中任何其他解支配的个体集合PS,表示为作为原多目标任务分配问题的最优分配方案集合。
2.一种计算机设备,其特征在于,包括处理器和存储器,所述处理器与存储器电性连接,存储器用于存储指令和数据,处理器用于执行权利要求1所述基于分解的异构群智感知任务多目标进化分配方法。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202410155545.3A CN117933662B (zh) | 2024-02-02 | 2024-02-02 | 基于分解的异构群智感知任务多目标进化分配方法 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202410155545.3A CN117933662B (zh) | 2024-02-02 | 2024-02-02 | 基于分解的异构群智感知任务多目标进化分配方法 |
Publications (2)
Publication Number | Publication Date |
---|---|
CN117933662A CN117933662A (zh) | 2024-04-26 |
CN117933662B true CN117933662B (zh) | 2024-10-25 |
Family
ID=90763025
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202410155545.3A Active CN117933662B (zh) | 2024-02-02 | 2024-02-02 | 基于分解的异构群智感知任务多目标进化分配方法 |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN117933662B (zh) |
Families Citing this family (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN118966500A (zh) * | 2024-08-09 | 2024-11-15 | 山东鲁软数字科技有限公司 | 一种基于ai算法多目标优化的应急资源模块化调拨和路径规划方法 |
Citations (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN110149649A (zh) * | 2019-06-21 | 2019-08-20 | 深圳市共进电子股份有限公司 | Mesh网络的测试方法、系统、设备终端和存储介质 |
CN113641192A (zh) * | 2021-07-06 | 2021-11-12 | 暨南大学 | 一种基于强化学习的无人机群智感知任务的路径规划方法 |
Family Cites Families (7)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US11364932B2 (en) * | 2019-06-25 | 2022-06-21 | Lg Electronics Inc. | Method for transmitting sensing information for remote driving in automated vehicle and highway system and apparatus therefor |
CN114298307A (zh) * | 2021-12-06 | 2022-04-08 | 南京信息工程大学 | 一种移动群智感知变速多任务分配问题的混合蛙跳求解方法 |
CN114925941A (zh) * | 2022-07-21 | 2022-08-19 | 深圳市信润富联数字科技有限公司 | 群智感知任务分配方法、装置、设备及存储介质 |
CN115617472A (zh) * | 2022-09-19 | 2023-01-17 | 北京理工大学 | 面向城市监控数据时延保障的无人机群感知方法 |
CN116483116A (zh) * | 2023-03-23 | 2023-07-25 | 展讯半导体(南京)有限公司 | 无人机移动群智感知的管理方法、系统、设备及存储介质 |
CN116541148B (zh) * | 2023-05-08 | 2024-10-18 | 中国矿业大学 | 一种群智感知的多任务动态多目标进化分配方法 |
CN117094399A (zh) * | 2023-08-17 | 2023-11-21 | 中国石油大学(北京) | 面向无人机辅助稀疏群智感知的协同感知方法及装置 |
-
2024
- 2024-02-02 CN CN202410155545.3A patent/CN117933662B/zh active Active
Patent Citations (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN110149649A (zh) * | 2019-06-21 | 2019-08-20 | 深圳市共进电子股份有限公司 | Mesh网络的测试方法、系统、设备终端和存储介质 |
CN113641192A (zh) * | 2021-07-06 | 2021-11-12 | 暨南大学 | 一种基于强化学习的无人机群智感知任务的路径规划方法 |
Also Published As
Publication number | Publication date |
---|---|
CN117933662A (zh) | 2024-04-26 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
Meraihi et al. | A comprehensive survey of Crow Search Algorithm and its applications | |
Eseye et al. | Short-term forecasting of heat demand of buildings for efficient and optimal energy management based on integrated machine learning models | |
Abualigah et al. | Salp swarm algorithm: a comprehensive survey | |
Zhou et al. | Multiobjective evolutionary algorithms: A survey of the state of the art | |
Pham et al. | Data clustering using the bees algorithm | |
Makhadmeh et al. | Recent advances in butterfly optimization algorithm, its versions and applications | |
CN110276393A (zh) | 一种绿色建筑能耗复合预测方法 | |
CN117933662B (zh) | 基于分解的异构群智感知任务多目标进化分配方法 | |
Martínez-Ballesteros et al. | Selecting the best measures to discover quantitative association rules | |
Kumar T et al. | Hybrid approach for resource allocation in cloud infrastructure using random forest and genetic algorithm | |
Cui et al. | A hybrid rolling grey framework for short time series modelling | |
Aggarwal et al. | On sensor selection in linked information networks | |
Kurada et al. | A preliminary survey on optimized multiobjective metaheuristic methods for data clustering using evolutionary approaches | |
CN112488192A (zh) | 一种区域电网短期负荷预测方法 | |
Zhang et al. | Hybrid edge-cloud collaborator resource scheduling approach based on deep reinforcement learning and multiobjective optimization | |
Leng et al. | Integrated energy system evaluation method based on dimensionality reduction and indexes updating with incomplete information | |
Qian et al. | An enhanced genetic algorithm for constrained knapsack problems in dynamic environments | |
Wang et al. | Improved Genetic Algorithm (VNS‐GA) using polar coordinate classification for workload balanced multiple Traveling Salesman Problem (mTSP) | |
CN119151091B (zh) | 一种新型配用电系统灵活性降碳资源配置优化方法及系统 | |
CN114546609A (zh) | 一种面向异构集群的dnn推理任务批调度方法 | |
CN114465256A (zh) | 多节点电动汽车充电负荷联合对抗生成区间预测方法 | |
Liu et al. | An improved multiobjective evolutionary approach for community detection in multilayer networks | |
CN118734004A (zh) | 联用电力场景语义模型的联动计算方法及系统 | |
KR20220030155A (ko) | 에너지 관리 장치 및 그 방법 | |
Benameur et al. | A new hybrid particle swarm optimization algorithm for handling multiobjective problem using fuzzy clustering technique |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
GR01 | Patent grant | ||
GR01 | Patent grant |