基于自動生成策略的供水管網(wǎng)抗震優(yōu)化算法

劉　威， 元宏偉， 徐　良

(1.同濟大學(xué) 土木工程防災(zāi)國家重點實驗室，上海 200092；2. 同濟大學(xué) 土木工程學(xué)院，上海 200092；3. 北京市建筑設(shè)計研究院，北京 100045；4. 上海核工程研究設(shè)計院，上海 200233)

?

基于自動生成策略的供水管網(wǎng)抗震優(yōu)化算法

劉威1,2， 元宏偉3， 徐良4

(1.同濟大學(xué) 土木工程防災(zāi)國家重點實驗室，上海 200092；2. 同濟大學(xué) 土木工程學(xué)院，上海 200092；3. 北京市建筑設(shè)計研究院，北京 100045；4. 上海核工程研究設(shè)計院，上海 200233)

摘要：以管網(wǎng)年費用折算值為優(yōu)化目標(biāo)、管網(wǎng)拓撲結(jié)構(gòu)與管徑為優(yōu)化參數(shù)、管網(wǎng)節(jié)點抗震可靠度為約束條件, 建立了供水管網(wǎng)抗震優(yōu)化設(shè)計模型.基于自動生成策略，并結(jié)合環(huán)形管網(wǎng)判斷方法，分別利用遺傳算法、遺傳-模擬退火算法和微粒群算法進行了供水管網(wǎng)的抗震拓撲優(yōu)化分析.利用3種優(yōu)化方法對2個典型供水管網(wǎng)進行了對比分析.對比分析表明，遺傳-模擬退火算法具有最好的優(yōu)化能力.

關(guān)鍵詞：供水管網(wǎng)； 自動生成策略； 遺傳算法； 遺傳-模擬退火算法； 微粒群算法

生命線工程系統(tǒng)是指維系現(xiàn)代城市功能與區(qū)域經(jīng)濟功能的基礎(chǔ)性工程設(shè)施系統(tǒng)[1].作為城市生命線系統(tǒng)的重要組成部分，城市供水管網(wǎng)對城市的日常運行和災(zāi)后搶險救災(zāi)具有重要意義.進行城市供水管網(wǎng)抗震優(yōu)化設(shè)計，確保城市供水系統(tǒng)在地震中和地震后安全可靠運行，減少地震災(zāi)害的損失，加快災(zāi)后城市恢復(fù)的時間，是亟待解決的問題.在這方面的研究中，Chen等[2]首次以管網(wǎng)建設(shè)造價為優(yōu)化目標(biāo)，利用遺傳算法并結(jié)合啟發(fā)式管徑優(yōu)化算法進行了基于功能可靠度的供水管網(wǎng)抗震拓撲優(yōu)化和管徑優(yōu)化研究.進而，李杰等[3]、邢燕等[4]分別利用模擬退火算法和遺傳-模擬退火混合算法對供水管網(wǎng)進行了抗震拓撲優(yōu)化設(shè)計.徐良等[5]以管網(wǎng)年費用折算值為優(yōu)化目標(biāo)、以管網(wǎng)拓撲結(jié)構(gòu)與管段管徑為優(yōu)化參數(shù)、以管網(wǎng)節(jié)點最低可靠度為約束條件，建立供水管網(wǎng)抗震優(yōu)化設(shè)計模型，并將微粒群算法應(yīng)用到管網(wǎng)系統(tǒng)抗震優(yōu)化問題中.上述研究都從一個初始經(jīng)驗管網(wǎng)出發(fā)來進行簡化，優(yōu)化結(jié)果對初始經(jīng)驗管網(wǎng)依賴很大.2010年，李杰等[6]首先提出了基于自動生成策略的供水管網(wǎng)抗震優(yōu)化設(shè)計方法.這一方法只需要管網(wǎng)用戶節(jié)點信息就可以生成滿足抗震要求的供水管網(wǎng)，但這一方法在生成管線時不考慮實際工程背景，而是直接認為管線是連接管網(wǎng)節(jié)點的直線，與實際工程尚有差距.

