供水管网是城市基础设施的重要组成部分,在城市发展和保障人民生活中发挥着重要作用。随着最优化理论及计算机技术的发展,Simpson等^[1]首次将遗传算法运用于供水管网优化设计中,与枚举法和非线性编程技术相比,遗传算法在较少的评估中能找到全局最优解。之后出现的蛙跳算法、差分算法等元启发式算法也应用到管网优化设计中。在众多元启发式算法中,差分算法(Differential Evolution,DE)凭借其原理简单、受控参数少、鲁棒性强等特点脱颖而出^[2]。由于DE算法具有向种群个体学习的能力,使其拥有其他进化算法无可比拟的性能。Vasan等^[3]首次将DE算法用于供水管网优化设计,并得出DE算法的寻优性能至少与其他元启发式算法一样好,甚至更好的结论。DE算法凭借其较强的搜索能力,成为近年来应用于供水管网优化研究中的热点。然而,DE算法自身存在易早熟收敛、陷入局部最优的缺陷。

本文对DE算法中的选择步骤进行了改进,用unique方法将交叉步骤代替,使用变异因子F在[0,1]间随机选择原则,结合sortrows排序选择方法,提出了一种改进差分进化算法,以提高DE算法的全局搜索性和局部收敛性。

本文涉及的NYTP管网模型的目标函数如式(1)所示:

$C{}_{\min }={\displaystyle \sum _{i=1}^{np}(}1.1D{}_i^{1.5}L{}_i)(1)$

式中 C_min——管网总成本,$;

D_i ——第i段管径,in(1 in=25.4 mm);

L_i ——第i段管长,ft(1 ft=0.305 m);

np ——管道数量。

与上述目标函数一起使用的连续性约束、节点水头约束、等径约束条件如式(2)～式(4)所示:

${\displaystyle \sum Q}{}_{\text{i}\text{n}}-{\displaystyle \sum Q}{}_{\text{o}\text{u}\text{t}}=Q{}_{\text{e}}(2)$

式中 Q_in——流入节点,CFS(1CFS=0.472 L/s);

Q_out ——流出节点,CFS;

Q_e ——外部流入或节点的需求量,CFS。

${\rm H}{}_j\ge {\rm H}{}_j^{\min },j=1,\cdots ,nn(3)$

式中 H_j——第j节点水头,ft;

H_j^min ——第j节点最小水头,ft。

$D{}_i=[D]\forall i\in np(4)$

式中 D_i——第i管道管径,in;

[D] ——市售标准离散管径,in;

np ——管道数量。

在本研究中,使用了组合的模拟优化计算机模型,该模型将DE算法与管网水力模拟软件EPANET 2.0版集成在一起。计算机编程代码是使用MATLAB为DE算法编写的,而EPANET是通过EPANET Toolkit链接。在DE算法中,生成的十进制管径值在传递到水力计算软件之前编码成离它最近的离散管径。

传统DE算法采用实数编码,进化流程分为3个步骤:变异、交叉和选择。其中,变异操作是通过差分策略实现个体的变异,即通过随机选取种群中的2个不同个体进行加权差(收缩权重因子F)后,扰动第三个待变异的个体,这也是区别于遗传算法的重要标志。本研究选择的差分策略为DE/rand/1/bin,其差分表达式为v_i,G=x_r1,G+F(x_r2,G+x_r3,G),其中,F是控制差分向量收缩的权重因子。当F取较大值时,可以保持初期种群个体的多样性,避免早熟,即扩大全局搜索能力,反之,则可以保持种群中优良个体信息,增强全局最优解的搜索概率,即增强局部收敛性。通常的做法是根据供水管网的特性,F在[0.5,1]中取经验值,正是由于供水管网优化问题是非线性问题,而F在寻优过程中没有改变,无法较好地满足变异阶段中算法性能对收缩权重因子F的特殊要求。因此采用参数自适应的DE算法,将F建议为[0,1]间的均匀分布随机数,即F～U[0,1],减少需要调整的参数,随机选择在一定程度上避免控制参数所影响的早熟收敛。改进差分算法的变异策略见式(5):

