基于间隔率和遗传算法的多资源均衡优化研究

欧阳红祥，陈伟伟，李 欣

(1.河海大学 商学院，江苏 南京210098;2.中石化集团管道储运分公司 南京输油处，江苏 南京210046)

资源优化有两类问题，一类是资源有限工期最短问题，另一类是工期固定资源均衡问题。工期固定资源均衡问题按涉及的资源种类数，可分为单资源和多资源均衡问题。工期固定资源均衡问题理论上属于组合优化问题，目前解决这类问题常用的方法有解析式法、启发式算法及智能优化算法［1］。解析式算法只适用于较小规模、较少资源的优化。启发式算法可以求解大规模资源均衡问题，但由于其优化准则、算法都与特定的问题有关，因此算法的可移植性和通用性较差［2］。智能优化算法主要包括遗传算法、模拟退火算法、蚂蚁算法，以及神经网络等。遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他方法相比，其具有自行概率搜索、运算并行性，以及搜索效率高等优点［3］，因此许多学者借助遗传算法来求解资源均衡问题，并取得了丰富的成果。在以往的许多研究中，学者们往往基于项目各作业的开工时间进行编码，这种编码方式容易导致在求解过程中产生不满足作业间逻辑关系约束的非可行解。目前解决的办法有两种：一是通过修复算子对不满足作业间逻辑约束的非可行解进行修复;二是通过特定的编码方式来避免求解过程中产生违反作业间逻辑关系约束的非可行解［4］。相比较而言，后一种办法效率更高。基于此，笔者提出了一种基于间隔率的编码与解码方法，可以避免在交叉、变异等遗传操作中出现违反作业间逻辑关系的情况，从而大大提高遗传算法解决该类问题的寻优速度。

1 多资源均衡优化模型

1.1 假设和定义

假设1 各项活动在优化过程中是不可拆分的，其持续时间是固定的;各项活动所需资源种类数和数量在优化过程中保持不变。

假设2 在优化过程中，项目的总工期不变，并且在任一时间段内，各种资源的供应量足够多，可满足需求。

定义1V={1，2，…，N}为网络计划中所有活动的集合，Di和LSi为活动i的持续时间和最迟开始时间，Pred(i)为由活动i的紧前活动组成的集合，Si和Fi分别为活动i的计划开始时间和计划完成时间。为满足既定的逻辑关系和总工期不变的要求，Si∈［max(Fh)，LSi］，其中，h∈Pred(i)，i∈V。活动i的计划开始时间的取值范围如图1 所示。

定义2 称PFi为间隔率，PFi= (Si-max(Fh))/(LSi-max(Fh))。从图1 可以看出，0≤PFi≤1。若PFi=0，则表示活动i的计划开始时间与紧前活动h的计划完成时间相等，也即活动h按计划完成后，活动i立即开始。若PFi=1，则意味着活动i的计划开始时间与其最迟开始时间相等。

定义3 假如某一项目需要K种资源(如材料、设备等)，第i项活动单位时间内所需第k种资源数量记为项目总工期记为T，第t时刻项目所需第k种资源数量记为

图1 活动i 的计划开始时间的取值范围

1.2 优化模型描述

多资源均衡优化的目标是寻找各项活动的计划开始时间，使得在项目总工期内各种资源需要量尽可能均衡。用于评价资源均衡效果的指标主要有不均衡系数、方差、最大绝对离差和极差值这4 种［5-6］。由于方差更能体现项目在各时刻资源需求的不均衡程度，因此，笔者选择该指标用于评价资源需求均衡程度。

假如第k种资源需求的方差用δ(k)表示，则：

对于多资源均衡问题，由于资源的重要性有所差别，因此可采用不同的权重系数来反映其对目标函数的影响程度。为消除不同资源在数量等级、单位等方面的差异，需要对资源量进行标准化处理［7-8］。对数据进行标准化处理的方法有很多，笔者采用极小-极大化方法。设为第k种资源需要量的最大值，则若用表示第k种资源需要量的最小值，则第t时刻项目所需第k种资源数量经过极小-极大化变化后变成为可按式(3)进行计算。

第k种资源需要量的平均值¯R(k)经过极小-极大化变化后变成¯R(k)'，则：

通过上述变换后，各种资源需要量的取值都在区间［0，1］内，并且变成了一个无量纲的数，从而消除了资源在数量级、单位等方面对目标函数取值的影响。

综上所述，多资源均衡的目标函数可定义为：

约束条件为：

式(5)中，ω(k)为选定的一组权系数，满足，其他符号同前。

2 遗传算法

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它最早由美国密执安大学的HOLLAND 教授提出。20 世纪70 年代JONG 基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算实验，在一系列研究工作的基础上，20 世纪80 年代由GOLDBERG 进行归纳总结，形成了遗传算法的基本框架。遗传算法的基本运算过程如下［9-10］：

(1)初始化。令进化代数计数器t=0，最大进化代数为T，随机生成M个个体作为初始群体P(t);

(2)个体评价。计算群体P(t)中各个个体的适应度;

