算法测试与分析探究

采用本书第3章所构造的多项目调度算例库中的256个算例对本算法进行计算测试。设定多项目遗传算法（MPGA）的种群规模为50，总世代数为100。其他参数设置如表7.2所示。

表7.2　多项目遗传算法参数设置

上述不同参数设置一共可以组合成3×3×2＝18种MPGA算法，此外还可以在MPGA算法中结合MPFBI对种群进行改善。在采用MPFBI时，遗传算法世代数减半。如此，一共可以产生36种MPGA算法，其计算所得结果如表7.3所示。

表7.3　多项目遗传算法计算结果

续表(www.xing528.com)

续表

与抽样算法相比，上述所有MPGA算法求解效果均优于PRS及采用MPFBI的PRS。在所有参数设置中，6号MPGA算法的求解效果最佳，4号、2号及10号算法紧随其后。不过，威尔科克森符号秩检验（Wilcoxon Signed Ranks Test）结果表明，6号MPGA与4号、2号算法相比并无显著差异，但显著优于10号算法（P=0.01）。

值得注意的是，方差分析证实，在应用MPFBI之后，MPGA的求解效果显著下降（P=0.001）。这可能存在两方面的原因。一是因为在应用MPFBI后，MPGA的迭代次数限制为原先的一半，因此种群的演化不够充分；二是因为MPFBI适用于对任务列表进行改进，而对于随机键表达方式，需要进行解码和编码，并不能直接针对染色体进行操作，因此在应用过程中可能破坏原先的遗传信息，使得算法效率下降。事实上，在所有采用MPFBI的MPGA，即第19至36号算法中，有12种算法求解效果不如CRS；而在第1至18号MPGA中，只有第13、15、17号三种算法求解效果劣于CRS。由于MPFBI效果不佳，后续针对第1至18号算法进行分析。

从表7.3中可以注意到初始种群的影响。方差分析也证实初始种群构造方式对求解效果具有显著影响（P=0.01）。整体来看，初始种群的多样性非常重要，而个体质量并不是关键。对交叉概率和变异概率的方差分析则表明，交叉概率对求解效果不具有显著影响，而变异概率具有显著影响（P=0.05）。这说明多项目进度计划在结构上与单项目进度计划具有差异，使得两点交叉算子对基于随机键表达方式的多项目遗传算法不是非常有效。而均匀变异算子因为与进度计划的结构无关，因而对于多项目调度仍然是有效的。所以，后续应当进一步设计更加有效的多项目遗传算法交叉算子。此外，种群规模对MPGA算法效率的影响也值得后续进一步研究。