基于NSGA-Ⅱ的车载光学测量设备任务调度方案优化

doi:10.12305/j.issn.1001-506X.2024.07.21

摘要/Abstract

摘要：

针对车载光学测量设备任务调度方案优化问题, 提出了一种基于非支配排序的遗传算法(non-dominated sorting genetic algorithm Ⅱ, NSGA-Ⅱ)的多目标遗传算法。首先, 建立了包含约束、优化指标在内的观测任务调度问题的数学模型。其中, 针对多优化指标进行巧妙处理, 将某些不作为最优指标的优化指标作为指标约束进行处理。其次, 基于NSGA-Ⅱ中的快速非优超排序方法计算多目标适应度函数与选择算子, 多目标优化求解得到的Pareto最优解集即为任务调度方案集。最后, 通过仿真算例对所提算法进行了求解验证。仿真结果表明, 该算法能够有效解决任务调度方案优化问题, 为车载光学测量设备的工程实践提供了一定的参考。

关键词: 车载光学测量设备, 任务调度, 多目标优化, 遗传算法

Abstract:

To improve the task dispatch plan for vehicular optical observation equipment, a multi-objective genetic algorithm based on non-dominated sorting genetic algorithm Ⅱ (NSGA-Ⅱ) is proposed. Firstly, the task dispatch problem is modeled with the constraints and optimum indexes. To deal with multiple optimum indexes, the optimum index which is not considered in the objective function is considered as a constraint. Secondly, the multi-objective fitness function and selection operator is calculated based on the fast non-dominated sorting method of NSGA-Ⅱ. The Pareto solution set obtained by the multi-objective optimization is the task dispatch plan solution. Finally, the proposed algorithm is verified by a simulation example. The simulation results show that this method can solve the task dispatch plan problem effectively, which is valuable for the application of the vehicular optical observation equipment.

Key words: vehicular optical observation equipment, task dispatch, multi-objective optimization, genetic algorithm

中图分类号:

许强强, 柴华. 基于NSGA-Ⅱ的车载光学测量设备任务调度方案优化[J]. 系统工程与电子技术, 2024, 46(7): 2393-2400.

Qiangqiang XU, Hua CHAI. Optimization of task dispatch plan for vehicular optical observation equipment based on NSGA-Ⅱ[J]. Systems Engineering and Electronics, 2024, 46(7): 2393-2400.

图/表 8

图1

图2

表1

表2

表3

表4

表5

表6

参考文献 34

1	罗剑, 于小红, 王杰娟. 多平台空间目标观测协同调度问题[J]. 火力指挥与控制, 2021, 46 (12): 81- 87.
	LUO J , YU X H , WANG J J . Cooperative scheduling problem space target observation of multi-platform[J]. Fire Control & Command Control, 2021, 46 (12): 81- 87.
2	崔嵩. 船载空间目标观测系统的任务规划[J]. 电讯技术, 2021, 61 (12): 1514- 1520. doi: 10.3969/j.issn.1001-893x.2021.12.008
	CUI S . Mission planning of shipborne space target observation system[J]. Telecommunication Engineering, 2021, 61 (12): 1514- 1520. doi: 10.3969/j.issn.1001-893x.2021.12.008
3	刘莹奇. 轻型车载大口径光电跟测系统光学设计[J]. 光学技术, 2012, 38 (5): 583- 587.
	LIU Y Q . Optical design of electro-optical vehicle-based tracking system with large aperture and lightweight[J]. Optical Technique, 2012, 38 (5): 583- 587.
4	刘莹奇, 王志, 刘欣悦, 等. 米级车载高分辨光电成像系统光学设计[J]. 红外与激光工程, 2011, 40 (8): 1512- 1516.
	LIU Y Q , WANG Z , LIU X Y , et al. Optical design of vehicle-based high resolution E-O imaging system using meter class telescope[J]. Infrared and Laser Engineering, 2011, 40 (8): 1512- 1516.
5	柴华, 宋旭民, 赵乾, 等. 车载光学测量设备任务调度问题建模与求解[J]. 国防科技大学学报, 2021, 43 (5): 1- 9.
	CHAI H , SONG X M , ZHAO Q , et al. Modeling and solving for task dispatch problem of vehicular optical observation equipment[J]. Journal of National University of Defense Technology, 2021, 43 (5): 1- 9.
