基于分解优化的多星合成观测调度算法

某些卫星的侧摆性能较差, 必须进行合成观测以提高观测效率. 研究了多星联合对地观测中的任务合成观测调度问题. 提出了将原问题分解为任务分配与任务合成的分解优化思路. 任务分配为任务选择卫星资源及时间窗口; 任务合成则针对该分配方案,将分配到各卫星的任务按照轨道圈次分组, 分别进行最优合成. 采用蚁群优化算法(Ant colony optimization, ACO)求解任务分配问题, 通过自适应参数调整及信息素平滑策略, 实现全局搜索和快速收敛间的平衡.提出了基于动态规划的最优合成算法, 求解任务合成子问题,能够在多项式时间内求得最优合成方案. 依据分配方案的合成结果, 得到优化方案的特征信息, 反馈并引导蚁群优化算法对任务分配方案的搜索过程. 大规模测试算例验证了本文算法的效率.     

复杂约束条件下卫星观测多目标获取优化算法

在复杂约束条件下,卫星对多目标的获取效率成为卫星观测研究领域的热点问题。提出基于贪婪方法的实际复杂约束条件下多目标获取优化算法。该方法基于传感器约束模型对多目标进行可视筛选,基于卫星侧摆约束模型对可视目标实现可访问互斥目标集合分类,采用考虑能源约束模型的贪婪优化算法获取最优目标访问路径。实验结果表明,实际复杂约束条件下,该算法可在最少能源消耗情况下获取更多目标,获取效率及能耗明显优于传统的蚁群算法和遗传算法。     

敏捷凝视卫星密集点目标聚类与最优观测规划

针对敏捷凝视卫星密集点目标观测规划问题,提出一种快速观测任务聚类策略和启发式蚁群优化算法.首先,针对敏捷凝视卫星视场范围特点,提出基于顶点度的团划分算法,解决密集点观测任务聚类问题,形成系列团观测目标,有效提高观测效率;其次,为得到最优团目标观测序列,考虑目标可见时间窗口约束以及卫星敏捷机动能力约束,构建基于多目标观测收益和姿态机动能耗的性能指标,实现能量高效的任务规划;再次,为克服传统蚁群算法易陷入局部极小值和收敛较慢的缺点,设计一种同时考虑目标点优先级、目标可见时间窗口、目标之间卫星姿态转换时间等因素的启发式蚁群算法;最后,选取大规模密集地面目标验证所提出算法的可行性和高效性.     

基于蚁群算法的卫星地面站任务规划方法

卫星在运行过程中,与地面站之间存在许多可见窗口,只有在可见窗口之内,地面站才能直接对卫星进行观测和操作,因此,如何合理调度地面站资源,实现最大化利用星地可见窗口是一个重要的课题。本文定义卫星与地面站之间的可见窗口为任务集合,将蚁群算法应用于构造有效的任务调度序列,求解任务最大执行时间,即可利用的可见窗口时间最长。实验数据显示,蚁群算法有着优良的调度结果,同时其调度结果亦优于FCFS和贪婪算法。由此可以看出,该算法能有效求解卫星地面站任务调度问题。     

基于免疫粒子群算法的多星观测调度研究

多星观测调度是一个复杂的组合优化问题,且为NP难题.目前常用解决方法是采用智能搜索算法在搜索空间寻找近似最优解.针对上述问题,首先探讨了国内外成像侦察卫星调度算法的研究现状,然后阐述了传统微粒子群优化算法与免疫粒子群优化算法的特点,并对带有多个时间窗口约束的多星观测问题建立了数学模型.在此基础上,提出一种用于解决多星观测调度问题的免疫粒子群算法.实验结果表明,免疫算法收敛速度快,可以很好地逼近精确解,并具有较强的搜索能力.     

基于改进烟花算法的密集任务成像卫星调度方法

传统卫星调度模型一般比较简单,当问题规模较大、任务比较集中时,往往会出现任务之间相互排斥,任务收益较低等缺点。针对这个问题,提出一种基于改进烟花算法（IFWA）的密集任务成像卫星调度方法。该方法在分析密集任务处理及成像卫星观测特点的基础上,首先对任务进行合成约束分析,然后基于合成任务综合考虑成像卫星可观测时间、任务间姿态调整时间、成像卫星能量和容量等约束因素,建立基于任务合成的多星密集任务调度约束满足问题（CSP）模型,最后改进烟花算法对该模型进行求解,利用精英选择策略在保证种群多样性同时加快了算法的收敛,得到较优的卫星调度方案。仿真结果表明该模型相比没有考虑任务合成因素,收益平均增加30%~35%,改进算法后效率上提升32%~45%,有效保证了调度方案的可行性和有效性。     

