張 進(jìn),王衛(wèi)敏,荊振鋒,趙有民

(1.陜西城鎮(zhèn)規(guī)劃建筑設(shè)計研究院,西安710068;2.西安建筑設(shè)計研究院,西安710054;3.延安熱電廠,延安716000)

0 引言

水力管網(wǎng)優(yōu)化的實質(zhì)是,在水力約束條件下,確定使目標(biāo)函數(shù)即綜合費(fèi)用 (包括初投資和設(shè)計年限內(nèi)的運(yùn)行費(fèi)用)為最小的變量 (管徑)。這類問題在數(shù)學(xué)分析中稱為極值問題,在統(tǒng)計數(shù)學(xué)中稱為最優(yōu)化問題。傳統(tǒng)的求解非線性優(yōu)化問題的方法對管網(wǎng)優(yōu)化模型進(jìn)行求解時必須先假設(shè)管徑是連續(xù)變量,同時在求解過程中必須對目標(biāo)函數(shù)進(jìn)行求導(dǎo),因此,在實際應(yīng)用中受到了限制。本文嘗試將遺傳算法應(yīng)用到水力管網(wǎng)的優(yōu)化中,相對于傳統(tǒng)的優(yōu)化方法,遺傳算法直接針對實際規(guī)格的管徑,計算簡便易行,只包括復(fù)制、交叉、變異這幾個簡單的過程。

1 遺傳算法簡介

遺傳算法其實質(zhì)是一種由計算機(jī)完成主要計算過程的迭代方法。遺傳算法起源于20世紀(jì)60年代對自然和人工自適應(yīng)系統(tǒng)的研究[1],最早由美國密執(zhí)安大學(xué)的Holland教授提出。遺傳算法借鑒了達(dá)爾文的自然進(jìn)化理論與孟德爾的遺傳變異理論,通過選擇一定數(shù)量的個體進(jìn)行雜交以及基因突變,把優(yōu)秀的基因傳給后代,丟棄不良基因,經(jīng)過數(shù)代遺傳,最終得到最優(yōu)秀的一個或幾個后代 (問題的最優(yōu)解)。

遺傳算法已用于求解帶有應(yīng)用前景的一些問題,例如遺傳程序設(shè)計、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計算機(jī)圖像處理和機(jī)器人運(yùn)動規(guī)劃等。遺傳算法經(jīng)過很多人的改良也產(chǎn)生了很多變種,本文所涉及的遺傳算法僅指 “簡單遺傳算法”簡稱SGA。與傳統(tǒng)優(yōu)化算法相比,SGA具有以下特點(diǎn)[2]:(1)搜索過程不直接作用在變量上,而是作用在將變量編碼后的字符串上;(2)搜索過程從一組解迭代到另一組解,降低了陷入局部最優(yōu)解的可能性;(3)搜索過程是隨機(jī)的而非確定性的;(4)對搜索空間沒有任何特殊要求,不需要導(dǎo)數(shù)等其它輔助信息。

2 遺傳算法解決優(yōu)化問題的主要步驟

從技術(shù)經(jīng)濟(jì)觀點(diǎn)來看,任何輸配系統(tǒng)的方案,均可用工程造價和運(yùn)行費(fèi)用來評價。

2.1 管徑編碼

編碼是遺傳算法的第一步,采用二進(jìn)制編碼方案。為便于討論,水力管網(wǎng)的管材選用無縫鋼管(GB8163-87)系列,實際應(yīng)用時選用其他管材無非價格不同而已。取8種規(guī)格的鋼管進(jìn)行編碼,如表1所示。

表1 管徑編碼表

2n種規(guī)格的鋼管編碼便有n位。

管徑編碼完成后,管網(wǎng)的設(shè)計方案即可用按管段編號順序排列的一串0,1字符表示。例如,由8根管段組成的管網(wǎng)的公稱管徑按管段號排列依次為:20,25,25,32,40,32,70,80,那么對應(yīng)的二進(jìn)制表示的字符串則為:000|001|001|010|011|010|101|110。這個二進(jìn)制字符串在遺傳算法中稱為遺傳算子,也叫染色體。

以8根管段組成的管網(wǎng)為例,算法第一步就是隨機(jī)產(chǎn)生一定數(shù)量的染色體,每個染色體為24位字節(jié)的二進(jìn)制數(shù)即可。染色體總數(shù)叫種群規(guī)模,它對算法的效率有明顯的影響,規(guī)模太小不利于進(jìn)化,而規(guī)模太大將導(dǎo)致程序運(yùn)行時間長。建議對管網(wǎng)優(yōu)化問題,此規(guī)模取30至100。

2.2 適應(yīng)度函數(shù)

為了體現(xiàn)染色體的適應(yīng)能力,引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù),叫適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度,它體現(xiàn)了自然進(jìn)化中的優(yōu)利劣汰原則。

