Chemical reaction optimization for solving shortest common supersequence problem.
Shortest common supersequence (SCS) is a classical NP-hard problem, where a string to be constructed that is the supersequence of a given string set. The SCS problem has an enormous application of data compression, query optimization in the database and different bioinformatics activities. Due to NP-hardness, the exact algorithms fail to compute SCS for larger instances. Many heuristics and meta-heuristics approaches were proposed to solve this problem. In this paper, we propose a meta-heuristics approach based on chemical reaction optimization, CRO_SCS that is designed inspired by the nature of the chemical reactions. For different optimization problems like 0-1 knapsack, quadratic assignment, global numeric optimization problems CRO algorithm shows very good performance. We have redesigned the reaction operators and a new reform function to solve the SCS problem. The outcomes of the proposed CRO_SCS algorithm are compared with those of the enhanced beam search (IBS_SCS), deposition and reduction (DR), ant colony optimization (ACO) and artificial bee colony (ABC) algorithms. The length of supersequence, execution time and standard deviation of all related algorithms show that CRO_SCS gives better results on the average than all other algorithms.
Computer Science and Engineering Discipline, Khulna University, Khulna 9208, Bangladesh.
C M
CM
Khaled Saifullah
Computer Science and Engineering Discipline, Khulna University, Khulna 9208, Bangladesh. Electronic address: dmri1978@yahoo.com.
Md
M
Rafiqul Islam
D000465:Algorithms; D000818:Animals; D001000:Ants; D001516:Bees; D019295:Computational Biology; D008962:Models, Theoretical
Algorithm; Chemical reaction optimization; Meta-heuristics; NP-hard problem; Shortest common supersequence