论文部分内容阅读
中图分类号：TP301 文献标识码：A
摘要：通过研究云计算的编程模型和多种分布式任务调度算法，提出一种改进的遗传蚁群算法，使用间接混合编码方式让每条染色体形成了单独的任务调度方案，利用遗传算法生成的优化解，解决了蚁群算法的前期信息素聚集慢的问题，提高了云计算中任务调度的效率。实验结果证明，本算法取得了不错的的结果。
关键词：云计算；遗传算法；蚁群算法
一、引言
近年来，互联网行业快速发展，云计算作为一种新兴的商业模式应运而生。云计算的特点是超大规模、虚拟化、高可靠性和通用性好等。目前，为人们所熟知的云平台有Google云计算、Amazon弹性计算云EC2、百度云平台和阿里巴巴云电子商务等[8]。
云计算通过网络将大型的计算任务拆分成较小的计算任务，交给大型分布式服务器系统处理，经过计算分析后将计算结果交给用户。因为在云计算的过程需要处理大量的任务，如何保证这些大量的计算任务能够正确、高效的被调度，成为了云计算之中的重点。本文采用遗传蚁群混合算法（Generic Algorithm Ant Colony Optimization， GAACO），通过结合遗传算法前期搜索速度快和蚁群算法后期搜索优势大的优点，对云计算中的任务调度进行优化，通过了仿真对比试验，验证了良好的性能。
二、算法
1.云计算编程模型Map/Reduce
随着云计算的兴起，越来越多的企业提出了自己的“云计划”，大多数企业都以Map/Reduce编程模型的思想来开发自己的云，Map/Reduce特别适合产生和处理大规模的数据集。Map/Reduce首先在Map阶段通过一个Map/Reduce函数把一个大型的计算任务分割成N个较小的子任务给多台工作主机并行执行。然后我们把在Map阶段生成的中间文件在Reduce阶段汇总分析处理，输出M个（M与Reduce任务数量一致）输出文件。
2.染色体的编码和解码
根据Map/Reduce编程模型的特点，在遗传算法执行阶段本文针对云环境中的资源和在资源中对任务的分配制定了一种间接编码方式（worker-task-subtask），利用随机函数随机生成一定数量的种群。每一个染色体都是对任务的子任务在资源中的分配方式的抽象。假设有m个任务，每个任务i的子任务数是subTask（i），子任务的总数n为：
第i个任务中第j个子任务的编号是：
假设云环境中资源总数为w，那么染色体的长度为w+n。前w（1，2，…w）个整数代表资源（worker），w+1到w+n代表分配给资源执行的子任务（subtask）。本文规定任务队列中的子任务分配到当前任务执行总时间最少的资源中。
假设w=3，m = 3， subTask （i） = i+1（i的范围是1到3），n的总数为9。那么对染色体实例{1，4，5，9，2，6，12，3，7，8，10，11}做出如下解释：任务1中的包含编号为1，2的子任务，任务2中包含编号为3，4，5，的子任务，任务3中包含编号为6，7，8，9的子任务。子任务1，2，6运行在资源1中，子任务3，9运行在资源2中，子任务4，5，7，8运行在资源3中。对染色体的解码能得到各个task的subTask在worker上的分布情况和各个worker上的任务执行序列。对上述染色体实例的解码为
Worker（1）：[1，2，6]， Worker（2）：[3，9]， Worker（3）：[4，5，7，8]
通过解码后的序列和ETC（Expect Time to Compute）矩阵（ETC[i，j]代表序号为i的subTask在第j个资源上执行完成所需要的时间）可以计算出每个资源的任务队列中所有nSub个子任务的执行时间：
则完成所有任务的总时间函数为：
假设第t个任务一共有s个子任务，第t个任务的完成时间为在w个资源中每个资源执行t的子任务的时间最大值：
任务的平均时间为：
nTask表示任务数。
3.遗传算法操作
3.1选取适应度函数
适应度函数用来度量种群之中个体在优化计算中有可能达到或者接近最优解的程度，它关系着算法的效率的高低。本文在选取适应度函数时，考虑到了在云计算中需要为多个用户执行不同的任务，在考虑到执行所有任务的效率的同时也要保证每个任务的执行效率在一个用户相对满意的范围之内。本文选用了所有任务（task）执行的平均时间函数avgTime作为主要衡量标准，并结合使用完所有任务完成总时间函数FTime来构造适应度函数：
在这里我们取u=0.7。在云计算中，所有任务执行的平均时间和任务完成的总时间不成正比，所以我们利用任务完成的总时间的平均值来调整平均任务执行时间的值，u就是调整系数。
3.2交叉与变异操作
本文在这里先进行普通的双点交叉处理，再进行维持原有访问顺序和编码格式的修改，并同时采用均匀交换变异方法对个体进行变异处理。利用随机数生成函数生成r∈[0， 1]，若r小于交叉概率x1，则进行交叉操作，否则什么也不做。与交叉类似，若r小于变异概率x2，则进行变异操作，否则保持原状。交叉和变异操作完成之后，比较生成的新个体的适应度函数值，留下新个体中适应度增加的个体，抛弃适应度降低的个体。经过多次迭代，生成若干组优化解，为蚁群算法做准备。
三、蚁群算法与遗传算法的融合
蚁群算法是根据蚁群集体寻找路径的行为提出的仿生进化算法，它具有提供正反馈，适合并行计算等特点，所以蚁群算法很适合来优化云计算中的并行任务调度效率。本文先采用遗传算法对Map/Reduce模型上的任务进行迭代调度，得到一些较优解，减少蚁群算法前期阶段积累信息素占用的时间。另外，蚁群算法在运行后期的高效率也能弥补遗传算法后期容易造成大量冗余迭代的缺点。 1.遗传算法与蚁群算法的衔接时机选择
遗传算法的后期易产生冗余迭代，在遗传算法运行合适的迭代次数后融合蚁群算法会优化算法的效率。在选择遗传算法和蚁群算法的衔接时机时，本文在这里借鉴了一种动态算法，首先设定遗传算法的最小迭代次数Gmin和最大迭代次数Gmax，并规定迭代后必须达到的子代种群进化率P，若迭代Gmin次后连续X代（0 2.蚁群算法的信息素设置
信息素更新模型：τjnew=ρ·τjold + Δτj，其中ρ是信息挥发系数（0≤ρ≤1）。在搜索过程中，蚁群算法根据每个资源上的信息量及启发信息来计算任务在t时刻分配到每个资源上的概率：
其中α是信息启发因子，β是期望启发因子，表示资源能见度的相对重要性。η作为启发函数，反映了任务分配到指定资源上的期望程度。
四、小结
本文根据云计算模型的特点，优化了遗传算法的编码方案；并改进了遗传蚁群算法的融合方法，让两者融合点的定位更加动态化。通过让云计算模型上各个资源节点上的负载更加均衡，任务调度更加高效。
参考文献：
[1]段海滨. 蚁群算法原理及其应用[ M ]. 北京： 科学出版社， 2 005： 385- 390.
[2]王小平， 曹立明. 遗传算法 [ M ]. 西安： 西安交通大学出版社，2002 .
[3]丁建立，陈增强，袁著址. 遗传算法与蚂蚁算法的融合[J].计算机研究与发展1999，36 （10）：1240-1245.
[4]康岚兰.基于遗传算法的混合蚁群算法研究[D].江西理工大学工学硕士学位论文.2008.
[5]彭建，于晓翠. 基于遗传算法与蚁群算法动态融合的网格任务调度[J].计算机应用与软件，2009，26（7）：121-124.
[6]吴吉义，平玲娣，潘雪增，等.云计算： 从概念到平台[J]. 电信科学，2009，25（ 12） ：23-30.
[7]田文洪，赵勇.云计算—资源调度管理[M].北京：国防工业出版社，2011.
[8]张为民，唐剑锋，罗治国，钱岭.云计算：深刻改变未来[M].北京：科学出版社，2009.
[9]房秉毅，张云勇，程莹.云计算国内外发展现状分析[J].电信科学.2010，8A：1-5.
[10]王庆波，金涬，何乐，等.虚拟化与云计算[M]. 北京：电子工业出版社，2010.
作者简介：
许树堃（1991—），男，汉族，内蒙古呼伦贝尔人，工学硕士，单位：大连交通大学计算机科学与技术专业，研究方向：计算机管理信息系统。
摘要：通过研究云计算的编程模型和多种分布式任务调度算法，提出一种改进的遗传蚁群算法，使用间接混合编码方式让每条染色体形成了单独的任务调度方案，利用遗传算法生成的优化解，解决了蚁群算法的前期信息素聚集慢的问题，提高了云计算中任务调度的效率。实验结果证明，本算法取得了不错的的结果。
关键词：云计算；遗传算法；蚁群算法
一、引言
近年来，互联网行业快速发展，云计算作为一种新兴的商业模式应运而生。云计算的特点是超大规模、虚拟化、高可靠性和通用性好等。目前，为人们所熟知的云平台有Google云计算、Amazon弹性计算云EC2、百度云平台和阿里巴巴云电子商务等[8]。
云计算通过网络将大型的计算任务拆分成较小的计算任务，交给大型分布式服务器系统处理，经过计算分析后将计算结果交给用户。因为在云计算的过程需要处理大量的任务，如何保证这些大量的计算任务能够正确、高效的被调度，成为了云计算之中的重点。本文采用遗传蚁群混合算法（Generic Algorithm Ant Colony Optimization， GAACO），通过结合遗传算法前期搜索速度快和蚁群算法后期搜索优势大的优点，对云计算中的任务调度进行优化，通过了仿真对比试验，验证了良好的性能。
二、算法
1.云计算编程模型Map/Reduce
随着云计算的兴起，越来越多的企业提出了自己的“云计划”，大多数企业都以Map/Reduce编程模型的思想来开发自己的云，Map/Reduce特别适合产生和处理大规模的数据集。Map/Reduce首先在Map阶段通过一个Map/Reduce函数把一个大型的计算任务分割成N个较小的子任务给多台工作主机并行执行。然后我们把在Map阶段生成的中间文件在Reduce阶段汇总分析处理，输出M个（M与Reduce任务数量一致）输出文件。
2.染色体的编码和解码
根据Map/Reduce编程模型的特点，在遗传算法执行阶段本文针对云环境中的资源和在资源中对任务的分配制定了一种间接编码方式（worker-task-subtask），利用随机函数随机生成一定数量的种群。每一个染色体都是对任务的子任务在资源中的分配方式的抽象。假设有m个任务，每个任务i的子任务数是subTask（i），子任务的总数n为：
第i个任务中第j个子任务的编号是：
假设云环境中资源总数为w，那么染色体的长度为w+n。前w（1，2，…w）个整数代表资源（worker），w+1到w+n代表分配给资源执行的子任务（subtask）。本文规定任务队列中的子任务分配到当前任务执行总时间最少的资源中。
假设w=3，m = 3， subTask （i） = i+1（i的范围是1到3），n的总数为9。那么对染色体实例{1，4，5，9，2，6，12，3，7，8，10，11}做出如下解释：任务1中的包含编号为1，2的子任务，任务2中包含编号为3，4，5，的子任务，任务3中包含编号为6，7，8，9的子任务。子任务1，2，6运行在资源1中，子任务3，9运行在资源2中，子任务4，5，7，8运行在资源3中。对染色体的解码能得到各个task的subTask在worker上的分布情况和各个worker上的任务执行序列。对上述染色体实例的解码为
Worker（1）：[1，2，6]， Worker（2）：[3，9]， Worker（3）：[4，5，7，8]
通过解码后的序列和ETC（Expect Time to Compute）矩阵（ETC[i，j]代表序号为i的subTask在第j个资源上执行完成所需要的时间）可以计算出每个资源的任务队列中所有nSub个子任务的执行时间：
则完成所有任务的总时间函数为：
假设第t个任务一共有s个子任务，第t个任务的完成时间为在w个资源中每个资源执行t的子任务的时间最大值：
任务的平均时间为：
nTask表示任务数。
3.遗传算法操作
3.1选取适应度函数
适应度函数用来度量种群之中个体在优化计算中有可能达到或者接近最优解的程度，它关系着算法的效率的高低。本文在选取适应度函数时，考虑到了在云计算中需要为多个用户执行不同的任务，在考虑到执行所有任务的效率的同时也要保证每个任务的执行效率在一个用户相对满意的范围之内。本文选用了所有任务（task）执行的平均时间函数avgTime作为主要衡量标准，并结合使用完所有任务完成总时间函数FTime来构造适应度函数：
在这里我们取u=0.7。在云计算中，所有任务执行的平均时间和任务完成的总时间不成正比，所以我们利用任务完成的总时间的平均值来调整平均任务执行时间的值，u就是调整系数。
3.2交叉与变异操作
本文在这里先进行普通的双点交叉处理，再进行维持原有访问顺序和编码格式的修改，并同时采用均匀交换变异方法对个体进行变异处理。利用随机数生成函数生成r∈[0， 1]，若r小于交叉概率x1，则进行交叉操作，否则什么也不做。与交叉类似，若r小于变异概率x2，则进行变异操作，否则保持原状。交叉和变异操作完成之后，比较生成的新个体的适应度函数值，留下新个体中适应度增加的个体，抛弃适应度降低的个体。经过多次迭代，生成若干组优化解，为蚁群算法做准备。
三、蚁群算法与遗传算法的融合
蚁群算法是根据蚁群集体寻找路径的行为提出的仿生进化算法，它具有提供正反馈，适合并行计算等特点，所以蚁群算法很适合来优化云计算中的并行任务调度效率。本文先采用遗传算法对Map/Reduce模型上的任务进行迭代调度，得到一些较优解，减少蚁群算法前期阶段积累信息素占用的时间。另外，蚁群算法在运行后期的高效率也能弥补遗传算法后期容易造成大量冗余迭代的缺点。 1.遗传算法与蚁群算法的衔接时机选择
遗传算法的后期易产生冗余迭代，在遗传算法运行合适的迭代次数后融合蚁群算法会优化算法的效率。在选择遗传算法和蚁群算法的衔接时机时，本文在这里借鉴了一种动态算法，首先设定遗传算法的最小迭代次数Gmin和最大迭代次数Gmax，并规定迭代后必须达到的子代种群进化率P，若迭代Gmin次后连续X代（0
信息素更新模型：τjnew=ρ·τjold + Δτj，其中ρ是信息挥发系数（0≤ρ≤1）。在搜索过程中，蚁群算法根据每个资源上的信息量及启发信息来计算任务在t时刻分配到每个资源上的概率：
其中α是信息启发因子，β是期望启发因子，表示资源能见度的相对重要性。η作为启发函数，反映了任务分配到指定资源上的期望程度。
四、小结
本文根据云计算模型的特点，优化了遗传算法的编码方案；并改进了遗传蚁群算法的融合方法，让两者融合点的定位更加动态化。通过让云计算模型上各个资源节点上的负载更加均衡，任务调度更加高效。
参考文献：
[1]段海滨. 蚁群算法原理及其应用[ M ]. 北京： 科学出版社， 2 005： 385- 390.
[2]王小平， 曹立明. 遗传算法 [ M ]. 西安： 西安交通大学出版社，2002 .
[3]丁建立，陈增强，袁著址. 遗传算法与蚂蚁算法的融合[J].计算机研究与发展1999，36 （10）：1240-1245.
[4]康岚兰.基于遗传算法的混合蚁群算法研究[D].江西理工大学工学硕士学位论文.2008.
[5]彭建，于晓翠. 基于遗传算法与蚁群算法动态融合的网格任务调度[J].计算机应用与软件，2009，26（7）：121-124.
[6]吴吉义，平玲娣，潘雪增，等.云计算： 从概念到平台[J]. 电信科学，2009，25（ 12） ：23-30.
[7]田文洪，赵勇.云计算—资源调度管理[M].北京：国防工业出版社，2011.
[8]张为民，唐剑锋，罗治国，钱岭.云计算：深刻改变未来[M].北京：科学出版社，2009.
[9]房秉毅，张云勇，程莹.云计算国内外发展现状分析[J].电信科学.2010，8A：1-5.
[10]王庆波，金涬，何乐，等.虚拟化与云计算[M]. 北京：电子工业出版社，2010.
作者简介：
许树堃（1991—），男，汉族，内蒙古呼伦贝尔人，工学硕士，单位：大连交通大学计算机科学与技术专业，研究方向：计算机管理信息系统。