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

ACA-Based Solution of Shortest Common Supersequence Problems

作　　者：陶维安[1] 

机构地区：[1]长江师范学院数学与计算机学院,重庆408100

出　　处：《西南大学学报（自然科学版）》2011年第11期136-139,共4页Journal of Southwest University(Natural Science Edition)

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

摘　　要：提出基于多数融合启发式与向前看策略求解多个字符串最短公共超序列问题的蚁群算法.该算法采用n只蚂蚁相互独立地建立字符串集合R的超序列.每只蚂蚁在完成一次超序列构建后更新R中每个字符上的信息素.字符串中的每一个字符所得到信息素的多少依赖于该蚂蚁构建的超序列的质量、构建解的过程中字符出现的先后顺序以及在一个构建步骤中同一个字符在不同串中出现的次数3个因素.不同实验数据集上的对比测试结果表明该算法能求得更好的解.An ant algorithm is proposed in this paper to solve shortest common supersequence problems based on majority merge heuristic and look-ahead strategies.In this algorithm,n ants are used to independently establish a supersequence of the character string set R,and then update the pheromone of each character in set R,which depends on the quality of the supersequence and the occurrence order and frequency of the character.Experimental results of different test data show that the algorithm can find better solution than other algorithms.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]