混合蛙跳算法在TCRO问题中的应用

摘  要：遗传算法和粒子群算法等进化算法（EAs）因其适用性被用于开发过去二十年来的多目标时间-成本资源优化（TCRO）。比较混合蛙跳算法与现有群智能算法对可分裂的TCRO问题的解决，结果表明，混合蛙跳算法比现有的群智能优化算法在寻找更好的项目进度解决方案方面具有更高的优势，其总项目成本更低，项目总项目时间更短，资源分配的总体变化或资源分配的总时间利用更少。

关键词：SFLA;TCRO;群智能算法

中图分类号：TP301.6;TP212      文献标识码：A 文章编号：2096-4706（2020）18-0007-07

Abstract：Evolutionary algorithms （EAs），such as genetic algorithm （GA）and particle swarm optimization （PSO），have been used to develop multi-objective time-cost resource optimization （TCRO）in the past 20 years. This paper compares the hybrid frog leaping algorithm with the existing swarm intelligence algorithm in solving the divisible TCRO problem. The results show that，compared with the existing swarm intelligence optimization algorithm，the hybrid frog leaping algorithm has higher advantages in finding a better project schedule solution. The total project cost is lower，the total project time is shorter，the overall change of resource allocation or the total time utilization of resource allocation are less.

Keywords：SFLA;TCRO;swarm intelligence algorithm

0  引  言

建設项目规划最具挑战性的任务之一就是在考虑最优资源配置和资源平衡有关的问题同时，最大限度地减少总项目成本和项目总时间。因此，项目规划者面临着复杂的多变量——时间、成本、资源优化的（TCRO）问题，需要进行时间—成本—资源权衡分析。项目总时间和成本的一个重要因素是延迟，延迟是延长完成合同下活动所需时间的事件，如果一个项目延期到期，那么承包商会承担罚款。如果活动的进行或者延迟时间长于总浮动时间，则会延迟项目总时间。如果在活动执行期间发生延迟，在此将其称之为“允许拆分”，它影响活动的总时间，但活动的活动时间不会改变。拆分可能由于以下原因而发生：

（1）天气变化。

（2）预算不足（或其他财务问题）。

（3）未预见的人力问题。

（4）资源限制（机械，人力等）。

（5）非工作日（周末，节假日）。

（6）活动的性质，例如混凝土固化等内部活动不能连续完成。

因此，关键问题是如何在考虑分裂的情况下为活动分配资源，以便从承包商、赞助商和项目客户的角度按时完成项目。现行方法的主要目标是：通过中断项目活动并在项目活动中调动资源来实现更好的项目计划和资源平衡，从而实施“拆分允许”。本文作者从2008年开始研究群智能算法问题，长春工程学院以土木工程专业见长，但是TCRO始终是工程类专业难以解决的问题。本人读博士期间对比不同算法在TCRO问题中的应用结果，应用混合蛙式跳跃算法（SFLA）来实现更好的TCRO模型的项目进度解决方案。

1  问题建模

考虑一个典型的由N个相关活动组成的项目计划问题：A1，A2，…，AN有限的活动选择来分配S个类型的项目资源R1，R2，…，RS来执行活动;每个选项代表不同资源的数量以及完成活动的相应时间和成本。假设Oij代表项目策划者可以从成本j中选择以执行活动i=1，2，…，N的整个可行选项集合。

该集合属于可行时间，总项目成本，可执行活动资源，其中，T为时间Time，C为成本Cost，R为资源Resource。

在允许分裂的情况下，本文假设λij为分配活动的待续时间，每个活动Ai：=Ti：分配活动持续时间，分裂仅适用于TCRO模型的最终结果得到改进的活动。如果活动的可能占用位置被确定，则每个位置被分配一或零天（λ的值），这些位置的总和必须等于该活动的持续时间。举一个例子，图1为在不分裂的情况下占领活动i的位置，其中Total Float为总浮动时间，Duration为持续时间，图2为在分裂的情况下占领活动i的位置，其中Split为分裂，在图1和图2中使用方程（1）：