在上述工作基礎(chǔ)上，本文將供水管網(wǎng)所在區(qū)域的道路信息引入管網(wǎng)優(yōu)化設(shè)計中，并結(jié)合環(huán)形網(wǎng)絡(luò)判斷方法，提出了新的自動生成網(wǎng)絡(luò)拓撲結(jié)構(gòu)的策略.基于此策略，本文利用遺傳算法、遺傳-模擬退火算法和微粒群算法進行了城市供水管網(wǎng)系統(tǒng)抗震拓撲優(yōu)化分析，并結(jié)合算例進行了對比分析.

1供水管網(wǎng)的抗震優(yōu)化模型

以城市供水管網(wǎng)拓撲結(jié)構(gòu)和管徑為優(yōu)化參數(shù)、抗震可靠度作為約束條件、管網(wǎng)建造運營費用最小為設(shè)計目標(biāo)來進行供水管網(wǎng)優(yōu)化設(shè)計，可建立如下供水管網(wǎng)抗震優(yōu)化模型[5]:

minW

(1)

式中：βmin為供水管網(wǎng)所有節(jié)點的抗震可靠度指標(biāo)的最小值，可以采用文獻[7]介紹的均值一次二階矩方法來求解；β0為供水管網(wǎng)設(shè)計時允許的抗震可靠指標(biāo)限值；W為供水管網(wǎng)的年費用折算值，可用下式表示[8]：

(2)

式中：p為管網(wǎng)的每年折舊和大修的百分率；T為管網(wǎng)建設(shè)投資償還期，年；n為泵站數(shù)目；WPi為泵站i的單位運行電費指標(biāo)，元·(m-3·s·m·年)；qi為泵站i的設(shè)計揚水流量，m3·s-1；hpi為泵站i的最大揚程，m；WN為管網(wǎng)造價，可用下式計算得到:

(3)

式中：lj為管線j的長度，m；dj為管線j的管徑，m；a1，a2，a3為造價經(jīng)驗系數(shù)，可以分別取62.105 1，1 979.7，1.486[9]；γj為管線j的連通系數(shù)，鋪設(shè)管線時取為1，不鋪設(shè)時取為0；m為管網(wǎng)中管線的數(shù)目.

2供水管網(wǎng)自動生成策略

自動生成技術(shù)的含義是從某種已有拓撲結(jié)構(gòu)(包括空白結(jié)構(gòu))出發(fā)，按照一定的規(guī)則，將單元增加到結(jié)構(gòu)中去，并不斷地進行調(diào)整，直至最后形成滿足預(yù)先給定要求的拓撲構(gòu)形為止.在供水管網(wǎng)抗震優(yōu)化設(shè)計中，采用自動生成技術(shù)可以生成優(yōu)化算法的初始種群.考慮到在實際工程中供水管網(wǎng)應(yīng)盡可能沿道路延伸，本文將供水管網(wǎng)所在區(qū)域的道路信息引入管網(wǎng)優(yōu)化設(shè)計中，建立了基于道路信息的供水管網(wǎng)自動生成策略.

相比于樹狀供水管網(wǎng)，環(huán)狀供水管網(wǎng)有著更好的可靠性.因此，本文將環(huán)形管網(wǎng)生成方法引入自動生成策略中，實現(xiàn)了供水管網(wǎng)的優(yōu)化設(shè)計.

2.1建立管網(wǎng)的初始信息

將管網(wǎng)所在區(qū)域的道路信息用道路節(jié)點間的路徑來表示，同時將管網(wǎng)節(jié)點放置于路徑之中.這樣在初始狀態(tài)下，管網(wǎng)信息由道路節(jié)點、道路節(jié)點間的路徑以及管網(wǎng)節(jié)點信息組成.同時，根據(jù)實際情況可以給出道路節(jié)點以及管網(wǎng)節(jié)點間的路徑長度.

2.2判斷能否生成環(huán)形網(wǎng)

2.3管線生成規(guī)則

管線的生成規(guī)則為：①當(dāng)管線兩節(jié)點之間沒有通過其他管網(wǎng)節(jié)點或只通過道路節(jié)點，則生成1條管線；②當(dāng)兩節(jié)點之間的管線通過其他管網(wǎng)節(jié)點，則以這些節(jié)點為端點生成多條管線.

