趙昆

摘 要：本文旨在應(yīng)用GA建立燃?xì)夤芫W(wǎng)的布局設(shè)計模型，實現(xiàn)以應(yīng)用軟件平臺為基礎(chǔ)的計算機(jī)優(yōu)化設(shè)計。主要工作包括：首先，在閱讀了大量文獻(xiàn)的基礎(chǔ)上，本文指出了燃?xì)夤芫W(wǎng)布局優(yōu)化在現(xiàn)實工作中的重要意義，論述了遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化上的現(xiàn)狀和研究工作。其次，基于優(yōu)化燃?xì)夤芫W(wǎng)布局的數(shù)學(xué)建模，將遺傳算法應(yīng)用于燃?xì)夤芫W(wǎng)布局的優(yōu)化問題中，采用Prüfer數(shù)的編碼方式及相應(yīng)的遺傳操作，設(shè)計了遺傳算法。并在MAPINFO平臺上實現(xiàn)了燃?xì)夤芫W(wǎng)連接布局系統(tǒng)。最后給出進(jìn)一步的研究方向。

關(guān)鍵詞：燃?xì)夤芫W(wǎng)；遺傳算法；優(yōu)化設(shè)計

在燃?xì)夤こ添椖康耐顿Y和燃?xì)夤芫W(wǎng)管理系統(tǒng)運(yùn)行中燃?xì)夤芫W(wǎng)的工程造價所用的費(fèi)用是很大的，如采用優(yōu)化組合設(shè)計可節(jié)省大量能源。要選擇最優(yōu)的燃?xì)夤芫W(wǎng)優(yōu)化設(shè)計方案，必須要保證燃?xì)夤┙o所滿足的流量、壓力、壓差、溫度等安全因素，同時要考慮工程投資的經(jīng)濟(jì)性，以及系統(tǒng)運(yùn)行的管理費(fèi)用的經(jīng)濟(jì)性。如何能保證整個過程最大程度地安全輸配，并且具有科學(xué)性、合理性，是現(xiàn)實中的一個難點(diǎn)。所以城市燃?xì)夤芫W(wǎng)優(yōu)化設(shè)計具有極其重要的意義。隨著計算機(jī)技術(shù)及應(yīng)用軟件的發(fā)展，智能科學(xué)的研究幾乎滲透于各個學(xué)科領(lǐng)域，智能優(yōu)化算法理論的不斷發(fā)展豐富、應(yīng)用研究的不斷廣泛深入，已經(jīng)有越來越多的新方法應(yīng)用于各個工程領(lǐng)域，使其業(yè)已成為解決諸多大規(guī)模復(fù)雜工程實際問題的有利工具和有效方法。燃?xì)夤芫W(wǎng)的設(shè)計過程已從手算過渡到電算，從憑經(jīng)驗設(shè)計過渡到智能優(yōu)化設(shè)計。若只依賴于大量表格的經(jīng)驗設(shè)計，會受一些條件的約束，使得計算不太準(zhǔn)確而且繁瑣。采用遺傳算法（Genetic Algorithm，GA），模擬退火算法、蟻群算法、粒子群算法及其混合優(yōu)化算法等智能優(yōu)化方法來研究可靠性綜合問題。特別是大型復(fù)雜管網(wǎng)的可靠性優(yōu)化、冗余的最優(yōu)分配以及管網(wǎng)的最優(yōu)設(shè)計，是十分有效的，可以獲得較傳統(tǒng)方法和啟發(fā)式方法更好的優(yōu)化方案。這些智能優(yōu)化算法已不再采用傳統(tǒng)的設(shè)計思想，由于魯棒性強(qiáng)，目前已解決了各種各樣的組合優(yōu)化問題。當(dāng)城市氣源和用戶地理給定后，在各用戶和其它相鄰的用戶之間根據(jù)地理條件和市政要求，存在多個管道布置方案，從中選擇最佳的布局形式是后續(xù)進(jìn)行參數(shù)優(yōu)化的基礎(chǔ)。因此，需要選擇一種高效、科學(xué)、合理的算法是系統(tǒng)設(shè)計優(yōu)化的關(guān)鍵。將遺傳算法應(yīng)用于優(yōu)化設(shè)計燃?xì)夤芫W(wǎng)的布局中具有很強(qiáng)的適應(yīng)性，它是與傳統(tǒng)技術(shù)有著截然的不同。通常在求解一個具體的問題時，在確定個體編碼、適應(yīng)度函數(shù)及遺傳算子后，遺傳算法將在進(jìn)化過程中利用所獲得的信息自動進(jìn)行搜索，這種自然選擇消除了算法設(shè)計過程中的一個最大的障礙，即“需要事先描述問題的全部特點(diǎn)”，所以遺傳算法能以較少的計算來獲得較大的收益，是優(yōu)化燃?xì)夤芫W(wǎng)布局的一種理想化的選擇方法。因此，采用新的方法研究適用性更強(qiáng)的燃?xì)夤艿纼?yōu)化設(shè)計方案及應(yīng)用軟件是十分必要的。以燃?xì)夤芫W(wǎng)鋪設(shè)線路總長度最短為目標(biāo)，建立燃?xì)夤芫W(wǎng)布局?jǐn)?shù)學(xué)模型，并將遺傳算法應(yīng)用到燃?xì)夤芫W(wǎng)的布局設(shè)計中，同時解決算法中所設(shè)計到的一系列技術(shù)，其主要的工作步驟包括個體編碼方式、適應(yīng)度函數(shù)的確定、群體規(guī)模大小、選擇算子、交叉算子和變異算子等，求解出最佳的燃?xì)夤芫W(wǎng)布局優(yōu)化設(shè)計的形式。遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化的研究分析眾所周知，自然界有不少問題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或準(zhǔn)最優(yōu)解，TSP問題和規(guī)劃問題等組合優(yōu)化問題就是典型的例子。在求解此類問題時，若不能利用問題的固有知識來縮小搜索空間，則會產(chǎn)生搜索的“組合爆炸”。因此，遺傳算法研究能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準(zhǔn)最優(yōu)解的通用搜索算法一直是令人矚目的研究課題。雖然遺傳算法是隨機(jī)化方法，但它不是簡單的隨機(jī)搜索，而是有效的利用歷史信息來推測新搜索點(diǎn)，并且不用事先知道目標(biāo)函數(shù)，大大減輕了工作量，同時也提高了工作效率，是優(yōu)化燃?xì)夤芫W(wǎng)布局的理想方法。隨著城市現(xiàn)代化建設(shè)的發(fā)展，對優(yōu)化燃?xì)夤芫W(wǎng)布局應(yīng)用的重視程度也與日俱增，應(yīng)用了許多方法對它進(jìn)行評估，取得了顯著的效果。