(3)选择运算。通过选择运算选出最优的个体直接遗传到下一代;

(4)交叉运算。通过配对交叉产生新的个体;

(5)变异运算。将个体串中某些基因座上的基因值作出变动;群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)。

(6)终止条件判断。若t=T，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

3 算例

某网络计划如图2 所示，箭头线上方的数字表示活动所需资源数量(假设项目中所有活动使用两种资源)，箭头线下方的数字表示活动的持续时间(时间单位为天)，假定两种资源的权重分别为0.7和0.3。

图2 活动所需资源数量

3.1 计算活动的时间参数

根据给定的网络计划，采用关键线路法(critical path method，CPM)计算各项活动的最早开始时间(ES)和最迟开始时间(LS)。

3.2 浮点数编码

考虑到资源均衡优化目标函数和约束条件的复杂性，笔者采用浮点数编码方法。以各项活动的间隔率(PF)作为决策变量，个体的每个基因值用区间［0，1］内的一个浮点数来表示。各项活动的浮点数编码如表1 所示。由间隔率的定义可知，可行解集合{PFi}对应唯一的计划开始时间序列S。

表1 浮点数编码

3.3 染色体解码

染色体解码的实质是将各活动的间隔率转换成对应的计划开始时间。解码的规则如下：

3.4 选择运算

笔者采用轮盘赌选择法来选择遗传个体。其基本思想是：各个个体被选中的概率与其适应度大小成正比。具体过程为：①先计算出群体中所有个体的适应度总和;②计算每个个体的相对适应度大小，即为该个体被遗传到下一代的概率;③使用模拟赌盘操作(即0 到1 的随机数)来确定各个个体被选中的次数。

3.5 交叉运算

笔者采用单点交叉算子，具体执行过程如下：①对群体中的个体进行两两随机配对;②随机设置交叉点位置;③依预先设定的概率(p=0.8)，互换交叉点后的基因值，形成两个新的个体。

3.6 变异运算

采用均匀变异算子，具体操作过程如下：①指定个体编码串中的某个基因座为变异点;②依预先设定的概率(p=0.05)从对应基因的取值范围［0，1］中随机取一数值代替原数值。

3.7 运算结果

利用Matlab 7.0 提供的遗传算法工具箱，结合具体问题编制相应的适应度函数、选择函数、交叉函数和变异函数，优化运行过程经过51 代，其适应度函数值下降到3.201。优化后各项活动的计划开工时间如表2 所示。各资源需求量优化前后的对比如图3 和图4 所示。资源1 的方差由37.7 下降到2.8，资源2 的方差由7.71 下降到4.14。

表2 各项活动计划开工和完工时间 天

图3 第1 种资源优化前/后需求量对比

图4 第2 种资源优化前/后需求量对比

4 结论

遗传算法是一类具有较好鲁棒性的搜索算法，由于其模型简单、易于实现、无需梯度信息和参数少等特点使其在组合优化问题中显示出良好的求解效果。笔者将遗传算法引入到资源均衡优化问题中，建立了基于间隔率的资源均衡优化模型，从而避免了在优化过程中容易产生无效解的情况，大大提高了优化效率。在此基础上，叙述了算法流程，并通过算例证明所引入的算法具有一定的可行性和有效性，为工程项目实施中的资源安排提供了一种新的思路和方法。同时，研究过程也表明，优化结果与参数的选择有很大关系，因此，如何融合其他算法对现有模型进行改进，使其具有更好的全局收敛性，还有待进一步研究。

［1］HARRIS R B. Packing method for resource leveling［J］. Journal Construction Engineering and Management，1990，116(2)：331 -350.

［2］谢洁锐，黄忠民，俞守华，等. 一种“工期固定，资源均衡”的神经网络模型设计［J］. 计算机应用与软件，2005，22(1)：66 -68.

［3］骆刚，刘尔烈，王健.遗传算法在网络计划资源优化中的应用［J］.天津大学学报，2004(2)：179 -183.

［4］LEU S S，YANG C H，HUANG J C. Resource leveling in construction by genetic algorithm- based optimization and its decision support system application［J］.Automation in Construction，2000(10)：27 -41.

［5］TAREK H. Optimization of resource allocation and leveling using genetic algorithms［J］.Journal of Construction Engineering and Management，1999(3)：167-175.

［6］张淑山，张连营. 建设项目多资源优化的进化算法实现［J］.科技进步与对策，2009(11)：88 -90.

［7］张连营，张金平，王亮.工程项目资源均衡的遗传算法及其Matlab 实现［J］.管理工程学报，2004(1)：52-55.

［8］王首绪，周学林.遗传算法优化施工网络计划的多种资源均衡［J］.重庆交通学院学报，2001(6)：39-45.

［9］玄光男，程润伟.遗传算法与工程设计［M］. 北京：科学出版社，2000：43 -98.

［10］雷英杰. Matlab 遗传算法工具箱及应用［M］. 西安：西安电子科技大学出版社，2005：65 -98.