A genetic algorithm for the longest common subsequence problem

被引：0

作者：

Hinkemeyer, Brenda ^{[1
]}

Julstrorn, Bryant A. ^{[1
]}

机构：

[1] St Cloud State Univ, Dept Comp Sci, St Cloud, MN 56301 USA

来源：

GECCO 2006: GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, VOL 1 AND 2 | 2006年

关键词：

strings; longest common subsequence; genetic algorithm;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A genetic algorithm for the longest common subsequence problem encodes candidate sequences as binary strings that indicate subsequences of the shortest or first string. Its fitness function penalizes sequences not found in all the strings. In tests on 84 sets of three strings, a dynamic programming algorithm returns optimum solutions quickly on smaller instances and increasingly slowly on larger instances. Repeated trials of the GA always identify optimum subsequences, and it runs in reasonable times even on the largest instances.

引用

页码：609 / +

页数：2