城市供水系统是由相互联系的一系列构筑物和供水管网组成^[1]。从整个供水系统投资的角度看, 建设供水管网所需资金的比例最大^[2]。供水管网的设计方案和施工水平, 对后期的运行管理费用以及供水系统的可靠性都有着重要影响。因此, 对供水管网系统进行优化设计, 在降低建设成本的同时提高管网系统的水力性能具有十分重要的意义。

　　 第二代非支配排序遗传算法 (NSGA-Ⅱ) 是供水管网优化领域一种常用的优化算法, 由Deb和Srinivas在2002年提出^[3]。其主要特点是:第一, 提出一种基于分级的快速非支配排序法, 降低计算复杂度;第二, 提出拥挤度和拥挤度比较算子, 保持种群多样性;第三, 引入精英策略, 有利于保持父代中的优良个体进入下一代^[3]。在NSGA-Ⅱ中, 负责产生子代个体的搜索算子是模拟二进制交叉 (Simulated Binary Crossover, SBX) 和多项式变异 (Polynomial Mutation, PM) ^[4]。

　　 NSGA-Ⅱ算法有6个参数, 分别是种群大小 (Population Size, PS) , 进化代数N, 交叉概率p_c, 变异概率p_m, 交叉分布指数η_c, 变异分布指数η_m。种群大小和进化代数共同决定了目标函数的评价次数, 在一定范围内, 目标函数评价次数越多, 算法的收敛性越好, 但优化时间也随之增加。p_c和p_m控制着种群进化过程中发生交叉或变异操作的概率。η_c和η_m控制着种群发生交叉和变异时子代个体与父代个体的距离。η_c和η_m可以取任意非负实数, 取较大值时产生的子代个体将以较大概率分布在距离父代较近的位置;反之, 取较小值时子代个体更有可能位于距离父代个体较远的位置^[4]。换句话说, 较小的分布指数意味着算法倾向于全局搜索, 而较大的分布指数意味着算法倾向于局部搜索。Deb等^[3]建议p_c取0.9, p_m取决策变量个数的倒数;对于η_c和η_m, Deb给出的推荐值为两个分布指数均取20^[3]。然而, 其测试案例所涉及的决策变量均是连续型变量, 管网优化设计通常是处理离散型变量, 因此, Deb推荐的参数取值不一定适用于管网优化设计。此后, 在供水管网优化研究中, 多数将p_c设为0.7～0.9, 将p_m设为决策变量个数的倒数^[5,6,7,8], 与Deb的推荐值十分接近, 但大部分的研究忽略了对分布指数的设置。此外, 一部分相关研究考虑了分布指数的影响, 但对η_c和η_m如何取值尚未形成统一的看法。例如:Wang等^[5]在用NSGA-Ⅱ求解12个供水管网的双目标优化问题时, 统一将η_c和η_m设为15和7;Zheng等^[6]在比较NSGA-Ⅱ和其他几种多目标优化算法的搜索性能时, 沿用了文献[5]的参数取值;Jayaram等^[7]在用NSGA-Ⅱ优化供水管网全生命周期费用时, 将η_c设为20, η_m设为100;Asadzade和Tolson^[8]在用NSGA-Ⅱ与一种新型算法进行对比时, 交叉和变异分布指数的设定值与文献[3]一致, 即两个指数都取20。

　　 基于此, 本文旨在通过对NSGA-Ⅱ关键参数的系统测试与分析, 发现潜在的影响规律并提出通用的参数设置原则。

　　 分别以最小化铺设管道的总费用C_total和最小化节点不足水头总和H_d为两个目标函数, 见式 (1) 和式 (2) :

　　 $\begin{array}{l}\text{m}\text{i}\text{n}C{}_{\text{t}\text{o}\text{t}\text{a}\text{l}}={\displaystyle \sum _{i=1}^{{\rm N}}C}{}_{i}L{}_i(1)\\ \min {\rm H}{}_d={\displaystyle \sum _{j=1}^{{\rm M}}\text{m}}\text{a}\text{x}({\rm H}{}_{\min }-{\rm H}{}_j;0)(2)\end{array}$

　　 式中N——管网管道数, 根;

　　 C_i ——更换管道的直径对应的单位管长花费, EUR/m;

　　 L_i ——第i根管道长度, m;

　　 M ——管网节点数, 个;

　　 H_min ——管网节点所需的最小水压, mH₂O;

　　 H_j ——第j个节点的实际水压, mH₂O。

　　 决策变量为管网中每根管道的管径。供水管网优化必须满足节点连续方程, 管网能量平衡方程, 管段压降方程, 节点水头约束条件及可选标准管径条件。各约束条件表达式见式 (3) ～式 (7) :

　　 节点连续性方程:

　　 $Aq+Q=0(3)$

