给水管网是城市给水系统的重要组成部分，其投资往往占整个给水系统工程总投资的60%~80%，而且运行期间还需投入庞大的运行动力费及管理维修费^[1]。当前我国各城市给水管网都已达到一定规模，原有管网出现外壁腐蚀、爆管漏损率高等问题；随着城市的快速发展，部分管道无法满足供水需求；城市街道拓宽、其他管线的施工使现有管道需做相应调整。针对这些问题，需对给水管网进行改扩建优化设计。

为了优化给水管网，许多方法被广泛应用，如遗传算法^{[2, 3]}、蚁群算法^[4]、启发式算法^[5]、差分算法^[6]和足球联赛竞争算法^[7]。其中粒子群(particle swarm optimization,PSO)算法因其可调参数少及具有本质的并行性、全局搜索能力强、整体收敛速度快等优点，展现了较大的解决多种优化问题的潜力和发展空间，同时PSO算法在解决给水管网这类组合优化问题时也存在以下缺点：容易陷入局部极值、局部搜索能力差导致的搜索精度不高。

针对PSO算法在优化给水管网系统时容易陷入局部极值的问题，文献[8]提出在PSO算法中加入遗传算法的交叉和变异操作，对新产生的位置进行随机变异，避免算法陷入局部极值，并通过优化实际管网案例表明改进算法的有效性，同时算法在搜索后期收敛速度变慢；文献[9]提出在PSO算法的速度公式中加入一个收缩因子，实现算法的离散优化，删除种群中重合的点并随机产生相应的新个体，有效增加了种群多样性，避免算法陷入局优，同时算法的局部搜索能力有待加强；文献[10]通过判断2个粒子的空间距离提出聚集度的概念，并根据聚集度大小对粒子进行变异，避免算法陷入局优，以上随机增加种群多样性的机制在一定程度确实能避免算法陷入局优，提高全局搜索能力。针对PSO算法在优化给水管网系统时由于局部搜索能力差导致的搜索精度不高的问题，许多学者通过改进参数的调整机制，平衡了算法的全局和局部搜索能力，或在算法中加入局部搜索机制增强算法的局部搜索能力。文献[11]通过对自动学习机的研究，提出自动学习调整权重和加速系数的方法，对比冒险和保守2个调整策略，仿真结果表明具有学习自动调整的冒险策略能更高效地平衡算法的全局和局部搜索能力，提高算法的搜索精度，但算法收敛速度变慢；文献[12]提出在PSO算法中加入差分进化算法的变异和选择操作，对种群中的个体极值进行变异操作，相当于对个体极值的周围进行局部搜索操作，增强了算法的搜索精度；文献[13] 提出根据每个粒子与全局最优粒子的不同，评估种群粒子的相似度，利用相似度大小对惯性权重进行动态调整，根据种群分布状态，在搜索后期增强算法的局部搜索能力，提高搜索精度。根据以上分析可知，当前改进的PSO算法在优化给水管网问题时的性能得到一定程度的提升，同时仍存在待提高的研究方向。

PSO算法的3个参数ω、c₁、c₂对其寻优效果有重要影响，惯性权重ω平衡算法的全局和局部搜索能力，加速系数c₁可以调节粒子飞向自身最好位置的步长，加速系数c₂可以调节粒子向群体最优位置的飞行步长。因此，本文将继续研究这3个参数的调整策略，并根据以上3个参数的调整思想，为动态评估种群中各粒子分布状态，实现算法自适应性，对种群粒子进行收敛性分析，定义种群粒子相似度的概念，提出一种参数自适应粒子群算法(parameter adaptive particle swarm optimization,PAPSO)，将改进的算法用于优化实际的管网改扩建案例，取得较好的效果。

给水管网系统改扩建优化设计是在改造现有旧管网、发挥旧管网输水能力的基础上，决定如何经济合理的增敷新管^[14]。使新旧管网满足水量、水压、水质的要求，并使管网建造和运行年折算费用最低。

给水管网改扩建优化的目的就是建立一个全面、统一的给水管网改扩建优化设计模型，运用现代智能算法，寻求经济合理的改扩建方案^[15]，目标函数是方案优劣的评价标准，如式(1)所示：

