（化学工艺专业论文）基于列队竞争算法的混合算法研究及其在化工过程系统中的应用.pdf

武汉理工大学硕士学位论文 摘要 化工过程系统综合问题是典型的混合整数规划( m i x e d - i n t e g e r p r o g r a m m i n g , m i p ) 问题，随着过程系统研究的规模越来越大，综合问题变得越来越复杂，其 求解变得更加困难。混合整数规划问题的求解己成为目前研究的热点与难点。 为此，本文试图提出一种有效的混合算法用于求解化工过程系统中的m 口问题。 本文提出了基于列队竞争算法( l i n e a r - u pc o m p e t i t i o n a l g o r i t h m ，l c a ) 的 混合算法，它是l c a 与确定性算法的混合。求解策略为两种算法的两层嵌套， 外层应用l c a 优化整形变量，内层应用单纯形法或序y u - - 次规划算法( s e q u e n t i a l q u a d r a t i cp r o g r a m m i n g ，s q p ) 优化连续变量。本文研究了混合算法的结合机理、 实现准则与求解步骤，并通过对测试函数的求解验证了算法的有效性。 将提出的混合算法用于化工过程系统中的m i p 问题的求解，求解了以下三 个方面的问题： ( 1 ) 白酒勾兑问题：建立了一种新的白酒勾兑混合整数线形规划 ( m i x e d i n t e g e rl i n e a rp r o g r a m m i n g ，m i l p ) 模型，用本文提出的混合算法进行 求解，得到了使白酒勾兑成本最低、基酒存储空间利用率最高及操作费用最低 的优化结果； ( 2 ) 多周期操作锅炉蒸汽系统优化调度问题：以操作费用与转运费用之和 最小为目标函数，建立了此问题的混合整数非线性规划( 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 i ) 模型，用本文提出的混合算法进行求解，得到了接近于 文献值的优化结果； ( 3 ) 长输热油管道运行操作优化问题：以热力费用与动力费用之和最小为 目标函数，建立了此问题的混合整数非线性规划( m i n l p ) 模型，用本文提出 的混合算法进行求解，得到略优于文献值的优化结果。 本文提出的基于列队竞争算法的混合算法应用于化工过程系统中的m i l p 及m i n l p 问题的求解，取得了较好的结果，表明了算法的有效性，为化工过程 系统中的m i p 问题的求解提供了一种新的求解算法。 关键词：混合整数规划；化工过程系统；列队竞争算法；混合算法 武汉理工大学硕士学位论文 a b s t r a c t ac h e m i c a lp r o c e s ss y s t e ms y n t h e s i sp r o b l e mi sat y p i c a le x a m p l eo fa m i x e d - i n t e g e rp r o g r a m m i n g ( m 口) p r o b l e m a st h er e s e a r c hs c a l eo ft h ep r o c e s s s y s t e mi n c r e a s e s ，t h es y n t h e s i sp r o b l e mw i l la l s ob e c o m ei n c r e a s i n g l yc o m p l e x ，a n d s o l v i n gt h ep r o b l e mw i l lb e c o m em o r ed i f f i c u l t t h em i pp r o b l e ms o l v i n gm e t h o d h a sb , o m eaw i d e l yr e s e a r c h e dt o p i c t h e r e f o r e ，t h i sa r t i c l ea t t e m p t st op u tf o r w a r d a ne f f e c t i v eh y b r i da l g o r i t h mf o rs o l v i n gc h e m i c a lp r o c e s ss y s t e mp r o b l e m s t h i sp a p e rp r o p o s e dah y b r i da l g o r i t h mb a s e do nt h el i n e a r - u pc o m p e t i t i o n a l g o r i t h m ( l c a ) i ti sl c a m i x e dw i t hd e t e r m i n i s t i ca l g o r i t h m t w os t r a t e g i e sf o r s o l v i n gt h et w o t i e rn e s t i n ga l g o r i t h ma r eu s e d ；i nt h eo u t e rl a y e r , l c ao p t i m i z e i n t e g e rv a r i a b l e sa n di n t h ei n n e rl a y e r ，s i m p l e xm e t h o do rs e q u e n t i a lq u a d m t i c p r o g r a m m i n ga l g o r i t h m ( s q p ) o p t i m i z ec o n t i n u o u sv a r i a b l e s t h i sp a p e rs t u d i e dt h e c o m b i n a t i o nm e c h a n i s m ，i m p l e m e n t a t i o ng u i d e l i n e sa n dp r o b l e ms o l v i n gs t e p so ft h e h y b r i da l g o r i t h m ，a n dt h r o u g hs o l v i n gt h e c e r t i f i c a t i o nf u n c t i o n st e s t e d t h e e f f e c t i v e n e s so ft h ea l g o r i t h m t h eh y b r i da l g o r i t h mw a su s e df o r t h es o l u t i o no fm 口p r o b l e m si nt h ec h e m i c a l p r o c e s ss y s t e m ，f o rt h ef o l l o w i n gt h r e ea s p e c t s ： ( 1 ) l i q u o rb l e n d i n gp r o b l e m ：an e wl i q u o rb l e n d i n gm i x e d - i n t e g e r l i n e a r p r o g r a m m i n g ( m i l p ) m o d e lw a s e s t a b l i s h e da n du s i n gt h eh y b r i da l g o r i t h m p r o p o s e di nt h i sp a p e rs o l v e dt h em o d e la b t a i n i n gt h em i n i m u ml i q u o rb l e n d i n gc o s t s ， m a x i m u mu t i l i z a t i o no fb a s el i q u o rs t o r a g es p a c ea n dt h el o w e s to p e r a t i n gc o s t ； ( 2 ) o p t i m i z a t i o ns c h e d u l i n gp r o b l e mo fam u l t i - c y c l eb o i l e rs t e a ms y s t e m o p e r a t i o n ：t a k i n gl o w e s to p e r a t i n gc o s t sa n dt r a n s i te x p e n s e sa so b j e c t i v ef u n c t i o n ； e s t a b l i s h e dam i x e d - i n t e g e rn o n l i n e a rp r o g r a m m i n g ( m l n l p ) m o d e lf o rt h ep r o b l e m a n ds o l v e dt h em o d e lu s i n gt h eh y b r i da l g o r i t h m t h eo p t i m i z a t i o nr e s u l to b t a i n e d w a sc l o s e rt ot h a tq u o t e di nl i t e r a t u r e ( 3 ) l o n gd i s t a n c e h o to i l p i p e l i n eo p e r a t i o no p t i m i z a t i o np r o b l e m ：t a k i n g l o w e s tf u e lc o s t sa n dp o w e re x p e n s e sa so b j e c t i v ef u n c t i o n ；e s t a b l i s h e dam i n l p l i 亟堡里三盔堂竺主兰垡笙茎 m o d e lf o rt l l e p r o b l e ma n d s o l v e dt h em o d e lu s i n gt h eh y b r i da l g o r i t h m t h e o p t i m i z a t i o nr e s u l to b t a i n e dw a ss l i g h t l yb e t t e rt h a nt h a tq u o t e di nl i t e r a t u r e t h e h y b r i da l g o r i t h mb a s e do nt h el i n e a r - u pc o m p e t i t i o na l g o r i t h mp r o p o s e d i nt h i sp a p e rf o rs o l v i n gm i l pa n dm i n l pp r o b l e m si nc h e m i c a lp r o c e s ss y s t e m a c h i e v e dg o o dr e s u l t s , s h o w i n gt h e e f f e c t i v e n e s so ft h eh y b r i da l g o r i t h m t h e a l g o r i t h mc a n b eu s e da san e w a l g o r i t h mf o rs o l v i n gm i pp r o b l e m s k e y w o r d s ：m i x e d - i n t e g e rp r o g r a m m i n g ；c h e m i c a lp r o c e s ss y s t e m s ；l i n e a r - u p c o m p e t i t i o na l g o r i t h m ；h y b r i da l g o r i t h m 1 l 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名：庄慧硷r 期：独立：! ! ：! 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：左叁垒 导师签名： 日期：州f 2 | ( 注：此页内容装订在论文扉页) 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 为研究化工过程系统中的混合整数规划( m i x e d - i n t e g e rp r o g r a m m i n g , m i p ) 问题，本文从化工过程系统综合问题中的m m 问题着手。化工过程系统综合是 化工过程系统的核心问题【1 j 它着重考虑在给定进料和产出要求的前提下，考虑 固定投资和操作费用、产品质量、环境目标、安全和可操作性等判据，确定优 化过程流程，以最有经济效益的方式将进料转化为产品【2 】。其研究内容主要【3 l 有： 反应路径与反应网路综合( r e a c t o rn e t w o r k s ) 1 4 5 1 ，分离序列综合( d i s t i l l a t i o n s e q u e n c i n g ) 【叨，换热器网络综合( h e a te x c h a n g en e t w o r ks y n t h e s i s ) 【8 9 1 ，公 用工程系统综合( u t i l i t ys y s t e m s ) 1 0 , 1 1 】，质量集成网络( m a s se x c h a n g en e t w o r k ) 1 2 1 和全流程综合( p r o c e s sf l o w s h e e ts y n t h e s i s ) 1 3 l 。 化工过程系统综合常通过对过程系统超级结构的分析，建立其相应的数学 模型，一般为混合整数规划( m 口) 模型，其数学表达式如下： n l i n c = f ( x ，y ) j j g ，y ) 0 h ( x ，y ) = 0 x r “= 工i 矿z 工” y 0 ，1 ，” 其中x 为竹维连续变量，表示系统的操作参数或设计参数，其上、下界为， ；y 为m 维0 1 变量，表示系统中可能存在的过程单元取舍的结构参数；目 标函数c f ( x ，y ) 一般为变量x ，y 的线性或非线性函数，表示所追求的目标，通 常取系统的总费用最小或总收益最大；等式或不等式约束方程表示超结构必须 满足的物料平衡、能量平衡、物理性能约束、设计规定以及逻辑条件等约束。 根据模型的线形或非线性特性，可以将混合整数规划( m i p ) 问题分为混合 整数线性规划( m i x e d - i n t e g e rl i n e a rp r o g r a m m i n g ，m i l p ) 问题和混合整数非线 性规划( m i x e d i n t e g e rn o n - l i n e a rp r o g r a m m i n g ，m i n l p ) 问题。化工过程系统 综合问题大多为m i n l p 问题，对m i n l p 问题的求解，由于函数的非凸性、或 武汉理工大学硕士学位论文 存在很多极值点，很难得到优解。下面对目前m i n l p 问题的求解算法做简要介 绍。 1 2 化工过程系统的m i n l p 算法简介 化工过程系统的m i n e p 问题的求解算法基本上可以分为两类：确定性算法 ( 经典方法) 和现代优化算法。求解m i n l p 问题的确定性算法主要有广义 b e n d e r s 分解法( g e n e r a l i z e db e n d e r sd e c o m p o s i t i o n ，g b d ) 、分枝定界法( b r a n c h a n db o u n d m e t h o d ，b b ) 及外逼近法( o u t e r a p p r o x i m a t i o n ，o a ) 等；求解m i n l p 问题的现代优化算法主要有遗传算法( g e n e r i ca l g o r i t h m ，g a ) 、模拟退火法 ( s i m u l a t i o n a n n e a l i n g a l g o r i t h m ，s a ) 、禁忌搜索法( t a b us e a r c h a l g o r i t h m ，t s ) 及列队竞争算法( l i n e a r - u pc o m p e t i t i o na l g o r i t h m ，l c a ) 等。 1 2 1 求解m i n l p 问题的确定性算法简介 1 2 1 1 分支定界法( b r a n c ha n db o u n dm e t h o d ，b b ) 【1 4 l m i n l p 问题的分支定界法与m i l p 的分支定界法相似，第一步先对整数条 件进行松弛，求解松弛后的连续型n l p 问题；若得到的解满足整数条件，即为 原问题的最优解；否则松弛的n l p 问题的解提供了原问题最优解的一个下界( 对 极小化问题而言) 并连续执行一个树枚举，其中在每一个节点上对应一个n l p 问题，这里有些整变量取固定值，而其他整变量松弛为在【o ，l 】上取值的连续变 量，这样在每个节点上对应的n l p 阃题的解提供原m i n l p 问题目标值的一个 上界，目标值超过该上界的所有节点予以删除，并进一步搜索下一分支，直到 得到最优解。 分支定界法的优化策略在对所有节点的树枚举中只搜索其中的一部分，节 点即可得到最优解。但对大规模问题所要枚举的节点数目很大，每一节点都涉 及一个大规模n l p 问题的求解，这个子问题不能像m i l p 中l p 子问题那样有效 地改进，势必造成了计算费用时间的提高。 武汉理工大学硕士学位论文 1 2 1 2 广义b c n d c 侣分解法( g e n e r a l i z e db e n d e r sd e c o m p o s i t i o nm e t h o d ，g b d ) 【1 5 ，1 6 l 广义b e n d e r s 分解法通过划分变量将问题分解进行求解。g b d 法求解 m i n l p 时是将变量划分为若干组复杂变量和非复杂变量( m i n l p 模型中的0 - 1 变量一般认为是复杂变量) ，将m i n l p 问题分解为交替求解的n l p 子问题和 m i l l 主导问题。n l p 子问题是原m i n l p 问题中所有0 1 变量取一组固定值时 对应的连续型优化问题，其最优解为原问题的解提供一个上界；m i l p 主导问题 是在简约的复杂变量空间中由原问题投影得到的，b e n d e r s 分解法求解m i l p 问 题时，也是将连续变量和整形变量分开，利用线性规划可行解表示定理，把原 问题转化和分解为若干子问题，通过求解一系列子问题导出原问题的解。 m i l p 主导问题为后续的n l p 子问题给出一组新的整数变量值。当原问题 为凸规划时，主导问题为原问题的解提供一个下界，该下界对每个主循环而言 是单调增加的。当上、下界等于( 或大于) 当前上界时，过程收敛，最优解由 这个界给出。这种方法所需的迭代次数一般很大，也需求解大型n l p 问题，同 样需要较大的计算成本。 1 2 1 3 外逼近法( o u t e r - a p p r o x i m a t i o na l g o r i t h m ，o a ) 【1 6 ，1 7 1 外逼近法是由d u r a n 和g r o s s m a n n 提出的，在算法上与g b d 法基本相同， 即将m i n l p 问题分解为交替求解的n l p 子问题和m i l p 主导问题，分别提供原 问题解的一个上、下界。与g b d 法不同之处在于m i l p 主导问题的给出是基于 连续可行域的外部近似，这些外部近似是通过在0 - l 变量取固定值的n l p 子问 题的解点上的函数线性逼近获得的。相对于g b d 法而言，外逼近主导问题为原 问题提供一个较好的下界，因而迭代次数明显减少，求解效率有所提高。另外， m a w e n g k a n 和m u r t a g h 1 8 】还提出一个可行性方法，其主要思想是将松弛的n l p 的解至少园整到一个局部下降的解，这种方法不能保证全局最优，但取得了非 常好的结果。 这类算法的一个共同点是需将问题分解成一系列子问题后再求解，不同之 处只是分解的策略不同。这些算法从理论上可以求解较大规模的一些问题，但 武汉理工大学硕士学位论文 计算时间较长，且对目标函数和约束条件都有一定的特殊要求，当求解的问题 不满足要求时，不能保证搜索到全局最优解。 1 2 2 求解m i n l p 问题的现代优化算法简介 1 2 2 1 遗传算法( g c n e r i c a l 9 0 r i t h m ，g a ) 遗传算法( g a ) 是一类借鉴生物界自然选择和自然遗传机制的随机化搜索 算法，由美国j h o l l a n d 教授提出，其主要特点是群体搜索策略和群体中个体之 间的信息交换，搜索不依赖于梯度信息。遗传算法是以自然选择和生物遗传理 论为基础，模仿大自然生物遗传和进化方式，将自然界生物进化过程中适者生 存规则同一个群体中人工染色体的随机产生、交换相结合的搜索算法，其特点 是在选择、交叉、变异等遗传算子的作用下，充分利用己有的信息作引导，从 一组点向另一组点迭代。它对搜索空闻和目标函数没有特殊要求，适用于不可 微、不连续、非线性、非凸、多峰的复杂优化问题，且具有获得( 接近) 全局 最优解的能力，现已广泛用于组合优化【1 9 j 、机器学习【2 0 l 、自适应控制【2 1 1 、规划 设计、模型识别等领域。 1 2 2 2 模拟退火法( s i m u l a t i o na n n e a l i n g a l g o r i t h m ，s a ) 模拟退火法( s a ) 是一种基于热力学退火原理建立的随机搜索算法。s a 算 法的思想最早是由m e t r o p o l i s 于1 9 5 3 年提出的1 2 4 1 ，后来由k i r k p a t r i c k 等人研究 发展了s a 算法的理论瞵l 。由于s a 算法它综合利用了m o n t ec a r l o 法和爬山法 来解决优化问题，可避免陷入局部最优，因此它能成功地用于解旅行商问题和 v l s i 布局等大型组合优化问题，目前s a 算法已扩展到解连续变量的优化问题。 在化工领域s a 算法已用于管路综合1 2 6 1 ，换热网络综合1 2 ”们，分离序列综合1 3 0 l 、 反应网络的综合f 3 1 j 和多产品化工间歇过程最优设计与调度1 3 2 钏等问题的求解， 并取得了满意的结果。 该算法的显著特点是它在搜索最优解过程中，按照m e t r o p o l i s 准则：不仅接 受优化解，而且以一定概率接受使目标函数值增大的恶化解，并且此概率缓慢 趋于零，这使得算法能跳出局部最优的“陷阱”，具有全局收敛性。模拟退火算 法的主要不足是计算时间过长，一方面由于要产生一个可行解需要多次搜索， 4 武汉理工大学硕士学位论文 另一方面是退火算法本身需要合理的算法参数，而这些参数又很难精确给定： 退火太快，导致局部最小值；退火太慢，变为盲搜索。由于涉及大量的试探法， 其计算效率较低。 1 2 2 3 禁忌搜索法( t a b us e a r c h a l g o r i t h m ， i s ) 禁忌搜索法( 鸭) 的思想最早由g l o v e 0 3 5 3 6 l 提出，是一种全局逐步寻优算 法，是对人类智力过程的一种模拟，是局部领域搜索的一种扩展。它最重要的 思想是通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通 过特赦准则来赦免一些被禁忌的良好状态，进行保证多样化的有效搜索以最终 实现全局最优。禁忌搜索涉及到邻域、禁忌表、禁忌长度、候选解、特赦准则 等一些关键概念。t s 刚开始是为了组合优化算法问题而提出的，并在组合优化 领域得到了迅速地发展。t a b u 搜索法的主要问题是列表的大小( 控制参数) 不 易确定。一般来说，太小的列表可能无法避免搜索路径的往返重复，这将影响 算法的全局搜索性能；另一方面，列表过大除了增加计算时空复杂度外，还可 能因列表对搜索区域的过分限制，而使t a b u 搜索法难以接近最优解的近旁，这 又从另一个方面影响算法的全局搜索性能。所以在实际应用中，需要对列表进 行调整。 1 2 2 4 列队竞争算法( l i n e a r - u pc o m p e t i t i o n a l g o r i t h m ，l c a ) 列队竞争算法( l c a ) 是一种群体搜索的进化算法，是由武汉理工大学鄢 烈祥教授提出来的。它在求解非凸非线性规划和混合整数非线性规划及组合优 化的全局最优解方面具有优良的特性，该方法已成功应用于求解经典的旅行商 组合优化问题【”j 踟。在化工过程系统方面，已成功用于求解大规模管路网络综合 【3 9 1 、分离序列综合、换热网络综合【4 1 4 2 l 等问题，并取得了较好的效果。 列队竞争算法是一种群体搜索过程，与进化算法的基本机制相似，主要的 区别在于列队竞争算法在进化过程中始终保持着独立并行进化的家族，每个家 族仅有一个个体，通过无性繁殖产生后代。此外，在竞争机制上与进化算法完 全不同。在列队竞争算法中有两个竞争水平，一个是纵向竞争，系指同一家族 内繁殖的子代为生存进行的竞争，只有一个最优秀个体能够生存，它代表这个 家族：另一个是横向竞争，指不同家族之间的地位竞争，根据各个家族目标函 武汉理工大学硕士学位论文 数值的大小排列成一个列队，最优秀的家族排在列队的首位，最差的排在末位。 通过上述两个水平的竞争，使列队中的首位家族不断地被其他家族所取代或其 值被更新，以此快速地向最优点逼近。为使每个家族有同等的机会到达列队的 首位，这里赋予每个家族一个竞争推动力。竞争推动力是促使家族变异的动力， 是使家族改变自身状况而具有赶上或超过它前面家族的一种潜在力量。对于不 同的优化问题，具有不同的表达形式，对于连续变量的优化问题，竞争推动力 为搜索子空间大小，而对于组合优化问题，它为个体在搜索空间中的迁移距离。 列队竞争算法的求解步骤及计算框图图1 - 1 如下： ( 1 ) 在搜索空间内均匀分布产生p 个个体( 代表p 个家族) ，组成初始解 群，并计算各个个体的目标函数值。 ( 2 ) 按目标函数的大小，对p 个个体排序( 求全局最小值时，采用升序； 求全局最大值时，用降序) 。 ( 3 ) 根据各个个体在列队中的位置，按一定比例确定其相应的搜索空间， 处于第1 位的搜索空间最小，处于最末位的搜索空间最大。 ( 4 ) 每个个体在各自的搜索空间内进行无性繁殖，产生口个尽可能均匀分 散的子代个体，口个子代与其父代进行生存竞争，将其中最优秀的一个个体保留 下来，代表它所属的家族，参加下次列队地位的竞争。 ( 5 ) 搜索空间收缩或者是代表迭代步骤的参数递增1 ，然后，转到第2 步。 终止条件：搜索空间收缩到接近于一点或达到设定的最大迭代步骤。 这些算法的共同特征是： ( 1 ) 都是全局优化方法，即都具有发现全局最优解的能力； ( 2 ) 都对目标函数的要求很低，不要求目标函数可导，不要求目标函数连 续，甚至不要求目标函数存在显式的表达，只需要给出一定的参数配置，能够 求得目标函数值即可； ( 3 ) 算法的框架都很简单，通用性强。 在这些算法中，列队竞争算法具有结构简单、全局收敛能力强、通用性强 的特点，在多个应用领域得到广泛地使用，被认为是很有研究前景的算法之一。 武汉理工大学硕士学位论文 随机产生p 个家族，计算且标函数值 7 对p 个家族捧序( 家族问列队地位竞争) j r l收缩搜索空间 分配搜索子空间或变异程度( 竞争推动力) i 家族内无性繁殖，生存竞争( 家族内生存竞争) n i i ：* - 霜f 厶审4 。 地化刊茸f 疋代最 回 图1 - 1 列队竞争算法计算框图 1 3 本论文的研究内容 化工过程系统中的m i p 问题的求解随着过程系统研究的规模越来越大，综 合问题变得越来越复杂，其求解更加困难，研究新的算法用于化工过程系统中 的m 口问题的求解越来越受到人们的重视。为此，本文提出了一种混合算法用 于混合整数规划问题的求解，为化工过程系统中的m 口问题的求解提供一种新 的有效算法。 本文研究的内容主要有以下几个方面： ( 1 ) 研究基于列队竞争算法的混合算法结合机理与求解策略，给出算法的 求解步骤与计算框图；研究初始设定参数对混合算法的影响，并通过测试验证 算法的有效性； ( 2 ) 提出的混合算法在白酒勾兑问题中的应用，建立一种新的白酒勾兑混 合整数线形规划( m i l p ) 模型，并用本文提出的混合算法进行求解，得到使白 酒勾兑成本最低、基酒存储空间利用率最高及操作费用最低的优化结果： ( 3 ) 提出的混合算法在多周期操作锅炉蒸汽系统优化调度问题中的应用， 以操作费用与转运费用之和最小为目标函数，建立此问题的混合整数非线性规 武汉理工大学硕士学位论文 划( m i n l p ) 模型，并用本文提出的混合算法对模型进行求解； ( 4 ) 提出的混合算法在长输热油管道运行操作优化问题中的应用，以热力 费用与动力费用之和最小为目标函数，建立此问题的混合整数非线性规划 ( m i n l p ) 模型，并用本文提出的混合算法对模型进行求解。 武汉理工大学硕士学位论文 第2 章基于列队竞争算法的混合算法研究 2 。1 引言 通过对一般混合整数规划( m m ) 模型的分析，可以知道一旦给定混合整数 规划模型的整型分量，那么模型就可以转化为一个普通的线性或非线性规划问 题。针对这个特性，提出了一种具有两层嵌套构架的基于列队竞争算法的混合 算法，并分别为混合整数线性规划( m i l p ) 问题及混合整数非线性规划( m i n l p ) 问题的求解给出了与列队竞争算法结合的线性与非线性规划算法。 本文从混合算法的结合机理、实现准则、性能测试三个方面进行了研究， 遵循列队竞争算法的求解思想，为混合算法提出了新的繁殖、排序、终止准则， 实现混合算法对混合整数规划问题的求解。 2 2 基于列队竞争算法的混合算法研究 2 2 1 混合算法的结合机理 混合整数规划( m 口) 问题一般可以定义为如下形式： m i n 厂 ，) ，) s j a 茗+ c y 量b a e q 茗+ c e q y b e q 瑰o ，y ) 一o , i 一1 ，2 ，j g ，0 ，y ) s o , j - 1 ，2 ，f ( 2 1 ) p i ( y ) s o , km 1 ，2 ，口 x l b x 董x 一曲 y e 0 ，1 t “ 其中，y 为m 维0 - 1 整型变量( 其他整型变量可以通过变换转化为这种0 - 1 整型形式) ，x 为n 维连续向量，x ；【x l ，而，】，其上限为： xu b i x u b l ，工一u b ：，x u b 】，其下限为：x l b - i x l b , ，x 一峨，一，石一l b 】。 a x + c y b 是m i p 模型线性不等式约束，a e q x + c e q y b e q 是m i p 模型 武汉理工大学硕士学位论文 的线性等式约束；g j ( x ，y ) - 0 代表m i p 模型中非线性不等式约束，而 o ，y ) 代 表m i p 模型中非线性等式约束，p ( y ) 代表纯整型约束。 一旦给定y 为y 后，该m i p 模型就可以转化为以下线性规划( l i n e a r p r o g r a m m i n g ，l p ) 或非线性规划( n o n - l i n e a rp r o g r a m m i n g ，n l p ) 模型： m i n f 0 ，广) j j _ 石s b c y a e q x b e q c e q y 噍g ，) ，) 一0 , i - 1 2 ，j j gi b ，y i ) o ，j - 1 , 2 , ，t 工一l b 工j u b 对m i p 问题的求解本文提出了一种基于列队竞争算法的混合算法，这种算 法通过l c a 在外层搜索遍历整型变量组合，在内层采用确定性算法( 在这里用 m d 表示) 对l p 或n l p 问题进行优化获得相应最优连续变量的值。m 口问题的 两层嵌套框图见图2 - 1 ： 。二盖：孟j ： r a i nf ( x , y ) - ；s j g ( x ，y ) s o ；j j l ( x ，y ) 一0 图2 - 1l c a 内嵌m d 求解m i p 问题的双层嵌套图 0 武汉理工大学硕士学位论文 根据求解问题的线性或非线性特征，m i p 问题可以转化为m i l p 问题或 m i n l p 问题。本混合算法在求解m i l l 问题与m i n l p 问题时，其内层采用的方 法是不同的，若为m i l p 问题，m d 为解线性规划的单纯形法；若为m i n l p 问 题，m d 为序列二次规划算法( 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 ，s o p ) 。以下 分别对线性规划的单纯形法和s q p 及采用m a t l a b 数值计算软件的优化运行作简 单的介绍。 2 2 1 1 线形规划的单纯形法 若一个凸集仅包含有限个极点，则称此凸集为单纯形。线性规划的可行域 是单纯形，进而线性规划的基可行解又与线性规划问题可行域的极点一一对应， 线性规划单纯形法就是基于线性规划可行域的这样的几何特征设计产生的。这 个方法最初是在2 0 世纪4 0 年代由g e o r g ed a n t z i g 研究出来的1 4 3 l 。线性规划单纯 形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行 域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如 果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下 降，这样重复进行有限次后，可找到最优解或判断问题无最优解。 线性规划的单纯形法的求解步骤为：( 1 ) 将原问题化为标准形式：( 2 ) 列 出初始单纯形表；( 3 ) 检查检验数；( 4 ) 建立新的基相应的单纯形表。在m a t l a b 的优化工具箱中提供了基于单纯形法求解线性规划问题的函数l i n p r o g ( 1 ，该函 数将线性规划数学模型中的约束条件分为不等式约束、等式约束及变量的取值 范围三部分，即： 目标函数： 约束条件： j f ( z 、一c x a z s b a e q z b e q l b s 工u b 函数l i n p r o g ( ) 的调用格式为： 【x , j m 】| l i n p r o g ( c ，a ，b ，a e q ，b e q ，l b ，u b ，x o , o p t i o n s ) 其中，x 为使目标函数i ，t ，0 ) 为最小值的值；j 。为目标函数i ，的最小值： c 为目标函数的系数向量；a 和b 为不等式约束中的系数矩阵和系数向量：a e q 武汉理工大学硕士学位论文 和b e q 为等式约束中的系数矩阵和系数向量：u b ，l b 分别代表x 的上下界；加 为给定初始解，不给定时加= 【】。若无不等式约束条件，则在函数调度格式中 a = 【】，b = 【】；若无等式约束条件，则在函数调用格式中a e q = 【】，b e q = 【】；若 无边界限制，则在函数调用格式中胁= ，u b = 【】。 2 2 1 2 序列二次规划算法( 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 ，s q p ) 序列二次规划算法( s q p ) 是目前应用最为广泛、最为有效的非线性优化算 法之一，其强大的非线性处理性能和良好稳定性在处理中小规模优化命题中得 到广泛认可。该算法本质上是一种迭代算法，其基本思想是在给定的近似点处 通过二次近似逐渐得到一个更好的迭代点，这需要通过求解一个二次规划 ( q u a d r a t i cp r o g r a m m i n g ，q p ) 子问题得到，在当前迭代点处算法通过求解一系 列的二次规划子问题，使得迭代点逐步接近原优化命题的最优点，算法最终收 敛到最优解处【删。 s q p 具有以下优点：强大的非线性处理能力；非常适用于约束优化问题求 解；采用拟牛顿方法计算搜索方向，不需要二阶导数信息；不需要初始可行解； 具有快速收敛性甚至超线性收敛性；稳定性好，鲁棒性强。m a t l a b 对s q p 的实 现分三步：( 1 ) 拉格朗同函数h e s s i a n 矩阵的更新；( 2 ) 二次规划问题求解：( 3 ) 一维搜索和目标函数的计算。在m a t l a b 工具箱中用s q p 求解的函数为 f m i n c o n ( ) ，该函数将非线性规划数学模型中的约束条件分为不等式非线性约束、 等式非线性约束、不等式线性约束、等式线性约束及变量的取值范围五部分， 即： 目标函数：j = ，o ) 约束条件：c “) s 0 c e q o ) 一0 a 工b a e q x b e q l b s zs u b 函数f m i n c o n ( 1 的调用格式为： 【x ，j m = f m i n c o n ( f u n ，加，4 ，b ，a e q ，b e q ，l b ，u b ，n o n l c o n ，o p t i o n s ) 武汉理工大学硕士学位论文 其中，x 为使耳标函数，一f ( x ) 为最小值的值；_ r 。为目标函数，的最小值； a 和口为不等式约束中的系数矩阵和系数向量；a e q 和b e q 为等式约束中的系数 矩阵和系数向量；曲，f 6 分别代表x 的上下界；x o 为给定初始解，不给定时 x 0 = 。若无不等式约束条件，则在函数调度格式中a = 【】，b = 【】；若无等式约 束条件，则在函数调用格式中a e q = 【】，b e q = 【】；若无边界限制，则在函数调用 格式中l b = 【】，u b 【】。f u n 函数代表目标函数，其形式一般为m 文件，其约束 条件为a 毒b 和a e q z b e q ：n o n l c o n 参数提供非线性不等式约束c ( x ) 或等式 约束c e q o ) ，具体说明如下： n o n l c o n 参数计算非线性不等式约束c ( x ) so 和非线性等式约束c e q 仅) 。0 ， 是一个包含函数名的字符串。该函数可以是m 文件、内部文件或m e x 文件。 它要求输入一个向量石，返回两个变量解z 处的非线性不等式向量c 和非线 性等式向量c e q 。例如，若n o n l c o n 一m y c o n m ，则m 文件m y c o n m 的形式如下： f u n c t i o n 【c ，c c q = m y c o n ( x ) c = c e q = 。 计算x 处的非线性不等式 计算x 处的非线性等式 本文提出的算法将采用m a t l a b 语言编程优化运行，内层优化算法一线性 规划的单纯形法和s o p 在m a t l a b 环境下进行求解时，可以通过数学方法将l j p 或n l p 问题的数学表达式转化为m a t l a b 工具箱函数计算所需的形式，便可调用 相应的函数对问题进行求解。结合图2 1 ，则基于列队竞争算法的混合算法 l c a & m d 能否很好实现，关键就在于如何根据l c a 的求解思想，提出新的繁 殖、排序及终止方法。为此，本文为l c a & m d 算法设计了一些基本实现准则， 使其能够有效的求解混合整数规划问题。 2 2 2 混合算法的实现准则 2 2 2 1 繁殖 列队竞争算法的繁殖是最大差异性无性繁殖，相当于在以某点为中心所确 定的搜索空间内产生均匀分散的点，这些分散的点被认为是这个搜索空间内中 心点的后代。在特定的区域内产生均匀分散点有两种方法：一种是确定型的方 武汉理工大学硕士学位论文 法，另一种是随机型的方法。在确定型的方法中，当区域和分布模式已定的条 件下，分布点在区域中的位置是完全确定的。而在随机型方法中，由于不存在 固定的分布模式，分布点在空间中的分布位置是随机的，具体过程可以参考文 献【4 5 】。 这里我们运用邻域的概念来进行繁殖，它也是一种随机型方法，是 l c _ 础d d d 算法的核心步骤。对于当前点( 矿，y ) 而言，其邻域是这样定义： 如果点( x ，y )