混合蛙跳算法在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—），女，漢族，吉林長春人，講師，博士研究生，主要研究方向：智能算法的研究與工作。