譚 陽

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院,湖南長沙 410004)

模擬退火算法在結(jié)構(gòu)化布線中的應(yīng)用

譚 陽＊

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院,湖南長沙 410004)

針對在綜合布線工程中水平子系統(tǒng)的布線設(shè)計難以達到最優(yōu)化的缺陷,提出了使用模擬退火算法來計算結(jié)構(gòu)化布線方案,使得總體布線方案基本達到最優(yōu)化。后續(xù)實驗證明該算法在實際運用中是有效的,較傳統(tǒng)布線方法能優(yōu)化 10%以上。

綜合布線;模擬退火算法;最優(yōu)化;算法

一、前言

在信息化時代,隨著計算機和通信技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)互聯(lián)的應(yīng)用已成為一種基本需求,其中建筑的智能化成為網(wǎng)絡(luò)互聯(lián)應(yīng)用中一個重要的研究方向。智能化建筑由建筑自動化系統(tǒng) (BA)、通信自動化系統(tǒng) (CA)和辦公自動化系統(tǒng) (OA)組成,通過信息系統(tǒng)的集成,使得 3A系統(tǒng)的信息得以共享,便可以實現(xiàn)科學(xué)合理地運用建筑物內(nèi)所有的物理和邏輯上的資源。實現(xiàn) 3A系統(tǒng)的基礎(chǔ)是信息通路的建設(shè),建設(shè)計算機信息網(wǎng)絡(luò)成為建設(shè)智能化建筑的核心。然而在結(jié)構(gòu)化布線的設(shè)計當(dāng)中,一般卻難以獲得最優(yōu)化的布線方案,這使得整個信息網(wǎng)絡(luò)實現(xiàn)方案存在著各種浪費和不合理的現(xiàn)象。

模擬退火算法是一種模擬金屬冶煉中冷卻過程的仿真算法。因為其具有求解與問題無關(guān)性、算法過程簡單等優(yōu)點,被廣泛的用于函數(shù)優(yōu)化、路徑尋優(yōu)及最優(yōu)調(diào)度等實際應(yīng)用中;也常用于各種 NP難題的求解上,是一種通用性很好的算法。本文通過在布線設(shè)計過程引入模擬退火算法,克服了傳統(tǒng)方法的缺陷,使布線方案基本達到了最優(yōu)化的目的。

二、基本理論

1、結(jié)構(gòu)化綜合布線及水平子系統(tǒng)

綜合布線系統(tǒng)是一套開放式的布線系統(tǒng),一般劃分為:工作區(qū)子系統(tǒng)、水平子系統(tǒng)、管理子系統(tǒng)、干線子系統(tǒng)、設(shè)備間子系統(tǒng)、建筑群子系統(tǒng)六個子系統(tǒng)。它既能使語音、數(shù)據(jù)、圖像和交換設(shè)備與其它信息管理系統(tǒng)彼此相連,也能使這些設(shè)備與外部信息網(wǎng)絡(luò)相連接。但是在 PDS的應(yīng)用中需要充分考慮通信技術(shù)的發(fā)展,設(shè)計時要留有足夠的技術(shù)儲備,能充分滿足用戶的長期需求。所以在設(shè)計結(jié)構(gòu)化綜合布線方案時,必須充分考慮所采用的網(wǎng)絡(luò)技術(shù)及布線結(jié)構(gòu)的優(yōu)化,避免硬件資源的冗余和浪費。布線方案應(yīng)具有高度的靈活性,各種設(shè)備位置的改變,網(wǎng)絡(luò)拓撲結(jié)構(gòu)的調(diào)整,應(yīng)確保盡量不需重新布線,只要在配線間作適當(dāng)?shù)恼{(diào)整便可滿足要求。

水平子系統(tǒng)通常的拓撲結(jié)構(gòu)為星形拓撲,其主要是實現(xiàn)信息插座和管理子系統(tǒng)間的聯(lián)接,并包括了傳輸介質(zhì)與部件集成。選擇水平子系統(tǒng)的聯(lián)接介質(zhì),要根據(jù)建筑物內(nèi)具體信息點的類型、容量、帶寬和傳輸速率來確定。在水平子系統(tǒng)中一般采用超五類或六類非屏蔽的雙絞電纜。其中需要注意的地方為:在水平布線鏈路中,使用雙絞線其永久鏈路長度不能超過 90m,信道長度不能超過 100m。水平子系統(tǒng)線路結(jié)構(gòu)復(fù)雜,其設(shè)計量和工程施工量都是綜合布線工程的重點,亦是本文討論的重點。其他子系統(tǒng)相對來說線路較為單一,并且使用的傳輸介質(zhì)不同 (通常為光纖),本文暫不討論。

2、模擬退火算法

模擬退火算法是由 S.Kirkpatrick,C.D.Gelatt和 M.P.Vecchi于 1983年所提出的,算法具有求得的解與初始值的無關(guān)性,并具有漸近全局最優(yōu)解的收斂性,作為一種通用概率演算法,經(jīng)常用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。算法的基本思想是從一給定解開始的,從鄰域中隨機產(chǎn)生另一個解,接受準則允許目標函數(shù)在有限的范圍內(nèi)變壞,它由一控制參數(shù) t決定,其作用類似于物理過程中的溫度 T,對于控制參數(shù)的每一取值,算法持續(xù)進行“產(chǎn)生新解—判斷—接受或舍棄”的迭代過程,對應(yīng)著固體在某一恒定溫度下趨于熱平衡的過程。經(jīng)過大量的解變換后,可以求得給定控制參數(shù)值時優(yōu)化問題的相對最優(yōu)解。然后減小控制參數(shù)的值,重復(fù)執(zhí)行上述迭代過程。當(dāng)控制參數(shù)逐漸減小并趨于零時,系統(tǒng)亦越來越趨于平衡狀態(tài),最后系統(tǒng)狀態(tài)對應(yīng)于優(yōu)化問題的整體最優(yōu)解,該過程也稱為冷卻過程。

模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟:

由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解,為便于后續(xù)的計算和接受,減少算法耗時,通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法,如對構(gòu)成新解的全部或部分元素進行置換、互換等;

計算與新解所對應(yīng)的目標函數(shù)差,因為目標函數(shù)差僅由變換部分產(chǎn)生,所以目標函數(shù)差的計算一般按增量計算;

判斷新解是否被接受,判斷的依據(jù)是一個接受準則,常用的接受準則是 Metropolis準則,若△t’＜0則接受 S’作為新的當(dāng)前解 S,否則以概率exp(-△t’/T)接受 S’作為新的當(dāng)前解 S;

當(dāng)新解被確定接受時,用新解代替當(dāng)前解,需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn),同時修正目標函數(shù)值。此時,當(dāng)前解實現(xiàn)了一次迭代,可在此基礎(chǔ)上開始下一輪迭代。而當(dāng)新解被判定為舍棄時,則在原有解的基礎(chǔ)上繼續(xù)下一輪迭代。

