一种带约束云工作流调度的自适应多目标进化方法

技术领域

本发明涉及解决带约束的多目标优化的问题，并应用于云工作流调度技术领域，特别是指一种带约束云工作流调度的自适应多目标进化方法。

背景技术

云环境下的工作流调度(简称：云工作流调度)是寻找合适的云资源来执行工作流任务，并满足用户的服务质量需求。云工作流调度问题是一个带约束的多目标优化问题，多目标进化算法能有效处理此类问题。但现有技术中，大多是简单地利用静态的惩罚函数来处理约束条件，这样容易导致早熟收敛，甚至进入不可行的搜索空间，例如：

现有技术一，通过利用帕累托(Pareto)熵信息和Pareto差熵信息来评估多目标粒子群算法中种群的多样性以及进化状态，并且以此为反馈信息来设计进化策略，使得算法具有更好的收敛性和多样性。

现有技术二，在NSGA-II算法的基础上进行了改进，通过离散化整个Pareto最优前沿，找到一些良好分布的参考点，在算法的进化过程中以这些点为搜索方向，找到与提供的参考点集相关联的Pareto最优解或Pareto最优解附近的解，使得到的解集具有更优的收敛性和多样性。

现有技术一和现有技术二，虽然可以使算法得到的非支配解集具有更好的收敛性和多样性，但其针对的是无约束的多目标优化问题。对于云环境下的工作流调度问题是一个带约束的多目标优化问题，在处理此类问题时，常用的方法是基于多目标进化算法，使用静态的惩罚函数将带约束优化问题转化为无约束优化问题，惩罚函数如果太小，一些非可行解的适应度值将高于大部分可行解，种群很有可能会朝一个非可行的搜索空间进化；但惩罚函数如果太大，许多更优的个体将会被排除，从而导致早熟收敛，综上，现有的多目标进化算法在使用静态惩罚函数处理约束条件时容易陷入局部最优。

发明内容

本发明要解决的技术问题是提供一种带约束云工作流调度的自适应多目标进化方法，以解决现有技术所存在的多目标进化算法在使用静态惩罚函数处理约束条件时容易陷入局部最优的问题。

为解决上述技术问题，本发明实施例提供一种带约束云工作流调度的自适应多目标进化方法，包括：

S1、根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序，其中，在个体评估策略中，采用约束违反处理方法来处理约束条件；

S2、根据个体排序结果，从种群中选择个体进行遗传操作，得到子种群，其中，在进行遗传操作时，根据种群在进化过程中所处的进化状态自适应地调节进化参数。

进一步地，所述根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态包括：

若种群中没有Pareto解，则种群在进化过程中所处的进化状态为初始状态。

进一步地，所述根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态包括：

若种群中Pareto解的个数小于种群大小，则种群在进化过程中所处的进化状态为收敛状态；或，

若种群中Pareto解的个数等于种群大小，且种群在t+1次迭代中，Pareto解的个数发生了变化，则种群在进化过程中所处的进化状态为收敛状态；或，

若种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，且则种群在进化过程中所处的进化状态为收敛状态；

其中，△Entropy(t+1)表示第t+1次迭代和第t次迭代的差熵，M表示优化目标的个数，△Entropy_max-diver表示最大差熵值。

进一步地，所述根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态包括：

若种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，且则种群在进化过程中所处的进化状态为多样化状态；或，

若种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，Pareto熵也没变化，则种群在进化过程中所处的进化状态为成熟状态；

其中，△Entropy(t+1)表示第t+1次迭代和第t次迭代的差熵，M表示优化目标的个数，△Entropy_max-diver表示最大差熵值。

进一步地，所述△Entropy_max-diver表示为：

其中，Entropy_max表示Pareto解为最佳分布时的Pareto熵，Entropy_min表示Pareto解为最差分布时的Pareto熵，M表示优化目标的个数，K表示每一维优化目标下的网格分区，Cell_k,m(t)表示第t次迭代中的个体数量，是被映射到PCCS中的整数标号，表示第k个Pareto解的第m个格坐标分量，表示第k个Pareto解对应的第m个优化目标的值，l表示Entropy_min情况下只有一个个体的那个格子的坐标。

进一步地，所述根据检测到的种群在进化过程中所处的进化状态，自适应地选择相应的个体评估策略处理约束条件，并对种群中的个人进行排序，包括：

若检测到种群在进化过程中所处的进化状态为初始状态，则根据第一适应度函数评估种群的个体适应度值，其中，所述第一适应度函数表示为：

按照个体适应度值的大小对种群中的个体进行排序；

