云计算环境下基于遗传蚁群算法的任务调度

     云计算环境下基于遗传蚁群算法的任务调度                  周彬（江苏省扬州商务高等职业学校信息系，江苏扬州225000）摘要：研究了云计算环境下的任务调度问题，通过构造云计算环境下的任务调度模型，提出了一种混合调度算法，该算法是蚁群算法与遗传算法的有机融合。其中的遗传算法采用间接编码方式，结合由遗传算法衍生出的优化解，对蚁群信息素的分布进行初始化处理，使遗传算法的快速搜索能力得到充分利用，并通过克服蚁群算法的起始信息素不足问题，加快了求解速度。云计算环境下的仿真实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，该混合算法是一种行之有效的任务调度算法。关键词：云计算；遗传算法；蚁群算法；任务调度DOI：10.11907/rjdk.143557TP311.5：A：1672?7800（2014）012?0063?02作者简介：周彬（1980-）,男，江苏扬州人，硕士，江苏省扬州商务高等职业学校信息系讲师，研究方向为计算机应用技术。0引言迄今为止，我国课题研究领域仍极度重视对云计算环境下的任务调度问题的研究。然而由于缺乏一个完善的云计算环境下的任务调度理论，导致研究无法通过系统的科学方法进行。无论采用遗传算法还是蚁群算法，都无法获得理想的实际效果。由此可见，实现不同算法的融合具有非常重要的意义。而本文阐述的是一种将蚁群算法与遗传算法进行融合的混合调度算法，即云计算环境下基于遗传蚁群算法的任务调度方法，可极大提高云计算环境下的任务执行效率。1云计算环境下的任务调度模型构造云计算环境下任务调度的含义是：在云计算环境中，将p个彼此相互独立的子任务全部分配到q个虚拟机上执行任务，其中p与q存在以下关系，即：p＜q。等待处理的任务用集合的形式表示:A={a1,a1,...,ap}，其中ai表示待处理任务中的第i个子任务；云资源中的虚拟机也可用集合的形式表示：B={b1,b2,...,bq},其中bj表示云资源中第j个虚拟机。1.1编码 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 设计合理的编码应综合考虑蚂蚁的种族遗传以及蚂蚁群的初始状态［1］，本文采用间接方式进行编码。设定染色体基因长度为子任务数q，而子任务在虚拟机bj上的执行相当于染色体在基因上的表示，如染色体集合为:{1，2，3，3，4，6，…，p－1，p}，表示子任务ai放置在对应的bj上，确保所有子任务a都能放置在全部虚拟机B上。这样就可以通过反推，得到虚拟机bj上所有子任务的集合bj={a1,a1,...,ai}。由虚拟机bj处理后，计算出完成所有子任务的预测时间，并用矩阵E表示任何一个任务ai被分配在虚拟机bj上执行的预测时间［2］。此外，除了考虑虚拟机本身的处理能力外，还应结合使用Ｒ（bj）表示虚拟机bj的运行成本。因此得到虚拟机上的任何一个子任务都可以描述为:（ai,bj,E（ai,bj））（i∈［1,q］,j∈［1,p］）1.2目标函数构造通过计算矩阵E可以得出虚拟机bj执行所有任务时，所花费的预测时间X(bj)为:X(bj)=∑pj=1time(aj,bj)(i∈［1,q］)云计算是通过分布计算进行求解的，而不同任务之间是同步执行的，因此可以将所有虚拟机X(bj)中的最大值作为完成所有子任务所需的时间值［3］，任务完成所需时间可以用如下公式表示:max(X(bj))(j∈［1,p］)云计算环境下的任务调度应综合考虑时间要求与其它成本要求，如费用成本等，因此最终得到目标函数为:∑pj=1X(bj)×R(bj)(j∈［1,p］)2遗传算法与蚁群算法融合蚁群算法是一种对全局进行优化的方法，通过模拟真实的蚁群寻径行为，对种群的原始仿生进化进行计算，能够对相关信息进行正反馈，并能模拟负载情况［4］。然而其缺乏初期信息素，导致需要花费大量时间搜索初期积累的信息素。有研究已得出结论：蚁群算法搜索初期信息素的时间占总时间的70%以上。遗传算法在求解效率上过于偏低，导致求解过程中容易造成大量多余迭代，使蚁群算法与遗传算法之间的衔接受到影响。以往通过固定遗传算法的迭代次数实现衔接，但无法得到最好效果。本文通过动态融合策略，将遗传算法与蚁群算法有机融合，以确保迭代次数既不冗余又能达到最好的计算效果［5］。具体步骤如下：将最小以及最大遗传迭代次数预先设定好，在进行遗传迭代时及时记录子代群体的进化率，将此进化率作为子代群体的最小进化率。3遗传算法具体求解步骤3.1适应度函数选取在云计算环境下的遗传算法中选取适应度函数应谨慎，因为其会直接影响到所得解的优劣性以及收敛速度的快慢。云计算一般同时为多位客户提供服务，因此可以将每个用户的响应时间进行综合考虑，使每位用户都能满意。为了实现这个目的，可以将响应时间用任务平均完成时间进行衡量。云计算的特殊性要求每一个用户程序必须分为多个子任务执行，这样总任务的完成时间就能达到理想状态［6］。所以遗传算法可以选取任务的平均所用时间函数作为适应度函数。3.2信息素初始化虚拟机在云计算环境中的性能存在差异性，所以初始化该环境中的虚拟机信息素时，应根据虚拟机各自的性能参数，初始化每台虚拟机的信息素，而不能简单地将其设置为空［7］。虚拟机的性能差异性主要指处理器的计算能力差异，因此应根据虚拟机的不同计算能力初始化相应信息素:Aj(0)=Mj×Sj其中Aj(0)表示对第j台虚拟机信息素进行初始化的数值，Mj代表虚拟机中PE的个数，Sj代表单独的PE处理能力。3.3信息素更新处理可以根据前一次所得解集对虚拟机上的信息素进行更新处理，如果用Aj(t)表示t时刻虚拟机bj的信息素浓度，则在t+l时刻虚拟机bj上的信息素浓度Aj(t+L)可由如下公式计算：Aj(t+L)=(1-q)×Aj(t)+q×ΔTj式中q代表信息素的挥发程度，1-q则代表信息素的残留程度，q的取值范围为q∈(0，1］，信息素的挥发程度随着q值的增大而增大，也即下一个虚拟机bj的选择程度也将随之降低［8］。信息素的增量ΔAj有如下计算公式：ΔAj=0或min(Z(i))/d其中d为常量，Z(i)表示完成子任务时的资源需求情况。4仿真实验4.1实验基本条件设定由于云计算局部类似于一个具有特殊结构的网格环境，所以可以借助网格仿真工具局部模拟云过程，与此同时，观察本算法在云计算环境下的具体运行情况。模拟时将两种算法进行比较，设置初始参数如表1所示。4.2实验结果根据表1初始参数的设置，结合两种算法在搜寻40%可用节点时显示的仿真结果（显示结果均取平均值）：Points：50Usable-Points：20MPeriod-cost：210.01MThe-variance：0.40Mfly-past：40.12NPeriod-cost：199.987NThe-variance：0.70Nfly-past：41.13　在搜寻20%可用节点时显示的仿真结果为：Points：100UsablePoints：40MPeriod-cost：1351.70MThe-variance：0.50Mfly-past：36.21NPeriod-cost：976.57NThe-variance：0.60Nfly-past：36.49对比搜寻两个不同可用节点时的仿真结果发现，可用节点比率越小，本算法优势越为明显，也就是说在云计算环境下的任务调度中应用本算法是明智的。接下来通过改变初始参数进行深入研究，设置参数如表2所示。再次进行对比发现，扩大搜索规模能使本算法优势更加明显。图1即为根据表1所设置的两种算法的初始模拟结果曲线图。5结语综上所述，本文从云计算环境的特点出发，将蚁群算法与遗传算法进行融合，构建合理的云计算任务调度模型并提出科学的编码方案，以解决云计算环境下的任务调度问题。遗传算法与蚁群算法相互融合形成的混合任务调度算法，有效提高了云计算环境下的任务执行效率，缩短了任务的平均执行时间,从而大大提高了资源利用率。这种特殊的融合算法使在云计算环境下进行有效任务调度的目的得以实现，并在任务调度上达到最好效果。参考文献：\[1\]李玉庆,徐敏强,王日新,等.基于蚁群算法的航天器观测动态调度研究［J］.计算机测量与控制,2012,10(12):13?14.［2］张晓杰,孟庆春,曲卫芬.基于蚁群优化算法的服务网格的作业调度［J］.计算机工程，2011,8（4）:32.［3］丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合［J］.计算机研究与发展,2013,9(5):63.［4］周文丽,张正青，刘小青.网格环境下任务调度算法的应用研究［D］.大连：大连海事大学，2013.［5］李建锋,彭雨舰，冯玉如.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用,2012,6(2):40.［6］叶春晓,陆文杰，周思涵.基于改进遗传算法的网格任务调度研究［J］.计算机科学,2012,5(3):43.［7］华夏渝,郑敏骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法［J］.华东师范大学学报：自然科学版,2011,6(2):12.［8］刘永春,王新华,邢长明,等.云计算环境下基于蚁群优化算法的资源调度策略［J］.计算机技术与发展,2013,9(5):3.（责任编辑：黄健） -全文完-