算法测试与分析优化方案

采用实验方式对上述PSO算法的求解效果进行评估。采用Java语言编写PSO代码，并在HP IQ526cn计算机上测试。机器的主频为2.00GHz，RAM为4.00GB。采用PSPLIB中的RCPSP算例库作为测试实例。PSPLIB的RCPSP算例库按包含的任务数量分为j30、j60、j90和j120四组。其中，j30算例库已用精确算法求得最优解，其余3个算例库则给出了解的最大下界及当前最好解。

1.参数设置

在参数选择上采用Shi和Eberhar（t1998）的研究结论，在速度最大值不超过2的时候，惯性因子的较好选择为1，在速度最大值超过3时，惯性因子的较好选择为0.8。参考Zhang等（2005），将学习因子设为1，粒子群的大小swarmSize设为项目的任务个数。所有算法都最多产生5000个进度计划。四种PSO算法的参数设置如表9.2所示。

表9.2　PSO算法参数设置

2.实验结果

按照表9.2的参数设置，将四种PSO算法分别应用于j30、j60、j90及j120四个算例库中的所有实例。另外，为了说明“允许一次抢占”对问题解的影响，也将PSO（AL）和PSO（PV）算法应用于RCPSP，并统计结果数据。表9.3至表9.6是求解结果中总体偏差率的统计。其中“基准解偏差”部分统计的是各PSO算法求解结果与算例库中各实例的最优解（针对j30）或已知最好解（针对j60、j90和j120）的比较。“关键路径法解偏差”部分统计的是各个PSO算法求解结果与根据关键路径法计算得出的项目总工期的对比。在各个指标中，AD是所有实例的平均偏差率（average deviation）；MD是最大偏差率（maximum deviation）；PO是所有实例中求得最优解的比例（percentage of optimal solutions）；PB则是好于最优解的比例（percentage of better solutions）。以上所有数值都用百分比表示。此外，还给出了算法的平均CPU时间，单位为秒。

以表9.3为例，PSO（AL）的基准解偏差AD＝0.59％、MD＝7.35％、PO＝79.38％，表示在j30算例库中，针对RCPSP，PSO（AL）算法所求得的所有实例的解与PSPLIB中给出的最优解的偏差平均值为0.59％，其中偏差最大达到7.35％，有79.38％的实例求得最优解。PB一栏主要针对1_PRCPSP，因为“抢占”的引入可能使得部分实例求出比PSPLIB最优解更好的解。例如，针对1_PRCPSP，PSO（AL）的基准解偏差PB＝24.38％，表示在j30中，有24.38％的实例（480×24.38％＝117）求得了比RCPSP最优解更好的解。相应地，AD＝－0.43％，也说明“抢占”确实能发挥作用。关键路径法偏差一栏中，统计指标与基准解偏差一样，只不过参照的标准变成了CPM求得的解。我们注意到所有算法的关键路径法解偏差PB指标都为0，这是因为CPM是不考虑资源约束的，因此不管是否允许抢占，RCPSP的项目总工期都不可能比CPM总工期更短。

表9.3　j30算例库测试结果

表9.4　j60算例库测试结果

表9.5　j90算例库测试结果

表9.6　j120算例库测试结果

从实验测试结果来看，在所有4个算例库中，允许抢占都有助于减少项目总工期。(www.xing528.com)

从基准解偏差的指标来看，对于j30算例库，最好的算法是PSO（PVPP），在27.92％（134个）的算例上求得了比非抢占情况下的最优解更好的解。对于j60、j90和j120，最佳算法和PO值分别是PSO（PV）的8.13％（39个）、PSO（AL）的4.38％（21个）和PSO（PV）的2.29％（14个）。

如果统计PO和PB的和，则对于j30算例库，最好的算法是PSO（PV），在97.08％（466个）的实例上求得了与非抢占情况下的最优解相当的或更好的解，比非抢占情况下PSO（PV）的83.96％高出13.12个百分点。对于j60、j90和j120，最好的PO和PB之和分别是76.88％、73.96％和34.34％，分别比非抢占情况下的最好结果高出3.76、0.66和1.84个百分点。针对平均偏差的指标，抢占情况下的求解结果也显著好于非抢占情况。尤其对于j30算例库，所有抢占情况下的算法都求出了小于零的AD，而最好的PSO（PV）求得的AD达到－0.65％。

