论文部分内容阅读
摘 要：以树状给水管网为例，将管网经济性和可靠性作为目标函数，对其约束条件以惩罚函数加权，建立管网优化多目标数学模型。采用整数编码、双切点交叉等技术构建基本遗传算法，并在此基础上添加育种算子，对其进行改进，形成育种遗传算法。最后以一个典型的工程案例进行验证，结果表明育种算子能加快遗传算法的收敛速度，防止算法早熟，极大的改善了传统遗传算法的性能。
关键词：育种遗传算法；给水管网；多目标数学模型；优化设计；整数编码
Abstract： As an example of tree-shaped water supply network， the multi-objective mathematical model？，in which the economy and reliability of network are taken as the objective functions，the constraint condition is weighted by penalty function is established. Integer coding and the double tangent crossing technology are used to construct the basic genetic algorithm，and based on this，the improved form breed genetic algorithm is established by adding breeding operator.Finally，a typical example is used to verify the breed genetic algorithm and the results show that the performance of the traditional genetic algorithm is greatly improved by the breeding operator，which can accelerate the convergence speed of genetic algorithm，to prevent premature convergence.
Keywords： breed genetic algorithm；water distribution networks；multi-objective mathematical model；optimization design；integer encoding
1.引言
城市給水工程主要由取水工程、水处理工程和管网系统三部分组成。其中管网系统约占整个给水工程总费用的50%～80%[1]。本文通过对已有的一典型树状给水管网模型进行分析，将管网经济性定义为管网年费用，将可靠性定义为管网节点富余水头加权平均值，并对可靠性定量分析，添加权重因子 。而优化方法采用育种遗传算法[2]，将育种的思想应用于遗传算法，和基本遗传算法相比，其收敛速度和得到的最优解可行性的都有很大的提高。
2.管网优化数学模型
本文模型为简单树状管网，在保证水量水压的前提下，不再考虑水质安全这方面，而以管网年费用和可靠性为目标函数建立多目标遗传算法数学模型。
2.1 参考文献[3]，考虑货币时间价值的管网经济性目标函数用数学模型可表示为：
2.2 供水管网优化设计可靠性以节点富余水头来表示，节点富余水头是指节点自由水头超过节点所要求的最小自由水头的水头，节点富余水头越小，管网中水压就越低，管网正常工作的概率就越大因此，节点富余水头与管网系统可靠性负相关[4]。用所有节点可靠性的加权平均值来表示，即：
在供水管网优化设计的数学模型中，这两项均是求极小值。采用线性加权法将多目标数学模型转化为单目标数学模型，假设管网的可靠性和经济性同样重要[4]，故对二者赋予相同的权重，均为 0.5，但是可靠性与经济性不在一个量级上相差很大，故可靠性应添加权重因子 ，则管网优化设计的目标函数可改写为：
2.3 供水管网优化设计约束条件
（1）水力平衡约束条件
3 遗传算法设计
3.1编码与初始化种群
由于标准管径为整数而且采用二进制编码时字符串过长，管径规格往往存在冗余问题，故采用整数编码，克服二进制编码频繁的编码与解码过程，提高了算法的实用性和计算效率。本文实例中有8种可选管径，采用整数[1，2，3，4，5，6，7，8]一一对应地表示，笔者应用matlab7.0中的round（1+7*rand（））函数随机生成1-8的任意整数，通过循环语句生成一组管径组合，即为一个染色体，种群规模设定为30，由30个染色体构成了初始化的种群。
3.2 适应度函数的分析与设计
对管网中压力和流速采用惩罚函数项加以约束， 则广义目标函数为：
3.3 交叉和变异算子的分析与设计
本文管网模型优化管段数为26，染色体长度较长，采用单点交叉容易破坏优秀个体，故笔者采用双切点交叉方法，有利于优秀个体的保护。杂交概率Pc为0.9，变异概率Pm为0.05，
3.4选择策略
3.5 育种算子设计
遗传算法以交叉实现局部搜索，变异实现全局搜索，但由于变异概率如果取得太大，算法将不能收敛，取得太小就会陷入局部最优。为解决这个问题，将每次迭代的优异种子进行保存，生成育种空间，对此空间中的种子进行高概率的交叉变异操作，然后将最高适应值的种子替换遗传算法的最劣个体，而当种群相似度达到阀值时，在育种算子中选择相似度最低个体带入种群中，扩展搜索空间。
4.应用实例
如图1所示，为单水源树状管网，由21个节点，20个管段组成，8中可供选择的管径规格，分别为90、110、125、140、160、180、220和225mm，管段长度及流量见表1，水厂的最高日最高时供水量为180m3/h，水泵净扬程为m，输水管采用PE管，水头损失计算采用海曾—威廉公式：
本例运算采用matlab7.0编程，计算机属性如下：采用2.5GHz Intel处理器，2GB内存，Win7 64位操作系统，基本遗传算法运行时间为0。734s，搜索到的最优解是7.288e+05，而育种遗传算法运行时间为3.218s，虽然育种遗传算法的时间较长，但其搜索效率更好，在200代时搜索到最优解6.264e+05，运行结果如图2所示。
从图中容易发现，基本遗传算法收敛速度慢，适应值呈小幅振动，在局部最优解范围内上下浮动，无法进一步收敛；而育种遗传算法，呈现出一条光滑收敛的曲线，当有更优解出现能快速捕捉，不会陷入局部最优解，且在120步时收敛得到全局最优解。
5.结语
传统遗传算法在求解组合优化问题时容易陷入局部最优解，导致未成熟收敛问题，使得遗传算法的应用受到很大限制，而加入育种算子后，种群的进化效率有了很大提高，且不会由于提高全局搜索能力导致的种群退化现象。以一个实例的运算对比育种遗传算法和基本遗传算法，比较直观的展现了育种遗传算法在给水管网优化问题中的优异性能。
参考文献
[1] 卢姗姗.城市给水管网水力特性分析研究.硕士论文[D].2012.
[2] 常晓宇，周春光，管恩政等.用育种算子改进遗传算法.吉林大学学报[J]，2005，23（2）.
[3] 严煦世，范瑾初.给水工程[M]。北京：中国建筑工业出版社，2008.
[4] 储成山.改进混合遗传算法用于给水管网优化设计的研究[D].天津大学，2006.
作者简介：姓名：李宣，学校：山东科技大学，研究方向：给水管网优化。
关键词：育种遗传算法；给水管网；多目标数学模型；优化设计；整数编码
Abstract： As an example of tree-shaped water supply network， the multi-objective mathematical model？，in which the economy and reliability of network are taken as the objective functions，the constraint condition is weighted by penalty function is established. Integer coding and the double tangent crossing technology are used to construct the basic genetic algorithm，and based on this，the improved form breed genetic algorithm is established by adding breeding operator.Finally，a typical example is used to verify the breed genetic algorithm and the results show that the performance of the traditional genetic algorithm is greatly improved by the breeding operator，which can accelerate the convergence speed of genetic algorithm，to prevent premature convergence.
Keywords： breed genetic algorithm；water distribution networks；multi-objective mathematical model；optimization design；integer encoding
1.引言
城市給水工程主要由取水工程、水处理工程和管网系统三部分组成。其中管网系统约占整个给水工程总费用的50%～80%[1]。本文通过对已有的一典型树状给水管网模型进行分析，将管网经济性定义为管网年费用，将可靠性定义为管网节点富余水头加权平均值，并对可靠性定量分析，添加权重因子 。而优化方法采用育种遗传算法[2]，将育种的思想应用于遗传算法，和基本遗传算法相比，其收敛速度和得到的最优解可行性的都有很大的提高。
2.管网优化数学模型
本文模型为简单树状管网，在保证水量水压的前提下，不再考虑水质安全这方面，而以管网年费用和可靠性为目标函数建立多目标遗传算法数学模型。
2.1 参考文献[3]，考虑货币时间价值的管网经济性目标函数用数学模型可表示为：
2.2 供水管网优化设计可靠性以节点富余水头来表示，节点富余水头是指节点自由水头超过节点所要求的最小自由水头的水头，节点富余水头越小，管网中水压就越低，管网正常工作的概率就越大因此，节点富余水头与管网系统可靠性负相关[4]。用所有节点可靠性的加权平均值来表示，即：
在供水管网优化设计的数学模型中，这两项均是求极小值。采用线性加权法将多目标数学模型转化为单目标数学模型，假设管网的可靠性和经济性同样重要[4]，故对二者赋予相同的权重，均为 0.5，但是可靠性与经济性不在一个量级上相差很大，故可靠性应添加权重因子 ，则管网优化设计的目标函数可改写为：
2.3 供水管网优化设计约束条件
（1）水力平衡约束条件
3 遗传算法设计
3.1编码与初始化种群
由于标准管径为整数而且采用二进制编码时字符串过长，管径规格往往存在冗余问题，故采用整数编码，克服二进制编码频繁的编码与解码过程，提高了算法的实用性和计算效率。本文实例中有8种可选管径，采用整数[1，2，3，4，5，6，7，8]一一对应地表示，笔者应用matlab7.0中的round（1+7*rand（））函数随机生成1-8的任意整数，通过循环语句生成一组管径组合，即为一个染色体，种群规模设定为30，由30个染色体构成了初始化的种群。
3.2 适应度函数的分析与设计
对管网中压力和流速采用惩罚函数项加以约束， 则广义目标函数为：
3.3 交叉和变异算子的分析与设计
本文管网模型优化管段数为26，染色体长度较长，采用单点交叉容易破坏优秀个体，故笔者采用双切点交叉方法，有利于优秀个体的保护。杂交概率Pc为0.9，变异概率Pm为0.05，
3.4选择策略
3.5 育种算子设计
遗传算法以交叉实现局部搜索，变异实现全局搜索，但由于变异概率如果取得太大，算法将不能收敛，取得太小就会陷入局部最优。为解决这个问题，将每次迭代的优异种子进行保存，生成育种空间，对此空间中的种子进行高概率的交叉变异操作，然后将最高适应值的种子替换遗传算法的最劣个体，而当种群相似度达到阀值时，在育种算子中选择相似度最低个体带入种群中，扩展搜索空间。
4.应用实例
如图1所示，为单水源树状管网，由21个节点，20个管段组成，8中可供选择的管径规格，分别为90、110、125、140、160、180、220和225mm，管段长度及流量见表1，水厂的最高日最高时供水量为180m3/h，水泵净扬程为m，输水管采用PE管，水头损失计算采用海曾—威廉公式：
本例运算采用matlab7.0编程，计算机属性如下：采用2.5GHz Intel处理器，2GB内存，Win7 64位操作系统，基本遗传算法运行时间为0。734s，搜索到的最优解是7.288e+05，而育种遗传算法运行时间为3.218s，虽然育种遗传算法的时间较长，但其搜索效率更好，在200代时搜索到最优解6.264e+05，运行结果如图2所示。
从图中容易发现，基本遗传算法收敛速度慢，适应值呈小幅振动，在局部最优解范围内上下浮动，无法进一步收敛；而育种遗传算法，呈现出一条光滑收敛的曲线，当有更优解出现能快速捕捉，不会陷入局部最优解，且在120步时收敛得到全局最优解。
5.结语
传统遗传算法在求解组合优化问题时容易陷入局部最优解，导致未成熟收敛问题，使得遗传算法的应用受到很大限制，而加入育种算子后，种群的进化效率有了很大提高，且不会由于提高全局搜索能力导致的种群退化现象。以一个实例的运算对比育种遗传算法和基本遗传算法，比较直观的展现了育种遗传算法在给水管网优化问题中的优异性能。
参考文献
[1] 卢姗姗.城市给水管网水力特性分析研究.硕士论文[D].2012.
[2] 常晓宇，周春光，管恩政等.用育种算子改进遗传算法.吉林大学学报[J]，2005，23（2）.
[3] 严煦世，范瑾初.给水工程[M]。北京：中国建筑工业出版社，2008.
[4] 储成山.改进混合遗传算法用于给水管网优化设计的研究[D].天津大学，2006.
作者简介：姓名：李宣，学校：山东科技大学，研究方向：给水管网优化。