基于遗传算法的汽轮机项目计划研究

洪超（上海电气电站设备有限公司上海汽轮机厂，上海 200240）

基于遗传算法的汽轮机项目计划研究

洪超
（上海电气电站设备有限公司上海汽轮机厂，上海 200240）

交货期已成为企业继关键技术之后的又一核心竞争力。因此通过合理安排排产计划变得尤其重要。本文系统阐述了基于遗传算法的方法论，并结合汽轮机行业特点，寻求出复杂产品的全生命周期项目的计划，通过MARLAB多次迭代运算，能迅速得出满足资源约束的工期最短的项目调度计划。有效地解决了企业项目调度的优化问题，值得在企业级项目管理中运用。

项目计划；遗传算法；RCPSP问题；汽轮机

1　前言

随着“十三五”“五大发展”论述将绿色发展理念放在更突出位置、社会对雾霾国家为降低经济下行压力，加大对固定资产投入；本着电力是经济发展“先行官”理念，大功率、低热耗的发电机组需求叠加式增长。汽轮机厂时隔数十年，再次迎来在手订单数量的井喷，2016年达到历史极值。汽轮机设计采购制造是系统工程，具有明显的“私人订制”项目化特征。当下，产品的交货期作为除技术外，产品的核心竞争力，做好执行计划，将成为企业提升管理的又一抓手。

作为装备制造业典型代表：汽轮机其全生命周期，可分解出：招投标、方案评审、详细设计、采购、制造、装配、成套、安装、服务等阶段。每阶段都有一些特定的相互制约具体活动组成，这些逻辑网状活动，将占用不同的资源。一个最优的可执行计划，将成为企业在产能高位时期是否能够顺利组织日常经营活动的基础。提供基准计划可成为后续计划的基础。可以说，合理的计划就是一切经营活动的指挥棒。

传统项目计划获取方法：关键路径法、计划评审技术法，都未考虑资源在项目执行过程中的约束问题。显然，这两种方法，对汽轮机这种大型项目，略显狭隘。因此需要谋求新的解决方案。实践证明：为解决这类问题，可以采用资源约束项目（Resource Constrained Project Scheduling Problem，RCPSP）数学工具来解决，且相当有效。

2　优化方向及其数学依据

在RCPSP问题中，数学模型的搭建是为满足目标函数。这些函数按优化方向，分为时间类、资源类、财务类、质量类等。其中，时间类和资源类的目标函数最常见。在实际工程问题中，关于资源和工期的优化方向分两方面：一是资源条件有限的情况下，力求通过合理计划安排达到工期最小；二是在规定的较为宽松的工期下，力求通过合理安排，达到系统对各类资源平衡的需求，以达到承载项目的系统冲击最小。前者更适合市场化运作的企业单位，后者则更适合计划需求稳定的事业单位。

由于RCPSP问题已被证实为NP－HARD问题，因此，在数学上精确求解很困难。针对汽轮机这样的大型项目，活动较多，精确求解将变得不切实际。因此一些元启发式求解算法（metaheuristic）被提出，并成为当下项目管理计划体系研究的热点领域。

目前流行的元启发式算法有：参考基因理论，模拟种群的遗传算法；运用物理现象，模拟物质冷却的模拟退火算法；参照社会行为学中的禁忌概念，避免局部最优而忽略整体最优的禁忌搜索算法；模拟生物昆虫学，蚂蚁利用信息素寻找蚁穴和食物源，体现群体智慧的蚁群优化算法等等；目前在RCPSP问题

3　遗传算法理论依据

项目管理中当随探讨对象的扩大（数量、复杂度的提升），考虑因素的增加，针对组合优化、调度问题的搜索解空间也急剧增加。甚至在目前性能的计算机上，都无法通过枚举法求解。同时在搭建数学模型时，力求简化，但所得解与实际现实情况相差甚远。模型复杂，虽贴合实际，但却造成了求解的困难。精确求最优解几乎不可能。针对这类问题，学者们通过研究的主要方向为退而求其次的满意解。遗传算法是寻求满意解的最佳工具。实践证明，遗传算法对组合优化NP-Hard问题非常有效。遗传算法（Genetic Algorithms GA）是仿制于生物遗传、进化进程。他从本质上说是一种使用范围很广的全局概率搜索算法。最初由Michigan大学的Holland教授提出。其核心思想是基于“自然选择说”，在算法中模拟引入优胜劣汰、适者生存的进化原理，通过一系列技术手段，将目标值，朝预定方向进行渐进演化。

4　RCPSP数学模型描述

设有项目N有ni（i=1，2，3，…，m）个活动，项目各活动消耗r种资源，要求同时满足紧前关系和每时刻资源双重限制条件。假设：

STi和di为第i活动的时间开始时间和活动执行时间；

Rk为资源K在某一时间段的系统组织能够提供的总量；Rik为第i活动在单位时间内对K中资源的需求量；Rikt为时刻t（t=1，2，3，…，T）处对K种资源的需求量。Pi为i个活动的紧前活动集合。

STi≤t≤STi+di

t取其他数值

s.t.STi≥STh+di其中h∈Pi，∀i；Rikt≤Rk其中∀k，t，i；

5　解决问题整体方案设计

5.1染色体编码

染色体编码是将问题数学化后启用遗传算法的基础。编码是将问题的可行解从其解空间转换到遗传算法能处理的搜索空间。针对项目管理的遗传算法，目前文献中主要存在五类编码设计方案：任务列表表达法（Activity List Representation，ALR）；任务优先规则表达法（Priority Rule Representation，PRR）；随机键表达法（Random Key Representation，RKP）；移位向量表达法（Shift Vector Representation，SVR）；直接表达法（Direct Representation，DR）。其中，任务列表表达法，由于内嵌活动的紧前关系，因此也被数值实验证明为一种有效的表达方式，因此是目前运用遗传算法解决RCPSP问题的最常用的染色体编码方式。

5.2适应度函数

工期最短问题是求解目标函数的最小数值。因此项目最后一个活动的结束时间就是目标值，须将原始的目标值转换为适应值，以确保优秀个体应具有更大的适应值。所以应对目标函数做适应度尺度变化，假设vk是种群第k个染色体。f（vk）是vk的活动最短时间，即目标函数。g（vk）是vk的适应度函数，fmax和fmin和分别是当代种群中最大目标和最小目标值，即项目的持续时间，变化方法：其中，ε∈（0，1）

ε的存在是为了防止fmax=fmin情况的出现，导致g（vk）无解。

5.3染色体初始化获取初始种群

初始种群的定义是一个可行的解，也就是一个选择一个多项目可行的计划方案的表述方式。具体方法是按照从左到右的顺序依次确定染色体各个基因位对应的活动序号。首先定义可调度活动集合φ，即所有紧前活动已被安排在基因位上的活动序号集合。每个项目开始活动的序号，组成可调度的活动集合φ，每次从 φ中随机选择项目i，活动 j，并且将其序号 i，j安排在基因位上，同事将活动从集合 φ中移除，并且修正0-1方阵A=aij第i行j列元素值。如：aij=1，修正为 aij=0，当0-1方阵aij=0，则说明所有的活动，都被基因序列表述出来。

5.4标准遗传操作

选择（Selection）——模拟自然选择

选择也称复制，是在群体中选择更好个体产生新的群体过程。体现自然界中优胜劣汰的思想选择算子用来对群体中的个体进行优胜劣汰过滤和筛选，好的选择算子，可把适应度更高个体，以更高的概率遗传到下一代。通过多代选择，使得解不断接近最优解。选择常用的有比例选择，精英选择，联赛选择，排序选择。经典遗传算法常常采用比例选择，每个个体进入下一代的概率就是他适应度与整个种群中个体使用度的比例。以此来表示该个体在选择过程中被选择作为父本的概率。

交叉（Crossover）——模拟杂交繁殖

交叉是将两父本的信息进行交换，以产生新个体，其作用是将优良的解，传给下一代。具体操作为：将代表解的有序数对，随机选择一个交叉位置。根据确定的交叉概率Pc，执行交叉操作。在交叉位置交换彼此对应部分的数据片段，从而形成新的个体。

变异（mutation）——模拟突变

变异是模拟基因突变的过程，在父本产生下代染色体时，因某一些因素，出现了复制差错，从而表现出新生物特性。模仿此法，遗传算法通过变异其目的是为了跳脱出目前收敛，防止解集过早地收敛于局部最优解，而无法获得全局最优解。

遗传算法的基本流程是：首先对优化问题的可行解进行编码（EnCoding，EC）形成染色体（Chromosome，C），构造出包含了系统优化的目标合适的适值函数（Fitness Function，FF）作为评价指标。对种群中的个体用适值函数进行评估（Evaluation E）进行后进行选择（Seletion，S），将适应值高的染色体获得更高的保留生存概率，实在优胜劣汰。得到的新染色体后，经复制、交叉、变异等形成子染色体，再用适值函数，进行选择，再次获得更优秀的染色体，这样循环，新群体更优于上一代同时也继承了上一代的信息，周而复始，种群中个体的个体（解）不断地提高适应度，直到满足一定的条件（譬如：预先设定的循环代数），在合理的计算时间内，得到一可接受的最优解。（详见图1）。

6　试验验证

6.1WBS活动结构分解和活动、资源的预估

在实际工程项目运用遗传算法，首先需对项目活动的前后逻辑顺序进行判别，生成一任务列表，同时，汽轮机的研发设计制造活动的全生命周期，按模块来分解大致涵盖：期初招投标管理、研发设计、采购毛坯、精加工、成套、发运、现场安装、联调168小时并网发电等阶段，这些特定的阶段又有一些细分的活动，如研发设计往往细分成方案设计、详细设计、设计收尾及服务等。而设计收尾又穿插进入了制造加工。因此这项系统工程庞大，活动数量繁多，持续时间长，占用资源多。通过列表将活动和活动时间进行罗列，并形成逻辑图（图 2），体现活动前后逻辑，同时通过德尔菲法得出各项活动所需要的时间和所需要的资源，形成报表。

图1　遗传算法解决流程

图2　汽轮机全生命周期活动示意

6.2 本文通过MATLAB实现上述的程序

硬件环境为普通工作站，软件环境为基于Windows 10的MATLAB 2015；通过编写程序，获得进化代数和最优解（资源限定下工期最短，见图3）。

当人为设置循环代数为500代后自动结束程序循环。通过运算，发现工期最优解在第23次迭代后，完成收敛，达到最优解，迭代效率很高。

7　结语

在经济新常态下，充分利用现有企业资源，在不加大资源投入的情况下，缩短在制品流转周期，在更短时间内将产品推向市场，做到及时响应，已成为饱和电力市场抢夺市场订单的重要手段之一。本文运用遗传算法，解决了资源有限条件下，项目的活动时间最短化。同时通过合理的数学假设和简化，最终获得了一个可行解，最后通过MATLAB运算后，得到验证。

主要参考文献

［1］周明，孙树栋.遗传算法原理及应用［M］.北京：国防工业出版社，1999.

［2］［日］玄关男，程润伟.遗传算法与工程优化［M］.于杰，周根贵，译.北京：清华大学出版社，2005.

［3］寿永毅.资源受限多项目调度的模型与方法［M］.杭州：浙江大学出版社，2010.

［4］史峰，王辉，等.MATLAB智能算法30个案例分析［M］.北京：航空航天大学出版社，2011.

［5］雷英杰.Matlab遗传算法工具箱及应用［M］.西安：电子科技大学出版社，2006.

10.3969/j.issn.1673-0194.2016.17.039

TP312

A

1673-0194（2016）17-0083-04

2016-05-10

洪超（1984－），男，浙江奉化人，工程师，上海交通大学在职研究生，主要研究方向：企业级项目管理。中，运用最广泛的是：遗传算法。且被证明是一种最有效的求解算法，其提供了标准的求解框架，尤其对项目调度问题一般都有比较里理想的求解效果。