6	SAHIN M A, LEBLEBICIOGLU K. A standard expert system for weapon target assignment problem[C]//Proc. of the International Symposium on Performance Evaluation of Computer & Telecommunication Systems, 2009: 221-224.
7	LU Y P , CHEN D Z . A new exact algorithm for the weapon-target assignment problem[J]. Omega, 2021, 98, 102138. doi: 10.1016/j.omega.2019.102138
8	HAMZEHI S, BOGENBERGER K, FR ANECK P, et al. Combinatorial reinforcement learning of linear assignment problems[C]// Proc. of the IEEE Intelligent Transportation Systems Conference, 2019: 3314-3321.
9	SUMMERS D S , ROBBINS M J , LUNDAY B J . An approximate dynamic progmming approach for comparing firing policies in a networked air defense environment[J]. Computers and Operations Research, 2020, 117, 104890. doi: 10.1016/j.cor.2020.104890
10	LEBOUCHER C , SHIN H S , MENEC S L , et al. Optimal weapon target assignment based on an geometric approach[J]. IFAC Proceedings Volumes, 2013, 46 (19): 341- 346. doi: 10.3182/20130902-5-DE-2040.00037
11	SHALUMOV V , SHIMA T . Weapon-target-allocation strategies in multi-agent target-missile-defender engagement[J]. Journal of Guidance, Control, and Dynamics, 2017, 40 (10): 2452- 2464. doi: 10.2514/1.G002598
12	HU X W, LUO P C, ZHANG X N. IACO algorithm for weapon-target assignment problem in air combat[C]//Proc. of the 2nd International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, 2018: 35-40.
13	KLINE A G , AHNER D K , LUNDAY B J , et al. Real-rime heuristic algorithms for the static weapon target assignment problem[J]. Journal of Heuristics, 2019, 25 (3): 377- 397. doi: 10.1007/s10732-018-9401-1
14	AHNER D K , PARSON C R . Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming[J]. Optimization Letters, 2015, 9 (8): 1689- 1701. doi: 10.1007/s11590-014-0823-x
15	CHANG T Q , KONG D P , HAO N , et al. Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization[J]. Applied Soft Computing, 2018, 70, 845- 863. doi: 10.1016/j.asoc.2018.06.014
16	XIN B , WANG Y P , CHEN J . An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem[J]. IEEE Trans.on System, Man, and Cybernetics: Systems, 2019, 49 (12): 2536- 2547. doi: 10.1109/TSMC.2017.2784187
17	LI X Y , ZHOU D Y , YANG Z , et al. A novel genetic algorithm for the synthetical sensor-weapon-target assignment problem[J]. Applied Sciences, 2019, 9 (18): 3803. doi: 10.3390/app9183803
18	ZHANG K , ZHOU D Y , YANG Z , et al. Constrained multi-objective weapon target assignment for area targets by efficient evolutionary algorithm[J]. IEEE Access, 2019, 7, 176339- 176360. doi: 10.1109/ACCESS.2019.2955482
19	LI J , XIN B , PARDALOS P M , et al. Solving bi-objective uncertain stochastic resource allocation problems by the CVaR-based risk measure and decomposition-based multi-objective evolutionary algorithms[J]. Annals of Operations Research, 2021, 296, 639- 666. doi: 10.1007/s10479-019-03435-4
20	XU W Q , CHEN C , DING S X , et al. A bi-objective dynamic collaborative task assignment under uncertainty using modified MOEA/D with heuristic initialization[J]. Expert Systems with Applications, 2020, 140, 112844. doi: 10.1016/j.eswa.2019.112844
21	FU G Y , WANG C , ZHANG D Q , et al. A multi-objective particle swam optimization algorithm based on multi-population coevolution for weapon-target assignment[J]. Mathematical Problems in Engineering, 2019, 2019 (1): 1- 11.
22	ZHANG K , ZHOU D Y , YANG Z , et al. Efficient decision approaches for asset-based dynamic weapon target assignment by a receding horizon and marginal return heuristic[J]. Electronics, 2020, 9 (9): 1511. doi: 10.3390/electronics9091511
23	KLINE A , AHNER D , HILL R . The weapon-target assignment problem[J]. Computers and Operations Research, 2019, 105, 226- 236. doi: 10.1016/j.cor.2018.10.015
24	王储, 南英, 许航. 一种新的精英遗传算法及在多弹拦截分配策略的应用[J]. 航天控制, 2021, 39 (4): 59- 65.
	WANG C , NAN Y , XU H . A new elite genetic algorithm and its application in multi-missile interception assignment strategy[J]. Aerospace Control, 2021, 39 (4): 59- 65.
25	陈曼, 周凤星, 张成尧. 改进MOPSO的联合火力打击目标分配[J]. 火力指挥与控制, 2019, 44 (9): 125- 129.
	CHEN M , ZHOU F X , ZHANG C Y . Improved MOPSO joint fire strike target assignment[J]. Fire Control & Command Control, 2019, 44 (9): 125- 129.