其中，F^a(x_i)表示个体i的适应度值，x_i代表个体i，a表示F^a(x_i)是加了惩罚函数后的适应度值，是归一化的约束违反。

进一步地，所述根据检测到的种群在进化过程中所处的进化状态，自适应地选择相应的个体评估策略处理约束条件，并对种群中的个人进行排序，包括：

若检测到种群在进化过程中所处的进化状态为收敛状态，则根据第二适应度函数评估种群的个体适应度值，其中，所述第二适应度函数表示为：

按照个体适应度值的大小对种群中的个体进行排序；

其中，表示个体i的第k个目标的适应度值，x_i代表个体i，a表示是加了惩罚函数后的适应度值，表示个体i的第k个目标的归一化后的适应度值，表示归一化的约束违反，r_f表示可行比率。

进一步地，所述根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略，对种群中的个体进行排序包括：

若检测到种群在进化过程中所处的进化状态为多样化状态或成熟状态，则基于约束的支配排序原则对种群中的个体进行排序。

进一步地，所述进化参数包括：交叉概率和变异概率；

所述在进行遗传操作时，根据种群在进化过程中所处的进化状态自适应地调节进化参数包括：

在进行遗传操作时，对遗传操作中的交叉概率和变异概率进行自适应的调整，其中，第t次迭代的交叉概率p_c(t)的调整规则表示为：

第t次迭代的变异概率p_m(t)的调整规则表示为：

其中，<·>表示一个保持p_c(t)和p_m(t)处于给定的边界之中的函数，当p_c(t)和p_m(t)低于下边界，将下边界值赋予给它们，当p_c(t)和p_m(t)高于上边界，将上边界值赋予给它们，p_c(t-1)表示第t-1次迭代的交叉概率，p_m(t-1)表示第t-1次迭代的变异概率，△np(t)表示在第t次迭代中Pareto个体数的变化数，△Entropy(t-1)表示第t-1次迭代和第t-2次迭代的差熵，c_i和m_j表示调整步长，i，j＝1,2,3,4。

本发明的上述技术方案的有益效果如下：

上述方案中，根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序，其中，在个体评估策略中，采用约束违反处理方法来处理约束条件，能有效的处理约束条件；根据个体排序结果，从种群中选择个体进行遗传操作，得到子种群，其中，在进行遗传操作时，根据种群在进化过程中所处的进化状态自适应地调节进化参数，使多目标进化方法具有很好的收敛性和多样性，在解决云工作流调度的优化问题时具有较优的性能，使得在约束条件下也能具有较优的全局探测和局部开采能力。

附图说明

图1为本发明实施例提供的带约束云工作流调度的自适应多目标进化方法的流程示意图；

图2为本发明实施例提供的带约束云工作流调度的自适应多目标进化方法的详细流程示意图；

图3表示Epigenomics工作流在时限1约束条件下总执行成本TEC和不平衡度DI的均衡解；

图4表示Epigenomics工作流在时限2约束条件下总执行成本TEC和不平衡度DI的均衡解；

图5表示Epigenomics工作流在时限3约束条件下总执行成本TEC和不平衡度DI的均衡解；

图6表示Epigenomics工作流在时限4约束条件下总执行成本TEC和不平衡度DI的均衡解；

图7表示Inspiral工作流在时限1约束条件下总执行成本TEC和不平衡度DI的均衡解；

图8表示Inspiral工作流在时限2约束条件下总执行成本TEC和不平衡度DI的均衡解；

图9表示Inspiral工作流在时限3约束条件下总执行成本TEC和不平衡度DI的均衡解；

图10表示Inspiral工作流在时限4约束条件下总执行成本TEC和不平衡度DI的均衡解。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述。

本发明针对现有的多目标进化算法在使用静态惩罚函数处理约束条件时容易陷入局部最优的问题，提供一种带约束云工作流调度的自适应多目标进化方法。

如图1所示，本发明实施例提供的带约束云工作流调度的自适应多目标进化方法，包括：

S1、根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序，其中，在个体评估策略中，采用约束违反处理方法来处理约束条件；

S2、根据个体排序结果，从种群中选择个体进行遗传操作，得到子种群，其中，在进行遗传操作时，根据种群在进化过程中所处的进化状态自适应地调节进化参数。

