基于蚁群模拟退火的云任务调度算法改进
|
摘要
随着云计算的快速发展,如何高效地进行云任务调度逐渐成为云计算研究的重点。任务调度问题属于NP优化问题,许多超启发式算法被应用到任务调度问题。针对蚁群算法在任务调度中存在收敛速度慢、局部搜索能力差和易于陷入局部最优的问题,将蚁群算法和模拟退火算法相结合,提出了蚁群模拟退火算法,拟解决云计算中的任务调度问题。在该算法中,以减少任务的完成时间和保证资源负载均衡为目标,根据蚁群算法构造局部最优解,利用模拟退火算法较强的局部搜索能力,将局部最优解作为模拟退火算法的初始解进行局部搜索并以一定的概率接受当前搜索结果,从而避免算法陷入局部最优。仿真结果表明,蚁群模拟退火算法的性能优于先来先服务(First Come First Served,FCFS)和标准蚁群优化(Ant Colony Optimization,ACO)算法。
With the rapid development of cloud computing,howto carry on task scheduling effectively is crucial in the research of cloud computing.Cloud task scheduling belongs to a NP-hard optimization problem,and many meta-heuristic algorithms have been proposed to solve it.ACO algorithm in task scheduling still has many shortcomings such as slowconvergence speed,poor ability of local search and falling into local optimum easily.Therefore,a newalgorithm-ACOSA is presented to solve task scheduling problem.In this algorithm,reducing task completion time and ensuring resource's load balance as the goal,according to the local ant colony algorithm the optimal solution is constructed,and the strong local search capability of simulated annealing algorithm is applied to make the local optimal solutions as the initial solutions of simulated annealing algorithm and accept the results of current search to a certain probability in order to avoid falling into the local optimal.Simulation results showthat ACOSA is superior to First Come First Served( FCFS) and Ant Colony Optimization( ACO) by reducing make span and achieving load balance.
With the rapid development of cloud computing,howto carry on task scheduling effectively is crucial in the research of cloud computing.Cloud task scheduling belongs to a NP-hard optimization problem,and many meta-heuristic algorithms have been proposed to solve it.ACO algorithm in task scheduling still has many shortcomings such as slowconvergence speed,poor ability of local search and falling into local optimum easily.Therefore,a newalgorithm-ACOSA is presented to solve task scheduling problem.In this algorithm,reducing task completion time and ensuring resource's load balance as the goal,according to the local ant colony algorithm the optimal solution is constructed,and the strong local search capability of simulated annealing algorithm is applied to make the local optimal solutions as the initial solutions of simulated annealing algorithm and accept the results of current search to a certain probability in order to avoid falling into the local optimal.Simulation results showthat ACOSA is superior to First Come First Served( FCFS) and Ant Colony Optimization( ACO) by reducing make span and achieving load balance.
引文
[1]Jadeja Y,Modi K.Cloud computing-concepts,architecture and challenges[C]//International conference on computing,electronics and electrical technologies.[s.l.]:IEEE,2012:877-880.
[2]Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[3]李建江,崔健,王聃,等.MapReduce并行编程模型研究综述[J].电子学报,2011,39(11):2635-2642.
[4]Stonebraker M,Abadi D,Dewitt D J,et al.MapReduce and parallel DBMSs:friends or foes?[J].Communications of the ACM,2010,53(1):64-71.
[5]徐洁,朱健琛,鲁珂.基于双适应度遗传退火的云任务调度算法[J].电子科技大学学报,2013,42(6):900-904.
[6]Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.
[7]Liu C Y,Zou C M,Wu P.A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing[C]//13th international symposium on distributed computing and applications to business,engineering and science.[s.l.]:IEEE,2014:68-72.
[8]黄翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1344-1353.
[9]Zhu J,Rui T,Fang H,et al.Simulated annealing ant colony algorithm for QAP[C]//Eighth international conference on natural computation.[s.l.]:IEEE,2012:789-793.
[10]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.
[11]陈华根,吴健生,王家林,等.模拟退火算法机理研究[J].同济大学学报:自然科学版,2004,32(6):802-805.
[12]高尚.蚁群算法理论、应用及其与其它算法的混合[D].南京:南京理工大学,2005.
[13]华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010(1):127-134.
[14]高鹰,谢胜利.基于模拟退火的粒子群优化算法[J].计算机工程与应用,2004,40(1):47-50.
[15]张晖,吴斌,余张国.引入模拟退火机制的新型遗传算法[J].电子科技大学学报,2003,32(1):39-42.
[2]Dean J,Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[3]李建江,崔健,王聃,等.MapReduce并行编程模型研究综述[J].电子学报,2011,39(11):2635-2642.
[4]Stonebraker M,Abadi D,Dewitt D J,et al.MapReduce and parallel DBMSs:friends or foes?[J].Communications of the ACM,2010,53(1):64-71.
[5]徐洁,朱健琛,鲁珂.基于双适应度遗传退火的云任务调度算法[J].电子科技大学学报,2013,42(6):900-904.
[6]Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.
[7]Liu C Y,Zou C M,Wu P.A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing[C]//13th international symposium on distributed computing and applications to business,engineering and science.[s.l.]:IEEE,2014:68-72.
[8]黄翰,郝志峰,吴春国,等.蚁群算法的收敛速度分析[J].计算机学报,2007,30(8):1344-1353.
[9]Zhu J,Rui T,Fang H,et al.Simulated annealing ant colony algorithm for QAP[C]//Eighth international conference on natural computation.[s.l.]:IEEE,2012:789-793.
[10]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.
[11]陈华根,吴健生,王家林,等.模拟退火算法机理研究[J].同济大学学报:自然科学版,2004,32(6):802-805.
[12]高尚.蚁群算法理论、应用及其与其它算法的混合[D].南京:南京理工大学,2005.
[13]华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010(1):127-134.
[14]高鹰,谢胜利.基于模拟退火的粒子群优化算法[J].计算机工程与应用,2004,40(1):47-50.
[15]张晖,吴斌,余张国.引入模拟退火机制的新型遗传算法[J].电子科技大学学报,2003,32(1):39-42.