（系统工程专业论文）基于遗传算法的工程项目工期与成本的优化.pdf

一 、 c l a s s i f i e di n d e x ： u d c ： ad is s e r t a t i o nf o rt h ed e g r e eo fm e n g g a sa r i t h m e t i co nt i m e - - c o s to p t i m i z a t i o n i na r c h i t e c t u r ee n g i n e e r i n g c a n d i d a t e ：t i a nz h e nj i e s u p e r v i s o r ：p r o f l vs h u p i n g a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l t y ：s y s t e m se n g i n e e r i n g d a t eo fs u b m i s s i o n ：s e p t e m b e r2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：d e c e m b e r2 0 0 9 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。厂- 作者( 签字) ：，铆口苎 日期：斫年, t 月日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 酌在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 一l b 夕 作者( 签字) ：f 匐拓廷导师( 签字) ：勿肜纵 j | 日期：矽哆年力月，日卅年，月，日 f 哈尔滨_ 亡程大学硕十学位论文 摘要 工期与成本优化是施工项目计划的一个重要方面，属于多目标优化。多 目标优化问题一直是科学和工程研究领域的一个难点和热点问题，在遗传算 法应用到这一领域以前，已经产生许多经典的方法，但这些方法在处理多维 等复杂问题时存在许多不足。通常传统的规划方法往往由于对优化函数的数 学特性的依赖和方法本身在搜索空间上的限制，不能很好地解决复杂的多目 标优化问题。而遗传算法具有处理这类问题能力，因此应用遗传算法求解多 目标优化问题将成为工程领域的发展趋势。本文基于遗传算法对工程工期与 成本优化问题进行了研究。 论文对遗传算法及多目标优化的基本理论和框架进行了分析，阐述了多 目标优化问题的p a r e t o 最优解、传统多目标优化的方法及局限性研究了遗传算 法的基本原理和流程，将制造系统的多工序选择模型p p p 应用于网络计划优 化中，并利用关键路线法，最后找到一系列的p a r e t o 解。 论文给出了利用遗传算法对优化问题求解的设计思路，在分析基本的多 目标遗传算法优化方法的基础上，提出了一种基于改进精英保存策略上的权 系数改进遗传算法，该算法将改进( ”九) 进化策略与基于权系数的遗传算 法相结合，通过对种群规模的不断检测和部分群体重新初始来保证群体多样 性和搜索方向的多样性，从而保证了p a r e t o 解得搜索效果。 通过仿真，验证了改进的遗传算法矛f l p p p 模型在网络计划成本和工期优 化中的有效性和可行性，并针对改进算法存在运行速度变慢问题，又将小生 境技术与改进算法进行结合，给出一种混合算法，仿真表明该混合算法在搜 索效果和效率上有一定的优势。 关键词：遗传算法；工期与成本优化；网络计划优化；p a r e t o 解 哈尔滨工程大学硕十学位论文 a b s t r a c t t h et i m e c o s to p t i m i z a t i o ni so n eo ft h em o s tc r u c i a la s p e c t so fc o n s t r u c t i o n p r o j e c tp l a n n i n g ，i tb e l o n gt om u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m m u l t i o b j e c t i v eo p t i m i z a t i o ni sad i f f i c u l tp r o b l e ma n dar e s e a r c hf o c u si nt h ef i e l d so f e n g i n e e r i n g c l a s s i c a lm u l t i o b j e c t i v eo p t i m i z a t i o n m e t h o d sh a v es e v e r a l s h o r t c o m i n g si ns o l v i n gh i g hd i m e n s i o na n dm u l t i - m o d e lp r o b l e m s m a n y p r o b l e m sw h i c ho f t e nd e p e n do nt h em a t h e m a t i c a lc h a r a c t e r i s t i c so ft h eo b j e c t i v e f u n c t i o n sc a nn o tb es o n e ds a t i s f a c t o r i l yb yt h et r a d i t i o n a la p p r o a c h e s i no r d e rt o s o l v et h e s e p r o b l e m s r e s e a r c h e r s h a v e d e v e l o p e dm a n ym u l t i o b j e c t i v e o p t i m i z a t i o ng e n e t i ca l g o r i t h m sb a s e do ns i m p l eg e n e t i ca l g o r i t h m a n d ，a st h e c a p a b i l i t yo fs e a r c h i n gt h eg l o b a lb e s ts o l u t i o n sr a p i d l y ，g e n e t i ca l g o r i t h mh a s b e c o m ear e s e a r c ha r e a 、i t hi n c r e a s i n gi m p o r t a n c e i nt h i st h e s i s ，t h eb a s i cc o n c e p t s ，t h e o r i e sa n df r a h a e so ft h e e v o l u t i o n a r y a l g o t i t h ma n dt h em u l t i o b j e c t i v eo p t i m i z a t i o na r es y s t e m a t i c a l l yi n t r o d u c e d f i r s t l y e x p l a i n i n gt h ec o n c e p to ft h ep a e r t oo p t i m i z a t i o ns o l u t i o n s t os u m m a r i z e s o m ec l a s s i c a lm u t i - o b j e c t i v e so p t i m i z a t i o nm e t h o d sa n ds h o wt h el i m i t so f t h e m i nt h ep a p e r ，w ea l s oi n t r o d u c et h eb a s i ct h e o r yo fg e n e t i ca l g o r i t h m i n c l u d i n gi t sw o r k i n gf l o wa n dt h ec o m m o nt e c h n o l o g yt h a th a sb e e nu s e di nt h e o p t i m i z a t i o np r o c e s s a tt h es a m et i m et ou s em u l t i s t a g ep r o c e s sp l a n n i n g ( p p p ) m o d e la n dc r i t i c a l p a t h m e t h o dt os o l v et h e p r o b l e mo fm u l t i - o b j e c t i v e o p t i m i z a t i o na n dt o f i n dp a r e t ov a l u e st h r o u g hu s i n gt h eg am e t h o da n d e v o l u t i o ns t r a t e g y a na p p l i c a t i o ne x a m p l ei sa n a l y z e dt oi l l u s t r a t et h eu s eo ft h em o d e la n d a l g o r i t h mi no p t i m i z a t i o n p r o v e dt h ev a l i d i t yo ft h ei m p r o v e dg a f i n a l l yt a b l e da m i x e dg ao nn i c h e d p a r e t oa n di m p r o v e dg aa n dp r o v e dt h ev a l i d i t yo ft h i s g a k e yw o r d s ：g e n e t i ca l g o r i t h m ；t i m e c o s to p t i m i z a t i o n ；n e t w o r k p l a n o p t i m i z a t i o n ；p a r e t o 哈尔滨工程大学硕士学位论文 ；i l l _ - - ；宣；i i ；i ；i ；i ；i ；昌i 目录 第1 章绪论1 1 1 课题背景与意义1 1 2 基于网络技术的优化研究现状。2 1 2 1 网络计划技术3 1 2 2 工期与费用优化技术研究现状7 1 3 本文的主要工作内容。9 第2 章多目标优化理论及技术1 1 2 1 多目标优化数学模型1 2 + 2 2 多目标优化的非劣解1 2 2 3 多目标优化的方法1 4 2 4 本章小结1 6 第3 章遗传算法的原理及实现：1 7 3 1 遗传算法优化原理17 3 1 1 标准遗传算法步骤和流程1 8 3 1 2 流程描述1 9 3 2 遗传算法的数学理论2 4 3 2 1 模式定理2 4 3 2 2 积木块假设2 6 3 3 本章小结2 7 第4 章多目标遗传算法的优化2 8 4 1 遗传算法的多目标优化技术分析j 2 8 4 2 遗传算法流程的改进设计3 2 4 2 1 储备仓保存策略的改进3 2 4 2 2 基于权系数选择方法的改进3 4 4 2 3 遗传操作3 5 4 3 模型和编码的设计3 6 4 3 1p p p 模型3 6 4 3 2 编码设计：3 8 一 】 一一 哈尔滨工程大学硕士学位论文 4 3 3 权重系数的确定和适应度函数评价3 8 。4 3 4 全节点编码3 9 4 3 5 关键路线模型编码及算法验证4 0 4 4 本章小结4 2 第5 章基于改进遗传算法的仿真分析4 4 5 1 实例设计4 4 5 2 小生境算法的实现4 5 5 2 1 小生境算法4 5 5 2 2 结果分析4 7 5 3n s g a - i i 算法及实现4 8 5 3 1n s g a - i i 算法4 8 5 3 2 结果分析4 9 5 4 基于改进算法的分析5 1 5 4 1 关键路线编码不带储备仓和检测的算法5 1 5 4 2 关键路线编码带储备仓和检测的算法5 3 5 4 3 仿真结果分析5 5 5 5 基于混合算法的仿真分析6 0 5 6 本章小结j 6 3 结论6 5 参考文献6 6 攻读硕士学位期间发表的论文和取得的科研成果6 9 致 谢7 0 哈尔滨：r 程大学硕士学位论文 第1 章绪论 1 1 课题背景与意义 我国从2 0 世纪8 0 年代初期开始引进建设工程项目管理的概念，世界银 行和一些国际金融机构要求接受贷款的业主方应用项目管理的思想、组织和 手段组织实施建设工程项目。1 9 8 3 年我国原国家计划委员会提出推行项目前 期项目经理负责制，1 9 8 8 年开始推行工程监理制度。可以说我国7 0 年代从 国外引进项目管理理论，此后在改革开放的过程中结合中国的建设管理体制 和建设管理实践进行了系统的理论研究和实践探索【l 】。当前在工程项目管理 中也在大力推行招投标制、建设监理制度和项目管理中的建造师制度。如在 2 0 0 3 年2 月2 7 日国务院关于取消第二批行政审批项目和改变一批行政审 批项目管理方式的决定中就明确了：取消建筑施工企业项目经理资质核准 制，由注册建造师代替，由此说明我国项目管理逐渐在完善和确立，与此相 关的理论研究和实践探索也在不断促进着国内建筑企业管理科学的发展。 建设工程项目管理的内涵是：自项目的开始至项目的完成，通过项目策 划和项目控制，以使项目的费用目标、进度目标和质量目标得以实现。项目 管理的核心任务就是项目目标的控制1 2 j 。项目管理包括很多方面：如业主方 项目管理、设计方项目管理、施工方项目管理和采购方的项目管理等。而施 工项目工程管理在全过程项目管理中，是落实投资计划，实现设计概算指标 和企业盈利的关键环节。特别现正在逐渐落实招投标实行工程量清单制度下， 相对于目标偏差的被动控制，好的施工计划是对工程目标进行控制有效的主 动管理方法。而施工项目管理目标主要包括：施工的安全管理目标、成本目 标、进度目标和质量目标。对于施工方来说，要想扩大盈利，在建筑市场上 立于不败之地，就必须在质量目标控制下特别重视施工工程成本和工期管理。 工期和成本目标有各自的内涵和控制方法，它们不能互相替代和等同，它们 之间存在着对立统一的辩证关系。工期是工程从丌工到完工的全部时间；成 本对施工企业来说是工程建设的全部费用；工期和成本是相互依存又相互矛 盾的一组共同体，合理的缩短工期，从业主方来考虑，将会使工程尽早投入 哈尔滨工程大学硕十学位论文 使用，给业主带来超前收益，提高投资效益。对施工方来说间接费用会降低， 间接费即不是直接与工程实体相关的费用，如管理费用等。但工期缩短，势 必增加人工和机械设备的使用量从而导致工程直接费用的增加，引起工程成 本的增加。直接成本是与工程直接相关的费用，如人工费，材料费、机械费 等。也就是说，工期目标和成本目标之间是凹型关系【3 】，即工期过短和过长 都能造成成本的大幅度上升。 在实践中网络计划工期的确定往往是靠工期定额和业主的要求而定，然 后再确定网络计划的关键路线工期不超过已定工期，从而来进行网络计划的 编制，但这样工期和成本可能并不是最优，可能由于工期不足，造成施工单 位为赶工期，在工程质量一定的情况下，势必造成工程成本的增加。或由于 定额工期的平均水平低于本企业企业的施工水平，从而由定额工期确定的工 期进行网络计划的编制必将引起工期增加，同样也会造成工程成本的增加和 业主效益的下滑。因此在质量水平为定值的情况下，项目建设的理想状态就 是同时达到工期和成本的最优，但在实际情况下双优很难实现，因此只能综 合评定，给出一系列帕累托( p a r e t o ) 解来进行决策更为有意义。 1 2 基于网络技术的优化研究现状 工期与费用的管理从属于项目管理范畴，项目管理丌始引起人们关注是 由于1 9 5 8 年的美国海军的北极星导弹的研制计划，当时应用关键路径技术采 用加权的方法进行计划编制，结果工期节省了3 3 ，从此项目管理技术开始 崭露头角。1 9 6 5 年欧洲率先成立了国际项目管理协会( i p m a ) ，之后美国 也成立了项目管理学会( i p m a ) ，前期的研究主要集中在各个专业领域，p m i 将各个专业共性的东西提出来于1 9 8 7 年推出了项目管理知识体系指南 ( p m b o k ) 将项目管理研究推向了顶峰，这是项目管理的一个里程碑。因此 项目管理作为- 1 7 学科，核心就是目标控制。 归纳起来对于目标的控制方法的研究可以分为三个阶段：事前计划控制、 事中的偏差控制、事后的评价控制。目标的研究内容也日趋丰富主要有：成 本目标、工期目标、质量目标、安全目标和各类组织管理目标的研究以及以 上目标的综合型研究等，因为事前控制是预控，对于目标的控制具有重要作 用，因此本文主要是事前的计划控制，而进行计划控制重要的工具就是网络 2 哈尔滨工程大学硕士学侍论文 计划。 1 2 1 网络计划技术 1 2 1 1 网络计划基本情况 网络计划在5 0 年代产生、应用和推广，在管理理论上是一次质的突破， 基本原理就是：首先用网络图形来表示项目的各项工作进行顺序及其相关间 的联系，并确定每项工作所需要的资源等数据，使得可以对项目进行分析和 计算，找出计划中的关键路线和关键工作，继而可以不断地改进网络计划， 从而优化网络。工程项目其规模往往规模庞大，建设周期长，为使工程项目 施工能够协调、高效运行、往往需要事前制定网络计划，因此网络计划是工 程项目管理的一个必要过程，并且网络计划贯穿于施工全过程，可以说网络 计划是计划组织、协调控制的重要组成部分【4 】o 国际上，工程网络计划有许多名称，如c p m 、p e r t 、c p a 、m p m 等。 工程网络计划的类型有如下几种不同划分方法： ( 1 ) 按照网络计划工作持续时间特点可分为：肯定型问题网络计划、非 肯定型网络计划和随机网络计划等； ( 2 ) 按照工作和事件在网络图中的表示方法可分为：事件网络( 以节点 表示事件的网络计划) 、工作网络( 以箭线或节点表示工作的网络计划) ； ( 3 ) 按照计划平面的个数划分可分为：单平面网络计划、多平面网络计 划( 多阶段网络计划，分级网络计划) 。 在国内网络计划常用的可以分为双代号网络图，单代号网络图和时间坐 标网络计划，单代号网络计划见图1 1 。前两种网络计划图，箭杆长短并不 表明时间的长短，而后一种是以时间为坐标的一种网络计划。双代号网络图 见图1 2 ，是应用较为普遍的一种网络计划，它以圆圈和有向箭杆表达计划 所要完成的各项工作及其先后次序和相互关系而构成的网状形状，在双代号 图中，用有向箭杆表示工作，工作的名称写在箭杆上方，工作所持续的时间 写在箭杆下方，箭尾表示工作的开始，箭头表示工作的结束。单代号网络图 也是由节点和箭线组成，但构成单代号网络图的基本符号含义与双代号不尽 相同。与双代号相比，单代号绘图较为简单，逻辑关系明确，没有虚箭杆， 便于检查和修改，但存在由于工作持续时间表示在节点之中，没有长度、不 3 因素的大的规模开发研究，主要是时间的控制【5 1 。之后人们在传统的c p m 基 础和p e r t 网络基础上，将决策引入了网络优化中，这也就是后面提到的优 化中决策，如8 0 年代初将风险决策引入图示评审技术g e r t ( g e a p h i c a l e v a l u a t i o na n dr e v i e wt e c h n i q u e ) 和风险评审技术v e r t ( v e n t u r ee v a l u a t i o n a n dr e v i e wt e c h n i q u e ) 等，其最大特点就是工序间的逻辑关系不确定性，允 许存在网络回路，这开创了网络计划研究的思路。但k i d d 在做了一份网络计 划使用方便性的调查显示，虽然人们对v e r t 和g e r t 研究多年，但是目前 项目网络计划方法仍然是方便快捷的c p m 和p e r t ，而v e r t 和g e r t 则由 于计算量大，计算复杂耗时长而没有被使用。因此本文主要研究的是基于 c p m 条件下的网络优化研究。 一b ) ( 卫二一l 。生_ 叫型 、弋d7 7 - 图1 1 单代号网络示例图 1 2 1 2 网络计划基本术语 ( 1 ) 工作：工作也称活动，是指完成一项任务的过程。根据计划编制的 粗细不同，工作既可以是一个建设项目、一个单项工程、也可以是一个分项 工程乃至一个工序。 ( 2 ) 紧前工作：紧接在该工作前面的工作，称为紧前工作。 ( 3 ) 紧后工作：紧接在该工作后面的工作，称为紧后工作。 4 哈尔滨t 程大学硕十学位论文 ( 4 ) 虚工作：所谓虚工作是虚拟的工作，因此它既不会消耗任何资源， 亦不会消耗时间仅仅是虚拟来补充表示其它相邻工序中间的某种衔接关系， 在网络图中起中断、隔离作用。 ( 5 ) 节点：节点也称事件，是指表示工作的开始、结束或连接关系的圆 圈，箭杆的出发点叫工作的起始节点，箭杆的指向节点叫工作的终点节点。 ( 6 ) 线路：从原始节点出发，沿着箭杆箭头所指方向直至结束节点，中 间经由一系列节点和箭杆，所构成的若干条通道，即成为线路。一条线路上 的各项工作所持续的时间累加之和称为线路之长，它表示完成线路上所有工 作所需要花费的时间。 ( 7 ) 关键路线：所有线路中，完工时间最长的那条链，决定了整个工程 的完工时间，称为关键线路。在单代号网络图或搭接网络图中间隔时间为0 的路线，关键路线非常重要，揭示了关键路线是网络计划的宗旨。 图1 2 双代号网络图 1 213 网络计划目标优化技术 网络计划技术的优点在于1 1 8 】：把项目中的各种有关工作组成了一个有机 的整体：能全面而明确地表达出各项工序进行的先后顺序同时又能反映出各 项工作之间的相互制约和相互依赖的关系；能进行各种时间参数计算找出决 定项目工期的关键工作和关键线路，便于管理者集中力量抓主要矛盾，确保 工期，避免盲目施工；能够从多个可行方案中选出最优方案；在计划的执行 过程中，某一工作由于某种原因推迟或提前完成时，可以预见到它对其它工 作和整个项目的影响，而且能够根据变化了的情况，迅速进行调整，保证自 始至终对计划进行有效的控制和监督；利用网络计划中反映出的各项工作的 时差，可以更好地调配资源，以达到降低成本的目的，即实现“向关键工作 要时间，向非关键工作要资源”。因此归纳起来优化目标常有以下几种情况。 哈尔滨工程大学硕十学位论文 昌暑i 宣；ii i e i m l i ；i ；i i 暑；宣宣宣i ；昌薯 1 工期优化问题 工期优化也是时间优化，就是当初始网络计划的计算工期大于要求工期 时，通过压缩关键路线和调整工作关系，以满足工期要求的过程，此时要考 虑资源有限情况和压缩后关键路线改变问题，是单目标问题。 2 资源优化问题 资源的优化就是解决网络计划实施中的资源供求矛盾或实现资源的均衡 利用，以保证工程的顺利完成，并取得良好的经济效果，通常有以下两种形 式：资源有限，工期最短；工期一定，实现资源的需求均衡。 ( 1 ) 资源有限工期最短【6 】 研究资源有限、工期最短有以下四个前提条件： 优化过程中不改变网络计划的逻辑关系： 在优化过程中，网络计划的各工作持续时间不予变更； 各工作的每天资源需要量是常数，且是合理的； 一般不允许中断工作，应保持连续性。 早期资源有限工期最短问题的求解采用网络计划技术，绘制网络、计算 网络时间和确定关键路线，得到一个满足进度顺序的初始方案，再考虑资源 约束来调整优化，由于启发式算法简洁有效，一度在此类问题中占据了主要 地位。但是研究发现，启发式规则的确定很大程度上依赖于问题模型的建立， 针对特定问题，很难确定其最佳的启发式准则。而且大量的实际应用例子表 明，尽管多数情况下启发式算法可以产生十分可靠的可行解，但是不能保证 所得解的最优性问题1 2 】。 ( 2 ) 工期一定，实现资源的需求均衡【7 】 工期固定资源均衡问题是解决网络计划中资源的供需矛盾和实现资源 均衡利用的有效方法，通过资源均衡优化可实现项目按期、均衡施工。均衡 施工可以降低资源需要量的强度、机械设备和运输工具用量的峰值，避免增 设临时设施，从而降低施工管理费和工程造价。常用的方法有方差值最小法、 极差值最小法、消高峰法等，也可分为数学解析法、启发式算法、仿生算法 进行求解。 以上是常规对网络计划优化的研究，而对于多目标问题研究归纳起来一 般分为以下几个方面：工期一成本、质量一成本、质量一进度两个目标的综 6 哈尔滨t 稗入学硕十学位论文 合优化和工期一成本一质量三个目标的综合优化等。由于在具体施工中往往 最重要的两个方面就是工期与成本，因此在实际中这两个目标也是最常用的 控制目标，因此本文主要研究的就是工期与成本两个参数的优化控制问题。 1 2 2 工期与费用优化技术研究现状 由于在项目管理中，工期与费用的关系是管理中比较敏感因素，因此本 文着重对工期和费用优化进行探讨。总的来说工期和成本优化研究目的可以 分为以下几类： 1 单目标问题 ( 1 ) 工期一定条件下的费用最下问题【8 】【9 】；这个问题类似于上面提到的 资源优化问题。 ( 2 ) 最小工期研究问题。采用缩减工期，费用增加最少的方法； 2 多目标问题 求出工期与费用的p a r e t o 解，供决策者进行分析，比较选择合适的工期 与费用。本文研究的就是此类关系下的工期与费用优化问题。因为第一类问 题本质还是单目标问题。 工程成本和工期是相互联系和制约的，常见的关系如图1 3 ，在生产效率 一定的条件下，要缩短工期，提高施工速度，工程就必须投入更多的人力、 物力和财力，从而直接费用d c 增加、间接费用尼则减小，总费用t c 就会 形成凹的关系。在目标关系上，早期大部分文献都假设工期一成本的关系是连 续的【1 0 】。然而由于每个活动可供选择的模式对应的工期和成本是离散的， 并且离散化能够使建立工期一成本优化问题的模型更为方便【1 2 】，因此后期的 工期一成本优化问题多为离散型关系。在计算方法上，起初人们采用数学规 划方法解决此类问题，如整数规划【1 6 】、线性规划法、动态规划法等【1 3 】【1 4 】【1 5 】。 在这些方法中，工期和成本的关系的假设可分为以下几类：( 1 ) 线性或非线性； ( 2 ) 凸的或凹的；( 3 ) 离散的或连续的；( 4 ) 混合型关系。数学算法的缺点是算法 效率很大程度上依赖于模型是否做出很强的假设，假设太强常常与实际情况 不符，而且数学算法需要很大的计算量，不能解决实践中较大较复杂的问题 1 7 1 18 1 。之后1 9 6 1 年f o n d a l l ，1 9 7 1 年s i m e r s e 以及m o s e l h i 利用启发式搜索 的方法对问题加以解决，但启发式搜索方法却不能保证得到最优解，在很大程 7 一， 。 。? 一。：。一 一 。ii 一 ? 7 一。 | j ：2 ri+“ 哈尔滨下程大学硕士学位论文 度上依靠经验方法来得出问题的答案【1 9 1 。 工期 图1 3 工期与费用关系图 实际中成本和工期并没有固定的函数关系，另外面对实际情况，对于工期 与成本的决策也并不完全一定是要求成本最小下的工期最优，可能还要面对 其它很多问题，比如工期和成本的合理配合决策，因此给出一系列解，组成专 家解答，进行决策分析更有现实意义。另外对目标的研究相当大一部分工作 也都是集中在数学模型的建立研究上，如利用网络计划对多目标的研究起初 也是通过建立数学模型进行分析，传统上的模型建立，往往是在各个工作方 案不受紧前工作的影响下考虑的，实际中紧后工作的方案选择与紧前工作有 很大的关系，然后利用数学规划方法、启发式搜索方法、模拟退火法进行解 决。在这些方法中没有一个方法能实现现实问题的完美解决，另外数学规划 方法在网络图的工序增多时，需要进行计算的次数会按照指数级的速度增长， 启发式和模拟退火法有一定改善但存在一个致命的缺陷就是很难保证求得最 优解【1 9 1 。 现在出现了一些现代算法在网络优化中起到了很好的效果，f e n gc h u n g w e i 2 0 1 和l i h e n g 2 1 1 是利用遗传算法解决工期与费用优化问题的现行者，他们 提出的方法是假定每个活动的持续时间与直接费用之间为离散关系，即每个 活动有多种执行方案，优化的过程就是方案选择的过程，遗传算法首先得到 直接费用曲线然后再将间接费用加到总费用中进行求解，这种方法充分利用 了遗传算法高效运行的寻优能力，达到了几乎每个可行工期的最小成本解 瞰】，但随着工程量清单普遍使用，每个工序费用就可以包括直接费用和间接 8 哈尔滨工程大学硕士学位论文 费用两种，不必将直接费用优化后再加入间接费用。文献【2 3 】将遗传算法应用 到网络优化中，通过对网络计划的所有节点进行实数编码，每个值代表着这 个工序上的一个方案，通过一系列无偏好的最优系列解的求解，得到了较好 的优化效果。并且将质量也引入优化序列，通过确定每个活动的权重以及各 个质量指标在某项活动中的权重，采用线形加权方法得到工程总质量。这类 方法存在以下不足：首先由于权重确定上很难把握，因此实际应用意义不大； 另外算法和编码过程中没有考虑优化时关键路线不变的情况，如果依然采用 全节点运算势必加大运算负担。胡华选【2 4 】在蚁群算法在工程项目工期一 费用优化问题中的应用一文中，将网络计划与蚁群算法相结合对工程管理 多目标进行优化分析，首先假设各工序时间与费用成正比的关系，建立工期 与费用的函数，确定由工期和费用决定的总成本最小为目标函数的优化，然 后将各工序参数分为正常参数和极限参数，即将某一工序的时间根据方案的 不同，工序的持续时间有一个变化范围，然后将此变化范围离散化为各个时 间点，从而将模型转化为类似的旅行商最小路径问题：熊鹰1 2 5 j 的工期与成本 优化问题，实际上是在网络计划的拓扑结构的约束下，为每个工序确定实施 方案，将工期和成本化为单目标问题，以实现工期和成本目标的最小化，转 化为t s p 问题等。这类问题的不足之处就是需要依赖于工期和费用函数关系， 如此就失去工期和费用关系的普遍性。 因此本文对网络计划优化研究的是：基于c p m 形式的成本和工期多目 标的事前控制网络计划的优化，首先每个活动的持续时间与直接费用之间的 关系采用离散关系的思路，这样更符合实际情况，并且每个工序费用值包含 直接费用和间接费用两个部分，如此就不必再分为两步进行计算，简化过程。 最后利用遗传算法可以处理连续时间和离散费用之问关系的工作，可以得到 一系列的p a r e t o 解来对工期与费用进行优化计算。 1 3 本文的主要工作内容 本文针对工期与费用间的相互关系，利用改进的遗传算法对工期与费用 的p a r e t o 进行求解，达到对工期与费用的优化，具体归纳起来分为四个部分： ( 1 ) 通过对网络计划和工期与费用优化的研究现状综述分析，引出本文： 研究工作；利用遗传算法对基于c p m 形式的成本和工期多目标的网络计划 o 哈尔滨工程大学硕士学何论文 m i i 进行优化，求出一系列p a r e t o 解。 ( 2 ) 对多目标优化和遗传算法理论进行了研究，同时对常用的多目标优 化方法和标准遗传算法流程中的各个步骤的实现进行了分析，奠定采用遗传 算法对工期与费用进行多目标优化的理论基础。 ( 3 ) 对常用的遗传算法的优化技术进行了研究，分析了各类算法的优缺 点，针对n s g a i i 算法的精英保存策略存在复杂度高和循环内保存的策略容 易产生p a r e t o 破坏的情况，对精英保存策略进行了改进，采用了双向比较的 循环外保存策略可以避免以上弊端。同时结合改进的保存策略采用了基于权 系数选择方法对遗传算法进行了改进，使之具有收敛快的特点，并不断的检 测个体的多样性，即当种群多样性小于设定值时，对部分个体重新初始来达 到搜索方向的改变，并随着进化将精英进行循环外保存( 保存组不参加内部 遗传操作) ，最终达到p a r e t o 的求解。 ( 4 ) 在对n s g a i i 算法、小生境遗传算法的多目标优化仿真分析基础上， 。对改进的遗传算法是否带储备仓进行了仿真分析。验证了改进算法求p a r e t o 解的有效性和完整性及在较小的种群规模下也具有较好的求解效果，但同时 也发现了改进算法存在随着种群规模和参数九增大而运算速度下降的问题。 进而提出了将改进算法和小生境相结合的混合算法，仿真结果表明该算法在 求解能力没有降低的情况下，运算速度得到较大改善。 1 0 哈尔滨l ：榉人 第2 章多目标 本文主要研究的是工期与费用两个目标的优化技术，总的来说它属于多 目标优化问题，因此本章主要进行多目标理论的基本论述，从数学模型上来 说明本文多目标研究的结构。多目标是最近3 0 年来发展起来的- - f - j 新兴的学 科，它研究的是向量目标函数满足一定约束条件时，在某种意义下的最优化 问题。它们往往具有相互冲突的目标，一个目标的改善如果不是p a r e t o 解， 就意味着另一个目标的恶化。自2 0 世纪4 0 年代以来，最优化理论和方法日 益受到人们重视，也形成了一系列的优化理论如：线形规划、整数规划、非 线性规划、几何规划、动态规划、随机规划、网络流等。但对于多目标来说， 传统优化方法很难满足解决目标之间互相冲突的问题。 多目标优化问题最早可以追溯到1 7 7 2 年，当时f r a n k l i n 提出了多目标矛 盾如何协调的问题，国际上一般认为多目标优化最早是由法国经济学家 v p a e r t o 在1 8 9 6 年提出的，他从政治经济角度进行了归纳，1 9 4 4 年 v o n n e u m a n n 和j m o r g e n s t e r n 从对策论的角度，提出了多个决策者而且彼此 又互相矛盾的多目标决策问题，1 9 5 1 年t c k o o p m a n s 从生产和分配的活动 分析中提出了多目标优化问题，并且第一次提出了p a r e t o 最优解概念。同年， h w k u h n 和八w t t u c k e r 从数学规划的角度给出了向量极值问题的p a r e t o 最优解概念，1 9 6 8 年l a z a d e h 又从控制论角度提出了多目标控制问题，1 9 6 8 年z j o h s e n 系统的提出了关于多目标决策问题的研究报告，这是多目标最优 化这么学科发展的一个转折剧矧。我国于上世纪7 0 年代丌始注意多目标的 研究，从7 0 年代至今每年相关论文数量平均每1 0 年以约1 1 倍的数量级递增， 7 0 年代多目标研究多集中于多目标规划和一些简单的多目标决策问题，8 0 年代丌始主要集中于方法论、决策和模型的研究上，模糊数学丌始引入多目 标理论的研究，到了9 0 年代论文数量激增，相关研究也开始多样化，注重各 个方面层次的研究，复杂系统和网路技术及现代算法也丌始应用到多目标理 论问题中，概括起来传统多目标优化方法主要有：权重系数法、最小最大法、 惩罚函数法等。本文多目标优化研究是基于2 1 节数学模型l j 的研究，防l 此 想值，此点成为理想点如图2 1 所示，但多目标优化的本质在于：各个子目标 之间互相冲突，一个目标的改善往往以导致其它子目标的恶化，往往很难达 到理想点，因此多目标优化只能是对各个目标进行综合分析考虑。 为了能清除说明，首先建立一个多目标数学模型，这里以目标最小值作 为目标函数进行分析。 多目标问题可以描述为( 2 1 ) 数学模型： m i n f ( x ) = 【石( x ) ，六( x ) ，l ( x ) 1 7，、 二- s t x x 其中f ( x ) 是目标函数向量，z ( _ x ) ，石( x ) ，无( x ) 是各目标函数，x 是决 策变量，x 是由决策变量x 形成的决策空间。 x x 图2 1多目标的理想解示意图 2 2 多目标优化的非劣解 多目标与单目标有着本质的不同，为正确分析多目标最优解，首先对多 目标最优解进行如下定义： 定义2 1 目标向量函数f ( x ) ，x 为欧氏空间，而xx 2 x ， 若五( 而) - l ( x 2 ) ( v k = 1 ，2 ，p ) 并且以( 五) 五( 而) ( v k = 1 ，2 ，p ) 则称 1 2 哈尔滨工程大学硕士学位论文 l 五比而优越。 定义2 2 目标向量函数厂( 石) ，x 为欧氏空间，x x ，x x ， 若五( x ) o ，则册( h f ) 呈指数级增长；若c o 的情况下： 0 ( 1 4 ) 越小，则m ( n , o 越容易呈指数级增长；o ( h ) 越大，则m ( n , o 越不 容易呈指数级增长： 3 变异算子的作用 若某一模式被破坏，则必然是模式的某一基因发生变化，其发生概率为： 1 一( 1 一) 。h ；当l 时，则：1 - ( 1 一p 。) 。何d ( ) 。 由此可知，在变异算子作用下，模式日的生存概率大约是( 3 1 2 ) 式： 见1 一d ( 日) ( 3 1 2 ) 模式的阶o ( 仞越小，模式日越易生存；模式的阶o ( 功越大，模式h 越易破 坏。 综上所述在比例选择算子、单点交叉算子和基本位变异算子的连续作用 下，群体中的模式h 予代样本数为( 3 1 3 ) 式： 朋( 蛳+ 1 ) 猢( 脚等卜箬叫以i ( 3 - 1 3 ) 由此得以下模式定理： 遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义 长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。 3 2 2 积木块假设 模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数将 按指数级增长，这种模式具有低阶、短的定义长度，且平均适应度高于群体 平均适应度的模式。这种类型的模式被称为基因块或积木块。 模式定理说明了积木块的样本数呈指数级别增长，亦即说明了用遗传算 法寻求最优样本的可能性，但并没有说明一定能够找到最优样本，而积木块 假设却能给与说明。 积木块假设 个体的基因块通过选择、交叉、变异等遗传算子的作用， 能够相互拼接在一起，形成适应度更高的个体编码串； 积木块假设说明了用遗传算法求解各