基于改进蚁群算法的周期多帧任务分配  

Partitioning periodic multi-frames tasks based on improved ant colony algorithm

作　　者：徐成[1] 王培磊[1] 杨志邦[1] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机应用研究》2012年第9期3251-3254,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60973030)

摘　　要：研究一组多帧任务在异构多核处理平台上的分配,使得所有任务得以完成并耗费更少的时间。建立了带约束条件的异构多核周期多帧任务模型,运用蚁群算法来解决任务分配优化问题。其中结合了遗传算法中的复制、交叉、变异等遗传因子,以提高算法的收敛速度和全局搜索能力;改进了信息素的更新方式,以使算法在执行过程中可以根据收敛及进展情况动态地调整信息素残留程度,加快寻找最优解的能力;此外还引入了一种确定性搜索方法,以加快启发式搜索的收敛速度。实验证明,使用改进后的蚁群算法在解决异构多核平台上的多帧任务分配问题时,可以有效且快速地求得问题的最优解或近似最优解,并且拥有更低的时间复杂度。Given a set of multi-frame tasks and a heterogeneous multi-processor processing platform,the problem was to determining whether the tasks could be partitioned among the processors in such a manner that all timing constraints were met.This paper constructed a heterogeneous multi-processors periodic multi-frame task model with constraints and proposed an improved ant colony algorithm to solve the partition optimization problem of periodic multi-frames tasks among heterogeneous multi-processors.It introduced several genetic operators,such as reproduction,crossover and mutation,into the ant colony algorithm to enhance the converging rate and global search capability.To improve the self-adaptability of the algorithm,it modified pheromone updating strategy by dynamically adjusting the pheromone residual according to the progress of the algorithm convergence.Additionally,it introduced a deterministic search approach into the algorithm to accelerate the converging rate of the heuristic method.The experimental result proves that it can obtain an optimal or nearly optimal solutions to the multi-frame task allocation in heterogeneous multi-processor quickly with the improved ant colonyalgorithm,which has lower time-complexity as well

关 键 词：异构多核 多帧任务 蚁群算法 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]