參數(shù)自適應(yīng)粒子群算法的給水管網(wǎng)優(yōu)化研究

王超，喬俊飛

（1．北京工業(yè)大學(xué)電子信息與控制工程學(xué)院，北京100124；2．北京工業(yè)大學(xué)計(jì)算智能與智能系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室，北京100124）

參數(shù)自適應(yīng)粒子群算法的給水管網(wǎng)優(yōu)化研究

王超1，2，喬俊飛1，2

（1．北京工業(yè)大學(xué)電子信息與控制工程學(xué)院，北京100124；2．北京工業(yè)大學(xué)計(jì)算智能與智能系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室，北京100124）

針對(duì)粒子群算法在解決給水管網(wǎng)優(yōu)化問(wèn)題時(shí)存在容易陷入局部最優(yōu)的缺點(diǎn)，通過(guò)分析粒子的運(yùn)動(dòng)軌跡和相似程度，提出一種參數(shù)自適應(yīng)粒子群算法。該算法利用種群粒子與期望粒子之間相似度的大小，動(dòng)態(tài)調(diào)整算法參數(shù)，平衡算法全局和局部搜索能力，利用分期變異策略增加種群多樣性，保證算法收斂于全局最優(yōu)值。將改進(jìn)算法用于優(yōu)化漢諾塔管網(wǎng)和紐約管網(wǎng)2個(gè)經(jīng)典的管網(wǎng)案例，證明算法可以有效應(yīng)用于給水管網(wǎng)這類組合優(yōu)化問(wèn)題。將該算法優(yōu)化實(shí)際的管網(wǎng)改擴(kuò)建案例，結(jié)果表明，所提出的算法具有更好的尋優(yōu)性能和收斂性能。

給水管網(wǎng)系統(tǒng)；粒子軌跡；相似度；參數(shù)調(diào)整；自適應(yīng)粒子群

給水管網(wǎng)是城市給水系統(tǒng)的重要組成部分，其投資往往占整個(gè)給水系統(tǒng)工程總投資的60%～80%，而且運(yùn)行期間還需投入龐大的運(yùn)行動(dòng)力費(fèi)及管理維修費(fèi)［1］。當(dāng)前我國(guó)各城市給水管網(wǎng)都已達(dá)到一定規(guī)模，原有管網(wǎng)出現(xiàn)外壁腐蝕、爆管漏損率高等問(wèn)題；隨著城市的快速發(fā)展，部分管道無(wú)法滿足供水需求；城市街道拓寬、其他管線的施工使現(xiàn)有管道需做相應(yīng)調(diào)整。針對(duì)這些問(wèn)題，需對(duì)給水管網(wǎng)進(jìn)行改擴(kuò)建優(yōu)化設(shè)計(jì)。

為了優(yōu)化給水管網(wǎng)，許多方法被廣泛應(yīng)用，如遺傳算法［2?3］、蟻群算法［4］、啟發(fā)式算法［5］、差分算法［6］和足球聯(lián)賽競(jìng)爭(zhēng)算法［7］。其中粒子群（particle swarm optimization，PSO）算法因其可調(diào)參數(shù)少及具有本質(zhì)的并行性、全局搜索能力強(qiáng)、整體收斂速度快等優(yōu)點(diǎn)，展現(xiàn)了較大的解決多種優(yōu)化問(wèn)題的潛力和發(fā)展空間，同時(shí)PSO算法在解決給水管網(wǎng)這類組合優(yōu)化問(wèn)題時(shí)也存在以下缺點(diǎn)：容易陷入局部極值、局部搜索能力差導(dǎo)致的搜索精度不高。

