面向对象技术实现求解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)。李琦，硕士生，主研领域：项目调度优化。张静文，教授。王帅，硕士生。