移动群智感知中基于改进文化基因算法的长时多任务分配

图1 任务⁃用户⁃时间段关系

Fig.1 Relationship diagram of task⁃user⁃time period

图2

图2 (a)任务⁃用户关系；(b)用户⁃时间段关系；(c)任务⁃时间段关系

Fig.2 Relationship diagram of task⁃user (a)，user⁃time peroid (b) and task⁃time peroid (c)

将图1的阴影方框表示为1，白色方框表示为0，可得图3所示的任务分配示意图.图中第一行表示任务集A；第二行X序列为01数组，表示任务的一个分配方案，长度为报名用户数n，元素值为1代表该用户入选，为0则未入选； E 为01矩阵，行数为时长 $T'$ 分成的单位时间段数q，列数为报名用户数n，元素的列号为用户号，行号为任务的单位时间段号，对于每一列，元素值为1表示该用户可以完成该时段的任务.本文目标是在所有被选用户总报价低于预算B这一条件下，找出最佳的 X 序列使得任务覆盖质量最大.

图3

图3 任务分配示意图

Fig.3 Task assignment diagram

2.3　长时任务覆盖质量评价模型

对于长时任务的覆盖质量，希望在预算内热点区域的数据比非热点区域多，各任务的时间覆盖率高，冗余数据多且均衡.根据此目标构建长时任务覆盖质量评价模型.任务覆盖质量F如式（4）所示，子任务覆盖质量 $f (a_{i}) (1 \leq i \leq m)$ 如式（5）所示：

F = z \times \sum_{i = 1}^{m} f (a_{i})

(4)

f (a_{i}) = (ω_{i} \times {x_{i}}^{2} \times y_{i}) / (σ + α)

(5)

其中，z为任务覆盖率，m为子任务数，ω为任务的权重系数，x为时间覆盖率，y为时间冗余度，σ为冗余均衡度，α为一极小值，防止 $σ = 0$ 导致式（5）的分母为0.主要参数定义如下：

（1） z是任务覆盖率，定义为有用户进行感知的子任务数h与总任务数m的比，即：

z = h / m

(6)

（2） ω表示任务的重要程度.在多任务的分配中需调控各子任务的资源分配，任务的ω_i 越大，则覆盖质量越大，获得的资源越多.

（3） x表示任务中已覆盖时长的占比.子任务a_i 中进行感知的所有用户覆盖的非重复单位时间段数s_i 与单位时间段数q的比称为时间覆盖率x_i，即：

x_{i} = s_{i} / q

(7)

（4） y表示同时同地收集的数据的冗余程度.子任务a_i 中所有用户进行感知的总时间段数k_i 与单位时间段数q的比称为时间冗余度y_i，即：

y_{i} = k_{i} / q

(8)

（5） σ表示同一任务地点不同时段冗余数据的均衡程度，以任务各单位时间段的覆盖次数的标准差来衡量.对于 $T' = \{t_{1}, t_{2}, \dots, t_{q}\}$ 的q个单位时间段，a_i 的有覆盖次数 $C = \{c_{1}, c_{2}, \dots, c_{q}\}$ ，则：

σ = \sqrt[]{({(c_{1} - \bar{c})}^{2} + {(c_{2} - \bar{c})}^{2} + \dots + {(c_{q} - \bar{c})}^{2}) ∕ q}

(9)

\bar{c} = (c_{i}) / q

(10)

3 任务分配

3.1　改进文化基因任务分配算法

文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的融合算法.本文提出改进文化基因算法（Improved Memetic Algorithm，IMA），采用自适应遗传算法（Adaptive Genetic Algorithm，AGA）进行全局搜索，结合模拟退火算法（Simulated Annealing Algorithm，SAA）进行局部搜索，并设计贪心修复算法（Greedy Repair algorithm，GRA）对不合适的个体进行修复.IMA使用格雷编码，以0和1构成的X序列作为任务分配的一个结果，通过对交叉概率和变异概率的自适应调整，提高全局寻优的速度.在陷入局部最优后使用SAA进行局部寻优，并对种群中不满足预算约束的个体通过GRA进行修复.IMA的算法流程如下.

