文献类型：期刊文献

英文题名：An improved chemical reaction optimization algorithm for solving the shortest common supersequence problem

作者：Luo, Fei[1];Chen, Cheng[1];Fuentes, Joel[2]

机构：[1]East China Univ Sci & Technol, Sch Informat & Engn, Shanghai, Peoples R China;[2]Univ Bio Bio, Dept Comp Sci & Informat Technol, Chillan, Chile

年份：2020

卷号：88

外文期刊名：COMPUTATIONAL BIOLOGY AND CHEMISTRY

收录：;EI(收录号：20202908950605);WOS:【SCI-EXPANDED(收录号:WOS:000591245400001)】；

基金：This work is partially supported by the project on Educational Teaching Law and Method of East China University of Technology, the Online Education Fund (pervasive education) of Online Education Research Center in Chinese Ministry of Education (No. 2017YB122), and the National Natural Science Foundation of China (NSFC) (No. 61472139).

语种：英文

外文关键词：Chemical reaction optimization; Shortest common supersequence; Heuristic algorithm; NP-hard

摘要：The shortest common supersequence (SCS) problem is a classical NP-hard problem, which is normally solved by heuristic algorithms. One important heuristic that is inspired by the process of chemical reactions in nature is the chemical reaction optimization (CRO) and its algorithm known as CRO_SCS. In this paper we propose a novel CRO algorithm, dubbed IMCRO, to solve the SCS problem efficiently. Two new operators are introduced in two of the four reactions of the CRO: a new circular shift operator is added to the decomposition reaction, and a new two-step crossover operator is included in the inter-molecular ineffective collision reaction. Experimental results show that IMCRO achieves better performance on random and real sequences than well-known heuristic algo-rithms such as the ant colony optimization, deposition and reduction, enhanced beam search, and CRO_SCS. Additionally, it outperforms its baseline CRO_SCS for DNA instances, averaging a SCS length reduction of 1.02, with a maximum length reduction of up to 2.1.