项目规划人员的问题是如何分配项目资源并安排活动，以尽量减少总项目成本和项目总时间，同时保持每日资源限制。因此，项目规划者在这个优化问题中的决策变量是：

解决方案的顺序应与活动之间优先关系中的活动顺序一致，每个解决方案都包含基于所选不同活动选项的一个项目的信息，包含非关键活动的解决方案是使用拆分的候选对象。所以，根据每位候选对象的项目活动总量和自由流通量，应用分裂来获得更好的解决方案，以得到最短的项目总时间、最低的总项目成本和资源分配。此外，在资源有限的情况下，资源平衡条件应该在模型中得到满足。

1.1  目标函数

项目规划者在TCRO问题中的目标函数可以表述为同时最小化总项目成本、总项目时间和资源分配，总结如下：

Z1为最小化总项目成本（TC）：总项目成本包括执行项目活动的总直接成本和完成项目的间接成本。

Z2为最小化总项目时间（TD）：项目的总项目时间是完成关键路径上关键活动所需的时间。

上面提到的目标和以下的资源分配目标之一是优化模型的三个目标函数：

Z3为最小化资源分配的总体变化：衡量资源分配变化的最常见指标之一是每日资源的平方和（SSR）。项目规划者应该尽量减少这一资源时刻，以实现更好的资源调配：

其中，n为每日资源数。

Z4为最小化资源分配的总时间利用率：资源利用率高的时间段和资源的晚期释放时间可以增加这个资源时刻的价值，这适合于最小化建筑项目中连续和昂贵的消耗资源，例如机械。项目计划人员可以通过测量资源消耗（SPD）的日常资源产品和日期（因为项目分裂导致项目开始日期为多个，所以要综合每个开始日期的进行时间）的总和来消除特定资源的开支：

其中，资源nk为在总项目时间的第k天计划使用的资源nk的数量：n=1，2，…，TD，X为单个资源时间利用率。

1.2  模型的约束

建筑项目规划中的TCRO问题受到以下若干限制：

（1）项目活动网络图中所示的项目活动之间的逻辑或物理依赖关系。项目活动之间的开始—开始、开始—结束、结束—开始以及结束—结束关系必须作为活动开始日期SD1，SD2，…，SDN和总项目时间T1，T2，…，TN的适当限制来捕获。由于本文只有“结束—开始”活动之间的关系，以下约束排除了后续项目在上一个活动开始之前已经开始的情况，即考虑一个解决方案中所有活动的TF和FF。在允许分裂的情况下应满足以下约束条件：

其中，m为分裂出的项目个数。

非关键活动k具有前任活动p，p项活动的持续时间为3天，FFp是1天，TFp是4天，TFk是4天。λp1，λp2，λp3和λp4的值不会影响任何λkj的值，其中j=1，2，…，7是因为在该时间段内活动p和k没有重叠。然而，λp5，λp6和λp7的值对λkj的值有影响，其中j=1，2，3，因为潜在的重叠和p在k之前的要求。例如，如果λp5是1，λk1必须是0才能维护关系逻辑。如果λp6为1，则λk1和λk2必须为0。如果λp7为1，则λk1，λk2和λk3必须为0，如图3所示。

这个例子的约束条件可以表示为：

（2）（任何）资源总量的（任何）限制：整个项目活动中特定资源的总消耗量不得超过项目期间任何时间点该资源的能力。

接下来，本文介绍一种混合蛙跳算法（SFLA）算法来解决这个允许在建设项目规划中进行活動分裂时间—成本—资源优化（STCRO）问题。

2  SFLA算法在施工项目规划中的应用实例

混合蛙式跳跃算法（SFLA）将粒子群算法（PSO）作为本地搜索工具和混合复杂进化算法（SCE）作为并行局部搜索的信息的操作符，算法能实现更快的收敛速度并获得更好的Pareto最优解。SFLA是Eusuff和Lansey在2003年提出的一种元启发式迭代方法，它启发于寻找食物时一群青蛙的模因进化。SFLA不使用遗传算法中的基因，而是使用模因子来提高对Pareto前沿解的传播和收敛比。基因和模因之间的主要区别与其传播能力有关，基因只能在无性繁殖的情况下由父母或父母传播给后代，而模因可以在任何两个人之间传递。

SFLA优化算法基于在大范围可行解空间的广泛扫描生成解决方案，同时深入搜索有前途的位置以获得全局最优。整个解决方案分布在称为memeplex的不同子集内，memeplex分区过程如图4所示，其中，nd为第几轮迭代即方案的迭代数，th为第几个模因。

每个memeplex都与PSO操作员进行独立的本地搜索，在搜索每个解决方案时可能会受到其他解决方案的影响，并通过模因演化的方式发展。经过一定数量的演化步骤之后，解决方案在memeplexes之间进行混合，使解决方案能够在不同活动之间交换可行的选项，并确保它们移动到最佳位置。局部搜索和混洗过程一直持续到定义的收敛标准得到满足。

本文将Eusuff和Lansey的SFLA算法用于解决TCRO优化问题，本文在建设项目规划中进行分裂。算法由以下步骤组成：

（1）设置解决方案k=1，初始化一组可行的项目进度解决方案：该初始人口集由m×n项目进度表解决方案组成，其中m是memeplexes的数量，n是每个memeplex中解决方案的数量。从考虑项目活动之间的逻辑关系和时间关系的角度，活动是从可行的开始日期和时间—成本—资源分配（以及允许分裂的情况下的自由流通量和总浮动时间）中随机抽取的。

（2）将解决方案划分为  ，解决方案的总体划分为许多并行社区（memeplexes），这些社区允许独立进化，以在不同方向上搜索解决方案空间。

（3）在每个可行项目进度计划选项  中，计算每个可行项目进度计划选项的优化目标函数值：总项目成本（Z1）、总项目时间（Z2）以及资源分配总量（Z3）或资源分配总时间利用率（Z4）。

（4）从可行集合中消除主导的项目进度解决方案 ：主导解决方案是相应成本、持续时间和资源变化大于或等于可行集合中另一可行解决方案的各自的总项目成本、持续时间和资源变化的解决方案，删除主导的项目进度表选项并更新每个  中的项目进度表解决方案。

（5）分别计算更新的  中Z1、Z2和Z3或Z4中某一个的剩余项目进度表解决方案的平均总项目成本、平均总项目时间和资源分配的平均总变化量。

（6）对于  中的每个总项目时间表选项，计算三维客观空间中距离原点的归一化距离D：

（7）从最大距离到最小距离订购  中的总项目时间表选项（在SCE中应用洗牌算子，该算法由Eusuff和Lansey在2003年首次提出）。

（8）在  发展之后，算法返回全局洗牌研究（在PSO中应用移动算子，该算法由Zhang等人在2006年提出），并更新总体中P（k）中最佳解决方案的位置。这些（新）解决方案也属于由P（k+1）表示的下一代人口集的项目进度计划选项。

（9）重复步骤（2）到步骤（8），直到执行步骤（7）和步骤（8）不能找到新的项目进度表解决方案，即当下一代人口组的项目进度计划选项等于当前的一组项目进度计划选项时。

图5演示了SFLA的流程图。接下来，本文将演示如何使用所提出的SFLA算法来解决建设项目规划中的TCRO问题，并将结果与现有的优化算法进行比较。pb为解决方案i中的最佳解决方案;pg为当前人口的全局最佳解决方案;ω为惯性重量。

3  案例分析

第一个案例是一个如表1所示的七个相互关联的活动组成的项目。本项目使用了七种资源类型R1，R2，…，R7，包含范围从50美金到4 000美金的固定单位成本;项目总共有80个选项用于使用不同资源配置的项目活动。例如，表1显示了执行活动1的11个时间配置，直接成本和资源分配。此外，该项目的间接成本假定为每天1 500美元。郑等人在2004年使用遗传算法来解决这个项目计划问题并找到最优的项目进度解决方案;Zahraie和Tavakolan在2009年重新回顾了这个问题，并应用NSGA-Ⅱ演化算法找到项目进度解决方案的Pareto最优前沿。本文将SFLA算法应用于此项目规划问题的分裂，以找到项目进度解决方案的Pareto最优前沿，然后将本文的解决方案与允许分裂前后的算法的结果进行比较。

首先，本例中的项目规划目标只考虑同时最小化总项目成本和总项目时间，未考虑最小化资源变化。图6、图7展示了项目进度计划解决方案，该项目进度计划解决方案是在总项目成本和总项目时间在二维空间中的TCRO问题的Pareto最优前沿以及允许分裂之前和之后的对比。SFLA方法能够找到具有较低总项目成本和总项目时间的项目进度表解决方案，这是以前的算法没有找到的。尤其是项目进度计划解决方案的总项目时间较短（即64天），项目进度计划解决方案的总项目成本较低（即226 300美元）;允许项目分裂SFLA算法中项目期限最短（即62天），找到了允许分裂后的最低总项目成本（即225 450美元），另外，可以用SFLA寻找到额外的最佳项目进度解决方案。其中，总资源变化配比为总资源在可分裂问题中的资源配比，总资源配比其具体含义理解为（每天资源数量）2。

图8展示了各算法（NSGA-Ⅱ方法、允许分裂之前的SFLA算法和允许分裂后的SFLA算法）总项目的三维空间中的最佳项目进度解决方案中的总项目成本、总项目时间和资源配比的总时间利用率。图8（a）是NSGA-Ⅱ方法下总项目成本、总项目时间和资源配比的总时间利用率;图8（b）是允许分裂前SFLA下总项目成本、总项目时间和资源配比的总时间利用率;图8（c）是允许分裂后SFLA下总项目成本、总项目时间和资源配比的总时间利用率。

将对本文所用的SFLA算法与NSGA-Ⅱ算法进行比较，考虑同时最小化总项目成本、总项目时间和资源分配的总变化。图7（a）、（b）和（c）展示了项目目标三维空间中Pareto最优前沿的项目进度解决方案的项目总项目成本、项目总时间和资源分配总变化，这些数据分别由Zahraie和Tavakolan提出的NSGA-Ⅱ算法以及在允许分裂后SFLA算法得到。由于其中一个资源时刻（Z3或Z4）被认为是Z1和Z2作为TCRO模型的目标函数，所以在项目目标的三维空间中可以看到相同的方法。

为更好地比较这两种算法在项目规划目标的二维空间中得出的最优项目进度计划解决方案，引入第二个例子，第二个例子包括了18个活动。用图9展示了在不同案例下总项目时间和总资源变化配比。可以看出，研究中提出的允许分裂的SFLA算法能够找到最短总项目时间的解决方案，具有最短的总项目时间、最低的总项目成本和较少的资源分配总变化。

4  结  论

综上所述，在可分裂的TCRO问题中，使用蛙跳算法能够以较低的总项目成本、总项目时间以及分配前后资源分配总时间利用率，来寻找额外的最佳项目进度解决方案。此外，本文提出的算法也加快了解决建设项目规划中TCRO问题的计算速度，与其他已经用于该问题中的群智能的优化方法相比，本文的方法将解决方案处理时间减少了2.71倍。

参考文献：

[1] 陈东宁，刘一丹，姚成玉，等.多阶段自适应蝙蝠-蚁群混合群智能算法 [J/OL].机械工程学报：1-15（2019-12-04）.http：//kns.cnki.net/kcms/detail/11.2187.TH.20191202.1845.016.html.

[2] BRANKE J，NGUYEN S，PICKARDT C W，et al. Automated Design of Production Scheduling Heuristics：A Review [J]. IEEE Transactions on Evolutionary Computation，2016，20（1）：110-124.

[3] 郭梽煒，黄雄峰，翁杰.基于改进正交优化群智能算法的分布式电源规划 [J].三峡大学学报（自然科学版），2018，40（1）：59-63.

