云计算任务优化调度关键技术：遗传蚁群融合算法

提出的遗传蚁群融合算法的思想为在遗传算法中利用改进的遗传设计中的编码设计、选择及交叉设计，将搜索解的空间进一步扩大，得到融合算法路径上的信息素分布，再利用改进的蚁群算法对云数据中心的任务调度求得精确解。其中融合转化点为在前期进行遗传算法时，记录迭代中不同子代种群的进化率，在给定的种群迭代进行的范围内，连续多代的进化率都小于给定的最小进化值，则转入蚁群算法，继续执行。

（1）算法执行过程

算法　MGAA算法

步骤1：设置遗传算法中种群规模的大小，交叉算子以及变异概率Pm；

步骤2：对用户任务进行编码设置，进行适应度函数定义；

步骤3：对种群中的个体进行解码，为下一步遗传操作做准备；

步骤4：计算种群中个体的适应度值，对种群进行选择操作，选出适应度高的个体进入遗传的其他操作；

步骤5：对选出的父代个体使用交叉算子进行交叉操作，产生新个体；

步骤6：对新个体利用变异概率Pm进行变异操作，得到新的群体；

步骤7：依据筛选原则，选出优秀个体作为最终的新群体；

判断遗传和蚁群算法的融合条件：若此时的遗传代数Gcurrent，Gmin＜Gcurrent＜Gmax，当前进化率rcurrent满足rcurrent＞re，则转到步骤4，否则到步骤8；

步骤8：根据遗传算法退出时所得到的当前最优调度方案，将m只蚂蚁分别置于相应的计算节点中，并为每个计算节点的信息素分别赋初值；(www.xing528.com)

步骤9：将每个蚂蚁当前所在的计算节点分别放置于各自的解集；

步骤10：对于每个个体i中的数据，节点记录所有访问的资源请求；

步骤11：检查每个计算节点上的任务执行情况，并根据具体的任务执行结果，为每个计算节点赋予不同的信息素增量；

① 如果有任务从个体i上执行成功并返回，为该节点赋予信息素增量Δδ，其值为节点信息素差值；

②如果有任务从个体 i上执行失败并返回，为该节点赋予信息素增量Δδ'；

步骤12：更新所有计算节点的信息素值；

步骤13：检查是否有计算节点加入或退出云数据中心，对于新加入的节点，根据其计算能力为其设置信息素初始值，对于退出的节点，将其信息素值置零；

步骤14：根据各计算节点的信息素分布情况，计算资源分配概率，基于得到的最大分配度为每只蚂蚁分别选取下一个计算节点；

步骤15：当算法达到最大遗传代数Gmax，则输出最优调度策略，否则返回步骤8。

（2）算法时间复杂度分析

为了更方便分析算法时间复杂度，设需要调度的任务数为m，对应的可分配资源节点数为p，根据遗传算法选择最优的算法原理，经过交叉、变异过程，在此基础上进行蚁群算法，算法的时间复杂度为O（pm）×O（m）×O（m）=O（pm3）。