基于遗传算法的云计算任务调度算法研究

发布时间：2018-04-10 06:32

本文选题：云计算　切入点：任务调度　出处：《厦门大学》2014年硕士论文

【摘要】：云计算是一种新型的商业计算模型,它通过网络进行连接,能够获得各种应用、数据和IT服务。云计算的核心,是根据用户的需求,对云环境中的资源和用户提交的任务进行统一的调度和管理,而用户只需要按需付费。因而在云服务中,如何满足不同用户对服务质量(QoS)的不同需求,是云计算调度必须要考虑的重要问题。遗传算法是一种进化算法,它借鉴生物界的进化思想和自然界中“优胜劣汰”的自然选择机制,是一种全局优化搜索算法。遗传算法由于其本身所具备的并行性和全局解空间搜索的特点,被引入到了大规模集群系统的资源调度中。本文以用户对服务质量的需求为出发点,通过权重向量的设置,综合考虑不同用户对作业完成时间、带宽、可靠性和费用等4个因素的不同需求,设计基于用户满意度的适应度函数,以保证服务质量。针对遗传算法存在的“早熟”问题,本文采用模拟退火算法对其进行优化。模拟退火算法借鉴物理上固体退火的机理,具有能够跳出局部最优解的特性,是一种全局最优算法。然而,它存在对整个搜索空间的情况了解不多的缺点。将遗传算法和模拟退火算法结合起来,能够充分发挥两者的优势,弥补二者的不足,提高算法性能。本文在遗传算法产生新个体的过程中引入模拟退火算子,根据模拟退火算法中的Metropolis准则来决定是否接受遗传算法产生的新个体,在保证种群多样性的同时,也使种群能够逐步进化。本文还介绍了云仿真工具CloudSim,并配置了实验环境。在CloudSim仿真平台上,对本文所设计的遗传算法和模拟退火算法优化后的遗传算法进行了仿真实验。通过与基本遗传算法进行实验比较,表明本文设计的遗传算法能够更好地满足不同用户对云服务质量的不同需求。通过对优化前后两种遗传算法以及CloudSim自带的随机分配算法RA和轮询算法RR之间的实验结果对比,表明采用模拟退火算子对算法进行优化后,算法性能有所改善。
[Abstract]:Cloud computing is a new type of business computing model, which can access various applications, data and IT services through a network connection.The core of cloud computing is to schedule and manage the resources and tasks submitted by users according to the needs of users, and users only need to pay on demand.Therefore, how to meet the different needs of different users for QoS in cloud services is an important issue that must be considered in cloud computing scheduling.Genetic algorithm (GA) is an evolutionary algorithm, which draws lessons from the evolutionary thinking of the biological world and natural selection mechanism of "survival of the fittest" in nature, and is a global optimization search algorithm.Genetic algorithm (GA) is introduced into the resource scheduling of large-scale cluster system because of its parallelism and global solution space search.Based on the user's demand for quality of service (QoS), this paper considers the different requirements of different users for four factors, such as job completion time, bandwidth, reliability and cost, by setting the weight vector.The fitness function based on user satisfaction is designed to guarantee the quality of service.Aiming at the problem of precocity in genetic algorithm, simulated annealing algorithm is used to optimize it.The simulated annealing algorithm is a global optimal algorithm because it can jump out of the local optimal solution by referring to the mechanism of solid annealing in physics.However, it has the disadvantage of not knowing much about the whole search space.The combination of genetic algorithm and simulated annealing algorithm can give full play to the advantages of the two algorithms, make up for their shortcomings and improve the performance of the algorithm.In this paper, the simulated annealing operator is introduced in the process of generating new individuals by genetic algorithm. According to the Metropolis criterion of simulated annealing algorithm, we decide whether to accept the new individuals generated by genetic algorithm. At the same time, we can ensure the diversity of population.It also allows the population to evolve.The cloud simulation tool CloudSimand is also introduced in this paper, and the experimental environment is configured.On the platform of CloudSim, the genetic algorithm and simulated annealing algorithm are simulated.By comparing with the basic genetic algorithm, it is shown that the genetic algorithm designed in this paper can better meet the different needs of different users for cloud quality of service.By comparing the experimental results between the two genetic algorithms before and after optimization, CloudSim's own random assignment algorithm RA and the polling algorithm RR, it is shown that the performance of the algorithm is improved by using simulated annealing operator to optimize the algorithm.
【学位授予单位】：厦门大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18;TP393.01

【参考文献】