基于贪婪的自适应退火合同网算法的卫星任务规划方法

摘要

本发明提供一种基于贪婪的自适应退火合同网算法的卫星任务规划方法、系统、存储介质和电子设备，涉及卫星调度领域。本发明中根据预设的从卫星数学模型，各从卫星针对当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案；根据预设的主卫星数学模型，主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案；并最终输出全局最优的卫星任务规划方案。通过建立双层决策数学模型解决了传统合同网未考虑的分布式卫星任务分配和调度问题中存在的主目标和子目标不一致性问题；通过多轮招标以及投标的过程来得到质量更高的方案。

说明书

技术领域

本发明涉及卫星调度领域，具体涉及一种基于贪婪的自适应退火合同网算法的卫星任务规划方法、系统、存储介质和电子设备。

背景技术

随着我国卫星技术的不断发展，卫星发挥的作用也越来越大。其中，遥感卫星能够快速准确的获取地表信息，应用范围广泛，已成为国家综合实力的重要标志。同时，也在环境灾害防治、城市建设规划、气象预报等邻域发挥重要作用。

国内外针对卫星调度问题的研究集中在多星多任务调度。传统的多星多任务规划问题多采用基于地面离线规划的集中式架构进行处理，但集中式规划存在任务响应能力差、执行效率低等诸多缺陷。分布式架构以其通信分散、鲁棒性好等优点成为当前多星任务规划的主要架构方式，合同网是解决分布式任务规划的一种有效方法，以其分配效率高，适应动态环境强等特点在分布式卫星规划中得到广泛应用。

合同网是针对任务和资源分配所提出的经典协商策略。合同网将系统中的成员角色分为管理者和合同者通过模仿经济行为中的“招标投标中标”机制实现任务分配。各代理之间通过标值进行相互协作和任务竞争，在局部最优的系统配置上追求全局的最优，从而以最优的系统配置和最低代价完成任务，合同网协议是解决分布式卫星任务分配的一种经典且有效的方法，主要工作流程为：主星发布任务，各从卫星针对任务进行投标，主星从各投标方案中选择一个中标方案并将任务分配给中标星。

但是，在实际分布式卫星任务规划中，主目标和子目标并不总是完全一致的，需要考虑到目标的不一致性。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种基于贪婪的自适应退火合同网算法的卫星任务规划方法、系统、存储介质和电子设备，解决了在实际分布式卫星任务规划中，未考虑主目标和子目标不总是完全一致的技术问题。

(二)技术方案

为实现以上目的，本发明通过以下技术方案予以实现：

一种基于贪婪的自适应退火合同网算法的卫星任务规划方法，其特征在于，包括若干的从卫星和用于决策的主卫星，该方法具体包括：

S1、所述主卫星获取待观测任务序列，进入循环招投标过程，令q＝1，设定循环终止次数；

S2、所述主卫星开始第q次招投标，获取当前未进行安排的任务序列，若当前未进行安排的任务序列为空，转S5；否则，转S3；

S3、所述主卫星将当前未进行安排的任务序列广播至各所述从卫星；根据预设的从卫星数学模型，各所述从卫星针对该当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，若各所述投标方案都为空，转S5；否则，转S4；

S4、根据预设的主卫星数学模型，所述主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案，并更新中标的从卫星的规划方案，以及更新当前未进行安排的任务序列；

S5、若所述待观测任务序列中所有任务都被安排，或者没有投标方案，或者总观测收益连续达到所述循环终止次数相同，则规划结束，输出全局最优的卫星任务规划方案；否则，令q＝q+1，转S2。

优选的，所述S3中的从卫星数学模型包括以综合收益最大化的目标函数：

以及第一约束条件：

OTS

e

其中，公式(2)表示唯一性约束，即一个任务最多被观测一次；公式(3)表示任务进行观测时必须要满足时间窗要求；公式(4)表示任务的实际观测结束时间和任务观测持续时间的关系；公式(5～6)表示卫星规划中的能量约束以及能量消耗计算方式；公式(7)表示存储约束；公式(8)表示生成的方案所产生的扰动的计算方式；

