基于元胞自动机遗传算法的云资源调度

计 算 机 工 程 第 38 卷 第11期

Computer Engineering V ol.38 No.11

文章编号:文章编号:1000—3428(2012)11—0011—03 ·云计算专题·云计算专题·

2012年6月

June 2012

文献标识码:文献标识码:A

中图分类号:中图分类号:TP391

基于元胞自动机遗传算法基于元胞自动机遗传算法的云资源调度遗传算法的云资源调度

张水平a,邬海艳b

(江西理工大学 a. 信息网络中心;b. 信息工程学院,江西 赣州 341000)

摘 要:针对传统遗传算法易陷入早熟收敛等问题,提出一种改进的元胞自动机遗传算法(CGA),并将其应用于云环境下的资源调度。分析云计算环境中处理用户群请求的庞大任务数及资源合理分配的问题,利用CGA算法寻求一组最优的资源调度方案。在CloudSim仿真平台上进行实验,结果表明,CGA算法能缩短任务完成时间,降低用户总成本,满足云环境下的资源调度要求。 关键词:关键词:云计算;遗传算法;元胞自动机;遗传算子;资源调度

Cloud Resource Schedule

Based on Cellular Automata Genetic Algorithm

ZHANG Shui-pinga, WU Hai-yanb

(a. Center of Information and Network; b. Faculty of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China)

【Abstract】To the problem that traditional Genetic Algorithm(GA) has early convergence, this paper proposes an improved Cellular automata Genetic Algorithm(CGA), and applies on resource schedule under cloud environment. It makes a discussion on the enormous tasks required by users group and how to allocate resources reasonably, takes use of CGA to search for the optimal resource schedule proposal. Experimental results under the simulator platform CloudSim shows that the algorithm can reduce the whole makespan and decrease the costs of users, which is an effective resource schedule satisfying cloud environment.

【Key words】cloud computing; Genetic Algorithm(GA); cellular automata; genetic operator; resource schedule DOI: 10.3969/j.issn.1000-3428.2012.11.004

1 概述

云计算[1-2]是通过互联网连接的超级计算模式,包含了 分布式处理、并行处理和网格计算等相关技术。云环境下的资源调度是一个关键技术,其主要机制是将用户的任务映射给合适的资源节点去执行,而这些资源节点可以是巨大的集群,也可以是中型的工作站,还可以是小型的闲散个人电脑、PDA、移动电话等终端设备,它们分散的异构分布共同构成云计算的共享基础架构。云计算资源节点开放、异构、复杂等特点导致云计算的资源调度成为一个NP完全问题。因此,实现高效的资源调度策略对充分利用基础设施资源节点至关重要。

遗传算法(Genetic Algorithm, GA)[3]因其隐形并行性和全局解空间搜索特点得到学术研究者的青睐。文献[4]提出了一种具有双适应度的遗传算法,应用到云计算的任务调度。遗传算法在资源调度问题上能够得到有效应用,但它仍存在一些缺陷,如搜索后期效率低、早熟、遗传算子存在局限性等。因此,本文在传统遗传算法的基础上,引入元胞自动机模型的基本原理,将元胞自动机遗传算法(Cellular automata Genetic Algorithm, CGA)应用于云环境下的资源调度问题中。

元胞自动机[5]基本由元胞、元胞空间、状态集、邻居和

演化规则等构成。用数学符号可表示成一个四元组:A=(Ld, S, N, f)。具体描述如下:

(1)A元胞又可称为单元,这些单元组成了整个元胞自动机的元胞集。

(2)元胞空间Ld表示元胞所分布的任意d维空间网格, 亦称为元胞空间,本文取Ld=2。

(3)状态集S:一般来说,每个元胞在每一个时刻都有一个状态,可用{0, 1}二进制形式表示,0表示元胞的状态为死,1表示元胞的状态为生。

(4)元胞邻居N:一个邻域内所有元胞的组合,记为N= (S1, S2,…, Sn),n是元胞的邻居个数。常见的3种元胞邻居模

型如图1所示,其中,冯-诺依曼型有4个邻居;摩尔型有 8个邻居;扩展摩尔型有16个邻居。

基于元胞自动机遗传算法的云资源调度

2 元胞自动机及云环境描述元胞自动机及云环境描述

2.1 元胞自动机简介

元胞自动机用于模拟生命系统所具有的自复制功能,它是一个时间和空间都离散的动力系统,元胞自动机的每个元胞的变化都是同步进行的,特别适合于并行计算,被称为下一代并行计算机的雏形。

图1 元胞邻居模型

(5)演化规则f即状态转移函数,也就是某元胞下一刻的

作者简介:作者简介:张水平(1965-),男,副教授,主研方向:元胞自动机,智能计算;邬海艳,硕士研究生

收稿日期:收稿日期:2011-08-17 E-mail:haiyanmeng0512@http://www.mianfeiwendang.com

基于元胞自动机遗传算法的云资源调度相关文档

最新文档

返回顶部