　　 能量方程:

　　 $Lh=0(4)$

　　 管段压降方程:

　　 $h=sq{}^n(5)$

　　 节点水头约束条件:

　　 ${\rm H}{}_j\ge 0(6)$

　　 可选标准管径约束条件:

　　 $D{}_k\in \{D{}_1,D{}_2,\cdots ,D{}_z\}(7)$

　　 式中A——衔接矩阵 (联系矩阵) ;

　　 Q ——管网系统中的节点流量, m³/s;

　　 q ——管网系统中的管段流量, m³/s;

　　 L ——回路矩阵;

　　 h ——管网系统中的管段水头损失, mH₂O;

　　 s ——管网系统中的管段摩阻;

　　 D_k ——任意一根管道的管径大小, mm;

　　 D_z ——可选标准管径大小, 下标z为可选标准管径总数目, mm。

　　 本试验选用的案例管网为Balerma Irrigation Network (BIN) ^[9], 管网模型如图1所示。BIN管网位于西班牙阿尔梅里亚省, 是一个大型供水系统, 由443个需水节点和4个水源节点组成, 各节点所需的最小压力为20 mH₂O。BIN管网包含8个环和454条管段, 每条管段共有10种可选尺寸, 管径范围在125～600 mm。因此, BIN管网多目标优化设计问题的解空间包含10⁴⁵⁴种可能的组合方式。不同管径对应的管道单价以及更多BIN管网相关信息可以参考文献[9]。

　　 试验主要分为两个部分, 第一部分探究交叉和变异分布指数对NSGA-Ⅱ算法优化性能的影响, 第二部分探究交叉和变异概率对优化性能的影响。试验流程如图2所示。

　　 第一部分的试验固定交叉和变异概率, 观测NSGA-Ⅱ的收敛性对交叉和变异分布指数取值的敏感程度。交叉和变异概率取文献中的推荐值^[3], 即p_c=0.9, p_m=1/454=0.002 2 (454为案例管网的决策变量^[9]) 。理论上, 分布指数可以取任意非负实数^[4], 但是过小或过大都不利于算法收敛, 根据相关研究中广泛采用的取值范围, 将交叉和变异分布指数的范围设为[1 100], 进而确定一系列不同组合, 得到在推荐的交叉和变异概率下NSGA-Ⅱ优化性能最优的分布指数组合。

　　 第二部分试验固定交叉和变异分布指数 (即第一部分试验找到的最优组合) , 进行一系列单因素敏感性分析。具体来说, 先固定p_c=0.9, 观察不同的p_m对NSGA-Ⅱ收敛性的影响, 找到最优的p_m后, 再固定变异概率值, 观测不同的p_c对NSGA-Ⅱ收敛性的影响。

　　 上述试验都在C语言环境下完成编译;涉及水力计算的部分通过调用EPANET2的动态链接库实现^[10]。种群大小设为100, 进化代数设为50 000, 即目标函数的总评价次数为5 000 000;同时, 为了控制随机初始种群对结果分析的影响, 对每组参数组合都独立计算10次。这样的试验设计可以确保算法的充分收敛, 进而提高对比分析的可信度。

　　 在种群进化的初始阶段, 算法找到的管径的解集很可能会使管网部分节点存在负压, 这时种群还没有跳出非可行域。一般算法在进化足够大的情况下都能跳出非可行域。然而, 当算法的参数设置不尽合理时, 即使进化相当长的时间也有可能被困在非可行域内。因此, 本试验采用3种指标评价NSGA-Ⅱ算法的优化性能:①每个参数组合下跳出非可行域的种子数 (N_seed) ;②10组随机试验中, 节点不足水头总和H_d为0时对应的铺设管道费用的 平均值Avg (C_total^H_d=0) ;③Avg (C_total^H_d=0) 偏离已知最优解192.14 万欧元^[11]的百分比 (f) 。N_seed越大, 说明算法跳出非可行域的能力越强, 而Avg (C_total^H_d=0) 和f越小, 表明进化算法的收敛性能越好。

　　 不同交叉和变异分布指数下的结果如表1所示。表1从左往右是按f的大小升序排列, 越往前优化性能越好。可以看出, 最优的交叉和变异分布指数组合是[20 10], 在这个组合下, Avg (C_total^H_d=0) 只偏离了已知最优解1.47%。最后5组只有部分种子甚至没有种子跳出非可行域, 并且f也比其他14组更大。这5组的共性是η_c和η_m两个参数的取值都偏大, 而没有一个较小的参数来提供全局搜索。相反, 其他14组全部10个种子跳出了非可行域, f也能维持在一个较小值, 除了[20 30], 其他组都有一个参数取值较小 (≤10) 。所以可以认为, 两个分布指数必须有一个值较小 (≤10) , 才能使NSGA-Ⅱ的优化性能较优, 见表1。

