殷方康

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

科技與應(yīng)用

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

殷方康

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

在城市供水系統(tǒng)中，管網(wǎng)的鋪設(shè)費(fèi)用占很大比重。如何最大限度降低建設(shè)成本而又保證供水的可靠性，是供水管網(wǎng)設(shè)計(jì)的重點(diǎn)和難點(diǎn)?；诠┧芫W(wǎng)的固有特性，結(jié)合蟻群、粒子群算法的優(yōu)點(diǎn)，將蟻群粒子群混合算法應(yīng)用到供水管網(wǎng)設(shè)計(jì)的多目標(biāo)優(yōu)化中。將蟻群中的信息素、啟發(fā)因子、信息素?fù)]發(fā)度參數(shù)映射到粒子群算法中粒子的位置坐標(biāo)，通過粒子迭代尋找最優(yōu)位置，并將蟻群算法通過特定信息素更新方式并限制迭代次數(shù)來(lái)進(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ì)具有很大的經(jīng)濟(jì)價(jià)值。在供水管網(wǎng)路徑設(shè)計(jì)中，如果提高供水能力，則投資費(fèi)用相應(yīng)升高，而一味地追求低費(fèi)用，則不能滿足城市的用水需求，而且存在著水質(zhì)安全無(wú)法保證的問題[1]。所以單目標(biāo)優(yōu)化并不適用于供水管網(wǎng)優(yōu)化設(shè)計(jì)。需在保證用水需求量的基礎(chǔ)上，將管網(wǎng)建設(shè)費(fèi)用降到最低，以期達(dá)到既保證管網(wǎng)服務(wù)性能，又節(jié)省成本，即供水管網(wǎng)多目標(biāo)優(yōu)化。多目標(biāo)問題中，需要同時(shí)兼顧多個(gè)目標(biāo)，但不一定使得每個(gè)目標(biāo)達(dá)到最優(yōu)[2]。這種情況下，一般會(huì)以犧牲某一目標(biāo)為代價(jià)來(lái)獲得全局的最優(yōu)解。

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

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

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

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

(1)

Z為管網(wǎng)造價(jià)成本；xj為管徑變量，f(xj)為j管徑值所對(duì)應(yīng)的造價(jià)成本；di為第i條管段的長(zhǎng)度值；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)可利用流量。

③管徑約束條件：

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

xi∈{X0,X1…Xm}

(6)

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

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

f懲罰=Z+PΔH

(7)

ΔH=max(Hi-Hmin)

(8)

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

P=(Zmax-Zmin)/Hmin

(9)

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

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

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

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

(10)

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

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

(11)

(12)

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

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

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

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

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

pi={α,β,ρ}

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

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

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

(13)

(14)

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

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

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

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

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

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

圖1 算法流程圖

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

[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è)計(jì)研究[D].合肥工業(yè)大學(xué),2009.

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

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

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

[7]柴寶杰,劉大為. 基于粒子群優(yōu)化的蟻群算法在TSP中的應(yīng)用[J]. 計(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ì)算機(jī)學(xué)院碩士在讀。

TU991

A

1671-4385(2014)04-0102-04