式中：i₀为基金收益率，m为大修理基金提取率，k为铺设管道数目，a、b、α为管段造价系数，E为电费价格，η为泵站效率，D_i为第i管段的直径，L_i为第i管段长度，x_i为新建或改扩建管段，T为投资回收期，T₁、T₂为供水时间和传输时间，Q_j、H_j、Q_j′、H_j′为第j泵站高峰用水和最大传输时的流量及扬程，γ₁、γ₂为供水能量变化系数。

给水管网的优化方案需满足一定的约束条件，依据给水工程的规范要求，目标函数的约束条件如下：

1)节点流量连续性约束

2)能量平衡约束

3)节点水压约束

4)最小管径及标准管径约束

5)水流流速约束

6)旧管约束

PSO算法结合了生命科学和优化计算的优点，群体中的个体代表问题的一个潜在解，若优化问题的搜索空间是n维的，则第i粒子的位置和速度可分别表示X_i=x_i1,x_i2,…,x_in、V_i=v_i1,v_i2,…,v_in。粒子根据速度和位置公式迭代如公式(8)和(9)所示。

式中：ω决定先前速度对现在的影响程度；Y_i为个体极值；Y_g为全局极值；c₁、c₂为粒子受到个体认知和社会认知的影响程度；r₁、r₂为0~1的随机数。

粒子位置和速度变化过程的分析在本质上是一样的，为了描述粒子运动轨迹，本文只分析粒子的位置变化过程。为便于分析和表达，首先将问题空间简化为一维的，仅研究某一个粒子的运动轨迹，并暂时先假设Y_i、Y_g不变，用φ₁、φ₂表示式(9)中的c₁r₁和c₂r₂，且为常数，于是得到粒子i的状态方程组(10)、(11)^[16]。

将式(11)代入式(10)可得

将式(10)中的时间后推一步，代入式(12)，并将该式中的时间前推一步可得一个二阶差分方程，如式(13)所示。

多个粒子位置的发散将使整个种群发散，粒子位置变化过程的稳定性对种群的行为将产生重要影响，故对粒子位置变化过程的稳定性进行分析，将式(13)取Z变换得

式中:J=φ₁+φ₂-1-ω。式(14)是一个线性系统，对应的特征方程为

将代入式(15)，对其进行双性变换得

该线性系统稳定的充分必要条件是特征方程各项系数均为正值，因此可得到粒子的位置变化过程稳定条件为

在算法迭代过程中，使算法参数始终满足式(17)，则由Z变换的终值定理可得

粒子群在寻优过程中Y_i将逐步趋向Y_g，因此在无限的搜索时间内，所有粒子的位置将逐步靠近并停止在处。通过大量实验研究^[17]发现，粒子轨迹收敛到固定点的概率与参数选择密切相关，若满足式(17)，则绝大多数粒子轨迹会收敛到固定点，各类问题函数值的分布都有一定规律，即当满足稳定条件时，多数粒子能收敛到固定点，并能为找到最优位置提供一定的线索。

粒子适应度值能分辨位置的好坏，为充分利用粒子适应度分布情况动态调整算法参数，进行上述的粒子轨迹分析，可知所有粒子的位置最终停止在Y_g处，但在种群迭代过程中的绝大部分时间里粒子是向靠拢的，故将其定义为期望粒子位置x_e。其中Y_i对应的适应度值为f_pBest，Y_g对应的适应度值为f_gBest，故定义期望适应度值f_e如下：

惯性权重的调整很大程度上决定了PSO算法的优化性能，其大小的调节具有一定规律，且与种群分布和单个粒子位置密切相关，粒子在迭代过程中相似程度越来越大，通过种群分布状态，利用粒子相似程度来调节惯性权重，进而分析和改进PSO算法，提出粒子相似度s(i,e)如式(20)所示：

式中：s(i,e)表示第i粒子与期望粒子的相似度，f_i为第i粒子的适应度值，D_max、D_min是固定正常数。文献[13]中基于空间距离提出相似度的概念，表示的是每个粒子和当前的全局最优粒子的相似程度。本文分析了粒子运动轨迹，提出相似度的概念来表示粒子与期望粒子的相似程度，并自适应调整惯性权重和2个加速系数，同时实现变异的自适应性，有效平衡了粒子群算法的全局搜索能力和收敛速度。