$v{}_{i,G}=x{}_{r1,G}+\text{r}\text{a}\text{n}\text{d}U(x{}_{r2,G}+x{}_{r3,G})(5)$

式中 v_i,G——第G代生成的变异向量个体;

x_ri,G ——第G代种群中选取的随机向量个体,i=1,2,3…N;

rand U ——取[0,1]间的均匀分布随机数。

DE算法中的交叉步骤是指变异产生的中间体个体与父代个体进行交叉操作后产生子代的过程,其作用是保持种群的稳定性,并引导进化向最优解方向进行。

基于对上述DE算法交叉操作原理的深入理解,在不破坏算法本身性能的前提下,本研究对交叉操作进行了改进及深化,即用unique算法代替传统的交叉步骤,并结合sortrows排序选择的方法,实现DE算法中的“交叉”和选择这两个步骤。原理如图1所示:首先将变异产生的中间体H与父代X放入空矩阵X-H,使用unique算法剔除矩阵中父代X与中间体H重复的向量组,目的是保持种群的多样性;其次,将剔同后的矩阵X-H按照是否违反设计约束分为违反约束矩阵P₁和满足约束矩阵P₂;其中,矩阵P₁按照违反程度进行sortrows排序,矩阵P₂按照目标函数值进行sortrows排序;最后,将新矩阵P₁′和P₂′按P₂′在前的方式合并为一个新矩阵P₀。这样,一方面可以克服参数CR固定或线性改变所带来的不足,增加种群的多样性,另一方面可以通过sortrows排序加快向最优解收敛,并提高计算效率。

为了保证评价算法性能的客观性以及算法间比较的公平性,本研究在保留最低造价方案运行次数和功能评估次数的基础上,添加以下评价指标:①最优解的平均值;②最优解的标准偏差;③全局最优解的百分比。

NYTP管网是Schaake和Lai^[4]4]于1969年提出的一个从单一水源(水库)供水的重力流管网系统,原管网由20个节点,21根管道和1个水库组成,如图2所示。因现有管网设施无法满足节点压力下所需用水量,需安装与现有管道平行的新管道。因此,优化问题为确定平行管道直径,使成本最小化。管网中所有现有管道和新管道,Hazen-Williams粗糙系数均为100。除了节点16和17的水力梯度线分别为260.0 ft和272.8 ft,所有节点的最小允许水力梯度线为255.0 ft。Suribabu等^[5]5]给出了该管网的详细信息,包括水头约束、管道成本和用水需求等,由于该模型管段数为21,市售可选管径有15种,且将“造价为0”作为第16种选择,所以该模型的总搜索空间为16²¹(1.934×10²⁵)。

本研究改进DE算法参数种群NP设置为100,最大迭代步数设置为100,独立运行30次,每次运行进行10 000次评估。图3显示出改进DE算法的收敛曲线图,图4表示运行10次时收敛代数,其中,改进DE算法求得的最优造价为3 864万美元。表1对比了改进DE算法与文献中传统DE算法求得的NYTP管网数据,可以看出,改进DE算法运算得到的最小值与其他两种传统DE算法一致,在种群大小一致的情况下,评估次数比传统DE算法低,搜索成功率达到80%,标准差为0.371,说明在搜索空间中,运算结果密集分布在可行域中的可行解附近。所以,改进DE算法能以较小的计算量求得最优解,且搜索成功率较高。

改进DE算法与传统DE算法相比较,改进差分算法具有较快的计算能力,较强的搜索能力与收敛精度,在保证供水安全可靠性的前提下,能达到管网运行经济性的要求,本研究未讨论种群大小对优化问题的影响以及对其它供水管网的适应性,下一步将对以上两个问题做深入研究。