基于Q学习文化基因算法的考虑任务聚类的多敏捷对地观测卫星调度研究

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

Abstract

Abstract:

To address the multiple agile Earth observation satellite （AEOS） scheduling problem considering task clustering, this problem is modeled as a team oriented problem with task dynamic clustering, time dependent and with time windows. A mixed-integer programming model is constructed. A Q-learning memetic algorithm （QLMA） is proposed, which generates the initial population using a spatial point-target clustering algorithm based on density and clustering time windows. A crossover operator based on historical clustering information is designed to realize population evolution. A Q-learning-based neighborhood selection framework is proposed, with four types of neighborhood search operators—AEOS reallocation, re-clustering, reversal and exchange of observation task clustering. Numerical experiments on instances of different scales validate the effectiveness of the model, the QLMA, and task clustering.

Key words: satellite scheduling, Earth observation, task clustering, memetic algorithm

CLC Number:

O 221

Jingxian LUO, Guanghui ZHOU, Jinyue YU, Yang ZHANG. Research on multiple agile earth observation satellite scheduling based on Q-learning memetic algorithm considering task clustering[J]. Systems Engineering and Electronics, 2026, 48(4): 1349-1359.

Figures/Tables 13

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Table 2

Table 3

Table 4

Table 5

Fig.5

Table 6

Fig.6

Fig.7

References 29

1	National Aeronautics and Space Administration. Landsat science. [EB/OL]. [2025-04-06]. https: //landsat.gsfc.nasa.gov/.
2	European Space Agency. Europe’s eyes on Earth: the EU’s Copernicus Programme [EB/OL]. [2025-04-08]. https://omcs.atlassian.net/wiki/spaces/CSWK/pages/407404661/Copernicus+Programme.
3	China National Space Administration. High-resolution Earth observation syetem [EB/OL]. [2025-03-09]. https://www.cnsa.gov.cn/n6758824/n6759009/n6759041/c6780463/content.html.
4	LEMAITRE M, VERFAILLIE G, JOUHAUD F, et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6 (5): 367- 381. doi: 10.1016/S1270-9638(02)01173-2
5	WOLFE W J, SORENSEN S E. Three scheduling algorithms applied to the Earth observing systems domain[J]. Management Science, 2000, 46 (1): 148- 166. doi: 10.1287/mnsc.46.1.148.15134
6	WANG Z L, HU X X, MA H W, et al. Learning multi-satellite scheduling policy with heterogeneous graph neural network[J]. Advances in Space Research, 2024, 73 (6): 2921- 2938. doi: 10.1016/j.asr.2023.12.036
7	LI P Y, WANG H Q, ZHANG Y X, et al. Mission planning for distributed multiple agile Earth observing satellites by attention-based deep reinforcement learning method[J]. Advances in Space Research, 2024, 74 (5): 2388- 2404. doi: 10.1016/j.asr.2024.06.003
8	CHANG Z X, ZHOU Z B. Three multi-objective memetic algorithms for observation scheduling problem of active-imaging agile Earth observation satellites[J]. Annals of Operations Research, 2024, 346, 861- 893.
9	CHEN M, DU Y H, TANG K, et al. Learning to construct a solution for the agile satellite scheduling problem with time-dependent transition times[J]. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2024, 54 (10): 5949- 5963.
10	高天旸, 胡笑旋, 夏维. 基于分布式协同进化的星座自主任务规划算法[J]. 系统工程与电子技术, 2022, 44 (5): 1600- 1608.
	GAO T Y, HU X X, XIA W. Constellation autonomous mission planning algorithm based on distributed co-evolution[J]. Systems Engineering and Electronics, 2022, 44 (5): 1600- 1608.