管道的初投資取決于材料費(fèi)和安裝費(fèi)。管道的安裝費(fèi)在管道敷設(shè)深度、土壤和路面性質(zhì)、管子連接方法、施工機(jī)械化程度確定后則由管徑?jīng)Q定,一般來說管徑變化對安裝費(fèi)影響不大。

管網(wǎng)的運(yùn)行費(fèi)用主要由電費(fèi)和維修費(fèi)組成,維修費(fèi)受當(dāng)?shù)毓芾硭较拗埔话闩c初投資成正比,電費(fèi)與流量和壓降的乘積成正比,而壓降在管徑確定后則由流量決定。

工程實際中,已知管網(wǎng)總流量,給定各管段管徑后,根據(jù)連續(xù)性方程,并聯(lián)管段阻力相同和水力計算的經(jīng)驗公式可由電腦計算出各管段流量。有了管徑和流量就可以計算出初投資和設(shè)計年限內(nèi)的運(yùn)行費(fèi)用 (也由電腦自動完成),得出費(fèi)用評價函數(shù)W=∑[f(di)+g(di,qi)]。式中f(di)為初投資費(fèi)用,是管徑的函數(shù),單位為元。g(di,qi)為運(yùn)行費(fèi)用,是管徑及流量的函數(shù),單位為元。di為各段管徑,單位為mm。qi為各段流量,單位為噸每小時。

可見每個染色體唯一對應(yīng)一個綜合費(fèi)用,從而可以用綜合費(fèi)用評價染色體的優(yōu)劣。管網(wǎng)優(yōu)化計算中應(yīng)該費(fèi)用越低則適應(yīng)度越大,才能達(dá)到管網(wǎng)優(yōu)化的目的。按照這個要求,通常可以將適應(yīng)度函數(shù)取為與費(fèi)用評價函數(shù)W成反比,即:f=1/W,也可取與W平方成反比。

2.3 遺傳操作

簡單遺傳算法的遺傳操作主要有三種:選擇、交叉、變異。

2.3.1 選擇操作 選擇的目的是把優(yōu)化的染色體直接復(fù)制到下一代或通過配對交叉產(chǎn)生新的染色體再遺傳到下一代。這里采取配對交叉遺傳的方式。選擇機(jī)制為適應(yīng)度比例選擇機(jī)制,也叫賭輪或蒙特卡羅選擇。在該機(jī)制中,每個染色體的選擇概率為其適應(yīng)度值除以所有染色體適應(yīng)度值之和,適應(yīng)度值大的染色體被選擇的幾率較高。同時,采用最佳個體保存方法,把群體中適應(yīng)度值最大的染色體不進(jìn)行配對交叉而直接復(fù)制到下一代中,這樣,可以保證產(chǎn)生的新一代群體的最大適應(yīng)度值不會小于上一代。Radolph在文獻(xiàn) [3]中證明了遺傳算法不一定收斂,只有每代保存了最優(yōu)個體時才收斂。在實際應(yīng)用中,使用了上述結(jié)論來保證收斂性。采用優(yōu)秀個體保護(hù)法就是將每代中的最優(yōu)個體,直接進(jìn)入子代。

對保存最優(yōu)個體時遺傳算法是收斂的結(jié)論的證明是通過對遺傳算法構(gòu)造馬爾柯夫 (markov)鏈,因為遺傳算法的進(jìn)行過程是一個馬爾柯夫過程。

注:馬爾柯夫鏈。狀態(tài)是指某一事件在某個時刻 (或時期)出現(xiàn)的某種結(jié)果。事件的發(fā)展,從一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài),稱為狀態(tài)轉(zhuǎn)移。在事件的發(fā)展過程中,若每次狀態(tài)的轉(zhuǎn)移都僅與前一時刻的狀態(tài)有關(guān),而與過去的狀態(tài)無關(guān),或者說狀態(tài)轉(zhuǎn)移過程是無后效性的,則這樣的狀態(tài)轉(zhuǎn)移過程就稱為馬爾柯夫過程。馬爾柯夫鏈?zhǔn)菂?shù)t只取離散值的馬爾柯夫過程。

2.3.2 交叉操作 交叉是模仿自然界有性繁殖的基因重組過程,其作用是將原有的優(yōu)良基因遺傳給下一代個體,并生成包含更復(fù)雜基因結(jié)構(gòu)的新個體。交叉操作是遺傳算法區(qū)別于其他所有優(yōu)化算法的根本所在,如果從一個遺傳算法中去掉交叉操作,則其結(jié)果將不再是一個遺傳算法[4]。

交叉操作是將被選擇出的兩個個體P1和P2作為父母個體,將兩者的部分碼值進(jìn)行交換。對于24位的染色體:由電腦隨機(jī)產(chǎn)生一個在1到24之間的隨機(jī)數(shù)c,假如現(xiàn)在產(chǎn)生的是3,將P1和P2的低3位交換:P1的高21位與P2的低3位組成一個新染色體,這就是P1和P2的一個后代Q1個體;P2的高21位與P1的低3位組成另一個新染色體,這就是P1和P2的一個后代Q2個體。

