摘要
目前主流优化方法通常将云工作流调度建模为单目标或者不超过三个目标的多目标优化问题，未能充分考虑实际应用场景需求。为克服传统方法局限性，将云工作流调度问题直接建模为涉及时间、费用、可靠性、资源消耗度、负载均衡等众多指标的超多目标优化问题，并针对该问题提出一种改进协同演化算法，利用双阶段策略和多性能指标协同机制有效地平衡解集的收敛性和多样性，提升算法寻优能力。在七类真实工作流实例上的实验表明，所提方法相比现有算法在大多数情况下可找到更好的调度方案。
Abstract
Most current studies formulate the cloud workflow scheduling as a single-objective or multi-objective optimization problem with at most three objectives, which is unable to fully meet practical scenarios′ needs. To address the limitations above, many-objective cloud workflow scheduling model was established, where many indicators such as time, cost, reliability, resource consumption, load balancing, were taken into account. Then, an improved co-evolutionary algorithm was introduced to address this problem, where dual-stage search strategy and multi-indicator cooperation mechanism were employed to effectively balance the convergence and diversity of solution set, so as to enhance the search capability of algorithm. Experiments on seven types of real life workflow instances reveal that our proposal outperforms the existing peers and can find better scheduling schemes in most cases.
随着科学研究和工程实践活动的深入，计算任务的规模和复杂度不断增加，许多实际工程应用涉及大量的计算密集型任务，如天气预报、军事模拟、森林火灾探测等，需要高性能计算系统的支持。传统高性能计算系统配置和管理复杂，维护成本相对高昂，对中小企业和组织并不友好。云计算通过虚拟化技术汇聚海量计算资源，以按需使用的方式为用户提供高性能计算服务，从而提高资源利用率并降低使用成本[1]。工作流模型将大规模计算过程划分为多个相互依赖的计算任务，工作流调度即为这些计算任务分配合适的计算资源，以达到较优的调度效果和目标[2]。如何有效利用云平台提供的计算资源，为工作流任务提供最佳的服务质量，是云计算的核心问题之一。
云平台以虚拟机的形式提供计算资源，但多个服务质量指标之间通常相互冲突，如时间和费用，执行任务耗费时间较短的计算资源通常性能更好，但费用更高，反之，费用相对较低的计算资源执行任务所需时间较长。此外，能耗近来也成为云计算关注的重点[3]，以国家超级计算中心天河二号为例，整机平均功率约为17 808 kW，以1元/（kW·h）单价计算，天河二号平均每年的电费约为1.56亿元[4-5]。随着云服务计算能力的提升，用户越来越关注计算系统的可靠性，但高可靠性往往伴随着更高的成本和更大的资源开销。可靠性是任务成功执行的关键，硬件故障、资源丢失、超时故障和网络故障等均会导致云计算的可靠性下降[6]。计算资源的利用率是影响云计算效率的关键因素，充分利用计算资源空闲时段以降低工作流执行成本并提高计算资源利用率至关重要[7]。在调度工作流任务时考虑负载均衡指标，可提高虚拟机工作负荷相对均衡度，利于系统稳定[8]。任务执行时间和通信开销反映资源消耗度，异构嵌入式系统中工作流的可靠性和资源消耗对提升其稳定性至关重要[9]。目前针对云工作流调度优化目标的研究主要集中在执行时间和费用两个指标，少部分研究涉及能耗和可靠性。然而，其他重要优化目标如资源利用率、负载均衡及资源消耗等很少被考虑。
云工作流调度为NP难问题[10]。目前，大部分研究工作将其建模为带有约束的单目标问题以及多目标问题，仅优化其中的两个或三个目标，采用启发式算法或演化算法等方法进行求解，已经取得了一定的进展。Rodriguez和Buyya[11]提出截止日期约束下成本最小化单目标工作流调度模型，旨在实现给定截止日期约束下以最小成本执行目标任务。针对该模型，多种求解算法相继被提出，如协同进化遗传算法[12]、动态分组学习分布式粒子群算法[13]、蒙特卡罗采样法[14]等。在考虑能耗约束的情况下，Shi等[15]以最小化作业完成时间为优化目标，确定任务放置计划和资源分配计划。Xie等[16]提出在给定响应时间范围内可靠性最大化的优化方法。此外，部分研究针对响应时间和可靠性约束条件下最小化能耗[17]和资源消耗[18]的工作流调度问题进行了研究。以上工作大多是面向单目标工作流调度优化。
部分研究直接采用多目标模型进行优化。Chen等[19]将云工作流调度问题建模为双目标（时间和费用）优化问题，设计了一种基于协同进化多目标多种群框架的多目标蚁群算法；Li等[20]针对该问题模型提出了一种基于评分和动态层次的非支配排序遗传算法。Li等[21]在该问题模型的基础上增加了截止日期约束，并提出了一种基于多群协同进化的混合智能优化算法。Xue等[22]构建了针对云环境下完工时间、成本和负载最优化的云工作流调度模型，采用参考向量引导进化算法获得合适的工作流调度策略。上述多目标云工作流调度模型仅考虑两个或三个目标，忽略了其他重要目标，缺乏对问题的全盘考虑，鲜有涉及四个及以上目标的云工作流调度研究工作，存在一定的局限性。将云工作流调度建模为超多目标优化问题，并提出相应的求解方法，可为云计算平台资源分配提供更丰富的决策信息。
超多目标通常指四个及以上目标，超多目标优化存在维度爆炸、支配阻抗、收敛性与多样性难以合理平衡以及非规则前沿面等难点。其中，维度爆炸容易导致寻优种群陷入局部最优；支配阻抗是指种群中非支配解的比例急剧增加，导致基于非支配排序的选择机制难以区分解的质量；多样性与收敛性难以平衡是指由于目标空间维度增大、搜索难度增加，解集的收敛性和多样性难以平衡；非规则前沿面使权重向量设计困难和种群多样性维持机制失效。在这一具有挑战性的背景下，需要一种更加高效、灵活且具备适应性的算法。
目前，多目标演化算法主要分为基于非支配排序、基于分解以及基于性能指标的方法[23]，这些算法在处理超多目标问题时表现出显著的性能差异。随着非支配解的比例增加，基于非支配排序的选择机制效率急剧降低。基于分解的算法中设置合适的权向量和参考点较为困难，对复杂问题的适应性不佳。基于性能指标的方法利用解的性能指标贡献度来引导搜索，但单一性能指标难以全面刻画解的贡献度。协同演化利用多个互补的搜索机制对问题进行协作优化[24]，被认为是弥补单一性能指标不足的有效手段。目前将协同演化算法应用于云工作流调度，尤其是将其应用于超多目标的云工作流调度问题中的研究比较少见。因此，基于协同演化机制，本文提出一种双阶段改进协同演化算法，旨在解决超多目标云工作流调度问题，该算法首先生成高质量解集，然后通过双档案集和多性能指标协同机制在搜索过程中平衡收敛性和多样性。
1 超多目标云工作流调度问题
将云工作流调度建模为包含7个目标的超多目标问题，具体目标为可靠性、执行时间、能耗、执行成本、资源空闲率、负载均衡度和资源消耗度，问题模型所涉及的符号和变量含义见表1。云工作流采用有向无环图（direct acyclic graph，DAG）表示，其简单示例如图1所示。
表1符号和定义
Tab.1 Symbols and definitions
图1简单云工作流示例
Fig.1Simple cloud workflow example
1）设是虚拟机集合，工作流G=（T，E），其中代表任务集合，Eij∈E代表任务之间的依赖关系，若Eij=1，则Tj的开始时间必须在Ti完成之后。工作流中第i个任务的调度方案可表示为Si=[Ti，x[i]，ST（i），ET（i）]，其中x[i]代表执行任务Ti的虚拟机编号，且每个任务只能分配给一个虚拟机，ST（i）和ET（i）分别表示任务Ti的开始时间和结束时间。此外，虚拟机Vj的租赁开始时间和租赁结束时间分别为LST（j）和LET（j）。任务Ti在虚拟机Vj上的执行时间根据任务大小和虚拟机的计算能力采用式wi，j=DTi/Pj得到。根据任务之间的依赖关系，Ti的开始时间、结束时间以及对应虚拟机的租赁开始时间和租赁结束时间可采用递归的方式得到，具体计算方法如下：
(1)
(2)
(3)
(4)
(5)
其中，Transfer（i）代表任务Ti在分配虚拟机之后传输数据所需时间。如果工作流中有多个输入和输出节点，则在对应位置设虚拟任务节点，初始任务的开始时间ST为0。总执行时间TET和总执行成本TEC的计算如下：
(6)
(7)
2）云工作流调度可靠性定义为虚拟机在给定时间间隔内连续工作不发生故障的概率，即在虚拟机Vj上执行任务Ti的可靠性为R（Ti，Vj）= ，其中λj代表虚拟机Vj的恒定故障率。整个云工作流的可靠性为：
(8)
3）能耗功率模型可表示为Γ=Γs+Γd=Γs+β·fp，其中：Γs代表虚拟机待机静态功耗；Γd代表虚拟机处理任务时动态功耗，Γd取决于虚拟机的电路相关常数β和虚拟机频率f；p是动态幂指数，通常取大于2的固定值。为简化起见，默认所有虚拟机运行时均以最大频率运行，频率f设为固定值1。因此，在虚拟机Vj上执行任务Ti的能耗为：
(9)
式中，Γv代表虚拟机的静态电路系数。整个云工作流的总能耗为：
(10)
4）空闲率反映所分配的虚拟机有效利用的情况，其值越小，代表被租用的虚拟机空置时间越少。与之相对应的是虚拟机利用率，虚拟机空闲率越小，则虚拟机利用率越高。虚拟机Vj的利用率计算方式如下：
(11)
当Vj上没有任何任务时，其利用率为0。虚拟机Vj的空闲率为idle（j）=1-u（j），整个云工作流的空闲率为：
(12)
5）负载均衡度反映虚拟机利用率的均衡程度，具体计算方法为：
(13)
式中，μ代表所有虚拟机利用率的平均值。
6）资源消耗度取决于任务的执行时间和通信时间，用RC表示，设γj表示虚拟机Vj的增长率，对于在虚拟机Vj上执行的任务Ti，其计算代价为γj·wi，j。同时，假定通信成本随着通信开销而增长，并且对于所有处理器来说增长率是恒定的，γ*表示通信成本的增长率，则任务Ti在虚拟机Vj上执行产生的资源消耗度为：
(14)
云工作流的资源消耗度为：
(15)
云工作流调度问题的目标为：
(16)
为便于理解，根据图1所示工作流，生成一个简单实例。设虚拟机数量为4，表2为随机生成的虚拟机各项参数。
表2虚拟机参数
Tab.2 Virtual machine parameters
设任务在虚拟机上的执行时间矩阵w和任务之间的数据传输时间矩阵e为：
给定初始解x=（4，2，4，1，1，2，3，2），待虚拟机分配完成之后，任务执行顺序确定，解x对应的甘特图如图2所示。图中白色方块代表任务在虚拟机上的执行时间，灰色方块代表任务之间的数据传输时间。
图2解x对应的甘特图
Fig.2Gantt chart corresponding to the solution x
任务执行顺序确定后，根据前述公式，可得总执行时间TET=37.57 s，总执行成本TEC=17.85，总可靠性R（G）=99.622 4%，总能耗E（G）=67.7，总空闲率IR（G）=0.297，负载均衡度LB=0.017，资源消耗度RC（G）=41.97。
为对比初始解x得到的结果，随机生成解y=（4，1，4，1，3，1，4，2），其对应的甘特图如图3所示。
图3解y对应的甘特图
Fig.3Gantt chart corresponding to the solution y
可得解y对应的总执行时间TET=29.91 s，总执行成本TEC=20.26，总可靠性R（G）=99.622 9%，总能耗E（G）=63.53，总空闲率IR（G）=0.308，负载均衡度LB=0.018，资源消耗度RC（G）=48.14。对比解x和解y的性能指标，可知解x在总执行时间、可靠性和能耗上差于解y，但其余目标上均优于解y，二者在不同目标上有各自优势。
云工作流调度问题的解空间具有组合爆炸特征，图1工作流包含8个任务和4个虚拟机，其搜索空间规模为48=65 536。随着任务数量和虚拟机数量的增加，搜索空间规模呈指数增长。此外，高维空间中不同目标冲突进一步加剧，对寻优算法提出了更高要求。
2 双阶段改进协同演化算法
由于超多目标优化问题存在维度爆炸和支配阻抗等特征，传统的演化算法在解决此类问题时寻优性能下降，并且高维空间中平衡解集的收敛性和多样性更加困难，为此，提出一种双阶段改进协同演化算法（dual-stage improved co-evolutionary algorithm，DSICEA）：
1）引入双阶段策略使算法分阶段探索解空间。第一阶段通过集成指标选择综合性能较好的个体，作为第二阶段的初始解；第二阶段通过双档案集互补指标协同来引导种群搜索，兼顾收敛性和多样性。
2）在第一阶段搜索进程中，提出一种融合解集收敛性与多样性的集成指标，引导种群进化，以期提高解集质量，缓解支配阻抗问题。
3）对第二阶段中父代个体更新方式进行改进，从双档案集中选择父代个体，以提升生成新解的多样性，避免种群陷入局部最优。
2.1 算法框架
DSICEA流程如图4所示，第一阶段采用集成指标获得综合性能较好的解集，第二阶段采用双指标双档案集引导种群进化，以更好地平衡解集收敛性和多样性。DSICEA伪代码见算法1。首先初始化种群P和第二阶段初始化标志位Initialized（1~2行），算法执行第一阶段搜索的条件为FE＜t×maxFEs，其中FE代表当前迭代的评价次数，参数t控制第一阶段搜索资源投入占比。在第一阶段中（5~7行），首先采用随机配对选择得到父代集合Parent（5行），通过遗传算子产生子代种群Off（6行），之后执行环境选择算子，通过集成指标选择个体得到更新后的种群（7行）。在第二阶段中（9~18行），对Two_Arch2算法[25]进行延伸和拓展，首先对收敛性档案集CA和多样性档案集DA赋值，通过随机配对选择生成父代集合Parent1和Parent2。Parent2在Two_Arch2中仅从档案集CA中选择个体，未考虑档案集DA中的个体，难以充分发挥档案集的作用，DSICEA对此进行改进。通过遗传算子生成子代后根据指标更新档案集CA（15行），根据Lp距离指标更新档案集DA（16行）。迭代进化完成后将多样性表现更好的档案集DA作为最终解集输出。
图4DSICEA流程图
Fig.4DSICEA flow chart
算法1 DSICEA程序
Alg.1 Procedure of DSICEA
2.2 集成指标策略
DSICEA第一阶段搜索过程中，采用集成指标I反映解的综合性能，其由两部分组成，其中第一部分I1（x）为：
(17)
(18)
式中，md为目标空间维度，代表个体x在目标空间中支配个体y所需要的最小距离。具有支配保持的特性，若x支配y，则＜0。指标I1仅和个体目标值相关，无须设置参考点或者相关参数，避免了参数设置对结果的影响。第二部分I2（x）可以反映个体的多样性，具体计算方式如下：
(19)
(20)
(21)
其中：ISDE通过距离反映个体的密度值，较小的距离值对应较大的密度值，在进化过程中更容易被淘汰，可有效维持种群多样性；y precedes x代表个体y在种群P中的下标位置先于个体x[26]，经过验证，使用该设置不仅可减少计算开销，而且会使得DSICEA的寻优效果进一步提升。为平衡解集的收敛性和多样性，集成指标由I1和I2归一化处理后相加：
(22)
I（x）的值越大，对应个体x质量越好。算法2给出了基于集成指标I的环境选择步骤。
算法2 环境选择
Alg.2 Environmental selection
2.3 父代集合更新策略
在Two_Arch2中，档案集CA维持收敛性，档案集DA维持多样性，并且CA在多样性方面远差于DA。Two_Arch2中父代集合Parent2通过随机方式只从CA当中生成，没有考虑DA中的个体。为了充分利用档案集中的信息，DSICEA从CA和DA的合集中选择表现更好的个体组成Parent2，具体操作过程见算法3。
2.4 复杂度分析
DSICEA的时间复杂度与迭代次数K、种群规模N、目标个数m和任务数|T|有关。DSICEA包括两个阶段，第一阶段通过集成指标选择优势个体，该阶段时间复杂度为O（0.3KmN2|T|2）；第二阶段通过双档案集指导种群进化，该阶段时间复杂度为max{O（0.7KNlgm-2N|T|2），O（0.7Km N2|T|2）}。综上，DSICEA的总时间复杂度为O（mKN2|T|2+max{KNlgm-2N|T|2，mKN2|T|2}）。
算法3 配对选择Parent2
Alg.3 Mating selection for Parent2
3 实验结果及分析
本节对DSICEA进行实验验证，首先分析参数t对算法性能的影响，随后通过消融实验检验改进策略的有效性，最后通过与目前主流方法进行对比实验，检验DSICEA的寻优能力。所有算法独立重复运行30次，并采用非参检验测试所得结果的显著性差异。
3.1 实验设置
实验数据集为科学工作流CyberShake、Epigenomics、Inspiral、Montage、SIPHT以及Gaussian工作流和Fast Fourier工作流。每一类工作流均设置其对应的小、中、大不同规模的问题实例。
5 类科学工作流的所有实例数据及任务之间的依赖关系均来自南加州大学开发的一套开源工作流仿真软件的真实数据，Gaussian和Fast Fourier工作流的所有实例数据随机生成。云服务中虚拟机的各项参数参考文献[27-28]，其中虚拟机电路相关常数为0.8≤β≤1.2，虚拟机静态电路系数为0.03≤Γv≤0.07，虚拟机Vj的恒定故障率与虚拟机单位时间租赁价格线性相关，单位时间租赁价格越高的虚拟机代表其故障率越低，范围设为[6×10-5/ms，9×10-5/ms]。结合实际情况将虚拟机增长率设为0.5≤γ≤1.2 kbit/ms，虚拟机通信成本增长率设为γ*=0.5 kbit/ms。表3为不同规模工作流对应的任务数量和虚拟机数量，小规模任务场景下工作流的拓扑结构如图5所示。所有实验中种群规模N设为100，目标函数最大评价次数maxFEs为50 000。采用逆世代距离（inverted generational distance，IGD）对解集进行评价，IGD值越小，代表解集的收敛性和分布性越好。
表3云工作流实例参数配置
Tab.3 Parameter configurations of cloud workflow instances
图5云工作流拓扑结构
Fig.5Cloud workflow topology structures
(23)
其中，PF代表真实Pareto解集，Q代表算法输出的解集，dist（ν，Q）代表PF中的个体ν与Q中的目标向量之间的最小欧氏距离。由于所求问题理论最优前沿解集未知，因此通过多次运行所有参与比较的算法，从获取的解集中筛选出非支配解，以构建参考前沿解集。
3.2 参数分析
DSICEA中的参数t用于控制第一阶段计算资源投入占比，为考察其取值对算法性能的影响，对比参数t的9个不同取值（从0.1至0.9，间隔为0.1），在24个问题实例上分别运行30次。表4给出了单因素方差分析（analysis of variance，ANOVA）的结果，从表中可以得到p值远小于0.05，表明参数t对算法有显著影响。为寻找参数t的最佳取值，观察30次运行得到的IGD指标值具体分布情况。图6给出了IGD指标归一化之后的具体结果，当t=0.3时，IGD值处于最佳状态，并且在该取值情况下，IGD中位数的值明显好于其余情况。
表4单因素方差分析结果
Tab.4 One-way analysis of variance results
图6IGD指标值箱线图
Fig.6Box plot of IGD indicator values
图7给出了参数t不同取值下在24个问题实例上运行30次计算得到IGD值的Friedman排名情况，从图中可以看出，t=0.3时排名第一。与图6对应，以t=0.3为分界点，增大或减小t值，算法性能均有所降低。t值过小，算法第一阶段中生成解集的质量欠佳，进而影响后续的进化过程；t值过大，算法第一阶段消耗计算资源过多，导致第二阶段没有足够的计算资源对解集进行优化，使最终结果变差，当t取0.3时平衡效果较佳。
图7在不同t取值下所得DSICEA的 Friedman排名
Fig.7Friedman ranking of DSICEA for different values of t
3.3 消融分析
为考察所提策略对算法性能的影响，设计了四种变体，记作DSICEA-Ⅰ、DSICEA-Ⅱ、DSICEA-Ⅲ、DSICEA-Ⅳ。DSICEA-Ⅰ中，I被替换为；DSICEA-Ⅱ中I被替换为ISDE；DSICEA-Ⅲ中，将第一阶段删除；DSICEA-Ⅳ中，将第二阶段Parent2的更新方式用随机生成的方式替换。
表5给出了DSICEA与其他四种变体在24个问题实例上运行30次得到的IGD平均值、标准差及统计分析结果。Friedman代表算法在所有实例上排名的平均值，括号中的数值代表算法的最终排名；Best代表算法排名第一的问题数量和问题总数；表格最后给出了Wilcoxon秩和检验结果，其中+/=/-分别代表DSICEA显著优于、相似于、劣于该算法的问题实例数量。表格中灰色背景数值为该问题上的IGD最优值，符号●/§/○代表DSICEA优于、相似于、劣于该算法。从表中数据可以观察到DSICEA在11个实例上表现效果最优，而剩下四种变体分别只在3、3、1、6个实例上表现最好，并且DSICEA只在3个实例上略差于DSICEA-Ⅱ，在1个实例上略差于DSICEA-Ⅳ，在剩余实例上DSICEA优于或相似于其他变体，且DSICEA的Friedman排名第一，证明改进策略有效。
表5DSICEA与变体在所有问题实例上的IGD指标均值及标准差
Tab.5 Mean and standard deviation of IGD metric for DSICEA and variants over all instances
实验结果表明，第一阶段生成的高质量解集对第二阶段双档案集协同搜索具有积极作用，使得最终解集质量更好。仅使用有偏好的单一性能指标或ISDE无法兼顾收敛性和多样性，难以产生综合性能较好的解集。相较于仅从CA中选择配对个体，从CA与DA的合集中选择配对个体可提升配对个体的多样性，一定程度上避免陷入局部最优，进而提高算法寻优能力。
3.4 对比实验
为验证DSICEA的寻优能力，将其与目前主流方法AGE-MOEA[29]、BCE-IBEA[30]、BCE-MOEA/D[30]、NSGA-Ⅲ[31]、SPEA2[32]、Two_Arch2和MSPSO[33]进行对比。表6给出了8种算法在24个实例上运行30次得到的IGD平均值、标准差及统计分析结果。DSICEA的Friedman排名为1.166 7，在8种算法当中排名第一。DSICEA在20个问题实例上表现最优，且分别在19、21、17、24、21、19、16个实例上显著优于其余算法，仅在CyberShake规模为100和SIPHT规模为58时表现欠佳。
Friedman检验结果为：Friedman值为109.458 3，大于临界值χ2=14.07，因此在显著性水平α=0.05的情况下，8种算法在24个实例上运行30次得到的平均IGD值存在显著差异。结合Bonferroni-Dunntest计算得到临界差CD=2.143 2，算法Friedman排名差值大于该值即存在显著差异。8种算法的平均排名如图8所示，阈值Threshold=3.309 9小于所有对比算法的排名，且DSICEA的平均排名与对比算法有明显差距，充分证明了DSICEA远远优于其余7种算法。
表6对比算法在全部实例上的IGD指标均值及标准差
Tab.6 Mean and standard deviation of IGD metric of compared algorithms over all instances
图8对比算法的Friedman排名
Fig.8Friedman ranking of compared algorithms
图9和图10给出了8种算法在大规模Gaussian工作流和Montage科学工作流上IGD度量值中位数对应的归一化解集的对比情况，子图中每条不同颜色的折线代表一个可行解。AGE-MOEA和NSGA-Ⅲ解集收敛性较好，但在多样性方面表现较差；BCE-IBEA、BCE-MOEA/D和Two_Arch2在收敛性方面表现较差；BCE-MOEA/D和SPEA2在多样性方面表现较优，但解集整体质量效果欠佳。MSPSO易陷入局部最优且易出现只关注某一目标而忽略其余目标的情况。结果表明7种对比算法无法同时兼顾收敛性和多样性，而DSICEA拥有良好的收敛性和多样性，且得到的解集质量更优。
造成上述结果的可能原因如下：
1）AGE-MOEA对前沿解集的几何形状进行预估，通过多样性和收敛度指标来选择优势个体，然而该策略难以应对高维多目标前沿面，易陷入局部最优。DSICEA在进化过程中不依赖前沿面的形状，通过集成指标和双档案集协同引导种群搜索，有效提升算法的鲁棒性。
2）BCE-IBEA和BCE-MOEA/D中支配准则和SPEA2的支配强度准则无法解决超多目标问题中的支配阻抗问题，收敛压力不足，致使最终解集质量变差。DSICEA使用多阶段策略及集成指标和多指标协同机制引导种群进化，有效缓解了支配阻抗问题，进而提升算法寻优能力。
3）在高维目标空间中，BCE-MOEA/D算法和NSGA-Ⅲ算法面临维度爆炸和种群数量限制的挑战，导致其基于分解的策略和基于参考点的策略无法发挥作用。具体而言，预设的权重向量和参考点可能难以适应实际问题，导致寻优种群无法充分探索目标空间，容易陷入局部最优，影响解集的质量。同时，种群数量的限制也是一个制约因素，限制了算法在高维目标空间中的搜索能力，无法寻找到高质量解集。DSICEA不受预设参考向量或参考点限制，对非规则前沿面适应性较好。
4）MSPSO通过适应度函数将多目标问题转化为单目标问题，在迭代过程中易出现仅优化其中某一目标而忽略了其余目标的情况，且MSPSO虽然使用不同种类的粒子组成的多个子群来提高算法的探索能力，但在高维空间易陷入局部最优，难以充分探索目标空间。DSICEA使用集成指标在第一阶段选择优秀个体，在第二阶段通过双档案集指导种群进化可以有效避免种群陷入局部最优，并提升解集质量。
图9对比算法在7目标大规模Gaussian工作流上所得解集的目标值的平行坐标
Fig.9The final solution sets of compared algorithms on the 7-objective large-scale Gaussian workflow, shown by parallel coordinates
图10对比算法在7目标大规模Montage科学工作流上所得解集的目标值的平行坐标
Fig.10The final solution sets of compared algorithms on the 7-objective large-scale Montage workflow, shown by parallel coordinates
5）Two_Arch2通过多样性档案集和收敛性档案集协同指导种群的进化，但是随机初始化档案集质量难以保证，导致双档案集协同搜索效果欠佳。DSICEA通过第一阶段生成高质量解集作为第二阶段的初始解，可以有效发挥双档案集的指导作用，加快种群进化速度，进而提升算法性能。
3.5 运行时间
所有实验在一台Core i5 2.3 GHz、16 GB RAM、Windows 10的笔记本电脑上使用PlatEMO平台[34]运行，表7记录了8种算法在24个问题实例上运行30次的平均运行时间。DSICEA使用多性能指标协同机制平衡解集的收敛性和多样性，增加了一部分额外的计算开销，因此在运行时间方面DSICEA无法取得较大的优势。但随着问题规模的增加，DSICEA与对比算法之间的差距逐渐缩小，证明DSICEA有着良好的可扩展性和适应性。MSPSO算法通过适应度函数对比个体好坏，因此运行时间最短，但其对问题的优化效果最差。Two_Arch2算法因维护双档案集造成了较大的运行时间开销。BCE-MOEA/D算法的分解策略和支配准则无法缓解维度爆炸和支配阻抗等问题，导致了运行时间增加。虽然DSICEA在运行时间方面无法超越所有对比算法，但DSICEA中的双阶段策略和多性能指标协同机制可以有效平衡解集的收敛性与多样性，充分探索目标空间，提升解集质量，其效果显著优于对比算法。
4 结论
研究将云工作流调度建模为超多目标优化问题，提出改进协同演化算法，通过双阶段策略使算法分阶段探索解空间，有效平衡收敛性和多样性，避免陷入局部最优。第一阶段中使用集成性能指标引导种群搜索，缓解支配阻抗，通过改进第二阶段中父代更新方式以提升算法的寻优能力。在7类工作流实例上的测试结果表明，DSICEA在收敛性、多样性和解集质量等方面均有更好的表现，算法的寻优能力远优于目前主流演化算法。
今后可尝试将不同特征的指标结合运用在算法的第一阶段生成更高质量的解集，还可考虑将不同的算法融入第二阶段当中引导算法在保持多样性的同时快速收敛，对于第一阶段搜索资源投入占比的控制参数t的自适应研究同样也是一个具有前景的方向。
表7对比算法在全部实例上的平均运行时间
Tab.7 Average runtime of compared algorithms on all instances