本发明实施例所述的带约束云工作流调度的自适应多目标进化方法，根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序，其中，在个体评估策略中，采用约束违反处理方法来处理约束条件，能有效的处理约束条件；根据个体排序结果，从种群中选择个体进行遗传操作，得到子种群，其中，在进行遗传操作时，根据种群在进化过程中所处的进化状态自适应地调节进化参数，使多目标进化方法具有很好的收敛性和多样性，在解决云工作流调度的优化问题时具有较优的性能，使得在约束条件下也能具有较优的全局探测和局部开采能力。

本发明实施例提供的带约束云工作流调度的自适应多目标进化方法可以称为基于Pareto熵的带有自适应个体评估策略的NSGA-II算法(Pareto Entropy based on NSGA-II with adaptive individual-assessment scheme，ai-NSGA-II-PE)，ai-NSGA-II-PE以非支配排序的多目标优化算法(Non-dominated Sorting Genetic Algorithm-II，NSGA-II)为基础，如图2所示，本发明实施例提供的带约束云工作流调度的自适应多目标进化方法具体可以包括：

S201，初始化种群，包括迭代次数，种群规模等；

S202，根据Pareto解的个数和Pareto熵检测种群在进化过程中所处的进化状态，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序；其中，所述根据Pareto解的个数和Pareto熵检测种群在NSGA-II进化过程中所处的进化状态包括：

(1)若种群中没有Pareto解，则定义种群在进化过程中所处的进化状态为初始状态；

(2)如下3种情况，定义种群在进化过程中所处的进化状态为收敛状态：

a、种群中Pareto解的个数小于种群大小；

b、种群中Pareto解的个数等于种群大小，但种群在t+1次迭代中，Pareto解的个数发生了变化；

c、种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，且其中，△Entropy(t+1)表示第t+1次迭代和第t次迭代的差熵，M表示优化目标的个数，△Entropy_max-diver表示最大差熵值。

本实施例中，为了更好地理解Pareto熵、差熵、最大差熵值△Entropy_max-diver，对Pareto熵、差熵、最大差熵值△Entropy_max-diver进行详细说明：

本实施例中，可以借助平行格坐标系统(Parallel Cell Coordinate System，PCCS)来描述Pareto熵及其差熵。M为优化目标的个数，每一维优化目标下的网格分区为K，表示第k个Pareto解对应的第m个优化目标的值，按照式(1)映射到一个具有K×M个格子的二维平面网格，是被映射到PCCS中的整数标号，表示第k个Pareto解的第m个格坐标分量。每一个笛卡尔坐标系中的解的坐标分量都可以被映射到二维平面网格中的某一个格子中。

令其中为向上取整函数，即返回一个不小于x的最小整数，和分别是对于当前Pareto解集合中的第m个目标的最大值和最小值，如果将设置为1。

本实施例中，第t次迭代的Pareto熵Entropy(t)可以表示为：

其中，Cell_k,m(t)表示中的个体数量，第t次和t-1次迭代的差熵△Entropy(t)可以表示为：

△Entropy(t)＝Entropy(t)-Entropy(t-1)

最大差熵值△Entropy_max-diver指的是一种极端情况下熵的差值，即在多样化状态时，新解与旧解处于同一支配等级，但具有更好的拥挤度时，旧解会被替换，使和显著变化，导致解从最佳分布(即PCCS中每个目标的坐标向量都占据一个格子)变为最差分布(即PCCS中每个目标的坐标向量有K-1个挤在一个格子里，剩下的占据在另一个)，此时的Pareto熵的变化值(△Entropy_max-diver)可以表示为：

其中，Entropy_max表示Pareto解为最佳分布时的Pareto熵，Entropy_min表示Pareto解为最差分布时的Pareto熵，M表示优化目标的个数，K表示每一维优化目标下的网格分区，Cell_k,m(t)表示第t次迭代中的个体数量，是被映射到PCCS中的整数标号，表示第k个Pareto解的第m个格坐标分量，表示第k个Pareto解对应的第m个优化目标的值，l表示Entropy_min情况下只有一个个体的那个格子的坐标。

(3)若种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，且则定义种群在进化过程中所处的进化状态为多样化状态；

(4)若种群中Pareto解的个数等于种群大小，种群在t+1次迭代中，Pareto解的个数没有发生变化，Pareto熵也没变化，则定义种群在进化过程中所处的进化状态为成熟状态。

本实施例中，接着，根据检测到的种群在进化过程中所处的进化状态，自适应地利用相应的个体评估策略处理约束条件，并对种群中的个体进行排序。在自适应个体评估环节，主要通过两个方面来判断一个个体的好坏，一个是它在目标函数得到的目标值，另一个是在约束条件下得到的约束目标值是否超过所定约束。

