基于遗传算法的建筑工程计划管理优化研究

张国富

(滁州职业技术学院 土木工程系，安徽 滁州 239000)

建筑工程计划管理涉及多个紧密相关的任务，人员和设备资源分配的决策会影响项目成本和完成时间[1-2]。诸如关键路径方法(Critical Path Method，CPM)和程序评估与审查技术(Program Evaluation and Review Technique，PERT)之类的传统项目计划方法假定资源的无限可用性。然而在许多建筑环境中，无限制地使用各种资源的假设可能不成立，因为只有固定数量的资源可用，或者获取额外资源的成本非常高[3]。同时，资源的可用性也可能影响活动持续时间，影响决策者对于执行模式的选择。因此，本文在资源有限的情况下，通过设计一种基于遗传算法的计划管理优化模型来平衡工期和成本之间的矛盾。

1 问题建模

建筑工程项目由一系列活动j组成，用G(V,E)表示活动和活动之间的关系。其中，节点集合V表示活动的集合，弧集合E表示优先关系。在项目网络G(V,E)中，活动从0开始编号，第J+1号位置。其中活动0和J+1是“虚拟”活动，用来表示项目的开始和结束。活动之间的优先关系能够约束活动的开始，例如活动j需要在所有先前的活动Pj完成后才开始[4]。用Mj表示活动j的执行模式，当活动的执行模式确定后就不能更改了。假设共有K种可再生资源类型，用Rk表示资源类型k的可用量。在模式m中执行活动j需要花费时间为djm，需要的资源类型集合为Rjm和对资源k的需求表示为rjmk。

本研究的目的是确定一组非支配计划，以减少项目时间和成本为目标，同时满足优先级和资源约束。第一个目标是最小化项目的总工时Ft。在为每个活动选择执行模式后，确定相应的活动持续时间、直接费用和资源需求。然后将活动模式信息输入到多模型的第二阶段。搜索引擎将遗传算法与进度表生成方案集成在一起，以搜索最佳的序列，从而根据给定的约束为所有活动生成可行的进度表。

第二个目标是将总项目成本FC降至最低。项目成本分为直接成本和间接成本，其计算方式为FC=∑j∑mxjmcjm+fjci。直接成本(即∑j∑mxjmcjm)与项目活动的执行直接相关，并与项目资源的可用性密切相关。其中，cjm是活动j以模式m执行的直接成本，xjm是决策变量。间接成本(即fjci)与项目活动的执行无关。在这项研究中，假设每个时期的间接费用是固定的(即ci为常量)，而一个项目的总间接费用取决于项目工期fj。项目的总直接成本是活动执行成本的总和，直接费用总额取决于所选的执行模式。

2 基于遗传算法的优化模型

2.1 算法概述

本优化模型采用一种基于种群的算法，通过进行直接搜索解决全局优化问题[5]。该算法简要描述如下：

令S⊂R为问题的搜索空间，向量Xi,G为种群。初始种群是随机生成的，并且覆盖整个参数空间。在每一代中，算法应用两个算子(突变和交叉重组)为每个目标向量Xi,G产生一个试验向量Ui,G+1。然后，选择阶段确定试验向量是否进入下一代。使用以下公式为每个目标向量Xi,G确定一个突变向量Vi,G+1：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G

(1)

其中，r1、r2和r3是从种群中随机选择的个体，F是比例因数，取值范围是0到1。

在突变阶段之后，采用交叉算子来增加种群的多样性。对于每一个突变向量Vi,G+1，其对应的试验向量Ui,G+1中的元素按照以下规则生成：

(2)

其中，CR是自定义的交叉常数，其取值范围是0到1。jrand是从种群中随机选择的个体索引。

为了确定是否将试验向量Ui,G+1加入到下一代种群中，使用贪婪算法将该向量与其对应的目标向量Xi,G进行比较。选择算子表示如下：

(3)

算法的进化循环将反复进行，直到满足停止条件为止。

2.2 基于混沌技术的初始化

本研究同时优化了项目成本和项目工期。在优化之前，该模型需要项目信息输入，包括活动关系、每天的可用性资源、活动持续时间、成本、资源类型以及每个活动的执行模式。另外，还需要对以下的参数进行设置：种群大小NP、决策变量的数量D、目标函数的数量K、突变常数F和交叉概率常数CR。

种群初始化是进化算法中重要的一个步骤，结合均匀随机分布和混沌技术生成初始种群。

(4)

在使用混沌生成个体之后，选择NP个最佳的解决方案，并将其输入到模型的主循环中。可以将问题的候选解决方案表示为具有D个元素的向量，即xi=[Xi,1,…,Xi,D]。向量Xi,j表示活动j的一种执行模式，索引i表示种群中的第i个个体。执行模式Xi,j的取值范围是[1,Mj]。使用一个函数将那些活动的执行模式选项从实际值转换为可行域内的整数值，即

Xi,j=ceil(rand[0,1]×UB(j))

(5)

其中，rand[0,1]是0到1之间的随机数，UB(j)是活动j的执行模式的数量。ceil是向上取整的函数。

采用快速的非支配排序技术将种群分类为非支配集合(F1,F2,…)。选择属于最佳非支配集合(集合F1)的解，并将其输入到种群中。如果F1小于NP，则按照排序将其它非支配解(F2,F3,…)加入到种群。假设Fk是最后一个加入的非支配的集合。通常，集合F1,…,Fk中解的数量会大于NP。因此使用熵排序技术选择最佳NP个种群成员。

2.3 突变和交叉操作

初始化后，算法对种群进行突变操作。突变向量Vi,G+1的生成公式如下所示：

Vi,G+1=Xr1,G+F(Xr2,G-Xr3,G)

