计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (16): 225-231.DOI: 10.3778/j.issn.1002-8331.2009.16.066

• 工程与应用 • 上一篇    下一篇

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

陈祥国,武小悦   

  1. 国防科学技术大学 信息系统与管理学院,长沙 410073
  • 收稿日期:2008-11-19 修回日期:2009-03-04 出版日期:2009-06-01 发布日期:2009-06-01
  • 通讯作者: 陈祥国

Model and algorithm of ant colony optimization for satellite data transmission scheduling

CHEN Xiang-guo,WU Xiao-yue   

  1. College of Information System & Management,National University of Defense Technology,Changsha 410073,China
  • Received:2008-11-19 Revised:2009-03-04 Online:2009-06-01 Published:2009-06-01
  • Contact: CHEN Xiang-guo

摘要: 针对卫星数传调度问题,提出了基于任务-资源关联结点的新型解构造图模型,人工蚁群通过任务边和资源弧分阶段进行任务调度序列和资源分配序列构造,设计了任务调度和资源分配启发式信息,以增强蚁群在伪随机状态转移过程中的搜索能力。通过局部信息素更新防止算法陷入局部最优,利用全局信息素更新的信息素正反馈机制使算法逐渐收敛到全局最优。仿真结果表明,新型解构造图反映了任务与资源之间的密切联系,分阶段状态转移策略和启发式信息的利用有助于增强算法的寻优能力,算法正确可行,并具有良好的收敛性、鲁棒性。

关键词: 卫星数传, 任务调度, 蚁群优化算法, 解构造图, 启发式信息

Abstract: For satellite data transmission scheduling problem,a novel solution construction graph model based on nodes associated with tasks and resources was put forward.The artificial ant colony constructed tasks scheduling sequence and resources allotment sequence by stages through task-edges and resource-arcs.Heuristics of tasks scheduling and heuristics of resources allocation were designed to strengthen ants’ ability of search.The algorithm avoids plunging into local optimization by local pheromone updating,and uses positive feedback mechanism in global pheromone updating to converge to global optimization.The simulation result indicates that,the novel solution construction graph reflects affinity between tasks and resources;the state transition rule by stages and the utilization with heuristics contribute to searching for global optimization;the algorithm is feasible,convergent and robust.

Key words: satellite data transmission, tasks scheduling, ant colony optimization algorithm, solution construction graph, heuristics