基于改进双归档进化算法的多目标动态软件项目调度

陈志远，伍章俊+，童珊珊，刘 晓

(1.合肥工业大学 管理学院，安徽 合肥 230009；2.合肥工业大学 过程优化与智能决策教育部重点实验室，安徽 合肥 230009；3.迪肯大学 信息技术学院，澳大利亚 吉朗 VIC 3126)

0 引言

随着互联网应用和软件产业的快速发展，软件公司面临竞争激烈的市场环境。软件项目过程管理从软件项目计划、需求、设计、编码、测试和运行维护的整个生命周期出发，以提高业务过程的绩效为主要目标持续改进过程，最终实现降低项目成本和缩短项目工期等目标。其中，合理的资源调度能够保证项目生产经营活动顺畅运行，取得最佳的经济效益，是软件项目过程管理的关键步骤。为了赢得市场并满足预算、截止日期等要求，需要采用高效的软件项目调度方案[1-2]。软件项目调度(Software Project Scheduling Problem，SPSP)是一种将具有特定技能的员工有效地分配到需要完成的任务的资源约束调度问题[3-4]。其中，每个任务都有相应的任务工作量和完成任务所需的技能，并且必须根据任务优先级图确定的任务间优先级关系执行。员工有薪水、个人技能和最大贡献度值等属性，并且能够同时参与多项任务。SPSP确定每项任务分配给哪些员工和何时执行，其目的是在满足任务技能的限制和不过度工作等约束条件的前提下，实现缩短项目工期和减少项目成本等目标[5-6]。

在软件项目调度的研究中，通常假设每个任务所需的工作量是已知、固定的，同时在项目生命周期中没有干扰任务执行的动态事件。但在现实软件项目实施的过程中，工作环境会因为新任务的突然加入和某个员工的离开等不可预测事件的发生而动态变化。此外，软件项目活动通常会有相当大的不确定性，如，客户需求的变化、任务工作量估计方法的固有误差所带来的任务工作量估计的不准确、项目开始时未考虑的可预测及不可预测风险、事先无法预见的技术困难和人员流动[7-8]。若将SPSP作为静态问题处理而没有考虑问题中包含的动态性，容易导致获得的最优解存在巨大偏差。针对软件项目的不确定性和不可预测动态事件的发生，本文构建了多目标动态软件项目调度问题模型(Multi-Objective Dynamic Software Project Scheduling Problem, MODSPSP)并采用主动重调度的方法来处理该问题。其中，针对任务工作量估计的不确定性引入鲁棒性目标；为了减少动态事件发生对项目效率的影响，引入稳定性目标，故本文同时考虑持续时间、成本、调度的鲁棒性和稳定性4个目标。

1 相关工作

随着基于搜索的软件工程的发展[9]，学者们将SPSP作为一个基于搜索的优化问题。文献[4]构建了基于任务的问题模型，并采用遗传算法求解最优调度；文献[5]采用了相同的问题模型，并对影响遗传算法求解的重要问题特征进行了系统的经验研究；文献[6]通过运行时理论证明分析了进化算法的设计选择是如何影响求解性能的；文献[10]将任务持续时间划分成离散时间单位，通过迭代的方式将员工分配到离散时间单位的任务中，从而可以考虑更多的如员工的离开、学习和培训等人为因素，但频繁的调度会导致系统的不稳定性；文献[11]构建了基于事件的模型，并采用蚁群算法求解最优调度。上述文献均将软件项目调度问题考虑为静态问题。

到目前为止，研究涉及不确定项目环境下的动态软件项目调度的文献比较有限。文献[12]采用主动调度的方法解决软件项目调度中的不确定性；文献[13]通过动态资源重调度来处理软件项目中的动态事件；文献[14]引入软件项目中的不确定性和动态事件，构建了多目标动态软件项目调度问题的数学模型MODSPSP，采用基于ε-占优的主动重调度方法来求解该问题，利用档案存储非支配解使得算法的多样性得到提升；文献[15]针对MODSPSP提出一种基于Q-learning的主动重调度方法，并运用Q-learning结合双档案平衡算法的收敛性和多样性，使得算法性能得到提升，但也导致过多的计算量；双归档进化算法[16]通过收敛性档案(Convergence Archives，CA)和多样性档案(Diversity Archives，DA)来平衡算法的收敛性和多样性，以较低的复杂度获得了不错的算法性能，但在处理较多目标数的优化问题时，双归档算法容易陷入局部优化，据此文献[17]提出更适于较多目标优化问题的改进双档案进化算法Two-Arch2，但由于在档案维护方案中缺乏对边界解的保护，在处理MODSPSP时，存在获得的非支配解扩展性差和命中率低的问题。

