殷方康

( 中國地質(zhì)大學(xué)，湖北 武漢 430074 )

科技與應(yīng)用

基于蟻群粒子群混合算法的多目標(biāo)優(yōu)化在供水管網(wǎng)優(yōu)化設(shè)計中的應(yīng)用

殷方康

( 中國地質(zhì)大學(xué)，湖北 武漢 430074 )

在城市供水系統(tǒng)中，管網(wǎng)的鋪設(shè)費(fèi)用占很大比重。如何最大限度降低建設(shè)成本而又保證供水的可靠性，是供水管網(wǎng)設(shè)計的重點(diǎn)和難點(diǎn)?；诠┧芫W(wǎng)的固有特性，結(jié)合蟻群、粒子群算法的優(yōu)點(diǎn)，將蟻群粒子群混合算法應(yīng)用到供水管網(wǎng)設(shè)計的多目標(biāo)優(yōu)化中。將蟻群中的信息素、啟發(fā)因子、信息素?fù)]發(fā)度參數(shù)映射到粒子群算法中粒子的位置坐標(biāo)，通過粒子迭代尋找最優(yōu)位置，并將蟻群算法通過特定信息素更新方式并限制迭代次數(shù)來進(jìn)行優(yōu)化，再將粒子最優(yōu)位置反饋到優(yōu)化后的蟻群算法中，尋找最優(yōu)解。通過此算法，優(yōu)化了供水管網(wǎng)中管徑的選擇，在保證供水管網(wǎng)可靠性的前提下，盡量縮減建設(shè)費(fèi)用，為決策者提供更加經(jīng)濟(jì)實(shí)用的決策參考。

蟻群粒子群混合算法；多目標(biāo)優(yōu)化；供水管網(wǎng)

引言

在供水工程中，管網(wǎng)的建設(shè)費(fèi)用占很大比重，因此供水管網(wǎng)的優(yōu)化設(shè)計具有很大的經(jīng)濟(jì)價值。在供水管網(wǎng)路徑設(shè)計中，如果提高供水能力，則投資費(fèi)用相應(yīng)升高，而一味地追求低費(fèi)用，則不能滿足城市的用水需求，而且存在著水質(zhì)安全無法保證的問題[1]。所以單目標(biāo)優(yōu)化并不適用于供水管網(wǎng)優(yōu)化設(shè)計。需在保證用水需求量的基礎(chǔ)上，將管網(wǎng)建設(shè)費(fèi)用降到最低，以期達(dá)到既保證管網(wǎng)服務(wù)性能，又節(jié)省成本，即供水管網(wǎng)多目標(biāo)優(yōu)化。多目標(biāo)問題中，需要同時兼顧多個目標(biāo)，但不一定使得每個目標(biāo)達(dá)到最優(yōu)[2]。這種情況下，一般會以犧牲某一目標(biāo)為代價來獲得全局的最優(yōu)解。

1 多目標(biāo)規(guī)劃數(shù)學(xué)模型

供水管網(wǎng)優(yōu)化設(shè)計中，要在滿足管網(wǎng)工況設(shè)計要求的基礎(chǔ)上保證經(jīng)濟(jì)性。在管線布局已經(jīng)確定的情況下，需要考慮各節(jié)點(diǎn)的用水量及水壓，來確定管線各干路、支路上流量以及水壓。設(shè)計中需根據(jù)各管段上的設(shè)計流量和需水節(jié)點(diǎn)的設(shè)計自由水頭來匹配相應(yīng)的管徑，由于不同的管徑對應(yīng)不同的造價成本，所以對于管段造價成本可以表示成關(guān)于管徑的函數(shù)。

供水管網(wǎng)優(yōu)化設(shè)計的目標(biāo)是在滿足供水管網(wǎng)可靠性即約束條件的基礎(chǔ)上，使管網(wǎng)造價成本費(fèi)用即目標(biāo)函數(shù)最小。它的數(shù)學(xué)模型如下：

1. 1目標(biāo)函數(shù)為：

(1)

Z為管網(wǎng)造價成本；xj為管徑變量，f(xj)為j管徑值所對應(yīng)的造價成本；di為第i條管段的長度值；n為管段的數(shù)量，m為管徑的種類數(shù)量。

