基于集對分析與NSGA-II的工程項(xiàng)目多目標(biāo)優(yōu)化

翟 瑞，張云寧，陳國偉，趙迎亮

(1.河海大學(xué) 商學(xué)院，江蘇 南京 211100；2.江蘇省電力設(shè)計院有限公司，江蘇 南京 210000；3.南京城建集團(tuán)，江蘇 南京 210000)

?

基于集對分析與NSGA-II的工程項(xiàng)目多目標(biāo)優(yōu)化

翟 瑞1，張云寧1，陳國偉2，趙迎亮3

(1.河海大學(xué) 商學(xué)院，江蘇 南京 211100；2.江蘇省電力設(shè)計院有限公司，江蘇 南京 210000；3.南京城建集團(tuán)，江蘇 南京 210000)

工程項(xiàng)目進(jìn)度、成本和質(zhì)量三者是對立統(tǒng)一的，工程項(xiàng)目的多目標(biāo)優(yōu)化著重于求解三者的和諧統(tǒng)一。以工程項(xiàng)目施工過程中的進(jìn)度、成本和質(zhì)量水平閾值為約束條件，運(yùn)用集對分析法為建筑工程多目標(biāo)優(yōu)化問題的處理構(gòu)建了柔性的建?？蚣?利用NSGA-II算法求解多目標(biāo)優(yōu)化模型，得到多目標(biāo)優(yōu)化的Pareto最優(yōu)解集;通過實(shí)際算例驗(yàn)證了該算法在解決工程項(xiàng)目多目標(biāo)優(yōu)化問題中的可行性和有效性。

工程項(xiàng)目;多目標(biāo)優(yōu)化；集對分析；Pareto解集；NSGA-II算法

進(jìn)度、成本和質(zhì)量是工程項(xiàng)目的三大控制目標(biāo)，這三大目標(biāo)不是完全相容的，甚至是相悖的[1]。多目標(biāo)優(yōu)化的理想狀態(tài)是在資源得到均衡充分利用的情況下達(dá)到工期最短、成本最低及質(zhì)量最優(yōu)。BADU等基于工程的質(zhì)量水平、持續(xù)時間和成本之間呈線性關(guān)系的假設(shè)，分別針對質(zhì)量、成本和工期建立了3個線性規(guī)劃模型來研究三者之間的平衡關(guān)系[2]。馬超等將風(fēng)險作為優(yōu)化目標(biāo)，建立了優(yōu)化TCQR多目標(biāo)模型，并通過MOEA/D算法進(jìn)行求解[3]。陳勇強(qiáng)等利用Pareto最優(yōu)原理對工程項(xiàng)目優(yōu)化調(diào)度問題進(jìn)行求解[4]。

筆者基于集對理論，考慮工程項(xiàng)目施工過程的成本型指標(biāo)和效益型指標(biāo)，建立多目標(biāo)的集對聯(lián)系度模型，為進(jìn)度、成本和質(zhì)量的優(yōu)化構(gòu)建柔性建模框架，再運(yùn)用NSGA-II算法求解多目標(biāo)的優(yōu)化模型最優(yōu)解。

1 基于集對分析的多目標(biāo)優(yōu)化模型

集對分析理論(set pair analysis,SPA)最早是在1989年由我國學(xué)者趙克勤[5]提出的一種新的系統(tǒng)分析方法，主要是針對系統(tǒng)中的確定、不確定信息從同異反3個方面定量分析兩個集合之間的相互聯(lián)系、影響和轉(zhuǎn)換，并通過聯(lián)系度μ=a+bi+cj定量地描述集合在研究背景下的同異反聯(lián)系程度大小。a表示兩個集合的同一程度，c表示對立程度，a+c就代表這兩個集合的確定度；b表示兩個集合的差異度，即系統(tǒng)的不確定度；差異度系數(shù)i的取值范圍為[-1,1]，對立度系數(shù)j按照一定概率取值-1,0或者1。其中a,b,c滿足a+b+c=1的歸一化條件。