11	WU G H, LIU J, MA M H, et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
12	WU G H, WANG H L, WITOLD P, et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Computers & Industrial Engineering, 2017, 113, 576- 588.
13	WANG P, REINELT G, GAO P, et al. A model, a heuristic and a decision support system to solve the scheduling problem of an Earth observing satellite constellation[J]. Computers & Industrial Engineering, 2011, 61 (2): 322- 335.
14	SPANGELO S, CUTLER J, GILSON K, et al. Optimization-based scheduling for the single-satellite, multi-ground station communication problem[J]. Computers & Operations Research, 2015, 57, 1- 16.
15	PENG G S, DEWIL R, VERBEECK C, et al. Agile Earth observation satellite scheduling: an orienteering problem with time-dependent profits and travel times[J]. Computers & Operations Research, 2019, 111, 84- 98.
16	WOLSEY L A, NEMHAUSER G L. Integer and combinatorial optimization[M]. Hoboken: John Wiley & Sons, 1999.
17	WERTZ J R. Spacecraft attitude determination and control[M]. Berlin: Springer Science & Business Media, 2012.
18	GOLDEN B L, LEVY L, VOHRA R. The orienteering problem[J]. Naval Research Logistics, 1987, 34 (3): 307- 318.
19	LI J J, ZHU J H, PENG G S, et al. Branch-price-and-cut algorithms for the team orienteering problem with interval-varying profits[J]. European Journal of Operational Research, 2024, 319 (3): 793- 807. doi: 10.1016/j.ejor.2024.07.015
20	HE M, WU Q H, BENLIC U, et al. An effective multi-level memetic search with neighborhood reduction for the clustered team orienteering problem[J]. European Journal of Operational Research, 2024, 318 (3): 778- 801. doi: 10.1016/j.ejor.2024.06.015
21	ZHAO J, POON M, TAN V Y F, et al. A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem[J]. European Journal of Operational Research, 2024, 317 (3): 921- 935. doi: 10.1016/j.ejor.2024.04.011
22	卢弘, 王耀南, 乔非, 等. 面向可持续生产中多任务调度的双重增强模因算法[J]. 自动化学报, 2024, 50 (4): 731- 744.
	LU H, WANG Y N, QIAO F, et al. Dual-enhanced memetic algorithm for multi-task scheduling in sustainable production[J]. Acta Automatica Sinica, 2024, 50 (4): 731- 744.
23	周光辉, 梁伟, 敬帅. 多飞艇协同对地观测和数据传输调度模型与算法研究[J]. 系统工程理论与实践, 2020, 40 (4): 1045- 1056.
	ZHOU G H, LIANG W, JING S. Research on multi-airship cooperative earth observation and data transmission scheduling model and algorithm[J]. Systems Engineering − Theory & Practice, 2020, 40 (4): 1045- 1056.
24	ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc. of the International Conference on Knowledge Discovery and Data Mining, 1996.
25	MICHALEWICZ Z. Genetic algorithms+data structures=evolution programs[M]. Berlin: Springer, 1992.
26	WATKINS C J C H, DAYAN P. Q-learning[J]. Machine Learning, 1992, 8, 279- 292.
27	KARIMI-MAMAGHAN M, MOHAMMADI M, PASDELOUP B, et al. Learning to select operators in meta-heuristics: an integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2023, 304 (3): 1296- 1330.
28	HU R, HUANG Y F, WU X, et al. Collaborative Q-learning hyper-heuristic evolutionary algorithm for the production and transportation integrated scheduling of silicon electrodes[J]. Swarm and Evolutionary Computation, 2024, 86, 101498. doi: 10.1016/j.swevo.2024.101498
29	LÓPEZ-IBÁÑEZ M, DUBOIS-LACOSTE J, CÁCERES L P, et al. The irace package: iterated racing for automatic algorithm configuration[J]. Operations Research Perspectives, 2016, 3, 43- 58. doi: 10.1016/j.orp.2016.09.002

序号	半长轴/km	轨道倾角/（°）	升交点赤经/（°）	离心率	近地点辐角/（°）
1	7569.35	100.74	83.24	0.0025	10.97
2	7467.87	63.40	338.34	0.0280	4.93
3	7580.23	100.63	39.86	0.0006	260.43
4	7467.80	63.40	116.96	0.0187	4.74
5	7129.37	98.41	280.69	0.0001	60.33
6	7011.36	98.30	84.10	0.0019	218.13
7	7620.68	100.28	190.60	0.0022	30.916
8	7580.05	100.05	283.20	0.0009	207.72

地面站	经纬度
地面站1	（116.98°E, 40.57°N）
地面站2	（75.95°E, 39.51°N）
地面站3	（109.33°E, 18.31°N）
地面站4	（102.80°E, 25.03°N）
地面站5	（20.30°E, 67.90°N）

参数名称	取值范围	调优结果
种群规模	$\{ 10,20,30,40\} $	20
交叉概率	$\{ 0.6,{\text{ }}0.7,{\text{ }}0.8,{\text{ }}0.9\} $	0.6
邻域观测任务临界值	$\{ 2,{\text{ }}3,{\text{ }}4,{\text{ }}5\} $	3
任务分配均衡性阈值	$\{ 0.4,{\text{ }}0.5,{\text{ }}0.6,{\text{ }}0.7\} $	0.5
种群多样性阈值	$\{ 0.5,{\text{ }}0.6,{\text{ }}0.7,{\text{ }}0.8\} $	0.6
最大迭代次数	$\{ 100,200,300,400\} $	300
最大无改进代数	$ \{ 10,20,30,40\} $	20