上述規(guī)則保證任意一條管線以節(jié)點為端點，中間不通過其他節(jié)點.以圖1d中的網(wǎng)絡(luò)為例(節(jié)點8，9和10為道路節(jié)點)，若節(jié)點7，5間生成管線，即為管線7-5，管線的連接方式為7-5，長度為500 m；若節(jié)點7，6間生成管線，管線的連接方式為7-9-6，由于9是道路節(jié)點，不是管網(wǎng)節(jié)點，故生成管線7-6，長度為900 m；若節(jié)點7，1間生成管線，管線的連接方式為7-3-1，由于節(jié)點3為管網(wǎng)節(jié)點，則生成管線7-3和3-1，長度分別為500 m和400 m.

2.4生成初始管網(wǎng)拓撲結(jié)構(gòu)

在優(yōu)化算法中，首先要生成一系列初始管網(wǎng).在生成初始管網(wǎng)時，按照管網(wǎng)節(jié)點的編號順序逐個遍歷所有節(jié)點.對每個管網(wǎng)節(jié)點，生成它與其他節(jié)點之間的管線.生成方法為：對處于管網(wǎng)邊緣的節(jié)點，利用Dijkstra算法[10]找出與其路徑最短的3個節(jié)點；對處于管網(wǎng)中心的節(jié)點，找出與其路徑最短的4個節(jié)點，同時以一定概率生成它們之間的管線.

a管網(wǎng)1b管網(wǎng)2

c 管網(wǎng)3

d 管網(wǎng)4

圖2　待建供水管網(wǎng)

如圖2所示待建供水管網(wǎng)，4為水源點，1-3和5-12為需水節(jié)點， 13-19為道路節(jié)點.以邊緣節(jié)點1為例，如圖3a所示，與其路徑最短的3個節(jié)點為節(jié)點3，4和2.若節(jié)點1和3間生成管線，即為管線1-3，管線的連接方式為1-19-3.節(jié)點4為中間節(jié)點，如圖3b所示，與其路徑最短的4個節(jié)點分別為節(jié)點9，2，1和6.若節(jié)點4和2間生成管線，即為管線4-2，管線的連接方式為4-13-2；若節(jié)點4，9間生成管線，即為管線4-9，管線的連接方式為4-15-9.對每個節(jié)點進行一次操作，得到的一個可能的管網(wǎng)拓撲結(jié)構(gòu)如圖4所示.

2.5環(huán)狀修補過程

需要指出的是，在環(huán)狀管網(wǎng)設(shè)計過程中，可能會產(chǎn)生一些無意義的解，即：出現(xiàn)節(jié)點度為零的節(jié)點，從而造成1個管網(wǎng)斷成2個或多個子網(wǎng)；或者生成的管網(wǎng)為非環(huán)形網(wǎng).因此要對每一次生成的管網(wǎng)進行環(huán)狀修補，修補過程如下：

(1)將初始管網(wǎng)個體中生成的一條管線暫時刪除，同時暫時刪除這條管線所經(jīng)過道路的道路信息.

(2)對此個體在此道路信息下進行連通性修補.

a生成與節(jié)點1連接的管線b生成與節(jié)點4連接的管線圖3 管網(wǎng)生成過程Fig.3 Processofnetworkgeneration圖4 管網(wǎng)拓撲結(jié)構(gòu)Fig.4 Networktopology

首先，采用廣度優(yōu)先搜索，判斷生成的管網(wǎng)拓撲結(jié)構(gòu)的連通性，若存在與水源點不連通的節(jié)點，則對其進行連通性修補.進行修補時，對每個與水源點不連通的節(jié)點按前述自動生成管線的方式來增加管線，即：對處于管網(wǎng)邊緣的不連通節(jié)點，找出與其連接路徑最短的3個與水源點連通的節(jié)點，若此時與水源點連通的節(jié)點數(shù)小于3，則找出所有與水源點連通的節(jié)點；對處于管網(wǎng)中心的不連通節(jié)點，找出與其連接路徑最短的4個與水源點連通的節(jié)點，若此時與水源點連通的節(jié)點數(shù)小于4，則找出所有與水源點連通的節(jié)點.同時，以一定概率生成它們間的管線.

(3)將暫時刪除的那條管線和道路信息還原.

