基于改进AGD-分布式多智能体系统的目标优化分配模型

doi:10.3969/j.issn.1001-506X.2020.04.17

系统工程与电子技术 ›› 2020, Vol. 42 ›› Issue (4): 863-870.doi: 10.3969/j.issn.1001-506X.2020.04.17

基于改进AGD-分布式多智能体系统的目标优化分配模型

刘家义^1,²(), 王刚¹(), 张杰^1,²(), 王闯^1,²(), 宋喜团³()

1. 空军工程大学防空反导学院, 陕西西安 710051
2. 空军工程大学研究生院, 陕西西安 710051
3. 中国人民解放军93453部队, 山西朔州 038300

收稿日期:2019-09-11 出版日期:2020-03-28 发布日期:2020-03-28
作者简介:刘家义(1996-),男,硕士研究生,主要研究方向为防空反导指挥控制系统、基于强化学习的智能决策。E-mail:sixandone1@163.com|王刚(1975-),男,教授,博士,主要研究方向为机器学习、信息融合、指挥控制系统。E-mail:sharesunny123@163.com|张杰(1995-),男,硕士研究生,主要研究方向为基于强化学习的作战多智能体研究、战术级防空反导指挥控制系统研究。E-mail:afeu_zhangjie@163.com|王闯(1995-),男,硕士研究生,主要研究方向为战场态势估计。E-mail:2956962496@qq.com|宋喜团(1981-),男,工程师,硕士,主要研究方向为电子对抗。E-mail:435425270@qq.com
基金资助:
国家自然科学基金青年科学基金项目(61703412);中国博士后科学基金资助(2016M602996)

Target optimal assignment model based on improved AGD-distributed multi-Agent system

Jiayi LIU^1,²(), Gang WANG¹(), Jie ZHANG^1,²(), Chuang WANG^1,²(), Xituan SONG³()

1. Air and Missile Defense College, Air Force Engineering University, Xi'an 710051, China
2. Graduate College, Air Force Engineering University, Xi'an 710051, China
3. 3 Unit 93453 of the PLA, Shuozhou 038300, China

Received:2019-09-11 Online:2020-03-28 Published:2020-03-28
Supported by:
国家自然科学基金青年科学基金项目(61703412);中国博士后科学基金资助(2016M602996)

摘要/Abstract

摘要：

由于现代化战场环境动态多变、作战实时性高,针对当前防空作战中武器目标分配(weapon target assignment, WTA)约束多且复杂、传统建模无法真实反映战争过程、模型可信度不高等问题,提出一种在分布式约束优化问题(distributed constraint optimization problem, DCOP)背景下,基于多智能体系统(multi-Agent system, MAS)理论的武器目标优化分配模型,并利用改进的加速梯度下降(accelerated gradient descent, AGD)算法进行求解。通过实验证明了该算法具有良好的收敛性和低复杂度,能够适应现代化防空作战的需求,满足大规模寻优问题的需求,高效解决多智能体目标优化分配问题。

关键词: 多智能体系统, 分布式约束优化问题, 武器目标分配, 加速梯度下降

Abstract:

Because the modern battlefield environment is dynamic and the tasks are fulfilled in real-time, in view of the fact that the target allocation of weapons targets in current air defense operations is complex, traditional modeling cannot truly reflect the war process, with low confidence in the model, a weapon target assignment (WTA) model based on multi-Agent system (MAS) theory and distributed constrained optimization problem (DCOP) is proposed, and the improved accelerated gradient descent (AGD) algorithm is used to solve the model. The experiment proves that the algorithm has good convergence and low complexity, can adapt to the needs of modern air defense operations, meet the needs of large-scale optimization problems, and efficiently solve the problem of optimal allocation of multi-Agent targets.

Key words: multi-Agent system (MAS), distributed constraint optimization problem (DCOP), weapon target assignment (WTA), accelerated gradient descent (AGD)

中图分类号:

TP391.9

刘家义, 王刚, 张杰, 王闯, 宋喜团. 基于改进AGD-分布式多智能体系统的目标优化分配模型[J]. 系统工程与电子技术, 2020, 42(4): 863-870.

Jiayi LIU, Gang WANG, Jie ZHANG, Chuang WANG, Xituan SONG. Target optimal assignment model based on improved AGD-distributed multi-Agent system[J]. Systems Engineering and Electronics, 2020, 42(4): 863-870.

图/表 12

图1

图2

图3

图4

图5

表1

表2

表3

图6

图7

表4

表5

参考文献 24

1	娄寿春. 地空导弹射击指挥控制模型[M]. 北京: 国防工业出版社, 2009.
	LOU S C . Ground-to-air missile firing command and control model[M]. Beijing: National Defense Industry Press, 2009.
