(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210921087.0 (22)申请日 2022.08.02 (71)申请人 集美大学 地址 361000 福建省厦门市集美区银 江路 185号 (72)发明人 黄兴旺　张宗良　苏锦河　李超鹏　 (74)专利代理 机构 厦门市精诚新创知识产权代 理有限公司 3 5218 专利代理师 张锐 (51)Int.Cl. G06F 9/455(2006.01) G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) (54)发明名称 基于一维灰狼算法云计算任务调度方法、 装 置及存储介质 (57)摘要 本发明提供了一种基于一维灰狼算法云计 算任务调度方法、 装置及存储介质， 所述方法针 对云计算环境下的任务调度问题， 在灰狼算法 中， 采用了一维的实数直接编码方式进行编码， 使得种群大小等于待调度的任务数， 每个灰狼个 体表示一个任务到虚拟机节点的分配； 进一步 地， 采用贪心算法对在灰狼算法中所更新的种群 进行赋值更新， 直到符合结束条件， 获取种群适 应度值最小的云调度方案作为最终的云计算任 务调度方案。 本发明将搜索空间降至一维， 同时 有机整合了进化算法的高性能和贪心算法的高 效率的优点， 消除了种群大小的超参设置， 优化 了云计算资源分配， 减少了云计算任务的总运行 时间， 提高了所分配的云计算任务的计算效率。 权利要求书2页 说明书8页 附图2页 CN 115145694 A 2022.10.04 CN 115145694 A 1.一种基于一维灰狼算法的云计算任务调度的方法， 其特 征在于， 包括： S1,确定云计算任务调度要解决的问题为： 将N个云计算任务分配给M个虚拟机， 使所述 N个云计算任务的总完成时间最小， 其中N和M均为自然 数， 其中， 在灰狼算法中将所述N个云 计算任务中的每一个任务分配到对应虚拟机的调 度方案的组合构建为一个灰狼种群， 所述 灰狼总群的大小为 N； S2,采用一维的实数对所述灰狼种群进行编码并初始化所述灰狼种群， 所述灰狼种群 中， 每个灰狼个 体都是一维的整数， 表示 其中的一个 计算任务到虚拟机的调度方案； S3,将所述N个云计算任务的总完成时间作为适应度函数计算所述灰狼种群中所有个 体所表示的调度方案的适应度值； S4,判定所计算的适应度值或迭代次数是否满足预设的终止条件； 如是， 则将此时适应 度值最小的种群编码作为所述N个 云计算任务的最终云计算任务调度方案， 并结束流程； 如 否， 则执行步骤S5； S5,利用预设的贪心策略对当前 灰狼种群中的随机个 体进行更新； S6,计算更新后的种群编码所表示的调度方案的适应度值， 重复步骤S4 ‑S6。 2.根据权利要求1所述的方法， 其特 征在于， 步骤S2的初始化 步骤包括： S21,利用随机生成函数生成一个灰狼个体数量等于任务数量的种群parent， parent为 变量， 种群parent中每 个灰狼个 体的维度为1， 所述灰狼个 体的取值范围为[1,M]； S22,对所述灰狼个 体使用取整函数， 得到邻近的整数值； S23,令表示适应度值最优的三个任务调度方案对应的种群编码α、 β和δ的适应度值都 为inf， 其中inf表示正无穷大， 所述种群编码α、 β和 δ对应的位置编码alpha_pos、 beta_pos 和delta_pos取值都设为1xN的全0向量。 3.根据权利要求2所述的方法， 其特征在于， 利用适应度函数计算种群的进化适应性， 所述适应度函数为fobj＝max(timei)， i∈(1,2,3, ……,M)， 式中， M为虚拟机的数量， timei 表示完成虚拟机i上 所有云计算任务所用的总时间。 4.根据权利要求3所述的方法， 其特征在于， 所述步骤S5 中对当前种群 中选定的个体进 行更新的步骤为： 利用适应度值最优的三个调度方案对应的种群编码α、 β 和 δ对种群中的个 体进行更新， 生成下一代种群， 然后用生成的下一代种群中的第一个灰狼个体随机更新原 来调度方案中对选 定任务所分配的虚拟机映射。 5.根据权利要求4所述的方法， 其特征在于， 步骤S5对当前种群中的随机个体进行更新 的步骤为： S51,利用所述 适应度函数计算当前 所述种群parent的适应度值； S52,根据所述种群parent的适应度 值更新所述α、 β和 δ 的适应度 值， 并分别更新各自对 应的种群位置编码alpha_pos、 beta_pos和delta_pos； S53,令下一代种群为offspring， 利用当前parent的种群编码初始化所述offspring种 群； S54,利用所述offspring、 种群大小N、 灰狼个体取值范围、 灰狼算法权重因子a以及所 述α、 β和 δ 的位置编码执行灰狼算法狩猎操作， 生成表示候选的任务调度方案的位置编码， 用candidatePos表示； S55,利用所述候选 的任务调度方案的位置编码candidatePos中的第一个灰狼个体取权　利　要　求　书 1/2 页 2 CN 115145694 A 2值， 贪心替换所述offspring种群随机选定任务分配的映射， 生成新的候选调度方案， 并赋 值给offspring， 同时删除所述candidatePos种群第一个灰狼个 体； S56,利用适应度函数公式计算该候选任务调度方案offspring的适应度值， 若所得适 应度值小于parent种群的适应度值， 则利用offspring更新parent种群及其适应度值， 否则 不进行操作； S57,判断candidatePos是否为空， 如是， 则结束本流 程； 如否， 则返回步骤S5 5。 6.根据权利要求5所述的方法， 其特征在于， 步骤S54所述权重因子 a随着迭代次数的变 化， 从2线性 地减少到 0， 所述狩猎 操作为： 根据所述灰狼种群offsp ring， 计算所有 N个灰狼个体的值Xi， 组成表示候选的任务调度 方案编码的candidatePos种群， 其中， i∈(1,2,3, ……,N)， 所述Xi计算方法包括： S5401， 利用随机生成函数分别生成2个[0， 1]之间的随机数r1、 r2； S5402， 利用A1＝2ar1‑a， C1＝2r2， 计算灰狼算法在包围猎物阶段α 的协同系数A1和C1； S5403， 利用公式Dα＝|C1·Xα‑X|计算当前offspring种群第i维候选灰狼和α种群第i维 灰狼之间的距离， 其中X表示所述offspring种群第i维灰狼的值， Xa表示α种群第i维灰狼的 值； S5404， 利用公式X1＝Xα‑A1·Dα计算猎物在α周边的候选解 位置X1； S5405， 利用随机生成函数分别生成2个[0， 1]之间的随机数r1、 r2； S5406， 利用A2＝2ar1‑a， C2＝2r2， 计算灰狼算法在包围猎物阶段α 的协同系数A2和C2； S5407， 利用公式Dβ＝|C2·Xβ‑X|计算当前offspring种群第i维候选灰狼和β 种群第i维 灰狼之间的距离， 其中X表示所述offspring种群第i维灰狼的值， Xβ表示β 种群第i维灰狼的 值； S5408， 利用公式X2＝Xβ‑A2·Dβ计算猎物在β周边的候选解 位置X2； S5409， 利用随机生成函数分别生成2个[0， 1]之间的随机数r1、 r2； S5410， 利用A3＝2ar1‑a， C3＝2r2， 计算灰狼算法在包围猎物阶段δ 的协同系数A3和C3； S5411， 利用公式Dδ＝|C3·Xδ‑X|计算当前第i维候选灰狼和δ种群第i维灰狼之间的距 离， 其中X表示所述 offspring种群第i维灰狼的值， Xδ表示 δ种群第i维灰狼的值； S5412， 利用公式X3＝Xδ‑A3·Dδ， 计算猎物在 δ周边的候选解 位置X3； S5413， 利用公式Xi＝(X1+X2+X3)/3， 更新所述 offspring种群在i维的灰狼的位置值； S5414， 利用取整函数对Xi做取整处 理， 使其值为[1， M]之间的整数。 7.一种实现基于一维灰狼算法的云计算任务调度的方法的装置， 其特征在于， 所述装 置包括存储器和处理器， 所述存储器存储有至少一段程序， 所述至少一段程序由所述处理 器执行以实现如权利要求1至 6任一所述的基于一维灰狼算法的云计算任务调度的方法。 8.一种计算机可读存储介质， 其特征在于， 所述存储介质中存储有至少一段程序， 所述 至少一段程序被处理器执行以实现如权利要求1至6任一所述的基于一维灰狼算法的云计 算任务调度的方法。权　利　要　求　书 2/2 页 3 CN 115145694 A 3