基于改进量子遗传算法的云计算资源调度

基于改进量子遗传算法的云计算资源调度

作者：刘卫宁 靳洪兵 刘波 来源：《计算机应用》2013年第08期

摘 要：针对云计算环境下资源的高效调度问题，当前研究较少关注云服务提供商的服务成本，为此，以云服务提供商降低最小服务成本为目的，提出了改进量子遗传算法的云资源调度算法。由于采用二进制量子位表示的染色体无法描述资源调度矩阵，该算法将量子位的二进制编码转换为实数编码，并使用旋转策略和变异算子保证算法的收敛性。通过仿真实验平台将此算法与遗传算法和粒子群算法进行比较分析，在种群迭代次数为100的情况下，分别取种群数为1和10，实验结果表明该算法能取得更小的最小服务成本。 关键词：云计算；量子遗传算法； 资源调度； 最小成本；实数编码 中图分类号： TP18；TP393.027 文献标志码：A 0 引言

云计算是一种利用互联网实现随时随地、按需、便捷的访问共享资源池（如计算设施、存储设备、应用程序等）的计算模式[1]。云计算按服务层级可分为三种服务架构： 1）基础设施及服务（Infrastructure as a Service，IaaS）； 2）平台及服务（Platform as a Service，PaaS）； 3）软件及服务（Software as a Service，SaaS）。

本文重点关注IaaS层服务架构，由于基础设施的异构性，合理的资源调度方式成为影响云服务质量的关键。为了最大限度地满足用户的服务需求，又产生资源浪费，云计算资源调度问题就成为学界关注的焦点。

针对资源调度问题的求解，主要有基于经典优化问题的求解技术，即：将调度问题归结为某种己知的数学问题，在此基础上构造模型，并采用该数学问题经典的求解方法。但由于资源调度问题是一个NPhard问题，在解空间规模迅速增加的情况下，该方法因其较高的计算时间复杂性会导致其性能的严重局限。因而，智能算法越来越多地应用到资源调度问题的求解中：例如，遗传算法（Genetic Algorithm，GA）[2-4]。而云计算降低了资源准入的门槛，汇聚了更多的资源，形成了海量的候选资源池，极大地增加了云计算环境下资源调度的问题规模，同时也对调度问题的求解效率提出了严峻的挑战。量子遗传算法（Quantum Genetic Algorithm，QGA）因其具有按概率优化和广阔的解空间搜索特性而被广泛应用[5-6]。但尚未用于对云计算

龙源期刊网 http://www.qikan.com.cn

资源调度问题的求解，而且，既有的量子遗传算法采用二进制编码，对大规模云计算资源调度问题的求解尚存在局限。

鉴于此，本文提出基于实数编码的改进量子遗传算法，利用量子算法的按概率优化特性，使用旋转门更新，并增加变异算子，使得在量子编码的广阔空间中避免获得局部最优解。 1 云资源调度模型 1.1 调度模型

云计算环境下的资源调度模型可以用n个用户和m个资源组成的四元组来描述[7]： 实验结果表明，在相同条件下求解云资源调度问题，IQGA比GA和PSO具有更高的效率，能显著降低云服务商的支付成本。 4 结语

本文对云计算资源调度问题进行了研究，提出了基于改进量子遗传算法（IQGA）的云计算资源调度，该算法通过改进量子遗传算法的二进制编码使其适用于实数编码。CloudSim仿真模拟实验结果表明，在相同条件下求解云资源调度问题，IQGA比GA和PSO具有更高的效率，能显著降低云服务商的支付成本。下一步工作将放宽调度模型的假设条件，优化算法，进一步提高求解效率和准确性。 参考文献：

[1]MELL P， GRANCE T. The NIST definition of cloud computing [EB/OL]. [2012-12-08]. http：//www.nist.gov/itl/cloud/.

[2]李建锋， 彭舰. 云计算环境下基于改进遗传的算法的任务调度算法[J]. 计算机应用， 2011，31（1）：184-186.

[3]齐金平， 查显锋. 多任务多资源优化调度的病毒遗传算法[J]. 计算机应用， 2011， 31（7）：1773-1775.

[4]徐骁勇， 潘郁， 凌晨. 云计算环境下资源的节能调度[J]. 计算机应用， 2012， 32（7）：1913-1915.

[5]LAYEB A， MESHOUL S， BATOUCHE M. Multiple sequence alignment by quantum genetic algorithm [C]// IPDPS 2006： Proceedings of the 20th International Parallel and Distributed Processing Symposium. Piscataway： IEEE Computer Society， 2006.

龙源期刊网 http://www.qikan.com.cn

[6]LI B B， WANG L. A hybrid quantuminspired genetic algorithm for multiobjective flow shop scheduling [J]. IEEE Transactions on Systems Man and Cybernetics， Part B： Cybernetics， 2007， 37（3）：576-591.

[7]孙大为， 常桂然， 李凤云，等. 一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J]. 电子学报，2011，39（8）：1824-1831.

[8]ZHENG Z N， WANG R， ZHONG H， et al. An approach for cloud resource scheduling based on parallel genetic algorithm [C]// ICCRD2011： Proceedings of the 3rd International Conference on Computer Research and Development. Washington， DC： IEEE Computer Society， 2011： 444-447.

[9]YANG Z， YIN C Q， LIU Y. A costbased resource scheduling paradigm in cloud computing [C]// PDCAT 2011： Proceedings of the 12th International Conference on Parallel and Distributed Computing， Applications and Technologies. Washington， DC： IEEE Computer Society， 2011： 417-422.

[10]Google compute engine pricing [EB/OL]. [2012-12-20]. http：//cloud.google.com/pricing/computeengine.html.

[11]NARAYANAN A， MOORE M. Quantuminspired genetic algorithms [C]// ICEC96： Proceedings of the 1996 IEEE International Conference on Evolutionary Computation. Washington， DC： IEEE Computer Society， 1996： 61-66.

[12]HAN K H， KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem [C]// ICEC 2000： Proceedings of the 2000 IEEE Conference on Evolutionary Computation. Washington， DC： IEEE Computer Society， 2000： 1354-1360.

[13]李士勇， 李盼池. 基于实数编码和目标函数梯度的量子遗传算法[J]. 哈尔滨工业大学学报， 2006， 38（8）： 1216-1223.

[14]王凌. 量子进化算法研究进展[J]. 控制与决策， 2008， 23（12）： 1321-1326. [15]LI B， ZHUANG Z Q. Genetic algorithm based on the quantum probability representation [C]// Proceedings of the 3rd International Conference on Intelligent Data Engineering and Automated Learning， LNCS 2412. Berlin： SpringerVerlag， 2002： 500-505.