(4)對個體中每條已生成的管線依次重復(fù)步驟(1)～(3).

(5)對修補后的個體判斷是否為環(huán)狀網(wǎng).若非環(huán)狀網(wǎng)，則刪除此個體，重新生成.

圖5是對圖4進行環(huán)狀修補后得到的環(huán)狀管網(wǎng).

圖5　修補生成的環(huán)狀網(wǎng)

3基于自動生成策略的優(yōu)化算法在供水管網(wǎng)抗震優(yōu)化中的應(yīng)用

在管網(wǎng)優(yōu)化過程中，可以采用生物進化的原則構(gòu)造管網(wǎng)拓撲優(yōu)化問題的優(yōu)化算法.

3.1遺傳算法

遺傳算法是借鑒生物進化原則在20世紀70年代初期由美國密西根大學(xué)的Holland[11]教授提出的一種自適應(yīng)并行全局優(yōu)化概率搜索算法.其計算步驟包括編碼、生成初始種群、個體評價、選擇操作、交叉操作、變異操作和收斂性判斷等.

(1)編碼.把一個問題的解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的過程稱為編碼.假定一根管線管徑可取100，150，200，250，300，350，400，450，500 mm，則對應(yīng)的基因可取1，2，3，4，5，6，7，8，9，而基因取0值則表示這根管線不鋪設(shè).所有優(yōu)化參數(shù)對應(yīng)的基因按照指定的次序排列起來，就構(gòu)成一條染色體.在管網(wǎng)拓撲優(yōu)化模型中一個染色體對應(yīng)管網(wǎng)的一種拓撲結(jié)構(gòu)方案.多條染色體構(gòu)成遺傳算法的一個種群.

(2)生成初始種群.初始種群的生成由自動生成策略來實現(xiàn).

(3)個體評價.通過計算個體適應(yīng)度來評價個體，這里定義個體s(個體也即優(yōu)化的一個解)的適應(yīng)度函數(shù)為

(4)

式中：M為預(yù)先指定的一個較大的數(shù)值；W(s)為個體s對應(yīng)管網(wǎng)的年費用折算值；P1(s)，P2(s)為懲罰函數(shù)，可采用下式來計算懲罰函數(shù)：

徐曉春等(2004)對民樂銅礦區(qū)的輝銅礦化英安斑巖等樣品進行了Sm-Nd同位素年齡測定，等時線年齡為228±56 Ma，說明與該套中三疊世火山巖地層的時代屬于同一時代。

(5)

P2(s)=

(6)

(4)選擇操作.選擇操作是根據(jù)計算得到的個體適應(yīng)度選擇優(yōu)勝的個體進入下一代，并淘汰劣質(zhì)個體.本文采用最佳個體保存方法和適應(yīng)度比例方法.最佳個體保存方法是將上一代最優(yōu)的個體直接選擇進入下一代，并將最優(yōu)個體從群體中刪除; 適應(yīng)度比例方法即按群體中各個體的適應(yīng)度來確定個體被選擇的概率.當(dāng)選擇出來的個體達到規(guī)定的數(shù)目時，選擇操作結(jié)束，本文取為群體個體總數(shù)的1/3.

(5)交叉操作.交叉操作是遺傳算法中的重要操作之一，其以一定的交叉概率把2個父代個體的部分結(jié)構(gòu)加以替換重組從而生成新個體.這里采用單點交叉方法，其操作過程是在個體串中隨機設(shè)定一個交叉點，對隨機選擇出來的2個父代個體在該點前的部分結(jié)構(gòu)進行互換，從而生成2個新個體.這里對每一次交叉操作生成的新個體進行環(huán)狀網(wǎng)判斷及相應(yīng)的環(huán)狀修補.

(6)變異操作.變異操作是指以一定的變異概率將某個染色體編碼串中的基因用其他等位基因進行替換.這里對交叉獲得的新管網(wǎng)通過對其中的管線以一定的概率用其他直徑的管線代替來形成一個新的個體.在這過程中，為了引導(dǎo)管網(wǎng)個體向較好的方向發(fā)展，對滿足最小可靠度指標(biāo)要求的節(jié)點，以一定概率刪除以此節(jié)點為端點的管線；對不滿足最小可靠度指標(biāo)要求的節(jié)點，按生成管線的方式以一定概率生成與其他節(jié)點連接的管線.對新個體進行環(huán)狀網(wǎng)判斷及相應(yīng)的環(huán)狀修補.

