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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (24): 39-42.

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

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

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

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-08-21 发布日期:2011-08-21

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

摘要/Abstract

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

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

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

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

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]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[4]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[5]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[6]	李壮阔，常凯旋. 合作博弈的连续蚁群算法求解[J]. 计算机工程与应用, 2021, 57(24): 198-204.
[7]	王晓光，杨培蓓. 航运物流企业数字化转型设计与效果分析[J]. 计算机工程与应用, 2021, 57(21): 241-247.
[8]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[9]	李二超，齐款款. 改进双向蚁群算法的移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(18): 281-288.
[10]	何雅颖，范昕炜. 改进蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2021, 57(16): 276-282.
[11]	付朝晖，刘长石. 多物流中心共同配送的车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(16): 291-298.
[12]	张苏英，郭宝樑，陈灵芝，刘慧贤. 双向蚁群算法的智能消防疏散图路径规划[J]. 计算机工程与应用, 2021, 57(14): 259-266.
[13]	付朝晖，刘长石. 生鲜电商配送的开放式时变车辆路径问题研究[J]. 计算机工程与应用, 2021, 57(1): 271-278.
[14]	胡春阳，姜平，周根荣. 改进蚁群算法在AGV路径规划中的应用[J]. 计算机工程与应用, 2020, 56(8): 270-278.
[15]	张松灿，普杰信，司彦娜，孙力帆. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用, 2020, 56(8): 10-19.