针对上述问题，本文提出一种改进的双档案进化算法(Improved Two-Archive evolutionary Algorithm, ITAA)以主动重调度的方法来处理MODSPSP。在算法搜索过程中，首先，采用佳点集和启发式策略进行种群初始化；其次，利用评价函数自适应地对两种交叉和变异方法进行概率选择；最后，对收敛性档案和多样性档案分别采用质量指标和动态拥挤度距离进行更新。综上所述，ITAA以较低的算法复杂度，很好地平衡了算法的收敛性和多样性，并在处理MODSPSP时，可以获得质量更高的Pareto解集。

2 问题模型

针对软件项目调度问题的动态性，本文设计了一个动态多目标软件项目调度模型，具体描述如下：

2.1 员工属性

假设项目有M个员工参与，项目完成需要S个技能数。记tl(l=1,2,3,…)为重调度点，其中重调度点包括初始点t0。每名员工ei具有属性的描述如下：

2.2 任务属性

假设在项目初始阶段有N0个任务。随着项目的进行，新任务会逐个加入。本文假设在tl时刻有Nnew(tl)个新任务加入，即在tl时刻项目中已经有共计N0+Nnew(tl)个任务需要考虑。每个任务Wj具有以下属性：

TPG表示任务优先级关系的有向图；

2.3 动态事件

本文主要针对软件项目实施过程中经常出现的不确定性和动态事件，包括新任务的加入、员工的离开和回归及任务工作量的不确定性，分别用el1，el2和el3表示动态事件的类型、发生事件和其他的额外信息。具体描述如下：

ev={el1,el2,el3}；

(1)

(2)

(3)

(4)

假设所有动态事件发生的概率服从泊松分布，同类型动态事件间的发生时间服从指数分布。

2.4 解的表征

2.5 优化目标及约束

在每个重调度点tl(tl>t0)，需要考虑的优化变量包括：一系列可被调用的员工e_ava_set(tl)、一系列可被调度的任务W_ava_set(tl)，以其相应的剩余工作量和在tl时刻更新了的任务优先级图(Work Precedence Graph,WPG)。在重调度点tl，多目标动态软件项目调度问题可以定义如下：

(5)

其中目标函数[Td,Tc,Tr,Ts]对应软件项目的持续时间、项目成本、调度的鲁棒性和稳定性。

(6)

(7)

(8)

(9)

通过计算相邻两个重调度点间的偏差和来表示项目的稳定性，目的是避免员工在不同调度点间被频繁地调来调去。其中权重ωij的取值如下：

(10)

同时调度解还需要满足如下约束条件：

(1)在tl时刻后的某个时间点t′，员工对其所有正在参与任务的贡献度和不大于他的最大贡献度值。

(2)所有参与分配任务的员工应具有完成任务所需的所有技能数。

(3)分配到每项任务Wj中的员工不能大于该项任务的最大人手数目限制。

在每个重调度点tl，软件项目经理可以通过相应的决策方法选出一个非支配解作为调度方案实施[7]。据此，相应的软件项目总持续时间Fd和总成本Fc计算公式如下：

(11)

(12)

其中tL表示项目最后一个重调度点。

3 改进的双归档进化算法

ITAA首先运用种群初始化策略，获得丰富多样性和良好收敛性的初始种群；然后引入自适应的子代生成策略，更优地搜索解空间；最后结合质量指标Iε+[18]和动态拥挤度距离[19]进行档案更新，以较低的复杂度很好地实现算法收敛性与多样性的平衡。基本的双归档进化算法见文献[16-17]。

3.1 种群初始化策略

在双归档进化算法中，采用随机方法进行种群初始化，生成的种群往往分布不均匀，使得算法容易陷入局部最优。针对该问题，本文引入佳点集理论[20]构造搜索解空间的佳点，并将其作为初始种群。图1为采用佳点集方法和随机方法生成的规模为100的二维初始种群分布对比图。由图1可知，在相同的取点个数下，采用佳点集方法较随机方法生成的初始种群分布更加均匀，多样性更加丰富。