(6)

为了提升算法的收敛速度，选择适应度最高的向量作为突变操作的基向量。

针对算法的三个阶段设计了三种选择机制：

(1)g≤ms×Gmax：采用随机选择机制，在种群中随机选择Xr1、Xr2和Xr3。在进化过程的开始，所有用于突变的个体都是随机选择的，随机选择可以确保种群的多样性。

(2)ms×Gmax

(3)g>2×ms×Gmax：在优化过程的最后阶段，算法必须加速收敛。用于突变的所有向量Xr1、Xr2和Xr3均是适应度值较高的个体。

其中：ms是突变选择系数，Gmax是最大迭代次数。

交叉操作交换目标向量和突变向量的元素，使种群多样化。把交叉操作得到的向量称为后代向量，如下所示：

(7)

2.4 资源受限子系统

后代向量首先定义每个活动的执行模式，然后确定相应的成本、持续时间和资源需求。将执行模式信息输入到资源受限的子系统中，该子系统将基于给定的约束条件生成可行的时间表。在资源受限的子系统运行之前，随机均匀分布生成器会创建包含M个个体的初始种群。资源受限问题的解决方案是一个具有D个元素的向量，即Xs=[Xs1,…,XsD]。其中D是当前问题中决策变量的数量，同时也是项目网络中的活动数量。

将基于优先级的调度与串行转换方案相结合，针对资源受限的项目调度问题，设计遗传算法中个体的编码表示方式。作为D维空间中的一个点，DE个体中的第D个元素可以表示项目中的D活动。向量Xs(t)中的D个参数{xs1(t),…,xsD(t)}表示D个活动的D维优先值。对向量中的元素按照其优先值排序，得到新的向量。

串行方法包含n个阶段，每个阶段中选择一项活动进行调度。当一项活动的当前可用资源量足够时，该活动将会在最早的优先时间被调度。所设计的串行方法如下所示：

步骤1：根据优先级约束将个体优先级转移到活动计划中。假设项目活动集合为j={1,2,…,n}。用集合C={(i,j)}表示集合J={1,2,…,n}中活动的优先级关系，其中(i,j)表示活动i必须在活动j之前执行。引入二元关系矩阵V=(vij,1≤i,j≤n)：当(imj)∈C时，vij=1；否则vij=0。同时引入优先级关系矩阵G=(gij,1≤i,j≤n)来描述所有优先级关系链：当(k,k1),(k1,k2),…,(kj-1,kj)都属于集合C，那么有gkj=1。因此，可以根据集合C来构建矩阵G。

步骤2：根据活动时间表计算项目工期。在应用串行方法之前，必须考虑两个重要点：首先，活动A在所有前继活动完成后开始；其次，活动开始时间取决于资源的可用性。因此，当活动A的前继活动完成后且有足够的资源时，活动A立刻会被执行。

2.5 精英库更新

项目总工期和每个执行模式的成本会被输入到子系统以进行评估。多目标优化的一个重要步骤是选择机制，采用基于帕累托支配的选择机制。该选择机制首先评估后代向量Ui,G，然后将该向量与目标向量Xi,G进行行比较：当Xi,G支配Ui,G，则将Ui,G丢弃；当Ui,G支配Xi,G且Xi,G=Ui,G，更新外部精英库；对于其他情况，采用熵排序选择个体。

在选择操作过程中选择的向量称为选择向量。如果所有精英库个体都支配选择向量，则不将选择向量加入到精英库中。如果选择向量支配一个或多个精英库成员，则删除该精英库成员，并将选择向量加入到精英库。

当算法满足停止条件时，优化过程终止。一个停止条件是最大迭代次数Gmax，即算法迭代次数达到Gmax，算法就停止。另一个停止条件是最大评估次数，即适应度函数的计算次数。在优化过程终止后，就会输出一组最佳的解决方案。

3 实验评估

采用案例来评估本方法的有效性，并将本方法获得的结果与通过多目标差分进化算法(MODE)和非支配排序遗传算法(NSGA-II)的结果进行比较。实验采用MATLAB R2020a仿真平台，实验在工作站上进行，该工作站的配置为：CPU采用Intel 酷睿i7-10700 5.3 GHz，内存的大小为16 G，硬盘容量为256 G SSD + 1 T 机械硬盘。实验采用了一个仓库建筑工程的案例数据来验证本文算法。该案例一共有37个活动，各个活动之间的优先级关系如图1所示。案例数据中，每项活动的属性包括了活动序号、活动的具体描述、工期、前继活动以及成本，部分活动的时间成本如表1所示。

图1 活动优先级图

表1 部分活动的信息

分别将本文算法、MODE算法和NSGA-II算法运行20次，并取平均值。分别从三种算法所获得的帕累托前沿中选取较好的结果，并将结果呈现在表2中。

表2 三种算法结果对比

由表2可知，解决方案1的工程总成本是最高的，但其工期是最短的；而解决方案3的工期较长，成本却是最低的。对比三种算法的结果可知，相同工期的情况下，本算法能够获得最低的成本；而当成本相近时，本算法的工期是最短的。由此可知，本算法能获得最佳的综合性能。

4 结论

本研究提出了一种基于遗传算法的优化模型，以解决资源受限的建筑工程计划管理问题，实现了工期和成本的均衡。该模型生成的帕累托最优解有助于决策者在项目时间和成本限制下做出最佳工程计划。实验结果表明，本模型可以有效地解决计划管理问题，并可以找到多目标帕累托最优解。拟议的模型使决策者能够根据时间和成本偏好作出及时、知情的决定。未来的工作集中在将本模型应用于更多的实际案例中，以进一步评估本模型的性能。