算法的测试与分析的介绍，

由于对MORCPSP的已有研究较少，尚缺乏公认的算例库，甚至连如何评价算法优劣也值得深入探讨。寿涌毅、傅奥（2010）提出一种基于目标规划的算法测试方法，并利用单目标RCPSP算例库构造MORCPSP问题用于算法测试与对比分析。

选择Patterson算例库中的全部实例（Patterson，1984），将其目标函数设为工期最小化和加权任务拖期最小化，为各目标函数随机给定权重wi，=1。以关键路径法（CPM）给出的关键路线长度为项目目标工期。以CPM给出的各任务最早完成时间为任务截止时间，关键路线上的任务赋予区间[1，2]内的随机值作为拖期惩罚系数，非关键路线任务赋予区间[0，1]内的随机值作为拖期惩罚系数。

将关键路径法所得的项目进度计划作为目标解，将其所对应的各目标函数值作为目标值。

在对Patterson算例库进行上述改造后，可以用各类算法进行求解，并计算算法给出的最好解与目标值的差距，即可行解各目标函数与目标值之间的欧氏距离，并以该距离为评价标准，比较不同算法的整体表现。

对于MCAA，通过计算测试，设定最大循环次数为100次，2个蚁群的蚂蚁数量均为50只，确定其他参数取值为：α（1，1）=α（2，2）=1，α（1，2）=0，α（2，1）=0.1，ρ=0.6，r1=50，r2=200，r3=1000。

此外，也采用第8.2节的单种群蚁群优化算法（ACO）对110个MORCPSP问题进行求解，并比较不同算法所得解与目标值欧氏距离的最小值、最大值和均值。测试结果如表8.1所示，其中第5列表示ACO算法所得项目进度计划与目标值欧氏距离的均值高过MCAA均值的百分比。(www.xing528.com)

表8.1　各算法测试结果

表8.1说明多种群蚁群算法（MCAA）表现好于单种群的蚁群算法。进一步分析项目规模对算法表现的影响。在用于测试的项目实例中，任务数J=21的问题有46个，任务数J=26的问题有43个，任务数J=50的问题有10个。对这三类不同规模的问题，上述算法的表现如图8.1所示，其中纵坐标为各算法解与目标值的平均偏差。对于任务数J=50的问题，MCAA算法的平均偏差比单种群ACO算法要小3.15％，与其他启发式算法相比调度效果更加明显。这说明多种群蚁群算法对大型复杂项目调度有较好的表现。

图8.1　项目规模对算法效率的影响

在实际测试中也发现多种群蚁群算法存在信息素积累过快、容易陷入局部过早收敛的缺陷。这也是制约多种群蚁群算法搜索效率的主要因素。可以尝试调整信息素更新机制，设计新的全局优化方法等方式克服这一局限。

上述多种群蚁群优化算法，由于采用了理想点方法，本质上仍然是单目标优化算法，并不能产生一系列Pareto最优解。近年来，部分学者开始致力于将蚁群算法拓展到多目标优化领域，并已经取得了一定成绩（Angus and Woodward，2009；张勇德、黄莎白，2005），也将成为项目调度多目标优化领域后续研究的方向。