殷方康

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

科技與應用

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

殷方康

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

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

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

引言

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

1 多目標規(guī)劃數(shù)學模型

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

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

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

(1)

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

1.2約束條件為：

①流量及水壓約束條件：

qi≥qmin

(2)

Hmin≤Hi≤Hmax

(3)

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

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

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

∑(HFi-HTi)=0

(4)

∑(±qi)+Qi=0

(5)

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

③管徑約束條件：

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

xi∈{X0,X1…Xm}

(6)

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

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

f懲罰=Z+PΔH

(7)

ΔH=max(Hi-Hmin)

(8)

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

P=(Zmax-Zmin)/Hmin

(9)

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

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

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

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

(10)

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

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

(11)

(12)

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

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

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

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

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

pi={α,β,ρ}

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

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

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

(13)

(14)

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

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

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

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

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

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

圖1 算法流程圖

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

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

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

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

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

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

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

6 結語

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

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

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

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

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

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

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

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

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

(責任編輯：孫強)

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-)，男，山東莒南人，計算機學院碩士在讀。

TU991

A

1671-4385(2014)04-0102-04