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

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

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
计量
- 文章访问数: 21
- HTML全文浏览量: 7
- PDF下载量: 1
- 被引次数: 0
出版历程
- 收稿日期: 2026-01-06
- 修回日期: 2026-05-05
- 录用日期: 2026-05-12
- 网络出版日期: 2026-06-02

A Social-Aware Ant Colony Optimization 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: Supported by the National Natural Science Foundation of China (61502239), Supported by the Natural Science Foundation of Jiangsu Province, China (No.BK20150924)

摘要

摘要: 针对MCS系统复杂任务的协作需求，建立了一种融合社交协作关系的任务分配优化模型，不仅考虑平台参与者间的协作，还将社交网络作为辅助执行资源，构建“平台参与者–社交好友”双层协作框架。提出基于生殖分工的多目标蚁群优化算法，根据社会分工将蚁群划分为四个协作子种群；基于统计学习选择交配对象以强化精英基因的交流；采用多策略混合搜索以提高探索的多样性与深度；引入贡献度预测自适应配置种群资源。在8个合成和4个真实算例上的对比实验表明，所提算法在收敛性与多样性测度上，比第二优算法平均提升16.41%和18.04%，上述结果验证了所提算法在解决复杂MCS任务分配问题上的精度优势与应用价值。
- 移动群智感知 /
- 任务分配 /
- 社交协作 /
- 蚁群算法 /
- 生殖分工
Abstract: Objective With the rise of handheld/wearable smart devices, Mobile Crowd Sensing (MCS) has become an efficient data collection paradigm. Effective task allocation improves system efficiency, requester/participant satisfaction, and platform sustainability. Existing models overlook task skill requirements, fail to leverage participants' social networks for emergencies, and ignore collaboration efficiency in team tasks. To address this, we propose a Social-Aware MCS Task Allocation Model (SAMCSTA) with dual objectives: maximizing platform total revenue and overall task perceived quality. The model incorporates social networks to build a two-tier collaboration framework, expanding resources and enhancing flexibility. For complex tasks, it quantifies individual capabilities and introduces a collaboration efficiency mechanism to optimize team composition. Methods This paper proposes a Multi-objective Ant Colony Optimization Based on Reproductive Division of Labor (MACORDL). The core innovations of the algorithm include: (1) Constructing four subpopulations—queen ants, male ants, scout ants, and worker ants—each equipped with distinct strategies such as local enhancement, memetic crossover, and knowledge transfer, forming a hierarchical collaborative search framework; (2) A mating selection strategy based on statistical learning is designed to enable the intelligent transfer of elite genes; (3) The short-term contribution of each subpopulation is predicted based on its historical performance, allowing for dynamic and adaptive allocation of computational resources; (4) Designing a cooperative update mechanism for node pheromones and participant pheromones, establishing a dual-layer search guidance system. Results and Discussions The evaluation uses 8 synthetic and 4 real-world instances, with performance measured by Hypervolume Ratio (HVR) and Inverted Generational Distance (IGD). The Wilcoxon rank-sum test (significance 0.05) is employed for statistical comparison. Results show that MACORDL achieves the best HVR and IGD on most instances (Table 2, Table 3). On average, it outperforms the second-best algorithm by 16.41% in HVR and 18.04% in IGD. Visual comparisons confirm that the Pareto front by MACORDL is superior in convergence, distribution uniformity, and breadth (Fig 4). Though slight improvement remains in fine-grained search on a few large-scale cases, MACORDL demonstrates stable performance and scalability across different scales, enabling the platform to obtain task allocation solutions with higher revenue and better perceived quality. Conclusions This paper addresses the task allocation problem in MCS systems, taking into account both interactions among platform participants and those between participants and their social connections. A social-aware MCS task allocation model is established. The MACORDL algorithm is proposed to solve it. Comparative experiments on 12 real and synthetic instances of varying scales show that MACORDL significantly outperforms six representative algorithms on most instances, obtaining allocation schemes and paths that yield higher revenue and better perceived quality, demonstrating good scalability. MACORDL incorporates multiple strategies to balance local exploitation and global exploration. However, limitations include assumption that all tasks are released at the start with full information, and the lack of participant privacy protection. Future work will focus on dynamic/uncertain MCS task allocation models and privacy-preserving distributed optimization.
- Mobile Crowd Sensing /
- 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算法与六种代表性算法的实验结果

测试算例	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]. Proceedings of 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.