Jansen, Thomas and Zarges, Christine (2012) Computing longest common subsequences with the B-cell algorithm. Lecture Notes in Computer Science, Vol.7597 . pp. 111-124. doi:10.1007/978-3-642-33757-4_9

Research output not available from this repository, contact author.

Request Changes to record.

Abstract

Computing a longest common subsequence of a number of strings is a classical combinatorial optimisation problem with many applications in computer science and bioinformatics. It is a hard problem in the general case so that the use of heuristics is motivated. Evolutionary algorithms have been reported to be successful heuristics in practice but a theoretical analysis has proven that a large class of evolutionary algorithms using mutation and crossover fail to solve and even approximate the problem efficiently. This was done using hard instances. We reconsider the very same hard instances and prove that the B-cell algorithm outperforms these evolutionary algorithms by far. The advantage stems from the use of contiguous hypermutations. The result is another demonstration that relatively simple artificial immune systems can excel over more complex evolutionary algorithms in the domain of optimisation.

Item Type:	Journal Article
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISSN:	0302-9743
Book Title:	Artificial Immune Systems
Official Date:	2012
Dates:	Date Event 2012 Published
Volume:	Vol.7597
Page Range:	pp. 111-124
DOI:	10.1007/978-3-642-33757-4_9
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item