遺傳算法（Genetic Algorithm， GA）啟發(fā)于自然現(xiàn)象或過程，是近年來迅速發(fā)展起來的一種全新的隨機(jī)搜索與優(yōu)化算法，其基本思想是基于Darw in的進(jìn)化論和Mendel的遺傳學(xué)說。20世紀(jì)40年代，生物學(xué)家們就試圖用計算機(jī)模擬自然遺傳系統(tǒng)。20世紀(jì)50年代，澳大利亞的A.S.Fraser用一個15位的串表示具有三個基因的染色體來研究異位顯性現(xiàn)象，美國芝加哥大學(xué)的J.Holland及其學(xué)生于1965年首次提出了人工遺傳操作的重要性，并且提出了遺傳算法的基本理論——模式定理。此后，遺傳算法的研究引起了國內(nèi)外學(xué)者的關(guān)注。1975年，Holland出版了專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》，比較系統(tǒng)地闡述了GA的基本理論和方法，為遺傳算法奠定了理論基礎(chǔ)。他的學(xué)生J.D.Bagley在論文中首次使用“遺傳算法”這一名稱。他發(fā)展了選擇、交叉、變異等遺傳操作，并對染色體選擇進(jìn)行了詳細(xì)的研究，提出了適應(yīng)度定標(biāo)（scaling）的概念和算法自我調(diào)整的思想，以防止“早熟”收斂。自1985年以來.國際上已召開了多次遺傳算法的學(xué)術(shù)會議和研討會.國際遺傳算法學(xué)會組織召開的ICGA會議和FOGA會議。為研究和應(yīng)用遺傳算法提供了國際交流的機(jī)會。遺傳算法是依據(jù)達(dá)爾文的自然進(jìn)化論與孟德爾的遺傳變異理論，經(jīng)過選擇一定數(shù)量的個體進(jìn)行雜交以遺傳算法及基因突變，按照適者生存和優(yōu)勝劣汰的原理，把優(yōu)秀的基因傳給后代，淘汰不良基因，逐代演化最終得到最佳的一個或幾個后代，即問題的最優(yōu)解。