算法1 IMA

输入：任务集A，用户集U，种群规模N，迭代阈值g，交叉概率pc₁，变异概率pm，初始温度T₀，温度衰减比例pt，终止温度T_min；

输出：最优分配结果X_m .

1.随机初始化种群矩阵 $Q_{|U| \times N}$ ；

2.遗传次数 $i = 0$ ，温度 $T e m = T_{0}$ ；

3.利用GRA得到可行矩阵 $Q'$ ；

4.计算 $Q'$ 中个体的适应度f；

5.保存F中最大的个体X_m 并记录其未变的次数n；

6.自适应调整pc和pm；

7.根据轮盘赌的方法进行选择操作，淘汰劣质个体；

8.根据与或逻辑运算进行交叉操作产生新个体；

9.进行变异操作；

10.若 $n > g / 5$ ，执行步骤11，否则，跳到步骤17；

11.随机产生个体，经GRA修复后得到新个体X₁；

12.计算增量 $Δ f = f (X_{1}) - f (X_{m})$ ；

13.按照Metropolis准则判断是否接受新解X₁；

14.i++；

15.温度衰减 $T e m = T e m \times p t$ ；

16.若 $T e m < T_{m i n}$ ，执行步骤18，否则，跳到步骤11；

17.i++；

18.若 $i > g$ ，执行步骤19，否则，跳到步骤3；

19.输出最优分配结果X_m .

步骤3用GRA对不可行的个体进行修复得到 $Q'$ ，因为X代表的分配方案费用可能会超出任务预算或只用了少部分预算，这显然不可行.

步骤4使用式（11）对F做标准化处理得出适应度f，其中，F_avg，F_max和F_min是当前种群所有X的覆盖质量的均值、最大值和最小值，F通过个体X选择的用户利用式（5）计算得出.

f = 1 - \frac{1}{1 + e^{\frac{F - F_{a v g}}{F_{m a x} - F_{m i n}} \times 3}}

(11)

步骤6使用式（12）和式（13）分别自适应调整pc和pm加速收敛，其中， $f_{m a x}$ 和 $f_{a v g}$ 分别为种群个体适应度的最大值和平均值， $f'$ 为交叉的两个体中较大的适应度，f为变异个体的适应度.

