基于聚类的卫星测控调度方法及系统

1.一种基于聚类的卫星测控调度方法，其特征在于，包括以下步骤：步骤1：获取可调度的卫星资源、地面站资源、任务集以及可见时间窗集合；步骤2：根据步骤1中所获取的内容构建混合整数规划模型；步骤3：对所述混合整数规划模型进行求解；步骤4：将求解得到的测控方案输出；所述混合整数规划模型是：目标函数为： （1）其中， 表示任务 的收益， 为0-1决策变量，表示任务 是否安排在天线 上第 个可见时间窗,1为安排，0为否， 表示任务， T 表示任务集， 表示天线， 表示天线集合， 表示任务 安排在天线 上第 个可见时间窗， 表示任务 安排在天线 上的时间窗集合；约束条件是： （2）式2表明任务需要在允许的开始时间之后开始执行任务； 表示任务 安排在天线 上第 个可见时间窗上的实际的测控时间长度， 表示任务 要求的测控时间长度； （3）式3表明任务需要在允许的结束时间之前完成任务； 表示任务 安排在天线 上第 个可见时间窗上的实际开始时间, 表示任务 安排在天线 上第 个可见时间窗上的结束时间； （4）式4表明任务最多可以执行一次； 表示任务 安排在天线 上第 个可见时间窗上的的最早允许开始时间； （5）式5表明任务实际执行时间应当与要求时间相同； 表示任务 安排在天线 上第 个可见时间窗上的的最晚允许结束时间； （6）式6表明任务执行过程需要在一个地面站时间范围内； 表示任务 安排在天线 上第 个可见时间窗的开始时间； （7）式7表明每个任务只能由一个天线服务； （8）式8表明每个任务只能在一个可见的时间窗口内执行； 表示任务 安排在天线 上第 个可见时间窗的结束时间； （9）式9表明每个任务在全部天线上最多执行一次； （10）式10表明每个任务在全部时间窗内最多执行一次； （11）式11表明任务在规划周期内最多被执行一次； （12）式12表明两个任务要满足任务转换时间的间隔要求； 表示任务之间的转换时间。 2.根据权利要求1所述的方法，其特征在于，步骤3中对所述混合整数规划模型进行求解的方法是基于聚类的遗传算法。 3.根据权利要求2所述的方法，其特征在于，所述基于聚类的遗传算法是：步骤3.1：初始化遗传算法参数、聚类K-means方法参数；步骤3.2：生成初始化种群，种群中的每一个个体为任务集中的所有任务进行编码后的编码序列；步骤3.3：当迭代代数没有达到最大迭代代数时，执行步骤3.3.1；否则，执行步骤3.4；步骤3.3.1：对种群内每一个个体生成测控方案初始解并计算目标函数值；步骤3.3.2：如果当代种群中的最大目标函数值大于最优目标函数值，则更新最优目标函数值并计数 ；如果当代种群中最大目标函数值大于上一代种群中最大目标函数值，则更新计数 ；如果当代种群中最大目标函数值小于上一代种群中最大函数值乘以比例 ，则更新计数 ；步骤3.3.3：根据目标函数值使用轮盘赌选择个体生成新的种群；步骤3.3.4：对新的种群使用基于聚类的交叉和变异方法进行更新；步骤3.3.5：如果 等于阈值 ，则更新k-means方法的参数K值并重新基于任务属性对任务集中的任务进行聚类，重置计数参数 ；如果 等于 ，则用最优目标函数值对应的最优个体替换掉新的种群内目标函数值最小的个体，并重置计数参数 ；如果 等于 ，则对新的种群中目标函数值最大的个体进行局部优化，随机生成一个新的个体并删除新的种群中目标函数值最小的个体，重置计数参数 ；步骤3.3.6：将新的种群中最大目标函数值记录为上一代种群最大目标函数值；步骤3.4：将最优目标函数值对应的个体作为测控方案输出。 4.根据权利要求3所述的方法，其特征在于，步骤3.3.1中：对种群内每一个个体生成测控方案初始解的方法是任务安排算法，具体为：对任务集中的所有任务按照编码序列依次按照可见时间窗顺序尝试安排给每个任务，如果全部时间窗都已经尝试且安排成功，则输出安排成功的结果作为初始解，否则，继续尝试安排；对每一个任务的具体安排方法为：1)：计算任务 最早实际可用时间 和最晚实际可用时间 ；2)：如果任务 在天线 的第 个时间窗长度大于任务 要求的测控时间长度，即 ，并且任务 实际可用时间长度大于任务 的测控时间长度，即 ，则转至步骤3)；否则，继续安排下一个任务；3)：将任务t最早实际可用时间 作为任务开始时间，如果任务t最早实际可用时间 等于任务 安排在天线 上第 个可见时间窗的开始时间 ，转至步骤4)；否则，转至步骤5)；4)：将任务 安排在天线 上第 个可见时间窗 ，将该窗口剩余时间窗更新为一个新时间窗 ；5)：将任务 安排在天线 上第 个可见时间窗 ，将该窗口剩余时间窗更新为两个新的时间窗 和 。 5.根据权利要求3所述的方法，其特征在于，步骤3.2中生成初始化种群的方法是使用多种启发式初始化方法生成初始化种群，所述初始化种群中存在各种启发式初始化方法生成的个体。 6.根据权利要求3所述的方法，其特征在于，步骤3.3.4中使用基于聚类的交叉方法是指：将所有任务按照任务属性使用k-means聚类方法划分成K类任务；交叉时，分别从属于两组不同类别的任务中选择相等长度的基因片段进行交叉，任务的类别根据轮盘赌进行选择。 7.根据权利要求6所述的方法，其特征在于，步骤3.3.4中使用基于聚类的变异方法包括两种，一种是同一类别中的变异，另一种是不同类别中变异，在每一次变异操作中随机选择两种变异方式中的一种执行变异操作；同一类别中的变异是指将个体内处在同一个类别内的两个任务进行位置交换；不同类别中的变异是指将个体内处在不同类别中的两个任务交换位置。 8.根据权利要求3所述的方法，其特征在于，步骤3.1中基于聚类的方法是基于任务的特征进行聚类，所述任务的特征包括任务的最早允许开始时间、最晚允许结束时间、收益、任务要求测控时间长度，当K值更新重新进行聚类时，增加任务是否被成功安排这个特征。 9.一种基于聚类的卫星测控调度系统，其特征在于，包括以下模块：输入模块：用于获取可调度的卫星资源、地面站资源、任务集以及卫星看见地面站的时间窗集合；模型构建模块：用于根据步骤1中所获取的内容构建混合整数规划模型；所述混合整数规划模型是：目标函数为： （1）其中， 表示任务 的收益， 为0-1决策变量，表示任务 是否安排在天线 上第 个可见时间窗,1为安排，0为否， 表示任务， T 表示任务集， 表示天线， 表示天线集合， 表示任务 安排在天线 上第 个可见时间窗， 表示任务 安排在天线 上的时间窗集合；约束条件是： （2）式2表明任务需要在允许的开始时间之后开始执行任务； 表示任务 安排在天线 上第 个可见时间窗上的实际的测控时间长度， 表示任务 要求的测控时间长度； （3）式3表明任务需要在允许的结束时间之前完成任务； 表示任务 安排在天线 上第 个可见时间窗上的实际开始时间, 表示任务 安排在天线 上第 个可见时间窗上的结束时间； （4）式4表明任务最多可以执行一次； 表示任务 安排在天线 上第 个可见时间窗上的的最早允许开始时间； （5）式5表明任务实际执行时间应当与要求时间相同； 表示任务 安排在天线 上第 个可见时间窗上的的最晚允许结束时间； （6）式6表明任务执行过程需要在一个地面站时间范围内； 表示任务 安排在天线 上第 个可见时间窗的开始时间； （7）式7表明每个任务只能由一个天线服务； （8）式8表明每个任务只能在一个可见的时间窗口内执行； 表示任务 安排在天线 上第 个可见时间窗的结束时间； （9）式9表明每个任务在全部天线上最多执行一次； （10）式10表明每个任务在全部时间窗内最多执行一次； （11）式11表明任务在规划周期内最多被执行一次； （12）式12表明两个任务要满足任务转换时间的间隔要求； 表示任务之间的转换时间；求解模块：用于对所述混合整数规划模型进行求解；方案输出模块：用于将求解得到的测控方案输出。