(7)收斂判斷.本文采用固定迭代次數(shù)作為算法終止條件.

3.2遺傳-模擬退火算法

將模擬退火算法[12]嵌入到遺傳算法中發(fā)展出來的遺傳-模擬退火混合算法[13]可有效地增強遺傳算法的搜索能力.混合算法的計算過程與遺傳算法基本一樣，只是在變異操作時采用模擬退火操作.下面結(jié)合管網(wǎng)優(yōu)化問題來介紹模擬退火操作的步驟.

3.2.1目標(biāo)函數(shù)

模擬退火操作針對交叉操作得到的解來進行，每次選擇一個解作為當(dāng)前的初始解，然后對當(dāng)前解進行隨機擾動產(chǎn)生一個新解，根據(jù)式(7)確定接受新解的概率P，也即用解s2代替解s1的概率.

(7)

式中：t為當(dāng)前的溫度；f(s)為解s的目標(biāo)函數(shù).

(8)

式中：W(s)為解s對應(yīng)管網(wǎng)的年費用折算值；P3(s)為懲罰函數(shù)，可以采用下式來計算：

(9)

式中：b1，b2為常數(shù)，其值的大小需要根據(jù)具體的管網(wǎng)來確定.

3.2.2隨機擾動模型

3.2.3溫度參數(shù)的控制

溫度參數(shù)是模擬退火過程中最關(guān)鍵的參數(shù)，主要包括起始溫度的選取、溫度的下降方法、每一溫度迭代次數(shù)的確定等.

一般采用t0=Cδ來估計初始溫度.其中，C為通過試算得到的一個充分大的數(shù)，δ=Wmax-Wmin，Wmax，Wmin為父代群體中個體年費用折算值的最大值和最小值.

模擬退火操作要求溫度下降到零，整個系統(tǒng)以概率1收斂到全局最優(yōu)解.本文所用溫度下降的方法為tr′+1=αtr′，其中：r′為模擬退火操作的計算代數(shù)；α為降溫速率，0<α<1，α越接近于1溫度下降越慢，這種方法簡單易行，它的每一步以相同的比率降溫.

本文采用固定長度法來給定每一溫度的迭代長度.

3.3微粒群算法

微粒群算法[14]是通過模擬鳥群的捕食行為而建立的優(yōu)化算法.在微粒群算法中，設(shè)待優(yōu)化問題的解在一個d維的搜索空間中，群體中的第s個微粒位置表示待優(yōu)化問題的一個解，可表示為一個d維矢量，Xs=(xs1,xs2,…,xsd)T；微粒s的速度表示其位置的改變，可用Vs=(vs1,vs2,…,vsd)T來表示.當(dāng)前群體的最好位置的微粒l用Kl=(kl1,kl2,…,kld)T表示，整個演化過程中歷史最好位置的微粒g用Kg=(kg1,kg2,…,kgd)T表示.則微粒群中，對每一代微粒s的第u維的進化方程為

(10)

(11)

式中：γ為慣性權(quán)重，取值越大全局搜索能力越強，取值越小局部搜索能力越好；r為進化代數(shù)；R1()和R2()為2個隨機函數(shù)，產(chǎn)生0～1之間的隨機數(shù)；c1，c2為加速度常數(shù)，取較大值可以拓展微粒的搜索空間，取較小值則可提高微粒的搜索精度.

將微粒群算法應(yīng)用到管網(wǎng)抗震優(yōu)化設(shè)計中時，每個微粒的位置對應(yīng)一個管網(wǎng)結(jié)構(gòu)方案，即問題的一個解.其編碼方式與遺傳算法相同.在進化過程中，當(dāng)位置矢量中某一維的值小于零時，則取零；當(dāng)其值大于最大管徑編碼值時，則取最大管徑編碼值；處于兩者間時，則選擇與其最接近的管徑編碼值.

