參數自適應粒子群算法的給水管網優化研究

王超，喬俊飛

（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

A

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．

王超，男，1987年生，碩士研究生，主要研究方向為智能計算和智能優化算法。

喬俊飛，男，1968年生，教授，博士，主要研究方向為復雜過程建模、優化與控制和智能優化控制。主持國家自然科學基金項目2項、國家“863”計劃項目2項，發表學術論文100余篇，出版專著2部，獲國家發明專利授權15項。

2014?10?27．

日期：2015?08?27．

國家自然科學基金重點資助項目（61034008）；國家自然科學基金杰出青年資助項目（61225016）；北京市自然科學基金資助項目（4122006）．

喬俊飛．E?mail：isibox＠sina．com．