1.一种云计算环境下基于多种群遗传算法的工作流执行优化方法，其特征在于：包括以下步骤：步骤1：获取云工作流执行优化所需的信息；

获取任务集T＝{t1,…,tI}，ti表示任务i，即编号为i的任务；其中I是需要调度的任务数量；

获取任务间的时序关系：任务i的父任务集合PRi，任务i的子任务集合SCi，其中i＝

1,…,I；

获取任务相关参数：任务i的长度leni、leni＞0，即任务i被虚拟机处理时需要耗费的指令数量，处理任务i时需要的输入文件列表IFLi、 任务i被处理后产生的输出文件列表OFLi、 及文件列表中文件file的大小file.size，其中：i＝1,…,I；任务i是+任务i的父任务的充要条件为：存在一个文件file，file是任务i的输出文件同时又是任务+i的输入文件，即： file∈OFLi∧file∈IFLi+；

获取云计算环境下的虚拟机类型集合VM＝{vm1,vm2,…,vmJ}，其中J是虚拟机的类型数量，vmj表示j类虚拟机；

获取虚拟机相关参数：j类虚拟机的计算能力psj，j类虚拟机的带宽bwj，j类虚拟机的单位时间成本vcj，j类虚拟机的固定起租成本fcj，j类虚拟机的最小计费时间单位utj，j类虚拟机的最小起租时间ftj；租用j类虚拟机的成本计算如下：其中：lt为租用时间，j＝1,2…,J；

获取云计算环境下工作流执行的成本约束Budget与时间约束Deadline；若没有成本约束则设置Budget＝MBV，若没有时间约束则设置Deadline＝MDV；其中：MBV为成本上限，MDV为时间上限；

步骤2：计算任务的层次值；

对于没有父任务的开始任务i，其层次值为：

lvli＝1 (1)

基于上述公式，其它任务的层次值采用如下递归公式进行计算：步骤3：初始化当代种群；

当代种群中包含S个子种群，每个子种群又包含N个个体，N为偶数且N>S，其初始化过程如下：对每个当代子种群采用基于层次和效益比的个体随机生成方法生成N个不同的个体；

所述个体编码方法如下：ch＝{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}，其中{gr1,…,grI}是任务调度顺序列表，为任务编号的一个拓扑排序；{gs1,…,gsI}是虚拟机实例列表，即虚拟机分配列表，gsi表示给任务i分配的虚拟机实例编号，gs1,…,gsI的取值为1到I之间的整数值；{gt1,…,gtI}是虚拟机类型列表，gti表示编号为i的虚拟机实例的类型，gt1,…,gtI的取值为1到J之间的整数值；

所述基于层次和效益比的个体随机生成方法包括如下步骤：步骤A1：根据任务层次值从小到大随机排列任务，即层次值小的排在大的前面，具有相同层次值的则随机排列，形成个体的任务调度顺序列表{gr1,…,grI}；

步骤A2：随机生成I个1到J之间的整数：π1,…,πI；令gti＝πi，i＝1,…,I，生成虚拟机类型列表{gt1,…,gtI}；

步骤A3：基于效益比生成个体的虚拟机分配列表{gs1,…,gsI}；获得所有任务的开始时间si和结束时间fi，i＝1,…,I；

步骤A3.1：令已分配任务的虚拟机实例集 所有虚拟机实例的可得时间段列表vatl1＝…＝vatlI＝{[0,∞]}；令所有任务的就绪时间rt1＝…＝rtI＝0；令变量δ＝1；

步骤A3.2：令变量i＝grδ，变量k＝1；计算把ti分别分配给每个潜在虚拟机实例后的综合效益比：步骤A3.2.1：计算ti分配给编号为k＝gsi的虚拟机实例后的执行时间其中： 是把ti分配给编号为k的虚拟机实例处理时任务的处理时间， 是编号为k的虚拟机实例的处理能力； 是把ti分配给编号为k的虚拟机实例处理时需要从其它的虚拟机获得输入文件的文件传输时间，‑

k 是处理 的虚拟机实例编号， 和

‑

是编号为k和k 的虚拟机实例的带宽； 是把ti分配给编号为k的虚拟机实例处理时需要从共享数据库获得输入文件的文件传输时间，步骤A3.2.2：在vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti,k和υk‑eti,k≥rti；

步骤A3.2.3：计算ti分配给编号为k的虚拟机实例后的开始时间si,k＝max{νk,rti}，完成时间fi,k＝si,k+eti,k；

步骤A3.2.4：计算综合效益比ξi,k：

如果insk∈INS，其中insk表示编号为k的虚拟机实例，则其中：θ∈[0,1]是权重系数，μ＞0是成本与时间的协调系数；

