自适应混合蚁群算法在MRCPSP中的应用

闫 森，王玉玫

(1.华北计算技术研究所系统三部，北京 100083； 2.华北计算技术研究所总体部，北京 100083)

0 引 言

活动工期的不确定性和多模式问题在项目调度中往往难以避免，为了如期完成任务，厂家往往通过增加资源投入来减少工期，由此产生了工期不确定的多模式资源约束项目调度问题(Multi-mode Resource Constrained Project Scheduling Problem， MRCPSP)[1]。多模式指同一活动的不同执行模式会有不同的活动工期以及相应的资源需求量。

MRCPSP中活动的执行除了要受到其紧前事件的限制，还要受到多种资源的约束。MRCPSP作为一种复杂的非线性NP难问题，很难利用精确算法[2]去求得最优解，而启发式算法[3-4]和智能优化算法(遗传算法[5-7]、模拟退火算法[8-9]、粒子群算法[10-11]和蚁群算法[12])往往能在求解精度和效率之间取得令人满意的效果，并且因为活动工期常来源于经验与主观预测，具有不准确性，因此往往采取随机任务工期的方法[13-15]。

自然界中，蚁群通过释放信息素，指导后续蚂蚁寻找目标，由此概念产生的蚁群算法在解决NP难问题方面功效尤为显著[16]。Chen等[17]将云工作流调度建模为一个多目标优化问题，使用2个蚁群分别处理这2个目标，提出了一种新的信息素更新规则。Zhou等[18]提出了一种新的混合互补启发式策略，该策略包含3种启发式信息方案，以避免蚁群只关注自己的目标。Mutar等[19]使用改进的蚁群算法解决CVRP问题，依赖于利用以前迭代中的子路径经验进行的信息素更新。迄今为止，对于改进蚁群算法的优化研究有些单纯在信息素更新策略方面进行改进而忽略了其他参数的影响[17-18，20]，有些在迭代过程中不能很好地对参数进行自适应更新[21]，于二者的平衡问题仍缺乏相关深入探索，有必要进行进一步的研究探索，加以优化。

因此，本文基于MRCPSP问题的特点，针对启发式蚁群优化算法收敛速度与解的质量之间的平衡问题，提出一种改进的自适应混合蚁群算法(Adaptive Hybrid Ant Colony System algorithm， AHACS)，并通过仿真实验结果验证该算法较其他算法的优越性。针对任务工期不确定问题，本文再基于改进的AHACS算法，采用模糊理论的方法，为项目工期的不确定性预留时间缓冲区。

1 问题建模和蚁群算法

1.1 MRCPSP问题

采用由活动及其可选模式组成的AOA(Activity-On-Arrow)图的方式对MRCPSP问题中的活动时序约束进行描述，可以清晰地显示出项目中活动的时序约束关系，如图1所示。对某一活动的正常执行，必须满足箭头紧前事件执行完成这一要求。为方便求解，引入虚事件0和N+1作为项目“开始”和“结束”虚拟活动，且只有一种执行模式(不占用资源和执行时间)。

图1 AOA图

求解MRCPSP问题，实质是寻求项目中每个活动的执行模式与开工时间之间的最佳组合。问题优化目标是在满足项目调度问题资源和时序条件约束下，通过合理地选择执行模式和时序使项目工期最短(网络图最短路径)，目标函数表达式如式(1)所示：

f(x)=Min(TN+1)

(1)

数学模型中的资源约束条件如式(2)所示，时序约束条件如式(3)所示：

(2)

(3)

其中，TN+1表示从初始任务到任务N+1所耗费的最短工时；(i,j)表示从任务i到任务j的活动；At表示t时刻正在进行的活动集合；Mij表示活动(i,j)的可选执行模式集合；rijkm表示以模式m执行活动(i,j)在单位工时内所耗费k类型资源的数量；Rk表示k类型资源的总量；xijm表示模式的选择，当活动(i,j)使用模式m时,xijm为1，否则为0；djlm表示完成活动(j,l)的工期，P(j)表示任务j的紧前任务集合，N(j)表示事件j的后继任务集合；如果活动(i,j)在处于[STij,ETij]时间窗内的时刻t被完成，则yijt为1，否则为0。

1.2 ACS算法

蚁群算法起源于自然界中蚁群寻找最短路径的策略，蚂蚁每到达岔路口时，都需要结合之前蚂蚁留下来的信息素含量及贪心算法进行道路选择。信息素含量可以帮助每只蚂蚁判断每条路径上走过蚂蚁的数量，贪心算法则可以从候选集中筛选出距离最短的点。信息素以一定的概率消失，可以避免信息素过多。

在MRCPSP中，由于在相应活动及活动对应模式的选择过程中，蚁群算法中的信息素会被释放并且随着迭代次数的增加而不断更新，因此在最优路径(最短项目工期)所包含的各个路径上信息素得以积累，这使得后继蚂蚁选择该路径的概率增大，并逐渐收敛到最优路径。

2 改进的AHACS算法

2.1 初始化过程

初始化启发项矩阵中值的大小由所选贪心策略来决定，用于记录项目调度中每个活动被选择的概率。在MRCPSP问题中，固有概率设为选取该活动所需的各类型资源总量与各类资源总资源量之和的比值，计算公式如式(4)所示:

(4)

信息素是MRCPSP中后续蚂蚁对路径选择的主要依据，本文采用信息素强度因子与活动数的比值对路径的信息素含量矩阵初始化，如式(5)所示：

(5)

引入多态蚁群思想，设置先驱侦察蚁来优化信息素的初始化分布。当启发因子α、期望启发因子β、信息素强度Q和信息素挥发因子ρ取值较小时，蚁群算法的搜索随机性增强，但收敛性变差。因此赋予侦察蚁的α、β、ρ值趋于极小，并设置适中的Q值，让其尽可能大范围地进行全局搜索，这有利于增加解的多样性，从而对信息素矩阵进行进一步的更新。

2.2 参数自适应阈值与混合蚁群

启发因子α表示信息素的重要性，期望启发因子β表示在指导蚁群搜索过程中启发式信息的相对重要程度。因此，为了优化MRCPSP问题中后续蚂蚁对路径(活动时序和模式)的选择策略，更好地平衡解的多样性与收敛速度，算法前期应该尽量搜索整个解值空间，α、Q应趋于极小值，而β、1-ρ应趋于极大值；算法后期则应加强正反馈作用从而加快收敛的速度，α、Q应趋于极大值，β、1-ρ应趋于极小值[21]。蚂蚁参数均在自适应调整后的阈值区间内随机取得，形成每只蚂蚁参数不同的混合蚁群。对于第t次迭代的第i只蚂蚁，其α、β取值如式(6)、式(7)所示。

αi(t)=random(αmin(t),αmax(t))

(6)

βi(t)=random(βmin(t),βmax(t))

(7)

算法初期，考虑到需要在一定的迭代次数内保证算法拥有足够的全局搜索能力，避免算法陷入局部最优，参数的自适应增量应较小；算法迭代后期，α、β的取值对算法解的质量影响越发弱化，因此应加快参数调整速度以促进算法的收敛速度加快，这个过程如式(8)、式(9)所示：

(8)

(9)

算法迭代后期，一味增加全局搜索能力不仅没有必要，而且会严重影响算法收敛速度，故应调整相关参数，推动整个算法的收敛。

采取传统的轮盘赌方式作为状态转移策略，根据当前活动的启发项信息和信息素含量进行综合考虑，决定蚂蚁下一活动的选取概率，计算公式如式(10)所示：

(10)

2.3 信息素挥发因子改进

改进信息素挥发因子能够控制算法正反馈过程，优化信息素更新策略。当ρ取值越大，全局搜索能力也随之变小，但收敛速度快；取值越小，收敛速度减慢，但全局搜索能力增强。本文所研究的算法，对每次迭代中ρ的取值都限制在(ρmin,ρmax)内随机取值，如式(11)所示。ρmax的取值随着迭代次数的增加自适应调整，如式(12)所示。ρ在范围内随机取值，可以避免其调整过程中出现ρ过快趋近于ρmin，最终导致某条路径信息素强度过大。

ρ(t)=random(ρmin(t),ρmax(t))

(11)

(12)

2.4 信息素更新策略改进

精英蚂蚁策略中，对每轮迭代中精英蚂蚁(全局最优蚂蚁)路径上的信息素进行自适应奖励，以增加该路径被选择的概率[20]。本文在此基础上做出进一步优化，引入排名因子对应权重值μ，以赋予排名靠前的蚂蚁更高的权重。蚂蚁更新信息素含量的策略中按排名因子规则引入相应的权重值μ，如式(13)所示。这种改进不仅是为了提高发现更优路径蚂蚁的话语权，还可以避免落后的经验形成自锁或压制更优解的产生。为防止最优路径被遗忘，每轮迭代中的最优路径劣于目前发现的全局最优路径时，将全局最优路径排到首位，以保证最优路径在被更优的路径取代之前不会被遗忘。

(13)

局部信息素的更新以及精英蚂蚁的选取，可能令信息素含量过大而导致算法过早停滞。针对这一问题，本文参考最大最小蚁群算法(MMAS)[22]的思想，定义信息素含量上下限的概念，信息素上限如式(14)所示。在算法运行后期，可以通过提高信息素上限，实现加速收敛。设定信息素上下限，能够有效增强蚁群的全局搜索能力，对提升解的质量有一定帮助。

(14)

2.5 信息素强度系数改进

AHACS算法中信息素强度Q的取值会在信息素更新过程中逐渐增大。当Q的取值较大时，会导致算法过早陷入局部最优解；取值较小时，会拖慢算法收敛速度。综合考虑，在算法运行的初期，Q应该取较小值，以增强全局搜索能力；算法运行到后期时，自适应选择较大的Q值，从而加快算法收敛速度。因此，可在算法中用式(15)所示的线性函数代替常数信息素强度。

(15)

3 仿真实验

3.1 AHACS算法解决MRCPSP问题

本文在文献[23]的基础上产生多组数据集验证算法的有效性，为了便于凸显比较结果，选择如图2所示的24事件37活动的较大规模的项目调度数据集，来对比验证AHACS算法在解决MRCPSP问题上的有效性，使用PyCharm进行仿真实验。引入3种可动态调度的资源R1、R2和R3，单位工期的可使用数量上限分别设为8、16和20。除0与N+1活动外，项目中每个活动包括普通工期模式(N)和资源换工期的压缩工期模式(C)这2种可执行模式。

图2 AOA仿真图

仿真实验分别将AHACS算法与自适应调整信息素挥发系数的QAACO算法[24]、带有局部更新策略和精英蚂蚁系统(EAS)的EACS算法[12]和遗传算法(GA)[5]在项目调度数据集上执行20次，求解最优目标函数，并对所得结果进行对比。经过大量的重复实验，将迭代次数上限均定为400。其中EACS算法将初始参数α、β、ρ分别设置为1、3、0.3，QAACO算法中ρ的上下限分别为0.6和0.1，GA算法中变异概率和交叉概率分别为0.01和0.6。

AHACS算法实验中参数初始化如表1所示。

表1 AHACS参数初始化

统计结果中总体偏差值的计算公式如式(16)所示：

(16)

4种算法在项目调度数据集上分别执行20次，记录的实验仿真数据如表2所示。

表2 实验仿真数据

实验求得最优解的迭代次数如图3所示。由于算法前期拥有较强全局搜索能力时，算法多样性高，解集范围大，在较少的迭代次数内找到较优路径集合的可能性就大。因此由实验结果可知，AHACS算法最早在第24次就找到了最终输出的最优解，收敛速度更快，而GA算法在较少的迭代次数得到的解的质量较差，容易早熟。比较算法的最少迭代次数和平均迭代次数，AHACS算法也同样优于QAACO算法和EACS算法。

20次仿真实验中，AHACS算法最优解出现101和102，找到了另外3种算法没有求得的更优解，说明其拥有更强的全局寻优能力，使得解标准差较其他3种算法更大。无论是从最优解或者是最差解的角度来看，AHACS算法都优于另外3种算法。同时，相比QAACO算法、EACS算法和GA算法，AHACS算法最优解平均值分别提高了1.4%、1.2%和0.7%。相比于QAACO算法和EACS算法，AHACS算法运行20次的总时长分别缩短了20.3%和13.7%。而GA算法在小规模数据集中效果较好[5]，但在本文数据集上会出现编码长、运行时间久的问题，性能较差。因此总体来说，AHACS算法相比于其他3种算法，在优化收敛速度的同时能有效跳出局部最优，成功提高了最终解的质量。

(a) QAACO

(b) EACS

(c) AHACS

(d) GA

3.2 工期不确定MRCPSP问题

第3.1节对MRCPSP问题的研究与仿真以活动工期确定为前提，往往很难与实际情况相吻合。事实上活动工期往往是人为估计的，具有不精确的特点。因此，本文参考模糊理论中的相关概念[25]，采用模糊任务工期的三点估计法以解决MRCPSP问题中的工期不确定问题。

三点估计法是不确定环境下常用的活动工期估计方法，应用概率的方法估算项目完成的乐观工期a、最可能工期m和悲观工期b，随后计算项目工期的估计值和标准差。乐观工期和工期时间之间形成了一个时间缓冲区，这就为项目工期的不确定性预留了时间缓冲，可以作为工期不确定MRCPSP问题最短工时的参考范围。项目工期估计值用me表示，计算方法如式(17)所示：

(17)

为使研究成果更具有普适性，本文放宽了约束条件，不假设活动工期服从特定的概率分布。对于项目调度中每个活动工期不确定的问题，以第3.1节中项目调度数据集的活动工期为中心(基准)，随机生成每个活动的乐观工期和悲观工期，并以二者均值作为活动最可能工期。三点估计法中，可以将区间数看作2点模糊数，表示为a=(amin,amax)，2个区间数的极大值如式(18)所示，2个区间数的极小值如式(19)所示：

max(a,b)=(max(amin,bmin),max(amax,bmax))

(18)

min(a,b)=(min(amin,bmin),min(amax,bmax))

(19)

表3 模糊工期实验仿真数据

4种算法在项目调度数据集上分别执行20次求解工期模糊区间和估计值，分别记录4种算法运行结果工期估计值me的最优值、最差值、平均值和总体标准偏差，以及模糊区间的极大值和极小值。将所记录的实验仿真数据绘制成表，如表3所示。从me的计算结果以及模糊区间数的极大值和极小值来看，在模糊任务工期的情况下，AHACS算法仍能得到比另外3种算法更优的解。

AHACS算法对项目工期的平均工期估计值和根据基准活动工期求得的项目平均工期误差约为1.20%，并且模糊区间最大值和最小值分别为(92,127)和(84,120)，均包含了第3.1节中求得的全部可能的最短项目工期，因此认为使用三点估计法求得的模糊工期估计值和模糊区间数可有效地应对各种不确定因素对项目工期的影响。

4 结束语

针对MRCPSP问题的特点，通过对蚁群算法的学习，本文提出了一种自适应混合蚁群算法(AHACS)，创新参数自适应策略和混合机制，引入信息素上下限的概念，先驱侦查蚁思想和精英蚁群系统排名奖励机制。仿真实验结果表明，改进的AHACS算法能有效平衡解的多样性和收敛速度之间的关系。同时，面对MRCPSP问题中工期不确定的情况，基于模糊理论中的三点估计法求解项目工期估计值和模糊区间，使项目调度更加灵活。分析发现本算法能够较好地解决工期不确定的MRCPSP问题，具备有效性和可行性，因此AHACS算法能够有效地应用到实际问题中，拥有广阔的应用空间。