針對(duì)PSO算法在優(yōu)化給水管網(wǎng)系統(tǒng)時(shí)容易陷入局部極值的問(wèn)題，文獻(xiàn)［8］提出在PSO算法中加入遺傳算法的交叉和變異操作，對(duì)新產(chǎn)生的位置進(jìn)行隨機(jī)變異，避免算法陷入局部極值，并通過(guò)優(yōu)化實(shí)際管網(wǎng)案例表明改進(jìn)算法的有效性，同時(shí)算法在搜索后期收斂速度變慢；文獻(xiàn)［9］提出在PSO算法的速度公式中加入一個(gè)收縮因子，實(shí)現(xiàn)算法的離散優(yōu)化，刪除種群中重合的點(diǎn)并隨機(jī)產(chǎn)生相應(yīng)的新個(gè)體，有效增加了種群多樣性，避免算法陷入局優(yōu)，同時(shí)算法的局部搜索能力有待加強(qiáng)；文獻(xiàn)［10］通過(guò)判斷2個(gè)粒子的空間距離提出聚集度的概念，并根據(jù)聚集度大小對(duì)粒子進(jìn)行變異，避免算法陷入局優(yōu)，以上隨機(jī)增加種群多樣性的機(jī)制在一定程度確實(shí)能避免算法陷入局優(yōu)，提高全局搜索能力。針對(duì)PSO算法在優(yōu)化給水管網(wǎng)系統(tǒng)時(shí)由于局部搜索能力差導(dǎo)致的搜索精度不高的問(wèn)題，許多學(xué)者通過(guò)改進(jìn)參數(shù)的調(diào)整機(jī)制，平衡了算法的全局和局部搜索能力，或在算法中加入局部搜索機(jī)制增強(qiáng)算法的局部搜索能力。文獻(xiàn)［11］通過(guò)對(duì)自動(dòng)學(xué)習(xí)機(jī)的研究，提出自動(dòng)學(xué)習(xí)調(diào)整權(quán)重和加速系數(shù)的方法，對(duì)比冒險(xiǎn)和保守2個(gè)調(diào)整策略，仿真結(jié)果表明具有學(xué)習(xí)自動(dòng)調(diào)整的冒險(xiǎn)策略能更高效地平衡算法的全局和局部搜索能力，提高算法的搜索精度，但算法收斂速度變慢；文獻(xiàn)［12］提出在PSO算法中加入差分進(jìn)化算法的變異和選擇操作，對(duì)種群中的個(gè)體極值進(jìn)行變異操作，相當(dāng)于對(duì)個(gè)體極值的周圍進(jìn)行局部搜索操作，增強(qiáng)了算法的搜索精度；文獻(xiàn)［13］提出根據(jù)每個(gè)粒子與全局最優(yōu)粒子的不同，評(píng)估種群粒子的相似度，利用相似度大小對(duì)慣性權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，根據(jù)種群分布狀態(tài)，在搜索后期增強(qiáng)算法的局部搜索能力，提高搜索精度。根據(jù)以上分析可知，當(dāng)前改進(jìn)的PSO算法在優(yōu)化給水管網(wǎng)問(wèn)題時(shí)的性能得到一定程度的提升，同時(shí)仍存在待提高的研究方向。

PSO算法的3個(gè)參數(shù)ω、c1、c2對(duì)其尋優(yōu)效果有重要影響，慣性權(quán)重ω平衡算法的全局和局部搜索能力，加速系數(shù)c1可以調(diào)節(jié)粒子飛向自身最好位置的步長(zhǎng)，加速系數(shù)c2可以調(diào)節(jié)粒子向群體最優(yōu)位置的飛行步長(zhǎng)。因此，本文將繼續(xù)研究這3個(gè)參數(shù)的調(diào)整策略，并根據(jù)以上3個(gè)參數(shù)的調(diào)整思想，為動(dòng)態(tài)評(píng)估種群中各粒子分布狀態(tài)，實(shí)現(xiàn)算法自適應(yīng)性，對(duì)種群粒子進(jìn)行收斂性分析，定義種群粒子相似度的概念，提出一種參數(shù)自適應(yīng)粒子群算法（parameter adaptive particle swarm optimization，PAPSO），將改進(jìn)的算法用于優(yōu)化實(shí)際的管網(wǎng)改擴(kuò)建案例，取得較好的效果。

1 給水管網(wǎng)改擴(kuò)建描述

給水管網(wǎng)系統(tǒng)改擴(kuò)建優(yōu)化設(shè)計(jì)是在改造現(xiàn)有舊管網(wǎng)、發(fā)揮舊管網(wǎng)輸水能力的基礎(chǔ)上，決定如何經(jīng)濟(jì)合理的增敷新管［14］。使新舊管網(wǎng)滿足水量、水壓、水質(zhì)的要求，并使管網(wǎng)建造和運(yùn)行年折算費(fèi)用最低。1．1 目標(biāo)函數(shù)

