首页 | 本学科首页   官方微博 | 高级检索  
     

基于TSP的构建系统发生树的蚁群算法
引用本文:张宏彬,郭静,王超,陈崚.基于TSP的构建系统发生树的蚁群算法[J].计算机工程与应用,2011,47(24):39-42.
作者姓名:张宏彬  郭静  王超  陈崚
作者单位:1. 扬州工业职业技术学院电子信息工程系,江苏扬州,225127
2. 扬州大学信息工程学院,江苏扬州225009;南京大学软件新技术国家重点实验室,南京210093
基金项目:国家自然科学基金,江苏省自然科学基金,江苏省教育厅自然科学基金
摘    要:受TSP问题的启发,提出一种基于TSP构建系统发生树的蚁群算法(TSP-PTC)。该算法将物种集合用一个带权图G表示,并利用蚁群算法在图中搜索一条最优路径,最终系统发生树用最优路径及距离矩阵构建而成。用该方法构建出来的系统发生树是一棵带权树,它不仅可以表示物种之间的进化关系,而且可以粗略地表示出物种之间的进化时间。

关 键 词:系统发生树  旅行商问题(TSP)  蚁群算法  遍历
修稿时间: 

Phylogenetic tree constructing algorithm based on TSP
ZHANG Hongbin,GUO Jing,WANG Chao,CHEN Ling.Phylogenetic tree constructing algorithm based on TSP[J].Computer Engineering and Applications,2011,47(24):39-42.
Authors:ZHANG Hongbin  GUO Jing  WANG Chao  CHEN Ling
Affiliation:Ling2,3 1.Department of Electronic and Information Engineering,Yangzhou Polytechnic Institute,Yangzhou,Jiangsu 225127,China 2.College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225009,China 3.National Key Lab of Novel Software Tech,Nanjing University,Nanjing 210093,China
Abstract:Given a set of species and their distance matrix,TSP-PTC builds a weighed graph where each Hamilton circuit represents a phylogenetic tree.Among the phylogenetic trees corresponding to all circle paths,the optimal tree with minimum fitness value is the one which is corresponding to the solution of TSP.Artificial ants can be used to search an optimal path in the weighed graph.The optimal tree can be constructed by the optimal path and the distance matrix.
Keywords:phylogenetic trees  Traveling Salesman Problem(TSP)  ant colony algorithm  traverse
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程与应用》浏览原始摘要信息
点击此处可从《计算机工程与应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号