基于数据驱动的自适应并行搜索算法求解多星协同调度问题
A data-driven adaptive parallel search algorithm for multiple agile satellites cooperative scheduling problem
吴健 1姚锋 2杜永浩 2陈宇宁 2何磊 2何永明 2罗绥芝3
作者信息
- 1. 国防科技大学系统工程学院,长沙 410073;西安电子科技大学杭州研究院,杭州 311231
- 2. 国防科技大学系统工程学院,长沙 410073
- 3. 湖南师范大学旅游学院,长沙 410081
- 折叠
摘要
针对元启发式算法在求解多星协同调度问题时暴露出的过早或过晚收敛、稳定性较差等问题,提出一种基于数据驱动的自适应并行搜索算法.首先,根据领域知识设计多个任务分配算子,目的是将多星协同调度问题转化为多个单星任务调度问题.然后,启动多个线程并行、独立求解各单星任务调度问题.在算法迭代过程中,各线程依据概率选择不同的邻域操作算子,并且动态更新精英解集和邻域操作算子概率.接着,对精英解集挖掘频繁模式,提取高质量解中有价值的知识并构造新解.最后,将单星任务调度的结果反馈给任务分配层,指导算法开展新一轮的任务分配.仿真实验表明,所提出的算法能够在有限时间内获得高质量的解,在不同的场景下均能表现出良好的适用性和优化效果.
Abstract
When solving the multiple agile satellites cooperative scheduling problem,the metaheuristics faces many problems due to their low intelligence,such as premature or late convergence,poor stability,etc.To solve these problems more efficiently,a data-driven adaptive parallel search algorithm is proposed.Firstly,some task allocation operators are designed to based on domain knowledge,with the purpose of transforming the multiple agile satellites cooperative scheduling problem into multiple single-satellite task scheduling subproblems.Then,multiple threads are started to parallelly and independently solve each single-satellite task scheduling problem.During algorithm iterations,each thread selects different neighborhood operators based on probability,and dynamically updates the probability of neighborhood operators and elites.Next,the frequent pattern mining method is applied to extract knowledge from the elites to construct new solutions.Finally,all single-satellite task scheduling results are fed back to the task allocation layer to start a new allocation.The simulation results show that the proposed algorithm can obtain high-quality solutions within a limited time,and has good applicability and optimization effects in different scenarios.
关键词
数据驱动/多星协同调度/自适应并行搜索/单星任务调度/频繁模式挖掘Key words
data-driven/multiple agile satellites cooperative scheduling/adaptive parallel search/single-satellite task scheduling/frequent pattern mining引用本文复制引用
出版年
2024
NETL
NSTL
万方数据