給水管網(wǎng)改擴(kuò)建優(yōu)化的目的就是建立一個(gè)全面、統(tǒng)一的給水管網(wǎng)改擴(kuò)建優(yōu)化設(shè)計(jì)模型，運(yùn)用現(xiàn)代智能算法，尋求經(jīng)濟(jì)合理的改擴(kuò)建方案［15］，目標(biāo)函數(shù)是方案優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)，如式（1）所示：

式中：i0為基金收益率，m為大修理基金提取率，k為鋪設(shè)管道數(shù)目，a、b、α為管段造價(jià)系數(shù)，E為電費(fèi)價(jià)格，η為泵站效率，Di為第i管段的直徑，Li為第i管段長(zhǎng)度，xi為新建或改擴(kuò)建管段，T為投資回收期，T1、T2為供水時(shí)間和傳輸時(shí)間，Qj、Hj、Qj′、Hj′為第j泵站高峰用水和最大傳輸時(shí)的流量及揚(yáng)程，γ1、γ2為供水能量變化系數(shù)。

1．2 約束條件

給水管網(wǎng)的優(yōu)化方案需滿足一定的約束條件，依據(jù)給水工程的規(guī)范要求，目標(biāo)函數(shù)的約束條件如下：

1）節(jié)點(diǎn)流量連續(xù)性約束

2）能量平衡約束

3）節(jié)點(diǎn)水壓約束

4）最小管徑及標(biāo)準(zhǔn)管徑約束

5）水流流速約束

6）舊管約束

2 PSO算法及其改進(jìn)

PSO算法結(jié)合了生命科學(xué)和優(yōu)化計(jì)算的優(yōu)點(diǎn)，群體中的個(gè)體代表問(wèn)題的一個(gè)潛在解，若優(yōu)化問(wèn)題的搜索空間是n維的，則第i粒子的位置和速度可分別表示粒子根據(jù)速度和位置公式迭代如公式（8）和（9）所示。

式中：ω決定先前速度對(duì)現(xiàn)在的影響程度；Yi為個(gè)體極值；Yg為全局極值；c1、c2為粒子受到個(gè)體認(rèn)知和社會(huì)認(rèn)知的影響程度；r1、r2為0～1的隨機(jī)數(shù)。

2．1 粒子運(yùn)動(dòng)軌跡分析

粒子位置和速度變化過(guò)程的分析在本質(zhì)上是一樣的，為了描述粒子運(yùn)動(dòng)軌跡，本文只分析粒子的位置變化過(guò)程。為便于分析和表達(dá)，首先將問(wèn)題空間簡(jiǎn)化為一維的，僅研究某一個(gè)粒子的運(yùn)動(dòng)軌跡，并暫時(shí)先假設(shè)Yi、Yg不變，用φ1、φ2表示式（9）中的c1r1和c2r2，且為常數(shù)，于是得到粒子i的狀態(tài)方程組（10）、（11）［16］。

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

將式（10）中的時(shí)間后推一步，代入式（12），并將該式中的時(shí)間前推一步可得一個(gè)二階差分方程，如式（13）所示。

多個(gè)粒子位置的發(fā)散將使整個(gè)種群發(fā)散，粒子位置變化過(guò)程的穩(wěn)定性對(duì)種群的行為將產(chǎn)生重要影響，故對(duì)粒子位置變化過(guò)程的穩(wěn)定性進(jìn)行分析，將式（13）取Z變換得

式中：J＝φ1＋φ2－1－ω。式（14）是一個(gè)線性系統(tǒng)，對(duì)應(yīng)的特征方程為

該線性系統(tǒng)穩(wěn)定的充分必要條件是特征方程各項(xiàng)系數(shù)均為正值，因此可得到粒子的位置變化過(guò)程穩(wěn)定條件為

在算法迭代過(guò)程中，使算法參數(shù)始終滿足式（17），則由Z變換的終值定理可得

