面向對象技術實現求解RCPSP的遺傳算法

李 琦 張靜文 王 帥

(西北工業大學管理學院 陜西 西安 710072)

面向對象技術實現求解RCPSP的遺傳算法

李 琦 張靜文 王 帥

(西北工業大學管理學院 陜西 西安 710072)

基于遺傳算法求解RCPSP(resource-constrained project scheduling problem)的算法框架，采用面向對象的技術抽象出算法運行中的五個類：活動類、項目網絡圖類、串行調度進程類、種群中的個體類及遺傳算法類。基于動態數組表示項目網絡圖和活動之間的邏輯關系，并分析出每個類的基本屬性及操作函數，其次，探究出各個類之間的組合或依賴關系，從整體角度，設計出包含所有類的算法靜態結構圖，清晰地展示了多個類之間復雜的數據互訪過程，進而實現了基于面向對象技術的遺傳算法求解RCPSP編碼，最后從理論上分析了采用面向對象技術的優勢。研究表明，相對于傳統的面向過程的編程方式，基于面向對象技術實現求解RCPSP的遺傳算法使得代碼編寫工作量大大減少，程序的可讀性增強，且算法的運行效率有很大提高。

RCPSP 面向對象 遺傳算法 編碼

0 引 言

資源約束型項目調度問題RCPSP廣泛地存在于建筑工程、軟件開發、計算機行業(如操作系統中的資源管理、處理器的任務調度等)、飛機及輪船制造等單件或者小批量生產方式的企業中[1-2]。活動僅有一種執行模式的RCPSP被稱作基本RCPSP[3]，它是項目調度問題PSP(project scheduling problems)中最經典、也是最具代表性的模型，因此其求解算法也是求解其它類型PSP的基礎。求解基本RCPSP模型的算法分為兩大類：精確算法和啟發式算法。對大規模的項目，精確算法求解問題不現實，因此從實用角度，PSP求解中更廣泛地使用啟發式算法，包括啟發式算法和超啟發式算法，而超啟發式算法則主要體現為智能優化算法，如遺傳算法GA、模擬退火、禁忌搜索、粒子群等[4-6]，還有將兩種啟發式算法相結合的混合智能優化算法[7]。相比較而言，超啟發式算法在求解基本RCPSP中使用的更普遍且求解效果更好。

采用超啟發式算法求解RCPSP時，當算法設計好之后，最關鍵的一個步驟是采用某種編程語言實現算法步驟。采用面向過程實現求解RCPSP及相關問題的過程太繁瑣，需要定義的變量太多，程序的可讀性差且編譯效率不高，基于此本文主要集中于算法的面向對象編程實現問題。遺傳算法是求解RCPSP的最具代表性且被學者證明是對RCPSP具有最好效果的超啟發式智能優化算法，因此本文以遺傳算法為依托，探究采用面向對象技術實現項目調度問題求解算法的核心技術。

1 遺傳算法求解基本RCPSP

1.1 算法框架

理論上，基本RCPSP模型是一類組合優化問題，以項目工期最短為目標函數，包括兩個約束條件：第一是最基本的活動之間的邏輯關系約束；第二是項目執行過程中的可更新資源約束。模型的解是所有活動開始時間構成的一個序列。通常，RCPSP模型借助一個有向五圈的項目網絡圖G=(V,E)來表達，其中V表示活動結合，E表示活動之間的優先關系集合，且|V|=J和|E|=e。

采用遺傳算法GA求解基本RCPSP時，在解的編碼、初始種群的產生、設置個體適應值評價函數等方面，在選擇、交叉、變異等遺傳操作的實現上都有多種方式，對此本文都采用了最具代表性的方式來闡述[8-13]。遺傳算法的運行參數有：設Popsize表示種群規模(population size)、Pc表示交叉概率(crossover)、Pm表示變異概率(mutation)，Maxgen表示種群的最大進化代數。設k(k=1,2,…,Popsize)代表種群中的第k個個體，用T(k)表示個體k對應的項目工期。

(1) 編碼和解碼

用優先關系可行的活動序列進行編碼，這也是眾多超啟發式智能優化算法求解RCPSP時最常用的編碼方式。由于簡潔直觀，這種編碼方式最具代表性，所以每個序列的長度為J(項目中包含的活動個數)；基本RCPSP以項目工期最短為目標，因此通常采用串行調度機制實現解碼過程，解碼后可獲得某個解對應的目標值─項目工期。

