考虑社交协作的移动群智感知生殖分工蚁群任务分配

申晓宁; 佘娟; 王智龙; 李嘉渊

doi:10.11999/JEIT260018

考虑社交协作的移动群智感知生殖分工蚁群任务分配

doi: 10.11999/JEIT260018 cstr: 32379.14.JEIT260018

申晓宁^{1, 2, 3, 4},
佘娟^1, ,,
王智龙¹,
李嘉渊¹

1.
南京信息工程大学自动化学院南京 210044
2.
江苏省大数据分析技术重点实验室南京 210044
3.
江苏省气象能源利用与控制工程技术研究中心南京 210044
4.
江苏省大气环境与装备技术协同创新中心南京 210044

基金项目: 国家自然科学基金 (61502239)，江苏省自然科学基金 (BK20150924)

详细信息

作者简介:
申晓宁：女，教授，研究方向为强化学习，多目标优化，演化计算及其应用

佘娟：女，硕士生，研究方向为群体智能优化算法及其应用

王智龙：男，硕士生，研究方向为进化算法、演化计算及其应用

李嘉渊：男，硕士生，研究方向为深度强化学习、演化计算及其应用

通讯作者:
佘娟　2249691859@qq.com

中图分类号: TP18
计量
- 文章访问数: 48
- HTML全文浏览量: 22
- PDF下载量: 5
- 被引次数: 0
出版历程
- 收稿日期: 2026-01-06
- 修回日期: 2026-05-05
- 录用日期: 2026-05-12
- 网络出版日期: 2026-06-02

A Social-Aware Ant Colony Optimization Algorithm with Reproductive Division of Labor for MCS Task Allocation

SHEN Xiaoning^{1, 2, 3, 4},
SHE Juan^{1
, ,},
WANG Zhilong¹,
LI Jiayuan¹

1.
School of Automation, Nanjing University of Information Science & Technology, Nanjing 210044, China
2.
Jiangsu Provincial Key Laboratory of Big Data Analysis Technology, Nanjing 210044, China
3.
Jiangsu Engineering Research Center of Meteorological Energy Utilization and Control, Nanjing 210044, China
4.
Jiangsu Collaborative Innovation Center of Atmospheric Environment and Equipment Technology, Nanjing 210044, China

Funds: The National Natural Science Foundation of China (61502239), The Natural Science Foundation of Jiangsu Province (BK20150924)

摘要

摘要: 该文针对移动群智感知(MCS)系统复杂任务的协作需求，建立了一种融合社交协作关系的任务分配优化模型，不仅考虑平台参与者间的协作，还将社交网络作为辅助执行资源，构建了“平台参与者–社交好友”双层协作框架。该文提出基于生殖分工的多目标蚁群优化算法，根据社会分工将蚁群划分为4个协作子种群；基于统计学习选择交配对象以强化精英基因的交流；采用多策略混合搜索以提高探索的多样性与深度；引入贡献度预测自适应配置种群资源。在8个合成和4个真实算例上的对比实验表明，所提算法在收敛性与多样性测度上，比第2优算法平均提升16.41%和18.04%，上述结果验证了所提算法在解决复杂MCS任务分配问题上的精度优势与应用价值。
- 移动群智感知 /
- 任务分配 /
- 社交协作 /
- 蚁群算法 /
- 生殖分工
Abstract: Objective With the rapid development of handheld and wearable smart devices, Mobile Crowd Sensing (MCS) has become an efficient data collection paradigm. Effective task allocation can improve system efficiency, requester and participant satisfaction, and platform sustainability. Existing models often neglect task skill requirements, do not use participants’ social networks as auxiliary execution resources in emergencies, and overlook the effect of collaboration efficiency on team-task quality. To address these issues, this paper proposes a Social-Aware MCS Task Allocation model (SAMCSTA) with two objectives: maximizing total platform revenue and total task sensing quality. Social networks are used to build a two-layer collaboration framework of platform participants and social-network friends, which expands available execution resources and improves allocation flexibility. For complex tasks, participant sensing capability is quantified, and collaboration efficiency is introduced to optimize team composition. Methods This paper proposes a Multi-objective Ant Colony Optimization based on Reproductive Division of Labor (MACORDL) algorithm. The main innovations are as follows. First, the ant colony is divided into four collaborative subpopulations: queen ants, male ants, scout ants, and worker ants. Local enhancement, memetic crossover, knowledge transfer, and other search strategies are designed for these subpopulations to form a hierarchical collaborative search framework. Second, a statistical-learning-based mating selection strategy is designed to support intelligent transfer of elite genes. Third, the short-term contribution of each subpopulation is predicted from historical performance, which enables dynamic and adaptive allocation of computational resources. Fourth, a cooperative update mechanism for node pheromones and participant pheromones is designed to establish a dual-layer search guidance system. Results and Discussions The evaluation uses 8 synthetic instances and 4 real-world instances. Performance is measured by HyperVolume Ratio (HVR) and Inverted Generational Distance (IGD). The Wilcoxon rank-sum test at a significance level of 0.05 is used for statistical comparison. The results show that MACORDL achieves the best HVR and IGD on most instances (Table 2, Table 3). On average, MACORDL improves HVR and IGD by 16.41% and 18.04%, respectively, compared with the second-best algorithm. Visual comparisons further show that the Pareto front obtained by MACORDL has better convergence, distribution uniformity, and breadth (Fig. 4). Although its fine-grained local search can still be improved for a few large-scale instances, MACORDL shows stable performance and good scalability across different problem scales. It helps the platform obtain task allocation schemes with higher revenue and better sensing quality. Conclusions This paper studies the task allocation problem in MCS systems by considering interactions among platform participants and between participants and their social-network friends. A social-aware MCS task allocation model is established, and MACORDL is proposed to solve it. Comparative experiments on 8 synthetic instances and 4 real-world instances with different scales show that MACORDL outperforms six representative algorithms on most instances. It obtains allocation schemes and paths that yield higher total platform revenue and better task sensing quality, indicating good scalability. MACORDL uses multiple strategies to balance local exploitation and global exploration. However, the current model assumes that all tasks are released at the initial stage and that complete information is available. Participant privacy protection is also not considered. Future work will focus on MCS task allocation models in dynamic and uncertain environments and on privacy-preserving distributed optimization.
- Mobile Crowd Sensing (MCS) /
- Task allocation /
- Social collaboration /
- Ant colony optimization /
- Reproductive division of labor