目前有關(guān)遺傳算法的研究主要集中在以下幾方面：（1）算法的數(shù)學(xué)基礎(chǔ)。（2）算法的改進(jìn)與深化。（3）算法策略研究與設(shè)計。（4）算法的并行研究。D.Goldberg在其博士論文中第一次將GA應(yīng)用于實際的工程問題--管道煤氣系統(tǒng)的優(yōu)化中，并且較好地解決了這一問題。對于組合優(yōu)化問題，目前遺傳算法己在具有NP難度的各種問題，已被成功地應(yīng)用于下業(yè)、經(jīng)濟(jì)答理、交通運(yùn)輸、工業(yè)設(shè)計等不同領(lǐng)域.解決了許多問題。包括求解旅行商問題、裝箱問題、圖像處理、圖形劃分、機(jī)器調(diào)度、布局優(yōu)化問題等得到成功的應(yīng)用。在解決燃?xì)夤芫W(wǎng)優(yōu)化布局問題方面存在著很大的潛力，近年來應(yīng)用遺傳算法進(jìn)行燃?xì)夤芫W(wǎng)布局優(yōu)化的設(shè)計，已取得了一些成果。

遺傳算法在燃?xì)夤芫W(wǎng)的優(yōu)化問題中可以從以下幾個方面進(jìn)行研究和應(yīng)用：（1）在燃?xì)夤芫W(wǎng)的遺傳優(yōu)化算法中，如何克服線性規(guī)劃、廣義簡約梯度法等傳統(tǒng)方法所存在的計算量大、應(yīng)用范圍窄等問題，較大地發(fā)揮遺傳算法所具有的簡單、搜索效率高等優(yōu)勢，借鑒應(yīng)用于各種網(wǎng)（給水管網(wǎng)等）的優(yōu)化問題的方法，建立適合燃?xì)夤芫W(wǎng)優(yōu)化的數(shù)學(xué)模型，并進(jìn)行優(yōu)化求解。（2）遺傳算法本身也有許多不足，如易陷人早熟，可以嘗試著把它與其他智能優(yōu)化算法有機(jī)地結(jié)合起來，形成混合遺傳算法，克服其不足，使其在組合優(yōu)化問題中的搜索效率更高，應(yīng)用更廣泛。

遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化的應(yīng)用主要以下幾個方面：（1）遺傳算法在燃?xì)夤芫W(wǎng)水力計算的應(yīng)用（2）遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化設(shè)計的應(yīng)用（3）遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化調(diào)度的應(yīng)用其中在優(yōu)化設(shè)計中還包括管徑優(yōu)化和布局優(yōu)化，前者為了得到管網(wǎng)的最低造價，對管徑進(jìn)行組合優(yōu)化設(shè)計，后者主要以枝狀形的燃?xì)夤芫W(wǎng)為研究對象，對燃?xì)夤芫W(wǎng)布局進(jìn)行優(yōu)化設(shè)計，在將多種可行路徑構(gòu)成燃?xì)夤芫W(wǎng)布局優(yōu)化設(shè)計的尋優(yōu)域中求解出最佳管網(wǎng)布局形式。

參考文獻(xiàn)

[1]李悅敏，李興泉，趙自軍等.遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化的應(yīng)用進(jìn)展[J].煤氣與熱力，2008，28（6）：12-15.

[2]王煊，段常貴.改進(jìn)遺傳算法在燃?xì)夤芫W(wǎng)布局優(yōu)化中的應(yīng)用[J].哈爾濱工業(yè)大學(xué)學(xué)報，2006，38（1）：46-48.

[3]呂木英.基于遺傳算法的城市燃?xì)夤芫W(wǎng)最優(yōu)化布局研究[D].武漢：武漢理工大學(xué)，2009-5.