合作协同进化算法的改进及其在云计算任务调度中的应用研究

发布时间：2018-01-21 12:13

本文关键词： 合作型协同进化算法合作者选择云计算任务调度 CloudSim仿真器　出处：《华南理工大学》2015年硕士论文　论文类型：学位论文

【摘要】：目前,遗传算法以其独特的优势吸引着研究者们的眼球。但是由于遗传算法在解空间很大的情况下编码过长,不方便处理。进而出现了合作型协同进化算法,它继承了遗传算法的优点,而又克服了遗传算法的缺点,因此在算法提出之日起就得到的广泛关注。当前,云计算技术蓬勃发展,云平台要处理海量的用户请求。如何对用户任务进行合理的调度,满足用户的需求,是云技术发展过程中一个迫切需要解决的问题。因为合作协同进化在处理多变量的复杂问题时存在优势,将合作协同进化算法应用于云任务调度中也是目前研究的热点。合作协同进化算法中一个种群的个体只代表问题解的一部分,因此需要从其他种群中选择合作个体构成完整解之后才能评价个体的优劣性。合作者选择问题是合作协同进化算法中一个非常重要的问题。当前,合作者的选择问题并没有一个合适的解决方案,具有改进的空间。本文基于机器学习中分类的思想提出了一种基于距离的合作者选择方法,通过计算待评价个体到最优个体和随机个体的距离来选择最合适的合作团体。该方法可以在控制评价次数的情况下,对个体做出更加合理的评价,从而使整个算法能够得到更优化的解。本文在典型的函数优化以及车间调度问题中验证了算法可行性和有效性,实验证明算法能搜索到更优化的解。本文将改进协同进化算法用于云任务调度问题中,主要解决云任务调度中用户任务请求量大及时间跨度的问题。首先,将云任务调度问题抽象为一个寻优模型;然后设计编码方式和遗传算子的操作细节,使算法能够发挥最佳性能;最后,设计出使用改进合作协同进化算法解决云任务调度问题的整体调度流程。之后在模拟器Cloud Sim上进行实验。实验证明,在数据中心虚拟机性能差异不大的情况下,算法能够得到比主流调度算法更优的时间跨度;在数据中心虚拟机性能差异较大的情况下,算法得到的时间跨度优于遗传算法和标准协同进化算法,但是比MIN-MIN算法的结果差。因此,算法不适合处理虚拟机差异较大时的云环境调度问题。
[Abstract]:At present, genetic algorithm has attracted the attention of researchers because of its unique advantages. However, because genetic algorithm encodes too long in large solution space, it is not easy to process, and then cooperative co-evolution algorithm appears. It inherits the advantages of genetic algorithm, but overcomes the shortcomings of genetic algorithm, so it has received extensive attention since the date of the algorithm was put forward. Currently, cloud computing technology is booming. Cloud platform has to deal with a large number of user requests. How to reasonably schedule user tasks to meet the needs of users. It is an urgent problem in the development of cloud technology, because cooperative co-evolution has advantages in dealing with complex multi-variable problems. The application of cooperative coevolutionary algorithm to cloud task scheduling is also a hot topic. In cooperative co-evolution algorithm, the individual of a population represents only a part of the solution of the problem. Therefore, it is necessary to select cooperative individuals from other populations to form a complete solution to evaluate the merits and demerits of individuals. The selection of collaborators is a very important problem in cooperative coevolutionary algorithms. There is not a suitable solution to the problem of partner selection, and there is room for improvement. This paper proposes a distance based partner selection method based on the idea of classification in machine learning. By calculating the distance between the individual to the optimal individual and the random individual to select the most suitable cooperative group, this method can make a more reasonable evaluation of the individual under the condition of controlling the evaluation times. So that the whole algorithm can get a better solution. This paper verifies the feasibility and effectiveness of the algorithm in the typical function optimization and job shop scheduling problem. Experiments show that the algorithm can find a better solution. In this paper, the improved co-evolution algorithm is applied to the cloud task scheduling problem, mainly to solve the problem of large amount of user task request and time span in cloud task scheduling. First of all. The cloud task scheduling problem is abstracted into an optimization model. Then the coding method and the operation details of the genetic operator are designed so that the algorithm can give full play to the best performance. Finally, the overall scheduling process of cloud task scheduling problem using improved cooperative co-evolution algorithm is designed. Then the experiment is carried out on the simulator Cloud Sim. When the performance of the data center virtual machine is not different, the time span of the algorithm is better than that of the mainstream scheduling algorithm. The time span of the algorithm is better than that of the genetic algorithm and the standard co-evolution algorithm, but the result is worse than that of the MIN-MIN algorithm when the performance of the virtual machine in the data center is quite different. The algorithm is not suitable to deal with the cloud environment scheduling problem with large differences in virtual machines.
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18;TP393.07

【参考文献】