摘要
针对网格环境中DAG任务调度问题,提出一种改进混洗蛙跳算法,通过增设族群进化点和引入邻域搜索策略,解决了原算法进化动力不足和易陷入局部最优的问题;为解决DAG任务在启发式算法中编码困难的问题,利用DAG任务自身的约束条件,重新定义解空间的度量方式,进而提出一种新的编码方式。仿真实验结果表明,改进算法的收敛速度较GA、PSO、SFL算法分别提高了75%、94%和27%,搜索性能亦有明显改善,能有效地提高最优解的质量。
In view of the problem of DAG task scheduling in grid environment,an improved shuffled frog leaping algorithm is presented.The evolutionary points of memeplexes and neighborhood search strategies are introduced to solve the evolutional power shortage and local optimization problem.Because it＇s difficult for coding DAG task in the heuristic algorithm,a new coding method is presented,which redefines the measurement of solution space by its own constraint condition of DAG task.The simulation results show that compared with GA,PSO,SFL,the convergence speed of the improved algorithm is respectively increased by 75%,94% and 27%,and search performance is significantly improved.Therefore,the improved algorithm can effectively improve the quality of the optimal solution.
出处
《桂林电子科技大学学报》
2015年第1期64-69,共6页
Journal of Guilin University of Electronic Technology
基金
广西教育厅科研项目(2009MS1195)
广西可信软件重点实验室开放基金(kx201106)
关键词
网格
混洗蛙跳算法
DAG任务
编码
邻域搜索
grid
shuffled frog leaping algorithm
DAG task
coding
neighborhood search