从关键路径法偏差的指标来看，允许抢占和不允许抢占导致了显著差异。当允许抢占时，在j30算例库中，最好的算法PSO（PVPP）在48.96％（235个）实例上求得了与CPM一样的解，而非抢占情况下这个值是PSO（PV）的44.38％（213个）。在其他三个算例库中，这两组数据分别是63.33％对60.42％、70.83％对67.71％、28.67％对27.92％。AD指标也反映了抢占情况优于非抢占情况。

测试结果还显示出抢占的影响在四个算例库中是不一样的。从基准解偏差的指标来看，对于PO和PB，1_PRCPSP的最好算法比RCPSP的最好算法，在四个算例库中求得的结果高出的比例分别是13.12、3.76、0.66和1.84个百分点。而从关键路径法偏差的指标来看，这一结果分别是4.38、4.16、1.06和2.08个百分点。随着项目规模的扩大，抢占所带来的工期改善率显著下降；但考虑到项目规模变大后工期也随之变长，工期改善的绝对值依然相当可观。

表9.7、表9.8及表9.9展示了不同算例库参数对抢占效果的影响，分别汇报了网络复杂度（NC）、资源系数（RF）及资源强度（RS）的影响。就不同的NC、RF和RS取值，分组统计了对于1_PRCPSP最好的PSO算法相比于RCPSP最好PSO算法的求解结果。改善实例比例（percentage of improved instances，PII）表示，在相应组别下，PSO算法针对1_PRCPSP求得的好于RCPSP实例的比例。平均改善率（average improvement，AI）则表示在相应组别下的所有实例中，1_PRCPSP相比RCPSP所改善的项目总工期的平均值。

表9.7　网络复杂度的影响

表9.8　资源系数的影响

表9.9　资源强度的影响

表9.7是根据网络复杂度分组统计的PII和AI值。在j30算例库中，PII和AI都随着网络复杂度的增加而明显减小；而在j60中，PII则随着网络复杂度的增加而增大，AI则没有明显变化趋势。在另外两个算例库中，j90呈现出与j30完全相反的趋势，PII和AI都随着网络复杂度的增加而增大；j120的趋势则是一个U形曲线，当NC＝1.8时，PII和AI均处于较低的水平。总体而言，除了j30数据集，其他组实例都在网络复杂度达到2.1时，PII和AI达到最大值。网络复杂度定义为一个项目网络中，平均每项任务拥有的非冗余弧的数量（Kolisch et al.，1995），它反映了项目网络中各项任务间优先关系的松紧程度。因此，上述测试结果或许反映了一个现象：当项目任务数较少时，任务间优先关系越紧密，抢占对项目工期改善的作用越有限；而当项目任务数较多时，任务间优先关系越紧密反而越有利于抢占机制发挥作用。

表9.8展示了资源系数对抢占的影响。可以看到，在j30与j60算例库中，PII均随着资源系数的增加而显著增大。尤其是j30算例库，当RF＝1.00时，PII为51.67％，比RF＝0.25时的22.50％增加了一倍多。但是随着任务数量的增加，资源系数对于两项指标的影响渐趋微弱。在j60算例库中，当RF＝1.00时，PII为35.83％，只比RF＝0.25时的30.00％多出5.83％。在j90算例库中，当RF＝0.50时，PII达到最大的34.17％。类似地，在j120算例库中，当RF＝0.75时，PII最大为68.00％。此外，AI指标也呈现出类似的趋势。这似乎意味着，当项目任务数量较多时，资源系数将不再线性地影响抢占的改善效果。

相比网络复杂度和资源系数，资源强度对于PII和AI两个指标都有着强烈的影响。从表9.9可以看出，资源强度越低，PII和AI都越高。四个算例库都表现出这一趋势。这一结果的实际意义也是显而易见的。由于资源强度描述了项目任务的资源需求与资源总量之间的关系，反映了资源的稀缺情况。当资源强度较低时，资源较为紧张，引入抢占有利于优化项目调度过程中的资源分配，从而显著改善调度结果。