基于蚁群算法求解最短公共超序列问题

摘要：

提出基于多数融合启发式与向前看策略求解多个字符串最短公共超序列问题的蚁群算法.该算法采用n只蚂蚁相互独立地建立字符串集合R的超序列.每只蚂蚁在完成一次超序列构建后更新R中每个字符上的信息素.字符串中的每一个字符所得到信息素的多少依赖于该蚂蚁构建的超序列的质量、构建解的过程中字符出现的先后顺序以及在一个构建步骤中同一个字符在不同串中出现的次数3个因素.不同实验数据集上的对比测试结果表明该算法能求得更好的解.

关键词：最短公共超序列、多数融合启发式、向前看策略、蚁群算法

所属期刊栏目：33

分类号：TP301(计算技术、计算机技术)

资助基金：重庆市教委科学技术研究项目KJ091309;涪陵区科委项目FLKJ;2011ABA2043

在线出版日期：2012-04-21（万方平台首次上网日期，不代表论文的发表时间）

页码：136-139