School of Information and Engineering, East China University of Science and Technology, Shanghai, China.
School of Information and Engineering, East China University of Science and Technology, Shanghai, China.
Comput Biol Chem. 2020 Oct;88:107327. doi: 10.1016/j.compbiolchem.2020.107327. Epub 2020 Jul 3.
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 algorithms 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.
最短公共超序列（SCS）问题是一个经典的 NP 难问题，通常通过启发式算法来解决。受自然界化学反应过程启发的一种重要启发式算法是化学反应优化（CRO）及其算法，即 CRO_SCS。在本文中，我们提出了一种新颖的 CRO 算法，称为 IMCRO，用于有效地解决 SCS 问题。在 CRO 的四个反应中的两个反应中引入了两个新的操作符：在分解反应中添加了新的循环移位操作符，并在分子间无效碰撞反应中包含了新的两步交叉操作符。实验结果表明，IMCRO 在随机和真实序列上的性能优于著名的启发式算法，如蚁群优化、沉积和减少、增强束搜索和 CRO_SCS。此外，对于 DNA 实例，它优于其基线 CRO_SCS，平均 SCS 长度减少 1.02，最大长度减少高达 2.1。