为已有任务分配给insk的情况下

把ti分配给insk后insk的租用时间，lt′k＝Rnt′k‑Hrt′k为ti还没有分配给insk前insk的租用时间， 为ti还没有分配给insk前insk的归还时间； 为ti还没有分配给insk前insk的开始租用时间；

如果 则

其中

为还没有任务分配给insk的情况下把ti分配给insk后insk的租用时间；

步骤A3.2.5：令k＝k+1，如果k≤I，转到步骤A3.2.1；否则转到步骤A3.3；

步骤A3.3：按顺序从ξi,1,…,ξi,I中找出一个最小的，不妨设为 如果编号为 的虚拟机实例 则步骤A3.4：把任务i分配给编号为 的虚拟机实例，令步骤A3.4.1：计算任务的开始时间 结束时间步骤A3.4.2：更新任务i的子任务的就绪时间步骤A3.4.3：在 中从早到晚找出一个空闲时段 满足 和步骤A3.4.4：在vatlk中删除 插入区间长度大于0的 和步骤A3.5：令δ＝δ+1；如果δ≤I，那么转到步骤A3.2，否则转到步骤A3.6；

步骤A3.6：获得虚拟机分配列表{gs1,…,gsI}；

步骤A4：输出一个个体{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}，操作结束；

步骤4：对当代种群中的所有个体采用FBI&D进行解码与改进，获得所有个体的工作流响应时间和执行成本，然后计算所有不可行个体的相对适应度值和可行个体的绝对适应度值；

对于每个当代子种群中的每个个体chn，所述FBI&D包括如下步骤：步骤B1：令工作流反向响应时间rsn＝∞；

步骤B2：采用基于插入模式的串行个体解码方法对个体chn进行解码，获得所有任务的完成时间f1,…,fI及其工作流响应时间rsn；如果rsn小于rsn，则转到步骤B3，否则，转到步骤B6；

步骤B3：把个体chn中的任务调度顺序列表根据任务完成时间fi从大到小重新排列，即把chn中的基因gri设置为倒数第i个完成的任务，i＝1,…,I，形成反向个体chn；

步骤B4：采用基于插入模式的串行反向个体解码方法对反向个体chn进行解码，获得所有任务反向完成时间f1,…,fI及其工作流反向响应时间rsn；若rsn小于rsn，则转到步骤B5，否则，转到步骤B6；

步骤B5：把反向个体chn中的任务调度顺序列表根据任务反向完成时间fi从大到小重新排列，即把chn中的基因gri设置为倒数第i个完成的任务，i＝1,…,I，形成个体chn，转到步骤B2；

步骤B6：输出个体chn及其工作流响应时间rsn，并计算其工作流执行成本ctn，操作结束；

所述基于插入模式的串行个体解码方法对个体chn进行解码包括如下步骤：步骤C1：令所有任务的就绪时间rt1＝rt2＝…＝rtI＝0；令变量δ＝1；令所有虚拟机实例的可得时间段列表vatlk＝{[0,∞]}，k∈{gs1,…,gsI}；

步骤C2：选取编号为i＝grδ的任务；

步骤C3：基于插入模式把任务i分配给编号为k＝gsi的虚拟机实例；

步骤C3.1：计算任务i的执行时间

步骤C3.2：在vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti和υk‑eti≥rti；

步骤C3.3：计算任务i的开始时间si＝max{νk,rti}，完成时间fi＝si+eti；

步骤C3.4：更新任务i的子任务的就绪时间

步骤C3.5：在虚拟机可得时间段列表vatlk中删除[νk,υk]，插入区间长度大于0的[νk,si]和[fi,υk]；

步骤C4：令δ＝δ+1，如果δ≤I，则转到步骤C2，否则步骤C5；

步骤C5：获得任务的开始时间和结束时间：si、fi，i＝1,…,I，计算工作流响应时间rsn，操作结束；

所述基于插入模式的串行反向个体解码方法对反向个体chn进行解码包括如下步骤：步骤D1：令所有任务的反向就绪时间 其中，SFLi是任务i输出给共享数据库的输出文件集合，即 令变量δ＝1；令虚拟机可得时间段列表vatlk＝{[0,∞]}，k∈{gs1,…,gsI}；

步骤D2：选取编号为i＝grδ的任务；

步骤D3：基于插入模式把任务i分配给编号为k＝gsi的虚拟机实例：步骤D3.1：计算任务i的执行时间

步骤D3.2：在vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti和υk‑eti≥rti；

步骤D3.3：计算任务i的反向开始时间si＝max{νk,rti}，反向完成时间fi＝si+eti；

