（系统工程专业论文）过程系统优化的分布式并行计算.pdf

浙扛大学博士学位论文 摘要， 流程工业作为一个国家的主导行业，对国民经济的发展起着举足轻重的作用。 利用企业综合自动化改造传统产业，可极大挖掘企业的内部潜力，产生巨大的经 济习社会效益。 f 过程系统通常采用基于过程机理和严格物性计算的精确数学模型，这类模型 往往具有大规模、非线性的特点庞大的过程全联立方程优化命题，需要耗费大 量的计算时间才能求解。尽管近年来计算机的硬件和处理能力已经有了极大的提 本文立足于大规模过程优丝的现实需求，在对国内外现有研究成果及技术发 展脉络进行系统总结及把握的基础上，对大规模过程系统并行优化中涉及的关键 技术和优化理论进行了深入的研究，并结合实际，对若干应用问题进行了有益的 探索。在此基础上，实现了并行优化计算平台与软件 本文的主要研究工作包括； l 1 ) 系统论述了并行技术的原理与并行优化的目的，讨论了并行算法与并行计算 模型，对现有研究成果进行了分析与评述，并指出了理论研究与实际应用中 所存在的困难和一些亟待解决的问题： 2 ) 比较各种并行处理系统后，提出利用机群系统来构建并行优化平台，这是一 种便于实际应用的高性能价格比的并行策略，目前，尚未见到有关此方面的 研究文献报道。分析了计算机机群系统的优点，讨论了利用机群系统实行优 化计算的关键所在和如何提高机群系统的效率问题； 3 ) 研究了现有的各种并行优化算法，并讨论了常见优化算法的并行化问题，对 这些并行化策略进行了评价。在此基础上，提出了各种并行优化算法的机群 系统求解方案； 4 ) 深入讨论了s q p 算法，分析了s q p 算法中的各种并行线索与策略。着眼于粗 粒度计算的要求，提出了一种基于梯度分裂的大规模并行s q p 算法，将梯度 求解过程转化为一些较小的子问题在各个机群节点求解，适合利用计算机机 旦一 塑垩查兰苎主堂竺兰奎 群系统进行并行计算。在一个精馏塔算例的仿真计算中显示了该算法的有效 性： 提出了一种合适并行计算的大规模分解协调算法，研究用s q p 算法进行底层 优化、拟牛顿法作为协调算法开展大规模过程系统优化计算。此种并行算法 体系所具有的粗粒度特征使之非常适合于用机群系统来实现。通过一个换热 器的算例，表明该算法的计算优越性及良好的并行性能。 提出了并行优化软件平台的总体设计框架，并设计了初始化函数，发送接收 任务函数、进行任务函数和回送并综合结果函数四大类的并行基础函数。在 这些并行基础函数的基础上，实现了并行s q p 与并行分解协调算法。从伪代 码的分析中表明，利用四大类基础函数实现并行计算是简单而有效的。y 塑垩奎兰堡主兰垒丝苎 ! ! ! a b s t r a c t p r o c e s so p t i m i z a t i o nh a se m e r g e da so n eo ft h em o s tv a l u a b l et e c h n i q u e sf o r s y s t e md e s i g n ，a n a l y s i sa n do p e r a t i o n c u r r e n t l y , t h er a p i dt r e n d st o w a r di n c r e a s e d m o d e ld e t a i la n dr i g o r , d y n a m i co p t i m i z a t i o n ，o n - l i n eo p t i m i z a t i o n ，a n ds c h e d u l i n g a c c e l e r a t et h en e e dt oo p t i m i z ev e r yl a r g es y s t e m so f e q u a t i o n sw i t hm a n yd e g r e e so f f r e e d o m t h e l a r g e - s c a l eo p t i m i z a t i o no fp r o c e s ss y s t e m s ，h o w e v e r , c o n t i n u e st o p r e s e n t a m a j o rc h a l l e n g e b o t hi na c a d e m i aa n di np r o c e s si n d u s t r i e s e v e nw i t ht h eh i g hp e r f o r m a n c ec o m p u t e r sn o w a d a y s ，t h e r es t i l l e x i s t sm a n y d i f f i c u l t i e sf o ras i n g l ec o m p u t e rt os o l v el a r g e s c a l ec h e m i c a lp r o c e s so p t i m i z a t i o n p r o b l e m s p a r a l l e lc o m p u t i n g w i t hc l u s t e ro f w o r k s t a t i o n s ，i sah i g h p e r f o r m a n c e p r i c e s o l u t i o nt os o l v el a r g e s c a l ep r o c e s s o p t i m i z a t i o np r o b l e m s t h i sd i s s e r t a t i o nd e t a i l st h e i n v e s t i g a t i o n ，d e v e l o p m e n ta n di m p l e m e n t a t i o no f e f f i c i e n ta l g o r i t h m sa n dt e c h n i q u e sf o rp a r a l l e lo p t i m i z a t i o no f p r o c e s ss y s t e m s t h e m a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 ) t h et h e o r ya n do b j e c tt op a r a l l e lc o m p u t i n gt e c h n o l o g yf o rp r o c e s so p t i m i z a t i o n p r o b l e m s a r er e v i e w e d m a n y p a r a l l e la l g o r i t h m sa n dp a r a l l e lm o d e l sa r ed i s c u s s e d d e t a i l so fc l u s t e ro f w o r k s t a t i o n s 。ar e l a t i v e l yr e c e n t l yd e v e l o p e dt e c h n o l o g y , a r e g i v e nt oh i 曲l i g h ti t sa d v a n t a g e sc o m p a r e dw i t ho t h e ra p p r o a c h e si np a r a l l e l c o m p u t i n g a n e ws o l u t i o nw i t hc l u s t e ro f w o r k s t a t i o n st os o l v e l a r g e - s c a l ep r o c e s s o p t i m i z a t i o np m b l a m si sp r o p o s e d t h ep l a n tc a nu s ec l u s t e ro fw o r k s t a t i o n st o g a i ns t r o n gc o m p u t a t i o np o w e r a tl o wc o s t o b s e r v a t i o mi n d i c a t et h a tt h ed e g r e e o f g r a n u l a r i t yp l a y s a m a j o r r o l ei nt h i sa p p m a e h i ts h o u l db e c a r e f u l l ys c h e m e d t o b a l a n c et h el o a do fc o m m u n i c a t i o na n dt h ed i s t r i b u t e dc a l c u l a t i o ns t e p s h o wt o i m p r o v ec o m p u t a t i o ne f f i c i e n c yi nc l u s t e r o f w o r k s t a t i o n si sa l s od i s c u s s e d 2 ) s e v e r a lp a r a l l e lo p t i m i z a t i o na l g o r i t h m sa r ed i s c u s s e da n de v a l u a t e d ，a n dt h e yc a r l b ed i v i d e di n t ot w o c l a s s e s ：a l g o r i t h m sb a s e d o n g r a d i e n ta n da l g o r i t h m sn o tb a s e d o n g r a d i e n t t h e ns o m ep a r a l l e ls o l u t i o n su s i n gt h e s ea l g o r i t h n a sb a s e do nc l u s t e r o f w o r k s t a t i o n sa r ep r o p o s e d j v 浙江大学博士学位论文 3 ) a ss q p ( s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ) h a se m e r g e da st h ea l g o r i t h mo f c h o i c ef o r s o l v i n gl a r g e s c a l ep r o c e s so p t i m i z a t i o np r o b l e m s ，s e v e r a lp a r a l l e l s t r a t e g i e s f o r s o pa r e p r e s e n t e d ap a r a l l e l s t r a t e g yu t i l i z i n g c l u s t e ro f w o r k s t a t i o n si sp r o p o s e dt os o l v ep r o c e s so p t i m i z a t i o np r o b l e m se f f i c i e n t l y t h e m o s te x p e n s i v ec o m p u t i n gp a r t si n s q pa r ef u n c t i o na n dg r a d i e n t se v a l u a t i o n u s i n g v a r i a b l ep a r t i t i o n ，al a r g e - s c a l eg r a d i e n t se v a l u a t i o np r o b l e mc a r lb ed i v i d e d i n t os e v e r a l s u b p r o b l e m s w i t hs m a l l e rd i m e n s i o n s t h e s u b - p r o b l e m s a l e i n d e p e n d e n ta n d c a nb ec a l c u l a t e do nd i f f e r e n t p r o c e s s o r s b e c a u s ec o m m u n i c a t i o n o v e r h e a d a m o n gw o r k s t a t i o n s i s v e r y h i g h o nl o c a la r e a n e t w o r k ，c o a r s e g r a n u l a r i t ym u s tb es e l e c t e dt or e d u c ec o m m u n i c a t i o nr a t i o t h i sm e t h o da s s u r e s t h en e e df o rc o a r s eg r a i na n d1 0 wc o m m u n i c a t i o n ，a n di t ss u i t a b l ef o rc l u s t e ro f w o r k s t a t i o n s c o m p u t i n gr e s u r so nad i s t i l l a t i o nc o l u m no p t i m i z a t i o np r o b l e m d e m o n s t r a t et h e e f f i c i e n c y o f t h i sa p p r o a c h 4 ) d e c o m p o s i t i o n - c o o r d i n a t i o n m e t h o dc a nb eu s e dt o s o l v e v e r yl a r g e s c a l e p r o b l e m s t h et w ot i e ra r c h i t e c t u r eo ft h i sm e t h o dm a k e si tt i m ee x p e n s i v ea m o d i f i e dd e c o m p o s i t i o n - c o o r d i n a t i o nm e t h o di s p r e s e n t e df o rl a l g e - s c a l ep r o c e s s o p t i m i z a t i o na n dp a r a l l e li m p l e m e n t a t i o n ，s q pi su s e da tl o w e rl e v e la n dq u a s i n e w t o nm e t h o di su s e da t u p p e rl e v e l i nt h i sm e t h o d i no r d e rt o i m p r o v e e f f i c i e n c y o fd e c o m p o s i t i o n - c o o r d i n a t i o n a l g o r i t h m ，ap a r a l l e la p p r o a c hu s i n g c l u s t e ro fw o r k s t a t i o n si s d e v e l o p e d c o m p u t i n gr e s u l t so nah e a te x c h a n g e o p t i m i z a t i o np r o b l e md e m o n s t r a t et h ee f f i c i e n c yo f t h i s a p p r o a c h 5 ) a d i s t r i b u t e dp a r a l l e lo p t i m i z a t i o nc o m p u t a t i o ne n v i r o n m e n tb a s e do nm a t l a bi s p r o p o s e d a f t e rd e t a i l so fp a r a l l e lc o m p u t a t i o ne n v i r o n m e n ta l ed i s c u s s e d ，t h e a r c h i t e c t u r eo fd i s t r i b u t e d p a r a l l e lo p t i m i z a t i o nc o m p u t a t i o ne n v i r o n m e n ti s a n a l y z e d f o u rk i n d so fp a r a l l e lf u n c t i o n si n c l u d i n gi n i t i a l i z a t i o n ，c o m m u n i c a t i o n ， c o m p u t a t i o na n di n t e g r a t i o na r ep r o p o s e da n dd i s c u s s e d p a r a l l e ls o pa n dp a r a l l e l d e c o m p o s i t i o n - c o o r d i n a t i o nm e t h o da r ei m p l e m e n t e db a s e do nt h i se n v i r o n m e n t a n d p s e u d o c o d c sa r cg i v e nf o rd e m o n s t r a t i o n 本文得到国家自然科学基金项目( 基金号2 9 9 0 6 0 1 0 ) “化工过程系统优化的分布式并行计算研究 资助 致谢 在本文即将完成之际，首先感谢我的导师钱积新教授多年来在我学业上给予 的悉心指导和在生活上的热情关怀。钱老师广博的知识、开阔的视野、严谨的治 学态度、忘我的敬业精神、诲人不倦的长者作风都使我终生难忘。在此谨向我的 导师表示最衷心的感谢和最诚挚的敬意! 特别感谢邵之江副教授和仲卫涛博士多年来给予的极大帮助和支持。在这几 年中，两位师兄在各方面都给了我非常热心的指导，并对本文的研究提出了很多 宝贵的意见和建议。在此致以深深的谢意! 、衷心感谢师兄张余岳博士、陈曦博士，师姐周立芳博士，同一课题组的李翔、 张仲广同学，他们与我进行了许多有益的交流和讨论。感谢所里的王慧副教授、 梁军副教授、马龙华副教授、赵均博士、赵豫红博士等诸位老师对我一向的关心 和支持。 衷心感谢邓赤女士长期以来所给予的帮助。 好友郭斯羽、孔亚广、沈晓波一直对我的学习和生活提供了很大的帮助，在 此并致谢。 最后，深深感谢我的父母和家人，是他们给予了我无私的帮助和支持，使我 能够全身心地投入到学习和工作中。 谨以此文献给我的老师，同学以及我的家人。 张帆 2 0 0 2 年5 月 于求是园 浙江大学博士学位论文 第一章绪论 摘要对大规模过程系统优化的背景进行了详细的介绍，阐述了本文的主要工作 和意义。系统论述了流程工业并行优化技术，讨论了并行算法和各种并行计算模 型，并对现有研究成果进行了分析与评述。在此基础上，提出利用机群系统解决 大规模过程系统优化命题。讨论了并行技术的最新趋势，即基于i n t e m e t 的网格 计算。 1 1 企业综合自动化 流程工业在国民经济中占据着主导地位，大型化和自动化是其发展的一个重 要趋势( 钱积新等，1 9 9 8 a ，1 9 9 8 b ) 。随着市场经济的发展，国内各个企业间越来 越多的兼并联合，在石化、冶金、造纸、化工等流程行业不断出现了特大型企业。 尤其是近些年来，随着全球化的步伐，各国流程工业更是以超乎寻常的速度日益 增长，并创造出巨大的经济和社会效益。 然而，随着现代流程工业生产过程越来越复杂、规模越来越庞大，以及原材 料短缺和能源价格的不断上涨，各个企业之间的竞争也越来越激烈。流程工业各 部门面临着生产规模、经济效益、产品品种、质量和环境保护等多方面的严峻挑 战。企业要想在市场竞争中立于不败之地，必须提高自身的竞争能力。不断地提 高生产效率，降低成本，改进产品质量，提高生产过程的柔性，以适应快速多变 的市场需求。 采用高新技术改造现有装置、设备的生产能力与水平，则是提高企业市场竞 争能力的必由之路。过程自动化作为工业生产不可缺少的组成部分，一直是实现 大规模工业生产安全、平稳、优质、高效的基本条件和重要保证，工业现代化程 度越高，其成套技术装备依赖自动控制的程度越大，对自动化技术、控制水平、 仪表装置的要求也就越高。当前，自动化装置与大型设备已成为不可分割的一个 整体。可以说，如果不配置合适的自动控制系统，大型生产过程根本无法进行。 实际上，生产过程自动化的程度已成为衡量工业企业现代化水平的一个重要标志 第一章绪论 ( 金以慧，1 9 9 3 ) 。 然而，流程工业生产过程具有高度的复杂性、强关联性、非线性、以及不确 定性，往往伴随着物理化学反应、生化反应、相变过程及物质与能量的转换和传 递，是一个十分复杂的工业大系统；流程工业生产过程还伴随着十分苛刻的生产 条件和环境，如高温、高压、低温、真空、易燃、易爆及存在有毒物质，生产的 安全性至关重要；流程工业生产过程还强调实时性、整体性，各生产装置间存在 复杂的耦合、制约关系，要求从全局的角度进行集成和协调，以保证整个生产的 高效平稳运行。 生产的快速发展、激烈的市场竞争使综合自动化成为流程工业过程自动化发 展的必然方向。过程的高度复杂性、非线性、不确定性等因素的存在，无疑使流 程工业综合自动化的发展面临更加严峻的挑战。当前，流程工业综合自动化尚处 在起步阶段，许多关键理论、技术及实际问题还有待人们进一步解决。 1 1 1 企业综合自动化框架 自动化作为一门学科，更作为直接服务于国民经济生产的一项重要技术，是 随着现代社会工业大生产的发展而不断得到完善的。自动化控制技术在经历了7 0 年代以前的简单控制系统、7 0 至8 0 年代的先进控制系统发展之后，进入9 0 年代， 以生产装置的优化操作并着眼于市场为导向的集管理、控制于一体的企业综合自 动化( c o m p u t e r i n t e g r a t e d p r o c e s s i n g s y s t e m s ，c i p s ) 就成为当前自动化发展的必 然趋势。企业综合自动化改变了原有单元水平上的生产过程优化与控制思路，将 分散于各个局部过程的众多生产状态信息进行充分集成、分析，根据实际情况对 当前的生产状态进行正确评估，并采取相应的控制与决策策略使企业生产达到整 体最优，以获取最大的经济效益。 通过考察一个典型的流程工业企业的生产过程自动化体系可知，对于一个具 有如此多样的信息模型，多变量和强耦合特性，以及庞大数据量、计算量的复杂 工业系统，以往采用单一过程控制与优化手段的作法显然无法满足生产要求。因 此必须从系统的角度来研究企业综合自动化系统，对其进行功能和层次上的分解。 借鉴于大系统多级递阶及分解协调的思想，企业的生产经营活动在纵向从功能上 可分解成企业的经营决策、计划管理、生产调度、操作优化、过程控制等多个层 次。同时将整个生产过程从横向上划分成一个一个的单元操作，如精馏塔、反应 器、裂解炉、压缩机等过程，作为过程控制与优化的基本单元。在对过程进行分 浙江大学博士学位论文3 解的同时，由于整体优化绝不是各局部优化的简单叠加，因此还必须进行综合协 调以实现生产过程的整体最优。 由此，就可将一个极其复杂的企业综合自动化问题分解成单元操作的控制、 局部优化及整体协调、生产过程的最优调度、企业经营管理及最优决策等四大部 分。这样形成的系统不仅是种单纯由计算机硬件环境及软件平台构成的技术系 统，同时也是种包括各级管理与工程人员、管理过程在内的社会系统。 复杂工业过程综合自动化系统的总体结构如图1 1 所示( 钱积新等，1 9 9 7 ) 。 由复杂工业过程综合自动化总体结构可知，过程优化层位于最优调度层与过程控 制层之间，是两者之间的桥梁和纽带：一方面，优化层将上层计划决策、调度方 案等信息具体化，给出量化的实施方案及细则，使企业计划决策得以贯彻实施； 另一方厩，优化层又将最优操作方案或设定值送至过程控制层，指导现场生产， 实现最优操作，从而获得最大效益。可见，过程优化是实现生产经营管理与生产 过程控制一体化的关键一环，是实现装置生产安全、平稳、优质、高效并最大限 度提高经济效益的重要保证。 本文的讨论重点将集中在过程优化层，并主要对流程工业过程的并行优化问 题进行深入的研究。在下面一节将对流程工业的优化命题进行详细的论述。 三一 苎二兰堕丝 能源 能源 图1 1 复杂工业过程综合自动化总体结构 标 1 1 2 流程工业的优化 从应用角度讲，流程工业中的优化可定义为( b i e g l e r e ta l ，1 9 9 7 ) ：对于一个 给定的过程或系统，在满足一定约束条件下寻找其“最佳”结果。 为了对“最佳结果”进行量化，需定义目标函数以作为评价某一特定解下过 程或系统“好”的程度。典型的目标函数可为产量最大、操作成本最低、原料利 用率最高、能量消耗最小、经济收益最大、投资成本最低等一系列经济指标函数。 此外，化工过程计算中理想、非理想混合物的g i b b s 自由能及熵值计算等也可作 为目标函数；为确定目标函数值，还需定义决策变量，这些变量一般都具有明确 的物理意义，如装置的尺寸，操作温度、压力，进料流率等；而过程操作中的一 些限制，设计规定，产品纯度要求，相关的质量平衡、能量平衡、相平衡方程， 变量的上下界约束、相互之间的关系等则构成了优化命题的约束条件。寻优过程 中，决策变量在使目标函数取极值的同时，约束条件也必须得到满足。 流程工业涉及面广，包括众多复杂过程，所进行的优化往往因目的、对象的 不同而存在较大差异。就实施阶段的不同，流程工业优化可分为设计优化与操作 优化。就命题类型的不同，则可分为稳态优化与动态优化。其中，稳态优化采用 静态模型，通常都由“纯”代数方程所表达，是目前应用最多的一类优化；动态 优化则采用动态模型，其命题本质上非线性连续可微，可由微分及代数混合方程 所描述。 针对不同命题，采用的最优化方法也不尽相同。总的来说，流程工业最优化 方法可分为以下几类( 杨友麒，1 9 8 9 ) ： 1 ) 按约束条件的有无： 无约束最优化，有约束最优化( 等式约束，不等式约束) ； 2 ) 按约束条件的处理方法： 可行路径法，不可行路径法； 3 ) 按目标函数的数目： 单目标优化，多目标优化； 4 ) 按决策变量的数目： 单维最优化，多维最优化； 第一章绪论 5 ) 按解算方法： 直接搜索法，解析法； 6 ) 按目标函数及约束性质： 线性规划，二次规划，非线性规划； 7 ) 按变量的性质： 连续规划，整数规划，混合规划； 8 ) 按处理方式： 确定型优化，随机型优化，模糊优化。 9 ) 按处理器个数： 串行优化，并行优化。 最优化方法虽然很多，但大都离不开计算机的处理，因此最优化方法既是一 种数学方法，又是一种计算机算法。本文将针对这两个方面主要研究连续非线性 约束优化问题。 1 2 大规模复杂系统是并行优化的推动力 过程系统通常采用基于过程机理和严格物性计算的精确数学模型，这类模型 往往具有大规模、非线性的特点。一个典型的化工过程系统优化全联立方程维数 一般在2 0 ，0 0 0 - 4 0 0 ，0 0 0 ，其中包含了所有的单元模型方程、物性计算方程、流程 联接方程。如此庞大的化工过程全联立方程优化命题，需要耗费大量的计算时间 才能求解。大规模复杂系统的来源主要有： 1 ) 开放式方程建模 在过程系统流程模拟中，序贯模块法一直占有主导地位，应用非常广泛。目 前绝大多数流程模拟系统都属于这一类。但由于序贯模块法存在着诸多缺陷，面 向开放式方程的联立解法被越来越多的采用( g a l l u ne t a l ，1 9 9 2 ) 。开放式建模的 基本思想是： 将描述过程模型的所有方程以残差方程形式联立起来，形成一个非线性方程 组： 占( 力= 0 浙江大学博士学位论文 式中，x 为过程变量；g 为模型方程组，包括物性方程，物料、能量、化学 平衡方程，单元联接方程，设计规定方程等。这种表达方式下决策变量与状态变 量的地位是等同的，而且模型的求解也不再与特定的算法相耦合，故称之为开放 式方程建模。 在开放式方程建模中，模型的修改和扩展变得非常容易：针对不同的已知条 件或建模要求，只需对变量重新进行指定即可，无需重写代码。不仅如此，开放 式方程法中各模型方程都具有形如式( 1 1 ) 的残差方程形式，它打破了序贯模块法 中所谓“洋葱”型的模型结构，所有方程均在同一层中列出。其收敛过程是一种 不可行路径法的思想，避免了序贯模块法中的层层迭代收敛以及由此而引起的模 型计算效率及稳定性等诸多问题，模型求解与寻优计算在同层中进行，极大地 提高了收敛速度。 虽然开放式方程建模有众多的优点，但由于该方法打破了原闭合式方程法下 的多层收敛机制，将所有模型方程在同一层中同时联立求解，故所得优化命题往 往规模很大，这就使面向开放式方程建模成为流程工业大规模优化命题的一个主 要来源。 微分代数混合系统优化 随着对流程工业生产的灵活性要求的不断增加，以动态过程为对象的最优化 问题在流程工业实践中发挥着越来越重要的作用。为降低生产成本，提高经济效 益，并考虑安全、环保等诸多因素要求，对动态过程优化问题的研究也逐渐成了 一个热点。 流程工业动态优化问题都可表示成微分代数混合方程形式 ( d i f f e r e n t i a l a l g e b r a i ce q u a t i o n ，d a e ) 。这里，微分方程用于描述过程的动态特 性，如质量平衡、能量平衡等；代数方程用于描述过程的稳态平衡机理及热力学 关系等。以d a e 模型为基础的流程工业动态优化问题则称为微分代数混合优化 问题( d i f f e r e n t i a l - a l g e b r a i co p t i m i z a t i o n p r o b l e m ，d a o p ) 。 目前，对于d a o p 问题的求解主要基于以下思路：对控制变量与状态变量轨 线同时进行参数化处理，将微分方程模型离散成一组纯代数方程，并以约束残差 形式嵌入到优化命题当中，最终形成个标准非线性优化命题。当前，随着技术 的发展，企业综合自动化中控制层与优化层的划分日趋模糊，那种传统上将稳态 优化与动态控制截然分开的作法正逐渐向以动态模型为基础、综合考虑过程稳态 第一章绪论 特性与动态品质的实时动态优化过渡。动态模型的离散化使最终优化命题规模较 一般开放式方程法下的稳态优化命题要大得多，因此，d a o p 问题的求解是流程 工业大规模优化命题的一个更大的来源。 3 ) 混合整数及多目标优化 在流程工业优化中还存在着另一大类特殊类型的优化命题，即混合整数非线 性优化( m i x e d - i n t e g e r n o n l i n e a r p r o g r a m m i n g ，m i n l p ) 。此类命题的提出是由于 一 在工程设计及实践中，一些命题的优化变量既包括连续变量，又包括离散变量， 即整数变量。这使该命题与一般非线性连续优化命题存在着显著差别一对优化变 量有离散性要求。为了满足该要求，构造混合整数优化算法就遇到了很大的困难： 由于混合整数优化命题具有组合数学的特征，极易发生组合爆炸问题，因此当搜 索量猛增时会使计算量的需求变得非常庞大。 另外，在实际的工程优化中还经常会遇到一些需要同时兼顾，但又相互矛盾 的具有多个优化目标的优化命题。如装置设计中的精馏塔、反应釜设计，既希望 用料尽可能节省，同时又希望使用时安全度要大，而这两个目标是相互制约的。 此外，流程工业的大规模生产中还存在着追求经济效益最大化与满足日益强烈的 环保要求，即社会效益之间的矛盾。对于这种同时要考虑多维评价指标的系统优 化问题称之为多目标优化。由于多目标优化问题的目标函数至少有两个，是一个 向量函数，因此不仅会带来如何衡量目标函数向量好坏的问题，而且在处理流程 过程系统时，由于系统规模通常很大，目标向量与决策变量之间关系复杂且难于 协调，因此往往会造成优化命题维数很高，计算非常困难。 在近期以来，为了求解大规模优化系统，人们发展了各种技术。目前，主要 的大规模求解算法有： 1 ) 大规模s q i 算法 经过近二十多年的发展，序列二次规划算法( s e q u e n t i a lq u a d r a t i c p r o g r a m m i n g ，s q p ) 已成为流程工业优化领域中应用最为广泛的算法。其卓越的 计算性能，强大的非线性处理能力，使其被公认为解决中小规模工程优化问题最 为有效的算法。由于s q p 通过求解一系列二次规划予问题来获得原问题的最优解， 这其中涉及一个n x n 维的h e s s i a n 矩阵，当命题维数扩大时，h e s s i a n 阵规模急剧 上升，从而带来存储及计算上的诸多困难，这是传统s q p 法求解大规模优化命题 时所必须解决的关键问题。 浙江大学博士学位论文 目前，s q p 的改进主要有两类思路：简约空间法，稀疏全空间法。简约空间 法本质上是一种空间分解策略，利用流程工业优化命题自由度不高的特点，通过 空间分解策略消去非独立变量和等式约束，使q v 子问题的维数大大降低，从而 降低命题的存储及计算需求( s c h m i da n d b i e 蕾c r ，1 9 9 3 ，1 9 9 4 ：b i e g l c r e ta 1 ，1 9 9 5 ) 。 大规模s q p 的另一条改进思路是稀疏全空间s q p 算法。这类算法根据流程工业 优化命题普遍具有稀疏结构的特点，通过利用大规模稀疏矩阵技术及特殊的处理 技巧，使命题的稀疏结构在优化计算中得以最大程度的保持，从而可显著减少高 维矩阵的存储需求及庞大计算量( b e t t sa n df r a n k ，1 9 9 4 ) 。 2 ) 大规模数值计算的自动微分 导数计算是大规模优化乃至科学计算中的一项基本的数学运算，工程计算中 的许多方法都需要利用导数。以s q p 算法为例，其迭代过程中约束方程的线性化、 h e s s i a n 阵的构造、线性搜索过程的进行，都离不开导数信息的支持。自动微分以 非标准分析理论为基础，通过将函数微分运算转换为实数延拓空间上的代数运算， 可在一次运算中同时求出任意阶复杂函数值及其导数，且所得导数为精确导数， 是数值计算与分析领域内一项全新的技术( g r i e w a n k e t a l ，1 9 9 3 ) 。求导运算在优 化算法的总计算量中占有相当大的比重，若能采用自动微分，使导数计算量及时 间消耗都得以显著降低，则优化算法的效率必会大大提高。 3 ) 大规模优化的修改障碍函数法 传统s q p 算法中大多采用积极集法求解q p 子问题，其计算复杂性随不等式 约束的增加而呈指数型上升，对大规模优化问题的求解十分不利。近年来，一类 求解大规模非线性约束优化命题的修改障碍函数法( m o d i f i e db a r r i e rf u n c t i o n ， m b f ) 逐渐引起人们的广泛关注。m b f 法不受命题自由度的限制，其迭代次数也 几乎不受不等式约束数量的影响，非常适合于求解含有大量不等式约束的流程工 业优化命题( v a s s i l i a d i sa n df l o u d a s ，1 9 9 7 ) 。 4 ) 并行优化 解决大规模优化问题的另一个可行思路是采用并行优化技术。大规模优化中 海量的数值计算及数据处理需求迫切需要不断提高计算机的性能及计算能力，依 靠并行处理( p a r a l l e lp r o c e s s i n g ) 技术提高计算机的运算速度，则是近年来令人瞩 目的一个发展方向。本文的讨论也集中在这方面。 1 0 第一章绪论 1 3 并行计算机与并行算法 1 3 1 并行技术概述 依靠并行处理( p a r a l l e lp r o c e s s i n g ) 技术来提高计算机的运算速度，其主要动 力来自于大规模科学计算的需要。有人曾这样定义并行处理：并行处理是由若干 处理单元以某种结构互连构成的系统，系统中的处理单元能够互相通讯并相互协 同以快速完成大型计算( 袁方，王风先，1 9 9 7 ) 。 并行计算的发展主要来源于以下两点：单机性能不可能满足大规模科学与工 程问题的计算需求；并行性是物质世界的普遍属性，具有实际物理背景的计算问 题往往能划分为可并行求解的多个子问题。国外曾经有人根据对几十个常规应用 软件的统计，发现9 0 左右的串行计算可以并行化。 从应用的角度看，并行处理系统主要有以下几类： 1 ) 向量处理系统( p v p ，p a r a l l e lv e c t o rp r o c e s s o r 或称v p p ，v e c t o rp a r a l l e l p r o c e s s o r ) 以c r a y y - m p 、n e cs x - 3 、f u j i t s u v p - 2 0 0 0 和国产的y h 1 等为代表，向量 计算机在结构设计中采用流水线概念，把一个功能部件分成几个不同的部分，每 一部分对一对操作数执行部分功能。向量存储结构如图1 2 所示： 主存贮器流水线 图1 2 向量机结构 2 ) 共享存储的多处理机系统( s m p ，s y m m e t r i c m u l f i p r o c c s s o r ) 如s g ip o w e rc h a l l e n g e 和s u ns p a r c c e n t e r 2 0 0 0 。多个处理器通过互联网络共 享一个统一的内存空间，并通过该内存空间来实现处理器间的协调。s m p 的一个 主要问题是可扩展性差，当处理器需要同时访问共享局部变量时，产生内存竞争 现象而严重影响效率，比较适合求解中小规模问题。 浙江大学博士学位论文 i内存互联网络 l 图1 3s m p 结构 3 ) 基于分布存储的大规模并行处理系统( m p p 。m a s s i v ep a r a l l e lp r o c e s s o r ) 比如c m - 5 、c r a y t 3 d 、i b m s p 2 、i n t e lp a r a g o nx p s 等；m p p 中每个处理器 中都有自己可直接访问的内存，每台处理器称为系统的一个节点，节点之间通过 互联网络相互连接，m p p 克服了s m p 的可扩展性差的缺点。 i 处理器if 处理器fl 处理器f l il l il i 内存ii 内存li 内存l ff iii l lil i内存互联网络 圈1 4 m p p 结构 4 ) 计算机机群系统( c o w s ，c l u s t e ro f w o r k s t a t i o n s ) 将在节1 4 中作详细论述。c o w s 与m p p 的区别在于m p p 的互联网络采用专 门的高速线路，而c o w s 采用松散的局域网络。 l l 处理器ji 处理器j i 处理器ii i ill li 内存li 内存ll 内存i iii 通用局域网络 图1 5 机群系统结构 第一章绪论 1 3 2 并行算法 并行算法是一些可同时执行的多个进程的集合，这些进程互相作用的协调动 作，从而达到对给定问题的求解( 张宝琳等，1 9 9 9 ) 。计算机发展的并行化趋势， 必然会引起数值计算方法的“并行化”。众多并行计算机厂家与用户已深切地感受 到，在并行机上进行科学计算急需强有力的并行算法的支持。否则，机器纵然性 能优越，也难以完成用户所需要的高性能计算任务，结果造成计算机资源的莫大 浪费。 并行算法和并行计算机的发展是相辅相成的，它经历了几个重要的阶段。首 先是基于向量运算的并行算法，在上世纪7 0 年代末和8 0 年代初最为流行。8 0 年 的初期和中期，随着多向量处理机的出现而提出了相应的并行算法，其特点是既 要考虑到多处理机的任务级粗粒度并行，又要考虑到单处理机上的向量级细粒度 并行。8 0 年代中期，s 1 1 v d ( s i n g l e - i n s t r u c t i o n - s t r e a mm u l t i p l e - d a t a - s t r e a m ) 计算机， 即“单指令流多数据流计算机”上的并行算法研究最为热门，该类并行机由大量 功能简单的微处理器构成，通常需要并行算法在各处理器上很好地分配局部数据， 并组织数据在处理器间的合理流动，从而解决整个计算命题。 m i m d ( m u l t i i n s t r u c t i o n - s t r e a mm u l t i p l e - d a t a - s t r e a m ) 计算机，即“多指令流多数据 流计算机”上的并行算法研究开始于8 0 年代初期，它的处理器功能比较强大，能 独立处理各类复杂运算，处理器间通过显式或隐式的通讯来相互协同，共同求解 同一问题。因为处理