Khaled Saifullah C M, Rafiqul Islam Md
Computer Science and Engineering Discipline, Khulna University, Khulna 9208, Bangladesh.
Computer Science and Engineering Discipline, Khulna University, Khulna 9208, Bangladesh.
Comput Biol Chem. 2016 Oct;64:82-93. doi: 10.1016/j.compbiolchem.2016.05.004. Epub 2016 May 31.
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.
最短公共超序列（SCS）是一个经典的NP难问题，即要构造一个给定字符串集的超序列的字符串。SCS问题在数据压缩、数据库查询优化以及不同的生物信息学活动中有着广泛的应用。由于其NP难特性，精确算法无法为较大规模的实例计算SCS。人们提出了许多启发式和元启发式方法来解决这个问题。在本文中，我们提出了一种基于化学反应优化的元启发式方法CRO_SCS，它是受化学反应的性质启发而设计的。对于不同的优化问题，如0-1背包问题、二次分配问题、全局数值优化问题，CRO算法都表现出了很好的性能。我们重新设计了反应算子和一个新的改进函数来解决SCS问题。将所提出的CRO_SCS算法的结果与增强束搜索（IBS_SCS）、沉积与归约（DR）、蚁群优化（ACO）和人工蜂群（ABC）算法的结果进行了比较。所有相关算法的超序列长度、执行时间和标准差表明，CRO_SCS平均而言比所有其他算法都能给出更好的结果。