1.2約束條件為：

①流量及水壓約束條件：

qi≥qmin

(2)

Hmin≤Hi≤Hmax

(3)

qi為i管段的流量，qmin為管段最低要求流量；Hi為管段節(jié)點(diǎn)自由水頭，Hmin、Hmax為節(jié)點(diǎn)最低、最高要求自由水頭。

②水力平衡約束條件[3]：

管段流量以及需水節(jié)點(diǎn)自由水頭需滿足連續(xù)性方程和能量方程：

∑(HFi-HTi)=0

(4)

∑(±qi)+Qi=0

(5)

HFi、HTi為i管段兩端節(jié)點(diǎn)的自由水頭；Qi為i節(jié)點(diǎn)可利用流量。

③管徑約束條件：

管徑是一組離散的變量，故其取值取決于市場現(xiàn)有的標(biāo)準(zhǔn)管徑：

xi∈{X0,X1…Xm}

(6)

1.3約束條件的罰函數(shù)處理[4]：

為將供水管網(wǎng)優(yōu)化設(shè)計中有約束最優(yōu)化求解轉(zhuǎn)化為無約束求解，引入罰函數(shù)法，其適應(yīng)度函數(shù)為：

f懲罰=Z+PΔH

(7)

ΔH=max(Hi-Hmin)

(8)

P為懲罰因子，其定義如下：

P=(Zmax-Zmin)/Hmin

(9)

Zmax、Zmin為懲罰前管線造價成本的最大、最小值。

2.蟻群算法在供水管網(wǎng)中的應(yīng)用

在多目標(biāo)優(yōu)化上，大都通過算法來求解。多目標(biāo)優(yōu)化算法有加權(quán)法、約束法、線性規(guī)劃法等傳統(tǒng)優(yōu)化算法，也有遺傳、粒子群、蟻群群等智能優(yōu)化算法。而由于蟻群算法具有能快速尋找全局最優(yōu)解的特點(diǎn)，被廣泛應(yīng)用到組合優(yōu)化問題中。蟻群算法最初由Marco Dorigo在1992年提出，源于螞蟻的覓食行為研究，即螞蟻可以在蟻巢與食物之間通過信息素的分泌來尋找最短路徑[5]。

在供水管網(wǎng)設(shè)計中應(yīng)用蟻群算法如下：在初始時，將m只螞蟻放置在水源處，然后每只螞蟻按照管段編號依次選擇各管段的管徑大小。對管徑大小設(shè)置初始信息素τ，螞蟻遍歷到第i條管段時，會參考信息素來選擇管徑的大小。即第k只螞蟻在遍歷過程中，在t時刻經(jīng)過第i條管段時，選擇管徑值為j的概率大小為：

(10)

當(dāng)每只螞蟻遍歷所有管段之后，獲得一組可行解，即每條管段上的管徑值。在遍歷的過程中，在每條管段上釋放信息素。在遍歷完成后，需要對每條管段上的信息素進(jìn)行更新，包括新釋放的信息素增加量以及揮發(fā)掉的信息素縮減量。

τij(t+1)=(1-ρ)τij+Δτij(t)

(11)

(12)

依此進(jìn)入循環(huán)迭代，每次迭代都會根據(jù)本次遍歷得到的最優(yōu)解和全局最優(yōu)解來更新信息素。當(dāng)?shù)螖?shù)達(dá)到指定次數(shù)或是適應(yīng)值達(dá)到某一值時，終止迭代，獲得最優(yōu)解。

蟻群算法在供水管網(wǎng)優(yōu)化設(shè)計中，由于其算法參數(shù)的選擇決定求解的質(zhì)量，而參數(shù)的選擇依賴于決策者的經(jīng)驗和主觀判斷，所以蟻群算法在管徑匹配上的求解性能受到一定的限制。

3.應(yīng)用粒子群算法優(yōu)化蟻群算法參數(shù)

