基于模糊最小生成樹的城域通信網(wǎng)絡(luò)優(yōu)化模型

基于模糊最小生成樹的城域通信網(wǎng)絡(luò)優(yōu)化模型

1網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化近年來，隨著計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用的蓬勃發(fā)展，新的網(wǎng)絡(luò)產(chǎn)品和網(wǎng)絡(luò)技術(shù)也得到了應(yīng)用，使計(jì)算機(jī)網(wǎng)絡(luò)的規(guī)?？梢詳U(kuò)大。在現(xiàn)實(shí)生活中，有許多問題類似于建筑工地之間的電話線、管道和建筑物之間的道路。通常，在一些早期的發(fā)展階段，由于技術(shù)和財(cái)力的限制，人們總是從降低成本的角度設(shè)計(jì)網(wǎng)絡(luò)，并嘗試連接不同的城市。這是最短的長度。某省的7個(gè)城市需要架設(shè)通信網(wǎng)絡(luò)系統(tǒng),為連接這7個(gè)城市,每2個(gè)城市之間的距離如表1所示.考慮地理環(huán)境的影響,綜合考慮各城市之間的距離和每公里修建網(wǎng)絡(luò)的費(fèi)用,各城市之間修建網(wǎng)絡(luò)每公里的費(fèi)用可用與10000元之間的比較來估計(jì)(表2).試問如何架設(shè)通信網(wǎng)絡(luò),使總費(fèi)用最小?對于此類網(wǎng)絡(luò)架設(shè)問題,通常采用星型、環(huán)型或總線型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),能夠較好地解決網(wǎng)絡(luò)建設(shè)過程中的連接和通信問題.但僅僅是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)構(gòu)架,往往達(dá)不到建設(shè)費(fèi)用最小的要求.圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)中的一個(gè)經(jīng)典和重要的分支,所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域.因此,在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的優(yōu)化中引入圖論的方法,以獲得實(shí)際應(yīng)用中較理想的網(wǎng)絡(luò)建設(shè)方案.同時(shí),以往對于此類問題的處理,通常都是采用精確數(shù)學(xué)的方法去解決.然而,人們的思維中有許多沒有明確外延的概念,即模糊概念.語言上有許多模糊概念的詞,例如以人的年齡為論域,那么“年青”、“中年”、“老年”都沒有明確的外延.在上述問題中所給出的“相當(dāng)接近”、“可認(rèn)為是”、“差不多是”等詞都是模糊概念,無法用精確數(shù)學(xué)的方法去解決.所以,又引入了模糊數(shù)學(xué),模糊集合是其基本概念之一.2相關(guān)概念和符號的表達(dá)2.1圖論與線性規(guī)劃圖、邊、權(quán)、無向圖、鏈、連通圖、樹、生成樹、最小生成樹的概念及符號表示見文獻(xiàn).圖論方法已經(jīng)成為數(shù)學(xué)模型中重要的數(shù)學(xué)方法,許多數(shù)學(xué)問題如果能夠歸結(jié)為圖論問題,往往能夠迎刃而解,在計(jì)算機(jī)理論以及數(shù)學(xué)的其他分支中有廣泛的應(yīng)用.在管理科學(xué)中,基于圖論的統(tǒng)籌方法也得到廣泛的應(yīng)用.許多圖論問題可以化為線性規(guī)劃問題,不過圖論中的許多特殊算法比利用一般線性規(guī)劃方法有效得多.2.2模糊數(shù)學(xué)的基本方法將被討論的全體對象或范圍叫做論域,常用U,V,E,…,X,Y,…大寫字母表示.將論域中的每個(gè)對象稱為元素,用相應(yīng)的小寫字母u,v,e,…,x,y,…表示.隸屬函數(shù):用解析形式描術(shù)元素屬于集合的程度.設(shè)A是論域X上的集合,記為UA(x)={1當(dāng)x∈A,0當(dāng)x?A.UA(x)={1當(dāng)x∈A,0當(dāng)x?A.集合A的特征函數(shù),也稱為隸屬函數(shù).模糊集:論域X上的模糊集合AˉˉˉAˉ由隸屬函數(shù)U(x)來表征,其中U(x)在實(shí)軸的閉區(qū)間[0,1]上取值,U(x)的值反映了X中的元素x對于AˉˉˉAˉ的隸屬程度.模糊數(shù)學(xué)是研究現(xiàn)實(shí)中許多界限不分明問題的一種數(shù)學(xué)工具,它的主要概念包括模糊集合、隸屬函數(shù)等.模糊集合完全由隸屬函數(shù)所刻劃.接下來用圖論法和模糊集合的方法來解決網(wǎng)絡(luò)架設(shè)問題的數(shù)學(xué)模型.3模糊集合的確定按照圖論法的規(guī)則建立通信網(wǎng)絡(luò)的圖論模型,即以7個(gè)相鄰的城市為圖的頂點(diǎn),兩頂點(diǎn)之間的網(wǎng)絡(luò)線路為圖的邊,其定義如下:G={V,E},V={R1,R2,R3,R4,R5,R6,R7},E={(R1,R2),(R1,R3),(R1,R4),(R1,R5),(R1,R6),(R1,R7),(R2,R3),(R2,R4),(R2,R5),(R2,R6),(R2,R7),(R3,R4),(R3,R5),(R3,R6),(R3,R7),(R4,R5),(R4,R6),(R4,R7),(R5,R6),(R5,R7),(R6,R7)}.由該定義所構(gòu)成的無向連通圖如圖1所示.每條邊的權(quán)w為某2個(gè)頂點(diǎn)之間網(wǎng)絡(luò)建設(shè)的費(fèi)用,如聯(lián)結(jié)頂點(diǎn)R1和R2的邊上的權(quán)值記為w(R1,R2).因此,一個(gè)無向連通圖可以定義為頂點(diǎn)、邊、權(quán)值構(gòu)成的集合,即G={V,E,W}.通過以上定義,可將城市之間的通信網(wǎng)絡(luò)架設(shè)問題轉(zhuǎn)化為以建設(shè)費(fèi)用最省為優(yōu)化目標(biāo),求解最優(yōu)通信網(wǎng)絡(luò)的問題.在建設(shè)費(fèi)用函數(shù)未知的情況下,可先將建設(shè)網(wǎng)絡(luò)的費(fèi)用看作城市之間距離的線性函數(shù),并考慮其他因素(地理、環(huán)境)的影響,先求解城域網(wǎng)絡(luò)的初始布局,即將這些頂點(diǎn)用邊聯(lián)結(jié)起來,用兩頂點(diǎn)間的直線距離與每公里網(wǎng)絡(luò)建設(shè)費(fèi)用的乘積作為邊的權(quán),使總的權(quán)值最小.可用圖論中的求解最小生成樹的方法求解.所以,問題的關(guān)鍵在于如何確定各條邊上的權(quán)值.在前面定義過,權(quán)值等于城市之間距離與每公里網(wǎng)絡(luò)建設(shè)費(fèi)用的乘積.各城市之間的距離是以公里為單位的確定值,可以定義L(Ri,Rj)為兩頂點(diǎn)Ri和Rj之間的距離,在表1中已列出所有具體值.由于考慮到受地理、環(huán)境因素的影響,相同距離、不同地段的建設(shè)費(fèi)用存在差別,而表2中只列出了各地段每公里建設(shè)費(fèi)用與10000元之間的比較關(guān)系,因此,引入模糊集合來表示這種界限不分明的情況.前面提到過,模糊集合完全由隸屬函數(shù)所刻劃,隸屬函數(shù)及其確定是模糊數(shù)學(xué)中最重要、最基本的量.在實(shí)際應(yīng)用中,它的確定方法主要有模糊統(tǒng)計(jì)法、德爾菲法、對比排序法、綜合加權(quán)法等等,當(dāng)然也可以直接使用常見的規(guī)則的隸屬度函數(shù),但必須知道變量的確定量度和意義.按照表2所列出的各種比較關(guān)系,根據(jù)語義規(guī)則,可以得到一個(gè)程度集合(完全是、可認(rèn)為是、差不多是、非常接近、十分接近、相當(dāng)接近、很接近、比較接近、大致接近).根據(jù)相對于10000元的各種比較關(guān)系,分3種情況討論每公里網(wǎng)絡(luò)建設(shè)的實(shí)際費(fèi)用:(1)10000元是最大值;(2)10000元是最小值;(3)10000元是一個(gè)中間值.由于問題要求求解最小費(fèi)用,因此可以暫且只考慮以10000元為每公里網(wǎng)絡(luò)建設(shè)費(fèi)用的最大值,這樣使得總花費(fèi)最小.于是給定程度集合的一個(gè)加權(quán)因子P=[1,0.95,0.9,0.85,0.8,0.75,0.7,0.65,0.6],這些因子與10000的乘積,可用于計(jì)算每公里網(wǎng)絡(luò)建設(shè)費(fèi)用的近似值.在表3中給出程度集合的符號表示以及按語義規(guī)則所分配的值.通過上述定義,可以進(jìn)一步描述圖1中聯(lián)接每對頂點(diǎn)的邊的權(quán)值w(vi,vj)=L(vi,vj)·Cn·M,(1)其中M為常數(shù)10000.為計(jì)算每條邊的權(quán)值,參照表1至表3得到2個(gè)矩陣,其對應(yīng)位置上分別列出L(vi,vj)和Cn的值:??????????41011581084326965510107955?????????????????????0.60.950.7510.650.90.850.80.9510.70.90.850.80.60.9510.650.70.850.65??????????(41058610118491010367259555)?(0.60.9510.850.70.950.750.650.80.910.90.950.850.6510.80.70.60.850.65)表4是根據(jù)(1)式計(jì)算得到的任意2個(gè)城市之間網(wǎng)絡(luò)建設(shè)的費(fèi)用.圖論中求無向連通圖G={V,E,W}的最小生成樹法.最小生成樹法將城域網(wǎng)絡(luò)看作無向連通圖,求該圖的最小生成樹,常用經(jīng)典算法有prim算法、Kruskal算法.下面將介紹以Kruskal算法解決上述問題的步驟.4執(zhí)行文件和運(yùn)行結(jié)果4.1賦權(quán)圖g中的邊的排列每次添加權(quán)盡量小的邊,使新的圖無圈,直到生成1棵樹為止,便得最小生成樹.算法步驟如下:(ⅰ)將賦權(quán)圖G中的邊按權(quán)的非減次序排列;(ⅱ)按(ⅰ)排列的次序檢查G中的每一條邊,如果這條邊與已得到的邊不產(chǎn)生圈,就取這一條邊為解的一部分;(ⅲ)若已取到n-1條邊,算法終止,此時(shí)以V為頂點(diǎn)集,以取到的n-1條邊為邊集的圖即為最小生成樹.4.2s1.4.3t4.3賦權(quán)的連通圖G={V,E,W}中m=|E|,n=|V|.S1對E中各邊的權(quán)排序,設(shè)w1≤w2≤…≤wm,wi=w(ei).S2初始化:w←0,T←?,k←1,t←0.S3若t=n-1則轉(zhuǎn)S6,否則轉(zhuǎn)S4.S4若T∪{ek}有圈則k←k+1轉(zhuǎn)S4,否則轉(zhuǎn)S5.S5T←T∪{ek},w←w+wk,t←t+1,k←k+1,轉(zhuǎn)S3.S6輸出T及w,結(jié)束.其中T為最小樹,w為T的權(quán).具體流程圖見圖2.4.3計(jì)算機(jī)上測試按照上述思想,用C語言編寫了Kruskal算法的實(shí)現(xiàn)程序,并在計(jì)算機(jī)上測試.測試結(jié)果與預(yù)期結(jié)果完全一樣,即得到了連結(jié)7個(gè)城市的最小生成樹.程序運(yùn)行后,得到圖1的最小生成樹見圖3.其總權(quán)值為1670,為連接7個(gè)城市的最小權(quán)值.5算法實(shí)現(xiàn)程序模擬對現(xiàn)代城域網(wǎng)絡(luò)架設(shè)問題進(jìn)行了建模分析,基于模糊最小生成樹理論對網(wǎng)絡(luò)初始模型實(shí)施優(yōu)化處理,在現(xiàn)實(shí)界限不分明的情況下,以投資建設(shè)費(fèi)用最省為目標(biāo),獲得了7個(gè)城市間網(wǎng)絡(luò)架設(shè)的最佳方案,并使用C語言編寫了算法實(shí)現(xiàn)程序,得到正確的運(yùn)行結(jié)果.通過分析認(rèn)為,在