面向对象技术实现求解RCPSP的遗传算法

REALIZATION OF GENETIC ALGORITHM FOR SOLVING RCPSP BASED ON OBJECT-ORIENTED TECHNIQUE

基于遗传算法求解RCPSP(resource-constrained project scheduling problem)的算法框架,采用面向对象的技术抽象出算法运行中的五个类:活动类、项目网络图类、串行调度进程类、种群中的个体类及遗传算法类。基于动态数组表示项目网络图和活动之间的逻辑关系,并分析出每个类的基本属性及操作函数,其次,探究出各个类之间的组合或依赖关系,从整体角度,设计出包含所有类的算法静态结构图,清晰地展示了多个类之间复杂的数据互访过程,进而实现了基于面向对象技术的遗传算法求解RCPSP编码,最后从理论上分析了采用面向对象技术的优势。研究表明,相对于传统的面向过程的编程方式,基于面向对象技术实现求解RCPSP的遗传算法使得代码编写工作量大大减少,程序的可读性增强,且算法的运行效率有很大提高。

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.