2	LLOYD S P, WITSENHAUSEN H S.Weapons allocation is NP-complete[C]//Proc.of the IEEE Summer Conference on Simulation, 1986: 1054-1058.
3	韦刚, 高嘉乐, 孙文. 多目标-多武器系统目标分配模型与算法研究[J]. 飞航导弹, 2016, 5, 77- 82.
	WEI G , GAO J L , SUN W . Research on target assignment model and algorithm for multi-target-multi-weapon system[J]. Aerodynamic Missile Journal, 2016, 5, 77- 82.
4	郭张龙, 李为民, 王刚. 基于遗传算法的目标分配问题研究[J]. 现代防御技术, 2002, 30 (6): 3- 7. doi: 10.3969/j.issn.1009-086X.2002.06.002
	GUO Z L , LI W M , WANG G . The target allocation problem based on genetic algorithm[J]. Modern Defense Technology, 2002, 30 (6): 3- 7. doi: 10.3969/j.issn.1009-086X.2002.06.002
5	MODI P J , SHEN W M , TAMBE M , et al. Adopt: asynchronous distributed constraint optimization with quality guarantees[J]. Artificial Intelligence, 2005, 161 (1): 149- 180.
6	雷兴明, 邢昌风, 吴玲. 基于分布式约束优化的武器目标分配问题研究[J]. 计算机工程, 2012, 38 (7): 128- 130.
	LEI X M , XING C F , WU L . Research on weapon target assignment problem based on distributed constraint optimization[J]. Computer Engineering, 2012, 38 (7): 128- 130.
7	刘转.基于多智能体系统的兵棋推演模型研究[D].武汉:华中科技大学, 2016.
	LIU Z.Research on war game simulation based on multi-agent-system[D].Wuhan: Huazhong University of Science and Technology, 2016.
8	NGUYEN B, MIAH S.Analysis of maritime air defense scenarios[C]//Proc.of the 7th Symposlum on Computational Intelligence for Security and Defense Application, 2014: 687-695.
9	XUE L , SUN C , WUNSCH D C . A game-theoretical approach for a finite-time consensus of second-order multi-agent system[J]. International Journal of Control, Automation and Systems, 2019, 17 (5): 1071- 1083. doi: 10.1007/s12555-017-0716-8
10	HU W , LIU L , FENG G . .Output consensus of heterogeneous linear multi-agent systems by distributed event-triggered/self-triggered strategy[J]. IEEE Trans.on Cybernetics, 2017, 47 (8): 1914- 1924. doi: 10.1109/TCYB.2016.2602327
11	YIN X, TAN C, HUANG J J.Output consensus for networks of heterogeneous linear agents[C]//Proc.of the 36th Chinese Control Conference, 2017: 7679-7683.
12	YANG Y, ZHANG C X, WANG L, et al.Distributed event-triggered control with dynamic triggering mechanisms for multi-agent systems[C]//Proc.of the 29th Chinese Control and Decision Conference, 2017: 741-745.
13	KIM Y, LESSER V.DJAO: a communication-constrained DCOP algorithm that combines features of adopt and action-GDL[C]//Proc.of the 28th AAAI Conference on Artificial Intelligence, 2014: 2680-2687.
14	CHACHRA S, MAREFAT M. Distributed algorithms for sleep scheduling in wireless sensor networks[C]//Proc.of the International Conference on Robotics & Automation, 2006: 3101-3107.
15	王思远,王刚,张家瑞.基于变权TOPSIS法的防空目标威胁评估方法[EB/OL].[2019-04-09].http://kns.cnki.net/kcms/detail/61.1234.TJ.20190829.1517.007.html.
	WANG S Y, WANG G, ZHANG J R.Threat assessment method for air defense targets based on variable weight TOPSIS algorithm[EB/OL].[2019-04-09].http://kns.cnki.net/kcms/detail/61.1234.TJ.20190829.1517.007.html.
16	SOTNIK G . The SOSIEL platform:knowledge-based, cognitive, and multi-agent[J]. Biologically Inspired Cognitive Architectures, 2018, 26, 103- 117. doi: 10.1016/j.bica.2018.09.001
17	YOU X , HUA C C , GUAN X P . Distributed adaptive event-triggered control for leader following consensus of multi-agent systems[J]. Asian Journal of Control, 2017, 19 (6): 2155- 2164. doi: 10.1002/asjc.1516
18	CSDN.Detailed deep learning optimization functions[EB/OL].[2019-08-09].https://blog.csdn.net/tsyccnh/article/details/76064087.
19	BOTEV A, LEVER G, BARBER D.Nesterov's accelerated gradient and momentum as approximations to regularised update descent[C]//Proc.of the International Joint Conference on Neural Networks (IJCNN) 2017: 1899-1903.
20	SU W , BOYD S , CANDES E J . A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[J]. Advances in Neural Information Processing Systems, 2015, 3 (1): 2510- 2518.
21	JI S, YE J.An accelerated gradient method for trace norm minimization[C]//Proc.of the International Conference on Machine Learning, 2009: 457-464.
22	张杰, 王刚, 宋亚飞, 等. 基于自适应SGD-多智能体的防空资源部署优化[J]. 系统工程与电子技术, 2019, 41 (7): 1536- 1543.
	ZHANG J , WANG G , SONG Y F , et al. Optimization of air defense resource deployment based on adaptiveSGD-multi-agent[J]. Systems Engineering and Electronics, 2019, 41 (7): 1536- 1543.