HTML全文

图 1 MACORDL算法框架

下载: 全尺寸图片幻灯片

图 2 个体编码示例

下载: 全尺寸图片幻灯片

图 3 个体解码示例

下载: 全尺寸图片幻灯片

图 4 4.3节和4.4节不同算法在实例Real-20/74/40中的Pareto前沿对比

下载: 全尺寸图片幻灯片

表 1 Real-20/74/40算例上不同参数对比结果

组别	参数		结果	组别	参数		结果
组别	$ ({\tau }_{\text{min}},{\tau }_{\text{max}}) $	$ \rho $	S/N	组别	$ ({\tau }_{\text{min}},{\tau }_{\text{max}}) $	$ \rho $	S/N
1	(5, 50)	0.5	–4.5962	9	(15, 150)	0.5	–4.5301
2	(5, 50)	0.6	–2.0156	10	(15, 150)	0.6	–1.4824
3	(5, 50)	0.7	–2.8703	11	(15, 150)	0.7	–2.5685
4	(5, 50)	0.8	–1.2667	12	(15, 150)	0.8	–3.6354
5	(10, 100)	0.5	–1.8292	13	(20, 200)	0.5	–2.4930
6	(10, 100)	0.6	–1.4618	14	(20, 200)	0.6	–2.1548
7	(10, 100)	0.7	–2.2117	15	(20, 200)	0.7	–2.8160
8	(10, 100)	0.8	–3.5436	16	(20, 200)	0.8	–3.1279

下载: 导出CSV

表 2 所提算法和替换单一策略算法的对比结果