步骤D3.4：更新任务i的父任务的反向就绪时间步骤D3.5：在虚拟机可得时间段列表vatlk中删除[νk,υk]，插入区间长度大于0的[νk,si]和[fi,υk]；

步骤D4：令δ＝δ+1，如果δ≤I，则转到步骤D2，否则步骤D5；

步骤D5：获得任务的反向开始时间si和反向完成时间fi，i＝1,…,I，及工作流反向响应时间rsn＝max{f1,…,fI}，操作结束；

步骤5：判断是否满足终止条件，如满足，则进化结束转到步骤9，否则转到步骤6；

所述终止条件为迭代到指定的代数TG或连续迭代GG代都没有出现可行个体或最优可行个体没有改进；

步骤6：判断是否满足进行子种群间交流的条件；如果满足则转到步骤7，否则转到步骤

8；

所述进行子种群间交流的条件为每迭代EFG代或自上次交流后连续迭代EVG代最优个体没有改进；

步骤7：进行子种群间的交流；

步骤7.1：令精英个体集 从每个当代子种群s即CPs中从优到劣选出当前TPS中尚不存在的1个个体，不妨设其为 把 放到TPS中；

步骤7.2：对每个CPs，s＝1,…,S，从TPS中找出CPs中不存在的精英个体集合CTPSs，用CTPSs中的个体替换CPs中从优到劣排名倒数的|CTPSs|个个体，形成新的CPs；

步骤8：子种群进行独立进化；

步骤8.1：对每个当代子种群进行交叉操作形成新子种群；

步骤8.2：对每个新子种群进行变异操作；

步骤8.3：对每个新子种群中的所有个体采用FBI&D进行解码与改进，获得所有个体的工作流响应时间和执行成本，然后计算所有不可行个体的相对适应度值和可行个体的绝对适应度值；

步骤8.4：对于每个子种群，从优到劣从当代子种群和新子种群中选出N个不同的个体形成新的当代子种群，转到步骤5；

对每个当代子种群，所述交叉操作包括如下步骤：步骤E1：令n＝1，新子种群为空；

步骤E2：采用基于排序的轮赌法从当代子种群中随机选择两个不同个体作为父体1和父体2，不妨设为不妨设通过交叉生成的子体1和子体2为：

步骤E3：随机产生一个1到I‑1的正整数α；随机产生一个小数λ∈[0,1)，如果λ＜0.5则转到步骤E4，否则转到步骤E5；

步骤E4：基于拓扑排序的任务调度顺序列表交叉操作：c1

步骤E4.1：ch 的任务调度顺序列表的前α个基因、虚拟机分配列表、虚拟机类型列表来自于父体1，即：c1

ch 的任务调度顺序列表的后I‑α个基因来自于父体2的任务调度顺序列表 中删除父体1的任务调度顺序列表的前α个基因 后的基因列表；

c2

步骤E4.2：ch 的任务调度顺序列表的前α个基因、虚拟机分配列表、虚拟机类型列表来自于父体2，即：c2

ch 的任务调度顺序列表的后I‑α个基因来自于父体1的任务调度顺序列表 中删除父体2的任务调度顺序列表的前α个基因后的基因列表；转到步骤E6；

步骤E5：进行虚拟机实例和类型的一体化交叉操作；

c1

步骤E5.1：子体ch 的任务调度顺序列表，虚拟机分配列表的后I‑α基因，虚拟机类型列p1表来自于ch ，即：

c1 p2

子体ch 的虚拟机分配列表的前α基因来自于ch ，即：c2

步骤E5.2：子体ch 的任务调度顺序列表，虚拟机分配列表的后I‑α基因，虚拟机类型列p2表来自于ch ，即：

c2 p1

子体ch 的虚拟机分配列表的前α基因来自于ch ，即：步骤E5.3：令虚拟机实例编号集 对于所有的k∈SI1，在 和 中随机选择一个，不妨设为ε′k，令步骤E5.4：令虚拟机实例编号集 对于所有的k∈SI2，在 和 中随机选择一个，不妨设为ε″k，令c1 c2

步骤E6：获得子体ch 和ch ，并把它们放到新子种群中；n＝n+1，如果n≤N/2，那么转到步骤E2；否则新子种群生成完毕，输出新子种群，子种群交叉操作结束；

对每个新子种群，所述变异操作包括如下步骤：

步骤F1：令变量n＝1；

步骤F2：对新子种群中的第n个个体，生成一个随机数λ1∈[0,1)，如果λ1＜pm1，则转到步骤F3，否则转到步骤F4；