管網(wǎng)抗震優(yōu)化問題的優(yōu)化目標(biāo)是為了獲得在滿足節(jié)點最低抗震可靠度條件下管網(wǎng)最低的年費用折算值，于是對不滿足約束條件的解，通過增加年費用折算值對其懲罰.解s的適應(yīng)值函數(shù)取為

(12)

式中：P4為懲罰函數(shù)，可取足夠大的常數(shù).

管網(wǎng)抗震優(yōu)化的微粒群算法的步驟如下：①微粒群個體的初始位置由自動生成技術(shù)來實現(xiàn)，并隨機產(chǎn)生初始速度；②計算每個微粒的適應(yīng)值，對不滿足約束條件的微粒采用罰函數(shù)進行處理；③對每個微粒，將其適應(yīng)值與其當(dāng)前群體最好位置的適應(yīng)值進行比較，若較好，則將其作為當(dāng)前群體最好位置；④將當(dāng)前群體最好位置的適應(yīng)值與整個演化過程中歷史最好位置的適應(yīng)值進行比較，若較好，則將其作為歷史最好位置；⑤分別對每個微粒的各維的速度和位置進行更新，并對無效的管網(wǎng)結(jié)構(gòu)進行修補，如未達到一個預(yù)設(shè)的最大迭代數(shù)，則返回步驟②.

3.4供水管網(wǎng)抗震優(yōu)化過程

城市供水管網(wǎng)系統(tǒng)的抗震優(yōu)化設(shè)計過程如圖6所示.整個設(shè)計過程依托于優(yōu)化算法的大框架，將自動生成策略嵌入此大框架之中，進而完成整個設(shè)計過程，最終給出優(yōu)化的設(shè)計管網(wǎng).

圖6　供水管網(wǎng)抗震設(shè)計過程

4實例分析

4.1實例1

圖7為一個20個節(jié)點的待建供水管網(wǎng)，其中節(jié)點1～19為用戶節(jié)點，20為水源點，21～33為道路節(jié)點，虛線給出了待建供水管網(wǎng)所在區(qū)域的道路分布狀況.考慮地震烈度為8度進行管網(wǎng)抗震優(yōu)化設(shè)計.管材為鑄鐵.約束條件取最低可靠度指標(biāo)為0.84(對應(yīng)節(jié)點最小可靠度0.80).根據(jù)工程實際，選定管網(wǎng)中管線的管徑種類和管徑值，分別為160，200，250，300，350，400，450，500，550 mm 這9 種，對應(yīng)的管徑編碼取為1，2，3，4，5，6，7，8，9.取種群規(guī)模為60，迭代次數(shù)為50，管線生成概率取0.9，各優(yōu)化算法基本參數(shù)如下.

圖7　實例1待建供水管網(wǎng)

遺傳算法：交叉概率采用動態(tài)自適應(yīng)算法來確定，即：若個體適應(yīng)度大于群體的平均適應(yīng)度，則交叉率取0.90；反之，則交叉率取0.99.變異概率取為0.2.

遺傳-模擬退火算法：交叉概率同遺傳算法，初始溫度為100度，當(dāng)前循環(huán)溫度為上一代的0.4倍，內(nèi)循環(huán)次數(shù)為10次.

微粒群算法：慣性權(quán)重γ從0.9至0.4線性減小，加速度常數(shù)c1和c2均從1.5至0.4線性減小.

利用前述3種方法分別對待建管網(wǎng)進行抗震優(yōu)化設(shè)計.圖8給出了3種方法的供水管網(wǎng)優(yōu)化方案.表1給出了3種方法所得優(yōu)化方案的管網(wǎng)年費用折算值，表2給出了3種優(yōu)化算法給出的優(yōu)化結(jié)果中各個節(jié)點的可靠度指標(biāo).從表1可以看出，遺傳-模擬退火算法的費用最低，微粒群算法次之，遺傳算法最高，但遺傳算法與微粒群算法的費用差別不大.從表2可以看出，遺傳-模擬退火算法得到的結(jié)果中節(jié)點可靠度指標(biāo)最高，平均值達到2.012 3；遺傳算法次之，節(jié)點可靠度指標(biāo)平均值為1.504 2；微粒群算法最低，為1.343 9.因此，遺傳-模擬退火算法得到的優(yōu)化結(jié)果年費用折算值低，節(jié)點可靠度指標(biāo)均值高，表現(xiàn)最好.遺傳算法雖然年費用折算值比微粒群算法略高，但是得到的節(jié)點可靠度指標(biāo)均值比微粒群算法好.因此本例中，遺傳-模擬退火算法表現(xiàn)最好，遺傳算法和微粒群算法表現(xiàn)相當(dāng).