测试算例	MACORDL		GP1		GP2		IS1
测试算例	HVR	IGD	HVR	IGD	HVR	IGD	HVR	IGD
Syn-10/35/20	0.7468	0.2033	0.5890+	0.2077=	0.6880+	0.2178=	0.5949+	0.2142=
Syn-10/35/25	0.7767	0.0712	0.5788+	0.1888+	0.4647+	0.2371+	0.6548+	0.1296+
Syn-15/62/25	0.6542	0.1025	0.5493+	0.1445+	0.4594+	0.2376+	0.6004=	0.1165=
Syn-15/62/30	0.7308	0.0869	0.5588+	0.1746+	0.4852+	0.1810+	0.6348+	0.1135+
Syn-15/62/35	0.7612	0.0970	0.5424+	0.2367+	0.5430+	0.1909+	0.5529+	0.1795+
Syn-25/94/35	0.6030	0.1724	0.5760+	0.2381+	0.4919+	0.3456+	0.6342=	0.1705=
Syn-25/94/40	0.6190	0.1528	0.4946+	0.2445+	0.4258+	0.2613+	0.5374+	0.2035+
Syn-25/94/45	0.6883	0.1073	0.5334+	0.2957+	0.5500+	0.1630+	0.5272+	0.2320+
Real-10/35/15	0.8448	0.0392	0.7961+	0.0521=	0.7214+	0.1344+	0.8269=	0.0503=
Real-20/74/40	0.6977	0.0759	0.5059+	0.1900+	0.4867+	0.1959+	0.5825+	0.1123+
Real-30/113/50	0.7010	0.0991	0.5420+	0.2820+	0.4783+	0.1684+	0.5737+	0.1765+
Real-35/140/60	0.6389	0.1032	0.5132=	0.0919=	0.5319=	0.0825-	0.5070+	0.1587+
+/-/=			11/0/1	9/0/3	11/0/1	10/1/1	9/0/3	8/0/4
测试算例	IS2		PS1		PS2
测试算例	HVR	IGD	HVR	IGD	HVR	IGD
Syn-10/35/20	0.6338+	0.2068=	0.5709+	0.2032=	0.6059+	0.2077=
Syn-10/35/25	0.6699+	0.1263+	0.5925+	0.1516+	0.6083+	0.1888+
Syn-15/62/25	0.6443=	0.1156=	0.6063=	0.1161=	0.6377=	0.1445+
Syn-15/62/30	0.6711+	0.0988=	0.6320+	0.1189+	0.6464+	0.1746+
Syn-15/62/35	0.5729+	0.1675+	0.5239+	0.1926+	0.5210+	0.2367+
Syn-25/94/35	0.6238=	0.1515=	0.5854=	0.1852=	0.6087=	0.2381+
Syn-25/94/40	0.5595=	0.1896+	0.4959+	0.2430+	0.5554+	0.2445+
Syn-25/94/45	0.5338+	0.2063+	0.5141+	0.2366+	0.5037+	0.2957+
Real-10/35/15	0.8207=	0.0460=	0.7903+	0.0610+	0.7964+	0.0521=
Real-20/74/40	0.5449+	0.1174+	0.5177+	0.1364+	0.5350+	0.1900+
Real-30/113/50	0.5441+	0.1666+	0.5460+	0.1725+	0.5249+	0.2820+
Real-35/140/60	0.5121+	0.1392+	0.5218+	0.1605+	0.5845+	0.0919=
+/-/=	8/0/4	7/0/5	10/0/2	9/0/3	10/0/2	9/0/3

下载: 导出CSV

表 3 MACORDL算法与6种代表性算法的实验结果