均匀分布的初始种群丰富了算法的多样性，为遍历解空间中的各种情况打下了基础。为了进一步提升算法处理MODSPSP的效率，本文针对MODSPSP的动态特性和不同重调度点的历史信息引入启发式策略[15]。在每个调度点上，上一个调度留下的信息被视为可以利用的历史信息；上一个重调度点，员工和任务间的贡献度值分配方案被称为历史解决方案。首先，从新任务的加入、员工的离开和回归这3种不同类型的动态事件出发设计解的修复机制，针对上述情况下员工可能出现的加班问题，采用规范化进行处理。然后，利用上一个重调度点生成的非支配解集中的历史信息进行种群初始化。

3.2 自适应子代生成策略

在进化算法寻优过程中，如何协调算法的全局搜索和局部搜索是提升算法搜索效率的关键。单一的交叉、变异方法选择和固定的交叉、变异概率往往只能使得某一方面的搜索能力得到强调，而不能起到协调作用。针对该问题，本文综合考虑了MODSPSP的具体特点和种群的进化过程提出一种自适应的子代生成策略。

首先，通过结合两种不同搜索能力的交叉、变异方法，引入的交叉方法包括具有较优全局搜索能力的二项式交叉操作[21]和具有很强局部搜索能力的模拟二进制交叉[22]；变异方法包括DE/rand/1变异策略和DE/best/1变异策略[23]。其次，利用评价函数比较两种交叉方法产生后代与父代的优劣关系，赋予表现更优的交叉方法更大的交叉概率。在算法迭代初期，代表全局搜索能力的交叉方法通过大而广的搜索获得大量更优的子代，由此被赋予更大的交叉概率，进一步增强了算法在迭代初期的全局搜索能力。在算法迭代后期，代表局部搜索能力的交叉方法通过精而细的搜索容易获得更优的子代，由此被赋予更大的交叉概率，使得算法在迭代后期的局部搜索能力得到进一步加强。

具体过程如下：

第i种交叉操作过后，比较第j个父代(Parentj)和它产生的后代(Offspringj)的优劣性，并由此给出相应的评价函数F(Crossi)：

(13)

(14)

(15)

其中：Pci表示第i种交叉操作交叉前的概率，Aft(Pci)表示第i种交叉操作交叉后的概率。

具体事例如表1所示。可以看出，本文提出的策略可以赋予表现更优的交叉操作更大的交叉概率。

表1 自适应交叉操作实例

同理，变异操作也采用与上述交叉操作同样的自适应方法。

自适应子代生成策略具体过程如下：

步骤1交叉操作。从CA(tl)中随机选出两个体x1和x2，比较两个个体的占优关系，若x1≻x2则选择x1作为父代个体，同理从DA(tl)选出另外一个父代个体，进行交叉操作获得子代个体加入D1(tl)，直到|D1(tl)|=2×npop。

步骤2变异操作。从CA(tl)中随机选出一个个体进行变异操作，将获得的子代个体加入D2(tl)，直到|D(tl)|=npop。

步骤3D(tl)=D1(tl)∪D2(tl)，输出D(tl)。

3.3 档案更新策略

在双归档进化算法中，采用基于Pareto占优关系的档案更新策略，丰富了算法的多样性，但在处理MODSPSP时，无法提供足够的选择压力，直接影响了算法收敛。另外，固定的总档案规模容易造成算法的多样性缺失，因为当CA中的解均来自问题的Pareto前沿而CA的个体数已经达到档案的总规模时，会导致档案DA中个体的缺失，直接影响算法的多样性。针对这些问题，本文对档案CA和DA分别采用固定的档案规模nCA和nDA，引入具有良好收敛表现的质量指标Iε+对档案CA进行更新，在Pareto占优关系的基础上引入动态拥挤度距离对档案DA进行更新。

3.3.1 CA更新策略

质量指标Iε+的计算公式如下：

(16)

(17)

其中:x1,x2表示解向量，m表示目标，F(x)表示对应个体的收敛性适应度值。

具体过程如下：

步骤1将CA和子代种群Q组合成混合种群Hc。

步骤2找出混合种群Hc中的非重复解记为CA(tl)。

步骤5若|CA(tl)|>nCA依然成立，返回步骤3；否则更新结束。

3.3.2 DA更新策略