1.1 工程項(xiàng)目多目標(biāo)集對聯(lián)系度分析

將工程項(xiàng)目成本目標(biāo)、進(jìn)度目標(biāo)和質(zhì)量目標(biāo)分為經(jīng)濟(jì)型指標(biāo)和效益型指標(biāo)，各資源配置計劃的效益也可以具體量化為完成關(guān)鍵作業(yè)的經(jīng)濟(jì)型水平和效益型水平。

在實(shí)際優(yōu)化過程中，可以選擇智能算法或者以往工作經(jīng)驗(yàn)來確定工程項(xiàng)目的施工作業(yè)多目標(biāo)優(yōu)化方案，但由于不確定性因素的存在不能使最終的多目標(biāo)優(yōu)化達(dá)到最優(yōu)狀態(tài)，而集對分析法利用聯(lián)系度可以將確定性和不確定性在同一個系統(tǒng)中進(jìn)行統(tǒng)一辯證處理，為工程項(xiàng)目多目標(biāo)優(yōu)化問題的處理構(gòu)建柔性的建?？蚣堋?/p>

對于經(jīng)濟(jì)型指標(biāo)最劣與最優(yōu)水平分別記作WU和WV，最低與最高值可以從項(xiàng)目內(nèi)部或外部根據(jù)項(xiàng)目實(shí)際目標(biāo)和客觀條件來確定，亦可由式(1)和式(2)確定：

(1)

(2)

式中：M為工程項(xiàng)目所包含的關(guān)鍵作業(yè)數(shù)量；Nj為參與第j項(xiàng)關(guān)鍵作業(yè)的資源配置計劃；Fjk為資源配置計劃k完成第j項(xiàng)關(guān)鍵作業(yè)的成本值。 實(shí)際優(yōu)化方案I的經(jīng)濟(jì)指標(biāo)為：

(3)

(4)

式中:同一度aWi和對立度bWi表示建筑工程優(yōu)化方案經(jīng)濟(jì)型指標(biāo)的優(yōu)劣程度，aWi=S/N,bWi=P/N；差異度cWi表示評價指標(biāo)的不確定性，cWi=F/N；i是取值范圍為[-1,1]的差異度系數(shù);j為對立度系數(shù),一般取-1；N為集對Wi、WV在建筑工程成本、質(zhì)量、進(jìn)度多目標(biāo)優(yōu)化問題背景下的特性數(shù)總和，其中在S個特性上Wi、WV是共同的；有P個是Wi、WV相對立的特性，在F=N-S-P個特性上Wi、WV的關(guān)系是不確定的。

與經(jīng)濟(jì)型指標(biāo)相反，效益型指標(biāo)越大對整體目標(biāo)優(yōu)化越有利，設(shè)效益型指標(biāo)最劣與最優(yōu)水平分別為BU和BV，計算公式為:

(5)

(6)

其中，Bjk為施工班組k完成第j項(xiàng)分類分項(xiàng)工程的效益值。

實(shí)際優(yōu)化方案I的效益指標(biāo)為:

(7)

則實(shí)際方案I的經(jīng)濟(jì)成本集對{Bi,BV}聯(lián)系度為:

(8)

1.2 工程項(xiàng)目多目標(biāo)優(yōu)化集對聯(lián)系度模型

對經(jīng)濟(jì)型指標(biāo)和效益型指標(biāo)分別進(jìn)行集對聯(lián)系度分析之后，以工程質(zhì)量、進(jìn)度和成本閾值作為約束條件構(gòu)建多目標(biāo)貼合度模型：

(9)

(10)

(11)

s.t.Qi≥Qth

(12)

Ei≥Eth

(13)

Ci≤Cth

(14)

Qth≥0,Eth≥0,Cjk≥0

