資源描述:
《基于模擬植物生長算法的構(gòu)造通訊網(wǎng)絡(luò)Steiner最優(yōu)樹方法.pdf》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、上海理工大學(xué)學(xué)報第32卷第1期J.UniversityofShanghaiforScienceandTechnologyVo1.32No.12010文章編號:1007—6735(2010)01—0088—04基于模擬植物生長算法的構(gòu)造通訊網(wǎng)絡(luò)Steiner最優(yōu)樹方法丁雪楓’馬良,丁雪松。(1.上海理工大學(xué)管理學(xué)院,上海200093;2.吉林大學(xué)商學(xué)院,長春130000)摘要:通訊網(wǎng)絡(luò)作為現(xiàn)代社會信息系統(tǒng)不可或缺的重要樞紐,其設(shè)計問題直接影響總消耗成本的高低.本文提出了基于模擬植物生長算法求解通信網(wǎng)絡(luò)設(shè)計問題的
2、新方法.對于給定原始通訊節(jié)點的通訊網(wǎng)絡(luò),利用模擬植物生長算法來構(gòu)造網(wǎng)絡(luò)的Steiner最優(yōu)樹使得網(wǎng)絡(luò)總布線耗費達到最?。ㄟ^對實例計算,結(jié)果表明,本算法不僅可獲得問題的最優(yōu)解,計算所需時間也有減少,明顯優(yōu)于其他方法.關(guān)鍵詞:通訊網(wǎng)絡(luò);Steiner最優(yōu)樹;模擬植物生長算法中圖分類號:N945.15文獻標志碼:AMethodofconstructingSteinerminimaltreeforcommunicationnetworkbasedonplantgrowthsimuUlatilonalgo,rmith
3、mDINGXuo-feng,MALiang,DINGXue-so~(1.BusinessSchool,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China;2.BusinessSchol,JilinUniversity,Changchun130000,China)Abstract:Asthemostimportanthingeofmodernsocietyinformationsystem,thedesignofcom—municat
4、ionnetworkdirectlyinfluencestheentireconsumingcost.Anewmethod-plantgrowthsim-ulationalgorithmwasproposedtosolvethedesignproblem.Foragivenoriginalcommunicationnetwork,aSteinerminimaltreewasconstructed,SOthattheWholenetworkconsumingcostcanreachminimum.Then。ex
5、perimentaltestsonrealinstanceswerecarriedout.Theresultsshowthatthealgorithmproposedissuperiortoothers.ItcanfindtheoptimumoftheSteinerpointlocations,andbequickerincalculationthanotheralgorithms.Keywords:communicationnetwork;Steinerminimaltree;plantgrowthsimu
6、lationalgo-rithm收稿日期:2009—04—08基金項目:國家自然科學(xué)基金資助項目(70871081);上海市重點學(xué)科建設(shè)資助項目($30504);上海市研究生創(chuàng)新基金資助項目(JWCXSL0901)作者簡介:丁雪楓(1980一),女,博士研究生.E-mail:dxf80310@sina.corn.工作單位:長春理工大學(xué)計算機學(xué)院長春130022第1期丁雪楓,等:基于模擬植物生長算法的構(gòu)造通訊網(wǎng)絡(luò)Steiner最優(yōu)樹方法89隨著通訊網(wǎng)絡(luò)設(shè)計和應(yīng)用的不斷發(fā)展,有關(guān)其控制和管理算法的設(shè)計已成為很多國
7、內(nèi)外學(xué)者的研2模擬植物生長算法究熱點.其核心問題之一就是通訊網(wǎng)絡(luò)的路由設(shè)計問題.由于有線網(wǎng)絡(luò)的通訊問題與通訊站點個數(shù)、站模擬植物生長算法將植物的整個生長空間模擬點間的相互距離均相關(guān),且通訊的費用隨著線路的為優(yōu)化問題解的可行域,光源模擬為全局最優(yōu)解,根長度而增加,因此設(shè)計使網(wǎng)絡(luò)達到連通,同時整個網(wǎng)據(jù)植物學(xué)中的形態(tài)素濃度理論和植物的向光性動力生長機制,來模擬植物枝干在長滿整個生長空間過絡(luò)線路也達到最短的有線通訊網(wǎng)絡(luò)的布線方案具有程中,在光線強度不同的環(huán)境下以全局最優(yōu)的方式重要的現(xiàn)實意義[1].文獻[1]提出采用模
8、擬退火算法向光源快速生長動力模型【2。。.來求解通訊網(wǎng)絡(luò)布線設(shè)計問題,該算法與窮舉法相2.1模擬植物生長算法動力機制比,無論在精度、時間上均有不同程度的提高,但該植物的生長過程可描述如下:最初由種子破土優(yōu)化算法的不足在于需要對初始溫度、溫度變化等生長出第一個莖枝,在莖、枝上可以生長出新枝的部因子進行設(shè)置,對于這些參數(shù)的優(yōu)化會直接影響計位稱為生長點,當植物具有大于一個生長點的時候,算速度、收斂性能和尋