26	陈曼, 周凤星. 改进粒子群算法的舰载武器目标分配[J]. 火力指挥与控制, 2018, 43 (11): 72- 76.
	CHEN M , ZHOU F X . Shipborne weapon target assignment based on improved particle swarm optimization[J]. Fire Control & Command Control, 2018, 43 (11): 72- 76.
27	张彦芳, 闫德恒, 王冀扬, 等. 一种基于蚁群算法的准动态防空武器分配算法[J]. 火力指挥与控制, 2016, 41 (9): 112- 116.
	ZHANG Y F , YAN D H , WANG J Y , et al. A quasi-dynamic defense weapon assignment based on ant-colony optimization[J]. Fire Control & Command Control, 2016, 41 (9): 112- 116.
28	吴文海, 郭晓峰, 周思羽, 等. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43 (4): 1012- 1021. doi: 10.12305/j.issn.1001-506X.2021.04.18
	WU W H , GUO X F , ZHOU S Y , et al. Improved differential evolution algorithm for solving weapon target assignment pro-blem[J]. Systems Engineering and Electronics, 2021, 43 (4): 1012- 1021. doi: 10.12305/j.issn.1001-506X.2021.04.18
29	王力超, 乔勇军, 李永胜. 基于CE-CAPSO武器目标分配优化算法[J]. 火力指挥与控制, 2020, 45 (11): 82- 87.
	WANG L C , QIAO Y J , LI Y S . Optimization algorithm for weapon target assignment based on CE-CAPSO[J]. Fire Control & Command Control, 2020, 45 (11): 82- 87.
30	邱少明, 刘良成, 张学翠, 等. 基于改进鲸鱼优化算法的武器目标分配[J]. 火力指挥与控制, 2021, 46 (7): 27- 31.
	QIU S M , LIU L C , ZHANG X C , et al. Research on weapon target based on improved whale optimization algorithm[J]. Fire Control & Command Control, 2021, 46 (7): 27- 31.
31	刘双双, 许瑞明, 潘俊杰. 基于小生境蝙蝠算法的联合远程打击武器目标分配问题建模与求解[J]. 装备学院学报, 2017, 28 (2): 93- 98.
	LIU S S , XU R M , PAN J J . Research on the modeling and solving of the joint long-range strike weapon target assignment problem based on the niche bat algorithm[J]. Journal of Equipment Academy, 2017, 28 (2): 93- 98.
32	张先剑. 空陆攻防博弈的动态武器目标分配[J]. 国防科技大学学报, 2019, 41 (2): 185- 190.
	ZHANG X J . Land defense weapon versus target assignment against air attack[J]. Journal of National University of Defense Technology, 2019, 41 (2): 185- 190.
33	GUO X H , JI M J , ZHAO Z W , et al. Global path planning and multi-objective path control for unmanned surface vehicle based on modified particle swarm optimization (PSO) algorithm[J]. Ocean Engineering, 2020, 216, 107693.
34	赵瑞. 多目标遗传算法应用的研究[D]. 天津: 天津大学, 2005.
	ZHAO R. Analysis about the application of the multi-objective genetic algorithm[D]. Tianjin: Tianjin University, 2005.

编号	初始位置纬经高/((°)/(°)/km)	剩余观测次数
E₁	P₁=(34.258/108.929/0)	R₁=5
E₂	P₂=(34.258/108.929/0)	R₂=3
E₃	P₃=(34.258/108.929/0)	R₃=4
E₄	P₄=(34.258/108.929/0)	R₄=3
E₅	P₅=(34.258/108.929/0)	R₅=2
E₆	P₆=(34.258/108.929/0)	R₆=5

编号	半长轴/km	偏心率	轨道倾角/(°)	近地点角距/(°)	升交点赤经/(°)	真近点角/(°)
T₁	6 678.14	0	60	0	0	0
T₂	6 678.14	0	60	0	90	45
T₃	6 678.14	0	60	0	180	90
T₄	6 678.14	0	60	0	270	135

编号	位置纬经高/((°)/(°)/km)
S₁	(43.8/87.583/0)
S₂	(36.617/101.767/0)
S₃	(25.939 4/107.002/0)
S₄	(38.041/114.479/0)

