譚 陽(yáng)

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

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

譚 陽(yáng)＊

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

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

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

一、前言

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

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

二、基本理論

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

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

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

2、模擬退火算法

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

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

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

計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差,因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生,所以目標(biāo)函數(shù)差的計(jì)算一般按增量計(jì)算;

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

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

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

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

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

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

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

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

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

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

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

四、實(shí)驗(yàn)

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

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

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

圖1 平面信息點(diǎn)分布情況

表1 幾種算法性能的比較

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

表2 幾種算法耗時(shí)的比較

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

五、結(jié)論

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

[1]吳達(dá)金.綜合布線系統(tǒng)工程設(shè)計(jì)標(biāo)準(zhǔn)實(shí)施指南 [M].北京:電子工業(yè)出版社,2006.

[2]何志議.智能大廈結(jié)構(gòu)化綜合布線系統(tǒng)設(shè)計(jì)方案綜述[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)化布線施工圖計(jì)算機(jī)輔助優(yōu)化設(shè)計(jì)研究[D].重慶:重慶大學(xué),2004.

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

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

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

[8]康立山,謝云,尤矢勇,羅祖華.非數(shù)值并行算法 (第一冊(cè))模擬退火算法 [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é)基金項(xiàng)目(06JJ50107)

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