本实施例中，在不同的进化状态采用不同的个体评估策略来评估个体，对个体进行排序，在个体评估策略中，采用约束违反处理方法来处理约束条件根据种群在进化过程中所处的不同的进化状态，可以采用不同的约束违反处理方法来有效的处理约束条件，使更优的可行个体保留下来；具体的：

(1)若检测到种群在进化过程中所处的进化状态为初始状态，则根据第一适应度函数评估种群的个体适应度值，其中，所述第一适应度函数表示为：

按照个体适应度值的大小对种群中的个体进行排序；

其中，F^a(x_i)表示个体i的适应度值，x_i代表个体i，a表示F^a(x_i)是加了惩罚函数后的适应度值，是归一化的约束违反，即将约束目标值(约束目标值是在约束条件下得到的)超过所定约束的那部分进行归一化，然后根据归一化的约束违反来给个体排序，使得保留下来拥有小的约束违反的个体。

(2)若检测到种群在进化过程中所处的进化状态为收敛状态，即种群中至少有一个可行解(可行解也可以称为可行个体)之后，则根据第二适应度函数评估种群的个体适应度值，其中，所述第二适应度函数表示为：

按照个体适应度值的大小对种群中的个体进行排序；

其中，表示个体i的第k个目标的适应度值，x_i代表个体i，a表示是加了惩罚函数后的适应度值，表示个体i的第k个目标的归一化后的适应度值，表示归一化的约束违反，r_f表示可行比率，r_f为可行个体数量与种群规模的比值。

(3)若检测到种群在进化过程中所处的进化状态为多样化状态或成熟状态，本实施例采用另一种个体评估策略来排序个体，按照定义1，基于约束的支配排序原则如下，使得种群搜索拥有更好拥挤度的可行个体，并防止非可行解进入种群：

定义1：如果以下任何一个条件为真，则说明个体S₁比个体S₂优秀：

(1)如果S₁是可行解而S₂是非可行解；

(2)S₁、S₂都是非可行解，S₁有更小的约束违反；

(3)S₁、S₂都是可行解，S₁比S₂有更高的非支配等级；或，当S₁和S₂都有相同的支配等级，S₁比S₂有更优秀的拥挤度，通过非支配等级对个体进行排序，其中，非支配等级排序和拥挤度计算与NSGA-II算法中所采用的类似；

非支配等级排序是指：如果某个个体i的一个或者多个优化目标值均优于另外一个个体j，而其他优化目标值相等，那么个体i支配个体j。根据支配关系给个体分配非支配等级，等级高的个体支配等级低的个体，如果个体m不能被任何个体所支配，即所得到的解最优，则称个体m为Pareto最优解或非支配解。

拥挤度，用于对处于相同非支配等级的个体进行排序，其基本思想是根据所有个体的优化目标值来计算与个体相邻的两个个体的欧式空间距离。

S203，根据个体排序结果，从种群中选择个体进行遗传操作，得到子种群。拥有排序更高的个体具有更大的概率被选入子群体中。

本实施例中，是在不同的进化状态采用不同的个体评估策略来选择个体进行遗传操作。

根据种群在进化过程中所处的进化状态进行相应的遗传操作时，种群根据其所处的进化状态自适应地进行进化参数的调整，即对遗传操作中的交叉概率和变异概率进行自适应的调整，从而提高全局探测和局部开采能力。

本实施例中，遗传操作中的交叉概率和变异概率，可以根据种群在进化过程中所处的进化状态、Pareto解的个数以及Pareto熵来自适应调整，其中，第t次迭代的交叉概率p_c(t)的调整规则表示为：

第t次迭代的变异概率p_m(t)的调整规则表示为：

其中，<·>表示一个保持p_c(t)和p_m(t)处于给定的边界之中的函数，当p_c(t)和p_m(t)低于下边界，将下边界值赋予给它们，当p_c(t)和p_m(t)高于上边界，将上边界值赋予给它们，p_c(t-1)表示第t-1次迭代的交叉概率，p_m(t-1)表示第t-1次迭代的变异概率，△np(t)表示在第t次迭代中Pareto个体数的变化数，△Entropy(t-1)表示第t-1次迭代和第t-2次迭代的差熵，c_i和m_j表示调整步长，i，j＝1,2,3,4；其中，c_i和m_j表示为：

其中，g_max表示为最大迭代次数。

S204，根据父种群和子种群在进化过程中所处的进化状态，自适应计算父种群和子种群的个体适应度值，具体步骤同S202。

S205，根据父种群和子种群的个体适应度值，确定父种群和子种群的个体排序。