a 基于微粒群算法的管網(wǎng)優(yōu)化方案

b 基于遺傳算法的管網(wǎng)優(yōu)化方案

c 基于遺傳-模擬退火算法的管網(wǎng)優(yōu)化方案

圖8　管網(wǎng)優(yōu)化結(jié)果

表1　實例1三種優(yōu)化算法的管網(wǎng)年費用折算值

表2　實例1不同優(yōu)化算法的節(jié)點可靠度指標(biāo)

4.2實例2

圖9為綿竹市城區(qū)供水管網(wǎng)，這里僅保留了各需水點、水源點和道路信息，其中節(jié)點1～58為需水點，59～62為水源點，63～64為道路節(jié)點，虛線給出了待建供水管網(wǎng)所在區(qū)域的道路分布狀況.利用前述3種方法分別對管網(wǎng)重新進行抗震優(yōu)化設(shè)計.考慮到本例中存在與管網(wǎng)由單條管線相連的水源點，因而在管網(wǎng)優(yōu)化設(shè)計中加入判定規(guī)則，以使管網(wǎng)中此類管線在優(yōu)化進程中的環(huán)狀網(wǎng)判斷中不被刪除，從而保證所有水源點都與管網(wǎng)相連.考慮地震烈度為8度進行管網(wǎng)抗震優(yōu)化設(shè)計.管材為鑄鐵.約束條件取最低可靠度指標(biāo)0.84(對應(yīng)節(jié)點最小可靠度0.8).各算法基本參數(shù)選取與實例1同.表3給出3種方法所得優(yōu)化方案的管網(wǎng)年費用折算值.從表中同樣可見，基于自動生成策略的遺傳-模擬退火算法具有最好的優(yōu)化性能，圖10為其優(yōu)化結(jié)果.

圖9　綿竹市待建供水管網(wǎng)

優(yōu)化算法年費用折算值/萬元節(jié)點可靠度指標(biāo)最小值微粒群算法276.30.8617遺傳算法272.80.9584遺傳模擬退火算法271.71.0634

5結(jié)論

結(jié)合環(huán)形供水管網(wǎng)的判斷方法并將道路信息引入管網(wǎng)抗震優(yōu)化設(shè)計中，建立了供水管網(wǎng)的自動生成策略.同時，將自動生成策略嵌入到3種優(yōu)化算法中，實現(xiàn)遺傳算法、遺傳-模擬退火混合算法和微粒群算法在供水管網(wǎng)的抗震優(yōu)化設(shè)計中的應(yīng)用.利用上述3種算法對2個供水管網(wǎng)進行了實例分析，結(jié)果表明，遺傳-模擬退火算法具有最好的優(yōu)化能力.

參考文獻:

[1]李杰. 生命線工程抗震—基礎(chǔ)理論與應(yīng)用[M]. 北京: 科學(xué)出版社， 2005.

LI Jie. Lifeline earthquake engineering—Basic methods and applications [M]. Beijing: Science Press, 2005.

[2]Chen L L, Li J, Xu C C. Seismic reliability-based optimization for water supply network[C]//Proc. the 9th International Conference on Computing in Civil and Building Engineering. Taipei: Taiwan University, 2002:793-798.

[3]李杰，衛(wèi)書麟，劉威. 基于模擬退火算法的供水管網(wǎng)抗震優(yōu)化設(shè)計[J].地震工程與工程振動，2009，29(3)：108.

LI Jie, WEI Shulin, LIU Wei. Seismic reliability optimization of water distribution networks with simulated annealing algorithms[J]. Earthquake Engineering and Engineering Vibration. 2009, 29(3):108.

[4]邢燕，李杰. 混合優(yōu)化策略在生命線管網(wǎng)拓撲設(shè)計中的應(yīng)用[J].同濟大學(xué)學(xué)報：自然科學(xué)版，2008，36(5)：569.

