Title :
Beam-ACO for the longest common subsequence problem
Author_Institution :
ALBCOM Res. Group, Univ. Politec. de Catalunya, Barcelona, Spain
Abstract :
The longest common subsequence problem is classical string problem. It has applications, for example, in pattern recognition and bioinformatics. In this work we present a so-called Beam-ACO approach for solving this problem. Beam-ACO algorithms are hybrid techniques that results from a combination of ant colony optimization and beam search, which is an incomplete branch and bound derivative. Our results show that Beam-ACO is able to find new best solutions for 31 out of 60 benchmark instances that we chose for the experimental evaluation of the algorithm.
Keywords :
optimisation; search problems; ant colony optimization; beam search; beam-ACO; classical string problem; longest common subsequence problem; Ant colony optimization; Convergence; Probabilistic logic; Search problems; Structural beams; Tuning; Upper bound;
Conference_Titel :
Evolutionary Computation (CEC), 2010 IEEE Congress on
Conference_Location :
Barcelona
Print_ISBN :
978-1-4244-6909-3
DOI :
10.1109/CEC.2010.5585928