单项目调度蚁群优化算法优化

蚁群优化算法是对蚂蚁群体利用信息素进行觅食行为的仿生，已被广泛应用于各种组合优化问题，也已应用于求解RCPSP问题（Merkle et al.，2002；Shou，2006；余建星、李彦苍，2007）。

一般而言，蚁群优化算法基本上采用进度生成机制，通过逐步扩展局部进度计划来生成一个完整可行的项目进度计划，并通过反复搜索获得最好解。

项目调度蚁群优化算法的伪代码如下所示。

在上述蚁群算法中，蚁群中的每一只蚂蚁从第1个任务开始搜索，遍历所有任务，在第J个任务处结束搜索。在第g个搜索阶段，蚂蚁k在选择完任务j后，其候选任务集合记为Dk（j），这个集合包括了所有尚未安排进度，同时其所有紧前任务都已排好进度的任务，因此Dk（j）不但排除了已经被选择过的任务，还排除了在逻辑上不能直接安排在任务j之后的任务。蚂蚁k从Dk（j）中选择任务h的概率为：

其中，τ（j，h）为信息素浓度，η（j，h）为启发式信息，α和β为控制两类信息权重的参数。

启发式信息一般表示蚂蚁在搜索决策中可以利用的直观信息。在RCPSP问题中，一般用优先规则来构造启发信息。在RCPSP蚁群算法中较常采用最晚结束时间（LFT）来计算启发式信息（Merkle et al.，2002）：(www.xing528.com)

信息素的更新是蚁群算法的重点，包括信息素的挥发和累积。信息素的挥发可采用如下机制：

其中，ρ为信息素的挥发率。

在更新信息素时，对于蚂蚁搜索到的解，相应的信息素增量为：其中，H为蚂蚁搜索到的解所对应的哈密尔顿回路，f为目标函数值，对于RCPSP即为项目工期cJ。

当蚂蚁k从第1个任务逐步搜索到第J个任务，就构成一个完整的可行任务列表。可以发现，这一任务列表事实上对应了项目网络图中的一条路径，如果将最后一个任务与第一个任务进行连接，则构成一个哈密尔顿回路。以该任务列表中的顺序，采用TSGS，在满足资源约束的前提下，按照尽早原则逐个安排所有任务的开始时间，就得到一个可行的项目进度计划。