Chemical reaction optimization for solving shortest common supersequence problem

• The paper propose a widely used nature inspired meta-heuristic algorithm named as chemical reaction optimization (CRO_SCS) algorithm to solve a well-known NP-hard combinatorial problem shortest common supersequence (SCS).
• Four basic reaction operators are used for exploring solution space and Reform function is used for checking the constraints of newly formed supersequence and repairing them if any violation occurs.
• Average length of returned supersequence, average execution time and average standard deviation of proposed CRO_SCS algorithm are compared with enhanced beam search (IBS_SCS), ant colony optimization (ACO), deposition and reduction (DR) and artificial bee colony (ABC) algorithms.
• Out of 26 instances of random and real datasets, in 24 cases CRO_SCS algorithm shows better result in average length of returned supersequence than all other algorithms.
• In case of average execution time, CRO_SCS has better result in 9 cases and ABC algorithm shows better result in 17 cases although ABC algorithm cannot ensure supersequence properties.
• Besides, in case of average standard deviation CRO_SCS shows better results than all other nondeterministic algorithms.

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.

Figure optionsDownload as PowerPoint slide