式(9)～式(11)分別為在相對確定條件下的質(zhì)量、進(jìn)度和成本的優(yōu)化目標(biāo)，即三者的貼合度最大。ΘQi、ΘEi、ΘCi分別為質(zhì)量貼合度、進(jìn)度貼合度和成本貼合度；aQi、aEi、aCi分別為質(zhì)量、進(jìn)度和成本的同一度程度；cQi、cEi、cCi分別為質(zhì)量、進(jìn)度和成本的對立度程度；Qi、Ei、Ci分別為施工過程中的實(shí)際施工質(zhì)量水平、進(jìn)度和成本，Qi、Ei、Ci必須都滿足最低的施工質(zhì)量可靠性閾值、最低效率閾值和最大預(yù)算成本閾值的約束條件。

2 基于NSGA-II的建筑工程多目標(biāo)優(yōu)化

2.1 NSGA-II算法

在建立了工程項(xiàng)目多目標(biāo)優(yōu)化模型之后，為了提高優(yōu)化系統(tǒng)的魯棒性，需要采用有效的算法來尋求在該研究背景下的最優(yōu)方案集。

SRINIVAS和DEB在1995年提出了非支配排序遺傳算法(nondominated sorting genetic algorithms，NSGA)[7]，NSGA優(yōu)點(diǎn)在于利用非支配分類程序?qū)⒍嗄繕?biāo)簡化成一個適應(yīng)度的函數(shù)。

2000年印度科學(xué)家在此基礎(chǔ)上提出了改進(jìn)的快速非支配排序遺傳算法NSGA-II[8]，定義了擁擠距離概念來對某個點(diǎn)周圍的解密度進(jìn)行估計，采用擁擠距離比較算子來代替復(fù)雜的參數(shù)適值共享方法。

筆者通過NSGA-II算法來實(shí)現(xiàn)工程項(xiàng)目多目標(biāo)貼合度的優(yōu)化，尋找在該特定問題背景下同一度大、對立度小的最佳方案集。NSGA-II算法的優(yōu)化過程是根據(jù)工程項(xiàng)目施工指標(biāo)和各資源配置計劃的施工標(biāo)準(zhǔn)數(shù)據(jù)得到工程項(xiàng)目質(zhì)量、成本和進(jìn)度參數(shù)的閾值范圍，再以不同資源配置計劃行程的活動模式為決策變量，在給定的約束閾值條件下，實(shí)現(xiàn)施工的質(zhì)量、成本和進(jìn)度指標(biāo)的多目標(biāo)優(yōu)化。

2.2 NSGA-II算法基本流程

NSGA-II算法依據(jù)小生境密度比較算子使得Pareto元素擴(kuò)展到整個Pareto域中，使種群的多樣性得到保證；同時引進(jìn)精英政策，擴(kuò)大了采樣空間，也使整個系統(tǒng)的效率和魯棒性得到提高。帶精英策略的NSGA-II算法流程圖如圖1所示。

圖1 NSGA-II算法流程圖

(1)種群初始化，隨機(jī)生成規(guī)模為N的初始種群。

(2)非劣前沿分級后進(jìn)行選擇、交叉和變異之后生成第一代子代種群。

(3)對合并后的二代父、子代種群進(jìn)行快速非劣前沿分級。

(4)對非劣前沿分級層結(jié)果中的個體進(jìn)行小生境密度計算，再依據(jù)小生境密度和非劣前沿關(guān)系選取適合的個體組成新的父代種群。

(5)對新生成的父代種群進(jìn)行選擇、交叉和變異操作生成新的子代種群。

(6)重復(fù)步驟(3)～步驟(5)，直到達(dá)到預(yù)先設(shè)定的迭代次數(shù)，即可獲得多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解集。

3 算例分析

為驗(yàn)證集對分析與NSGA-II算法相結(jié)合對建筑工程多目標(biāo)優(yōu)化的資源配置問題解決的有效性和可行性，對某個實(shí)際大橋的主墩群樁基施工過程進(jìn)行分析研究。主墩群樁基施工GERT的隨機(jī)網(wǎng)絡(luò)模型如圖2所示。

圖2 主墩群樁基施工GERT的隨機(jī)網(wǎng)絡(luò)模型

根據(jù)主墩群樁預(yù)先擬定的施工方案、進(jìn)度計劃和預(yù)估成本，在對施工現(xiàn)場實(shí)際情況進(jìn)行分析的基礎(chǔ)上，采用專家調(diào)查法對該工程的工期和費(fèi)用各參數(shù)進(jìn)行估計，數(shù)據(jù)如表1所示。

表1 關(guān)鍵作業(yè)時間和費(fèi)用參數(shù)估計表

利用水晶球軟件對主墩群樁基總工期和總費(fèi)用進(jìn)行模擬分析,計算結(jié)果如表2所示。由于主墩群樁基施工的各項(xiàng)工作是相互獨(dú)立的，可先求出各單項(xiàng)工作的局部優(yōu)化，進(jìn)而合并優(yōu)化子集以求得全局最優(yōu)解集。在運(yùn)用NSGA-II算法對施工作業(yè)進(jìn)行優(yōu)化調(diào)度時，需對經(jīng)濟(jì)型指標(biāo)和效益型指標(biāo)分別設(shè)置上、下限約束以確保多目標(biāo)優(yōu)化的準(zhǔn)確性及優(yōu)化結(jié)果的合理性。主墩群樁基施工各項(xiàng)活動的質(zhì)量、進(jìn)度和成本參數(shù)約束范圍如表3所示。

表2 各活動節(jié)點(diǎn)工期及費(fèi)用模擬值

表3 主墩群樁基施工各項(xiàng)活動參數(shù)范圍

工程項(xiàng)目中各活動因?yàn)橘Y源配置方案的差異而形成不同的活動模式，從而產(chǎn)生不同的目標(biāo)效果。算例中的決策變量為活動模式，用mi表示活動i的模式數(shù)量為m個，多目標(biāo)優(yōu)化需要從活動i的mi個模式中選擇一個j(j=1,2,…,mi)作為決策變量，使得最終的資源配置方案能夠使目標(biāo)優(yōu)化的目標(biāo)方程最優(yōu)，即達(dá)到質(zhì)量、進(jìn)度和成本的貼合度最高。各資源配置使用模式量化后相對應(yīng)的質(zhì)量水平、進(jìn)度水平和單位成本如表4所示。

針對多目標(biāo)優(yōu)化模型和算例數(shù)據(jù)，利用Matlab7.0軟件進(jìn)行NSGA-II算法的實(shí)現(xiàn)，求得各活動模式的非支配最優(yōu)解組合,如表5所示。

表4 各資源配置使用模式參數(shù)數(shù)據(jù)

表5 多目標(biāo)優(yōu)化非支配最優(yōu)解組合

表5給出了主墩群樁基施工的5組最優(yōu)解組合，與傳統(tǒng)的遺傳算法如粒子群和蟻群算法等相比，NSGA-II算法克服了多目標(biāo)優(yōu)化方案解的唯一性，管理者可以根據(jù)實(shí)際施工過程中的具體要求選擇不同的資源配置模式。在資源配置計劃調(diào)度問題研究中，NSGA-II算法中的遺傳操作參數(shù)對最終的計算結(jié)果影響很小，相比其他傳統(tǒng)算法具有較高的魯棒性。種群規(guī)模及進(jìn)化代數(shù)參數(shù)設(shè)置可根據(jù)具體問題進(jìn)行從小到大的逐步調(diào)整，得到的結(jié)果具有穩(wěn)定、足夠多且分布均勻的Pareto解集前端，NSGA-II算法具有更好的簡便性與精確性，為工程項(xiàng)目多目標(biāo)優(yōu)化問題的處理構(gòu)建了柔性的建?？蚣堋Ｍㄟ^NSGA-II算法得出的5組非支配最優(yōu)組合均能滿足集對分析法建立的多目標(biāo)優(yōu)化函數(shù)，達(dá)到質(zhì)量、進(jìn)度和成本3個方面的貼合度最高。

4 結(jié)論

通過集對分析法對工程項(xiàng)目質(zhì)量-進(jìn)度-成本的多目標(biāo)優(yōu)化進(jìn)行了集對聯(lián)系度的建模，為消除不同指標(biāo)之間的耦合，利用NSGA-II算法對多目標(biāo)優(yōu)化問題進(jìn)行了求解，有利于提高工程項(xiàng)目資源配置計劃的合理性和科學(xué)性。NSGA-II算法給出了在相對確定研究背景下的所有最優(yōu)解集合，可方便決策者根據(jù)實(shí)際作業(yè)需求和施工參數(shù)要求對優(yōu)化結(jié)果進(jìn)行選取。算例結(jié)果表明，運(yùn)用集對分析法和NSGA-II算法解決工程項(xiàng)目多目標(biāo)優(yōu)化問題是可行且有效的。

[1] 李雪淋，王卓甫.基于向量評價遺傳算法的工程項(xiàng)目多目標(biāo)優(yōu)化[J].水運(yùn)工程，2007(11):9-12.

[2] BADU A J G，SURESH N. Project management with time，cost and quality considerations[J].Eurapear Journal of Operational Research，1996,88(2):320-327.

[3] 馬超，張松，李玉東，等.考慮風(fēng)險的大型工程項(xiàng)目多目標(biāo)均衡優(yōu)化[J].計算機(jī)工程,2013,39(2):270-278.

[4] 陳勇強(qiáng)，高明，張連營.基于遺傳算法和Pareto排序的工期-費(fèi)用-質(zhì)量權(quán)衡模型[J].系統(tǒng)工程理論與實(shí)踐，2010,30(10):1774-1780.

[5] 趙克勤.集對分析及其初步應(yīng)用[M].杭州：浙江科學(xué)技術(shù)出版社，2000:45-101.

[6] WILLIS H L，ENGEL M V. Optimization applications to power distribution[J]. IEEE Computer Applications in Power,1995,8(4):12-17.

[7] SRINIVAS N,DEB K. Multi-objective optimization using non-dominated sorting in genetic algorithms[J]. Evolutionary Computation,1995,2(3):221-248.

[8] DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[J]. Parallel Problem Solving from Nature PPSN VI Lecture Notes in Computer Science,2000(1917):849-958.

ZHAI Rui:Postgraduate; School of Business, Hohai University, Nanjing 211100, China.

[編輯：王志全]

Project Multi-objective Scheduling Optimization Based on Set Pair Analysis and NSGA-II

ZHAIRui,ZHANGYunning,CHENGuowei,ZHAOYingliang

The three main objectives of the project are schedule, cost, and quality, which are the unity of opposites. The optimization of the multi-objectives of the project focuses on seeking the harmony of the three of them. Constrained by the threshold level of the project schedule, cost and quality, a flexible modeling framework was constructed for the construction of multi-objective optimization problem by set pair analysis method. Then NSGA-II algorithm was used to solve the model of multi objective optimization in order to get multi-objective optimization of Pareto optimal solution set. Finally, a practical example was given to verify the feasibility and effectiveness of the algorithm in solving multi-objective optimization project problems.

project; multi-objective optimization; set pair analysis; Pareto solution set; NSGA-II algorithm

2015-04-31.

翟瑞(1993-)，女，安徽蕪湖人，河海大學(xué)商學(xué)院碩士研究生.

校企合作科研基金資助項(xiàng)目(1063-51063213).

2095-3852(2015)06-0735-05

A

TU712.1

10.3963/j.issn.2095-3852.2015.06.016