(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211121786.3 (22)申请日 2022.09.15 (71)申请人 大连大学 地址 116622 辽宁省大连市经济技 术开发 区学府大街10号 (72)发明人 周士华　王思婕　胡轶男　 (74)专利代理 机构 大连智高专利事务所(特殊 普通合伙) 2123 5 专利代理师 盖小静 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) (54)发明名称 一种异构云环 境下多目标MAVOA算法优化任 务调度方法 (57)摘要 本发明公开了一种异构云环境下多目标 MAVOA算法优化任务调度方法， 该方法首先对异 构云环境下的任务调度问题进行建模， 明确目标 函数、 变量范围以及约束条件； 其次将MAVOA中的 种群个体位置对应于任务与处理机之间映射问 题的候选解， 其中位置向量的每一个维度代表一 个分配规则。 最后， MVAOA通过多次迭代得出最优 候选解和最优适应度值， 其中最优候选解即为任 务与处理器节 点的最佳映射关系， 而最优适应度 值则是目标函数的最小化平台耗费成本。 本发明 能够获得优秀的任务调度方案， 良好地解决平台 中系统资源利用不均的问题， 有效地降低平台服 务成本。 权利要求书3页 说明书5页 附图3页 CN 115454601 A 2022.12.09 CN 115454601 A 1.一种异构云环境下多目标MA VOA算法优化任务调度方法， 其特 征在于， 包括： 步骤1： 对异构云环境下的任务调度问题进行建模， 确定优化目标和约束条件， 并得到 所述任务调度问题的目标函数； 步骤2： 设定maxiterations和种群数量N， 获取初始种群X， 所述种群中的个体表示任务 和处理器节点之间的映射关系， 每个个体Xi的位置对应着一个候选解， Xij则代表了第i个候 选解的第j个维度上 数值， 即第i个任务绑定在处 理器节点j上； 步骤3： 根据 所述任务调度问题的目标函数评估种群； 获取每个候选解的适应度值F； 更 新当前最优候选解BestX、 Seco ndBestX和最优适应度值BestF、 Seco ndBestF； 步骤4： 获取判断值P1， 将适应度 值F大于1且判断值P1大于随机数rand的候选解标记为 1类候选解， 将适应度值F大于1且判断值P1小于等于随机数rand的候选解标记为2类候选 解， 并更新所述1类候选解和2类候选解； 步骤5： 当第t次迭代的最优适应度值BestFt与第t‑1次迭代的最优适应度值BestFt‑1相 等时， 突变计数count加1； 当所述突变计数count累积到设定值时发生一次个体位置更新， 此时突变 计数count归0， 转至步骤9； 步骤6： 获取判断值P2， 将适应度值F大于等于0.5、 小于1且判断值P2大于等于随机数 rand的候选解标记为3类候选解； 将适应度值F大于等于0.5、 小于1且判断值P2小于随机数 rand的候选解标记为 4类候选解， 并更新所述3类候选解和4类候选解； 步骤7： 获取判断值P3， 将适应度 值F小于0.5且判断值P3大于等于随机数rand的候选解 标记为5类候选解； 将适应度值F小于0.5且判断值P3小于随机数rand 的候选解标记 为6类候 选解； 并更新所述5类候选解和6类候选解； 步骤8： 使用基于Metropolis准则的局部调度策略优化种群中的非支配解， 并更新溢出 边界范围的个 体位置， 进 而更新种群； 步骤9： 通过动态阈值分类处理节点， 采用修正后的余弦相似度负载均衡策略迁移过载 以及轻载处理节点上的任务， 均衡系统资源利用率， 并更新个 体位置； 步骤10： 判断是否达到最大迭代次数， 若达到最大迭代次数则进行步骤11， 否则返回步 骤3。 步骤11： 得到最优候选解BestX和最优适应度值BestF， 所述最优候选解BestX即为任务 与处理器节点的最佳映射关系， 所述最优适应度值BestF即为目标函数的最小化平台耗费 成本。 2.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤4中的1类候选解采用式(1)更新， 2类候选解采用式(2)更新： P(i+1)＝|cei l(R(i)‑F*|2*rand*R(i) ‑P(i)|)mod  m| if P1≥randP1   (1) P(i+1)＝|cei l(R(i)‑F+rand2*((ub‑lb)*rand3+lb))mod m|if P1<randP1 (2) 权　利　要　求　书 1/3 页 2 CN 115454601 A 2其中， rand是介于(0,1)之间的随机数， ceil是向上取整， R(i)是最佳秃鹜之一， 最佳秃 鹜即为当前迭代次数下任务与处理器节点的最优映射关系， P(i +1)是下一次迭代中的秃鹜 位置向量， 该秃鹜位置向量即为优化调整后任务与处理器节点的映射关系， P(i)是秃鹜当 前的矢量位置， It erationi表示当前迭代次数， maxit erations表示最大迭代次数， F表示随 迭代次数变化的数值， z是介于( ‑1,1)的随机数， h是介于( ‑2,2)之间的随机数； ub和lb为个 体的上界向量和下界向量， m为虚拟机的数量； L1、 L2为更新操作所 给定的参数。 3.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤5中按照式(7)更新个 体位置： 其中， floor表示向下取整， X(n)表示当前迭代次数下任务与处理器节点间的映射关 系， U表示一个常数， 1e4是科学计数； 当循环次数小于总迭代次数的一半时， 采用plm规则更 新， 反之则采用lm规则更新。 4.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤6中的3类候选解采用式(8)更新， 4类候选解采用式(9)更新： P(i+1)＝|cei l(D(i)*(F+rand4)‑R(i)+p(l) )mod m| if P2≥randP2 (8) 5.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤7中的5类候选解采用式(10)更新， 6类候选解采用式(1 1)更新： P(i+1)＝|cei l(R(i)‑|d(t)|*F*levy(d) )mod m|if P3<randP3   (11) 其中， B1(i)表示当前迭代中第一 组的最佳任务调度方案， B2(i)表示当前迭代中第二 组 的最佳任务调度方案； d(t)表 示当前任务调度方案与当前迭代中两组的最佳任务调 度方案 之间差距， levy(d)为有规 律的更新机制。 6.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤8中按照式(12)更新溢出边界范围的个 体位置： 其中， betarnd表示生成服从betarnd分布的随机数， 表示第t次迭代中更新后的个体 向量的第i行第j列数值超过任务总体数量。 7.根据权利要求1所述一种异构云环境下多目标MAVOA算法优化任务调度 方法， 其特征 在于， 步骤9中按照式(13)、 (14)更新个 体位置：权　利　要　求　书 2/3 页 3 CN 115454601 A 3