[4] PONSICH A，JAIMES A L，COELLO C A C. A Survey on Multiobjective Evolutionary Algorithms for the Solution of the Portfolio Optimization Problem and Other Finance and Economics Applications [J]. IEEE Transactions on Evolutionary Computation，2013，17（3）：321-344.

[5] 赵新超，刘国莅，刘虎球，等.基于非均匀变异和多阶段扰动的粒子群优化算法 [J].计算机学报，2014，37（9）：2058-2070.

[6] BUMGARNER D J，WEBB J R，DULA C S. Forgiveness and adverse driving outcomes within the past five years：Driving anger，driving anger expression，and aggressive driving behaviors as mediators [J]. Transportation Research Part F：Traffic Psychology and Behaviour，2016，42（4）：317-331.

[7] BOGDAN S R，M?IREAN C，HAV?RNEANU C E. A meta-analysis of the association between anger and aggressive driving [J]. Transportation Research Part F Traffic Psychology and Behaviour，2016，42（4）：350-364.

[8] 贾瑞玉，宋建林.基于聚类中心优化的k-means最佳聚类数确定方法 [J].微电子学与计算机，2016，33（5）：62-66+71.

[9] 张敬磊，王晓原，王梦莎，等.三车道动态环境下汽车驾驶倾向性的转移概率及其预测 [J].交通运输系统工程与信息，2017，17（1）：82-90+97.

[10] 张敬磊，王晓原，王云云，等.驾驶任务缓急与汽车驾驶倾向性的相关性 [J].深圳大学学报（理工版），2017，34（2）：195-203.

[11] LIU A J，LIU H Y，TSAI S B，et al. Using a Hybrid Model on Joint Scheduling of Berths and Quay Cranes—From a Sustainable Perspective [J]. Sutainability，2018，10（6）：1959.

[12] HOMAYOUNI S M，TANG S H，MOTLAGH O.A genetic algorithm for optimization of integrated scheduling of cranes，vehicles and storage platforms at automated container terminals [J]. Journal of Computational and Applied Mathematics，2014，270（5）：545-556.

[13] MOUSAVI M，YAP H J，MUSA S N，et al. A Fuzzy Hybrid GA-PSO Algorithm for Multi-Objective AGV Scheduling in FMS [J]. International Journal of Simulation Modelling，2017，16（1）：58-71.

[14] XIANG W L，LI Y Z，MENG X L，et al. A grey artificial bee colony algorithm [J]. Applied Soft Computing，2017（60）：1-17

[15] CHEN Y P，WANG S D，HAN W D，et al. A New Air Pollution Source Identification Method Based on Remotely Sensed Aerosol and Improved Glowworm Swarm Optimization [J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing，2017，10（8）：3454-3464.

[16] HE J，YAO D. A nonlinear support vector machine model with hard penalty function based on glowworm swarm optimization for forecasting daily global solar radiation [J]. Energy Conversion and Management，2016（126）：991-1002.

[17] CHEN X，ZHOU Y Q，TANG Z H，et al. A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical travelling salesman problems [J]. Applied Soft Computing，2017（58）：104-114.

[18] DING S F，AN Y X，ZHANG X K，et al. Wavelet twin support vector machines based on glowworm swarm optimization [J]. Neurocomputing，2016（225）：157-163.

[19] 毛肖，和丽芳，王庆平.基于改进萤火虫优化算法的多阈值彩色图像分割 [J].計算机科学，2017，44（S1）：206-211.

[20] KANG S M，KIM M H，CHAE J J. A closed loop based facility layout design using a cuckoo search algorithm [J]. Expert Systems with Applications，2018（93）：322-335.

[21] BOUSHAKI S I，KAMEL N，BENDJEGHABA O. A New Quantum Chaotic Cuckoo Search Algorithm for Data Clustering [J]. Expert Systems with Applications，2018（96）：358-372.

作者简介：李波（1981—），女，汉族，吉林长春人，讲师，博士研究生，主要研究方向：智能算法的研究与工作。