The Library
Computing longest common subsequences with the B-cell algorithm
Tools
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 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-33757-4_9
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, Engineering and Medicine > 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: |
|
||||
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 |