基于双重编码遗传算法和图论的自压树状管网优化

2 0 1 0年 1月 农 业 机 械 学 报 第 41卷 第 1期 DO I: 10. 3969 / j. issn. 100021298. 2010. 01. 016 基于双重编码遗传算法和图论的自压树状管网优化 3 杨建军 1, 2 　丁玉成 1 　赵万华 1 (11西安交通大学机械制造系统工程国家重点实验室 , 西安 710049; 21青岛理工大学机械工程学院 , 青岛 266033) 　　【摘要 】　以投资最小为目标函数 ,压力、流速、管径等限制为约束条件 ,建立了自压树状管网优化数学模型 ,并 采用改进遗传算法进行求解。根据树状管网优化的特点 ,遗传算法采用二进制编码和整数编码相结合的双重编 码 ,实现了同时对管网布置形式和管径进行优化。根据图论中树的性质 ,在产生初始解及变异操作时 ,采用基于圈 的方法 ,对交叉方法进行了改进 ,从而减少了不可行解的产生。同时对遗传算法的操作过程进行了改进 ,结合了模 拟退火算法 ,调整了适应函数 ,改进了交叉率和变异率的计算方法。算例表明了该优化方法的有效性。 关键词 : 树状管网 　优化 　遗传算法 　双重编码 　图论 中图分类号 : TP30116; S27412 文献标识码 : A 文章编号 : 100021298 (2010) 0120081205 O ptim iza tion of Grav ity Tree2type P ipe Network Ba sed on D ua l Cod ing Genetic A lgor ithm and Graph Theory Yang J ianjun1, 2 　D ing Yucheng1 　Zhao W anhua1 (11S ta te Key Labora tory forM anufacturing System s Engineering, X i’an J iaotong U niversity, X i’an 710049, Ch ina　 21School of M echan ical Engineering, Q ingdao Technolog ica l U niversity, Q ingdao 266033, China) Abstract An op tim ization model for gravity tree2type p ipe network is established, in which the m inimal investment is taken as the objective function, and the p ressure, flow rate and p ipe diameter are taken as the constraint conditions. The imp roved genetic algorithm is used to solve the p roblem. Based on the op timal features of tree2type p ipe network, the dual coding combining binary coding with integer coding is adop ted in the genetic algorithm to op tim ize the p ipe layout and p ipe diameter simultaneously. Based on characteristics of tree in the graph theory, the cycle method is adop ted to imp rove cross method in the operations of initial solution creating and mutation so that the number of infeasible solutions is reduced. Some operational p rocesses of genetic algorithm are imp roved. The simulated annealing algorithm is introduced in the model. The fitness function is adjusted, and the computing methods of crossover rate and mutation rate are imp roved. Examp le shows that the algorithm is efficient. Key words　Tree2type p ipe network, Op tim ization, Genetic algorithm, Dual coding, Graph theory 收稿日期 : 2009201214　修回日期 : 20092032093 国家“863”高技术研究发展 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 资助项目 (2006AA100208)和泰山学者建设工程专项经费资助项目 (2007) 作者简介 : 杨建军 ,博士后 ,青岛理工大学副教授 ,主要从事系统工程优化、优化算法研究 , E2mail: yjjdem@163. com　　引言自压树状管网在灌溉等管网输配水系统中应用十分广泛 ,其完整的优化应包括管网布置优化和管径优化两部分 ,分别优化管网的连接路线和各管线的管径 ,这两个优化问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 均是涉及离散变量的非线性组合优化问题。 目前较多的研究成果 [ 1～3 ]是在管网布置形式一定的情况下针对管径进行的优化设计。当采用图论中 D ijkstra等算法进行管网布置优化时 ,得到的布置 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 为管线总长度最短 ,但其管网总投资未必最小 [ 4 ]。文献 [ 4～5 ]采用二进制编码单亲遗传算法对树状管网进行布置优化 ,用经济流速法确定各管线管径 ,其全局最优性很难保证 ,且随机产生初始解 时将产生大量不可行解。文献 [ 6 ]采用两级整数编 码遗传算法进行树状管网优化设计 ,采用不同目标 函数分两级分别对管网布置和管径进行优化 ,其解 的全局最优性较难保证 ,同时在布置优化时需已知 管网初步连接图中各管线的水流方向 ,对于提前无 法确定的较复杂管网 ,也将产生大量的不可行解。 管网布置优化时大量不可行解的存在 ,大大降低了 算法的计算效率。 当同时对管网布置形式和管径进行优化设计 时 ,将能最大限度地降低系统投资。本文针对自压 树状管网的结构特点 ,为了能够同时对管网布置和 管径进行优化设计 ,采用二进制编码和整数编码相 结合的双重编码遗传算法 ,并根据图论中树的性质 对产生初始解、交叉和变异方法进行改进 ,减少不可 行解的产生 ,提高算法的计算效率。 1　自压树状管网优化数学模型的建立 管网布置优化和管径优化的目的均是为了降低 系统投资 ,因此以系统投资最小为目标函数 ,其数学 模型为 m infc = ∑ N p i =1 δiL i Ci (1) 式中 　fc ———管网系统总投资 Np ———管网初步连接图中管线总数量 δi ———第 i条管线的连接状态 ,分别用 1或 0 表示该管线连接或断开 L i ———第 i条管线长度 Ci ———第 i条管线单位长度价格 ,与该管线 的管径 D i 相对应 需要考虑的约束条件有节点压力约束、流速约 束和管径约束 ,即 pi = E - ∑ j∈I i αf Q m j Dnj L j - Ei ≥pim in 　 ( i = 1, ⋯, N n ) (2) vim in ≤vi ≤vimax 　 ( i = 1, ⋯, N 1 ) (3) D j∈ID (4) 式中 　pi、pim in ———节点 i的运行压力值和最低要求 压力值 N n ———用水节点总数量 E———水源压力值 Ii ———水源到管网第 i节点经过的管线集合 α———考虑局部水头损失时的放大系数 f、m、n———管道水头损失中与管材有关的系 数 Ei ———节点 i处的地面高程 vim in、vimax、vi ———管线 i的最小、最大允许流 速和运行流速 N 1 ———处于连接状态的管线数量 ID ———可选 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 管径集合 ,设共有 N sd种 优化过程中通过编码设计管径约束自动得到满 足。利用惩罚函数法将原目标函数和剩余约束条件 转化为无约束优化问题 ,扩展后的目标函数为 f = fc +M p ∑ N n i =1 max (0, pim in - pi ) + M v ∑ N 1 j =1 max ( vj - vjmax , 0, vjm in - vj ) (5) 式中 　M p、M v ———压力、流速惩罚因子 此外 ,还应保证所有用水节点都能供水且生成 的管网布置形式为树状管网。 2　基于图论的树状管网特性 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 树状管网具有图论中树的性质 ,一棵树中边的 数量等于节点数量减一。对于单水源的情况 ,其树 状管网是管网初步连接图的一棵生成树 (连接状态 的管线数量等于节点数量减一 ) ,而对于含有 N s 个 水源的情况 ,则对应 N s 棵树 (非生成树 ,连接状态 的管线数量等于节点数量减去 N s )。管网布置形式 优化实质上就是在管网初步连接图的基础上寻找最 优的生成树 (单水源 )或某组树 (多水源 )。 本文在管网中引入图论中圈的概念。管网中的 圈是指在管网初步连接图中 ,可以形成的环状网络。 即从某一个节点出发 ,每个节点只经过一次 ,又回到 该节点的环状网络为第一类圈。如果是多水源管 网 ,从一个水源点出发 ,每个节点只经过一次 ,到达 另一个水源点的环状网络为第二类圈。 如图 1所示的简单管网初步连接图 ,节点 0和 7为水源节点 ,其他为用水节点 ,其中包括 7个圈 , 分别为 : 021222327、0212225262327、0212425262327、0212 425222327、122252421、223262522、1222326252421。前 4 个属于第二类圈 ,后 3个属于第一类圈。各圈中包 含的管线编号集合分别为 : { 8, 1, 2, 9}、{ 8, 1, 4, 7, 5, 9}、{ 8, 3, 6, 7, 5, 9}、{ 8, 3, 6, 4, 2, 9}、{ 1, 4, 6, 3}、 { 2, 5, 7, 4}、{ 1, 2, 5, 7, 6, 3}。 图 1　简单管网初步连接图 Fig. 1　Prelim inary connection diagram of simp le p ipe network 　 根据图论中的破圈法 [ 7 ] ,树状管网的生成方法 为 :逐次删除管网初步连接图中任一圈中的任一管 线 ,直到管网初步连接图中不存在圈。 28 农 　业 　机 　械 　学 　报 　　　　　　　　　　　　　　　　2 0 1 0年 3　双重编码遗传算法主要操作步骤 311　编码 因管网优化中需同时对管网布置形式及管径组 合进行优化设计 ,因此本文采用双重编码 [ 8 ]。布置 形式优化实质上是在管网初步连接图的基础上确定 各管线的连接状态 ,因管线只有连接或断开两种状 态 ,可直接用 1或 0来表示 ,因此用二进制编码表示 各管线的连接状态 ,所有编码为 1的管线构成一个 管网布置形式。管径为离散的标准值 ,可根据标准 管径的个数 N sd ,设计一个一维数组 ,数组的值为各 标准管径 ,通过数组的整数下标与标准管径对应 ,因 此可采用整数编码表示各管径 ,这样可以避免二进 制编码的编码冗余问题。 312　产生初始解 产生初始解时 ,首先产生二进制编码 ,为了避免 不可行解的产生 ,根据破圈法原理 ,具体实现方法 为 : ①令所有基因值均为 1,搜索管网初步连接图中 的所有圈。②逐个判断各圈中是否有断开的管线 , 如果没有 ,则随机断开该圈中任一条管线 ,如果已经 存在 ,不论存在几个 ,都不再操作 ,因为当一个圈与 其他圈有部分管线相同时 ,可能出现一个圈中断开 多条管线的情况 ,但不会存在节点不连通的情况。 产生过程中可随时判断连接状态的管线数量与节点 数量的关系 ,如果满足相应树的关系 ,则终止 ,以节 省计算时间。该方法产生的初始解均是可行解。 例如对于图 1的管网初步连接图 ,经过以下过 程可产生一随机初始解 :在处理第 1个圈时 ,随机选 择断开管线 2;第 2个圈随机选择断开管线 7;第 3、4 个圈中已有断开的管线 ,不操作 ;第 5个圈随机选择 断开管线 1,此时连接状态的管线数量 (6 )与节点数 量 (8)的关系已满足 2个水源时对应 2棵树的要 求 ,产生过程结束。该随机初始解为 { 0, 0, 1, 1, 1, 1, 0, 1, 1} ,表示断开的管线为 { 1, 2, 7}。 然后产生与各管线相对应的管径 ,即整数编码 , 对应各管线在 [ 1, N sd ]范围内产生一个随机整数来 表示其管径 ,计算时通过数组与该管线的标准管径 对应 ,这也使管径约束自动得到满足。 313　确定适应函数 遗传算法操作过程中依据的是适应函数值 ,适 应函数值应根据目标函数值确定 ,其值不能为负 ,且 其值增加的方向应对应目标函数的优化方向 ,本文 管网优化的目标函数是投资最小 ,应加以调整。采 用的变换方式为 Fi = exp ( ( fm in - fi ) / t) (6) 式中 　Fi ———染色体 i的适应函数值 fm in ———当代进化群体中最小目标函数值 t———与模拟退火算法结合后的温度参数 314　确定初温及退温操作 在遗传算法早期 ,应使种群中各染色体的适应 函数值相近 ,这样可以避免个别好的染色体充斥整 个种群 ,造成早熟。因此 ,从考虑初始种群的相对性 能出发确定初温 [ 9 ] ,令 Fsm in / Fsmax = pr (7) 式中 　Fsm in、Fsmax ———初始种群中最小、最大适应函 数值 pr ——— (0, 1)范围内的小数 ,可根据需要进行 调整 ,其值越大 ,各适应函数值越相近 由式 (6)和式 (7) ,可得初温的表达式为 t0 = ( fsm in - fsmax ) / lnpr (8) 式中 　fsm in、fsmax ———初始种群中最小、最大目标函数 值 退温函数为 tn =γn - 1 t0 (9) 式中 　γ——— (0, 1)范围内的小数 315　交叉操作 根据 Srinivas[ 10 ] 等提出的自适应遗传算法 ( adap tive genetic algorithm,简称 AGA ) ,并对其进行 改进 ,交叉率 Pc 的自适应计算方法为 Pc = k1 + k2 ( Fmax - F′i ) Fmax - Favg ( F′i ≥Favg ) k3 ( F′i < Favg ) (10) 式中 　k1、k2、k3 ———常数 ,且 k3 = k1 + k2 Fmax、Favg ———当代进化群体的最大、平均适 应函数值 F′i ———两个交叉个体中较大的适应函数值 对于表示管网布置形式的二进制编码 ,采用单 点交叉。为了减少不可行解的产生 ,在选择交叉点 时 ,应使两个染色体在交叉点一侧处于断开的管线 数量相同 ,这样交叉后仍能满足树状管网可行解的 基本条件 (连接状态的管线数量与节点数量关系 )。 如对应图 1的两个染色体编码为 { 0, 0, 1, 1, 1, 1, 0, 1, 1}、{ 1, 0, 1, 0, 1, 0, 1, 1, 1} ,选择的交叉点为 5,这 样在交叉点左侧两个染色体断开的管线数量均为 2,互换两个染色体的 6～9位基因值 ,生成的子染色 体为 { 0, 0, 1, 1, 1, 0, 1, 1, 1}、{ 1, 0, 1, 0, 1, 1, 0, 1, 1} 均为可行解。 对于表示管径的整数编码 ,采用算术交叉方法 , 并需进行取整操作以使其值为整数。设随机选择两 个染色体的整数编码为 ( x1 , ⋯, xi , ⋯, xN p )和 ( y1 , ⋯, yi , ⋯, yN p )进行交叉 ,则交叉方法为 38第 1期 　　　　　　　　　　　杨建军 等 : 基于双重编码遗传算法和图论的自压树状管网优化 x′i = round (λi xi + (1 -λi ) yi ) y′i = round (λi yi + (1 -λi ) xi ) 　 ( i = 1, ⋯, Np ) (11) 式中 　round———进行四舍五入取整操作的函数 λi ———[ 0, 1 ]范围内的随机数 316　变异操作 变异率 Pm 的自适应计算方法为 Pm = k4 + k5 ( Fmax - Fi ) Fmax - Favg ( Fi ≥Favg ) k6 ( Fi < Favg ) (12) 式中 　k4、k5、k6 ———常数 ,且 k6 = k4 + k5 对于二进制编码的变异 ,如果采用普通的单点 变异 ,当仅有某一位基因由 1变为 0时 ,一定会出现 不连通节点 ,而由 0变为 1时 ,则会出现圈。因此 , 变异操作时需两个基因位同时变化。本文在该类变 异时也基于破圈法原理 ,即首先随机选择染色体的 一个 0基因位将其变为 1,然后对包含该管线的圈 进行检查 ,如果某圈出现环状管网 ,则随机把此圈中 其他基因值由 1变为 0,如果不出现 (因某些圈中可 能存在多个断开的管线 ) ,则不必操作 ,这样操作产 生的均为可行解。 对于整数编码的变异 ,变异操作时设随机选择 基因 xi 进行变异 ,新基因值 x″i 的生成方法为 x″i = xi +Δ ( random (2) = 0) xi -Δ ( random (2) = 1) (13) 式中 　random ( x) ———产生 0到 x - 1范围内随机整 数的函数 Δ———较小的随机整数 为了能够自动满足管径约束 ,Δ的计算方法为 Δ = random (N sd - xi + 1) ( random (2) = 0) random ( xi ) ( random (2) = 1) (14) 4　优化算例 根据本文算法编制了自压树状管网优化程序 , 并对图 2所示管网 [ 4 ]进行了优化设计。该管网初步 连接图中有 0～9共 10个节点 ,其中 0为水源节点 , 其他为用水节点 ,各节点用水量均为 10 m3 / h,共有 23条可选连接管线 ,编号由 1到 23,图中管线编号 对应括号中的数值表示管线长度 ,单位为 100 m,计 算中各节点地面高程均相同 ,水源压力为 30 m,各 管线最低允许流速为 015 m / s。 管道沿程水头损失计算中忽略局部水头损失 , 采用海曾 2威廉公式 [ 11 ] 图 2　某管网初步连接图 Fig. 2　Prelim inary connection diagram of a p ipe network 　 H = 10167Q11852 A11852 D4187 L (15) 式中 　H———管道水头损失 , m Q———流量 , m3 / s　　D———管径 , m A———与管道材料有关的系数 ,取 A = 130 L———管长 , m 管线价格如表 1所示。 表 1　管线价格 Tab. 1　Pr ice of p ipeline 管径 /mm 65 80 100 125 150 单位长度价格 /元 4140 5190 8174 12160 16196 　　分别采用文献 [ 4 ]和本文优化方法对管网进行 优化设计 ,优化结果对比如表 2所示。 表 2　优化结果对比 Tab. 2　Com par ison am ong optim iza tion results 设计 方法 处于连接状态的管线 (对应管径 /mm ) 管线总 长度 /m 管网总 投资 /元 文献 [ 4 ] 方法 1 (100) , 2 (150) , 3 (125) , 5 (80) , 10 (125) , 11 (80) , 13 (80) , 19 (80) , 20 (80) 6 400 56 282 本文算法 2 约束 1 1 (100) , 2 (150) , 3 (100) , 5 (80) , 10 (150) , 11 (65) , 18 (80) , 19 (80) , 20 (80) 6 500 56 000 本文算法 2 约束 2 1 (80) , 2 (150) , 3 (100) , 10 (150) , 11 (65) , 16 (80) , 18 (80) , 19 (80) , 20 (80) 6 600 53 118 　　采用文献 [ 4 ]中的方法进行管网布置优化时 , 管径当作连续变量 ,用经济流速法确定 ,然后再选取 标准值 ,优化后末端节点的最低压力值为 19142 m。 采用本文方法同时对管网布置和管径进行优化设计 后 (节点压力约束中最低允许压力值设为 19142 m, 结果对应表 2中本文算法 2约束 1 ) ,虽然管线总长 度增加了 100 m,但由于连接路线和管径的变化 ,管 48 农 　业 　机 　械 　学 　报 　　　　　　　　　　　　　　　　2 0 1 0年 网投资降低了 282元 ,而且末端节点的最低压力值 提高到了 19154 m,同时由于在操作过程中减少了 不可行解的产生 ,使得计算速度明显提高。当适当 降低节点压力约束时 (结果对应表 2中本文算法 2约 束 2) ,得到的最优解中管线总长度为 6 600 m,管网 投资为 53 118元 ,末端节点的最低压力值为 16113 m。 5　结论 (1) 针对自压树状管网优化的特点 ,采用二进 制编码和整数编码相结合的双重编码遗传算法 ,准 确表示各优化设计变量 ,实现了对树状管网中的管 网布置形式和管径组合的同时优化。并针对简单遗 传算法的局限性 ,对操作过程进行了适当改进 ,结合 模拟退火算法变换了适应函数的确定方法 ,改进了 交叉率和变异率的计算方法。 (2) 针对树状管网的结构特点 ,根据图论中树 的性质 ,设计了基于圈的方法产生初始种群和进行 变异操作 ,并改进了交叉方法 ,大大减少了不可行解 的产生 ,提高了算法的计算效率。 参 考 文 献 1　Kadu M S, Gup ta R, Bhave P R. Op timal design ofwater networks using a modified genetic algorithm with reduction in search space[ J ]. Journal ofW ater Resources Planning and Management, 2008, 134 (2) : 147～160. 2　朱家松 ,龚健雅 ,郑皓. 遗传算法在管网优化设计中的应用 [ J ]. 武汉大学学报 :信息科学版 , 2003, 28 (3) : 363～367. Zhu J iasong, Gong J ianya, Zheng Hao. App lication of genetic algorithm to water distribution system design op tim ization[ J ]. Geomatics and Information Science ofW uhan University, 2003, 28 (3) : 363～367. ( in Chinese) 3　王新坤. 基于不可行度的机压树状管网退火遗传算法优化 [ J ]. 农业机械学报 , 2009, 40 (9) : 63～67. W ang Xinkun. Op tim ization of pump ing tree p ipe network by using annealing2genetic algorithm s based on infeasible degree [ J ]. Transactions of the Chinese Society for AgriculturalMachinery, 2009, 40 (9) : 63～67. ( in Chinese) 4　周荣敏 ,雷延峰. 管网最优化理论与技术 [M ]. 郑州 :黄河水利出版社 , 2002. 5　骆力明 ,王华 ,王炎. 基于单亲遗传算法的管网优化 [ J ].计算机应用与软件 , 2008, 25 (6) : 68～70. Luo L im ing, W ang Hua, W ang Yan, et al. Op tim izing p ipeline network based on single parent genetic algorithm [ J ]. Computer App lications and Software, 2008, 25 (6) : 68～70. ( in Chinese) 6　马孝义 ,范兴业 ,赵文举 ,等 .基于整数编码遗传算法的树状灌溉管网优化设计方法 [ J ]. 水利学报 , 2008, 39 (3) : 373～ 378. Ma Xiaoyi, Fan Xiangye, Zhao W enju, et al. Tree2type p ipe network op tim ization design method based on integer coding generic algorithm [ J ]. Journal of Hydraulic Engineering, 2008, 39 (3) : 373～378. ( in Chinese) 7　刘缵武. 应用图论 [M ]. 长沙 :国防科技大学出版社 , 2006. 8　杨建军 ,丁玉成 ,赵万华.基于双重编码遗传算法的树状管网优化设计 [ J ].节水灌溉 , 2008, 33 (12) : 41～43. Yang J ianjun, D ing Yucheng, Zhao W anhua. Op timal design of tree2type p ipe network based on dual coding genetic algorithm [ J ]. W ater Saving Irrigation, 2008, 33 (12) : 41～43. ( in Chinese) 9　王凌 ,郑大中. 一类改进进化规划及其优化性能分析 [ J ]. 计算机工程与应用 , 2002, 38 (1) : 8～10. W ang L ing, Zheng Dazhong. A class of imp roved evolutionary p rogramm ing and its op tim ization performances analysis[ J ]. Computer Engineering and App lications, 2002, 38 (1) : 8～10. ( in Chinese) 10　SrinivasM , Patnaik L M. Adap tive p robabilities of crossover and mutation in genetic algorithm s[ J ]. IEEE Transactions on System s, Man and Cybernetics, 1994, 24 (4) : 656～667 11　吴俊奇 ,付婉霞 ,曹秀芹. 给水排水工程 [M ]. 北京 :中国水利水电出版社 , 2004. 58第 1期 　　　　　　　　　　　杨建军 等 : 基于双重编码遗传算法和图论的自压树状管网优化