网格环境中一种改进的蚁群任务调度算法  

Improved ant colony algorithm for task scheduling in grid

作　　者：黄漾[1] 李肯立[2] 曾文[3] 

机构地区：[1]湖南铁路科技职业技术学院信息技术系,湖南株洲412000 [2]湖南大学信息科学与工程学院,长沙410082 [3]湖南铁路科技职业技术学院机车车辆系,湖南株洲412000

出　　处：《计算机应用研究》2012年第2期455-458,462,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(90715029);湖南省科技计划项目(2011FJ3067)

摘　　要：针对在蚁群算法中初始参数设置对算法收敛性能的影响较大,提出了一种新的改进蚁群算法NACA(new ant colony algorithm),针对蚁群算法中的四个关键参数随机编码,得到初始的染色体,从而获得一组较优解;再利用遗传算法的优点对上一步的结果单点顺序交叉、对换变异、选择操作以产生更好的解;然后以这组数据为蚁群算法下一次的工作备选值,并进行最大次数的循环迭代直至停止,即求得参数组合的近似最优解。将它应用于网格系统任务调度中,系统的性能得到了明显的改善。仿真模拟结果表明,所提出的算法具有更短的调度长度和更宽的适应性,当任务已知时,执行时间约缩短了21.7%,且负载变化时对网格中各处理器资源的影响大大减小。It has greater impact on the algorithm convergence that setting the initial parameters in ant colony algorithm.This paper presented an improved ant colony algorithm NACA.Firstly,it made the four parameters of the ant colony algorithm coding randomly and got the chromosomes,a set of optimum solutions could be gained by using the ant colony algorithm.Then they crossover,mutate and select by using the advantages of genetic algorithms.Finally,took the value of this group to explore the next round as the ant colony＇s original value,ran the maximum number of loop iterations until it stopping.The performance of the system had been significantly improved when it was applied to the grid task scheduling systems.The result of algorithm analysis shows the proposed scheduling algorithm has a shorter length and wider adaptability.When the task is known,execution time can be reduced about 21.7%.The execution time of the task is shorten greatly.

关 键 词：网格 任务调度 蚁群算法 GRIDSIM 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]