基于遗传算法的系统发生树构建方法

doi:10.3778/j.issn.1002-8331.2009.16.020

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (16): 72-76.DOI: 10.3778/j.issn.1002-8331.2009.16.020

基于遗传算法的系统发生树构建方法

郭静¹,王超¹,陈崚^2,3

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

收稿日期:2009-02-16 修回日期:2009-04-03 出版日期:2009-06-01 发布日期:2009-06-01
通讯作者: 郭静

Phylogenetic tree constructing algorithm based on genetic algorithm

GUO Jing¹,WANG Chao¹,CHEN Ling^2,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 Technology，Nanjing University，Nanjing 210093，China

Received:2009-02-16 Revised:2009-04-03 Online:2009-06-01 Published:2009-06-01
Contact: GUO Jing

摘要/Abstract

摘要： 提出了一种基于遗传算法的系统发生树构建方法。将遗传算法应用于系统发生树的构建，首先，用后缀表示法将树的拓扑结构表示成编码的形式。其次，针对系统发生树的性质，设计了交叉和变异操作方法，确定了对个体的评价及选择策略，从而通过遗传操作，最终搜索到最优解。实验结果表明该算法可以得到与传统UPGMA算法拓扑结果一致的系统发生树，并且除了最优拓扑结构的树之外，该算法还可以输入多个具有相似质量的树。

关键词: 遗传算法, 系统发生树, 后缀表示

Abstract: A method for Phylogenetic Tree Construction based on Genetic Algorithm（GA-PTC） is presented.GA-PTC first encodes the possible tree topologies into the solution space of the problem，and then searches for the optimal tree in the searching space.To coding the solutions，this paper proposes a suffix representation as the encoding strategy of genetic algorithm.To evaluate quality of the individual，this paper adopts a distance based fitness function to score solution，and selects parts of individuals according to a selection strategy called roulette wheel where the select probability is proportional to the fitness value. Experimental results show that GA-PTC can obtain higher accuracy results than UPGMA.

Key words: genetic algorithm, phylogenetic tree, suffix representation

郭静¹,王超¹,陈崚^2,3. 基于遗传算法的系统发生树构建方法[J]. 计算机工程与应用, 2009, 45(16): 72-76.

GUO Jing¹,WANG Chao¹,CHEN Ling^2,3. Phylogenetic tree constructing algorithm based on genetic algorithm[J]. Computer Engineering and Applications, 2009, 45(16): 72-76.

[1]	李昱奇，刘志乾，程凝怡，王莹莹，朱春丽. 多约束条件下无人机航迹规划[J]. 计算机工程与应用, 2021, 57(4): 225-230.
[2]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[3]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[4]	杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.
[5]	曹立佳，刘洋. 制造车间自动导引车调度新进展[J]. 计算机工程与应用, 2021, 57(21): 59-67.
[6]	陈倩茹，李雅丽，许科全，刘铱龙，王淑琴. 自调优自适应遗传算法的WKNN特征选择方法[J]. 计算机工程与应用, 2021, 57(20): 164-171.
[7]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[8]	代江涛，韩晓龙. 考虑作业状态能耗的集装箱码头设备协调调度[J]. 计算机工程与应用, 2021, 57(19): 290-298.
[9]	冯晓东，黄世荣，戴冠鸥，杨伟家，罗尧治. 天牛须遗传杂交算法的研究与应用[J]. 计算机工程与应用, 2021, 57(15): 90-100.
[10]	苏庆，林华智，黄剑锋，林志毅. 结合CNN和Catboost算法的恶意安卓应用检测模型[J]. 计算机工程与应用, 2021, 57(15): 140-146.
[11]	姜良重，雷航，李贞昊，钱伟中，施甘图. 采用自适应优化权重的出库货位优化方法研究[J]. 计算机工程与应用, 2021, 57(15): 271-278.
[12]	贺娇，谭代伦. 基于视野范围和遗传算法的三维地形路径规划[J]. 计算机工程与应用, 2021, 57(15): 279-285.
[13]	王秀丽，周鹏，侯静楠，王仕俊，林霞. 面向变电站机器人巡检路径规划中的算法研究[J]. 计算机工程与应用, 2021, 57(14): 245-250.
[14]	陈元文. MapReduce技术在物资调运与配载问题中的应用[J]. 计算机工程与应用, 2021, 57(12): 273-278.
[15]	邱云飞，高华聪. 混合Filter与改进自适应GA的特征选择方法[J]. 计算机工程与应用, 2021, 57(11): 95-102.

基于遗传算法的系统发生树构建方法

Phylogenetic tree constructing algorithm based on genetic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics