基于拓扑感知的TSP快速求解算法

发布时间：2018-03-26 05:46

  本文选题：拓扑　切入点：TSP　出处：《东南大学学报(自然科学版)》2014年03期

【摘要】：为了适应无线传感器网络环境的特点,提出了一种基于拓扑感知的旅行商问题(TSP)启发式快速求解算法.通过分析无线传感器网络拓扑与TSP解之间的关系,提出了基于最大公共同构子图的拓扑距离,并用于度量拓扑之间的相似度.然后,以拓扑距离为标准,对输入拓扑进行聚类分析,继而映射得出该输入拓扑的TSP解.该算法设置了合适的剪枝条件以提高运行速度,通过加入阈值参数来平衡类内拓扑间的相似度和聚类类别数目.仿真结果表明,在节点数为90和70的TSP环境下,这种拓扑感知算法的运行时间分别为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.
【作者单位】： 东南大学计算机科学与工程学院;东南大学网络和信息集成教育部重点实验室;
【分类号】：TP212.9;TN929.5

【共引文献】

相关期刊论文 前10条

1 张森;;改进蚁群算法求解最短路径问题[J];电子世界;2013年16期

2 廖翊丞;唐秋玲;岳岫峪;李贤;郑莉莉;;一种基于能量受限的移动sink数据收集策略[J];广西大学学报(自然科学版);2013年05期

3 刘双;陈国雄;刘天佑;;改进的蚁群算法及其在南岭地区花岗岩侵入体探测中的应用[J];吉林大学学报(地球科学版);2013年06期

4 孙骞;张进;王宇翔;;蚁群算法优化策略综述[J];信息安全与技术;2014年02期

5 刘钊;罗智德;张耀方;高培超;谢美慧;;基于GIS的时空节点规划与优化方法研究[J];地理与地理信息科学;2014年01期

6 刘海滨;刘国华;黄立明;宋金玲;;以业务单据为中心的业务流程模型聚类及相似性查询方法[J];计算机集成制造系统;2013年08期

7 史岚;张义宏;吕建辉;;基于绝对贪心和预期效率的0-1背包问题优化[J];计算机应用研究;2014年03期

8 伍尚昆;陈翠宜;祝胜林;;基于多种群蚁群算法的交叉路口信号配时优化[J];计算机应用与软件;2014年05期

9 冯禹;;基于改进蚁群算法的定向问题研究[J];物流工程与管理;2013年09期

10 张家善;王志宏;;基于信息素的改进蚁群算法及其在TSP中的应用[J];数学的实践与认识;2013年22期

相关会议论文 前1条

1 王晨;陈增强;;基于连续蚁群算法融合的神经网络RFID信号分布模型[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

相关博士学位论文 前9条

1 刘伟;城乡一体化交通网络配置研究[D];西南交通大学;2012年

2 张汝阳;高维数据交互作用分析的统计方法研究及其在肺癌全基因组关联研究中的应用[D];南京医科大学;2013年

3 寇嘉梁;基于分片网络的体育场人员疏散多目标优化研究[D];武汉理工大学;2013年

4 谭阳;求解广义旅行商问题的若干进化算法研究[D];华南理工大学;2013年

5 阮殿旭;井下工作面设备无线监测网络与故障诊断关键技术研究[D];中国矿业大学;2011年

6 金浩;基于改进蚁群算法梯式轨道及橡胶混凝土隔振基础优化研究[D];北京交通大学;2013年

7 刘宁;高心墙堆石坝施工场内交通仿真与实时控制研究[D];天津大学;2013年

8 李晴;基于优化机器学习算法的模拟电路故障诊断研究[D];湖南大学;2013年

9 王s鮯，

本文编号：1666600