HGPSO algorithm in cloud computing environment

一、介绍

优化目标

任务调度将用户任务分配到资源上，以最大化资源利用率和最小化任务执行时间为目标。

HGPSO 的主要讨论点

提出一种基于优先级的任务调度器，根据优先级对任务进行排序。优先级根据任务所需要的时间长度和内存大小。
该算法从 on-demand 队列中取出输入，然后给任务分配合适的资源。

二、相关工作

略

三、问题表述

QoS 指标：执行时间、可伸缩性、可用性

$ T $ ：执行的总时间

$ vm $ ：虚拟机

$ R $ ：资源

$ St $ ：在资源 r 上执行任务的开始时间

$ Ft $ ：在资源 r 上执行任务的结束时间

$ CTir $ ：资源 r 上任务 i 的完成时间

$ SCir $ ：资源的可伸缩性

$ AVir $ ：资源的可用性

$ M $ ：估计是任务的数量

$ k $ ：估计是资源的种类

$\begin{array}{l} \text { CTir }=\sum_{i=1}^{M} F t_{i}-S t_{i}, 1 \leq \mathrm{i} \leq \mathrm{M}, 1 \leq \mathrm{r} \leq \mathrm{k} \\ \text { SCir }=\sum_{i=1}^{M} v m_{i} / R r, 1 \leq \mathrm{i} \leq \mathrm{M}, 1 \leq \mathrm{r} \leq \mathrm{k} \\ \text { AVir }=\sum_{i=1}^{M} v m i / T, 1 \leq \mathrm{i} \leq \mathrm{M}, 1 \leq \mathrm{r} \leq \mathrm{k} \end{array}$

(这公式给的就离谱，看不懂什么意思，而且就不应该出现求和符号，后面还有一个公式会对 $ r $ 和 $ i $ 进行求和)

四、本文提出任务调度模型

Queue Manager：用户提交的任务首先进入这里，检查任务是否在历史中出现过。

如果出现过，则将用户任务送到 Priority Queue ，分配之前的优先级和之前的资源。
如果没有出现过，则将用户任务送到 On-Demand Queue，然后送到 HGPSO 算法中分配优先级，分配资源。

算法流程：

使用遗传算法生成初始的种群
使用选择操作，从种群中选择若干合适的个体（染色体），选择出的个体作为粒子群的粒子。
然后粒子群优化算法通过 pbest 和 gbest 找到最好的粒子（实际上就是做了一个局部搜索）
然后从种群中随机选择一个，和最好的粒子做 croswsover 操作
然后进行变异操作，分配资源（？？？）

基于优先级的任务调度

给任务分配优先级。

历史记录中存在的，直接分配。新的任务通过任务时长和任务内存大小分配。

基于HGPSO的任务调度

On-demand queue 输出到 HGPSO 算法，HGPSO 算法调用遗传算法初始化个体。把任务和资源编码为染色体。资源是里面的一个基因。

基因和染色体
在遗传算法中，我们首先需要将要解决的问题映射成一个数学问题，也就是所谓的“数学建模”，那么这个问题的一个可行解即被称为一条“染色体”。一个可行解一般由多个元素构成，那么这每一个元素就被称为染色体上的一个“基因”。
比如说，对于如下函数而言， $ [1,2,3]、[1,3,2]、[3,2,1] $ 均是这个函数的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均被称为染色体。
$ 3x+4y+5z<100 $
这些可行解一共有三个元素构成，那么在遗传算法中，每个元素就被称为组成染色体的一个基因。

在该问题中，任务和资源分别为染色体中的一个（或多个，毕竟资源有很多，任务限制也有很多）基因。

评估函数：

$\text{Fitness} = \min \sum_{ir} \frac{1}{CT_{ir}} + \max \sum_{ir}(AV_{ir} + SC_{ir})$

（所以说上面不应该带求和，这里有求和，上面那个求和看起来有点问题）

通过评价函数选出个体，然后转化为粒子群的粒子

$T_{i}^{S}(0)=\alpha \cdot G A_{n}$

其中 $ \alpha $ 是一个常数， $ GA_n $ 是遗传算法中的一个个体（就是一个可行解）， $ T_{i}^{S}(0) $ 是粒子群的一个粒子。

PSO 使用 PSO 的随机初始化操作初始化粒子。PSO 根据 pbest 和 gbest 值对所有任务进行评估，一旦 pbest 和 gbest 值更大，这些任务将被更新。每次更新速度和位置使用的是下面的公式：

$\begin{aligned} V(t)=& \omega v_{1}(t-1)+k_{1} n_{1}\left(x_{1} \wedge(t-1)-x_{1}(t-1)\right.\\ &+k_{2} n_{2}\left(x^{*}(t-1)\right)-x_{1}(t-1) \end{aligned}$

$ x_1(t) $ 是位置数组， $ i $ 是粒子下标， $ v_1(t) $ 是速度数组， $ x_1 \wedge (t-1) $ 是粒子的位置， $ x(t - 1) $ 是最好位置数组， $ n_1,n_2 \in [0,1] $ ， $ k_1,k_2 $ 是非负常量， $ \omega $ 是惯性常量

（粒子群优化算法不太懂，这部分不太明白）

最好的粒子的值会被解码，然后交给遗传算法，做 crossover 操作。.通过将交叉步骤中产生的 1s 到 0s 和 0s 到 1s 进行交换，产生全新的染色体，并对后代进行翻转突变，以保持遗传多样性。最后，将HGPSO算法输出的合适资源分配给用户任务。

算法运行的一些参数设置

五、结果分析

略

六、结论

略

参考：

10分钟搞懂遗传算法(含源码) - 知乎 (zhihu.com)

Task scheduling in a cloud computing environment using HGPSO algorithm

Luobuyu's Blog

HGPSO算法