基于反向差分算法的航空发动机装配车间优化调度

航空发动机装配车间的各个生产线的优化调度问题是一个典型的具有可重入特性的生产调度问题,从调度优化难易的角度来看,属于NP难题。针对这个问题,在分析航空发动机的工艺流程与特点以及航空发动机的数学模型之后,以最小化最大完工时间为调度优化问题的目标函数,提出了基于反向差分进化算法的优化调度方案。最后,仿真实验表明,该方案对于解决优化调度问题是行之有效的。     

实际复杂约束条件下多星区域覆盖优化算法

利用多星协同对大面积区域成像侦测,要求在最短的时间内完成对给定目标区域的完全覆盖,得到卫星每次过境最优侧视观测方案。现有覆盖算法具低效耗时技术瓶颈,有空间覆盖率及时效性局限。充分利用卫星每次过境观测机会,综合考虑相机分辨率、太阳高度角、地面精度等约束条件,依据不同卫星侧摆能力、传感器可视性能以及卫星轨道参数特征,对区域目标进行量化覆盖分析,建立网格划分模型,提出基于一次覆盖策略的覆盖优化算法。该算法能适应实际复杂约束条件,在实际问题规模下,具有良好的效率,能满足工业精度要求。在仿真应用中检验了该算法的有效性和适应性。     

航班滑行路径规划和停机位分配联合优化

针对机场的航班滑行路径规划和停机位分配的联合优化调度问题,构建基于冲突回避的滑行道与停机位联合调度模型,并提出改进的自适应差分进化算法求解问题.以最小化航班的滑行时间和旅客转机的行走时间为优化目标,建立非线性混合整数规划联合调度模型.设计考虑了滑行冲突的路径规划算法,完成航班的滑行路径分配,并通过自适应动态调整差分进化...     

基于改进蚁群协同算法的枢纽机场场面滑行道优化调度模型

滑行道连接停机位和跑道,是机场场面调度的重要关键环节。基于飞机滑行时的冲突约束和跑道资源的动态分配,采用改进蚁群协同算法与滑动窗口控制相结合的方法,对滑行道进行优化调度。在保证滑行道零冲突、兼顾单个航班滑行时间的前提下,缩小机场进出港航班总滑行时间。对国内某枢纽机场的滑行道调度仿真实验表明,所提出的方法和模型具有明显的优势,可为枢纽机场的场面滑行调度提供决策支持。     

数据驱动的多星任务网络预测调度算法

多星任务调度是具有NP-hard特性的优化问题,随着卫星资源规模和任务需求规模的双重增长,传统调度方法求解效率不高.在轨卫星在常年运行过程中积累了丰富的调度数据.针对大规模多星任务调度场景,建立多星多波束任务调度模型,并提出数据驱动的多星任务网络预测调度算法对其求解.以分割的思想,实现多星场景下任务可调度性预测.从历史调度数据中,提取设定的3个静态特征和5个动态特征,构建并训练预测网络,预测任务被不同卫星完成的概率,并以冲突避免、负载均衡等为原则,得到初始任务和资源卫星的分配方案.进一步设计双链结构的进化算法,以双链编码形式表征上述关系,配合设计的交叉、修复等进化算子,优化初始方案中的任务序列与资源分配关系,输出最终任务调度方案.仿真结果表明,与改进蚁群算法、混合遗传算法和数据驱动并行调度算法相比,所提出算法在运行时间、方案收益和卫星负载均衡3方面均有较好的表现.     

面向多星任务规划问题的改进遗传算法

卫星数量的快速增加为管控卫星的工作增加了很大的难度,如何有效地进行任务规划,有效管理卫星资源,成为了卫星领域的一个重要问题.针对此问题,本文构建了多星任务规划的数学模型,将最大化任务收益作为优化目标.本文分析了问题的难点并提出了一种包含两种优化策略的改进遗传算法,包括全局优化和局部优化两部分.全局优化和局部优化根据种群改进情况进行自适应切换.通过两种优化方法的结合可以提升任务规划的效果.本文还提出了一种任务规划算法,用于为改进遗传算法得到的任务序列选择合适的任务执行时间.仿真实验证明本文提出的改进遗传算法可以很好地解决多星任务规划问题,与对比算法相比可以得到更优的规划结果.改进遗传算法有很好的工程应用前景.     

基于禁忌搜索算法测地卫星任务调度研究

研究测地卫星调度问题,它是一个复杂的组合优化问题,涉及多个卫星,大量的任务与约束限制,何时和如何执行每项任务。分析了问题的主要约束,在合理的假设基础上建立了带有时间窗口多资源调度问题模型,提出一种改进的禁忌搜索算法求解该模型。用实例对模型和算法进行了验证,并将结果与动态规划方法求解结果比较分析,结果表明模型和算法是有效的。     