粒子群在尋優(yōu)過(guò)程中Yi將逐步趨向Yg，因此在無(wú)限的搜索時(shí)間內(nèi)，所有粒子的位置將逐步靠近并停止在處。通過(guò)大量實(shí)驗(yàn)研究［17］發(fā)現(xiàn)，粒子軌跡收斂到固定點(diǎn)的概率與參數(shù)選擇密切相關(guān)，若滿足式（17），則絕大多數(shù)粒子軌跡會(huì)收斂到固定點(diǎn)，各類問(wèn)題函數(shù)值的分布都有一定規(guī)律，即當(dāng)滿足穩(wěn)定條件時(shí)，多數(shù)粒子能收斂到固定點(diǎn)，并能為找到最優(yōu)位置提供一定的線索。

2．2 參數(shù)調(diào)整機(jī)制

粒子適應(yīng)度值能分辨位置的好壞，為充分利用粒子適應(yīng)度分布情況動(dòng)態(tài)調(diào)整算法參數(shù)，進(jìn)行上述的粒子軌跡分析，可知所有粒子的位置最終停止在Yg處，但在種群迭代過(guò)程中的絕大部分時(shí)間里粒子是向靠攏的，故將其定義為期望粒子位置xe。其中Yi對(duì)應(yīng)的適應(yīng)度值為fpBest，Yg對(duì)應(yīng)的適應(yīng)度值為fgBest，故定義期望適應(yīng)度值fe如下：

慣性權(quán)重的調(diào)整很大程度上決定了PSO算法的優(yōu)化性能，其大小的調(diào)節(jié)具有一定規(guī)律，且與種群分布和單個(gè)粒子位置密切相關(guān)，粒子在迭代過(guò)程中相似程度越來(lái)越大，通過(guò)種群分布狀態(tài)，利用粒子相似程度來(lái)調(diào)節(jié)慣性權(quán)重，進(jìn)而分析和改進(jìn)PSO算法，提出粒子相似度s（i，e）如式（20）所示：

式中：s（i，e）表示第i粒子與期望粒子的相似度，fi為第i粒子的適應(yīng)度值，Dmax、Dmin是固定正常數(shù)。文獻(xiàn)［13］中基于空間距離提出相似度的概念，表示的是每個(gè)粒子和當(dāng)前的全局最優(yōu)粒子的相似程度。本文分析了粒子運(yùn)動(dòng)軌跡，提出相似度的概念來(lái)表示粒子與期望粒子的相似程度，并自適應(yīng)調(diào)整慣性權(quán)重和2個(gè)加速系數(shù)，同時(shí)實(shí)現(xiàn)變異的自適應(yīng)性，有效平衡了粒子群算法的全局搜索能力和收斂速度。

PSO算法搜索前期選擇較大權(quán)重值，加強(qiáng)粒子探索能力，后期選擇較小權(quán)重值，保持算法收斂速度，這種思想被廣泛采用。但所有粒子的權(quán)重被統(tǒng)一調(diào)整，忽略了粒子之間的差異性，若早期就有粒子找到全局最優(yōu)點(diǎn)，卻因其權(quán)重過(guò)大而跳出，則會(huì)降低算法搜索效率。為此，本文設(shè)計(jì)出一種根據(jù)各粒子與期望粒子相似度不同而動(dòng)態(tài)調(diào)整權(quán)重的PSO算法，公式為

與期望粒子相似度較小的粒子，權(quán)重應(yīng)較大，加快粒子探索整個(gè)解空間；反之，其權(quán)重應(yīng)較小，這樣可使該粒子在期望最優(yōu)位置領(lǐng)域內(nèi)進(jìn)行微小探索，加強(qiáng)粒子的開(kāi)發(fā)能力。

加速系數(shù)c1是個(gè)體認(rèn)知，c2是社會(huì)認(rèn)知，算法搜索初期，c1應(yīng)較大，增加種群多樣性，c2應(yīng)較小，避免種群陷入局部最優(yōu)；搜索后期，逐漸找到最優(yōu)區(qū)域，c1應(yīng)較小，加快收斂速度，c2應(yīng)較大，領(lǐng)導(dǎo)種群趨向全局最優(yōu)位置。結(jié)合以上c1，c2的調(diào)整思想，提出其迭代公式如下：

2．3 分期變異機(jī)制