AEOS数量	观测任务数量	QLMA				Gurobi		QLMA与Gurobi总收益的差值/%
AEOS数量	观测任务数量	最大总收益	平均总收益	最小总收益	计算时间/s	总收益	计算时间/s	QLMA与Gurobi总收益的差值/%
1	10	2.69	2.69	2.69	1.49	2.69	4.63	0.00
	30	7.20	6.97	6.62	5.68	3.03	3600.00	57.92
	50	9.34	8.80	8.47	6.99	−	−	−
	70	11.18	10.48	9.67	9.57	−	−	−
	90	12.25	11.49	10.73	15.72	−	−	−
2	10	4.64	4.64	4.64	2.08	4.64	138.47	0.00
	30	12.58	12.58	12.58	7.31	−	−	−
	50	20.90	19.92	19.00	18.17	−	−	−
	70	26.67	25.78	24.37	26.45	−	−	−
	90	32.73	30.89	29.82	43.77	−	−	−
3	10	4.73	4.73	4.73	2.42	4.73	738.20	0.00
	30	13.28	13.28	13.28	8.81	−	−	−
	50	21.99	21.91	21.86	22.92	−	−	−
	70	32.15	31.75	30.77	58.97	−	−	−
	90	39.13	38.49	37.95	65.66	−	−	−
4	10	5.40	5.40	5.40	3.46	5.40	107.78	0.00
	30	14.84	14.83	14.79	14.39	−	−	−
	50	25.22	25.22	25.21	25.57	−	−	−
	70	36.76	36.74	36.70	39.32	−	−	−
	90	46.90	46.82	46.72	142.84	−	−	−

AEOS数量	观测任务数量	QLMA				MA				QLMA与MA 平均总收益的差值/%
AEOS数量	观测任务数量	最大总收益	平均总收益	最小总收益	计算时间/ s	最大总收益	平均总收益	最小总收益	计算时间/ s	QLMA与MA 平均总收益的差值/%
2	100	35.27	34.03	32.61	56.30	32.36	31.47	30.52	34.46	7.51
	200	46.27	43.56	39.97	64.43	41.52	40.54	39.40	48.95	6.94
	300	52.65	48.68	44.33	146.70	46.46	44.77	43.34	105.96	8.03
	400	55.46	53.50	50.71	203.52	51.02	48.75	46.09	174.86	8.89
	500	57.21	53.70	48.93	201.46	52.39	49.74	44.30	178.31	7.38
4	100	50.57	50.46	50.35	57.53	50.53	50.39	50.10	77.17	0.14
	200	87.02	83.92	81.16	243.35	81.64	80.26	76.55	223.16	4.36
	300	99.91	96.98	91.01	444.22	94.00	91.82	90.12	395.74	5.33
	400	116.39	112.44	108.43	694.62	101.60	99.77	97.96	647.07	11.27
	500	129.05	121.34	116.06	1203.91	113.87	104.98	93.90	609.74	13.48
6	100	50.59	50.57	50.54	65.11	50.57	50.57	50.57	53.65	0.00
	200	99.61	99.40	98.89	325.31	99.26	98.18	97.55	284.81	1.23
	300	135.71	132.15	129.44	722.52	126.55	124.83	122.61	725.40	5.54
	400	157.51	151.76	145.87	1382.75	152.14	148.94	144.17	1422.81	1.86
	500	174.36	171.48	165.94	1938.04	158.76	155.74	152.70	1683.13	9.18
8	100	50.59	50.58	50.57	78.74	50.59	50.58	50.57	60.66	0.00
	200	99.84	99.84	99.83	278.60	99.78	99.42	99.04	250.86	0.42
	300	143.23	141.38	139.98	936.23	138.60	135.34	131.64	794.88	4.27
	400	177.20	173.39	171.39	1620.43	163.37	160.04	158.70	1273.33	7.70
	500	206.38	201.18	197.31	2206.33	185.71	178.91	169.03	1734.53	11.07

Research on multiple agile earth observation satellite scheduling based on Q-learning memetic algorithm considering task clustering

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 29

Related Articles 11

Recommended Articles

Metrics

Comments