一种解决卫星网络通信冲突的调度算法

在卫星网络中多颗卫星同时对一颗卫星进行通信申请会产生任务冲突问题。为此,提出一种基于动态优先级的调度算法。建立卫星通信任务模型,利用任务执行紧迫性表达任务截止期与空余时间这2个时间约束,并根据卫星网络的特点,通过调整参数p控制紧迫性对任务优先级的影响程度。利用STK场景建立冲突模型进行仿真实验,结果证明该算法的任务完成率相比FCFS算法提高了3.9%。     

基于改进遗传算法的星地任务优化调度研究

星地任务优化调度是利用特定的星地资源合理地安排星地任务。由于星地任务众多而资源有限,而且星地任务受星地可见性以及多方面约束,星地任务调度问题十分复杂。针对星地任务的特点,建立了星地任务调度问题模型,提出了基于改进遗传算法的星地任务优化调度算法。算法采用按适应度排名轮盘赌选择、顺序交叉、随机对换变异的算法要素。针对遗传算法局部搜索能力弱的特点,提出了利用爬山算法优化新一代个体的方法,以增强遗传算法的局部搜索能力,给出了基于改进遗传算法的星地任务调度算法。     

基于改进蚁群算法的成像卫星调度方法

成像卫星调度问题中约束条件数量众多且复杂,战场环境中,快速决策的要求增加了成像卫星任务调度的难度。针对这个问题,提出了一种加入精英策略的改进蚁群算法的多卫星成像调度方法,对算法的状态转移规则、信息素更新规则做了详细描述;并提出了基于启发式规则的任务路径处理流程,以此产生调度方案,评价路径优劣,反馈给蚂蚁路径搜索阶段。通过实例计算,并与贪婪算法和遗传算法结果对比,说明本方法能够获得更高质量的求解结果。     

基于改进CBS算法的自动化码头多AGV无冲突路径规划

针对自动化集装箱码头上自动引导车（automated guided vehicle,AGV）数量增加导致冲突更频繁。提出一种改进的基于冲突的搜索（conflict based search,CBS）算法。底层采用基于曼哈顿距离的A*算法,上层结合二叉树原理建立冲突树对AGV之间的冲突进行规避。以最小化AGV在岸桥和堆场之间的总路径长度为目标,使用栅格法建立AGV路网模型。考虑AGV之间的点冲突与边冲突,将自动化码头多AGV无冲突路径规划问题规约为多智能体寻径问题。实验结果表明,所提出的算法在保证堵塞率为0%的前提下,缩短总路径长度并提高运算速度,验证算法的有效性。     

考虑邻域结构动态调整的多星应急调度算法

实际应用中的卫星调度方案往往受到外界因素的影响,例如电磁干扰、卫星失效、云层遮挡以及新任务的动态到达等,需要在短时间内对原始调度方案进行调整并生成新的调度方案,以保证卫星系统的稳定性.对此,考虑新任务到达情况下的卫星应急调度,建立多星协同应急调度的整数规划模型,并提出一种基于动态邻域结构的卫星应急调度算法(satellite emergency scheduling algorithm based on dynamic neighborhood, SESA-DN).设计多种类型的邻域结构以及动态的邻域选择策略,能够根据任务完成情况进行有效反馈,通过对应急任务的插入与替换生成卫星应急调度方案;同时,构建多星应急调度场景,通过大量仿真实验将SESA-DN算法与多种对比算法进行比较.实验结果表明, SESA-DN算法的稳定性优于对比算法,对于多星协同动态调度问题具有很好的适用性.     

Real-time task scheduling by multiobjective genetic algorithm

Real-time tasks are characterized by computational activities with timing constraints and classified into two categories: a hard real-time task and a soft real-time task. In hard real-time tasks, tardiness can be catastrophic. The goal of hard real-time tasks scheduling algorithms is to meet all tasks’ deadlines, in other words, to keep the feasibility of scheduling through admission control. However, in the case of soft real-time tasks, slight violation of deadlines is not so critical.In this paper, we propose a new scheduling algorithm for soft real-time tasks using multiobjective genetic algorithm (moGA) on multiprocessors system. It is assumed that tasks have precedence relations among them and are executed on homogeneous multiprocessor environment.The objective of the proposed scheduling algorithm is to minimize the total tardiness and total number of processors used. For these objectives, this paper combines adaptive weight approach (AWA) that utilizes some useful information from the current population to readjust weights for obtaining a search pressure toward a positive ideal point. The effectiveness of the proposed algorithm is shown through simulation studies.