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.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide