一种用于云计算资源调度的改进遗传算法

An Improved Genetic Algorithm for Cloud Computing Resource Scheduling

摘要:

针对轮询调度算法、遗传算法和模拟退火算法在云计算资源调度中存在收敛速度慢、易早熟和资源负载不均衡等问题,提出了一种基于模拟退火思想的改进遗传算法(simulated annealing improved genetic algorithm:SAIGA);改进算法设计了基于任务平均完成时间和负载均衡的双适应度函数和自适应的交叉变异概率函数,允许算法在退火过程中以一定概率接受劣质解从而避免早熟现象的发生,将虚拟资源上任务分配数的标准差作为选择个体的依据来实现节点的负载均衡;仿真结果表明,改进算法与上述算法相比,在任务平均完成时间、资源利用率以及收敛速度上表现得更优越,能够较快地找到资源最优调度方案,具有较好的可行性和实用性。

Abstract:

For Round-Robin scheduling algorithm and genetic algorithm and simulated annealing algorithm in cloud resource scheduling having shortcomings, such as slow convergence speed, easy to premature and the imbalance of the resource load, the paper proposed the improved genetic algorithm combined with simulated annealing thought (Simulated Annealing Improved Genetic Algorithm:SAIGA). The improved algorithm gave a dual fitness function based on task average completion time and load balance and adaptive crossover mutation probability function. It allowed the algorithm in the annealing process to accept inferior solution with a certain probability to avoid prematurity phenomenon occurs. We regarded the virtual machine task allotment standard deviation as the basis of individual choice to realize the resource node load balancing. Simulation experiments showed that the improved algorithm is more superior on average task completion time, resource load balancing, and the convergence rate. It can rapidly find the optimal scheduling scheme and has good feasibility and practicability.