基于解构造图的卫星数传调度ACO算法

Journal of Systems Engineering and Electronics ›› 2010, Vol. 32 ›› Issue (3): 592-597.

基于解构造图的卫星数传调度ACO算法

陈祥国, 武小悦

（国防科学技术大学信息系统与管理学院，湖南长沙 410073）

出版日期:2010-03-18 发布日期:2010-01-03

ACO algorithm of satellite data transmission scheduling based on solution construction graph

CHEN Xiang-guo， WU Xiao-yue

（Coll. of Information Systems and Management, National Univ. of Defense Technology, Changsha 410073, China）

Online:2010-03-18 Published:2010-01-03

摘要/Abstract

摘要：

针对卫星数传调度问题，建立了基于任务调度关系（弧模式）和基于任务调度位置（结点模式）的解构造图，提出了基于解构造图的卫星数传调度蚁群优化(ant colony optimization, ACO)算法。算法利用伪随机概率转移规则进行路径搜索，通过划分冲突任务集来限制蚁群的搜索邻域。算法根据迭代最优解和至今最优解进行全局信息素更新，并将构造图中的信息素浓度限制在一定范围内。仿真结果表明，文中提出的两种解构造图及ACO算法是正确可行的，基于结点模式解构造图的ACO算法能获得更优的解。

Abstract:

For satellite data transmission scheduling problems (SDTSP), two types of solution construction graphs based on task scheduling relation (arc model) and task scheduling position (node model) are founded, an ant colony optimization (ACO) algorithm of SDTSP based on solution construction graphs is proposed. The algorithm searches a path by making use of the pseudorandom proportional probability transfer rule and restricts searching the neighborhood through plotting out conflict task sets. The algorithm processes global pheromone updating based on the best iterative solution and best-so-far solution, and the consistency of pheromone in graph is restricted within a certain range. Simulation result shows that these two solution construction graphs and the ACO algorithm are feasible, and the ACO algorithm featuring a solution construction graph based on the node model can gain a preferable solution.

陈祥国, 武小悦. 基于解构造图的卫星数传调度ACO算法[J]. Journal of Systems Engineering and Electronics, 2010, 32(3): 592-597.

CHEN Xiang-guo， WU Xiao-yue. ACO algorithm of satellite data transmission scheduling based on solution construction graph[J]. Journal of Systems Engineering and Electronics, 2010, 32(3): 592-597.