2.3.3 變異操作 變異是模擬自然界生物體進(jìn)化中染色體上某位基因發(fā)生的突變現(xiàn)象。變異可以使搜索避免陷入局最優(yōu),可以在當(dāng)前解附近找到更好的解,同時還可以保持群體的多樣性,確保群體能夠繼續(xù)進(jìn)化[4]。

對于24位的染色體:由電腦隨機(jī)產(chǎn)生一個在1到24之間的隨機(jī)數(shù)d,假如現(xiàn)在產(chǎn)生的是3,將原染色體的第3位0和1互換產(chǎn)生一個新染色體。

2.3.4 操作的控制參數(shù) 不是每個被選擇了的染色體都進(jìn)行交叉操作和發(fā)生變異,而是以一定的概率進(jìn)行,一般在程序設(shè)計中交叉發(fā)生的概率要比變異發(fā)生的概率選取的大若干個數(shù)量級,交叉概率取0.6至0.95之間的值;變異概率取0.001至0.01之間的值。個人建議設(shè)定一大一小兩個變異概率,當(dāng)整個種群平均適應(yīng)度增長較快時,使用小變異概率;反之使用較大變異概率。

2.4 算法的終止條件

遺傳算法的一般循環(huán)終止條件為設(shè)定最大進(jìn)化代數(shù),個人建議取50～80次。也可以把解的質(zhì)量作為判據(jù),如連續(xù)幾次得到的最優(yōu)個體的適應(yīng)度沒有變化或變化很小時,則認(rèn)為算法收斂,循環(huán)終止。再次,種群中最優(yōu)個體的適應(yīng)度和群體的平均適應(yīng)度的差除以群體平均適應(yīng)度,所得的結(jié)果小于某一給定允許值,也可以作為循環(huán)終止的條件。

2.5 染色體解碼

終止后輸出種群中適應(yīng)度值最優(yōu)的染色體,對其進(jìn)行解碼得到管網(wǎng)各管段的管徑。解碼就是管道編碼的逆運(yùn)算。

2.6 遺傳算法解題步驟的總結(jié)

根據(jù)遺傳算法思想可以畫出如圖1所示的簡單遺傳算法框圖。

圖1 簡單遺傳算法示意圖

遺傳算法的主要步驟如下:

(1)隨機(jī)產(chǎn)生一個由確定長度的染色體組成的初始群體。

(2)對該染色體群體迭代地執(zhí)行下面的步驟①和步驟②直到滿足停止準(zhǔn)則為止:

①計算群體中每個染色體的適應(yīng)值;

②應(yīng)用復(fù)制、交叉和變異等遺傳操作產(chǎn)生下一代群體。

(3)達(dá)到終止條件后,把后代中出現(xiàn)的最好的染色體輸出為遺傳算法的執(zhí)行結(jié)果,這個結(jié)果可以解碼為問題的一個解。

2.7 算例描述

某管網(wǎng)連接圖見圖2。共有7個節(jié)點(diǎn),6條管道連接路線。管網(wǎng)中各個節(jié)點(diǎn)需水量和長度見圖示,管道單價經(jīng)驗公式為:

管徑D的單位為mm,適應(yīng)度函數(shù)取為與費(fèi)用評價函數(shù)W成反比,即:

圖2 某管網(wǎng)連接圖

對此管網(wǎng)應(yīng)用遺傳算法進(jìn)行優(yōu)化布置,設(shè)置群體規(guī)模為30,設(shè)定最大進(jìn)化代數(shù)為50代,進(jìn)行計算。

以下列出最后三步的最優(yōu)解 (見表2)。

表2 最后三步的最優(yōu)解

3 結(jié)語

遺傳算法在計算結(jié)果以及收斂速度方面具有優(yōu)勢,但是算法的參數(shù)選取直接影響到算法的效果,需要進(jìn)一步研究。

此外,管網(wǎng)系統(tǒng)是個復(fù)雜的系統(tǒng)工程,本文中未對當(dāng)?shù)厮牡刭|(zhì)條件、政策、物價的波動等因素做深入考察,需要進(jìn)一步研究加以完善。

[1] HOLLAND J H.Adaptation in nature and artificial systems[M].Michigan:The University of Michigan Press,1975

[2] 周明,孫樹棟.遺傳算法原理及應(yīng)用 [M].北京:國防工業(yè)出版社,1999

[3] Qi X F;Palmieri theoretical analysisof evolutionary algorithms with an infinite population size in continuous space(Part,)[M].IEEE Transactions on Neural Network;1994

[4] 張鈴,張鈸.遺傳算法機(jī)理的研究[J].軟件學(xué)報,2000,(7):945-952