A Dynamic Algorithm for the Longest Common Subsequence Problem using Ant
  Colony Optimization Technique
  We present a dynamic algorithm for solving the Longest Common Subsequence
Problem using Ant Colony Optimization Technique. The Ant Colony Optimization
Technique has been applied to solve many problems in Optimization Theory,
Machine Learning and Telecommunication Networks etc. In particular, application
of this theory in NP-Hard Problems has a remarkable significance. Given two
strings, the traditional technique for finding Longest Common Subsequence is
based on Dynamic Programming which consists of creating a recurrence relation
and filling a table of size . The proposed algorithm draws analogy with
behavior of ant colonies function and this new computational paradigm is known
as Ant System. It is a viable new approach to Stochastic Combinatorial
Optimization. The main characteristics of this model are positive feedback,
distributed computation, and the use of constructive greedy heuristic. Positive
feedback accounts for rapid discovery of good solutions, distributed
computation avoids premature convergence and greedy heuristic helps find
acceptable solutions in minimum number of stages. We apply the proposed
methodology to Longest Common Subsequence Problem and give the simulation
results. The effectiveness of this approach is demonstrated by efficient
Computational Complexity. To the best of our knowledge, this is the first Ant
Colony Optimization Algorithm for Longest Common Subsequence Problem.