主卫星S′，从卫星集合S＝{S

T＝{t

t

OTW

W

e

e

E

c

C

rd

优选的，所述S5中主卫星数学模型包括以总观测收益最大化的目标函数：

以及第二约束条件：

ET

其中，公式(9)表示任务数量之间在招投标过程中的约束；公式(10)表示规划时间截止约束；公式(11)表示规划时间截止约束；

ET

优选的，所述rd

任务安排到原任务序列的空闲时间片内，此时rd

任务安排导致原任务序列上的任务被替换，此时0＜rd

任务安排导致原任务序列上的任务不能观测，此时rd

优选的，所述S3中采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，具体包括：

S10、各所述从卫星以收益最大的贪婪规则，尝试依次将当前未进行安排的任务序列中的任务插入到该从卫星的观测方案中，获取各所述从卫星针对该当前未进行安排的任务序列的初始解；

S20、设定初始温度、等温步长、降温速率，将所述初始解作为当前最优解；

S30、进入循环，循环的次数为所述等温步长的大小；每次选择一种预设的算子生成邻域解，以Metropolis准则判断是否接受该邻域解，并基于自适应算子规则更新各算子的被选择概率，更新当前最优解；

S40、此温度下迭代完成，根据所述降温速率进行降温；

S50、循环S30～S40进行方案迭代更新，满足终止条件时停止循环；

S60、各所述从卫星针对该当前未进行安排的任务序列获取当前最优解，并根据当前最优解与该当前未进行安排的任务序列的交集，获取对应的当前投标方案。

优选的，所述S30中预设的算子包括插入、删除以及移位算子；基于自适应算子规则更新各算子的被选择概率，具体包括：

S100、首先为上述三种算子分别赋予相同的被选择概率，进入退火过程；

S200、选择邻域算子Q

S300、比较初始解和该邻域解的综合收益大小，若该邻域解的综合收益值小于初始解的综合收益值，则降低算子Q

优选的，所述S1中主卫星获取待观测任务序列后，将所述待观测任务序列按照收益从大到小进行重排序；若存在多个收益相同的任务，按照任务观测持续时间由小到大进行二次排序，之后再进入循环招投标过程。

一种基于贪婪的自适应退火合同网算法的卫星任务规划系统，包括若干的从卫星和用于决策的主卫星，该系统具体包括：

任务获取模块，用于执行S1、所述主卫星获取待观测任务序列，进入循环招投标过程，令q＝1，设定循环终止次数；

招投标开始模块，用于执行S2、所述主卫星开始第q次招投标，获取当前未进行安排的任务序列，若当前未进行安排的任务序列为空，转方案确认模块执行S5；否则，转方案生成模块执行S3；

方案生成模块，用于执行S3、所述主卫星将当前未进行安排的任务序列广播至各所述从卫星；根据预设的从卫星数学模型，各所述从卫星针对该当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，若各所述投标方案都为空，转方案确认模块执行S5；否则，转方案评标模块执行S4；

方案评标模块，用于执行S4、根据预设的主卫星数学模型，所述主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案，并更新中标的从卫星的规划方案，以及更新当前未进行安排的任务序列；

方案确认模块，用于执行S5、若所述待观测任务序列中所有任务都被安排，或者没有投标方案，或者总观测收益连续达到所述循环终止次数相同，则规划结束，输出全局最优的卫星任务规划方案；否则，令q＝q+1，转招投标开始模块执行S2。

一种存储介质，其存储有用于基于贪婪的自适应退火合同网算法的卫星任务规划的计算机程序，其中，所述计算机程序使得计算机执行如上所述的卫星任务规划方法。

一种电子设备，其特征在于，包括：

一个或多个处理器；

存储器；以及

一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行如上所述的卫星任务规划方法。

(三)有益效果

本发明提供了一种基于贪婪的自适应退火合同网算法的卫星任务规划方法、系统、存储介质和电子设备。与现有技术相比，具备以下有益效果：

本发明中，根据预设的从卫星数学模型，各从卫星针对当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案；根据预设的主卫星数学模型，主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案；并最终输出全局最优的卫星任务规划方案。通过建立双层决策数学模型解决了传统合同网未考虑的分布式卫星任务分配和调度问题中存在的主目标和子目标不一致性的问题；通过多轮招标以及投标的过程来得到质量更高的方案。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例的提供的一种基于贪婪的自适应退火合同网算法的卫星任务规划方法的流程示意图；

图2～4为本发明实施例的提供的插入、删除以及移位算子的示意图；

图5为本发明实施例的提供的一种投标方案筛选方式的示意图；

图6为本发明实施例的提供的一种基于贪婪的自适应退火合同网算法的卫星任务规划系统的结构框图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本申请实施例通过提供一种基于贪婪的自适应退火合同网算法的卫星任务规划方法、系统、存储介质和电子设备，解决了在实际分布式卫星任务规划中，未考虑主目标和子目标不总是完全一致的技术问题。。

本申请实施例中的技术方案为解决上述技术问题，总体思路如下：

本发明实施例中，根据预设的从卫星数学模型，各从卫星针对当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案；根据预设的主卫星数学模型，主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案；并最终输出全局最优的卫星任务规划方案。通过建立双层决策数学模型解决了传统合同网未考虑的分布式卫星任务分配和调度问题中存在的主目标和子目标不一致性的问题；通过多轮招标以及投标的过程来得到质量更高的方案。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

实施例：

第一方面，如图1所示，本发明实施例提供了一种基于贪婪的自适应退火合同网算法的卫星任务规划方法，包括若干的从卫星和用于决策的主卫星，该方法具体包括：

S1、所述主卫星获取待观测任务序列，进入循环招投标过程，令q＝1，设定循环终止次数；

S2、所述主卫星开始第q次招投标，获取当前未进行安排的任务序列，若当前未进行安排的任务序列为空，转S5；否则，转S3；

S3、所述主卫星将当前未进行安排的任务序列广播至各所述从卫星；根据预设的从卫星数学模型，各所述从卫星针对该当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，若各所述投标方案都为空，转S5；否则，转S4；

S4、根据预设的主卫星数学模型，所述主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案，并更新中标的从卫星的规划方案，以及更新当前未进行安排的任务序列；

S5、若所述待观测任务序列中所有任务都被安排，或者没有投标方案，或者总观测收益连续达到所述循环终止次数相同，则规划结束，输出全局最优的卫星任务规划方案；否则，令q＝q+1，转S2。

本发明实施例通过建立双层决策数学模型解决了传统合同网未考虑的分布式卫星任务分配和调度问题中存在的主目标和子目标不一致性的问题；通过多轮招标以及投标的过程来得到质量更高的方案。

下面将结合具体内容详细介绍上述技术方案的各个步骤：

首先需要说明的是，传统合同网采取的“单任务投标，单代理中标”模式会产生较大的协商通信量，本发明实施例设计了全任务投标策略来减少协商次数；在每一轮招投标过程中，主卫星都会更新当前未进行安排观测的任务序列，将其作为招标信息进行招标，各从卫星都会进行投标方案的筛选来决定是否投标，主要步骤如下：

S1、所述主卫星获取待观测任务序列，进入循环招投标过程，令q＝1，设定循环终止次数N

主卫星获取待观测任务序列后，将所述待观测任务序列按照收益从大到小进行重排序；若存在多个收益相同的任务，按照任务观测持续时间由小到大进行二次排序，之后再进入循环招投标过程。

S2、所述主卫星开始第q次招投标，获取当前未进行安排的任务序列，若当前未进行安排的任务序列为空，转S5；否则，转S3。

S3、所述主卫星将当前未进行安排的任务序列广播至各所述从卫星；根据预设的从卫星数学模型，各所述从卫星针对该当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，若各所述投标方案都为空，转S5；否则，转S4。

在各从卫星获得招标信息后需要生成对应的投标方案，本步骤设计了一种基于贪婪的自适应退火合同网算法用于从卫星投标方案的生成，其中算法编码方式采用整数编码方式，具体内容见下：

所述从卫星数学模型包括以综合收益最大化的目标函数：

以及第一约束条件：

OTS

e

其中，公式(2)表示唯一性约束，即一个任务最多被观测一次；公式(3)表示任务进行观测时必须要满足时间窗要求；公式(4)表示任务的实际观测结束时间和任务观测持续时间的关系；公式(5～6)表示卫星规划中的能量约束以及能量消耗计算方式；公式(7)表示存储约束；公式(8)表示生成的方案所产生的扰动的计算方式；

主卫星S′，从卫星集合S＝{S

T＝{t

t

OTW

W

e

e

E

c

C

rd

具体的，所述rd

任务安排到原任务序列的空闲时间片内，此时rd

任务安排导致原任务序列上的任务被替换，此时0＜rd

任务安排导致原任务序列上的任务不能观测，此时rd

此外，所述S3中采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，具体包括：

S10、各所述从卫星以收益最大的贪婪规则，尝试依次将当前未进行安排的任务序列中的任务插入到该从卫星的观测方案中，获取各所述从卫星针对该当前未进行安排的任务序列的初始解。

S20、设定初始温度、等温步长、降温速率，将所述初始解作为当前最优解。

S30、进入循环，循环的次数为所述等温步长的大小；每次选择一种预设的算子生成邻域解，以Metropolis准则判断是否接受该邻域解，并基于自适应算子规则更新各算子的被选择概率，更新当前最优解。

如图2～4所示，所述S30中预设的算子包括插入、删除以及移位算子；基于自适应算子规则更新各算子的被选择概率，具体包括：

S100、首先为上述三种算子分别赋予相同的被选择概率，进入退火过程；

S200、选择邻域算子Q

S300、比较初始解和该邻域解的综合收益大小，若该邻域解的综合收益值小于初始解的综合收益值，则降低算子Q

S40、此温度下迭代完成，根据所述降温速率进行降温。

S50、循环S30～S40进行方案迭代更新，满足终止条件时停止循环。

S60、各所述从卫星针对该当前未进行安排的任务序列获取当前最优解，如图5所示，并根据当前最优解与该当前未进行安排的任务序列的交集，获取对应的当前投标方案。

由上述可知，本发明实施例设计了基于贪婪的自适应退火合同网算法，首先通过贪婪策略能较快的得到一个较好的初始解，其次通过设计了多种算子增强了邻域解的多样性，最后通过自适应算子策略进一步增强邻域解生成的合理性。

S4、根据预设的主卫星数学模型，所述主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案，并更新中标的从卫星的规划方案，以及更新当前未进行安排的任务序列。

所述主卫星数学模型包括以总观测收益最大化的目标函数：

以及第二约束条件：

ET

其中，公式(9)表示任务数量之间在招投标过程中的约束；公式(10)表示规划时间截止约束；公式(11)表示规划时间截止约束；

ET

S5、若所述待观测任务序列中所有任务都被安排，或者没有投标方案，或者总观测收益连续达到所述循环终止次数相同，则规划结束，输出全局最优的卫星任务规划方案；否则，令q＝q+1，转S2。

第二方面，如图6所示，本发明实施例提供了一种基于贪婪的自适应退火合同网算法的卫星任务规划系统，其特征在于，包括若干的从卫星和用于决策的主卫星，该系统具体包括：

任务获取模块，用于执行S1、所述主卫星获取待观测任务序列，进入循环招投标过程，令q＝1，设定循环终止次数；

招投标开始模块，用于执行S2、所述主卫星开始第q次招投标，获取当前未进行安排的任务序列，若当前未进行安排的任务序列为空，转方案确认模块执行S5；否则，转方案生成模块执行S3；

方案生成模块，用于执行S3、所述主卫星将当前未进行安排的任务序列广播至各所述从卫星；根据预设的从卫星数学模型，各所述从卫星针对该当前未进行安排的任务序列，采用基于贪婪的自适应退火合同网算法生成对应的当前投标方案，若各所述投标方案都为空，转方案确认模块执行S5；否则，转方案评标模块执行S4；

方案评标模块，用于执行S4、根据预设的主卫星数学模型，所述主卫星采用总观测收益最大化评标策略进行评标，从各所述投标方案中选择中标方案，并更新中标的从卫星的规划方案，以及更新当前未进行安排的任务序列；

方案确认模块，用于执行S5、若所述待观测任务序列中所有任务都被安排，或者没有投标方案，或者总观测收益连续达到所述循环终止次数相同，则规划结束，输出全局最优的卫星任务规划方案；否则，令q＝q+1，转招投标开始模块执行S2。

第三方面，本发明实施例提供了一种存储介质，其存储有用于基于贪婪的自适应退火合同网算法的卫星任务规划的计算机程序，其中，所述计算机程序使得计算机执行如上所述的卫星任务规划方法。

第四方面，本发明实施例提供了一种电子设备，包括：

一个或多个处理器；

存储器；以及

一个或多个程序，其中所述一个或多个程序被存储在所述存储器中，并且被配置成由所述一个或多个处理器执行，所述程序包括用于执行如上所述的卫星任务规划方法。

可理解的是，本发明实施例提供的基于贪婪的自适应退火合同网算法的卫星任务规划系统、存储介质和电子设备与本发明实施例提供的基于贪婪的自适应退火合同网算法的卫星任务规划方法相对应，其有关内容的解释、举例和有益效果等部分可以参考卫星任务规划方法中的相应部分，此处不再赘述。

综上所述，与现有技术相比，具备以下有益效果：

1、本发明实施例通过建立双层决策数学模型解决了传统合同网未考虑的分布式卫星任务分配和调度问题中存在的主目标和子目标不一致性的问题；通过多轮招标以及投标的过程来得到质量更高的方案。

2、本发明实施例设计了基于贪婪的自适应退火合同网算法，首先通过贪婪策略能较快的得到一个较好的初始解，其次通过设计了多种算子增强了邻域解的多样性，最后通过自适应算子策略进一步增强邻域解生成的合理性。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。