基于多目标优化的云任务调度算法研究

摘要

云计算作为当前研究应用最广泛的商业化分布式计算技术，具有庞大的服务器规模和用户群体，系统需要频繁地对云环境下的各种任务进行调度以及管理。针对云环境下执行时间和执行费用的调度是一个NP-hard的多目标组合优化问题，而目前的云任务调度一般采用的是带有约束的执行费用或者执行时间的单目标优化的启发式调度方法，不能完全满足带有负载均衡的复杂云系统下的多用户执行时间和执行费用的多样化需求。因此，在多目标优化的基础上，对云环境下的任务调度算法进行研究，有着极其重要的意义。
　　本文通过分析云任务的特点，改进了云任务模型，并选取执行时间、执行费用以及负载均衡为优化目标，对云任务的调度过程进行了优化，基于此多目标优化，在云环境下建立了云任务调度模型，主要的研究工作如下：
　　1)针对云环境下任务需求多样化的特点，分析了云计算的概念、体系结构以及技术特点，改进了云任务模型，引入了多目标优化的概念。
　　2)针对混合云任务的调度要求，选取云用户所关注的执行时间和执行费用以及云服务提供商所关注的负载均衡这三个目标，作为云环境下任务调度的优化目标，建立了能够处理此混合云任务的多目标优化的云任务调度模型。
　　3)针对云环境的动态变化以及云任务调度的特点，对蚁群遗传算法进行了改进，在此基础上提出了基于自适应遗传蚁群算法的多目标云任务调度算法，该算法既发挥了遗传算法较好的全局搜索能力，又综合了蚁群算法较高的求解精度，避免了遗传算法后期局部求解能力的不足和蚁群优化算法初始信息素的缺乏而导致搜索效率低下的缺陷，通过CloudSim仿真平台验证了，该算法在云用户所关注的执行时间和执行费用这两个目标问题以及云服务提供商所关注的负载均衡方面均具有明显的优势。
　　4)针对遗传算法和大规模云任务调度的问题，改进了文化基因算法，引入爬山和禁忌搜索这两种局部启发式算法，充分地利用遗传算法较好的全局寻优能力以及爬山算法和禁忌搜索算法较强的局部寻优能力的优势，避免了遗传算法后期局部求解能力的不足以及爬山算法和禁忌搜索算法较弱的全局寻优能力的缺点，最后在CloudSim仿真平台上验证了本文提出的基于禁忌搜索算法的文化基因算法，在大规模云任务调度环境中，表现出更高的执行效率和更好的负载均衡。

目录

声明

插图索引

附表索引

第1章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 本文的主要研究工作

1.4 论文的结构组织

第2章 云任务调度和多目标优化

2.1 云计算理论知识

2.2 多目标优化

2.3 基于多目标优化的云任务调度模型

2.4 本章小结

第3章 基于自适应遗传蚁群算法的多目标云任务调度算法

3.1 遗传算法

3.2 遗传算法的基本原理

3.3 蚁群算法

3.4 基于自适应遗传蚁群算法的多目标云任务调度算法

3.5 实验环境与仿真分析

3.6 本章小结

第4章 基于改进的文化基因算法的多目标云任务调度算法

4.1 文化基因算法

4.2 局部启发式搜索

4.3 实验仿真与结果分析

4.4 本章小结

总结与展望

总结

展望

参考文献

致谢

附录 攻读硕士学位期间所发表的学术论文及所参与的科研项目