PSO算法搜索前期选择较大权重值，加强粒子探索能力，后期选择较小权重值，保持算法收敛速度，这种思想被广泛采用。但所有粒子的权重被统一调整，忽略了粒子之间的差异性，若早期就有粒子找到全局最优点，却因其权重过大而跳出，则会降低算法搜索效率。为此，本文设计出一种根据各粒子与期望粒子相似度不同而动态调整权重的PSO算法，公式为

与期望粒子相似度较小的粒子，权重应较大，加快粒子探索整个解空间；反之，其权重应较小，这样可使该粒子在期望最优位置领域内进行微小探索，加强粒子的开发能力。

加速系数c₁是个体认知，c₂是社会认知，算法搜索初期，c₁应较大，增加种群多样性，c₂应较小，避免种群陷入局部最优；搜索后期，逐渐找到最优区域，c₁应较小，加快收敛速度，c₂应较大，领导种群趋向全局最优位置。结合以上c₁，c₂的调整思想，提出其迭代公式如下：

PSO算法在迭代过程中会因种群多样性的缺失而陷入局部最优，为增加种群多样性，对种群粒子进行变异，当粒子与期望粒子相似度越大时，对应粒子变异的概率应越小，反之亦然。定义变异概率p_im和变异条件分别如下：

为有效平衡算法的全局搜索能力和收敛速度，将混沌变异和Gaussian变异分期交叉进行，整个迭代过程分为4个阶段，每个阶段的前20%的迭代步数进行混沌变异，后5%的迭代步数进行Gaussian变异。利用混沌的遍历性，充分增大种群多样性，如式(26)所示；利用Gaussian变异的局部搜索能力，加快算法的收敛速度，如式(27)所示。

式(26)中：λ_ij^(t)表示第t步混合演变后的值，当u=4，λ_ij^(t)∈(0,1)，且λ_ij^(t)0.25,0.5,0.75时，将产生混沌现象，λ_ij(t)在(0,1)内遍历。

Gaussian变异就是对原有粒子位置产生一个服从Gaussian分布的随机扰动项，其中δ为Gaussian分布的标准差，μ为期望，δ越小分布会越集中在x=μ的位置，反之会越分散。

变异的位置为x_ijm，公式为

变异后粒子的新位置为该粒子上一代位置与变异位置连线的中点，公式为

分期变异机制的主要特点：通过评估整个种群的分布情况，通过该粒子与期望粒子相似程度大小来决定是否对其变异；2种变异方法分期交叉进行，很好地平衡了种群多样性和算法的收敛能力，在前期避免算法陷入局优，后期可以使算法快速找到全局最优值。

设微粒数为N，问题的维数为D，最大迭代步数为T_max，本文算法描述如下：

1)初始化，包括各参数：N、x、v、T_max，随机产生N个粒子及其初始速度，并计算适应度；

2)更新粒子的位置和速度；

3)评价种群中各粒子的适应度；

4)根据适应度值更新粒子的个体极值Y_i；

5)根据适应度更新种群的全局极值Y_g；

6)计算粒子之间的相似度s(i,e)，并根据式(21)更新惯性权重；

7)根据式(24)计算变异概率，并判断是否满足变异条件，若满足变异条件，则根据式(26)~(29)进行分期交叉变异，重新计算粒子适应度，并更新Y_i、Y_g；

8)判断算法的终止条件，若满足则停止，输出相关结果；否则转2)。

为了验证算法的有效性，将PAPSO算法用于优化汉诺塔管网和纽约管网，2个经典管网的布局图、节点水压和管段长度等详细数据参照文献[18]。

根据汉诺塔管网实际问题，进行参数敏感性分析后，PAPSO算法在整个搜索过程中，各参数设置如下：ω_max=0.9，ω_min=0.4，c₁=2.05，c₂=1.45，N=300，T_max=100。图 1为汉诺塔管网造价收敛曲线，改进的PAPSO算法在第31步就找到了全局最优值，具有较快的收敛速度。

图 1 汉诺塔管网造价收敛曲线 Fig. 1 The convergence curve of Hanoi cost

图选项

对于汉诺塔问题，通过EPANET2.0(ω=10.667)水力模拟计算验证，目前最优的解决方案造价是6.081×10⁶美元。表 1列出了遗传算法、混合粒子群差分算法、自适应粒子群算法、差分算法和本文提出的PAPSO算法优化汉诺塔问题的结果对比，从表中可以看出各个算法都找到了全局最优值，但本文提出的PAPSO算法经过34 000次函数评价就找到了全局最优方案，改进算法需要的评价次数较少，且该算法有95%的搜索成功率，具有较高的搜索效率和较强的鲁棒性。