本实施例中，按照个体适应度值从小到大对父种群和子种群的个体进行排序，其中，排序时，父种群和子种群是放在一起操作的。

S206，从排序后的父种群和子种群中，选择前N个个体作为新种群，计算新种群的Pareto熵和检测种群状态，返回执行S202，新种群参与下一次迭代，直至迭代次数等于预设的最大迭代次数，其中，N的取值根据实际情况确定。

本实施例中，从排序后的父种群和子种群中，选择前N个个体作为新种群。排序时，父种群和子种群是放在一起操作的，选个体也是选两个种群(父种群和子种群)的前N个个体。

在计算敏感的云计算环境下，为解决其工作流调度问题，建立如下模型：

优化目标(Minimize)为最小化总执行成本(Total Execution Cost，TEC)和不平衡度(Degree of Imbalance，DI)，约束条件(Subject to)为总执行时间(Total Execution Time，TET)小于时限d_w，表示为

Minimize:TEC

DI

Subject to:TET≤d_w

其中，|VM|表示虚拟机的个数，表示执行任务i的虚拟机，是虚拟机单位时间成本，是执行任务i的实际运行时间，t_i表示任务i，τ是虚拟机单位处理能力，表示任务i和任务j之间的传输时间，下标e_i,j表示任务i和任务j是相连的，是的数据转换成本，i∈T,j∈T中的T指所有的任务下标，T_max和T_min分别表示所有虚拟机的最大运行时间和最小运行时间，T_avg是虚拟机的平均运行时间，，V是任务集合，表示任务i的结束时间。

本实施例中，执行任务i的实际运行时间表示为：

其中，为任务i的大小，是的处理能力。

本实施例中，任务i和任务j之间的传输时间表示为：

其中，和分别表示虚拟机VM_i和VM_j之间数据传输的带宽，下标e_i,j表示任务i和任务j是相连的，是由任务i产生的输出数据大小，如果任务i和任务j在同一虚拟机执行，则传输时间为0；

本实施例中，任务i的开始时间表示为：

其中，是租用终止时间，指执行任务i的虚拟机，t_a表示任务a，parent(t_i)表示任务i的所有母任务，表示任务a的结束时间，表示任务a和任务i之间的传输时间，下标e_a,i表示任务a和任务i是相连的。

本实施例中，任务i的结束时间表示为：

其中，表示任务i的开始时间，表示执行任务i的实际运行时间。

本实施例中，在进行测试时定义了4个时限值，这些时限值处于最快和最慢运行时间之间，最快运行时间由异构计算环境最早时间完成算法(Heterogeneous Earliest Finish Time，HEFT)调度工作流所获得，最慢运行时间由一个虚拟机执行所有的任务所获得，时限随着编号的增加逐渐变得严格。

本实施例采用了Epigenomics和Inspiral两种工作流进行了测试，其中，Epigenomics工作流是一种高度流水线的应用程序，其中多个线并行地对独立的数据块进行操作；Inspiral由几个子工作流组成。测试结果如图3、图4、图5、图6、图7、图8、图9、图10所示。

实施方式一

本实施例中，分别设置时限值为时限1，时限2，时限3，时限4，选取科学工作流模型Epigenomics，将ai-NSGA-II-PE与基于Pareto熵的NSGA-II算法(ParetoEntropy based on NSGA-II，NSGA-II-PE)(NSGA-II-PE采用本发明所提出的自适应调整进化参数，但使用传统静态惩罚函数处理约束条件)、NSGA-II、基于分解的多目标进化算法(Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D)、强度Pareto进化算法(Strength Pareto Evolutionary Algorithm 2，SPEA2)、多目标粒子群优化算法(Multi-Objective Particle Swarm Optimization，MOPSO)分别进行比较；仿真结果如图3、图4、图5、图6，由图3、图4、图5、图6可见，相比于其他算法，ai-NSGA-II-PE在严格的约束条件下能找到全局探测和局部开采效果更优的Pareto前沿。

实施方式二

本实施例中，分别设置时限值为时限1，时限2，时限3，时限4，选取科学工作流模型Inspiral，将ai-NSGA-II-PE与NSGA-II-PE(采用本发明所提出的自适应调整进化参数，但使用传统静态惩罚函数处理约束条件)、NSGA-II、MOEA/D、SPEA2、MOPSO进化算法分别进行比较；仿真结果如图7、图8、图9、图10，由图7、图8、图9、图10可见，相比于其他算法，ai-NSGA-II-PE在严格的约束条件下能找到全局探测和局部开采效果更优的Pareto前沿。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。