AEOS 数量	观测任务数量	QLMA				QLMA_NC				QLMA与QLMA_NC 平均总收益的差值/%
AEOS 数量	观测任务数量	最大总收益	平均总收益	最小总收益	计算时间/ s	最大总收益	平均总收益	最小总收益	计算时间/ s	QLMA与QLMA_NC 平均总收益的差值/%
2	100	35.27	34.03	32.61	56.30	32.77	32.25	31.86	45.03	5.22
	200	46.27	43.56	39.97	64.43	42.65	42.31	41.95	85.45	2.88
	300	52.65	48.68	44.33	146.70	44.59	42.87	40.07	126.72	11.94
	400	55.46	53.50	50.71	203.52	45.66	45.05	44.73	152.96	15.81
	500	57.21	53.70	48.93	201.46	47.39	46.58	45.62	229.01	13.26
4	100	50.57	50.46	50.35	57.53	50.54	50.40	50.45	91.12	0.12
	200	87.02	83.92	81.16	243.35	80.30	78.91	77.15	231.68	5.97
	300	99.91	96.98	91.01	444.22	89.67	87.57	84.09	572.59	9.71
	400	116.39	112.44	108.43	694.62	94.15	91.66	88.98	624.79	18.48
	500	129.05	121.34	116.06	1203.91	95.06	93.79	91.55	643.49	22.71
6	100	50.59	50.58	50.54	65.11	50.59	50.57	50.54	80.86	0.01
	200	99.61	99.40	98.89	325.31	98.81	97.23	96.00	350.40	2.18
	300	135.71	132.15	129.44	722.52	118.78	117.53	116.17	666.29	11.06
	400	157.51	151.76	145.87	1382.75	139.96	132.91	125.64	1157.04	12.42
	500	174.36	171.48	165.94	1938.04	141.67	139.16	136.41	1907.67	18.85
8	100	50.59	50.58	50.57	78.74	50.59	50.58	50.57	83.85	0.00
	200	99.84	99.84	99.83	278.60	99.84	99.77	99.64	284.40	0.06
	300	143.23	141.38	139.98	936.23	136.20	134.43	131.60	968.10	4.92
	400	177.20	173.39	171.39	1620.43	156.97	154.16	150.19	1427.18	11.09
	500	206.38	201.18	197.31	2206.33	172.74	167.35	161.33	1946.55	16.82

[1]	Peng JIN, Xiaoxi TANG. Multi-satellite emergency task scheduling with merging mechanism [J]. Systems Engineering and Electronics, 2022, 44(4): 1270-1281.
[2]	Bin ZENG, Quanxian ZHANG, Houpu LI. Optimal scheduling for cooperative support chain of logistics and equipment under uncertainty [J]. Systems Engineering and Electronics, 2021, 43(5): 1277-1286.
[3]	Songlian REN, Haiquan SUN, Peng JIN. Multi-satellite scheduling problem based on task merging mechanism [J]. Systems Engineering and Electronics, 2021, 43(1): 171-180.
[4]	Dewei LI, Liming JIANG, Houjun JIANG, Jinglong DONG, Hansheng WANG. System parameters analysis of the Moon-based SAR Earth observation [J]. Systems Engineering and Electronics, 2020, 42(4): 792-798.
[5]	Jingyu YAO, Peng JIN, Waiming ZHU, Xiaoxuan HU. Multi-satellite scheduling problem for regional targets with uneven income [J]. Systems Engineering and Electronics, 2020, 42(3): 638-645.
[6]	SU Xi-chao, HAN Wei, XIAO Wei, JIANG Ting-ting. Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm [J]. Systems Engineering and Electronics, 2016, 38(10): 2303-2309.
[7]	QIU Dishan， WANG Jianjiang， WU Chaobo， LIU Gang. Emergency scheduling method of earth observation satellites based on task merging [J]. Journal of Systems Engineering and Electronics, 2013, 35(7): 1430-1437.
[8]	LIAN Zhen-yu，TAN Yue-jin，YAN Zhen-zhen. Temporal reasoning technology for AEOS scheduling [J]. Journal of Systems Engineering and Electronics, 2013, 35(6): 1206-1211.
[9]	SHEN Jia-jie, LIN Feng. Structure learning of Bayesian network using adaptive hybrid Memetic algorithm [J]. Journal of Systems Engineering and Electronics, 2012, 34(6): 1293-1298.
[10]	GUO Hao， WU Guohua， QIU Dishan. Intensive task clustering method for agile imaging satellites [J]. Journal of Systems Engineering and Electronics, 2012, 34(5): 931-935.
[11]	WANG Pei，LI Ju-fang，TAN Yue-jin. Comparison of earth observation scheduling model for satellite formation [J]. Journal of Systems Engineering and Electronics, 2010, 32(8): 1689-1694.