根据纽约管网实际问题，PAPSO算法搜索过程中种群规模N取120，其他参数设置与优化汉诺塔管网时相同。图 2为纽约管网造价收敛曲线，可以看出该算法3次跳出局部极值后在第22步就找到了全局最优造价方案38.52×10⁶美元。

图 2 纽约管网造价收敛曲线 Fig. 2 The convergence curve of New York cost

图选项

表 2列出了不同算法优化的纽约管网扩建方案，对纽约管网进行改扩建优化设计后，没有列出的管道不需改变管径值，对应列出的管道编号新的管道铺设情况是优化方案给出的管径与原管径平行铺设。文献[19]得到的优化方案造价为38.64×10⁶美元，高于本文得到的优化方案，文献[20]提出的改进的遗传算法得到造价为37.13×10⁶美元的优化方案，水力验证时通过EPANET2.0(ω=10.667)水力模拟计算，可知节点16、17和19不满足最小节点水压，方案不可行。文献[21]与本文均得到造价为38.52×10⁶美元的最优方案，均满足水力约束条件，PSO-DE算法迭代到26步找到最优值，PAPSO算法在第22步即找到最优值。

本实例为北京市某高校给水管网改扩建设计工程，通过对工程调查分析，需水量预测、管线定线及简化后，充分考虑供水可靠性的要求，采用环状管网进行设计，改扩建管网如图 3所示。用改进的动态自适应粒子群算法对实际管网案例进行优化设计。

图 3 某高校给水管网改扩建示意 Fig. 3 Water supply network reconstruction of a university

图选项

某高校的给水管网工程设计年限T为20 年；年大修理基金提存率m为2.0%；电价为 0.58 元/(kW·h)；供水能量不均匀系数γ为0.2；水泵的效率为 0.8；期望收益率i₀为6.0%；最高用水时控制点的自由水头按28 m进行设计及校核。新建管道的粗糙度系数为130，旧管道的为100。各参数设置如下：ω_max=0.9，ω_min=0.4，c₁=2.05，c₂=1.45，N=500，T_max=100。

利用本文提出的PAPSO算法对某高校实际给水管网进行改扩建优化设计，各节点水压均满足最小服务水头的要求，水力计算软件NPANET2.0(ω=10.667)进行验证，满足水力约束条件，说明上述方案可行。工程造价收敛曲线见图 4，列出了PSO、WPSO以及改进的PAPSO 3种算法的优化曲线，3种算法分别在第40、29、28步找到了最优值，可知改进的PAPSO算法以更快的速度找到了更优的可行方案。

图 4 管网造价收敛曲线 Fig. 4 The convergence curves of the network cost

图选项

根据当前实际需水量预测，编号42以后的节点是需要扩建的节点，编号42以前的节点经过优化后部分管道需要并行铺设新管道。表 3列出4种优化方案，改扩建前年折算费用为175.46万元，PSO解决方案年折算费用为156.38万元，WPSO解决方案年折算费用为150.40万元，本文提出的PAPSO算法优化后年折算费用为142.15万元，该方案比原方案节省费用23.43%，比PSO优化方案节省费用10.01%，比WPSO优化方案节省5.80%，证明该优化方案是经济、合理的，节省了工程投资。

本文通过分析粒子运动轨迹，提出PAPSO算法，并将算法应用于工程实例，取得良好的效果。

通过分析粒子的运动轨迹，得到粒子运动的稳定条件，在PSO算法参数选择合理的情况下，粒子将收敛于期望位置处，通过判断粒子与期望粒子的适应度差异，得到粒子之间相似度的概念；相似度实时评估了种群的分布状态，利用粒子之间的相似度大小动态调整惯性权重和2个加速系数，平衡算法的全局和局部搜索能力，增强算法的局部搜索精度，对种群粒子进行分期交叉变异，增加种群多样性，保证粒子找到全局最优值，同时加快了算法的收敛速度；通过2个经典的管网：汉诺塔管网、纽约管网的实例验证，表明改进的粒子群算法解决此类组合优化问题的有效性，最后将PAPSO算法优化某高校的给水管网，不仅较大限度的节省工程投资，而且对算法的改进具有重要的理论指导意义。