淺析優(yōu)化設(shè)計(jì)燃?xì)夤芫W(wǎng)的布局

趙昆

摘 要：本文旨在應(yīng)用GA建立燃?xì)夤芫W(wǎng)的布局設(shè)計(jì)模型，實(shí)現(xiàn)以應(yīng)用軟件平臺(tái)為基礎(chǔ)的計(jì)算機(jī)優(yōu)化設(shè)計(jì)。主要工作包括：首先，在閱讀了大量文獻(xiàn)的基礎(chǔ)上，本文指出了燃?xì)夤芫W(wǎng)布局優(yōu)化在現(xiàn)實(shí)工作中的重要意義，論述了遺傳算法在燃?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è)計(jì)了遺傳算法。并在MAPINFO平臺(tái)上實(shí)現(xiàn)了燃?xì)夤芫W(wǎng)連接布局系統(tǒng)。最后給出進(jìn)一步的研究方向。

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

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

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

目前有關(guān)遺傳算法的研究主要集中在以下幾方面：（1）算法的數(shù)學(xué)基礎(chǔ)。（2）算法的改進(jìn)與深化。（3）算法策略研究與設(shè)計(jì)。（4）算法的并行研究。D.Goldberg在其博士論文中第一次將GA應(yīng)用于實(shí)際的工程問題--管道煤氣系統(tǒng)的優(yōu)化中，并且較好地解決了這一問題。對(duì)于組合優(yōu)化問題，目前遺傳算法己在具有NP難度的各種問題，已被成功地應(yīng)用于下業(yè)、經(jīng)濟(jì)答理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(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è)計(jì)，已取得了一些成果。

遺傳算法在燃?xì)夤芫W(wǎng)的優(yōu)化問題中可以從以下幾個(gè)方面進(jìn)行研究和應(yīng)用：（1）在燃?xì)夤芫W(wǎng)的遺傳優(yōu)化算法中，如何克服線性規(guī)劃、廣義簡(jiǎn)約梯度法等傳統(tǒng)方法所存在的計(jì)算量大、應(yīng)用范圍窄等問題，較大地發(fā)揮遺傳算法所具有的簡(jiǎn)單、搜索效率高等優(yōu)勢(shì)，借鑒應(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)用主要以下幾個(gè)方面：（1）遺傳算法在燃?xì)夤芫W(wǎng)水力計(jì)算的應(yīng)用（2）遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化設(shè)計(jì)的應(yīng)用（3）遺傳算法在燃?xì)夤芫W(wǎng)優(yōu)化調(diào)度的應(yīng)用其中在優(yōu)化設(shè)計(jì)中還包括管徑優(yōu)化和布局優(yōu)化，前者為了得到管網(wǎng)的最低造價(jià)，對(duì)管徑進(jìn)行組合優(yōu)化設(shè)計(jì)，后者主要以枝狀形的燃?xì)夤芫W(wǎng)為研究對(duì)象，對(duì)燃?xì)夤芫W(wǎng)布局進(jìn)行優(yōu)化設(shè)計(jì)，在將多種可行路徑構(gòu)成燃?xì)夤芫W(wǎng)布局優(yōu)化設(shè)計(jì)的尋優(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é)報(bào)，2006，38（1）：46-48.

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