本文選題：拓撲　切入點：TSP　出處：《東南大學(xué)學(xué)報(自然科學(xué)版)》2014年03期

【摘要】：為了適應(yīng)無線傳感器網(wǎng)絡(luò)環(huán)境的特點,提出了一種基于拓撲感知的旅行商問題(TSP)啟發(fā)式快速求解算法.通過分析無線傳感器網(wǎng)絡(luò)拓撲與TSP解之間的關(guān)系,提出了基于最大公共同構(gòu)子圖的拓撲距離,并用于度量拓撲之間的相似度.然后,以拓撲距離為標(biāo)準(zhǔn),對輸入拓撲進行聚類分析,繼而映射得出該輸入拓撲的TSP解.該算法設(shè)置了合適的剪枝條件以提高運行速度,通過加入閾值參數(shù)來平衡類內(nèi)拓撲間的相似度和聚類類別數(shù)目.仿真結(jié)果表明,在節(jié)點數(shù)為90和70的TSP環(huán)境下,這種拓撲感知算法的運行時間分別為0.615和0.508 s,約為Lin-Kernighan算法和蟻群算法的3%~4%,且其精確度介于這兩種算法之間.
[Abstract]:In order to adapt to the characteristics of wireless sensor network (WSN) environment, a fast heuristic algorithm based on topology awareness for traveling salesman problem (TSP) is proposed. The relationship between topology and TSP solution of WSN is analyzed. The topological distance based on the maximum common isomorphism subgraph is proposed and used to measure the similarity between topologies. Then the TSP solution of the input topology is obtained by mapping. The algorithm sets appropriate pruning conditions to improve the running speed, and balances the similarity between the topologies and the number of clustering categories by adding threshold parameters. The simulation results show that, In the TSP environment with 90 and 70 nodes, the operation time of this algorithm is 0.615 s and 0.508 s respectively, which is about 3 / 4 of Lin-Kernighan algorithm and ant colony algorithm, and its accuracy is between these two algorithms.
【作者單位】： 東南大學(xué)計算機科學(xué)與工程學(xué)院;東南大學(xué)網(wǎng)絡(luò)和信息集成教育部重點實驗室;
【分類號】：TP212.9;TN929.5

【共引文獻】

相關(guān)期刊論文 前10條

1 張森;;改進蟻群算法求解最短路徑問題[J];電子世界;2013年16期

2 廖翊丞;唐秋玲;岳岫峪;李賢;鄭莉莉;;一種基于能量受限的移動sink數(shù)據(jù)收集策略[J];廣西大學(xué)學(xué)報(自然科學(xué)版);2013年05期

3 劉雙;陳國雄;劉天佑;;改進的蟻群算法及其在南嶺地區(qū)花崗巖侵入體探測中的應(yīng)用[J];吉林大學(xué)學(xué)報(地球科學(xué)版);2013年06期

4 孫騫;張進;王宇翔;;蟻群算法優(yōu)化策略綜述[J];信息安全與技術(shù);2014年02期

5 劉釗;羅智德;張耀方;高培超;謝美慧;;基于GIS的時空節(jié)點規(guī)劃與優(yōu)化方法研究[J];地理與地理信息科學(xué);2014年01期

6 劉海濱;劉國華;黃立明;宋金玲;;以業(yè)務(wù)單據(jù)為中心的業(yè)務(wù)流程模型聚類及相似性查詢方法[J];計算機集成制造系統(tǒng);2013年08期

7 史嵐;張義宏;呂建輝;;基于絕對貪心和預(yù)期效率的0-1背包問題優(yōu)化[J];計算機應(yīng)用研究;2014年03期

8 伍尚昆;陳翠宜;祝勝林;;基于多種群蟻群算法的交叉路口信號配時優(yōu)化[J];計算機應(yīng)用與軟件;2014年05期

9 馮禹;;基于改進蟻群算法的定向問題研究[J];物流工程與管理;2013年09期

10 張家善;王志宏;;基于信息素的改進蟻群算法及其在TSP中的應(yīng)用[J];數(shù)學(xué)的實踐與認識;2013年22期

相關(guān)會議論文 前1條

1 王晨;陳增強;;基于連續(xù)蟻群算法融合的神經(jīng)網(wǎng)絡(luò)RFID信號分布模型[A];2013年中國智能自動化學(xué)術(shù)會議論文集（第三分冊）[C];2013年

相關(guān)博士學(xué)位論文 前9條

1 劉偉;城鄉(xiāng)一體化交通網(wǎng)絡(luò)配置研究[D];西南交通大學(xué);2012年

2 張汝陽;高維數(shù)據(jù)交互作用分析的統(tǒng)計方法研究及其在肺癌全基因組關(guān)聯(lián)研究中的應(yīng)用[D];南京醫(yī)科大學(xué);2013年

3 寇嘉梁;基于分片網(wǎng)絡(luò)的體育場人員疏散多目標(biāo)優(yōu)化研究[D];武漢理工大學(xué);2013年

4 譚陽;求解廣義旅行商問題的若干進化算法研究[D];華南理工大學(xué);2013年

5 阮殿旭;井下工作面設(shè)備無線監(jiān)測網(wǎng)絡(luò)與故障診斷關(guān)鍵技術(shù)研究[D];中國礦業(yè)大學(xué);2011年

6 金浩;基于改進蟻群算法梯式軌道及橡膠混凝土隔振基礎(chǔ)優(yōu)化研究[D];北京交通大學(xué);2013年

7 劉寧;高心墻堆石壩施工場內(nèi)交通仿真與實時控制研究[D];天津大學(xué);2013年

8 李晴;基于優(yōu)化機器學(xué)習(xí)算法的模擬電路故障診斷研究[D];湖南大學(xué);2013年

9 王s鮯，

本文編號：1666600