Phylogenetic tree constructing algorithm based on TSP

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (24): 39-42.

• 研究、探讨 • Previous Articles Next Articles

Phylogenetic tree constructing algorithm based on TSP

ZHANG Hongbin1，GUO Jing1，WANG Chao1，CHEN 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

Received:1900-01-01 Revised:1900-01-01 Online:2011-08-21 Published:2011-08-21

基于TSP的构建系统发生树的蚁群算法

张宏彬1，郭静1，王超1，陈崚2，3

1.扬州工业职业技术学院电子信息工程系，江苏扬州 225127
2.扬州大学信息工程学院，江苏扬州 225009
3.南京大学软件新技术国家重点实验室，南京 210093

Abstract

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.

Key words: phylogenetic trees, Traveling Salesman Problem（TSP）, ant colony algorithm, traverse

摘要： 受TSP问题的启发，提出一种基于TSP构建系统发生树的蚁群算法（TSP-PTC）。该算法将物种集合用一个带权图G表示，并利用蚁群算法在图中搜索一条最优路径，最终系统发生树用最优路径及距离矩阵构建而成。用该方法构建出来的系统发生树是一棵带权树，它不仅可以表示物种之间的进化关系，而且可以粗略地表示出物种之间的进化时间。

关键词: 系统发生树, 旅行商问题（TSP）, 蚁群算法, 遍历

ZHANG Hongbin1，GUO Jing1，WANG Chao1，CHEN Ling2，3. Phylogenetic tree constructing algorithm based on TSP[J]. Computer Engineering and Applications, 2011, 47(24): 39-42.

张宏彬1，郭静1，王超1，陈崚2，3. 基于TSP的构建系统发生树的蚁群算法[J]. 计算机工程与应用, 2011, 47(24): 39-42.

[1]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[2]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[3]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[4]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[5]	WANG Xiaoguang, YANG Peibei. Design and Effect Analysis of Digital Transformation of Shipping Logistics Enterprises [J]. Computer Engineering and Applications, 2021, 57(21): 241-247.
[6]	ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan. Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search [J]. Computer Engineering and Applications, 2021, 57(21): 270-277.
[7]	LI Erchao, QI Kuankuan. Improved Bidirectional Ant Colony Algorithm Mobile Robot Path Planning [J]. Computer Engineering and Applications, 2021, 57(18): 281-288.
[8]	FU Zhaohui, LIU Changshi. Research on Multi-depot Vehicle Routing Problem Based on Joint Distribution Mode [J]. Computer Engineering and Applications, 2021, 57(16): 291-298.
[9]	ZHANG Suying, GUO Baoliang, CHEN Lingzhi, LIU Huixian. Path Planning of Intelligent Fire Evacuation Map Based on Bidirectional Ant Colony Algorithm [J]. Computer Engineering and Applications, 2021, 57(14): 259-266.
[10]	FU Zhaohui, LIU Changshi. Research on Open Time-Dependent Vehicle Routing Problem of Fresh Food E-commerce Distribution [J]. Computer Engineering and Applications, 2021, 57(1): 271-278.
[11]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Survey on Application of Ant Colony Algorithm in Path Planning of Mobile Robot [J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
[12]	CHEN Xi, GAO Junwei, GUAN Sheng. Path Planning for Wave Glider Based on Artificial Pathfinder Ant [J]. Computer Engineering and Applications, 2020, 56(4): 241-246.
[13]	XU Chuanglai, HU Jiankun, HUANG Youfang. Robust Optimization of Express Delivery Network with Uncertain Demand [J]. Computer Engineering and Applications, 2020, 56(3): 272-278.
[14]	ZHANG Xiaoli, YANG Yaxin, XIE Yongcheng. Application of Improved Ant Colony Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(2): 29-34.
[15]	SONG Fangzhen, XU Yanyan, TANG Xin, PAN Shaoming. Emergency Communication Network Routing Protocol Based on Improved Ant Colony Algorithm [J]. Computer Engineering and Applications, 2020, 56(18): 90-96.

Phylogenetic tree constructing algorithm based on TSP

基于TSP的构建系统发生树的蚁群算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics