采用离散烟花算法的移动群智感知异构任务分配*

申晓宁，许 笛，宋丽妍，姚铖滨，王玉芳

(1.南京信息工程大学自动化学院，江苏 南京 210044；2.江苏省大气环境与装备技术协同创新中心，江苏 南京 210044； 3.江苏省大数据分析技术重点实验室，江苏 南京 210044； 4.广东省类脑智能计算重点实验室(南方科技大学)，广东 深圳 518055)

1 引言

自中国共产党第十九届中央委员会第五次全体会议上强调“推动绿色发展，促进人与自然和谐共生”这一理念以来，国家对环境质量的改善给予了持续的关注。当城市空气中的污染物含量超标或噪声分贝过大时，会使得环境承载能力下降，最终影响市民的身体健康[1]。近年来，随着可手持设备和可穿戴设备的迅速普及，以及它们在物联网和智能城市中的充分应用，移动群智感知MCS(Mobile Crowd-Sensing)已成为传感和收集数据的一种高效的城市感知模式。MCS是指通过人们已有的移动设备形成参与式的感知网络，并将感知任务发布给网络中的个体或群体来完成，从而帮助专业人员或公众收集数据、分析信息和共享知识。目前，MCS已应用于交通监控、空气质量检测、流域条件检测、健康感知和饮食感知等方面[2]。将MCS用于空气污染和噪声监测，为城市管理提供了新的解决方案，可以在没有额外花费的基础上，扩大已部署的传感系统的空间覆盖范围，从而显著改善公民的日常生活。

目前，对MCS系统的研究主要集中在4个方面，分别为任务分配、激励机制、数据收集和数据处理。其中,任务分配确定任务和参与者之间的分配关系，其合理性决定了参与者上传的数据质量。近年来，MCS任务分配问题已成为社会计算、协作计算和智能计算领域的研究热点[3]。文献[4]指出，心理过程会指导参与者的行为，行为是心理的体现。如果参与者对平台的任务分配方案不满意，或执行任务时的体验感较差，将影响任务的感知质量甚至产生无效的感知行为，损害平台利益，对系统产生负面影响。因此，平台在分配任务时除了要考虑平台效益外，还需顾及参与者的心理过程，即兴趣偏好，以尽可能地提高参与者的满意度。

在MCS任务分配问题中，学者主要从模型和求解算法2方面开展研究。在模型的研究中，针对任务类型，Zhao等[5]建立了同类型感知任务的分配模型，但忽略了系统中可能同时存在多种不同类型的异构任务。针对任务时间，袁姝等[6]考虑了参与者的弹性在线时间，忽略了参与者执行任务的测量时间对数据的影响。针对任务分配方案的稳定性,Zhou等[7]利用稳定匹配理论将任务分配问题转化为双边匹配问题。在算法设计方面，有分布式算法[8]、匹配算法[9]和多项式时间算法[5]等。然而，MCS任务分配已被证明为NP-hard问题[10]。上述传统算法受到时间和空间复杂度的限制，大多只适用于小规模问题。部分算法虽可用于求解大规模问题，但对解的质量无法保证。元启发式算法具有参数少、对问题信息依赖性小、全局优化能力强的优点，特别适用于求解NP-hard问题[11]。已有部分学者将MCS任务分配问题建模为基于搜索问题，采用元启发式算法求解该问题的最优解。Wang等[12]结合了蚁群优化算法的正反馈机制与遗传算法的快速收敛性，提出了MQC(Maximun Quality and minimun Cost)-遗传算法；袁殊等[6]用鲸鱼算法优化感知数据质量；杨正清等[13]用布谷鸟算法优化系统成本；Xi等[14]利用变异遗传算法最大化任务完成效率。上述算法虽然取得了一定的效果，但仍存在启发信息利用不足和未充分利用群体进化状态信息等问题。

烟花算法FWA(FireWork Algorithm)[15]是模拟烟花在夜空中爆炸过程的一种元启发式算法。目前已成功运用于物流配送[16]、随机装配线混流调度[17]等多种离散问题。本文针对上述已有MCS任务分配模型的不足，考虑参与者心理与行为过程，建立了MCS异构任务分配模型，并提出了引入预测信息的离散烟花算法DFWAPI(Discrete FireWorks Algorithm incorporating Predictive Information)求解该模型。设计了基于问题启发信息的爆炸算子、爆炸振幅的分组线性预测策略和变异自适应竞争机制。与6种已有算法的对比实验结果表明，所提算法在MCS异构任务分配模型上具有更高的求解精度。

2 考虑参与者心理与行为过程的空气质量MCS任务分配模型

本节主要以最小化平台成本为目标，考虑参与者的心理和行为过程及健康状况，构建更加贴合实际的空气质量MCS异构任务分配数学模型。

2.1 问题描述

任务发起者需要创建关于公民在不同污染环境等级中的个人暴露时间与位置信息。于是委托平台发布了一组异构任务T，其中包括m个测量机动车尾气任务和n个社会生活噪声任务。假设在平台上登记的候选参与者集合为U，U中参与者的数目l不少于任务数量。为了使上传数据不存在冗余现象且尽可能减少平台成本，需要进行合理的任务分配。本文采用单人单任务方式，即一个人只做一项任务，一项任务也只需被执行一次。

2.2 心理与行为过程

本节从补偿成本、参与者匹配度和数据损失成本三方面来阐述参与者心理过程对行为过程的影响。

2.2.1 补偿成本

(1)

其中，amin、bmin和cmin分别为空气质量为优的PM2.5最小值、小雨雨量的最小值和轻风时风速的最小值，amax、bmax和cmax分别为重度污染的PM2.5最大值、暴雨雨量最大值和狂风风速最高值。

Cj=αj×BC

(2)

(3)

其中，BC为完成一项任务的最大补偿成本，取值设定为5元；αj为等级系数。

2.2.2 参与者匹配度与数据损失成本

本文模型考虑参与者心理与行为过程的关系。通过匹配度反映参与者的心理状态，行为过程由参与者对任务数据的测量时间来体现。

(1)兴趣度HIij：为了使平台在分配任务时更加人性化，考虑参与者对各项任务的兴趣度。一般情况下，参与者与任务之间的距离及参与者是否能够顺路完成任务这2个因素对参与者的兴趣度影响较大。在平台发布任务之后，第i(i=1,2,…,l)个参与者对第j(j=1,2,…,m+n)个任务的兴趣度HIij的计算如式(4)和式(5)所示：

(4)

(5)

其中，dij为参与者i与任务j之间的距离值，单位为km;γ为方向系数。由式(4)和式(5)可见，当某项任务与参与者距离较近，且参与者可顺路完成该任务时，参与者对其兴趣度较大；若某项任务位于参与者附近但不在其行进方向上时，参与者的兴趣度将有所下降。由式(4)可知，HIij∈[0,100]。

Ri=100×[β×HDAi+(1-β)×OTUi]=

(6)

其中，l为参与者总人数，β为权重系数，r为参与者i参与历史任务的总数。由于历史数据感知质量对信誉度的影响更大，因此设置β=0.6。由式(6)可知，Ri∈[0,100]。

(3)匹配度Mij∈[0,100](i=1,2,…,l,j=1,2,…,m+n)定义为参与者i对任务j的兴趣度和信誉度的平均值，如式(7)所示：

Mij=(Hij+Ri)/2

(7)

(8)

(9)

其中，η为单位测量时间的数据损失成本。

2.3 数学模型

MCS异构任务分配模型中，定义决策变量Xij如式(10)所示：

(10)

目标函数和约束条件如式(11)～式(15)所示。

(11)

(12)

s.t.

(13)

(14)

(15)

其中，式(11)表示平台总成本,由补偿成本Cj、数据损失成本Pij和距离成本Qij组成。综合汽车、自行车和步行等不同出行方式的费用，估计得到参与者每千米的路程报酬约为g=5元。式(12)计算参与者与任务点的距离，(Uxi,Uyi)和(Txi,Tyi)分别为用户和任务的地理坐标。式(13)～式(15)为约束条件，式(13)表示任一任务由且只由一个参与者完成；式(14)表示任一参与者至多只能完成一项任务；式(15)表示执行测量尾气任务的参与者呼吸系统健康系数需大于或等于60。

3 求解MCS异构任务分配模型的离散烟花算法DFWAPI

针对所建MCS异构任务分配模型，提出一种引入预测信息的烟花算法DFWAPI，设计了引入反向学习的初始化策略、利用启发信息的烟花爆炸算子、爆炸振幅的分组线性预测策略及变异算子的自适应竞争机制，以提高算法的求解能力。

3.1 求解MCS异构任务分配模型的DFWAPI算法框架

DFWAPI求解MCS异构任务分配模型的框架如图1所示。DFWAPI主要由4个模块组成：(1)引入反向学习的初始化模块；(2)烟花爆炸产生爆炸火花模块；(3)烟花变异产生变异火花模块；(4)选择模块。其中选择模块采用的是把每一代的核心烟花保留到下一代的精英保留策略和排序选择策略[20]。

Figure 1 Framework of DFWAPI 图1 DFWAPI算法框架

3.2 引入反向学习的初始化策略

本文对烟花个体采用整数编码。一个个体表示参与者在平台发布任务中的一套分配方案。个体长度为当前发布的任务数量，个体每一维上的整数对应分配给相应任务的参与者编号。由于平台实际在线的参与者数量可能远高于任务数量，常规的对所有参与者和任务进行0-1矩阵编码的方式将产生大量全零行，因此本文采用的整数向量编码可节约计算资源，提高算法搜索效率。为了便于计算个体目标值，个体编码还引入了参与者属性，如图2所示。将参与者的匹配度依式(8)转化为相应的预计测量时间后与距离值共同代入式(11)，求出该个体的目标值。个体目标值越小，说明其适应度越好。

Figure 2 Encoding of introducing the participant attribute图2 引入参与者属性的编码方式

由于烟花算法的种群规模N较小，为了提高初始烟花种群中个体分布的多样性，本文在初始化阶段引入反向学习的思想[21]。首先随机生成N个烟花后，再根据式(16)对各初始烟花的每一维进行反向调整：

ψ′=S+E-ψ

(16)

其中，S为参与者编号的起始值；E为参与者编号的终止值；ψ为初始生成的分配到某任务的参与者编号；ψ′为调整后的参与者编号。由式(16)得到的N个个体称为反向烟花。若反向烟花的目标值优于初始烟花，则用反向烟花替换初始烟花；若劣于初始烟花，则保留初始烟花，由此得到N个最终的初始烟花。

3.3 离散爆炸算子

本节设计了烟花爆炸振幅的分组线性预测策略和利用问题启发信息的离散爆炸算子。

依据经典烟花算法(FWA)[15]计算爆炸火花数量Sk，由于本文面向的MCS异构任务分配是离散优化问题，FWA的爆炸振幅不再适用，因此本文将爆炸振幅定义为每个个体需要改变的维数。设每个个体烟花长度为len(len=m+n)，对于适应度值较优的烟花，可在其附近进行精细地挖掘，因而它们可以取较小的爆炸振幅；反之，对于适应度值较差的烟花，应在其周围进行大范围搜索。因此，为它们选取较大的爆炸振幅。本文首先依据式(17)计算出第k个烟花的基本爆炸振幅Ak，其后在此基础上对最终的爆炸振幅进行分组线性预测(见3.3.1节)：

k=1,2,…,N

(17)

其中，M为控制爆炸振幅的参数，且M=round(λ*len)，λ为常数，取值为0.8，round为四舍五入操作；Ymin为当前种群中个体目标的最小值；ε为一个极小的常数，用来避免除零操作。为防止爆炸振幅过大或者过小，通过式(18)对Ak进行调整：

(18)

3.3.1 爆炸振幅的分组线性预测

(19)

所提分组线性预测策略的伪代码如算法1所示。首先根据目标值排序将烟花种群分为2组，排名第2的烟花至中心烟花构成第1组，记为Poph，排名在中心烟花之后的烟花为第2组，记为Popl(第1～2行)。计算中心烟花和核心烟花的爆炸振幅(第3行)。动态调整核心烟花的爆炸振幅(第4行)。计算出中心烟花和核心烟花当前代与上一代爆炸振幅的改变幅度(第5～6行)。Poph中个体的爆炸振幅跟随核心烟花爆炸振幅的变化趋势进行调整(第7～9行)，Popl中个体的爆炸振幅跟随中心烟花爆炸振幅的变化趋势进行调整(第10～12行)。输出为种群中各烟花的爆炸振幅(第13行)。

1：对Pop按目标值由小到大排序，排在首位和中间位的烟花分别记为核心烟花和中心烟花；

2：排名第2的烟花至中心烟花之间的烟花构成分组Poph,排名在中心烟花之后的烟花构成分组Popl;