23	LIU J M , JIN X L , ZHANG S W . Multi-agent systems.models and experimentation[M]. Beijing: Tsinghua University Press, 2003.
24	LI J , CHEN G , WU Z , et al. Distributed subgradient method for multi-agent optimization with quantized communication[J]. Mathematical Methods in the Applied Sciences, 2016, 40 (4): 1201- 1213.

算法	数据量	时间复杂度	空间复杂度
SGD	5 000 20 000 50 000	O(log₂n) O(log₂n) O(n²)	O(mⁿ) O(mⁿ) O(m)
改进AGD	5 000 20 000 50 000	O(n²) O(1) O(1)	O(m) O(m) O(m)

数据集	大小	训练集	测试集
Data_1	28×28	1 000	200
Data_2	28×28	1 000	500
Data_3	32×32	5 000	1 000

数据集	卷积层数	全连接层神经元个数	参数总数
Data_1	3	2¹⁰	2.8×10⁵
Data_2	3	2¹¹	1.9×10⁶
Data_3	8	2¹¹	2.0×10⁶

算法	限制时间/s	目标函数平均值
SGD	1 3 5	23.124 11.998 10.785
自适应SGD	1 3 5	22.333 10.556 10.116
改进AGD	1 3 5	9.417 9.065 8.913

算法	限制迭代次数	目标函数平均值
SGD	10 20 50	31.145 23.586 12.036
自适应SGD	10 20 50	29.566 22.223 10.014
改进AGD	10 20 50	20.865 9.874 9.135

基于改进AGD-分布式多智能体系统的目标优化分配模型

Target optimal assignment model based on improved AGD-distributed multi-Agent system

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 24

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张普, 薛惠锋, 高山, 左轩. 具有混合执行器故障的多智能体分布式有限时间自适应协同容错控制[J]. 系统工程与电子技术, 2022, 44(4): 1220-1229.
[2]	罗哲, 权婉珍, 张朴睿, 杨小冈. 单边Lipschitz非线性多智能体系统一致性追踪控制[J]. 系统工程与电子技术, 2022, 44(1): 279-284.
[3]	刘家义, 岳韶华, 王刚, 姚小强, 张杰. 复杂任务下的多智能体协同进化算法[J]. 系统工程与电子技术, 2021, 43(4): 991-1002.
[4]	吴文海, 郭晓峰, 周思羽, 高丽. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4): 1012-1021.
[5]	高昂, 董志明, 李亮, 宋敬华, 段莉. MADDPG算法并行优先经验回放机制[J]. 系统工程与电子技术, 2021, 43(2): 420-433.
[6]	张普, 薛惠锋, 高山, 左轩. 具有弱通讯的多智能体分布式自适应协同跟踪控制[J]. 系统工程与电子技术, 2021, 43(2): 487-498.
[7]	王邑, 孙金标, 肖明清, 罗继勋. 基于类型2区间模糊K近邻分类器的动态武器目标分配方法研究[J]. 系统工程与电子技术, 2016, 38(6): 1314-1319.
[8]	陈军伟, 常天庆, 张雷, 杨国振, 马殿哲. 面向装甲分队战法运用的两阶段WTA模型[J]. 系统工程与电子技术, 2016, 38(6): 1326-1331.
[9]	孙一杰, 张国良, 张胜修, 曾静. 一类离散时间异构多智能体系统有向图下的一致性分析[J]. 系统工程与电子技术, 2015, 37(3): 693-699.
[10]	常天庆, 陈军伟, 郝娜, 马殿哲. 装甲分队动态武器目标分配中蚁群算法终止控制[J]. 系统工程与电子技术, 2015, 37(2): 343-347.
[11]	庞毅1, 孙青林1, 焦纲领2, 赵春龙1, 陈增强1. 基于多Agent的舰艇编队对海攻击仿真系统[J]. 系统工程与电子技术, 2015, 37(10): 2396-2403.
[12]	黄峰，陈中起，冯金富，李战武，樊文智. 基于半约束随机搜索的空舰导弹目标分配方法[J]. Journal of Systems Engineering and Electronics, 2013, 35(8): 1676-1680.
[13]	佘莹莹，方华京. 多智能体系统的有限时间跟踪控制[J]. Journal of Systems Engineering and Electronics, 2011, 33(8): 1871-1874.
[14]	唐苏妍，梅珊，朱一凡，雷永林，李群. 基于扩展合同网协议的分布式武器目标分配方法[J]. Journal of Systems Engineering and Electronics, 2011, 33(3): 568-574.
[15]	马飞，曹泽阳，刘晖. 基于博弈论的目标分配策略空间构建与搜索[J]. Journal of Systems Engineering and Electronics, 2010, 32(9): 1941-1945.