参数自适应粒子群算法的给水管网优化研究

2015-12-03王超乔俊飞

智能系统学报 2015年5期

关键词：给水管适应度全局

王超，乔俊飞

（1．北京工业大学电子信息与控制工程学院，北京100124；2．北京工业大学计算智能与智能系统北京市重点实验室，北京100124）

参数自适应粒子群算法的给水管网优化研究

王超1，2，乔俊飞1，2

（1．北京工业大学电子信息与控制工程学院，北京100124；2．北京工业大学计算智能与智能系统北京市重点实验室，北京100124）

针对粒子群算法在解决给水管网优化问题时存在容易陷入局部最优的缺点，通过分析粒子的运动轨迹和相似程度，提出一种参数自适应粒子群算法。该算法利用种群粒子与期望粒子之间相似度的大小，动态调整算法参数，平衡算法全局和局部搜索能力，利用分期变异策略增加种群多样性，保证算法收敛于全局最优值。将改进算法用于优化汉诺塔管网和纽约管网2个经典的管网案例，证明算法可以有效应用于给水管网这类组合优化问题。将该算法优化实际的管网改扩建案例，结果表明，所提出的算法具有更好的寻优性能和收敛性能。

给水管网系统；粒子轨迹；相似度；参数调整；自适应粒子群

给水管网是城市给水系统的重要组成部分，其投资往往占整个给水系统工程总投资的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个参数ω、c1、c2对其寻优效果有重要影响，惯性权重ω平衡算法的全局和局部搜索能力，加速系数c1可以调节粒子飞向自身最好位置的步长，加速系数c2可以调节粒子向群体最优位置的飞行步长。因此，本文将继续研究这3个参数的调整策略，并根据以上3个参数的调整思想，为动态评估种群中各粒子分布状态，实现算法自适应性，对种群粒子进行收敛性分析，定义种群粒子相似度的概念，提出一种参数自适应粒子群算法（parameter adaptive particle swarm optimization，PAPSO），将改进的算法用于优化实际的管网改扩建案例，取得较好的效果。

1 给水管网改扩建描述

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

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

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

1．2 约束条件

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

1）节点流量连续性约束

2）能量平衡约束

3）节点水压约束

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

5）水流流速约束

6）旧管约束

2 PSO算法及其改进

PSO算法结合了生命科学和优化计算的优点，群体中的个体代表问题的一个潜在解，若优化问题的搜索空间是n维的，则第i粒子的位置和速度可分别表示粒子根据速度和位置公式迭代如公式（8）和（9）所示。

式中：ω决定先前速度对现在的影响程度；Yi为个体极值；Yg为全局极值；c1、c2为粒子受到个体认知和社会认知的影响程度；r1、r2为0～1的随机数。

2．1 粒子运动轨迹分析

粒子位置和速度变化过程的分析在本质上是一样的，为了描述粒子运动轨迹，本文只分析粒子的位置变化过程。为便于分析和表达，首先将问题空间简化为一维的，仅研究某一个粒子的运动轨迹，并暂时先假设Yi、Yg不变，用φ1、φ2表示式（9）中的c1r1和c2r2，且为常数，于是得到粒子i的状态方程组（10）、（11）［16］。

将式（11）代入式（10）可得

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

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

式中：J＝φ1＋φ2－1－ω。式（14）是一个线性系统，对应的特征方程为

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

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

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

2．2 参数调整机制

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

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

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

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

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

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

2．3 分期变异机制

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

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

变异的位置为xijm，公式为

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

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

2．4 算法流程及性能测试

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

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

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

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

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

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

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

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

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

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

根据汉诺塔管网实际问题，进行参数敏感性分析后，PAPSO算法在整个搜索过程中，各参数设置如下：ωmax＝0．9，ωmin＝0．4，c1＝2．05，c2＝1．45，N＝300，Tmax＝100。图1为汉诺塔管网造价收敛曲线，改进的PAPSO算法在第31步就找到了全局最优值，具有较快的收敛速度。

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

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

表1 汉诺塔管网优化结果Table 1 optimization result for the Hanoi network

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

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

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