在处理MODSPSP时，保留所有Pareto最优解不仅没有实际意义且计算量巨大，软件项目经理需要的是一系列均匀分布的Pareto最优解。针对该问题，引入合理的多样性维护方法是关键。拥挤度距离排序法作为一种常见的多样性维护方法[24]，能在保证对问题Pareto前沿良好覆盖的情况下，剔除集中在密集区域的解个体。计算方法如下：

(18)

其中：Li表示xi的拥挤度距离，xi-1和xi+1是距离xi最近的两个点，fk(xi-1)和fk(xi+1)为对应的目标函数值。但这种方法可能会在同一时间删除密集区域的大量个体，影响解的均匀分布。针对该问题，本文引入动态拥挤度距离，在二维解空间两种方法得到的Pareto最优解分布对比如图2所示。显然，采用动态拥挤距离对档案进行更新，得到的解分布更加均匀。

具体过程如下：

步骤1将DA和子代种群Q组合成混合种群Hd。

步骤2将混合种群Hd中的非支配解记为DA(tl)。

步骤3若|DA(tl)|>nDA，初始化DA(tl)中个体的拥挤度距离，将边界解个体初始化一个极大值，保证所有的边界解在下一次迭代中可用。

步骤6若|DA(tl)|>nDA依然成立，返回步骤4；否则更新结束。

3.4 算法步骤

步骤1主动调度。在软件项目初始阶段取l=0，利用ITAA自动生成一系列优化目标为项目持续时间、项目成本、调度的鲁棒性和稳定性的非支配解，并从中选择一个解作为调度方案实施。

步骤2重调度。当动态事件发生，l=l+1，在每个重调度点有如下子步骤：

(1)初始化。对档案CA和DA运用3.1节种群初始化策略初始化相应种群规模的档案个体，根据正态分布随机取样任务工作量θq,q=1,2,…,Q，初始化最大目标向量评估数NumEvl，赋值ct=0。

(2)生成子代。根据正态分布随机取样一系列任务工作量θ′q，q=1,2,…,Q，根据3.2节提出的自适应子代生成策略生成子代D(tl)，ct=ct+|D(tl)|。

(3)档案更新。对于加入的子代个体D(tl)根据3.3节提出的档案更新策略进行更新，以维持CA和DA所具有固定种群规模nCA和nDA。

(4)直到ct=NumEvl，输出表示优化目标为项目持续时间、项目成本、调度的鲁棒性和稳定性的非支配解集DA，并从中选择一个解作为调度方案实施，直到软件项目中的任务全部完成。

3.5 算法复杂度

设双归档进化算法的种群规模为N，针对目标数M的优化问题，算法复杂度分析如下：

3.5.1 时间复杂度

初始化种群，包括两档案2N个体，复杂度是Ο(2N)；自适应的子代生成策略，包括生成3N子代，并在生成过程引入评价函数，复杂度最多为Ο(9N2)；档案更新策略，包括档案CA中个体适应度的计算，并在最差适应度解剔除后剩余个体适应度的重新计算，复杂度最多为Ο(MN2)，档案DA中个体适应度的计算，并在最差适应度解剔除后相邻个体适应度的重新计算，复杂度最多为Ο(MN2)。通过上述分析，ITAA整体时间复杂度为Ο(MN2)。

3.5.2 空间复杂度

存储档案CA和DA中个体的每个参数所需的空间均为N；存储每个个体所需的空间为M，则存储2N个体所需空间为2MN；子代生成过程中利用评价函数调整交叉、变异概率所需空间为3N；其他参数所需空间均为常数。经过上述分析，算法搜索过程的空间复杂度为Ο(MN)。

4 实验部分

本文所有程序代码均采用Java语言和Eclipse软件编写，使用的PC机配置如下，操作系统：64位Windows 10，处理器：Intel(R)Core(TM) i7-7700 CPU 3.60 GHz，内存：16 G。

4.1 实验设置

为了分析改进策略的有效性，设置如下对比算法：基本双归档算法Two-Arch[16]，在基本算法中加入种群初始化策略TA-PIS，再加入自适应子代生成策略TA-PIS-AOG。在实例选择上，本文针对文献[15]中的21个实例进行求解，考虑了任务工作量的不确定性和3种不同类型的动态事件(包括新任务的加入、员工的离开和回归)，同时还将任务的最大完成人数、员工的技能等级、员工兼职、加班考虑在内。实例包含不同的员工数、任务数和员工掌握的技能数，初始的任务数为10,20,30，10个新任务逐个加入到项目中，员工数为5,10,15，员工掌握的技能数为4～5和6～7。记18个MODSPSP实例为s#1_d#2_E#3_SK#4～#5，s#1表示初始任务数，d#2表示加入的动态任务数，E#3表示员工数，SK#4～#5表示每个员工具有4～5技能，3个现实实例记为r1、r2和r3。