粒子群算法是由Eberhart博士和Kennedy博士于1995年提出，源于對鳥群在尋找食物時的群體行為的研究[6]。粒子群算法通過隨機(jī)初始化粒子位置，利用個體以及全局信息，不斷迭代來更新粒子位置，尋找最優(yōu)解。其特點(diǎn)是易實(shí)現(xiàn)、精度高、收斂快，并且在實(shí)際應(yīng)用中展現(xiàn)了其優(yōu)越性。

將蟻群算法中信息素相對重要程度α、啟發(fā)因子相對重要程度β、信息素?fù)]發(fā)度ρ映射到粒子群算法中[7]，即粒子的位置坐標(biāo)由該三個參數(shù)來表示：

pi={α,β,ρ}

并隨機(jī)產(chǎn)生粒子的初始速度，粒子每一維對應(yīng)一個速度方向：

vi={vα,vβ,vρ}

對粒子位置初始化后，即調(diào)用蟻群算法，在迭代循環(huán)完成后，通過得到的最優(yōu)解來對粒子位置的優(yōu)劣進(jìn)行判斷，從而更新粒子速度和位置：

(13)

(14)

在粒子進(jìn)行一個移步之后，需要粒子位置坐標(biāo)反饋到蟻群算法中，即再次調(diào)用蟻群算法，將粒子當(dāng)前位置坐標(biāo)各維分量，分別賦值給蟻群算法中的信息素相對重要程度α、啟發(fā)因子相對重要程度β、信息素?fù)]發(fā)度ρ。當(dāng)粒子連續(xù)迭代若干次仍未出現(xiàn)更優(yōu)解，則終止迭代，返回一個全局最優(yōu)解，即最優(yōu)粒子的位置坐標(biāo)，賦值到蟻群算法的參數(shù)中，即完成整個優(yōu)化算法。

4 蟻群算法的優(yōu)化

在粒子每個移步之后都要調(diào)用一次完整的蟻群算法，由于蟻群算法迭代次數(shù)可以高達(dá)數(shù)百次，而且每次迭代都需要更新信息素，所以上述求解算法雖能保證了求解的準(zhǔn)確性，但大大增加了計算時間成本。故本文對蟻群算法進(jìn)行了部分優(yōu)化：

在調(diào)用蟻群算法時，并不是在每次迭代之后進(jìn)行更新，而是當(dāng)出現(xiàn)更優(yōu)解時，才進(jìn)行更新。調(diào)用一次蟻群算法之后，信息素并不清空，當(dāng)下次蟻群算法開始調(diào)用時，信息素為上一次蟻群算法結(jié)束時的值[8]。由于每次調(diào)用蟻群算法時，不需要再從初始的隨機(jī)解一步一步迭代，在每次開始調(diào)用蟻群算法時，已經(jīng)具備了所積累的環(huán)境信息。所以可以將蟻群算法中的迭代次數(shù)設(shè)置為較小的數(shù)值，這大大節(jié)省了程序運(yùn)行的時間成本。

5 供水管網(wǎng)優(yōu)化設(shè)計流程及實(shí)例

在供水管網(wǎng)優(yōu)化設(shè)計程序算法中，首先初始化粒子群算法中粒子位置坐標(biāo)，位置坐標(biāo)的每個維度分別為蟻群算法中信息素、啟發(fā)因子相對重要程度以及信息素?fù)]發(fā)度初始參數(shù)。經(jīng)過粒子群一次迭代，尋找全局最優(yōu)位置，將其位置坐標(biāo)反饋到蟻群算法，通過調(diào)用完整的蟻群算法，尋找最優(yōu)管徑匹配組合，更新蟻群算法中的信息素以及全局最優(yōu)解。再次對粒子群進(jìn)行一次迭代，將位置坐標(biāo)反饋到蟻群算法，再次調(diào)用完整的蟻群算法后，更新最優(yōu)解。以此類推，直到粒子群算法中，連續(xù)迭代若干次，相應(yīng)的蟻群算法中沒有更優(yōu)解，算法完成。流程圖如圖1所示：

圖1 算法流程圖

選取環(huán)狀管網(wǎng)為示例管網(wǎng)模型，包含一個水源和9個需水節(jié)點(diǎn)，各節(jié)點(diǎn)編號、流量以及管段編號如圖2所示：