步骤F3：进行任务调度顺序列表变异，即：从任务调度顺序列表中随机选择一个基因，不妨设为gri；如果任务gri存在父任务，则向前找到第一个父任务gri′，令位置值pos1＝i′+

1，否则令pos1＝1；如果任务gri存在子任务，则向后找到第一个子任务gri″，令位置值pos2＝i″‑1，否则令pos2＝I；在[pos1,pos2]之间重新随机选择一个位置插入gri；

步骤F4：生成一个随机数λ2∈[0,1)，如果λ2＜pm2，则转到步骤F5，否则转到步骤F6；

步骤F5：进行虚拟机分配列表变异，即：从虚拟机分配列表中随机选择一个基因，不妨设为gsi，在1到I之间重新随机选择一个值，不妨设为k，令gsi＝k；

步骤F6：生成一个随机数λ3∈[0,1)，如果λ3＜pm3，则转到步骤F7，否则转到步骤F8；

步骤F7：进行虚拟机类型列表变异，即：从虚拟机类型列表的有效范围内随机选择一个基因，不妨设为gti，i∈{gs1,…,gsI}；为编号为i的实例重新随机选择一个虚拟机类型，不妨设为j，则gti＝j，转到步骤F8；

步骤F8：令n＝n+1，如果n≤N，转到步骤F2；否则，新子种群变异操作结束；

其中，pm1,pm2,pm3∈[0,1)分别是任务调度顺序列表、虚拟机分配列表和虚拟机类型列表的变异率；

步骤9：如果当代种群中存在可行个体，那么输出当代种群中绝对适应度值最小的个体，其对应的执行方案为优化方案，否则无可行执行方案。

2.根据权利要求1所述的一种云计算环境下基于多种群遗传算法的工作流执行优化方法，其特征在于：所述MBV和MDV的一种具体计算方法如下：其中： 为ti的最大执行时间。

3.根据权利要求1所述的一种云计算环境下基于多种群遗传算法的工作流执行优化方法，其特征在于：对于每个子种群中的每个个体chn，所述工作流响应时间rsn和执行成本ctn的具体计算方法如下：其中：rfi是任务i的响应时间，

其中： 是编号为k的虚拟机实例的固定起租成本， 是编号为k的虚拟机实例的单位时间成本， 是编号为k的虚拟机实例的最小计费时间单位， 是编号为k的虚拟机实例的最小起租时间， 是编号为k的虚拟机实例的带宽，ltk＝Rntk‑Hrtk是编号为k的虚拟机实例的租用时间，Hrtk为编号为k的虚拟机实例的开始租用时间；Rntk为编号为k的虚拟机实例的归还时间； tfi是完成OFLi中的文件输出给相应接收者的最大时刻，如果ti没有文件输出给共享数据库即 那么相应接收者为处理ti的子任务的虚拟机，如果ti没有子任务即 那么相应接收者为共享数据库，另外如果ti即有文件输出给共享数据库又有子任务即 那么相应接收者为处理ti的子任务的虚拟机和共享数据库，

4.根据权利要求1所述的一种云计算环境下基于多种群遗传算法的工作流执行优化方法，其特征在于：对于每个子种群中的每个个体chn，n＝1,2…,N，如果ctn≤Budget∧rsn≤Deadline，则chn为可行个体，否则chn为不可行个体；

不可行个体的相对适应度值的具体计算方法如下：可行个体的绝对适应度值的具体计算方法如下：afitn＝θ×μ×ctn+(1‑θ)×rsn；

其中：θ∈[0,1]是权重系数，μ＞0是成本与时间的协调系数；

进行个体优劣比较时，可行个体优于不可行个体；对于都是可行个体，则绝对适应度值越小，个体越优；对于都是不可行个体，则相对适应度值越小，个体越优。

5.根据权利要求1所述的一种云计算环境下基于多种群遗传算法的工作流执行优化方法，其特征在于：所述步骤E2中基于排序的轮赌法从当代子种群中随机选择两个不同个体作为父体1和父体2的具体步骤如下：步骤E2.1：对当子代种群中的个体从优到劣进行排序，获得个体n的排序值rkn，n＝

1,…,N，其中最优的其取1，次优的其取2，以此类推，最劣的其取N；

步骤E2.2：计算个体n被选中的概率 R＞1为区分度系数；

步骤E2.3：计算累计概率A0＝0，

步骤E2.4：产生一个随机数λ1∈[0,1)，如果An‑1≤λ1＜An，那么选择个体n作为父体1；

步骤E2.5：产生一个随机数λ2∈[0,1)，如果An′‑1≤λ2＜An′并且n′≠n，那么选择个体n′作为父体2，转到步骤E2.6，否则转到步骤E2.5；

步骤E2.6：个体选择操作结束。