PSO算法在迭代過(guò)程中會(huì)因種群多樣性的缺失而陷入局部最優(yōu)，為增加種群多樣性，對(duì)種群粒子進(jìn)行變異，當(dāng)粒子與期望粒子相似度越大時(shí)，對(duì)應(yīng)粒子變異的概率應(yīng)越小，反之亦然。定義變異概率pim和變異條件分別如下：

為有效平衡算法的全局搜索能力和收斂速度，將混沌變異和Gaussian變異分期交叉進(jìn)行，整個(gè)迭代過(guò)程分為4個(gè)階段，每個(gè)階段的前20%的迭代步數(shù)進(jìn)行混沌變異，后5%的迭代步數(shù)進(jìn)行Gaussian變異。利用混沌的遍歷性，充分增大種群多樣性，如式（26）所示；利用Gaussian變異的局部搜索能力，加快算法的收斂速度，如式（27）所示。

變異的位置為xijm，公式為

變異后粒子的新位置為該粒子上一代位置與變異位置連線的中點(diǎn)，公式為

分期變異機(jī)制的主要特點(diǎn)：通過(guò)評(píng)估整個(gè)種群的分布情況，通過(guò)該粒子與期望粒子相似程度大小來(lái)決定是否對(duì)其變異；2種變異方法分期交叉進(jìn)行，很好地平衡了種群多樣性和算法的收斂能力，在前期避免算法陷入局優(yōu)，后期可以使算法快速找到全局最優(yōu)值。

2．4 算法流程及性能測(cè)試

設(shè)微粒數(shù)為N，問(wèn)題的維數(shù)為D，最大迭代步數(shù)為Tmax，本文算法描述如下：

1）初始化，包括各參數(shù)：N、x、v、Tmax，隨機(jī)產(chǎn)生N個(gè)粒子及其初始速度，并計(jì)算適應(yīng)度；

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

3）評(píng)價(jià)種群中各粒子的適應(yīng)度；

4）根據(jù)適應(yīng)度值更新粒子的個(gè)體極值Yi；

5）根據(jù)適應(yīng)度更新種群的全局極值Yg；

6）計(jì)算粒子之間的相似度s（i，e），并根據(jù)式（21）更新慣性權(quán)重；

7）根據(jù)式（24）計(jì)算變異概率，并判斷是否滿足變異條件，若滿足變異條件，則根據(jù)式（26）～（29）進(jìn)行分期交叉變異，重新計(jì)算粒子適應(yīng)度，并更新Yi、Yg；

8）判斷算法的終止條件，若滿足則停止，輸出相關(guān)結(jié)果；否則轉(zhuǎn)2）。

為了驗(yàn)證算法的有效性，將PAPSO算法用于優(yōu)化漢諾塔管網(wǎng)和紐約管網(wǎng)，2個(gè)經(jīng)典管網(wǎng)的布局圖、節(jié)點(diǎn)水壓和管段長(zhǎng)度等詳細(xì)數(shù)據(jù)參照文獻(xiàn)［18］。

根據(jù)漢諾塔管網(wǎng)實(shí)際問(wèn)題，進(jìn)行參數(shù)敏感性分析后，PAPSO算法在整個(gè)搜索過(guò)程中，各參數(shù)設(shè)置如下：ωmax＝0．9，ωmin＝0．4，c1＝2．05，c2＝1．45，N＝300，Tmax＝100。圖1為漢諾塔管網(wǎng)造價(jià)收斂曲線，改進(jìn)的PAPSO算法在第31步就找到了全局最優(yōu)值，具有較快的收斂速度。

對(duì)于漢諾塔問(wèn)題，通過(guò)EPANET2．0（ω＝10．667）水力模擬計(jì)算驗(yàn)證，目前最優(yōu)的解決方案造價(jià)是6．081×106美元。表1列出了遺傳算法、混合粒子群差分算法、自適應(yīng)粒子群算法、差分算法和本文提出的PAPSO算法優(yōu)化漢諾塔問(wèn)題的結(jié)果對(duì)比，從表中可以看出各個(gè)算法都找到了全局最優(yōu)值，但本文提出的PAPSO算法經(jīng)過(guò)34 000次函數(shù)評(píng)價(jià)就找到了全局最優(yōu)方案，改進(jìn)算法需要的評(píng)價(jià)次數(shù)較少，且該算法有95%的搜索成功率，具有較高的搜索效率和較強(qiáng)的魯棒性。