表2 纽约管网优化结果Table 2 Optimization result for New York network

3 工程实例

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

某高校的给水管网工程设计年限T为20年；年大修理基金提存率m为2．0%；电价为0．58元／（kW·h）；供水能量不均匀系数γ为0．2；水泵的效率为0．8；期望收益率i0为6．0%；最高用水时控制点的自由水头按28 m进行设计及校核。新建管道的粗糙度系数为130，旧管道的为100。各参数设置如下：ωmax＝0．9，ωmin＝0．4，c1＝2．05，c2＝1．45，N＝500，Tmax＝100。

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

根据当前实际需水量预测，编号42以后的节点是需要扩建的节点，编号42以前的节点经过优化后部分管道需要并行铺设新管道。表3列出4种优化方案，改扩建前年折算费用为175．46万元，PSO解决方案年折算费用为156．38万元，WPSO解决方案年折算费用为150．40万元，本文提出的PAPSO算法优化后年折算费用为142．15万元，该方案比原方案节省费用23．43%，比PSO优化方案节省费用10．01%，比WPSO优化方案节省5．80%，证明该优化方案是经济、合理的，节省了工程投资。

表3 优化前后方案对比Table 3 The optimization scheme comparison

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

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

4 结束语

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

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

［1］MURPHY L J，SIMPSON A R，Dandy G C．Design of a pipe network using genetic algorithms［J］．Water⁃Melbourne Then Artarmon，1993，20（4）：40⁃42．

［2］ABKENAR S M S，CHASE D V，STANLEY S D，et al．Optimizing pumping system for sustainable water distribution network by using genetic algorithm［C］／／2013 International Green Computing Conference．Arlington，USA，2013：1⁃6．

［3］BLINCO L J，SIMPSON A R，LAMBERT M F，et al．Ge⁃netic algorithm optimization of operational costs and green⁃house gas emissions for water distribution systems［J］．Pro⁃cedia Engineering，2014，89：509⁃516．

［4］DINARDO A，DINATALE M，GRECO R，et al．Ant algo⁃rithm for smart water network partitioning［J］．Procedia En⁃gineering，2014，70：525⁃534．

［5］MOOSAVIAN N，ROODSARI B K．Soccer league competi⁃tion algorithm：a novel meta⁃heuristic algorithm for optimal design of water distribution networks［J］．Swarm and Evolu⁃tionary Computation，2014，17：14⁃24．

［6］LIU Boning，RECKHOW D A，LI Yun．A two⁃site chlorine decay model for the combined effects of pH，water distribu⁃tion temperature and in⁃home heating profilesusing differen⁃tial evolution［J］．Water Research，2014，53：47⁃57．

［7］NASER M，ROODSARIB K．Soccer league competition al⁃gorithm：A novel meta⁃heuristic algorithm for optimal design of water distribution networks［J］．Swarm and Evolutionary Computation，2014，17：14⁃24．

［8］WANG Hongxiang，GUO Wenxian．Calibrating chlorine wall decay coefficients of water distribution systems based on hy⁃brid PSO［C］／／Sixth International Conference on Natural Computation（ICNC）．Yantai，China，2010：3856⁃3860．

［9］MONTALVO I M，IZQUIERDO J，PÉREZ R，et al．A di⁃versity⁃enriched variant of discrete PSO applied to the de⁃sign of water distribution networks［J］．Engineering Optimi⁃zation，2008，40（7）：655⁃668．

［10］ZARGHAMIM，HAJYKAZEMIAN H．Urban water re⁃sources planning by using a modified particle swarm optimi⁃zation algorithm［J］．Resources，Conservation and Recy⁃cling，2013，70：1⁃8．

［11］HASHEMI A B，MEYBODI M R．A note on the learning automata based algorithms for adaptive parameter selection in PSO［J］．Applied Soft Computing，2011，11（1）：689⁃705．

［12］DE FÁTIMA ARAU＇JO T，UTURBEY W．Performance as⁃sessment of PSO，DE and hybrid PSO⁃DE algorithms when applied to the dispatch of generation and demand［J］．Inter⁃national Journal of Electrical Power＆Energy Systems，2013，47：205⁃217．