三、模擬退火算法在布線中的應(yīng)用

在實際操作中,一般為分別對單一樓層進行設(shè)計施工。普通水平結(jié)構(gòu)中會存在 1個或多個交換設(shè)備,并通過這些設(shè)備將同一水平結(jié)構(gòu)中所有的工作子系統(tǒng)進行聯(lián)接;要求所有工作子系統(tǒng)的數(shù)據(jù)都能匯聚,并能到達垂直干線子系統(tǒng)。如何使整個水平子系統(tǒng)的結(jié)構(gòu)最為合理,即工程造價最低化、信息延遲最小化成了設(shè)計中首先要解決的問題。

對問題的描述為:可移動的交換節(jié)點與終端之間的距離的總和,目標要求為距離總和最小化。約束條件為:節(jié)點與終端之間的距離不能大于 90m,之后還需考慮工程上施工的可行性,如:是否有強電的支持及是否為架空等因素。通過對問題的數(shù)學(xué)分析,該問題為一帶約束條件的路徑最優(yōu)化問題。問題本身為 NP難題,目前還沒有常規(guī)方法可以計算出精確解。通常采用“貪婪法”和“分支定界法”來求近似解,但效果并不理想。

為了提高布線問題解的質(zhì)量,應(yīng)用模擬退火算法的流程如下:

步驟 2:若 T＞T0,轉(zhuǎn)步驟 3;否則算法終止,輸出X0;

步驟 3:隨機生成網(wǎng)絡(luò)交換節(jié)點 i和終端 j,令 xiy=0(k=1,2,…,m,k≠j),xiy=1,此時變量記為 X1;

步驟 4:若新方案合理 (不存在 l(xiy)＞90),則計算新的總體布線長度 L1,△E=L1-L0;否則轉(zhuǎn)步驟3;

步驟 5:若△E≤0,則接受新的布線方案 X0←X0,T←αT,轉(zhuǎn)步驟 2;否則,若 exp(-△E/T)＞rand(0,1)時 ,也接受新值 ,X0←X1,T←αT,轉(zhuǎn)步驟 2;否則轉(zhuǎn)步驟 3。

在給定初始值之后,可以根據(jù)實際問題規(guī)模的大小選擇相適應(yīng)的始溫度 T及退火速度α。因為對問題求解的工程目標通常為總體造價最低,在新解生成時應(yīng)注意交換節(jié)點的數(shù)量是可以變化的,所以還要了解多少長度的連接距離和一個交換節(jié)點等價,并考慮多種數(shù)量的交換節(jié)點的設(shè)計方案,并通過實際情況加以選擇。

四、實驗

某小型公司對網(wǎng)絡(luò)建設(shè)要求及基本格局情況如下:

