List

Bachelor thesis:Evolutionary Algorithm for the Longest Common Subsequence Problem ( PDF )
Author:Pytelová Tereza
Supervisor:Ing. Jiří Kubalík Ph.D.
Keywords:
Abstract:The Longest Common Subsequence Problem is an interesting task in computer science which has many applications namely in data compression or in molecular biology. Used to find similarities through input sequences it can be solved to optimality by means of dynamic programming for two input sequences. However for number of input sequences greater than two it becomes NP hard and dynamic programming is not very efficient as it requires too much time and space. In order to find an approximate solution in reasonable time many algorithms were proposed such as beam search, ant colony optimalization or simmulated annealing. Genetic algorithms represent another metaheuristic suitable for solving discrete optimalizing problems with large search space. Aim of this work is to take an advantages of an iterative optimization algorithm called the Prototype Optimization with Evolved Improvement Steps (POEMS) applying it to the LCSP. It has been shown that POEMS as an iterative algorithm based on genetic algorithm can obtain very good results that is attributed to its ability to search larger neighbourhood than traditional iterative local search algorithm. Nevertheless performance of both proposed algorithms was not as good as was expected. Possible reasons for such underachievement are discussed at the end of this work.
Submited:Jun 2012
More info: