运用蚁群算法优化项目调度中的折现现金流的方法

摘要

本发明公开了一种运用蚁群算法优化项目调度中的折现现金流的方法。提出的方法用于解决多模式折现现金流的资源约束调度问题(MRCPSPDCF)。首先，建立了MRCPSPDCF的模型，其中除了普通的现金流入和流出外，该模型还会考虑间接成本以及一个奖励和惩罚机制。然后为MRCPSPDCF的模型建立了一个构造图，从而将调度问题转化为一个基于图表的搜索问题。通过运用串行进度生成方法(SSGS)，蚂蚁在构造图中根据信息素和启发式信息一步一步地构造问题的解。算法中综合运用了基于时间和基于费用的启发式信息来引导蚂蚁的搜索。与现有的其它算法相比，本发明的方法在问题的求解中能取得更好的结果。

主权项

1、一种运用蚁群算法优化项目调度中的折现现金流的方法，其特征在于，该方法首先建立了MRCPSPDCF的模型，其中除了普通的现金流入和流出外，该模型还会考虑间接成本以及一个奖励和惩罚机制。然后将MRCPSPDCF的模型转化为该问题的一个构造图，从而将调度问题就被转化为一个基于图表的搜索问题。蚁群算法基于此构造图的搜索步骤包括：(1)初始化算法的各个参数，设构造图上的信息素初值为τ0。(2)蚂蚁根据信息素和启发式信息，通过运用串行进度生成方法(SSGS)构造问题的解。假设蚂蚁当前处于modei，它选择下一个模式modej的公式为其中，q∈[0，1]是一个随机数，q0为选择参数，β是决定启发式信息比重的参数。τil和ηil分别表示从modei到model的有向边edge(i，l)上的信息素和启发式信息。每一步选择完成后，执行局部信息素的更新。假设蚂蚁当前处于modei并且下一步选择了modej，则局部信息素更新的法则由以下公式给出 τij＝(1-ξ)τij+ξτ0 其中，ξ∈[0，1]是一个参数。(3)所有蚂蚁都构造完解后，计算这些解的NPV。工序S的NPV用以下的方程计算 NPV(S)＝fIN(S)-fOUT(S)+fRP(S)其中，NPV(S)表示工序现金流的最终净现值。fIN(S)，fOUT(S)，和fRP(S)分别表示现金流入，现金流出和奖惩金额。而S必须满足优先次序约束和资源约束。(4)当所有蚂蚁都完成解的构建后，执行全局信息素更新以加强最好的工序。只有历史最优解或者当代最优解的边上的信息素才会得到加强其中ρ∈[0，1]是一个参量，ω是一个决定历史最优更新策略和当代最优更新策略运用比例的正整数。Δij bs的取值与NPV(Sbs)有关，表示为${\Delta }_{\mathrm{ij}}^{\mathrm{bs}}=(\frac{\mathrm{NPV}\left(S^{\mathrm{bs}}\right)-\mathrm{first}}{\mathrm{firstBest}-\mathrm{first}}+1)·\psi$ 在上式中，first是指在算法执行过程中找到的第一个可行解的NPV。firstBest是指第一个可行的历史最优解的NPV，firstBest必须大于first。ψ是控制信息素比例的一个参数。同样的，Δij ib也可以用以下公式表示${\Delta }_{\mathrm{ij}}^{\mathrm{ib}}=(\frac{\mathrm{NPV}\left(S^{\mathrm{ib}}\right)-\mathrm{first}}{\mathrm{firstBest}-\mathrm{first}}+1)·\psi$ 如果算法没有找到可行解(first未定义)，那么将不会执行全局信息素更新。如果找到了可行解，但是firstBest没有定义，则设定${\Delta }_{\mathrm{ij}}^{\mathrm{bs}}=\psi$或者${\Delta }_{\mathrm{ij}}^{\mathrm{ib}}=\psi .$ (5)如果达到结束条件，则输出最优工序，否则回到步骤(2)。