Solving shortest common supersequence problem using chemical reaction optimization

摘要

The Shortest Common Supersequence problem is an NP-hard optimization problem that has a vast use in real world problems. It is used in data compression and different bio-informatics analysis. Different types of approaches were used to solve this problem. Exact algorithms failed to compute for large instances whereas approximation algorithms lack optimality. In this paper, we propose a meta-heuristic approach named as Chemical Reaction Optimization Algorithm (CRO-SCS) to solve the Shortest Common Supersequence (SCS) Problem. The experimental results demonstrate that our proposed method takes less time to find SCS than dynamic programming and have better performance than other well-known approximation algorithms.