(2) 個體適應值評價函數

基本RCPSP的目標是項目工期(越小越好)，但在實現選擇操作時，適應值大的個體有更高的概率進入下一代，所以個體的項目工期不能直接作為它的適應值，需要基于個體的項目工期重新設計適應值函數。本文用所有個體工期的和減去最小化項目工期，把原始目標轉化為適應值函數。

(3) 初始種群的產生

本文選擇隨機方式產生初始種群POP0。

1.2 遺傳進化過程

通過選擇、交叉和變異三種遺傳操作實現算法的進化過程，對于基本RCPSP模型，這三種操作具體如下：

(1) 選擇

本文遺傳算法實施輪盤賭選擇操作，對應項目工期越小的個體適應值越高，因此有更大的概率被選擇參與交叉等遺傳進化過程。

(2) 兩點交叉

交叉操作采用兩點交叉方式，記參與交叉的兩個個體分別為Mother(用M表示)和Father(用F表示)，交叉后產生的兩個后代分別為Daughter(用D表示)和Son(用S表示)。兩點交叉中，兩個交叉點的基因位置分別為r1和r2，且滿足 1

(3) 變異

變異操作時，對交叉獲得的每個個體，對每個基因位依變異概率Pm發生變異。具體為，對于序列中的某個活動，首先確定該活動所有緊前活動在序列中最右側的基因位置；其次，確定該活動的所有緊后活動在序列中最左側的基因位置，這兩個位置即確定了該活動變異時可行的位置區域。將需要變異的活動隨機地插入其可行區域內的任意一個不同于當前位置的基因位上。

2 面向對象技術的算法編程

對于規模較小和流程簡單的程序，編程者可以較容易地寫出面向過程(結構化)的程序代碼，詳細地描述每一瞬時的數據結構及其操作過程。然而，當程序規模較大且復雜時，實現結構化的程序編碼就非常繁瑣且冗長。而面向對象的分析和設計，注重從宏觀上考慮問題，把對問題論域和系統的認識抽象為規范的對象和對象之間的消息傳遞[14]。對象封裝了數據和操作，數據與操作緊密結合，對象互訪非常方便，這些都為使用面向對象思想解決基本RCPSP提供了有利條件。

仔細分析遺傳算法求解基本RCPSP的流程及其中的各個模塊，從中抽象出五個類(Class)，分別是活動類、網絡圖類、串行調度過程類、種群中的個體類及遺傳算法類。

2.1 活動類CActivity

在Aon(Activity-on-node)方式的項目活動網絡圖中，節點表示的活動可以抽象為一個活動類，命名為CActivity。CActivity類的基本屬性包括：代號id、工期duration，它對四種可更新資源的需求量分別為r1、r2、r3、r4。由于每個活動的緊前(或緊后)活動是哪些活動、且緊前(或緊后活動)的數目都不相同，因此定義CActiveArray是一種動態數組類型的數據。

CActivity類的基本屬性還包括它的活動的緊前活動集合pre_activities和緊后活動集合suc_activities，pre_activities和suc_activities的數據類型都是動態數組。

2.2 網絡圖類CAonDiagram

在大規模數值實驗中，通常要測試很多的算例，每個算例的網絡圖結構和參數都不相同，因此將Aon項目活動網絡圖抽象為類CAonDiagram。不同的項目網絡圖中，活動的數目有差別，因此需要使用動態數組記錄網絡圖中的所有活動。使用CActiveArray動態數組來表示一個活動網絡中的所有活動。類CAonDiagram的基本屬性包括：動態數組activity_array，表示項目網絡中的所有活動，其中每個元素都是一個類CActivity(表示一個活動)；四種可更新資源的限量R1、R2、R3、R4。

2.3 種群中的個體類CSample

遺傳進化過程中，種群中包含多個個體，因此將個體對象抽象為類CSample。CSample的基本屬性包括：項目工期project_duration、適應值fi。CSample類的對象表現形式為一個優先關系可行的活動序列，同樣用動態數組表示。

2.4 串行調度過程CSerialSchedule

