【作者】 陈祥国；

【导师】 武小悦；

【作者基本信息】 国防科学技术大学 ， 控制科学与工程， 2010， 博士

【摘要】 卫星数传调度是亟待解决的重要现实问题和理论难题,一般启发式调度算法已难以满足卫星数传调度的需要。基于群体智能的蚁群优化算法已经成为求解大规模组合优化问题的代表性算法,为了探索蚁群优化算法在该问题中应用的可行性,为卫星数传调度的蚁群优化提供解决方案,本文基于蚁群优化理论,提出了三种基于解构造图的卫星数传调度蚁群优化算法,并通过仿真应用系统对算法进行了实验分析和比较。本文主要研究工作及创新点包括:(1)卫星数传调度模型为了评价蚁群优化算法获得的卫星数传调度方案,提出了卫星数传调度评价指标体系,包括任务调度收益率、各卫星任务调度收益均衡度、地面资源可见时间窗口利用率、各地面资源数传负荷均衡度等评价指标。建立了卫星数传调度模型,对卫星资源、地面资源、时间窗口、数传任务、调度约束等基本建模要素进行了形式化描述。(2)卫星数传调度的启发式信息为了利于蚁群优化算法进行知识利用,提高算法性能,提出了卫星数传调度的启发式信息体系,该体系包括任务调度启发式信息和资源分配启发式信息。提出了基于任务开始时间、任务收益属性、任务调度灵活度和任务调度冲突度的任务调度规则及启发式信息计算方法。任务调度启发式信息可用于ACO算法构造任务调度序列。提出了基于资源优先级、可见时间窗口冲突、可见窗口时间点和可见窗口持续时间的资源分配规则及启发式信息计算方法,资源分配启发式信息可用于ACO算法构造任务的资源分配序列和可行解。(3)基于任务调度关系图的卫星数传调度ACO算法为了研究基于任务调度关系的解构造图在卫星数传调度蚁群优化中的可行性,提出了任务调度关系图及基于该解构造图的卫星数传调度ACO算法。算法中,为了任务调度序列构造的多样性,提出了自适应概率决策模型;为了提高利用任务调度启发式信息的灵活性,提出了任务调度启发式信息随机选择策略;为了获得可行解,提出了基于资源分配启发式信息的迭代解成分构造算法;为了改善可行解,提出了基于资源分配启发式信息的迭代修复局部搜索;为了减少算法运行时间,提出了基于最大可能冲突任务集的搜索邻域确定算法;为了获得单目标至今最优解,提出了递阶全局信息素更新策略;为了获得多目标Pareto最优解集,提出了基于Pareto解偏离度的全局信息素更新策略。(4)基于任务调度位置图的卫星数传调度ACO算法为了研究基于任务调度位置的解构造图在卫星数传调度蚁群优化中的可行性,提出了任务调度位置图及基于该解构造图的卫星数传调度ACO算法。为了充分利用解构造图的环境信息,增强算法解构造能力,提出了基于信息素评价的自适应伪随机概率决策模型;为了加强算法对任务调度启发式的自主选择能力,提出了导引式任务调度启发式信息选择策略;为了改善蚁群构造解,提出了基于2-交换的迭代修复局部搜索改善可行解;为了增强算法的单目标优化能力,提出了基于信息素遗留的自适应全局信息素更新策略;为了获得距离Pareto前沿最近的Pareto最优解集,提出了基于Pareto解近似理想距离的全局信息素更新策略。(5)基于任务数传操作图的卫星数传调度ACO算法为了研究基于任务数传操作的解构造图在卫星数传调度蚁群优化中的可行性,提出了任务数传操作图及基于该解构造图的卫星数传调度ACO算法。算法采用伪随机概率决策模型,首先构造任务调度序列,然后构造每个任务的资源分配序列;每次迭代前通过随机加权综合计算任务调度启发式信息和资源分配启发式信息;为了增强任务调度序列构造的多样性,每次迭代后对列信息素向量执行基于混沌变异的信息素更新策略;为了避免单目标优化过早陷入局部最优,采用了具有补偿机制的全局信息素更新策略;为满足算法的多目标优化需求,提出了小生境的全局信息素更新策略。利用本文设计实现的仿真应用系统,针对上述三种基于不同解构造图的ACO算法进行了仿真实验分析和算法性能比较,结果表明:基于三种解构造图的单目标ACO算法都能获得比一般启发式算法更好的结果,大部分结果好于遗传算法,在大规模场景中的运算时间明显低于遗传算法;基于三种解构造图的多目标ACO算法都能获得Pareto最优解集,并且获得的Pareto解能支配一般启发式算法获得的大多数解,说明算法具有较强的多目标优化能力。相比而言,基于任务数传操作图的ACO算法性能最优,运算时间最短。基于其它两种解构造图的ACO算法性能相当,算法获得解的质量受解成分构造算法影响较大。更多还原