［13］刘建华，樊晓平，瞿志华．一种基于相似度的新型粒子群算法［J］．控制与决策，2007，22（10）：1155⁃1159．LIU Jianhua，FAN Xiaoping，QU Zhihua．A new particle swarm optimization algorithm based on similarity［J］．Con⁃trol and Decision，2007，22（10）：1155⁃1159．

［14］COELHO B，ANDRADE⁃CAMPOS A．Efficiency achieve⁃ment in water supply systems—a review［J］．Renewable and Sustainable Energy Reviews，2014，30：59⁃84．

［15］ANNELIES D C，KENNETH S．Optimisation of gravity⁃fed water distribution network design：a critical review［J］．European Journal of Operational Research，2013，228（1）：1⁃10．

［16］李宁，孙德宝，邹彤，等．基于差分方程的PSO算法粒子运动轨迹分析［J］．计算机学报，2006，29（11）：2052⁃2061．LI Ning，SUN Debao，ZOU Tong，et al．An analysis for a particle's trajectory of PSO based on difference equation［J］．Chinese Journal of Computers，2006，29（11）：2052⁃2061．

［17］VANDEN BERGH F．An analysis of particle swarm optimi⁃zers［D］．Pretoria，South Africa：University of Pretoria，2002：81⁃83．

［18］SEDKI A，OUAZAR D．Hybrid particle swarm optimiza⁃tion and differential evolution for optimal design of water distribution systems［J］．Advanced Engineering Informat⁃ics，2012，26（3）：582⁃591．

［19］SAVIC D A，WALTERS G A．Genetic algorithms for least cost design of water distribution networks［J］．Journal of Water Resources Planning and Management，1997，123（2）：67⁃77．

［20］IDEL M，JOAQUIN I，RAFAEL P G，et al．Improved per⁃formance of PSO with self⁃adaptive parameters for compu⁃ting the optimal design of water supply systems［J］．Engi⁃neering Applications of Artificial Intelligence，2010，23（5）：727⁃735．

［21］SURIBABU C R．Differential evolution algorithm for opti⁃mal design of water distribution networks［J］．Journal of Hydroinformatics，2010，12（1）：66⁃82．

An parameter adaptive particle swarm optimization for optimal design of water supply systems

WANG Chao1，2，QIAO Junfei1，2

（1．College of Electronic Information and Control Engineering，Beijing University of Technology，Beijing 100124，China；2．Beijing Key Laboratory of Computational Intelligence and Intelligence System，Beijing University of Technology，Beijing 100124，China）

Particle swarm optimization easily falls into a local optimum when solving water supply optimization prob⁃lems．In order to solve this weakness，by analyzing particle trajectories and the similarity of particles，this paper proposes a parameter adaptive particle swarm optimization（PAPSO）．By estimating the degree of similarity between particles and expected particles，the algorithm dynamically adjusts parameters and balances the global and local search ability．The algorithm uses the variation strategy of staging to increase the population diversity and ensure that it converges to the global optimum．The tower of Hanoi network and New York network have been optimized by the improved algorithm，and the result shows that the PAPSO algorithm can be effectively applied to the combinato⁃rial optimization of water supply pipeline networks．The proposed algorithm has been applied to optimize an actual pipe network reconstruction case and the result shows that the algorithm has better optimization and convergence performance．

water supply system；particle trajectories；similarity；parameter adjustment；adaptive particle swarm op⁃timization

TP18

1673⁃4785（2015）05⁃0722⁃07

10．11992／tis．201410036

http：／／www．cnki．net／kcms／detail／23．1538．TP．20150827．1030．012．html

王超，乔俊飞．参数自适应粒子群算法的给水管网优化研究［J］．智能系统学报，2015，10（5）：722⁃728．

英文引用格式：WANG Chao，QIAO Junfei．An parameter adaptive particle swarm optimization for optimal design of water supply systems［J］．CAAI Transactions on Intelligent Systems，2015，10（5）：722⁃728．