窗口编号	对应关系	开始时刻	结束时刻	窗口时长/s
1	S₁, T₁	2018/6/4 10:58:40	2018/6/4 10:58:52	12
2	S₁, T₁	2018/6/5 11:07:19	2018/6/5 11:07:37	18
3	S₁, T₁	2018/6/6 03:24:00	2018/6/6 03:24:30	30
4	S₁, T₂	2018/6/5 16:57:45	2018/6/5 16:58:14	29
5	S₁, T₂	2018/6/7 09:23:14	2018/6/7 09:23:43	29
6	S₁, T₃	2018/6/6 22:56:58	2018/6/6 22:57:28	30
7	S₁, T₃	2018/6/7 15:13:53	2018/6/7 15:14:07	14
8	S₁, T₄	2018/6/1 21:45:26	2018/6/1 21:45:52	26
9	S₂, T₁	2018/6/2 10:44:26	2018/6/2 10:44:45	19
10	S₂, T₁	2018/6/6 01:51:08	2018/6/6 01:51:19	11
11	S₂, T₂	2018/6/3 16:43:34	2018/6/3 16:44:04	30
12	S₂, T₂	2018/6/7 07:50:13	2018/6/7 07:50:41	28
13	S₂, T₃	2018/6/4 22:42:50	2018/6/4 22:43:15	25
14	S₂, T₄	2018/6/1 20:12:23	2018/6/1 20:12:52	29
15	S₂, T₄	2018/6/5 04:33:26	2018/6/5 04:33:37	11
16	S₃, T₁	2018/6/2 01:14:34	2018/6/2 01:15:03	29
17	S₃, T₁	2018/6/3 10:56:06	2018/6/3 10:56:22	16
18	S₃, T₂	2018/6/3 07:13:49	2018/6/3 07:14:14	25
19	S₃, T₂	2018/6/4 16:55:12	2018/6/4 16:55:42	30
20	S₃, T₃	2018/6/5 22:54:30	2018/6/5 22:54:51	21
21	S₃, T₄	2018/6/4 19:03:30	2018/6/4 19:03:59	29
22	S₃, T₄	2018/6/6 04:45:07	2018/6/6 04:45:12	5
23	S₄, T₁	2018/6/1 09:03:20	2018/6/1 09:03:45	25
24	S₄, T₁	2018/6/3 01:28:41	2018/6/3 01:29:01	20
25	S₄, T₂	2018/6/2 15:02:31	2018/6/2 15:03:01	30
26	S₄, T₂	2018/6/3 07:19:10	2018/6/3 07:19:35	25
27	S₄, T₃	2018/6/3 21:01:46	2018/6/3 21:02:12	26
28	S₄, T₃	2018/6/4 13:18:21	2018/6/4 13:18:51	30
29	S₄, T₄	2018/6/4 02:52:18	2018/6/4 02:52:39	21
30	S₄, T₄	2018/6/4 19:09:04	2018/6/4 19:09:06	2
31	S₄, T₄	2018/6/5 19:17:37	2018/6/5 19:17:57	20

设备	窗口编号	对应关系	开始时刻	结束时刻	窗口时长/s
E₁	9	S₂, T₁	2018/6/2 10:44:26	2018/6/2 10:44:45	19
E₁	27	S₄, T₃	2018/6/3 21:01:46	2018/6/3 21:02:12	26
E₁	28	S₄, T₃	2018/6/4 13:18:21	2018/6/4 13:18:51	30
E₁	3	S₁, T₁	2018/6/6 03:24:00	2018/6/6 03:24:30	30
E₂	23	S₄, T₁	2018/6/1 09:03:20	2018/6/1 09:03:45	25
E₂	14	S₂, T₄	2018/6/1 20:12:23	2018/6/1 20:12:52	29
E₂	24	S₄, T₁	2018/6/3 01:28:41	2018/6/3 01:29:01	20
E₃	1	S₁, T₁	2018/6/4 10:58:40	2018/6/4 10:58:52	12
E₃	2	S₁, T₁	2018/6/5 11:07:19	2018/6/5 11:07:37	18
E₃	6	S₁, T₃	2018/6/6 22:56:58	2018/6/6 22:57:28	30
E₄	25	S₄, T₂	2018/6/2 15:02:31	2018/6/2 15:03:01	30
E₄	26	S₄, T₂	2018/6/3 07:19:10	2018/6/3 07:19:35	25
E₅	29	S₄, T₄	2018/6/4 02:52:18	2018/6/4 02:52:39	21
E₆	13	S₂, T₃	2018/6/4 22:42:50	2018/6/4 22:43:15	25
E₆	31	S₄, T₄	2018/6/5 19:17:37	2018/6/5 19:17:57	20
E₆	10	S₂, T₁	2018/6/6 01:51:08	2018/6/6 01:51:19	11
E₆	12	S₂, T₂	2018/6/7 07:50:13	2018/6/7 07:50:41	28