根据2.5节的描述可知，当算法在不同的重调度点都能有良好且稳定的表现时，即可获得更优的项目总持续时间和成本。因此，本文的实验将从整体和不同重调度点的Pareto解集两方面进行设计。

具体的参数设置如下，ITAA的种群规模npop=100，CA和DA的固定个体数nCA=nDA=100，任务工作量不确定性抽样数q=30，初始交叉概率：多项式交叉和模拟二进制交叉的交叉概率取0.45；初始变异概率：DE/rand/1和DE/best/1的变异概率取0.05，最大目标向量评估次数NumEvl=16 000。20%的初始化种群个体来自启发式策略，剩余的80%个体采用佳点集方法生成。为了保证对比实验的公平性，对比算法具有相同的参数设置。本文采用文献[15]的中决策过程在每个重调度点选出一个调度方案实施，以保证在每个重调度点算法能在同一环境下比较。

4.2 实例Pareto解集比较

4.2.1 IGD分析

如表2所示，ITAA在所有的现实实例中都表现最优。18个MODSPSP实例中，与Two-Arch算法相比，ITAA在16个实例上显著优，2例相似。与TA-PIS算法相比，ITAA在14个实例上显著优，2例相似，2例较差。与TA-PIS-AOG算法相比，ITAA在8个实例上显著优，9例相似，仅有1例较差。而且在17个实例中有最优的平均值，综合表明ITAA有着明显优于其他3种算法的性能表现。

4.2.2 命中率分析

命中率(Hitrate)指的是程序找到可行方案解的次数(FRuns)与程序运行的总次数(Runs)间的比值，即

(19)

将算法在21个实例上的命中率实验结果记录于表2。如表2所示，Two-Arch算法的总体命中率偏低，有的实例甚至为0。当对Two-Arch算法采用种群初始化策略后，在所有实例上的命中率都达到了100%。在此基础上，先后采用自适应子代生成策略和档案更新策略，命中率依然维持在100%，说明改进策略对算法命中率提高的有效性和稳定性。

4.3 重调度点Pareto解集比较

为了证实算法在不同重调度点都能生成一个具有好的收敛性且均匀广泛分布的Pareto解集。本文针对3个不同实例从最优值、平均值和最差值出发绘制图3所示曲线图；随机选择实例sT20_d10_E15_SK6～7，tl=16.8，员工e2返回，项目中还有9个任务需要完成，绘制图4所示平面图。

4.3.1 重调度点IGD分析

如图3所示，ITAA在大多数的重调度点都表现最优且表现稳定，说明ITAA在不同重调度点具有稳定的良好表现。对比Two-Arch算法，随着改进策略的加入，算法的收敛性和多样性表现呈渐进式增长且逐渐趋于稳定，更加说明了改进策略的有效性。

表2 实验结果

4.3.2 重调度点解的分布

由于MODSPSP的4个目标具有不同的规模，利用对比算法所有运行过程中记录的最大、最小目标值对Pareto解集中的目标值进行了归一化，得到图4所示的平行坐标图。如图4所示，ITAA生成的非支配解集在目标空间中有着良好的分布。可以看出，Pareto解集不是在一个有限的区域内，而是分布在一个较大的范围内。这一结果表明了ITAA在重调度点tl能生成一个具有好的收敛性且均匀广泛分布的Pareto解集。

5 结束语

本文针对双归档进化算法在处理多目标动态软件项目调度时，算法的收敛性、多样性和复杂度难以平衡和命中率低的问题，提出一种改进的双归档进化算法来求解该问题。首先，采用佳点集方法和启发式策略进行种群初始化；然后，利用评价函数自适应地对两种代表不同搜索能力的交叉、变异方法进行概率调整；最后，引入质量指标Iε+和动态拥挤度距离分别对收敛性档案和多样性档案进行更新。

员工作为软件项目调度需要考虑的唯一资源，在未来工作中将引入更多的员工属性，使得问题模型更具现实意义。