自适应遗传算法在给水管网优化中的应用

作者:刘书明 李婷婷 王晓婷 吴雪
单位:清华大学环境学院
摘要:为求解管径优化设计问题, 众多学者采用遗传算法 (GA) 进行优化计算, 然而传统的遗传算法搜索效率偏低。针对此问题, 提出一种自适应遗传算法 (AAGA) 。根据管段的流速和管径值, 对遗传算法中下一代个体的管径可选择范围进行自适应调节, 进而提高进化效率。以纽约隧道管网扩建问题为案例, 对该方法进行了验证。结果表明, 自适应遗传算法比传统遗传算法具有更高的收敛速度, 优化效率更高。
关键词:自适应 管径范围 遗传算法 给水管网 管网优化
作者简介:刘书明, 通讯处:100084北京市清华大学环境学院403 电话:18601283668 E-mail:shumingliu@mail.tsinghua.edu.cn;

 

0前言

   随着我国经济的发展和城市人口的激增, 现存的一些城市基础设施已不能够满足城市发展的需求, 特别是城市的供水系统[1]。目前, 城市给水管网的新建和扩建是解决城市供水设施不足的主要方法。在给水管网的建设中, 有50%~70%的投资费用花费在管道的购置和敷设上[2]。因此, 在满足水力条件下, 合理地选择管段的管径和管材, 对于提高给水管网的经济性和保障供水安全具有重要的意义。

   给水管网的优化设计问题是一个典型的非线性问题。随着计算机科学技术的飞速发展, 有着随机搜索全局优化解的进化算法是目前解决非线性问题常用的优化算法之一。遗传算法 (Genetic Algorithm, GA) 具有收敛快的特点, 近年来成为管网优化的常用方法。常永第[3]使用遗传算法求解了以经济性和可靠性为目标的给水管网优化数学模型, 获得了比传统设计方案更好的结果。然而传统遗传算法存在计算时间长, 易陷入局部解的问题。为了解决这一问题, Keedwell等[4]提出一种基于自调节局部约束的启发式的改进遗传算法, 并应用于管网案例进行验证, 获得了比传统遗传算法更好的结果。

   但是在求解管网优化问题时, 传统遗传算法以及改进型遗传算法[5~9]通过交叉算子和变异算子确定下一代个体, 每一个基因片段所对应的管径值的可选范围是固定的。这一进化机制的优点是算子相对简单, 然而可能会导致效率低下。这是由遗传算法本身的随机特征决定的。优化过程中的计算量与每代进化过程中的可选择范围有关, 因此, 通过调整管径的选择范围, 可减少优化计算次数, 提高收敛效率。

   针对此问题, 本研究结合管网优化问题的属性, 提出了一种以管段的流速和管径为控制条件的管径可选范围的确定方法即自适应遗传算法 (Auto A-daptive Genetic Algorithm, AAGA) , 实现遗传算子搜索空间的自适应调节, 从而提高优化效率。本文采用纽约隧道管网扩建案例, 对该自适应算法的性能进行了验证。

1 给水管网优化的数学模型

   给水管网优化的数学模型的目标函数是管网的最低建造费用, 决策变量是离散管径, 约束条件是管网的基本水力条件及实际可选择的管径。

1.1 目标函数

    

   式中f———管网的造价;

   Di、Li———分别为管段i的管径和管长;

   N———为管网中新建管段的总数;

   C———为相应管径的单位管段的造价。

1.2 水力约束条件

    

   式中Qin、Qout———节点的流入和流出流量;

   Q———外部流入或节点用户所需流量;

   F (H) ———能量守恒方程;

   C、β、γ———式 (3) Hazen-Williams公式中的相关系数;

   Hmmin———节点满足的最小压力水头。

   使用已被广泛应用于管网平差的EPANET2.0水力学计算引擎来完成管网的水力学分析计算。

1.3 管径约束条件

    

   式中Dmin、Dmax———分别为离散管径的最小值和最大值。

2 自适应遗传算法

   自适应遗传算法是一种在传统遗传算法基础上, 结合了管段的流速和管径值, 在进行交叉和变异的遗传过程之前, 加入了自适应管径范围控制调节过程的新进化算法, 其具体流程如图1所示。

图1 自适应遗传算法

   图1 自适应遗传算法

    

2.1 种群的初始化

   为了避免二进制编码的冗余问题, 本文选取整数编码的编码方式, 对给水管网优化问题中目标管段的管径通过随机函数进行一系列的整数赋值, 生成管径组合即个体。不同的个体组成了初始化的种群。

2.2 个体评价

   因为考虑到在实际大规模管网中, 若让种群中所有个体均满足水力要求不太实际, 而且易出现临界管径连接成环的现象[10]。因此, 个体的适应度评价函数包括管网的造价和节点水压的惩罚因子两部分。其中, 惩罚因子是不满足水力条件的节点数量对应的惩罚值。

2.3 自适应调节过程

   完成个体的评价和选择后, 对个体的管径范围, 结合流速条件进行调节并为管段取值, 进而产生下一代个体。自适应调节流程如图2所示, 原可选择管径范围从最小值d1开始, 依次递加a至最大值dm, 共有m个可选择离散管径, 但进入自适应调节过程后, 其变化过程如下:

   (1) 从第n代种群适应度排名第三位的个体开始, 先进行水力核算, 然后从左向右调取个体即管径组合中每一管段的流速Vi和管径值dj, 将流速Vi与设定的控制流速VP进行比较, 如果管段的流速Vi小于或者等于设定的控制流速VP时, 该管段的可选择管径范围就会变为[d1, …, d (j-1) ], 例如在图2中, V1和Vk小于控制流速, 且其管径值D1和Dk分别为d15和d18, 那么其对应的可选择管径的最大值由dm分别变为d14和d17, 可选择管径范围由m个管径分别变为14个和17个管径。

   (2) 通过随机函数从新的可选择管径范围选取管径值来替换旧的管径值, 如D1和Dk, 通过随机函数从新的管径范围内取值后分别变为d5和d10, 从而调节了第n+1代的管径范围和管径值。

图2 自适应调节过程

   图2 自适应调节过程

    

2.4 遗传操作过程

   选择过程。为避免种群的适应度函数出现朝不收敛方向进化的情况, 在选择过程中保留父代中适应度排名前两位的个体为子代个体, 其余父代个体进行交叉和变异之后产生新的子代个体。

   交叉过程。本研究选取单点交叉, 即在一定的概率下发生交叉过程, 由随机函数产生个体基因中的一个交叉点, 父代在交叉点进行交叉, 产生新的子代个体。

   变异过程。为了保证种群的多样性, 防止早熟的现象出现。对种群父代个体以小概率, 随机产生变异位置, 进行单点变异操作。

3 案例应用

3.1 案例管网

   纽约隧道管网是管网优化计算邻域的经典算例, 以该管网为案例, 对提出的自适应遗传算法进行验证。如图3所示, 纽约隧道管网由1个水源、20个节点和21根管段组成。因城市的发展和人口的增多, 使得原有管网的供水量增加, 进而导致水压不足, 所以需要对管网进行扩建改造, 来满足用户的需求[11]

图3 纽约隧道管网案例

   图3 纽约隧道管网案例

    

3.2 管网扩建方案及其优化

   选取在管段15、16、17、18、19和21的旁边平行布设新管线的管网为扩建方案, 可选择离散管径范围为 (914~5 182 mm) , 基于MATLAB和EPA-NET软件平台采用自适应遗传算法和传统遗传算法对管网进行优化, 2种算法的参数相同 (包括种群大小、交叉概率和变异概率等) 。

3.3 试验结果

   自适应遗传算法和遗传算法获得相同造价时的优化迭代曲线如图4所示。从图4可以看出, 尽管自适应遗传算法在初始化种群时的造价4 896万美元远高于遗传算法初始化种群所得造价4 499万美元, 但是随着种群不断地进化, 在获得相同的优化造价结果4 098万美元时, 自适应遗传算法所需的遗传代数为14代, 远小于遗传算法所需的遗传代数39代。这是因为在种群的进化过程中, 自适应遗传算法结合优化问题的水力属性, 调整了管径的选择范围, 减少了优化计算次数, 提高了收敛效率。

图4 AAGA和GA管网优化迭代过程

   图4 AAGA和GA管网优化迭代过程

    

3.4 自适应调节过程

   表1为某平行敷设管段的管径范围在自适应调节过程中发生的变化。如表1所示, 在自适应遗传算法优化管网造价的迭代过程中, 当迭代代数为1, 6, 11时, 管段的流速低于控制流速VP, 且旧管径值均为3 048 mm, 因此该管段的管径范围由最初的[914, …, 5 182mm]变为[914, …, 2 743mm], 并且随机函数从新的管径范围内, 分别选取了新管径值1 829mm, 2 134 mm和914 mm。同理, 在进化代数分别为13和14时, 该管段的管径范围和管径值也发生了变化。在算法快速收敛的进化过程中, 该管段的管径范围在自适应过程的调节下, 发生了5次变化, 被调节频率较高。这是因为自适应调节过程对加快算法的收敛有着重要的引导作用。

