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

摘要

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