圖1 漢諾塔管網(wǎng)造價(jià)收斂曲線Fig．1 The convergence curve of Hanoi cost

表1 漢諾塔管網(wǎng)優(yōu)化結(jié)果Table 1 optimization result for the Hanoi network

根據(jù)紐約管網(wǎng)實(shí)際問(wèn)題，PAPSO算法搜索過(guò)程中種群規(guī)模N取120，其他參數(shù)設(shè)置與優(yōu)化漢諾塔管網(wǎng)時(shí)相同。圖2為紐約管網(wǎng)造價(jià)收斂曲線，可以看出該算法3次跳出局部極值后在第22步就找到了全局最優(yōu)造價(jià)方案38．52×106美元。

圖2 紐約管網(wǎng)造價(jià)收斂曲線Fig．2 The convergence curve of New York cost

表2列出了不同算法優(yōu)化的紐約管網(wǎng)擴(kuò)建方案，對(duì)紐約管網(wǎng)進(jìn)行改擴(kuò)建優(yōu)化設(shè)計(jì)后，沒(méi)有列出的管道不需改變管徑值，對(duì)應(yīng)列出的管道編號(hào)新的管道鋪設(shè)情況是優(yōu)化方案給出的管徑與原管徑平行鋪設(shè)。文獻(xiàn)［19］得到的優(yōu)化方案造價(jià)為38．64×106美元，高于本文得到的優(yōu)化方案，文獻(xiàn)［20］提出的改進(jìn)的遺傳算法得到造價(jià)為37．13×106美元的優(yōu)化方案，水力驗(yàn)證時(shí)通過(guò)EPANET2．0（ω＝10．667）水力模擬計(jì)算，可知節(jié)點(diǎn)16、17和19不滿足最小節(jié)點(diǎn)水壓，方案不可行。文獻(xiàn)［21］與本文均得到造價(jià)為38．52×106美元的最優(yōu)方案，均滿足水力約束條件，PSO?DE算法迭代到26步找到最優(yōu)值，PAPSO算法在第22步即找到最優(yōu)值。

表2 紐約管網(wǎng)優(yōu)化結(jié)果Table 2 Optimization result for New York network

3 工程實(shí)例

本實(shí)例為北京市某高校給水管網(wǎng)改擴(kuò)建設(shè)計(jì)工程，通過(guò)對(duì)工程調(diào)查分析，需水量預(yù)測(cè)、管線定線及簡(jiǎn)化后，充分考慮供水可靠性的要求，采用環(huán)狀管網(wǎng)進(jìn)行設(shè)計(jì)，改擴(kuò)建管網(wǎng)如圖3所示。用改進(jìn)的動(dòng)態(tài)自適應(yīng)粒子群算法對(duì)實(shí)際管網(wǎng)案例進(jìn)行優(yōu)化設(shè)計(jì)。

某高校的給水管網(wǎng)工程設(shè)計(jì)年限T為20年；年大修理基金提存率m為2．0%；電價(jià)為0．58元／（kW·h）；供水能量不均勻系數(shù)γ為0．2；水泵的效率為0．8；期望收益率i0為6．0%；最高用水時(shí)控制點(diǎn)的自由水頭按28 m進(jìn)行設(shè)計(jì)及校核。新建管道的粗糙度系數(shù)為130，舊管道的為100。各參數(shù)設(shè)置如下：ωmax＝0．9，ωmin＝0．4，c1＝2．05，c2＝1．45，N＝500，Tmax＝100。

利用本文提出的PAPSO算法對(duì)某高校實(shí)際給水管網(wǎng)進(jìn)行改擴(kuò)建優(yōu)化設(shè)計(jì)，各節(jié)點(diǎn)水壓均滿足最小服務(wù)水頭的要求，水力計(jì)算軟件NPANET2．0（ω＝10．667）進(jìn)行驗(yàn)證，滿足水力約束條件，說(shuō)明上述方案可行。工程造價(jià)收斂曲線見(jiàn)圖4，列出了PSO、WPSO以及改進(jìn)的PAPSO 3種算法的優(yōu)化曲線，3種算法分別在第40、29、28步找到了最優(yōu)值，可知改進(jìn)的PAPSO算法以更快的速度找到了更優(yōu)的可行方案。

根據(jù)當(dāng)前實(shí)際需水量預(yù)測(cè)，編號(hào)42以后的節(jié)點(diǎn)是需要擴(kuò)建的節(jié)點(diǎn)，編號(hào)42以前的節(jié)點(diǎn)經(jīng)過(guò)優(yōu)化后部分管道需要并行鋪設(shè)新管道。表3列出4種優(yōu)化方案，改擴(kuò)建前年折算費(fèi)用為175．46萬(wàn)元，PSO解決方案年折算費(fèi)用為156．38萬(wàn)元，WPSO解決方案年折算費(fèi)用為150．40萬(wàn)元，本文提出的PAPSO算法優(yōu)化后年折算費(fèi)用為142．15萬(wàn)元，該方案比原方案節(jié)省費(fèi)用23．43%，比PSO優(yōu)化方案節(jié)省費(fèi)用10．01%，比WPSO優(yōu)化方案節(jié)省5．80%，證明該優(yōu)化方案是經(jīng)濟(jì)、合理的，節(jié)省了工程投資。

表3 優(yōu)化前后方案對(duì)比Table 3 The optimization scheme comparison

圖3 某高校給水管網(wǎng)改擴(kuò)建示意Fig．3 Water supply network reconstruction of a university

圖4 管網(wǎng)造價(jià)收斂曲線Fig．4 The convergence curves of the network cost

4 結(jié)束語(yǔ)

本文通過(guò)分析粒子運(yùn)動(dòng)軌跡，提出PAPSO算法，并將算法應(yīng)用于工程實(shí)例，取得良好的效果。

通過(guò)分析粒子的運(yùn)動(dòng)軌跡，得到粒子運(yùn)動(dòng)的穩(wěn)定條件，在PSO算法參數(shù)選擇合理的情況下，粒子將收斂于期望位置處，通過(guò)判斷粒子與期望粒子的適應(yīng)度差異，得到粒子之間相似度的概念；相似度實(shí)時(shí)評(píng)估了種群的分布狀態(tài)，利用粒子之間的相似度大小動(dòng)態(tài)調(diào)整慣性權(quán)重和2個(gè)加速系數(shù)，平衡算法的全局和局部搜索能力，增強(qiáng)算法的局部搜索精度，對(duì)種群粒子進(jìn)行分期交叉變異，增加種群多樣性，保證粒子找到全局最優(yōu)值，同時(shí)加快了算法的收斂速度；通過(guò)2個(gè)經(jīng)典的管網(wǎng)：漢諾塔管網(wǎng)、紐約管網(wǎng)的實(shí)例驗(yàn)證，表明改進(jìn)的粒子群算法解決此類組合優(yōu)化問(wèn)題的有效性，最后將PAPSO算法優(yōu)化某高校的給水管網(wǎng)，不僅較大限度的節(jié)省工程投資，而且對(duì)算法的改進(jìn)具有重要的理論指導(dǎo)意義。

［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，F(xiàn)AN 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算法粒子運(yùn)動(dòng)軌跡分析［J］．計(jì)算機(jī)學(xué)報(bào)，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

王超，喬俊飛．參數(shù)自適應(yīng)粒子群算法的給水管網(wǎng)優(yōu)化研究［J］．智能系統(tǒng)學(xué)報(bào)，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年生，碩士研究生，主要研究方向?yàn)橹悄苡?jì)算和智能優(yōu)化算法。

喬俊飛，男，1968年生，教授，博士，主要研究方向?yàn)閺?fù)雜過(guò)程建模、優(yōu)化與控制和智能優(yōu)化控制。主持國(guó)家自然科學(xué)基金項(xiàng)目2項(xiàng)、國(guó)家“863”計(jì)劃項(xiàng)目2項(xiàng)，發(fā)表學(xué)術(shù)論文100余篇，出版專著2部，獲國(guó)家發(fā)明專利授權(quán)15項(xiàng)。

2014?10?27．

日期：2015?08?27．

國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（61034008）；國(guó)家自然科學(xué)基金杰出青年資助項(xiàng)目（61225016）；北京市自然科學(xué)基金資助項(xiàng)目（4122006）．

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