圖10　基于遺傳-模擬退火算法的綿竹管網(wǎng)優(yōu)化方案

XING Yan, LI Jie. Hybrid optimization strategy for topology design of lifeline networks[J]. Journal of Tongji University: Natural Science, 2008，36(5)：569.

[5]徐良，劉威，李杰. 基于微粒群算法的供水管網(wǎng)抗震優(yōu)化設(shè)計[J].防災(zāi)減災(zāi)工程學(xué)報，2010，30(3)：269.

XU Liang, LIU Wei, LI Jie. Seismic reliability optimization of water distribution network with particle swarm algorithm[J]. Journal of Disaster Prevention and Mitigation Engineering, 2010，30(3)：269.

[6]李杰，邢燕. 基于可靠度的生命線工程網(wǎng)絡(luò)抗震設(shè)計[J]. 同濟大學(xué)學(xué)報：自然科學(xué)版，2010，38(6)：783.

LI Jie, XING Yan. Reliability-based seismic design of lifeline networks[J]. Journal of Tongji University: Natural Science, 2010，38(6)：783.

[7]陳玲俐，李杰. 城市供水管網(wǎng)系統(tǒng)抗震功能可靠度分析[J]. 工程力學(xué)，2004，21(4)：45.

CHEN Lingli, LI Jie. Aseismatic serviceability analysis of water supply network[J]. Engineering Mechanics，2004，21(4)：45.

[8]嚴煦世, 劉遂慶. 給水排水管網(wǎng)系統(tǒng)[M]. 北京: 中國建筑工業(yè)出版社, 2003.

YAN Xushi, LIU Suiqing. Water and wastewater pipeline network systems[M]. Beijing: China Architecture and Building Press, 2003.

[9]邵知宇. 給水管網(wǎng)分段線性優(yōu)化模型[D]. 上海: 同濟大學(xué)，2001.

SHAO Zhiyu. Piecewise linear optimization model of water pipeline network[D]. Shanghai: Tongji University, 2001.

[10]Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematlk, 1959，1(1):269.

[11]Holland J H. Adaptation in natural and artificial systems[M]. ANN Arbor: University of Michigan Press, 1975.

[12]Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4958):671.

[13]Jeong I, Lee J. Adaptive simulated annealing genetic algorithm for system identifictation [J]. Engineering Applications of Artificial Intelligence, 1996, 9(5):523.

[14]Kennedy J. A new optimizer using particle swarm theory [C]//The Sixth International Symposium on Micro Machine and Human Science. Nagoya: Nagoya Municipal Industrial Research Institute, 1995: 39-43.

收稿日期：2015-07-07

基金項目：國家自然科學(xué)基金面上項目(51278380)

中圖分類號：P315.9

文獻標(biāo)志碼：A

Seismic Topology Optimization Algorithms for Water Distribution Networks based on Automatic Generation Strategy

LIU Wei1,2， YUAN Hongwei3, XU Liang4

(1. State Key Laboratory for Disaster Reduction in Civil Engineering, Tongji University, Shanghai 200092, China; 2. College of Civil Engineering, Tongji University, Shanghai 200092, China; 3. Beijing Institute of Architectural Design, Beijing 100045, China; 4.Shanghai Nuclear Engineering Research & Design Institute, Shanghai 200233, China)

Abstract：Taking water distribution network’s annual reduced cost as optimization object and seismic reliability as optimization restriction, a network topology optimization model is established. Then, an automatic generation strategy based on the existed road information is proposed. Combining with ring network generation method and automatic generation strategy, three approaches, a genetic algorithm, a simulated annealing genetic algorithm and a particle swarm algorithm, are employed to solve the seismic optimization model. Two networks are optimized using three algorithms and a comparative study is performed. The comparison indicates that the simulated annealing genetic algorithm performs the best.

Key words：water distribution network; automatic generation strategy; genetic algorithm; simulated annealing genetic algorithm; particle swarm algorithm

第一作者： 劉威(1976—)，男，副教授，工學(xué)博士，主要研究方向為生命線工程防災(zāi).E-mail：liuw@#edu.cn