　　 不同变异概率下的优化结果见图3。图3显示了固定η_c=20, η_m=10, p_c=0.9, 观测取不同p_m时对优化结果的影响。可以看出, p_m在文献推荐值0.002 2周围 (0.001～0.015) , f变化不大, 而当p_m>0.02时, f明显增大了。当p_m=0.01时, NSGA-Ⅱ优化性能最好, Avg (C_total^H_d=0) 只偏离了已知最优解的1.20%。

　　 不同交叉概率下的优化结果见图4。图4显示了固定η_c=20, η_m=10, p_m=0.01, 观测取不同p_c时对优化结果的影响。可以看出, p_c=0.75是NSGA-Ⅱ优化性能优劣的分界线, p_c 在0.75～0.95算法优化性要优于其在0.45～0.7;并且, 在p_c处于0.75～0.95范围内, f虽然有起伏, 但变化不大, 说明在p_c在该范围内, 对算法优化性能影响不大。当p_c=0.86时, NSGA-Ⅱ优化性能最好, Avg (C_total^H_d=0) 只偏离了已知最优解的1.15%。

　　 通过第二部分试验可以看出, 交叉和变异概率在文献推荐值周围较宽范围对NSGA-Ⅱ优化性能影响不大, 但在这个范围外, 算法优化性能会受到明显影响。

　　 为了验证以上基于BIN管网得出的参数设置原则, 本文又用NSGA-Ⅱ算法对英国埃克斯特市的供水管网 (EXN) 进行优化, 目标函数与BIN管网一致。EXN是由英国埃克斯特大学水系统研究中心建立的一个实际管网, 服务人口约为40万。EXN管网包含2 465根管道, 1 891个用水节点, 5个阀门以及7个水源节点, 节点所需的最小压力为15 mH₂O, 管网的拓扑结构如图5所示。图中加粗的位置表示由当地工程师根据经验挑选出来的567根瓶颈管道, 也是本次优化设计时考虑的全部决策变量。EXN管网的设计任务是确定在瓶颈管道所在位置铺设平行管道的最优方案。每条管道有10种不同的管径尺寸以及不铺设平行管共11种可选方案;因此, EXN优化问题的解空间共包含11⁵⁶⁷种可能的组合方式。

　　 本次研究中种群大小仍为100;为减小计算时间, 进化代数设为10 000, 即目标函数的总评价次数为1 000 000。同样, 为了控制初始种群对结果的影响, 每组参数组合都独立计算10次。NSGA-Ⅱ的参数取值和对应的优化结果如表2所示。参数组合1～4的交叉和变异概率都取文献中的推荐值, 但交叉和变异分布指数取不同值。由表2可知:采用文献中的推荐值 (即η_c=20, η_m=20) 并不是最优的参数组合;当η_c=20, η_m=1时NSGA-Ⅱ获得了最优的Avg (C_total^H_d=0) 。进一步观察发现:参数组合1和2对应的优化结果显著超过参数组合3和4, 组合1和2中至少有一个分布指数较小, 组合3和4中两个分布指数都偏大, 这与BIN管网得到的试验结果一致。组合5和6的交叉概率分别为0.75和0.95, 其他3个参数都相同。由表2可知:两组的优化结果十分接近。同样, 组合6和7除了变异概率相差5倍, 其他3个参数保持一致, 但两组的优化结果几乎一致。上述试验说明在一定范围内交叉和变异概率对优化结果的影响微乎其微。

　　 本文基于两个较大规模供水管网系统的多目标优化设计问题对NSGA-Ⅱ的4个关键参数进行敏感性分析, 系统探究了交叉概率、变异概率、交叉分布指数和变异分布指数对算法优化性能的影响, 主要结论如下:

　　 (1) 交叉和变异分布指数对NSGA-Ⅱ的搜索性能有显著影响。分布指数取值偏大意味着NSGA-Ⅱ侧重局部搜索, 而取值偏小意味着NSGA-Ⅱ侧重全局搜索。两个参数必须至少有一个取较小值才能使NSGA-Ⅱ维持较优的搜索性能。如果没有合理设置这两个参数, 整个种群甚至无法找到可行解 (即H_d=0) 。

　　 (2) 与分布指数相比, 交叉和变异概率对NSGA-Ⅱ的搜索性能影响较小。交叉和变异概率的取值在以文献推荐值为中心的较大邻域范围内, 对NSGA-Ⅱ的搜索性能没有显著影响。

　　 (3) 基于本文的研究结果, 采用NSGA-Ⅱ求解管网多目标优化设计问题时, 针对4个关键参数取值的建议如下:交叉和分布指数在1～20, 交叉概率在0.75～0.95, 变异概率为文献推荐值, 即决策变量个数的倒数。