测试算例	MACORDL		GGA		dCMaOEA-E-P		BPGA
测试算例	HVR	IGD	HVR	IGD	HVR	IGD	HVR	IGD
Syn-10/35/20	0.7468	0.2033	0.6156+	0.2107=	0.4860+	0.2272=	0.3156+	0.2768+
Syn-10/35/25	0.7767	0.0712	0.6263+	0.1292+	0.6960+	0.0935=	0.3483+	0.2874+
Syn-15/62/25	0.6542	0.1025	0.4350+	0.1857+	0.4504+	0.1753+	0.3315+	0.3479+
Syn-15/62/30	0.7308	0.0869	0.6628+	0.1054+	0.7164=	0.0897=	0.2601+	0.3892+
Syn-15/62/35	0.7612	0.0970	0.3690+	0.3201+	0.6463+	0.1257+	0.3863+	0.3011+
Syn-25/94/35	0.6030	0.1724	0.5711+	0.1728=	0.5564=	0.1996+	0.2555+	0.3127+
Syn-25/94/40	0.6190	0.1528	0.4973=	0.2293+	0.4349+	0.1850=	0.3221+	0.3275+
Syn-25/94/45	0.6883	0.1073	0.4250+	0.2571+	0.4870+	0.1653+	0.2909+	0.3042+
Real-10/35/15	0.8448	0.0392	0.7709+	0.0610+	0.7645+	0.0659+	0.4595+	0.2097+
Real-20/74/40	0.6977	0.0759	0.5413+	0.1298+	0.6534=	0.0797=	0.3267+	0.2126+
Real-30/113/50	0.7010	0.0991	0.5892+	0.1851+	0.5798+	0.1268+	0.4223+	0.3385+
Real-35/140/60	0.6389	0.1032	0.5198+	0.1814+	0.5455+	0.1009=	0.2957+	0.3255+
+/-/=			11/0/1	10/0/2	9/0/3	6/0/6	12/0/0	12/0/0
测试算例	CCFO		MaaCO		HWACOA
测试算例	HVR	IGD	HVR	IGD	HVR	IGD
Syn-10/35/20	0.3905+	0.2907+	0.5564+	0.2565=	0.4884+	0.3909+
Syn-10/35/25	0.3725+	0.2768+	0.5610+	0.1609+	0.4151+	0.3307+
Syn-15/62/25	0.3793+	0.3203+	0.5396+	0.2245+	0.3362+	0.3910+
Syn-15/62/30	0.2308+	0.4313+	0.4219+	0.2353+	0.3785+	0.3802+
Syn-15/62/35	0.4571+	0.2720+	0.3724+	0.3097+	0.5196+	0.2498+
Syn-25/94/35	0.2988+	0.3781+	0.3566+	0.3425+	0.3566+	0.3274+
Syn-25/94/40	0.3637+	0.3003+	0.3026+	0.3673+	0.3286+	0.3401+
Syn-25/94/45	0.3041+	0.3316+	0.3805+	0.3093+	0.3437+	0.2953+
Real-10/35/15	0.4369+	0.2528+	0.7771+	0.0591+	0.6844+	0.0768+
Real-20/74/40	0.3886+	0.3525+	0.3891+	0.2000+	0.3411+	0.2976+
Real-30/113/50	0.4548+	0.3792+	0.4307+	0.1009=	0.4919+	0.3008+
Real-35/140/60	0.2714+	0.3019+	0.3499+	0.2894+	0.3398+	0.3272+
+/-/=	12/0/0	12/0/0	12/0/0	10/0/2	12/0/0	12/0/0

下载: 导出CSV

参考文献(22)

