学位论文 > 优秀研究生学位论文题录展示

卫星数传调度的蚁群优化模型及算法研究

作　者: 陈祥国
导　师: 武小悦
学　校: 国防科学技术大学
专　业: 控制科学与工程
关键词: 卫星数传调度蚁群优化解构造图单目标优化多目标优化 Pareto占优
分类号: V57
类　型: 博士论文
年　份: 2010年
下　载: 194次
引　用: 7次
阅　读: 论文下载

内容摘要

卫星数传调度是亟待解决的重要现实问题和理论难题,一般启发式调度算法已难以满足卫星数传调度的需要。基于群体智能的蚁群优化算法已经成为求解大规模组合优化问题的代表性算法,为了探索蚁群优化算法在该问题中应用的可行性,为卫星数传调度的蚁群优化提供解决方案,本文基于蚁群优化理论,提出了三种基于解构造图的卫星数传调度蚁群优化算法,并通过仿真应用系统对算法进行了实验分析和比较。本文主要研究工作及创新点包括:(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算法性能相当,算法获得解的质量受解成分构造算法影响较大。

全文目录

摘要  12-14
Abstract  14-17
第一章绪论  17-48
  1.1 研究背景与意义  17-23
    1.1.1 卫星数传调度问题概述  17-18
    1.1.2 卫星数传调度是复杂优化问题  18-20
    1.1.3 卫星数传调度的研究意义  20-23
  1.2 国内外相关领域研究综述  23-41
    1.2.1 卫星数传调度相关研究综述  23-32
    1.2.2 蚁群优化及相关研究综述  32-41
  1.3 论文主要研究工作  41-48
    1.3.1 论文研究思路  41-44
    1.3.2 论文研究内容  44-45
    1.3.3 论文主要创新  45-48
第二章卫星数传调度模型及启发式信息研究  48-81
  2.1 卫星数传调度问题  48-55
    2.1.1 调度场景  48-49
    2.1.2 调度约束  49-50
    2.1.3 调度中的时间窗口转换  50-55
  2.2 卫星数传调度模型  55-65
    2.2.1 卫星数传调度评价指标  55-61
    2.2.2 卫星数传调度的数学模型  61-63
    2.2.3 卫星数传调度的可行解评价  63-65
  2.3 卫星数传调度的启发式信息  65-80
    2.3.1 卫星数传调度的启发式信息体系  66-67
    2.3.2 任务调度启发式信息  67-74
    2.3.3 资源分配启发式信息  74-80
  2.4 本章小结  80-81
第三章基于任务调度关系图的卫星数传调度ACO 算法  81-110
  3.1 基于任务调度关系的解构造图  81-85
    3.1.1 任务调度关系对调度的影响  81-82
    3.1.2 基于任务调度关系的调度方案描述  82-83
    3.1.3 任务调度关系图构造  83-84
    3.1.4 基于任务调度关系图的解构造特点  84-85
  3.2 基于任务调度关系图的ACO 算法描述  85-100
    3.2.1 自适应概率决策模型  85-87
    3.2.2 基于最大可能冲突任务集的搜索邻域  87-89
    3.2.3 任务调度启发式信息随机选择策略  89
    3.2.4 基于资源分配启发式信息的迭代解成分构造算法  89-91
    3.2.5 基于资源分配启发式信息的迭代修复局部搜索  91-93
    3.2.6 单目标优化的解评价与解更新  93
    3.2.7 Pareto 解集的评价与更新  93-94
    3.2.8 局部信息素更新策略  94
    3.2.9 单目标优化的递阶全局信息素更新策略  94-95
    3.2.10 基于Pareto 解偏离度的多目标优化全局信息素更新策略  95-97
    3.2.11 基于任务调度关系图的ACO 算法流程  97-100
  3.3 算法实验分析  100-109
    3.3.1 算法参数设置分析  100-104
    3.3.2 算法收敛性分析  104-107
    3.3.3 算法性能分析  107-109
  3.4 本章小结  109-110
第四章基于任务调度位置图的卫星数传调度ACO 算法  110-137
  4.1 基于任务调度位置的解构造图  110-114
    4.1.1 任务调度位置对调度的影响  110-111
    4.1.2 基于任务调度位置的调度方案描述  111
    4.1.3 任务调度位置图构造  111-113
    4.1.4 基于任务调度位置图的解构造特点  113-114
  4.2 基于任务调度位置图的算法描述  114-127
    4.2.1 基于信息素评价的自适应概率决策模型  114-117
    4.2.2 导引式任务调度启发式信息选择策略  117-118
    4.2.3 基于2-交换的迭代修复局部搜索  118-120
    4.2.4 基于信息素遗留的单目标优化自适应信息素更新策略  120-123
    4.2.5 基于近似理想距离的多目标优化信息素更新策略  123-124
    4.2.6 基于任务调度位置图的ACO 算法流程  124-127
  4.3 算法实验分析  127-135
    4.3.1 算法参数设置分析  127-131
    4.3.2 算法收敛性分析  131-133
    4.3.3 算法性能分析  133-135
  4.4 本章小结  135-137
第五章基于任务数传操作图的卫星数传调度ACO 算法  137-160
  5.1 基于任务数传操作的解构造图  137-142
    5.1.1 任务数传操作对调度的影响  137-138
    5.1.2 基于任务数传操作的调度方案描述  138
    5.1.3 任务数传操作图构造  138-140
    5.1.4 基于任务数传操作图的解构造特点  140-142
  5.2 基于任务数传操作图的算法描述  142-150
    5.2.1 任务调度序列概率决策模型  143
    5.2.2 资源分配序列概率决策模型  143-144
    5.2.3 基于随机加权的启发式信息利用策略  144-145
    5.2.4 基于混沌变异的列信息素向量更新  145
    5.2.5 具有补偿机制的单目标优化信息素更新策略  145-146
    5.2.6 基于小生境的多目标优化信息素更新策略  146-147
    5.2.7 基于任务数传操作图的ACO 算法流程  147-150
  5.3 算法的实验分析  150-159
    5.3.1 算法参数设置分析  150-154
    5.3.2 算法收敛性分析  154-157
    5.3.3 算法性能分析  157-159
  5.4 本章小结  159-160
第六章卫星数传调度ACO 算法仿真应用研究  160-194
  6.1 仿真系统设计  160-166
    6.1.1 总体结构设计  160-161
    6.1.2 功能模块设计  161-165
    6.1.3 仿真流程设计  165-166
  6.2 仿真实验设计  166-170
    6.2.1 仿真调度场景设计  166-168
    6.2.2 基准测试任务集生成  168-170
  6.3 仿真实验分析  170-193
    6.3.1 实验结果  170-178
    6.3.2 评价指标合理性分析  178-180
    6.3.3 单目标卫星数传调度ACO 算法性能分析  180-184
    6.3.4 多目标卫星数传调度ACO 算法性能分析  184-188
    6.3.5 算法运行时间复杂性分析  188-190
    6.3.6 分析结论  190-193
  6.4 本章小结  193-194
第七章结论与展望  194-198
  7.1 论文工作总结  194-196
  7.2 未来工作展望  196-198
致谢  198-200
参考文献  200-213
作者在学期间取得的学术成果  213-214
附录.1 仿真运行环境  214
附录.2 仿真场景中的地面站设置  214
附录.3 仿真场景中的卫星轨道参数  214-217
附录.4 仿真场景设计表  217-219
附录.5 仿真场景预报流冲突统计表  219

卫星数传调度的蚁群优化模型及算法研究

内容摘要

全文目录

相似论文