7：forallu∈Pophdo{

8: 依据式(17)和式(18)计算烟花u的基本爆炸振幅At(u);

10:forallv∈Popldo{

11: 依据式(17)和式(18)计算烟花v的基本爆炸振幅At(v);

3.3.2 利用启发信息的爆炸算子

3.4 变异算子的自适应竞争机制

FWA在连续优化问题中采用高斯变异的方式增加种群多样性，但在离散问题中并不适用。单一变异方式产生的变异火花无法控制其目标值的优劣，较差的变异火花在迭代中被逐步淘汰，没有对种群的进化起到促进的作用。而采用多种变异方式产生火花，虽然增加了火花的多样性，但并不能保证每种变异方式均适用于当前进化阶段，依旧可能产生较多劣解。为了解决该问题，本节设计变异算子的自适应竞争机制。该机制设置3种变异方式，每个烟花通过基于贡献度Cw(w=1,2,3)的轮盘赌策略自适应选择相应的变异方式，贡献度越高的变异方式被选择的概率越大，产生优良变异火花的可能性也越大。

3种变异方式分别为单基因位变异、基因对变异和基因片段变异，具体操作分别为随机替换、2点交换和片段逆序。随机替换是指在烟花个体中随机选一个基因位，对于尾气测量任务，从未被选中的健康参与者中随机选择一名替换原参与者，对于噪声测量任务，从未被选中的所有参与者中随机选择一名替换。2点交换是指随机选择2个基因位构成1个变异对，将2个参与者的位置交换。片段逆序是指随机选择2点作为片段的起始点与终止点，将选中的参与者片段逆序排列。对于2点交换和片段逆序后个体的前m个测量尾气的任务，若变异后的参与者为不健康参与者，则从未被选中的健康参与者中随机选择一名替换。

(1)将产生的变异火花依次与当前种群所有烟花的适应度进行比较。

(2)记录目标值劣于变异火花的烟花个数r。

(3)根据式(20)更新贡献度：

(20)

(21)

变异算子自适应竞争机制的伪代码如算法2所示。对第k个烟花采用基于贡献度的轮盘赌策略选择对应的变异方式(第6行)，其中index∈{1,2,3}，分别代表随机替换、2点交换和片段逆序，其后，记录第k个烟花产生第q个变异火花的变异方式reckq，并在集合Y中保存变异火花ykq(第7～17行)。接着，更新变异方式reckq的贡献度和各变异方式的选择概率(第18和第19行)。输出所有烟花产生的变异火花集合和每种变异方式更新后的贡献度(第20行)。

3:Y←∅;

4:forallxk∈Popdo{

5:forq=1 toSkdo{

7:ifindex==1{

8:ykq←Stochastic(xk);//随机替换

9:reckq=1;}

10:elseifindex==2{

11:ykq←Exchange(xk);//2点交换

12:reckq=2;}

13:elseifindex==3

14:ykq←Reverse(xk);//片段逆序

15:reckq=3;}

17:Y←[Y,ykq];

4 实验仿真与结果分析

为了验证所提算法和改进策略的有效性，采用Python3.7.6软件进行仿真实验，计算机处理器参数为Intel(R) Core(TM) i7-8565U CPU @ 1.80 GHz 1.99 GHz，8 GB运行内存。本文设计了2组实验：(1)改进策略的有效性验证；(2)将所提算法DFWAPI与文献中6种具有代表性的算法进行对比，以验证所提算法的性能。采用10个随机生成的算例和1个包含南京市夫子庙周边50个任务点的实例作为测试算例。所有对比算法均在各算例上分别进行30次独立实验，每次实验的最大目标评价次数为50 000。DFWAPI的种群规模N设置为12。其中除了算法GGA_I采用原文献的0-1编码解码方式外，其它对比算法均使用与所提算法DFWAPI相同的整数编码解码方式。其余参数设置均与原文献相同。

随机算例中，参与者和任务位置的横纵坐标均在[0,1 000]内随机均匀生成，参与者信誉度在[0,100]内随机均匀生成，参与者的方向系数随机取为1或0.5。为简化问题，假设平台中健康和不健康参与者的比例为4∶1。

4.1 改进策略有效性验证

为了验证第3.2～第3.4节所提各策略的有效性，分别将所提算法DFWAPI中的一个改进策略用另一种已有策略替换，得到4种对比算法：用随机初始化代替引入反向学习初始化的算法DFWAPI-RI、仅通过式(17)和式(18)计算烟花基本爆炸振幅的算法DFWAPI-LP、在爆炸生成算子阶段不引入启发信息的算法DFWAPI-HI和将3种变异策略等概率随机使用的算法DFWAPI-AV。将4种对比算法与DFWAPI在11个测试算例上分别独立运行30次，计算各算法搜索到的式(11)所示成本目标的平均值Avg和最优值Best，将Best和Avg的最好值加粗表示，如表1所示。为显著对比4种策略的优劣，采用显著水平为0.05的Wilcoxon秩和检验对实验结果进行统计测试，其中“+”“-”和“=”分别表示所提算法显著优于、显著劣于对比算法和与对比算法无显著差别。

Table 1 Comparison results of the proposed algorithm and the replace single strategy algorithms表1 所提算法和替换单一策略算法的对比结果 元

由表2可知，所提算法DFWAPI在绝大多数算例中取得了最优的Best值，对于平均值Avg,在大中小规模的算例中均为最优。同时，统计测试结果表明，在大多数算例中，在替换DFWAPI的单一改进策略后会导致求解性能显著变差，以上实验结果表明，所提各种改进策略是可行且有效的。产生以上结果的原因首先是引入反向学习的初始化降低了随机初始化产生劣解的概率，同时增加了种群的多样性。其次，采用线性预测的思想在基本爆炸振幅的基础上，根据基准烟花的爆炸振幅改变量，调整了各烟花的爆炸方向和振幅。再次，在确定烟花的爆炸数量与爆炸范围之后引入2种启发信息对烟花进行爆炸，使得烟花在解空间中的爆炸过程具有较好的方向性和目的性，降低了原有爆炸方式的盲目性。最后，变异火花的产生采用自适应的思想，评价每种变异方式在不同进化阶段对群体进化的贡献度，并依据贡献度选择更适合当前进化状态的变异方式，与等概率随机选择变异方式相比，所提策略能更有针对性地提高了算法的局部搜索精度。

Table 2 Comparative experimental results of FWAPI and contrast algorithms表2 FWAPI与对比算法的实验结果 元

4.2 所提算法的性能验证

为了验证所提DFWAPI算法在求解MCS异构任务分配问题时的整体性能，选用4种具有代表性的求解MCS任务分配问题的已有算法(混合遗传算法HGA(Hybrid Genetic Algorithm)[19]、贪婪增强遗传GGA_I(Greedy-enhanced Genetic Algorithm for International)算法[23]、遗传算法GA(Genetic Algorithm)[24]、鲸鱼算法WOA(Whale Optimization Algorithm)[6])以及2种新型烟花算法(裸骨烟花算法BBFWA(Bare Bones FireWorks Algorithm)[25]和基于失败者淘汰的烟花算法LoTFWA(Loser-out Tournament based FireWorks Algorithm)[26])，将它们分别应用于本文建立的模型，并与所提算法进行比较,实验结果如表2所示。

由表2可见，所提DFWAPI算法与其余6种算法相比，在所有随机算例和实例上均取得了最佳的最优值Best和平均值Avg。显著水平为0.05的Wilcoxon秩和检验结果表明，在大多数算例中DFWAPI显著优于6个对比算法。主要原因是4种改进策略的综合使用和有效配合。在初始化阶段，所提算法为后续烟花的爆炸操作提供了较好的起点；在烟花爆炸阶段，引入不同类型基准烟花的信息对烟花的搜索范围进行预测和调整，使得种群的搜索范围随着任务的推进自动地进行缩放，在进化前期强化了全局搜索能力，后期则提高了局部搜索能力；同时，根据问题不同类型的启发信息生成多种爆炸火花，引导个体的收敛方向。在火花变异阶段，利用自适应竞争机制进一步增强在烟花附近的局部搜索能力，提升了变异火花的质量。多种改进策略的协同合作，有效平衡了算法的全局搜索和局部挖掘能力，使算法获得了较强的寻优能力和求解精度。综上，与6种对比算法相比，所提算法能够更加有效地求解MCS异构任务分配问题，为平台提供一套成本更低的分配方案。

5 结束语

本文以监测空气污染与生活噪声为任务背景研究了MCS异构任务分配问题。本文工作和结论如下：(1)建立了考虑参与者心理与行为过程的MCS异构任务分配数学模型。(2)针对模型的特点，对初始化、爆炸振幅、爆炸算子和变异策略做出了改进。对策略有效性的验证结果表明，所提策略是可行且有效的。(3)将所提算法与文献中6种具有代表性的算法进行对比，实验结果表明，所提算法在求解精度方面优于所有对比算法，它在规模为小、中、大的随机算例与实际算例中均能搜索到具有最低成本的MCS异构任务分配方案，说明它对问题规模具有较好的可扩展性。