多种群蚁群算法优化方案

在单一种群蚁群算法的基础上，有学者提出双蚁群系统，通过蚁群间的互动对信息素信息进行分享，在充分利用优秀解的同时扩大搜索的解空间，比单蚁群系统取得了更好的效果（Kawamura et al.，2000）。但上述算法针对单目标优化问题进行的设计。在上述研究的基础上，开发如下的适用于多目标项目调度问题的多种群蚁群算法（multi-colony ant algorithm，MCAA）。

算法遵循一般ACO算法的流程。但是在状态转移规则、信息素更新机制和精英策略上，有所不同，分别叙述如下。

1.状态转移规则

在MCAA中，用（l，k）表示第l个种群的第k只蚂蚁，则蚂蚁（l，k）在选择任务j后接着选择任务h的概率可以表示为：

其中，ψlk（j，h）表示蚂蚁（l，k）在选择任务j后继续选择任务h的倾向程度，定义如下：

其中，参数α（l，r）决定种群l和种群r之间信息素的影响。如果α（l，r）的值为正，则种群r的信息素对种群l中的蚂蚁搜索决策存在正向促进效应；如果α（l，r）为负，则种群r的信息素有负向的抑制效应。α（l，r）的绝对值越大，信息素的正效应或负效应越强；如果a（l，r）为零，则种群l和种群r之间不存在相互影响。式（8.30）中，ε为一较小的正常数，以防信息素浓度为零的情况。β（l）表示启发式信息在蚁群l的搜索决策中的权重。

在MCAA中，可能涉及多个相互冲突的目标函数。因此，设定不同的蚁群各自对应不同的目标函数，且各蚁群可以利用不同的启发式信息，以增进搜索效率。

假设第一个蚁群的目标函数为项目总工期最小，采取经典RCPSP中普遍使用的最晚结束时间（LFT）优先规则，如式（8.19）所示。

假设第二个蚁群的目标函数为加权任务拖期最小。设计如下的基于任务拖期的优先规则：

则第二个蚁群的启发式信息为：

2.信息素更新机制

在MCAA中，蚁群l的信息素可采用如下更新机制：

其中，Δτlk（j，h）表示蚂蚁（l，k）在路径（j，h）上释放的信息素，其浓度取决于所得解的质量。(www.xing528.com)

对于不同的种群，可设计不同的信息素更新机制。

对于第一个种群，设计如下信息素增量：

其中，ρ1为一正常数，cJ（l，k）表示蚂蚁（l，k）得到的项目进度计划的总工期。

对于第二个种群，设计如下的信息素增量：

其中，ρ2为一正常数，WT（l，k）表示蚂蚁（l，k）得到的项目进度计划的加权任务拖期。

信息素挥发机制采用式（8.20）所定义的方式，并设定各蚁群的信息素挥发率相同。

3.多目标精英策略

设计如下的多目标精英蚂蚁改进策略。其基本思路是，多个种群并行进行搜索，当蚂蚁完成一次搜索之后，对这个解进行评估，并与当前最优解进行比较。评估与比较时，采用理想点（ideal point）方法（Marler and Arora，2004），以所得解与理想点的欧氏距离作为评估标准，如所得解的欧氏距离小于已知的最短距离，即为新的最优解，并对其所对应的路径进行额外的信息素增强，从而加快算法收敛速度。

在多目标精英策略中额外增加的信息素为：

其中，ρ3为一正常数，wi为各目标函数权重，fi*为项目第i个目标函数的目标值，H*表示当前最优解所对应的哈密尔顿回路。

综上所述，针对多目标资源受限项目调度问题设计的多种群蚁群算法如下所示（寿涌毅、傅奥，2010）。