[1]	ZHANG Xian, QIN Xiaolin, XU Haiwen, et al. PPHMA: Privacy-preserving hybrid multi-task allocation for mobile crowd sensing[J]. IEEE Transactions on Network Science and Engineering, 2025, 12(4): 3360–3373. doi: 10.1109/TNSE.2025.3559563.
[2]	GANTI R K, YE Fan, and LEI Hui. Mobile crowdsensing: Current state and future challenges[J]. IEEE Communications Magazine, 2011, 49(11): 32–39. doi: 10.1109/MCOM.2011.6069707.
[3]	V S and RAMACHANDRAN S. Hybrid optimized task scheduling with multi-objective framework for crowd sensing in mobile social networks[J]. Peer-to-Peer Networking and Applications, 2024, 17(2): 722–738. doi: 10.1007/s12083-023-01608-4.
[4]	SHEN Xiaoning, XU Di, SONG Liyan, et al. Heterogeneous multi-project multi-task allocation in mobile crowdsensing using an ensemble fireworks algorithm[J]. Applied Soft Computing, 2023, 145: 110571. doi: 10.1016/j.asoc.2023.110571.
[5]	WU Xiangling, MA Wenming, ZHU Xiao, et al. A Pareto-based genetic algorithm for online task allocation in mobile crowdsensing[J]. Computer Communications, 2025, 241: 108269. doi: 10.1016/j.comcom.2025.108269.
[6]	YANG Guisong, SANG Jian, LI Hanqing, et al. Efficient group collaboration for sensing time redundancy optimization in mobile crowdsensing[J]. IEEE Internet of Things Journal, 2024, 11(15): 26091–26103. doi: 10.1109/JIOT.2024.3393532.
[7]	DORIGO M. DORIGO M. Optimization, learning and natural algorithms[D]. [Ph. D. dissertation], Politecnico Di Milano, 1992.
[8]	HUANG Ting, ZHANG Zhenquan, GONG Yuejiao, et al. nLKH-ACS: A niching Lin-Kernighan-Helsgaun-based ant colony system for multisolution traveling salesman problems[J]. IEEE Transactions on Evolutionary Computation, 2025, 29(6): 2596–2610. doi: 10.1109/TEVC.2024.3507777.
[9]	唐伦, 周钰, 杨友超, 等. 5G网络切片场景中基于预测的虚拟网络功能动态部署算法[J]. 电子与信息学报, 2019, 41(9): 2071–2078. doi: 10.11999/JEIT180894. TANG Lun, ZHOU Yu, YANG Youchao, et al. Virtual network function dynamic deployment algorithm based on prediction for 5G network slicing[J]. Journal of Electronics & Information Technology, 2019, 41(9): 2071–2078. doi: 10.11999/JEIT180894.
[10]	LIU Yuting, GUO Shijie, TANG Shufeng, et al. Path planning for robots based on adaptive dual-layer ant colony optimization algorithm and adaptive dynamic window approach[J]. IEEE Sensors Journal, 2025, 25(11): 19694–19708. doi: 10.1109/JSEN.2025.3557437.
[11]	ZOU Hong, WANG Hongli, CUI Yaping, et al. Worker selection towards high service quality in mobile crowd sensing[C]. 2022 IEEE 96th Vehicular Technology Conference (VTC2022-Fall), London, United Kingdom, 2022: 1–5. doi: 10.1109/VTC2022-Fall57202.2022.10012834.
[12]	JI Jianjiao, GUO Yinan, GONG Dunwei, et al. Evolutionary multi-task allocation for mobile crowdsensing with limited resource[J]. Swarm and Evolutionary Computation, 2021, 63: 100872. doi: 10.1016/j.swevo.2021.100872.
[13]	殷礼胜, 唐圣期, 李胜, 等. 基于整合移动平均自回归和遗传粒子群优化小波神经网络组合模型的交通流预测[J]. 电子与信息学报, 2019, 41(9): 2273–2279. doi: 10.11999/JEIT181073. YIN Lisheng, TANG Shengqi, LI Sheng, et al. Traffic flow prediction based on hybrid model of auto-regressive integrated moving average and genetic particle swarm optimization wavelet neural network[J]. Journal of Electronics & Information Technology, 2019, 41(9): 2273–2279. doi: 10.11999/JEIT181073.
[14]	BLONDEL V D, ESCH M, CHAN C, et al. Data for development: The D4D challenge on mobile phone data[J]. arXiv preprint arXiv: 1210.0137, 2012. doi: 10.48550/arXiv.1210.0137.
[15]	申晓宁, 施江熠, 马燕昭, 等. 考虑工作量不确定性的软件项目策略梯度超启发式调度[J]. 电子与信息学报, 2026, 48(2): 794–805. doi: 10.11999/JEIT250769. SHEN Xiaoning, SHI Jiangyi, MA Yanzhao, et al. Considering workload uncertainty in strategy gradient-based hyper-heuristic scheduling for software projects[J]. Journal of Electronics & Information Technology, 2026, 48(2): 794–805. doi: 10.11999/JEIT250769.
[16]	MACHAČEK J, SIEGEL S, and ZACHERT H. DEEM—differential evolution with elitism and multi-populations[J]. Swarm and Evolutionary Computation, 2025, 92: 101818. doi: 10.1016/j.swevo.2024.101818.
[17]	XU Liping, ZHOU Tao, LI Kai, et al. Q-learning-driven multi-population cooperative evolutionary algorithm with local search for scheduling of network-shared manufacturing resources[J]. Computers & Operations Research, 2025, 180: 107076. doi: 10.1016/j.cor.2025.107076.
[18]	ZHAO Tianhao, WU Linjie, CUI Zhihua, et al. An adaptive strategy based multi-population multi-objective optimization algorithm[J]. Information Sciences, 2025, 686: 120913. doi: 10.1016/j.ins.2024.120913.
[19]	LI Zhetao, TAN Zhihui, LONG Saiqin, et al. A novel coverage-aware task allocation scheme in cooperative mobile crowd sensing[J]. Ad Hoc Networks, 2023, 151: 103297. doi: 10.1016/j.adhoc.2023.103297.
[20]	CAI Xingjuan, JI Chen, and ZHAO Tianhao. A constrained many-objective mobile crowdsensing task allocation method considering latent workers[J]. IEEE Internet of Things Journal, 2025, 12(4): 4065–4077. doi: 10.1109/JIOT.2024.3481637.
[21]	KHALEEL M I, SAFRAN M, ALFARHOOD S, et al. Combinatorial metaheuristic methods to optimize the scheduling of scientific workflows in green DVFS-enabled edge-cloud computing[J]. Alexandria Engineering Journal, 2024, 86: 458–470. doi: 10.1016/j.aej.2023.11.074.
[22]	CHANDRASHEKAR C, KRISHNADOSS P, KEDALU POORNACHARY V, et al. HWACOA scheduler: Hybrid weighted ant colony optimization algorithm for task scheduling in cloud computing[J]. Applied Sciences, 2023, 13(6): 3433. doi: 10.3390/app13063433.