基于集合型离散粒子群优化的云工作流调度方法

摘要

本发明公开了一种基于集合型离散粒子群优化算法的云工作流调度方法，该方法针对带有不同服务质量QoS需求的云工作流调度问题，采用了一类新型的集合型粒子群优化算法，通过将粒子群优化的速度、位置和相关的更新操作在离散的集合空间重定义，从而能够满足对离散空间的云工作流调度优化问题的应用需求，提高了云工作流调度的效率。

主权项

1.一种基于集合型离散粒子群优化算法的云工作流调度方法，其特征在于，采用了集合型离散粒子群算法来实现对云工作流的调度，算法具有如下的计算步骤：(1)初始化算法的各个参数，并建立第一代粒子群的位置和初始速度，粒子的编码方式为：X＝(X¹，X²，...，Xⁿ)其中Xⁱ∈S_i，S_i表示能用于执行第i个任务T_i的所有云计算服务的集合，初始化时Xⁱ用完全随机的方式生成；速度的编码方式为：V＝(V¹，V²，...，Vⁿ)其中每一维度是一个带有可能性的集合V^j＝{e/p(e)|e∈S_j}，表示集合S_j中的每一个元素e都关联着一个可能性p(e)，初始化时随机从S_j里面选择一个元素，并且分配一个随机的可能性p(e)∈(0，1]给这个元素，其它所有没选的元素的可能性都为0；(2)根据粒子当前的位置评估每个粒子的适应度值；(3)更新每个粒子的个体最优位置；(4)更新粒子的速度，公式为：$v_i^j\leftarrow \omega ·v_i^j+{\mathrm{cr}}^j({\mathrm{pbest}}_{f_i\left(j\right)}^j-x_i^j),j=\mathrm{1,2},...,n$其中下标i表示第i个粒子，上标j表示维度，ω是惯性权重，c是参数，r^j是位于[0，1]区间的随机数，表示第f_i(j)个粒子的历史最优位置的第j维，f_i(j)定义如下：首先产生一个处于[0，1]区间的随机数ran，如果ran比给定的参数Pc大，f_i(j)＝i，否则算法会对两个随机选择的粒子进行锦标赛选择，适应度值更大的那个会被选中为f_i(j)；在这个更新公式中，由于速度和位置的定义已经不再在连续的实数空间中定义，而是在离散的集合空间中定义，因此更新公式的相关操作也需要重新定义：(i)参数×速度：cV＝{e/p^l(e)|e∈E}，$p^l\left(e\right)=\left\{\begin{array}{cc}1,& \mathrm{if\; c}\times p\left(e\right)>1\\ c\times p\left(e\right),& \mathrm{otherwise}\end{array}\right.$(ii)位置-位置：$A-B=\left\{e\right|e\in \mathrm{A\; and\; e}\notin B\}$(iii)参数×(位置-位置)：cE^l＝{e/p^l(e)|e∈E}，$p^l\left(e\right)=\left\{\begin{array}{cc}1,& \mathrm{if\; e}\in E^l\mathrm{and\; c}>1\\ c,& \mathrm{if\; e}\in E^l\mathrm{and}0\le c\le 1\\ 0,& \mathrm{if\; e}\notin E^l\end{array}\right.$(iv)速度+速度：V₁+V₂＝{e/max(p₁(e)，p₂(e))|e∈E}(5)更新粒子的位置，由于在重新定义的离散空间里不能简单由速度加位置来更新粒子的位置，故采用如下4步来更新粒子的位置：(i)速度矢量V_i的每一个维度都用来生成另一个确定的集合${\mathrm{cut}}_{\alpha }\left(V_i^j\right)=\left\{e\right|e/p\left(e\right)\in V_i^j\mathrm{and\; p}\left(e\right)\ge \alpha \};$(ii)第i个粒子开始建立新的位置，由一个空集开始，粒子从里面选择一个可行元素加到新的位置里面；(iii)如果里面没有可行解，并且新位置的构造还没有结束，则从当前的位置里面选择一个可行元素加到新的位置里面；(iv)如果里面没有可行解，并且新位置的构造还没有结束，则从其它的可行解里面选择一个可行元素加到新的位置里面；更新种群位置操作时的第(ii)(iii)(iv)步都有一个选择操作，这里将采用基于启发信息的选择方式，即每次进行选择之前都从{时间优先启发式，费用优先启发式，可靠性优先启发式，性价比启发式，随机启发式}这五类启发信息中随机选择一种启发信息，并按照这种启发信息选出候选元素中具有最优启发信息值的元素添加到新的位置里面；时间优先启发式是指执行时间越短的计算服务越优先被选择；费用优先启发式是指费用越低的计算服务越被优先选择；可靠性优先启发式是指可靠性越高的计算服务越被优先选择；性价比启发式是指时间与费用的乘积值越小的计算服务越被优先选择；随机启发式是指每个候选的元素都被赋以均匀分布于(0，1)区间的随机数，随机数值越大的元素越被优先选择。如果两个或多个元素具有等优的启发式信息值，则算法随机地从中选择一个添加到新的位置里面；(6)如果达到终止条件则停止程序，否则返回步骤(2)。