（市政工程专业论文）给水管网现状分析方法研究.pdf

r e s e a r c ho ft h em e t h o d so fw a t e r - d i s t r i b u t i o nn e t w o r k s s t a t u s a n a l y z i n g a b s t r a c t t h es t a t u s a n a l y z i n go fw a t e r - d i s t r i b u t i o n n e t w o r k si sb a s e do nt h ek n o w n p r e s s u r ea n dq u a n t i t yo fw a t e rs o u r c e s t h ea i di st od e d u c ea l lo f t h en o d eh y d r a u l i c p r e s s u r e sa n dt h ep i p er u n o f f st h r o u g hp a r to ft h en o d eh y d r a u l i cp m s s u r e sa n dt h e p i p er u n o f f s m e a s u r i n gq u a n t i t y s ow e c a ng r a s pt h ew o r kc o n d i t i o no ft h en e t w o r k s a n ds o l v et h ea b n o r m a lp r o b l e m s ，f u r t h e r m o r e ，i tc a np r o v i d ec r e d i b l ef o u n d a t i o nt o a _ 【t e m p m ro p t i m i z a t i o na n de n l a r g e ，r e c t i f y t h en e t w o r k s f i r s t l y , t h i sp a p e re x p a t i a t e st h ec o n t e n ta n ds e n s eo ft h es t a t u sa n a l y z i n go f w a t e rd i s t r i b u t i o n n e t w o r k s s e c o n d l y i ti n t r o d u c e sg e n e t i c a r i t h m e t i c ( g a ) a n d g e n e r a lr e d u c e dg r a d i e n t m e t h o d ( g r g ) ，a n d t h e s et w om e t h o d sb o t hh a v e s u p e r i o r i t y a n dl i m i t a t i o n a f t e r w a r d s ，a h y b r i dg e n e t i ca r i t h m e t i c ( h g a ) i sp u t f o r w a r d ，w h i c hc o m p o s e sg r ga n dg a i t sm a t h e m a t i c a lm o d e l ，t h em e t h o do f r e a l i z i n g a n d t h em e t h o do f d e t e r m i n i n g t h ei m p o r t a n t p a r a m e t e r sa l ea l li n t r o d u c e d i n t h i s p a p e r a f t e rt e s t i f y i n g t h i sn e wm e t h o d s f e a s i b i l i t yb yu s i n gi t i na s i m p l e w a t e r - d i s t r i b u t i o nn e t w o r k ，w ea n a l y z et h es t a t u so ft h en e t w o r ka r o u n dt h en e w r a i l w a y s t a t i o ni na c i t ya n dg e tp r e f e r a b l e r e s u l t k e y w o r d s ：s t a t u sa n a l y z e g e n e r a lr e d u c e dg r a d i e mm e t h o d ( g r g ) g e n e t i ca r i t h m e t i c ( g a ) h y b r i d g e n e t i ca r i t h r n e t i c ( h g a ) 第一章绪论 1 1 给水管网现状分析的目的和内容f 岫i i i 随着用水规模的不断扩大及管道使用年限的增长，城市给水管网逐渐暴露 出一些问题，例如各水源间不合理调度引起管网压力过高，造成能量浪费，甚 至引起爆管问题：管道淤积结垢，阀门未正常开启使管道摩阻增大，管网压力 局部降低；管道锈蚀；接1 2 处漏水造成水资源浪费；管网水量、水压不足等问 题。通过进行给水管网现状分析，可以准确掌握管网工况，及时发现并解决管 网运行中存在的漏水、爆管、堵塞等异常问题，以减少水资源浪费并提高供水 的安全性和可靠性，还可发现由于各水源间不合理调度引起的部分地区水压过 高问题，以减少能量浪费，其结果可为管网优化调度，改、扩建提供可靠依据。 给水管网现状分析与管网乎差、优化设计、优化调度同属于管网水力计算 的范畴，但其研究对象各有不同。详见表1 一l 。 表i 一1 几种管网水力计算比较 皴 节点流量节点水压水源压力测压、测流 类别 管径管长 管线摩阻管段流量供水量点量测值 管网平差已知已知假设待求已知 优化计算待求已知假设待调整已知 优化调度已知已知已知已知待求 现状分析已知已知待求待求已知已知 它们各自的研究对象是不同的。管网平差是在管径、管长及水源压力和供 水量已知，假定节点流量、管道摩阻的条件下，求解各节点的供水压力；优化 设计计算是在管网布置确定，假定节点流量和管道摩阻的条件下，求解各管段 的管径和水源供水压力，同时对初分的管段流量进行调整；优化调度是在管网 布置已定，通过对用水量的预测，确定各水源的供水量和供水压力：而管网现 状分析是在水源的供水压力和供水量已知的条件下，通过部分节点、管段的水 压、流量的实际量测值来推断节点流量、管线摩阻，从而得到所有的节点水压 和管段流量值。 1 2 给水管网现状的特点0 3 i 城市供水管网处于建设中。一方面，管道敷设在地下，由于管理人员经常 变更导致基础资料不祥：另一方面，随着使用年限的增长，管网的结构参数 第一章绪论 1 1 给水管网现状分析的目的和内容f 岫i i i 随着用水规模的不断扩大及管道使用年限的增长，城市给水管网逐渐暴露 出一些问题，例如各水源间不合理调度引起管网压力过高，造成能量浪费，甚 至引起爆管问题：管道淤积结垢，阀门未正常开启使管道摩阻增大，管网压力 局部降低；管道锈蚀；接1 2 处漏水造成水资源浪费；管网水量、水压不足等问 题。通过进行给水管网现状分析，可以准确掌握管网工况，及时发现并解决管 网运行中存在的漏水、爆管、堵塞等异常问题，以减少水资源浪费并提高供水 的安全性和可靠性，还可发现由于各水源间不合理调度引起的部分地区水压过 高问题，以减少能量浪费，其结果可为管网优化调度，改、扩建提供可靠依据。 给水管网现状分析与管网乎差、优化设计、优化调度同属于管网水力计算 的范畴，但其研究对象各有不同。详见表1 一l 。 表i 一1 几种管网水力计算比较 皴 节点流量节点水压水源压力测压、测流 类别 管径管长 管线摩阻管段流量供水量点量测值 管网平差已知已知假设待求已知 优化计算待求已知假设待调整已知 优化调度已知已知已知已知待求 现状分析已知已知待求待求已知已知 它们各自的研究对象是不同的。管网平差是在管径、管长及水源压力和供 水量已知，假定节点流量、管道摩阻的条件下，求解各节点的供水压力；优化 设计计算是在管网布置确定，假定节点流量和管道摩阻的条件下，求解各管段 的管径和水源供水压力，同时对初分的管段流量进行调整；优化调度是在管网 布置已定，通过对用水量的预测，确定各水源的供水量和供水压力：而管网现 状分析是在水源的供水压力和供水量已知的条件下，通过部分节点、管段的水 压、流量的实际量测值来推断节点流量、管线摩阻，从而得到所有的节点水压 和管段流量值。 1 2 给水管网现状的特点0 3 i 城市供水管网处于建设中。一方面，管道敷设在地下，由于管理人员经常 变更导致基础资料不祥：另一方面，随着使用年限的增长，管网的结构参数 也发生了变化。因此，供水管网系统的工况是未知的，突出的表现在以下方面。 ( 1 )新旧管道并存，管网结构错综复杂。 ( 2 )管网结构参数如比阻和内径受敷设年代、内壁腐蚀、管内沉积及管材等 因素影响属未知。如某市1 9 9 4 年管径为4 0 0 m m 的管道爆管后，内壁有粉末状 及块状的锈斑，厚度约2 5 3 7 c m ；锈斑沿管长分布不均匀。 ( 3 )实际管网节点流量具有随机性和时变性，难以跟踪实测，但节点流量是 推求其它变量的基本变量，若估算不准，会产生较大误差。 ( 4 )限于经济条件，管网监测点不多，加上运行中流态随机变化，流速和水 压不稳定，存在量测误差，因此管网反馈信息不完善。 ( 5 )管网基础资料量大而杂乱，加之资料的补充更新常常滞后于建设，一些 基础资料不祥。因此，必须对现有资料进行大量的调查、核实、补充。此外， 还要进行现场测试，测定总用水量变化曲线及各类大用户的用水量变化曲线、 水泵特性曲线、典型管道的比阻等。 ( 6 )长期以来，将供水管网图形、文字、数据等信息作为档案管理，工作效 率低下，且易出差错，必须采用微机管理。为此，可以利用供水系统综合信息 管理系统将各类信息如图形、文字和数据输入计算机，对基础资料进行输入、 存储、添加、删除、查询、修改及输出等操作管理，以提高工作效率。 1 3 给水管网现状分析研究现状 给水管网现状分析研究较其它管网计算如管网平差和优化计算尚且不多， 一些城市如上海、深圳、苏州等己建立起给水管网模型进行管网现状工况分析。 常用方法有现状平差法、遗传算法和广义简约梯度法。 现状平差法 4 1 是通过实测与经验得出节点流量和管线摩阻，然后转化为管 网平差问题求解节点水压与管段流量，再与实测值相比较得知管网工况。由于 节点流量和管段摩阻均很难准确确定，此方法常导致平差计算结果与实际值存 在较大偏差，以致现状分析得出错误的结论。 在文献【1 】中，王荣和等提出通过以节点流量和管线摩阻为控制变量的非线 性规划来进行管网现状分析，并以遗传算法( g a ) 求解，得到较好的效果。但由 于遗传算法中随机抽取样本，存在偶然性，有时对部分节点或管段提供的结论 并不准确，只能达到8 0 的准确率，而且对管网末梢的树状管段和节点，也不 能正确控制。由于遗传算法局部收敛能力较差，对于大、中型管网，计算时间 很长，且很难逼近最优解。 而文献 2 】则尝试采用求解非线性规划的有效方法一一广义简约梯度法 ( g r g ) 来求解，其基本思想是利用简约梯度构造一个使目标函数改善的可行方 向，然后沿此方向进行搜索，找出一个更优点，从而逐步逼近最优解a 此方法 具有很强的局部收敛能力，但全局搜索能力欠佳，对于多峰值的规划问题，很 也发生了变化。因此，供水管网系统的工况是未知的，突出的表现在以下方面。 ( 1 )新旧管道并存，管网结构错综复杂。 ( 2 )管网结构参数如比阻和内径受敷设年代、内壁腐蚀、管内沉积及管材等 因素影响属未知。如某市1 9 9 4 年管径为4 0 0 m m 的管道爆管后，内壁有粉末状 及块状的锈斑，厚度约2 5 3 7 c m ；锈斑沿管长分布不均匀。 ( 3 )实际管网节点流量具有随机性和时变性，难以跟踪实测，但节点流量是 推求其它变量的基本变量，若估算不准，会产生较大误差。 ( 4 )限于经济条件，管网监测点不多，加上运行中流态随机变化，流速和水 压不稳定，存在量测误差，因此管网反馈信息不完善。 ( 5 )管网基础资料量大而杂乱，加之资料的补充更新常常滞后于建设，一些 基础资料不祥。因此，必须对现有资料进行大量的调查、核实、补充。此外， 还要进行现场测试，测定总用水量变化曲线及各类大用户的用水量变化曲线、 水泵特性曲线、典型管道的比阻等。 ( 6 )长期以来，将供水管网图形、文字、数据等信息作为档案管理，工作效 率低下，且易出差错，必须采用微机管理。为此，可以利用供水系统综合信息 管理系统将各类信息如图形、文字和数据输入计算机，对基础资料进行输入、 存储、添加、删除、查询、修改及输出等操作管理，以提高工作效率。 1 3 给水管网现状分析研究现状 给水管网现状分析研究较其它管网计算如管网平差和优化计算尚且不多， 一些城市如上海、深圳、苏州等己建立起给水管网模型进行管网现状工况分析。 常用方法有现状平差法、遗传算法和广义简约梯度法。 现状平差法 4 1 是通过实测与经验得出节点流量和管线摩阻，然后转化为管 网平差问题求解节点水压与管段流量，再与实测值相比较得知管网工况。由于 节点流量和管段摩阻均很难准确确定，此方法常导致平差计算结果与实际值存 在较大偏差，以致现状分析得出错误的结论。 在文献【1 】中，王荣和等提出通过以节点流量和管线摩阻为控制变量的非线 性规划来进行管网现状分析，并以遗传算法( g a ) 求解，得到较好的效果。但由 于遗传算法中随机抽取样本，存在偶然性，有时对部分节点或管段提供的结论 并不准确，只能达到8 0 的准确率，而且对管网末梢的树状管段和节点，也不 能正确控制。由于遗传算法局部收敛能力较差，对于大、中型管网，计算时间 很长，且很难逼近最优解。 而文献 2 】则尝试采用求解非线性规划的有效方法一一广义简约梯度法 ( g r g ) 来求解，其基本思想是利用简约梯度构造一个使目标函数改善的可行方 向，然后沿此方向进行搜索，找出一个更优点，从而逐步逼近最优解a 此方法 具有很强的局部收敛能力，但全局搜索能力欠佳，对于多峰值的规划问题，很 容易陷入局部最优解。 1 4 本课题研究的意义 本文在总结前人给水管网现状分析方法的基础上，提出一种集广义简约梯 度法( g r o ) 和遗传算法( g a ) 于一体的混合式遗传算法( h g a ) ，针对给水管网现 状分析数学模型中目标函数、约束条件均可微且较易求得的特点，在遗传算法 全局搜索的基础上加以沿负梯度方向的搜索，咀提高其局部搜索能力，很快达 到全局最优解。通过实例证明，此方法无须复杂的编码、解码，无须给定初始 值，能较快搜索到全局最优解，对于给水管网现状分析课题，可得到较准确的 节点流量和管段摩阻估计值，从而较好的模拟管网工况。并且此方法可推广到 管网优化计算等其它优化问题中，是一种较好的优化方法。 容易陷入局部最优解。 1 4 本课题研究的意义 本文在总结前人给水管网现状分析方法的基础上，提出一种集广义简约梯 度法( g r o ) 和遗传算法( g a ) 于一体的混合式遗传算法( h g a ) ，针对给水管网现 状分析数学模型中目标函数、约束条件均可微且较易求得的特点，在遗传算法 全局搜索的基础上加以沿负梯度方向的搜索，咀提高其局部搜索能力，很快达 到全局最优解。通过实例证明，此方法无须复杂的编码、解码，无须给定初始 值，能较快搜索到全局最优解，对于给水管网现状分析课题，可得到较准确的 节点流量和管段摩阻估计值，从而较好的模拟管网工况。并且此方法可推广到 管网优化计算等其它优化问题中，是一种较好的优化方法。 第二章给水管网现状分析基本理论 2 1 给水管网基本理论” 管网计算的基本原理是保证质量守恒和能量方程，据此可建立节点连续性 方程和能量方程。所谓连续性方程，就是对任一节点来说，流向该节点的流量 必须等于从该节点流出的流量。规定流出节点的流量为正，流向节点的流量为 负，则节点i 的连续陛方程可表示为： 岛+ 吼= 0 ( 2 一1 ) 其中庐为与节点i 相邻的节点号集合，q j ，为管段扩的流量，q ，为节点i 的流量。 能量方程表示管网每一环中各管段的水头损失总和等于零。一般规定水流 顺时针方向的管段，水头损失为正，逆时针方向的为负。则第_ ，环的能量方程 可表示为： y h z = 0 ( 2 - 2 ) 篙。 其中9 为组成环的管段号集合， ，为管段，的水头损失。 对于任一管网，一其节点数j 、管段数p 和环数三间的关系为： p = j + l 一1( 2 - 3 ) 可列出j 一1 个独立的节点流量方程和三个独立的能量方程，其中h , j 和q 可按水 头损失公式相互转换。给水管网计算中常用的水头损失计算公式有： ( 1 ) 海曾一威廉( a h a z e n ，g s w i l l i a m s ) 公式： ：氅( 2 - 4 ) 2 刁面声 其中l 为管段长度( i n ) ，d 为管径( m ) 。 ( 2 )舍维列夫公式： v21 2 m s i = 0 0 0 1 0 7 南 ( 2 5 ) v 1 2 m s o o 吲z 斋( t + 半】 e ， 其中v 为流速( m s ) ，d 为水管的计算内径( 1 i t ) 。 ( 3 )科尔勃洛克公式： 击卅筹+ 嚣 7 ， 其中兄为阻力系数，k 为绝对粗糙度a 第二章给水管网现状分析基本理论 2 1 给水管网基本理论” 管网计算的基本原理是保证质量守恒和能量方程，据此可建立节点连续性 方程和能量方程。所谓连续性方程，就是对任一节点来说，流向该节点的流量 必须等于从该节点流出的流量。规定流出节点的流量为正，流向节点的流量为 负，则节点i 的连续陛方程可表示为： 岛+ 吼= 0 ( 2 一1 ) 其中庐为与节点i 相邻的节点号集合，q j ，为管段扩的流量，q ，为节点i 的流量。 能量方程表示管网每一环中各管段的水头损失总和等于零。一般规定水流 顺时针方向的管段，水头损失为正，逆时针方向的为负。则第_ ，环的能量方程 可表示为： y h z = 0 ( 2 - 2 ) 篙。 其中9 为组成环的管段号集合， ，为管段，的水头损失。 对于任一管网，一其节点数j 、管段数p 和环数三间的关系为： p = j + l 一1( 2 - 3 ) 可列出j 一1 个独立的节点流量方程和三个独立的能量方程，其中h , j 和q 可按水 头损失公式相互转换。给水管网计算中常用的水头损失计算公式有： ( 1 ) 海曾一威廉( a h a z e n ，g s w i l l i a m s ) 公式： ：氅( 2 - 4 ) 2 刁面声 其中l 为管段长度( i n ) ，d 为管径( m ) 。 ( 2 )舍维列夫公式： v21 2 m s i = 0 0 0 1 0 7 南 ( 2 5 ) v 1 2 m s o o 吲z 斋( t + 半】 e ， 其中v 为流速( m s ) ，d 为水管的计算内径( 1 i t ) 。 ( 3 )科尔勃洛克公式： 击卅筹+ 嚣 7 ， 其中兄为阻力系数，k 为绝对粗糙度a 螽于本文所采胡静滢合式遗传算法鬻送行大量鲢偏墩分遣算，馥求霉强标 函数对节点流量和管段摩阻的广义简约梯度，采用舍维列夫公式和科尔勃洛克 公斌计算难度都太大，敞采用海曾一威廉公式( 2 4 ) 进行计算。 根据所取未知量的不同，管网计算方法一般有三种： ( 1 ) 管段方程法：爨黪段流量g ，为未翔数，需裂出p 个独立方程，霹，一l 拿节点连续毪方程弱令能量方程； ( 2 ) 节点方程法：以节点水压日，或节点集中输入( 或输出) 流量吼为未知数， 根据节点集中流量已知与否，需列出o r l 枷个独立的方程，将流量一水头损 失公式代入节点连续性方程即可； ( 3 ) 环方程法：以环，的校正流量a o ( x ) 代入髓量方程，倭霹褥三个独立方程， 菝露瑶求窭争未翔数。 就联立方程数目( 躐未知数数目) 面言，管段方程法最雾，一般很少采用。 环方程法量少，较适含手工计算，因此以解环方程为主，但环方程法有以下缺 点：首先，环方程中不仅要对管段两端的带点编号，还需对篱段进行编号，并 以邂当的方式将其与棚邻的环联系起来。黼此，需要用高维楚薄或两个二维矩 簿黻合寒表示，援嚣臻麓诗算量，簿羝遮雾速度。萁次，当掰予跨痰警瓣臻获 分析时，由于节点流慧并菲全部已翔，篙增加虚环，用虚管段流量代替未知节 点流量以满足所需独立方程的数量，使计算复杂且各节点、鬻敬问的关系变得 不崴观。最后，因为环方程求的是校正流匿，因此在计算前必颁以节点流量平 衡为条件进行流量预分配，无疑会增加凇铸工作和输入的数搬爨。相反，解节 患努程载不存在这耱麓题，苓熹方程法哭爨对节熹寒譬段滋锈镶号，鼓采竭二 缭缀阵即可清楚表永器参数及裙互闫豹关系。其次，节赢方稳数髫在 壬傍猜挽 下不会超过，个，所以总可得到唯一解。最后，节点方程本身包括流量平衡条 件，因此无论管段流擞的初值如何分配，谯反复的迭代过程中始终满足流量平 衡条l 牛m 。 基予鞋上分辑，辩予大型管隧焉言，节点方莛法具秀缀明嚣的往越性，尽 警方程数嚣较环方程滚多，毽对诗雾裁谤黧已不成鞫题。数奉文蒋采爱节点方 程法进行平差计算。 2 2 焓水管髓图论模溅 对于诸如交通图、通讯图、管网图等器式各样静圈，鬈鬻内窖远然不犀， 毽鄂镪含嚣令基本戆黉索：对象窝露象之阕熬菜耪特定关系。入察逶豢嚣一个 点( 节点) 来表示个对象，用点与点之间的连线( 枝或边) 来表示相应对象 之间的特定关系，这种由点和点与点之间逑线组成的称之为图( g r a p h ) 。每一有 向线段及其端点，称之为图的边。有向线段的端点称之为带点。构成闭合路径 或写为 面：0 其中 元= 啊 ：啊，】7 。 管段- ，的水头损失为： h ，= s j 砑 ( 2 一l i ) ( 2 一1 2 ) 2 3 给水管网现状分析数学模型“吖”1 给水管网现状分析，从数学求解的变量来说有两种，即各管段的摩阻系数 s 和各节点的节点流量g 。求解s 值的目的是为相对准确的获得各条管段的摩 阻，以判断管段是否淤积结垢、阀门是否完全开启等，便于合理确定管网的工 作状态；节点流量的求解，是为得到某一个时刻各个节点相对准确的节点流量， 通过与实测或水表抄表数据的比较，用来判断是否存在漏水问题。通过对所求 管段摩阻s 值和节点流量的分析，还可阻相对准确的判断管网中的断管问题。 给水管网现状分析，是基于管阿水力计算的单目标优化问题，其目标函数 由两部分组成，即节点计算水压与s c a d a ( s u p e r v i s o r yc o n t t o la n d d a t a a c q u i s i t i o ns y s t e m s ，监控和数据采集系统) 实测水压差的平方、管段流量与 s c a d a 实测流量差的平方。约束条件有水流的连续性方程约束、能量方程约束、 水源水量约束、s 值约束、最低要求水压约束和节点流量约束。 数学模型建立的依据是，在满足管网水力条件约束下，在允许的调幅范围 内，通过对节点流量口，管段过水能力系数，的调整，使测压点实测水压与计 算水压的差值及测流管段的实测流量与计算流量的差值降至最小。建立给水管 网现状分析数学模型如下： m i n j t q r ) 。f h j t h j h 。0 2 + f i 丐f ”t q i q 曲2 l 2 - i 曲 ：畜各 s t f t q ，r ，国= o q 。，q ? q ( i = 1 2 。) r i ，r i r i 。i j = 1 2 。“) g ，嘞 式中魁，风一测压点j 的计算水压与实测水压，m ； 0 ，如一测流点j 的计算流量与实测流量，m 3 s 西，口一测压点与测流点的集合； 疗一测流项的权重及量纲影响系数； ( 2 1 4 ) ( 2 一i 5 ) ( 2 一1 6 ) ( 2 一1 7 ) 厶，厶一各测压点和测流点的权重系数： q 。，口矗一节点j 的节点流量及其允许变化幅度的下、上限，m 3 s d ，r 厂管段的过水能力系数及其允许变化幅度的下、上限； o 一计算时刻的供水总量，3 s 。 对于上述模型的几点说明： 为使计算简洁易懂，本模型采用过水能力系数，代替摩阻且 式( 2 - 1 4 ) 为节点连续性方程约束条件，其分量形式为： = 功i h 。一q r 4 s g n 阢一圳- - q 。d 2 l 2 ”二彬 ( 2 一1 8 ) e u 其中z j j = o 2 7 8 5 3 c 珥。以为过水能力系数，可由海曾一威廉公式( 2 4 ) 求 得，_ 为与节点j 相连的节点集合，s g n 为符号函数。 为减小搜索范围、提高计算效率，设定q 、，的界限值见式( 2 1 5 ) ， ( 2 1 6 ) 。 “， 为保证满足水源供水量约束条件式( 2 一1 7 ) ，设口= 吼忙q ， 在每 i = l， 步得出g ，后均执行g = 口g ，以保证所有节点流量之和等于水源供 水量。 根据实际情况，如管段摩阻和节点流量中已知其一或其中的一部分，则可 令数学模型中对应的一项为已知常数即可。本文针对最复杂的情况，即所有管 段摩阻和节点流量均未知的情况进行研究。 第三章最优化方法基础 3 1 最优化方法简介 最优化问题是通过研究去寻找事件的最优设计方案，所研究的问题涉及到 信息技术、经济管理、工业过程、交通运输、通信网络等诸多领域f h j 。该问题 数学模型描述为： r a i n f ( x ) 或m a x ，( z )( 3 - 1 ) 旦t g ( x ) 0 ， d 。 其中f f x ) 为目标函数，占) 为约束函数，d 表示有限个点组成的集合。 最优化问题求解的目的是在设计变量允许的范围d 内，找出一组参数值 ( 一点) x ，使得m i n f ( x ) ( 或m a x f ( x ) ) = f ( x ) 成立，即x 为f ( x ) 在d 上的极小( 极大) 值。 解决最优化问题的方法可分为最优算法和启发式算法( h e u r i s t i c a l g o r i t h m ) ”。最优算法是通过数学方法求得问题每个实例的最优解，包括枚 举法、单纯形法、简约梯度法、牛顿法、可行方向法、乘子法等。启发式算法 是一个基于直观或经验构造的算法，在可接受的花费( 指计算时间、占用空间) 下给出待解决问题每个实例的一个可行解，该可行解与最优解的偏离程度不一 定事先可以预计，具体方法包括禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e d a n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、神经网络( n e u r a ln e t w o r k ) 和拉格朗日 松弛等算法。 尽管从理论上最优算法可以达到最优解，但其运算的复杂性和应用的局限 性往往限制了应用问题的范围和规模：最优算法中数学模型本身是实际问题的 简化，必然或多或少的忽略了一些因素；参数采集具有不确定性，参数估计具 有不准确性；这些因素可能使最优算法所得解比启发式算法所得解产生更大误 差。而启发式算法则有其特别的优点： f 1 ) 有些难的优化问题可能还没有找到最优算法，即使存在，由算法复杂性理 论，得知它们的计算时间是无法接受或不实际的。 ( 2 1 一些启发式算法可以用在最优算法中。如可用遗传算法为简约梯度法确定 初值等。 ( 3 ) 简单易行，比较直观，易被使用者接受。 ( 4 ) 速度快，在实时管理中非常重要。 ( 5 ) 多数情况下程序简单，因此易于修改。 其缺点是不能保证求得最优解，表现不稳定。 第三章最优化方法基础 3 1 最优化方法简介 最优化问题是通过研究去寻找事件的最优设计方案，所研究的问题涉及到 信息技术、经济管理、工业过程、交通运输、通信网络等诸多领域f h j 。该问题 数学模型描述为： r a i n f ( x ) 或m a x ，( z )( 3 - 1 ) 旦t g ( x ) 0 ， d 。 其中f f x ) 为目标函数，占) 为约束函数，d 表示有限个点组成的集合。 最优化问题求解的目的是在设计变量允许的范围d 内，找出一组参数值 ( 一点) x ，使得m i n f ( x ) ( 或m a x f ( x ) ) = f ( x ) 成立，即x 为f ( x ) 在d 上的极小( 极大) 值。 解决最优化问题的方法可分为最优算法和启发式算法( h e u r i s t i c a l g o r i t h m ) ”。最优算法是通过数学方法求得问题每个实例的最优解，包括枚 举法、单纯形法、简约梯度法、牛顿法、可行方向法、乘子法等。启发式算法 是一个基于直观或经验构造的算法，在可接受的花费( 指计算时间、占用空间) 下给出待解决问题每个实例的一个可行解，该可行解与最优解的偏离程度不一 定事先可以预计，具体方法包括禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e d a n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、神经网络( n e u r a ln e t w o r k ) 和拉格朗日 松弛等算法。 尽管从理论上最优算法可以达到最优解，但其运算的复杂性和应用的局限 性往往限制了应用问题的范围和规模：最优算法中数学模型本身是实际问题的 简化，必然或多或少的忽略了一些因素；参数采集具有不确定性，参数估计具 有不准确性；这些因素可能使最优算法所得解比启发式算法所得解产生更大误 差。而启发式算法则有其特别的优点： f 1 ) 有些难的优化问题可能还没有找到最优算法，即使存在，由算法复杂性理 论，得知它们的计算时间是无法接受或不实际的。 ( 2 1 一些启发式算法可以用在最优算法中。如可用遗传算法为简约梯度法确定 初值等。 ( 3 ) 简单易行，比较直观，易被使用者接受。 ( 4 ) 速度快，在实时管理中非常重要。 ( 5 ) 多数情况下程序简单，因此易于修改。 其缺点是不能保证求得最优解，表现不稳定。 基于此本文将提出的广义简约梯度法与遗传算法结合的混合式遗传算法， 以综合启发式算法遗传算法与最优算法广义简约梯度法的优点，形成一种更加 稳健、准确的算法。以下将对遗传算法、广义简约梯度法进行介绍。 3 2 遗传算法1 1 6 1 1 1 7 i 3 2 1 遗传算法的起源与发展 早在2 0 世纪3 0 年代，就有人提出可以通过模拟生物进化过程来达到自学 习与优化的目的。6 0 年代初美国m i c h i g a n 大学j o h nh h o l l a n d 教授最初尝试 从生物进化机理中发展出适合于现实世界复杂优化问题的模拟进化算法 ( s i m u l a t e de v o l u t i o n a r yo p t i m i z a t i o n ) 。当时的主要遗传算子是变异算子而不 是选择算子，所以收效甚微。1 9 6 2 年加利福尼亚大学伯克利分校h a n sj b r e m e r m a r m 首次提出了杂交算子：即后代的特征取决于双亲有关基因的总和。 1 9 6 7 年j d b a g l e y 发明了“g e n e t i c a l g o r i t h m ”一词并发表了第一篇有关g a 的应用论文。在该文献中采用双倍体编码，发展了与目前类似的选择、杂交、 变异、显性、倒位等基因操作算子，己觉察到g a 的早熟收敛，并发展了自组 织遗传算法的概念。1 9 7 1 年r 丑h o l l s t e i n 完成了关于g a 在纯数学优化应用方 面的第篇学术论文，其中主要研究了5 种选择方法和8 种杂交策略。1 9 7 5 年 h o l l a n d 出版了g a 方面的经典著作“a d a p t a t i o ni n n a t u m | a n da r t i f i c i a l s y s t e m s ”，该书详细阐述了g a 的理论，并为g a 奠定了一定的数学基础，发 展了一整套模拟生物自适应系统的理论。标志着遗传算法作为一门智能计算学 科的正式诞生。自1 9 8 5 年起，遗传算法及其应用国际会议每二年召开一次，至 今，g a 已经有了很大的发展，并开始渗透到自适应行为、人工智能、神经网 络、机器人、运筹学、人工生命等领域，成为当前国际学术界和工程界跨学科 的热门研究课题。 3 2 2 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是模拟达尔文的遗传选择和自然淘 汰的生物进化论的计算模型。根据达尔文的自然选择学说，生物要生存下去， 必须进行生存竞争。在生存竞争中，具有有利变异的个体就容易生存下来，并 且有更多的机会将有利变异传给后代，而具有不利变异的个体就容易被淘汰， 产生后代的机会也少得多，因此，凡是在生存斗争中获胜的个体都是对环境适 应性比较强的。遗传和变异是决定生物进化的内在因素，遗传能使生物的性状 不断的传给后代，因此保持了物种的特性，变异能使生物性状发生改变，从而 适应新的环境而不断的向前发展。 遗传算法将每个可能的解看作是群体( p o p u l a t i o n ) 中的一个个体 2 基于此本文将提出的广义简约梯度法与遗传算法结合的混合式遗传算法， 以综合启发式算法遗传算法与最优算法广义简约梯度法的优点，形成一种更加 稳健、准确的算法。以下将对遗传算法、广义简约梯度法进行介绍。 3 2 遗传算法1 1 6 1 1 1 7 i 3 2 1 遗传算法的起源与发展 早在2 0 世纪3 0 年代，就有人提出可以通过模拟生物进化过程来达到自学 习与优化的目的。6 0 年代初美国m i c h i g a n 大学j o h nh h o l l a n d 教授最初尝试 从生物进化机理中发展出适合于现实世界复杂优化问题的模拟进化算法 ( s i m u l a t e de v o l u t i o n a r yo p t i m i z a t i o n ) 。当时的主要遗传算子是变异算子而不 是选择算子，所以收效甚微。1 9 6 2 年加利福尼亚大学伯克利分校h a n sj b r e m e r m a r m 首次提出了杂交算子：即后代的特征取决于双亲有关基因的总和。 1 9 6 7 年j d b a g l e y 发明了“g e n e t i c a l g o r i t h m ”一词并发表了第一篇有关g a 的应用论文。在该文献中采用双倍体编码，发展了与目前类似的选择、杂交、 变异、显性、倒位等基因操作算子，己觉察到g a 的早熟收敛，并发展了自组 织遗传算法的概念。1 9 7 1 年r 丑h o l l s t e i n 完成了关于g a 在纯数学优化应用方 面的第篇学术论文，其中主要研究了5 种选择方法和8 种杂交策略。1 9 7 5 年 h o l l a n d 出版了g a 方面的经典著作“a d a p t a t i o ni n n a t u m | a n da r t i f i c i a l s y s t e m s ”，该书详细阐述了g a 的理论，并为g a 奠定了一定的数学基础，发 展了一整套模拟生物自适应系统的理论。标志着遗传算法作为一门智能计算学 科的正式诞生。自1 9 8 5 年起，遗传算法及其应用国际会议每二年召开一次，至 今，g a 已经有了很大的发展，并开始渗透到自适应行为、人工智能、神经网 络、机器人、运筹学、人工生命等领域，成为当前国际学术界和工程界跨学科 的热门研究课题。 3 2 2 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是模拟达尔文的遗传选择和自然淘 汰的生物进化论的计算模型。根据达尔文的自然选择学说，生物要生存下去， 必须进行生存竞争。在生存竞争中，具有有利变异的个体就容易生存下来，并 且有更多的机会将有利变异传给后代，而具有不利变异的个体就容易被淘汰， 产生后代的机会也少得多，因此，凡是在生存斗争中获胜的个体都是对环境适 应性比较强的。遗传和变异是决定生物进化的内在因素，遗传能使生物的性状 不断的传给后代，因此保持了物种的特性，变异能使生物性状发生改变，从而 适应新的环境而不断的向前发展。 遗传算法将每个可能的解看作是群体( p o p u l a t i o n ) 中的一个个体 2 基于此本文将提出的广义简约梯度法与遗传算法结合的混合式遗传算法， 以综合启发式算法遗传算法与最优算法广义简约梯度法的优点，形成一种更加 稳健、准确的算法。以下将对遗传算法、广义简约梯度法进行介绍。 3 2 遗传算法1 1 6 1 1 1 7 i 3 2 1 遗传算法的起源与发展 早在2 0 世纪3 0 年代，就有人提出可以通过模拟生物进化过程来达到自学 习与优化的目的。6 0 年代初美国m i c h i g a n 大学j o h nh h o l l a n d 教授最初尝试 从生物进化机理中发展出适合于现实世界复杂优化问题的模拟进化算法 ( s i m u l a t e de v o l u t i o n a r yo p t i m i z a t i o n ) 。当时的主要遗传算子是变异算子而不 是选择算子，所以收效甚微。1 9 6 2 年加利福尼亚大学伯克利分校h a n sj b r e m e r m a r m 首次提出了杂交算子：即后代的特征取决于双亲有关基因的总和。 1 9 6 7 年j d b a g l e y 发明了“g e n e t i c a l g o r i t h m ”一词并发表了第一篇有关g a 的应用论文。在该文献中采用双倍体编码，发展了与目前类似的选择、杂交、 变异、显性、倒位等基因操作算子，己觉察到g a 的早熟收敛，并发展了自组 织遗传算法的概念。1 9 7 1 年r 丑h o l l s t e i n 完成了关于g a 在纯数学优化应用方 面的第篇学术论文，其中主要研究了5 种选择方法和8 种杂交策略。1 9 7 5 年 h o l l a n d 出版了g a 方面的经典著作“a d a p t a t i o ni n n a t u m | a n da r t i f i c i a l s y s t e m s ”，该书详细阐述了g a 的理论，并为g a 奠定了一定的数学基础，发 展了一整套模拟生物自适应系统的理论。标志着遗传算法作为一门智能计算学 科的正式诞生。自1 9 8 5 年起，遗传算法及其应用国际会议每二年召开一次，至 今，g a 已经有了很大的发展，并开始渗透到自适应行为、人工智能、神经网 络、机器人、运筹学、人工生命等领域，成为当前国际学术界和工程界跨学科 的热门研究课题。 3 2 2 遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是模拟达尔文的遗传选择和自然淘 汰的生物进化论的计算模型。根据达尔文的自然选择学说，生物要生存下去， 必须进行生存竞争。在生存竞争中，具有有利变异的个体就容易生存下来，并 且有更多的机会将有利变异传给后代，而具有不利变异的个体就容易被淘汰， 产生后代的机会也少得多，因此，凡是在生存斗争中获胜的个体都是对环境适 应性比较强的。遗传和变异是决定生物进化的内在因素，遗传能使生物的性状 不断的传给后代，因此保持了物种的特性，变异能使生物性状发生改变，从而 适应新的环境而不断的向前发展。 遗传算法将每个可能的解看作是群体( p o p u l a t i o n ) 中的一个个体 2 ( i n d i v i d u a l ) ，并将每个个体编码( c o d e ) 贼字符窜的形式，根据预定的目标函数对 姆个个体进行评价，即绘出一个适应度值( f i t n e s s ) 。开始时，总是随机地产生一 魏个体，根据这些个体的适应度利粥遗传算子一一选择( s e l e e t i o n ) 、交叉 ( c r o s s o v e r ) 、变辫( m u t a t i o n ) ，对它们重新组台，得到一群新的个体。这一群耨 个体由予继承了上一彳弋的一些优馥特穗，明显优于上一代，戬逐步向麓更优解 的方向进化。 3 2 3 遗传算 去的应用步骤 遗传葵法稳供了一耱求鬓复杂系统饶讫蓠黻豹遥麓框絮，宅不菝羰子淘戆 的领域和种类。对一个浠要进行优化计算的实际应用问题，一般可按下述步骤 采揍遥求簿该瓣惩粒遗传算法。 ( 1 )确定决策变量及其各种约束条件，即确定个体的表现型和问题的解空间。 ( 2 ) 建立扰纯模型，霹确定基糠丞数懿类型( 楚求基撂函鼗的媛丈篷遥是求基 标函数的最小值) 及其数学描述形式或蹙化方法。 ( 3 )确悫表示可行解的染色体缡玛方法，也即确定个体数基因攫及遗传莫法鼹 搜索空间。 ( 4 )确定解码方法，即确定由个体基因型到个体表现型的对废关系域转换方 ( 5 ) 确定个体邋应度的量化评价方法，即确定由目标函数值f ( x ) 到个体适成 发f ( 盖) 豹转换蕊潮。 ( 6 )设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算予的具体 搡俸方法。 ( 7 )确定遗传算法的有关运行参数，即确定遗传算法的群体大小肘、终止代 数r 、交叉凝率芒、交舅壤率只等参数。 由上述构造步骤可以看出，可行解的编码方法、遗传算子的设计怒构造遗 蕊算法辩霉要考纛嚣嚣令主要潮蘧，惑是设诗遗转算法越懿嚣令关建疹骤。砖 不同的优化问题需要使用不同的犏码方