圖2 管網(wǎng)示意圖

管段水頭損失按照海曾威廉公式計算：

h=10.67q1.852l/C1.852D4.87

q、l分別為流量和長度；D為管徑；C為海曾威廉粗糙系數(shù)，此處取130，對于最大節(jié)點(diǎn)流量閉合差取0.001。

粒子群數(shù)量取30，w取0.5,c1=2,c2=2,蟻群數(shù)量取30，迭代次數(shù)取3次。粒子群迭代30次，程序終止。根據(jù)市場標(biāo)準(zhǔn)管徑造價，按由小到大的順序給不同的管徑進(jìn)行編號。優(yōu)化效果如表1所示：

表1 供水管網(wǎng)優(yōu)化表

6 結(jié)語

供水管網(wǎng)優(yōu)化設(shè)計一直是城市管線系統(tǒng)研究的重點(diǎn)。針對供水管網(wǎng)管徑選擇問題，本文應(yīng)用蟻群粒子群混合算法，將蟻群算法的三個重要參數(shù)賦值給粒子群算法中的例子位置坐標(biāo)，通過粒子位置的尋優(yōu)，反饋到蟻群算法，尋找最優(yōu)解，即最優(yōu)管徑組合，避免了蟻群算法中參數(shù)選取的盲目性。并通過蟻群算法的優(yōu)化，節(jié)省了時間成本。根據(jù)需水節(jié)點(diǎn)的需水量，調(diào)整相應(yīng)管段的管徑，保證其經(jīng)濟(jì)合理，故在供水管網(wǎng)優(yōu)化設(shè)計中具有廣闊前景。

[1]藺曉. 供水管網(wǎng)的智能優(yōu)化改擴(kuò)建[D].青島理工大學(xué),2011.

[2]楊穎蓉,侯學(xué)良. 淺談多目標(biāo)優(yōu)化決策方法[J]. 現(xiàn)代經(jīng)濟(jì)信息,2013,(15):80.

[3]樂永生. 基于MATALB的給水管網(wǎng)優(yōu)化設(shè)計研究[D].合肥工業(yè)大學(xué),2009.

[4]孫明月,許文斌,鄒彬,何英. 基于整數(shù)編碼粒子群算法的樹狀供水管網(wǎng)優(yōu)化[J]. 水資源與水工程學(xué)報,2012,(06):168-171.

[5]喻江平. 基于蟻群優(yōu)化的多目標(biāo)資源配置模型及應(yīng)用[J]. 統(tǒng)計與決策,2013,(14):82-85.

[6]楊亞紅,王瑛,曹輝. 基于粒子群優(yōu)化算法的環(huán)狀管網(wǎng)優(yōu)化設(shè)計[J]. 蘭州理工大學(xué)學(xué)報,2007,(01):136-138.

[7]柴寶杰,劉大為. 基于粒子群優(yōu)化的蟻群算法在TSP中的應(yīng)用[J]. 計算機(jī)仿真,2009,(08):89-91.136.

[8]李擎,張超,陳鵬,尹怡欣. 一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J]. 控制與決策,2013,(06):873-878.883.

(責(zé)任編輯：孫強(qiáng))

The Application of Multi-Objective Optimization of Ant Colony Algorithm and Particle Swarm Algorithm in the Design of Optimization of Water Distribution System

YIN Fang-kang

( China University of Geosciences, Wuhan, Hubei, 430074, China )

In water supply system in cities,the laying of pipe network accounts for a large proportion of the cost. It is an important and difficult part in the design of water distribution system to lower the cost and ensure the reliability of water supply at the same time. Based on the advantages of ant colony algorithm and particle swarm algorithm, this thesis applies them into the design of optimization of water distribution system with the aim to seek for the best solution. In this way, it optimizes the options of the diameter of water pipe. In the preposition of ensuring the reliability of water supply system, it can reduce the cost of construction.

colony algorithm and particle swarm algorithm; multi-objective optimization; water supply system

2014-06-20

殷方康(1989-)，男，山東莒南人，計算機(jī)學(xué)院碩士在讀。

TU991

A

1671-4385(2014)04-0102-04