遺傳算法中，對種群中的每個個體的解碼操作都是在實施一次串行調度過程，因此串行調度過程是遺傳算法求解基本RCPSP中的一個核心的模塊，將其抽象為類CSerialSchedule。

CSerialSchedule的基本屬性包括：第一，網絡圖Aon，數據類型為CAonDiagram的變量，提供了串行調度過程中活動之間的邏輯關系(網絡圖的結構)；第二，串行調度過程中某個階段的合格活動集合En，數據類型為CActivityArray；第三，PSn，表示串行調度過程中某個階段的局部調度計劃集合，數據類型為CActivityArray；第四，priority，表示串行調度過程中活動的優先值序列(一個個體)，數據類型為CIntegerArray。

2.5 遺傳進化過程GGeneticAlgorithm

將遺傳進化過程也抽象為類GGenetic-Algorithm，它的基本屬性包括：第一，max_gen表示遺傳算法的最大進化代數(為整性變量)；第二，Pc表示交叉概率；第三，Pm表示變異概率。種群由多個個體構成，每個個體都是類型為CSample的對象，因此采用元素為CSample對象的動態數組CSampleArray表示種群。

2.6 五個類之間的互訪關系剖析

上述五個類之間的關系、每個類的基本屬性和操作函數總結于圖1中。在每個類對象的屬性或操作中，“-”表示私有成員變量或者私有成員函數(private)，“+”表示公有成員變量或者公有成員函數(public)，“#”表示受保護的成員變量或者受保護的成員函數(protected)。類CActivity與類CAonDiagram之間帶實心菱形的實線表示組合關系，菱形指向整體，即類CAonDiagram是整體，類CAonDiagram是部分；實線在類CActivity的一段標注“n”，在實心菱形段標注“1”，表示一個類CAonDiagram包含多個類CActivity，而且類CActivity不能離開類CAonDiagram而單獨存在；類CGeneticAlgorithm與CSerialSchedule之間帶箭頭的虛線表示依賴關系(Dependency)，箭頭指向被使用者，表示類CGeneticAlgorithm要依賴類CSerialSchedule(被使用的類)。

圖1 遺傳算法求解基本RCPSP模型的靜態結構圖

3 面向對象技術的優勢分析

如果考慮遺傳算法的通用框架，算法流程并不復雜。但是遺傳算法復雜性體現在所求解的特定問題上，比如采用遺傳算法求解RCPSP的實現過程就比較復雜，而這種復雜性源自RCPSP模型本身的復雜性(具有NP-hard特征的組合優化問題)。當然，采用面向過程的編碼也可以實現遺傳算法求解RCPSP。但是需要定義的變量非常多，編寫代碼的工作量很大，而采用面向對象技術編程將使代碼編寫量大大減少。

以項目網絡圖的表示為例，基于面向對象的類表示網絡圖且采用動態數組存儲活動網絡圖的復雜度為O{J+e}；在面向過程的程序中，存儲網絡圖通常采用鄰接矩陣(復雜度為O{J2})或鄰接表(復雜度為O{J+e})的形式，盡管采用鄰接表的復雜度與動態數組存儲網絡圖的復雜度相同，但是鄰接表的定義和訪問操作需要使用指針，計算和編程都較麻煩[15]。最關鍵的是，網絡圖的存儲方式直接決定了求解RCPSP時，遺傳進化過程中數據訪問操作的效率。因為種群中的每個個體都是一個優先關系可行的活動序列(本質是項目網絡圖)，并且對每個個體的編碼、解碼、交叉及變異操作都是對網絡圖的結構和數據的一次訪問過程。因此網絡圖的編碼表示和存儲方式直接決定了遺傳算法求解RCPSP的運行效率。

相對傳統的面向過程的的編程方式，面向對象的技術實現求解RCPSP的遺傳算法，代碼編寫工作量減少，程序的可讀性增強，其優勢是非常明顯的。而且，對于越復雜的組合優化問題，采用遺傳算法求解時，面向對象技術實現編程的優勢比面向過程的方式優勢體現得更明顯。

4 結 語

本文采用面向對象的類表示活動、網絡圖、串行調度過程、種群中的個體及遺傳算法，定義了每個類的基本屬性和操作函數，類之間的關系，開發了基于面向對象技術實現遺傳算法的代碼，進一步從理論上分析了采用面向對象技術的優勢。本文研究工作對采用面向對象技術實現更多復雜的智能優化算法求解組合優化問題提供了理論框架。基本RCPSP問題僅考慮可更新資源限量，本文后續將研究不可更新資源和雙重約束資源約束下項目進度計劃方面的面向對象實現技術。

[1] Hall Nicholas G.Projecr management: recent developments and research opportunities[J].Journal of Systems Science and Systems Engineering,2012,21(2):129-143.

[2] 劉士新.項目優化調度理論與方法[M].北京:機械工業出版社,2007:56-70.

[3] 張靜文.項目調度優化模型與方法的拓展[M].陜西西安:西安交通大學出版社,2015:2-3.

[4] Leus S,Chen A T,Yang C H.A GA-based fuzzy optimal model for construction time-cost trade-off[J].International Journal of Project Management,2001,19(1):47-58.

[5] Hapke M,Jaszkiewicz A,Roman S.Pareto simulated annealing for fuzzy multi-objective combinatorial optimization[J].Journal of Heuristics,2000,6(3):329-345.

[6] Tsai Y W,Gemmill D D.Using tabu search to schedule activities of stochastic resource-constrained projects[J].European Journal of Operational Research,1998,111(1):129-141.

[7] Ahsan M K,Tsao D.A heuristic search algorithm for solving resource-constrained project scheduling problems[J].Asia-pacific Journal of Operational Research,2003,20(2):143-160.

[8] 王宏,林丹,李敏強.一種求解資源受限項目調度問題的自適應遺傳算法[J].系統工程,2005,23(12):99-102.

[9] 楊利宏,楊東.基于遺傳算法的資源約束型項目調度優化[J].管理科學,2008,21(4):60-68.

[10] Liu S,Wang M.An object-oriented methodology for solving the RCPSPs with heuristics and metaheuristics[J].Production Planning & Control:The Management of Operations,2010,11(5):434-442.

[11] 王宏,林丹,李敏強.一種求解多目標資源受限項目調度的遺傳算法[J].計算機工程與應用,2008,44(7):1-4.

[12] Bianco L,Caramia M.An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations[J].European Journal of Operational Research,2012,219(1):73-85.

[13] Hartmann S.Project Scheduling with Multiple Modes:A Genetic Algorithm[J].Annals of Operations Research,2001,102(1/4):111-135.

[14] 譚浩強.C++面向對象程序設計[M].北京:清華大學出版社,2006:37-66.

[15] 張靜文,周杉.面向對象技術實現活動網絡圖及關鍵路徑算法[J].計算機工程與應用,2016,52(4):234-237.

REALIZATIONOFGENETICALGORITHMFORSOLVINGRCPSPBASEDONOBJECT-ORIENTEDTECHNIQUE

Li Qi Zhang Jingwen Wang Shuai

(SchoolofManagement,NorthwesternPolytechnicalUniversity,Xi’an710072,Shaanxi,China)

The framework of resource-constrained project scheduling problem(RCPSP)was solved based on genetic algorithm, an object-oriented(OO, in short) class was adopted to represent activities, project network diagrams, serial scheduling process, individuals in the population and genetic algorithms. And dynamic arrays were used to denote the project network graphs and the logical precedence relationships among activities. The basic properties and the operation function of each class were defined. Next, the combination or dependency relationship of each class was explored in this paper. And the static structure diagram of the algorithm which contains all classes from a whole perspective was designed, which clearly showed the complex process of data exchange between multiple classes. Then, the codes of the genetic algorithm were developed by means of an OO technique. Finally, the advantages of OO technology were analyzed theoretically. Compared with the traditional process-oriented programming, the research shows the genetic algorithm based on OO technology to solve RCPSP makes the code writing workload greatly reduced. The readability of the program is enhanced and the running efficiency of the algorithm is improved greatly.

RCPSP Object-oriented Genetic algorithm Coding

TP3

A

10.3969/j.issn.1000-386x.2017.09.001

2016-11-11。中國博士后科學基金項目(2015M580875，2016T90947)；航空科學基金項目(2015ZG53080)；陜西省科學基金項目(2015JM7368，2014P23)；西北工業大學研究生創意創新種子基金項目(Z2016177，Z2017055)。李琦，碩士生，主研領域：項目調度優化。張靜文，教授。王帥，碩士生。