p c = \{\begin{matrix} p c_{1} - \frac{(p c_{1} - 0.5) (f^{'} - f_{a v g})}{f_{m a x} - f_{a v g}}, f^{'} \geq f_{a v g} \\ p c_{1}, f^{'} < f_{a v g} \end{matrix}

(12)

p m = \{\begin{matrix} p m_{1} - \frac{(p m_{1} - 0.01) (f_{m a x} - f)}{f_{m a x} - f_{a v g}}, f \geq f_{a v g} \\ p m_{1}, f < f_{a v g} \end{matrix}

(13)

步骤13依据Metropolis准则接受新解，即在接受优质解的同时有一定概率接受劣质解，这样能有效地跳出局部最优.若两个体适应度的差 $Δ f > 0$ ，则接受X₁作为新解，否则以概率 $p' = e x p (Δ f / T e m)$ 接受X₁.

在算法时间复杂度方面，本文使用格雷编码来表示选择用户的一个解，每次迭代都经过自适应遗传算法的选择、交叉和变异等操作，时间复杂度依次为 $O (N), O (|U| \times N) 和 O (|U| \times N)$ ，一共需要经历g次迭代，所以IMA的自适应遗传阶段的时间复杂度为 $O (g \times |U| \times N)$ .由于IMA只是有一定概率进行模拟退火阶段，其时间复杂度为 $O (p \times N)$ ，其中，p为退火迭代次数.因为采用线性降温而收敛迅速，p远小于 $g \times N$ ，所以其退火阶段的时间复杂度小于自适应遗传阶段.综上，IMA自适应遗传算法的时间复杂度一致，均为 $O (g \times |U| \times N)$ .

3.2　不可行个体的贪心修复算法

算法2 GRA

输入：用户集 $U$ ，种群矩阵 $Q_{|U| \times N}$ ，总预算B；

输出：可行矩阵 $Q'$ .

1.初始化用户报价矩阵 $P_{1 \times |U|}$ ；

2.计算方案报价矩阵 $B_{1 \times N}^{'} = P_{1 \times |U|} \times Q_{|U| \times N}$ ；

3.For $(i = 0; i < N; i + +)$ do

4.If $(B_{i}^{'} > B)$ do

5.While $(B_{i}^{'} > B)$ do

6.将Q中第 $i + 1$ 列的个体记为 $X_{i}$ ；

7.拒绝 $X_{i}$ 中已选择且报价最低的用户；

8.重新计算 $B_{i}^{'}$ ；

9.End while

10.End if

11.Else if $(B_{i}^{'} < B)$ do

12.将 $X_{i}$ 未选择的用户中报价最小值记为P_m；

13.While $((B - B_{i}^{'}) > P_{m})$ do

14.接受 $X_{i}$ 中未选择且报价最低的用户；

15.重新计算 $B_{i}^{'}$ 和P_m；

16.End while

17.End if

18.得到修复后的个体 $X'$ ；

19.End for

20.输出可行矩阵 $Q'$ .

步骤1和步骤2中，根据用户集U中每个用户的报价得到用户报价矩阵P.种群矩阵Q每一列都是由 $|U| (|U| 为 U 的模, 即用户数)$ 个基因组成的个体X， $P \times Q$ 则得到种群中每个个体代表方案的报价矩阵 $B'$ .

步骤9和步骤10中，当 $X_{i}$ 代表的方案报价 $B_{i}^{'}$ 超出任务总预算B时，该分配方案不可行.可通过每次拒绝当前已选择的用户中报价最低的用户来降低方案总报价，直至其在预算B内.

步骤11~17中，当预算还有剩余时，为了最大程度地使用预算来实现最大化任务覆盖质量的目标，在每次剩余预算多于当前未选择的用户的最低报价时，就选择该用户，直到剩余预算不足以再选择任何用户.

4 实验仿真

4.1　实验设置

使用Python3.7进行仿真实验，采用香港科技大学智慧城市研究小组公开的上海市出租车数据集Taxis （cse.hkust.edu.hk/scrg/）和微软研究院公开的北京市出租车轨迹数据集T⁃Drive^［24］，其字段主要包括车辆编号、日期、时间、经度和纬度.图4是根据出租车运行数据生成的上海热点区域图，随机在图中生成若干个任务地点，以出租车数据作为用户的数据.对于首次经过任务地点一千米范围的出租车，认为其报名该任务，并将其在范围内待的时间作为报名的感知时间.仿真实验的主要参数范围如表1所示.

图4

图4 上海的热点区域图

Fig.4 Map of urban hot spots in Shanghai

表1 主要参数范围

Table 1 Range of main parameters

主要参数	范围
总预算（元）	$[200,1000]$
任务地点数	$[2,6]$
任务时长 (h)	$[3,7]$
时长阈值 (h)	12
单位时间段时长 (h)	0.5
热点区域任务权重	2
非热点区域任务权重	1
报名用户数	$[50,250]$
用户单位时间段报价 (元)	$[2,10]$
种群规模	50
迭代阈值	250

新窗口打开| 下载CSV

4.2　对比算法

本文主要验证移动群智感知中长时多任务分配问题，在预算约束下，以最大化任务覆盖质量为目标，提出的任务分配算法IMA的有效性，与MA （Memetic Algorithm），GGA（Grey Genetic Algorithm）和ACA （Ant Colony Algorithm）等基准算法在覆盖质量大小和时间利用率两个方面进行对比分析.MA是普通文化基因算法，其将遗传算法和模拟退火算法简单结合；GGA是贪心遗传算法，其采用花光预算去优先招募感知时段最长的用户，产生初始种群后依靠遗传算法求解；ACA为蚁群算法，通过蚁群在路径上累积的信息素浓度得到待优化问题的可行解.在预算约束方面，IMA使用设计的GRA，保证任务分配方案的报价不超出预算，而三种基准算法采用惩罚函数的方法.

4.3　结果与分析

任务预算为a，感知地点数为b，感知时长为c小时，共有d个用户报名，记为 $a \times b \times c \times d$ .图5给出了四种算法在Taxis数据集上 $500 \times 3 \times 4 \times 100$ 条件下运行一次（即迭代250次）的迭代次数和覆盖质量的关系，可以看到每次迭代各算法的寻优的覆盖质量.

图5

图5 500×3×4×100条件下的迭代次数⁃覆盖质量关系

Fig.5 Iteration times⁃coverage quality diagram under 500×3×4×100

4.3.1　覆盖质量的分析

分析任务规模（包括地点数量b和感知时长c，记为 $b \times c$ ）、报名人数和总预算对任务覆盖质量的影响.仿真实验中采取控制变量法来比较各算法在任务覆盖质量中的表现，同时，为了避免偶然性，每个算法都重复运行十次，取平均值作为最终结果.

图6是各算法在Taxis和T⁃Drive数据集中，预算为500元和报名人数为100时，不同任务规模对应的覆盖质量.由图可见，覆盖质量随着任务规模的增大而下降，因为在预算和报名人数不变的条件下，任务的地点越多、时长越长，时间覆盖率和时间冗余度等指标都会下降，导致覆盖质量整体降低.

图6

图6 Taxis (a)和T⁃Drive (b)数据集中各算法在不同任务规模时的覆盖质量

Fig.6 Coverage quality with different task scales on Taxis (a) and T⁃Drive (b) datasets

图7是各算法在Taxis和T⁃Drive数据集中，预算为500元和任务规模为 $3 \times 4$ 时，不同的报名人数对应的任务覆盖质量.由图可见，覆盖质量随着报名人数的增加而升高，因为在预算和任务规模不变的条件下，报名的人数越多，可选中的优质用户越多，因而提高了覆盖质量.这种质量提升依赖增加的人数中优质用户的数量，当优质用户较多时，质量提升的效果明显.

图7

图7 Taxis (a)和T⁃Drive (b)数据集中各算法在不同报名人数时的覆盖质量

Fig.7 Coverage quality with different enrollments on Taxis (a) and T⁃Drive (b) datasets

图8是各算法在Taxis和T⁃Drive数据集中，任务规模为 $3 \times 4$ 和报名人数为100时，不同预算对应的覆盖质量.由图可见，覆盖质量随着预算的增加而升高，因为在任务规模和报名用户数不变的条件下，预算越多，招募的用户越多，越能有效地提高覆盖质量.

图8

图8 Taxis (a)和T⁃Drive (b)数据集中各算法在不同预算时的覆盖质量

Fig.8 Coverage quality with different budgets on Taxis (a) and T⁃Drive (b) datasets

综上，在各对比实验中，提出的IMA与各基准算法相比，覆盖质量最高，分别比MA，ACA和GGA平均提高8%，14%和20%.IMA和MA表现较好，是因为它们结合了遗传算法全局寻优和模拟退火算法局部寻优的优势.IMA更是在MA的基础上，采用自适应遗传算法，进一步加快了收敛速度，这样有更多的机会留给模拟退火进行局部寻优，并且，设计了GRA对不合适的个体进行修复，充分利用了任务预算.ACA表现次优是因为其具有正反馈的特点，若一开始就寻到次优解，正反馈会快速占据优势，降低了种群的多样性，使算法陷入局部最优.GGA表现最差，虽然其迭代开始时使用贪心算法能获得一个较优的解，但随着迭代的进行，遗传算法陷入局部最优的缺陷越来越明显且难以跳出.

结合图5的迭代曲线对进行印证.由图可见，GGA的第一次迭代就有很高的覆盖质量，但迭代几十次后，覆盖质量没有变化，显然陷入了局部最优，最后的覆盖质量最低.ACA在迭代前期，寻优慢于遗传算法，但随着迭代的进行，正反馈的作用越来越大，整体表现较稳定.IMA和MA在迭代中后期多次实现跳跃，有效跳出了局部最优，找到了更优解.而且，IMA因为利用GRA进行个体修复，比MA更容易找到覆盖质量高的个体.

4.3.2　运行耗时的分析

分析报名人数对算法运行耗时的影响，图9展示了各算法在Taxis和T⁃Drive数据集上，预算为500元和任务规模为 $3 \times 4$ 时，各算法运行十次耗时的平均值，即为不同报名人数对应的运行耗时.

图9

图9 Taxis (a)和T⁃Drive (b)数据集中各算法在不同报名人数时的运行耗时

Fig.9 Running time with different enrollments on Taxis (a) and T⁃Drive (b) datasets

由图可见，报名人数的增多会不同程度地增加各算法的运行耗时，其中，IMA耗时稍长于MA，短于GGA，远短于ACA.因为IMA在每次运行迭代250次中，只有前一部分进行遗传迭代，陷入局部最优后，则进行模拟退火的迭代，比全部进行遗传迭代的GGA耗时更短.但IMA与MA相比，耗时多在贪心修复算法上，因为需要对不可行个体进行修复来找到更优解.ACA在处理组合优化问题时，运算量受候选解在问题空间分布的影响，分布越均匀，种群多样性越好，得到全局最优解的概率越大，但相应的寻优时间也越长.

综上，提出的IMA在获得最高覆盖质量的前提下，运行耗时相对较低，平均比MA多9%，比GGA和ACA省时29%.

5 结论

针对长时多任务分配问题，本文设计了多轮次多时间段的任务分解策略；其次，考虑任务权重、时间覆盖率、时间冗余度和冗余均衡度等因素，构建了长时任务质量评价模型；最后，提出基于改进文化基因算法的任务分配方法，在预算约束下实现最大化任务覆盖质量的优化目标.仿真实验的结果表明，与基准算法相比，提出的方法在具有竞争力的运行时间内覆盖质量平均提升14%.

未来将研究不同的全局寻优算法和局部寻优算法以及三种及以上的算法的融合与改进，提升寻优效率.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

刘云浩

群智感知计算

中国计算机学会通讯，2012，8(10)：38-41.

Liu

Y H

Crowd sensing and computing

Communications of the CCF，2012，8(10)：38-41.

[2]

Capponi

， Fiandrino

， Kantarci

，et al.

A survey on mobile crowdsensing systems：Challenges，solutions，and opportunities

IEEE Communications Surveys & Tutorials，2019，21(3)：2419-2465.

[3]

Kang

， Liu

， Ma

H D

Enhance the quality of crowdsensing for fine⁃grained urban environment monitoring via data correlation

Sensors，2017，17(1)：88.

[4]

Ali

， Ayub

， Shiraz

，et al.

Traffic efficiency models for urban traffic management using mobile crowd sensing：Aa survey

Sustainability，2021，13(23)：13068.

[5]

Tian

B Q

， Yuan

Y B

， Zhou

H Y

，et al.

Pavement management utilizing mobile crowd sensing

Advances in Civil Engineering，2020(2020)：4192602.

[6]

Arcas⁃Tunez

， Terroso⁃Saenz

Forest path condition monitoring based on crowd⁃based trajectory data analysis

Journal of Ambient Intelligence and Smart Environments，2021，13(1)：37-54.

[7]

Liu

， Cen

， Hu

H Z

，et al.

A radio map self⁃updating algorithm based on mobile crowd sensing

Journal of Network and Computer Applications，2021(194)：103225.

[8]

， Wang

Z X

， He

，et al.

Know where you are：A practical privacy⁃preserving semi⁃supervised indoor positioning via edge⁃crowdsensing

IEEE Transactions on Network and Service Management，2021，18(4)：4875-4887.

[9]

Wang

J T

， Wang

L Y

， Wang

Y S

，et al.

Task allocation in mobile crowd sensing：State⁃of⁃the⁃art and future opportunities

IEEE Internet of Things Journal，2018，5(5)：3747-3757.

[10]

J J

， Guo

Y N

， Gong

D W

，et al.

MOEA/D⁃based participant selection method for crowdsensing with social awareness

Applied Soft Computing，2020(87)：105981.

[11]

李卓，徐哲，陈昕，等.

面向移动群智感知的位置相关在线多任务分配算法

计算机科学，2019，46(6)：102-106.

， Xu

， Chen

，et al.

Location⁃related online multi⁃task assignment algorithm for mobile crowd sensing

Computer Science，2019，46(6)：102-106.

[12]

Guo

， Liu

， Wu

W L

，et al.

Activecrowd：A framework for optimized multitask allocation in mobile crowdsensing systems

IEEE Transactions on Human⁃Machine Systems，2017，47(3)：392-403.

[13]

Lai

， Zhang

X L

Duration⁃sensitive task allocation for mobile crowd sensing

IEEE Systems Journal，2020. 14(3)：4430-4441.

[14]

Wang

Y N

， Sun

G D

， Ding

X J

Coverage⁃balancing user selection in mobile crowd sensing with budget constraint

Sensors，2019，19(10)：2371.

[15]

Mondal

， Mitra

， Mukherjee

，et al.

Participant selection algorithms for large⁃scale mobile crowd sensing environment

Microsystem Technologies，2022，28(12)：2641-2657.

[16]

Yang

G S

， Wang

B Y

， He

X Y

，et al.

Competition⁃congestion⁃aware stable worker⁃task matching in mobile crowd sensing

IEEE Transactions on Network and Service Management，2021，18(3)：3719-3732.

[17]

周杰，於志勇，郭文忠，等.“

t⁃时隙k⁃覆盖”群智感知任务的参与者选择方法

计算机科学，2018，45(2)：157-164，196.

Zhou

， Yu

Z Y

， Guo

W Z

，et al.

Participant selection algorithm for t⁃sweep k⁃coverage crowd sensing tasks

Computer Science，2018，45(2)：157-164，196.

[18]

Jiang

W J

， Chen

J P

， Liu

X L

，et al.

Participant recruitment method aiming at service quality in mobile crowd sensing

Wireless Communications and Mobile Computing，2021(2021)：6621659.

[19]

J J

， Guo

Y N

， Gong

D W

，et al.

Evolutionary multi⁃task allocation for mobile crowdsensing with limited resource

Swarm and Evolutionary Computation，2021(63)：100872.

[20]

李晓东，於志勇，黄昉菀,等.

面向河道环境监测的群智感知参与者选择策略

计算机科学，2022，49(5)：371-379.

X D

， Yu

Z Y

， Huang

F W

，et al.

Participant selection strategies based on crowd sensing for river environmental monitoring

Computer Science，2022，49(5)：371-379.

[21]

Estrada

， Valeriano

， Torres

Multi⁃task versus consecutive task allocation with tasks clustering for Mobile Crowd Sensing Systems

Procedia Computer Science，2022，19(8)：67-76.

[22]

Huang

， Chen

H L

， Ma

G Q

，et al.

OPAT：Optimized allocation of time⁃dependent tasks for mobile crowdsensing

IEEE Transactions on Industrial Informatics，2022，18(4)：2476-2485.

[23]

， Zhang

X L

Multi⁃task allocation under time constraints in mobile crowdsensing

IEEE Transactions on Mobile Computing，2021，20(4)：1494-1510.

[24]

Yuan

， Zheng

， Xie

，et al.

Driving with knowledge from the physical world

∥Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego，CA，USA：ACM，2011：316-324.