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

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2151-2153.

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

刘卫宁¹,²,靳洪兵¹,²,刘波¹,²

1. 信息物理社会可信服务计算教育部重点实验室(重庆大学)，重庆 400044
2. 重庆大学计算机学院，重庆 400044;

收稿日期:2013-02-04 修回日期:2013-03-17 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 靳洪兵
作者简介:刘卫宁(1965-)，女，重庆人，教授，博士生导师，主要研究方向：智能计算与服务、物流与供应链管理、网络与分布式计算;
靳洪兵(1988-)，男，重庆人，硕士研究生，主要研究方向：云计算、智能计算;
刘波(1981-)，男，四川广安人，博士研究生，主要研究方向：先进制造、供应链管理及优化。
基金资助:
基金项目:国家自然科学基金资助项目;国家科技支撑计划项目

Cloud computing resource scheduling based on improved quantum genetic algorithm

LIU Weining¹,²,JIN Hongbing¹,²,LIU Bo¹,²

1. College of Computer Science, Chongqing University, Chongqing 400044, China
2. Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education (Chongqing University), Chongqing 400044, China

Received:2013-02-04 Revised:2013-03-17 Online:2013-09-11 Published:2013-08-01
Contact: JIN Hongbing

摘要/Abstract

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

关键词: 云计算, 量子遗传算法, 资源调度, 最小成本, 实数编码

Abstract: Focusing on the problem of high efficiency resource scheduling in cloud computing environment, since current research has been less concerned about the cost of the services of the cloud service provider, an improved Quantum Genetic Algorithm (QGA) was proposed to reduce the minimum service cost of cloud service provider. This algorithm converted quantum-bits encoded by binary number to real-coded quantum-bits as chromosome represented by binary-coded quantum-bits cannot describe the resource scheduling matrix, and used rotation strategy and mutation operator to guarantee the convergence of the algorithm. Comparative experiments were conducted among the improved QGA, Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) through simulation platform, the populations number is 1 and 100 with 100 iteration times. The experimental results show that the improved QGA can obtain smaller minimum service cost.

Key words: cloud computing, Quantum Genetic Algorithm (QGA), resource scheduling, minimum cost, real encoding

中图分类号:

刘卫宁靳洪兵刘波. 基于改进量子遗传算法的云计算资源调度[J]. 计算机应用, 2013, 33(08): 2151-2153.

LIU Weining JIN Hongbing LIU Bo. Cloud computing resource scheduling based on improved quantum genetic algorithm[J]. Journal of Computer Applications, 2013, 33(08): 2151-2153.

参考文献

［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.

［6］LI B B, WANG L. A hybrid quantum-inspired 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 cost-based 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/compute-engine.html.

［11］NARAYANAN A, MOORE M. Quantum-inspired genetic algorithms ［C］// ICEC96: 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: Springer-Verlag, 2002: 500-505.

[1]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[2]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[3]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[4]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[5]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[6]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[7]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[8]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[9]	蔡芸, 刘朋青, 熊禾根. 基于量子遗传混合算法的泊位联合调度[J]. 计算机应用, 2020, 40(3): 897-901.
[10]	王庆永, 毛莺池, 王绎超, 王龙宝. 基于多微云协作的计算任务卸载[J]. 计算机应用, 2020, 40(2): 328-334.
[11]	刘福鑫, 李劲巍, 王熠弘, 李琳. 基于Kubernetes的云原生海量数据存储系统设计与实现[J]. 计算机应用, 2020, 40(2): 547-552.
[12]	杨哂哂, 吴慧珍, 庄黎丽, 吕宏武. 基于Markov过程的IaaS系统可用性建模与分析方法[J]. 计算机应用, 2020, 40(10): 3013-3018.
[13]	王建华, 潘宇杰, 孙瑞. 考虑机床折旧的柔性作业车间绿色调度算法[J]. 计算机应用, 2020, 40(1): 43-49.
[14]	林立, 熊金波, 肖如良, 林铭炜, 陈秀华. Gaming@Edge:基于边缘节点的低延迟云游戏系统[J]. 计算机应用, 2019, 39(7): 2001-2007.
[15]	徐雅斌, 彭宏恩. 基于需求预测的PaaS平台资源分配方法[J]. 计算机应用, 2019, 39(6): 1583-1588.