網(wǎng)絡(luò)布局為單一水平結(jié)構(gòu),共計有 31間房間需要聯(lián)通網(wǎng)絡(luò),建筑呈 L形結(jié)構(gòu),如圖 1所示。網(wǎng)絡(luò)要求 100M到桌面,并考慮升級到 1000M的遠期規(guī)劃。需要獨立設(shè)立一個網(wǎng)絡(luò)管理及維護房間,并以此房間為外網(wǎng)接入點?？紤]交換端口的容量及以后可能新增加的終端,并留有部分供維護和替換的端口,采用了 2臺 24口的交換設(shè)備。算法設(shè)定交換節(jié)點為2,網(wǎng)絡(luò)終端接口為 31,起始溫度 T=1000,終止溫度T0=1,退火速度為α=1.0,模擬初始化 X0,計算目標為布線總體長度最小化。計算所使用的設(shè)備為P4-2.4GHz的 CPU,內(nèi)存為 512MB。

比較使用“貪心算法”、“分支定界算法”和“模擬退火算法”3種方法,分別就同一問題進行 10次給定不同的初始狀態(tài)進行求解。表 1為幾種算法計算結(jié)果的比較。

圖1 平面信息點分布情況

表1 幾種算法性能的比較

通過表 1可以看出,在布線設(shè)計中運用了模擬退火算法以后,無論是平均目標出長度還是最優(yōu)目標長度的值都優(yōu)于傳統(tǒng)算法。這說明模擬退火算法在運用于結(jié)構(gòu)化布線設(shè)計后,可以使得布線工程趨于最優(yōu)化,使得工程費用得以降低,避免了在設(shè)計過程中存在的浪費。優(yōu)化率分別達到了 11.83%和12.72%。若此方法用于大型項目優(yōu)化比率還可以進一步提升。

表2 幾種算法耗時的比較

從表 2中可以看出,因為模擬退火算法是基于多重迭代的計算,所以耗時較長;但是就目前大多數(shù)計算設(shè)備的水平而言,增加一點計算時間的消耗,換來 10%以上的資金節(jié)約還是值得的。且模擬退火算法可以十分容易地實現(xiàn)并行化計算,對于大規(guī)模布線應(yīng)用如:校園網(wǎng)布線的整體結(jié)構(gòu)化設(shè)計,其計算時間也能夠控制在可以接受的范圍之內(nèi)。

五、結(jié)論

本文通過對結(jié)構(gòu)化布線中,布線結(jié)構(gòu)難以達到最優(yōu)化的問題,提出應(yīng)用模擬退火算法來解決此問題。通過對實際問題的分析,給出了模擬退火算法對解決結(jié)構(gòu)布線問題的計算模型。并通過實驗驗證了本文方法的可行性和有效性;實驗結(jié)論得出較傳統(tǒng)方法而言,本文方法可以獲得更好的布線設(shè)計方案以及更大的經(jīng)濟效益。

[1]吳達金.綜合布線系統(tǒng)工程設(shè)計標準實施指南 [M].北京:電子工業(yè)出版社,2006.

[2]何志議.智能大廈結(jié)構(gòu)化綜合布線系統(tǒng)設(shè)計方案綜述[J].電氣應(yīng)用,2003(12):39-42.

[3]S.Kirkpatrick,C.D.Gelatt,M.P.Vecchi JrM P.Opt imization by s imulated annealing[J].Science,1983,(220):671-680.

[4]李江濤.智能建筑結(jié)構(gòu)化布線施工圖計算機輔助優(yōu)化設(shè)計研究[D].重慶:重慶大學(xué),2004.

[5]李振濤,王淑玲等.利用遺傳模擬退火算法優(yōu)化神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)[J].計算機工程與應(yīng)用,2007,(36):74-76.

[6]尚曉航,解文彬,馬頌陽.介質(zhì)長度對五類非屏蔽雙絞線電氣性能的影響[J].北京聯(lián)合大學(xué)學(xué)報,2006,(3):64-68.

[7]李陶深,陳松喬等.基于模擬退火遺傳算法的時延控制選播路由算法研究[J].計算機應(yīng)用研究,2007,(12):336-341.

[8]康立山,謝云,尤矢勇,羅祖華.非數(shù)值并行算法 (第一冊)模擬退火算法 [M].北京:科學(xué)出版社,1994.

S imulation Anneal Arithmetic in StructurizedW ir ing Application

TAN Yang

The project for integrated wiring,the Horizontal design difficult to optimize the defect,use of the SAA to calculate the program of structured cabling,wiringmakes the overall program to achieve the best opt imization.The following exper iment proved this algorithm in the actual utilization is effective,compares the traditionalwiringmethod to be able to optimize above 10%.

integrated wiring;simulate anneal arithmetic(SAA);optimization;algorithm

TP301.6

A

1009-5152(2010)01-0050-03

2009-06-12

湖南省自然科學(xué)基金項目(06JJ50107)

譚陽 (1979- ),男,湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院講師,工程師,計算數(shù)學(xué)碩士。