【Abstract】 Satellite data transmission scheduling (SDTS) is an important practical and difficult theoretical problem urgently to be solved. Ordinary heuristic scheduling algorithm is hard to satisfy the demand of satellite data transmission scheduling. Ant colony optimization (ACO) algorithm based on colony intelligent has already become a typical algorithm for large-scale combinatorial optimization problems. Based on ACO theory, this dissertation proposes three solution construction graph-based SDTS Ant colony optimization algorithms and analyses the algorithms by experiment of simulation application system for exploring the availability of application of ACO in the SDTS and providing solution for ACO in SDTS. The main work and contributions include:(1) The satellite data transmission scheduling modelThe evaluation index system of satellite data transmission scheduling is proposed for evaluating the scheduling solution of ACO algorithms. These indices include tasks scheduling earning rate, satellites tasks scheduling earnings balance degree, utilization ratio of visible time windows on ground resource, data transmission load proportion degree in ground resources and so on. This part of dissertation founded the satellites data transmission scheduling model and mathematically described the modelling element such as satellites resource, ground resource, time windows, data transmission task, scheduling constraints.(2) The heuristics of satellite data transmission schedulingIn order to improving the knowledge utilization and performance of ACO algorithms, the author proposes satellite data transmission scheduling heuristics system which includes task scheduling heuristics and resource allocation heuristics. Propose task scheduling rule and calculating method for its heuristics based on task starting time, task profit attribute, task scheduling flexible degree, task scheduling conflict degree. Task scheduling heuristics is used to construct the sequence of task scheduling for ACO algorithm. Propose resource allocation rule and calculating method for its heuristics based on priority of resource, conflict of visible time window, timeplot of visible time window, and duration of visible time window. Resource allocation heuristics is used to construct the sequence of resource allocation and feasible solution.(3) ACO algorithm for satellite data transmission scheduling based on task scheduling relations graphFor the purpose of reseaching the availability of task scheduling relations graph in SDTS, ACO algorithms for SDTS based on task scheduling relations graph are proposed. The algorithms makes use of a self-adapting probabilistic decision model for the diversity of tasks scheduling sequence construction, and random selecting strategy for agility of tasks scheduling heuristics, and iteration repair local search based on resource allocation heuristics for improving solutions constructed by ants. A step-up global pheromone updating strategy is proposed for single-objective ACO algorithm, and a global pheromone updating strategy based on Pareto solution offset degree is proposed for multi-objective ACO algorithm.(4) ACO algorithm for satellite data transmission scheduling based on task scheduling positions graphIn order to researching the availability of task scheduling positions graph in SDTS, ACO algorithms for SDTS based on the task scheduling positions graph are proposed. A self-adapting probabilistic decision model based on pheromone evaluations is proposed for utilize the environment information and enhance the solution construction ability of algorithm. A guided selection strategy for task scheduling heuristics according to best-so-far solution is proposed for strengthening the self-choosing ability of algorithm. Iteration repair local search based on 2-Opt are proposed in the algorithms in order to improving the construction solution. A self-adapting global pheromone updating strategy based on pheromone deposits is proposed for single objective ACO algorithm, and a global pheromone updating strategy based on approximation ideality distance is proposed for multi-objective ACO algorithm.(5) ACO algorithm for satellite data transmission scheduling based on task data transmission operations graphIn order to researching the availability of data transmission operations solution construction graph, ACO algorithms for SDTS based on task data transmission operations graph are proposed. The algorithms construct the sequence of task scheduling, and then construct each task’s resource allocation sequence, and a comprehensive utilize strategy by random weighting for heuristics is proposed. For enhancing diversity of the constructed task scheduling sequences, a pheromone updating strategy based on chaos variation is proposed for column pheromone vector. A global pheromone updating strategy based on compensate mechanism is proposed for single objective ACO algorithm, and a global pheromone updating strategy based on niche of Pareto solutions is proposed for multi-objective ACO algorithm.The author analyses simulation experiment and compares algorithms performance of above three ACO algorithms which are based on different solution construction graphs by simulation application systems. The numerical results show that all single-objective ACO algorithms based on three solution construction graph derive better solution than ordinary heuristics and most of the solutions are better than Genetic Algorithm and the running time is shorter than Genetic Algorithm in large scale scenario. All Multi-objective ACO algorithm that are on the basis of three solution construction graph can obtain Pareto optimum solutions which dominate the solution of ordinary heuristic algorithm which means the algorithms have strong ability of multi-objective optimization. Comparatively, ACO algorithm based on tasks data transmission operations graph has the best performance, the shortest running time. The performance of other two ACO algorithms based on other two solution construction graphs is almost the same and the quality of algorithm solution is affected greatly by the algorithm of solution element construction.更多还原