3.5 参数优化

   在参数优化的试验中, 流速参数是指优化算法中的控制参数值VP, 并非管段的实际流速值, 设置参数梯度为0.05m/s, 测试参数范围为0~1.25m/s, 所得的优化结果如图5所示。从图5可以看出, 当以流速0.25m/s为控制参数值时, 管网造价的最优方案是3 960万美元。该方案中的平行布设管段流速值如表2所示。从表2中可以看出, 最优造价方案的平行布设管段流速值均大于0.25m/s且大部分均为较高的流速值。因此, 控制参数的最优值是0.25m/s。此外, 筛选流速条件在0~0.75m/s时所获得的管网优化造价整体上比较相近, 而且优化结果明显要比流速在0.8~1.25m/s时所对应的优化结果好。当控制参数所选的流速值较高时, 水头损失会很大, 导致部分水压不能满足管网的压力约束条件, 从而使得以高流速为控制参数时, 所得到的造价较低的方案被淘汰, 使算法陷入局部最优解, 优化结果变差。

   表1 纽约管网自适应管径范围控制过程   

表1 纽约管网自适应管径范围控制过程

   注:管段流速<控制流速。

图5 流速参数优化试验结果

   图5 流速参数优化试验结果

    

   表2 最优造价方案的平行布设管段的流速值   

表2 最优造价方案的平行布设管段的流速值

4 结论

   结合所要求解的管网优化问题的属性, 提出了一种以管段的流速和管径为控制条件的自适应遗传算法, 并通过对纽约隧道管网扩建案例的研究来对算法的性能进行验证, 研究结果表明:

   (1) 基于优化问题属性的自适应遗传算法避免了在遗传过程中管径范围随机搜索的不合理性, 以第n代中的管径和流速值为依据, 调整第n+1代中的管径可选范围, 实现对管径范围的自适应调节。

   (2) 通过求解纽约隧道管网案例得知, 在获得相同的管网优化结果时, 自适应遗传算法比传统遗传算法使用遗传代数更少, 搜索效率更高, 优化效果更明显。

   (3) 自适应遗传算法的提出, 为解决其他复杂的优化问题, 提供了一种有效的解决思路, 即根据优化问题自身的属性和特点, 合理调控决策变量的选择范围, 与优化算法相结合使用, 从而更好地发挥算法性能, 提升搜索效率。这对于实际的规模浩大, 复杂的优化工作有着十分重要的意义。

  

 

  
 

    

参考文献[1]陈胜明.城市供水系统智能优化调度研究:[学位论文].浙江:浙江大学, 2007

[2]周平, 张戎.浅析给水工程中输配水管道投资的关键控制点.水工业市场, 2007, (4) :37~39

[3]常永第.基于遗传算法的供水管网优化研究.哈尔滨商业大学学报 (自然科学版) , 2009, 25 (5) :535~539

[4] Keedwell E C, Johns M B, Savic D.Adaptive Locally Constrained Genetic Algorithm For Least-Cost Water Distribution Network Design.Journal of Hydroinformatics, 2014, 16 (2) :288~301

[5]王瑛, 魏戈.基于改进遗传算法的给水管网优化.供水技术, 2009, 3 (6) :25~28

[6]余嵘, 严程, 逯佩宁.自适应罚函数遗传算法对给水管网优化的研究.给水排水, 2016, 42 (4) :136~140

[7] 王冰, 魏连雨.自适应遗传算法在给水管网优化中的应用.城市建筑, 2016, (14) :386~387

[8] Dandy G C, Simpson A R, Murphy L J.An improved genetic algorithm for pipe network optimization.Water Resources Research, 1996, 32 (2) :449~458

[9] Johns M B, Keedwell E, Savic D.Pipe smoothing genetic algorithm for least cost water distribution network design//Conference on Genetic and Evolutionary Computation.2013:1309~1316

[10]王亚仁, 秦亚斌, 高尚, 等.平原农村给水厂供水管网的优化设计.给水排水, 2016, (S1) :262~265

[11]刘书明, 陈晋端, 王琦, 等.遗传算法与其变型求解管径优选问题的比较.清华大学学报 (自然科学版) , 2010, (11) :1870~1874
491 0 0
文字:     A-     A+     默认 取消