文献类型：期刊文献

英文题名：An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence Problem

作者：Luo, Fei[1];Chen, Cheng[1];Fuentes, Joel[2];Li, Yong[1];Ding, Weichao[1]

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

年份：2022

卷号：24

期号：5

外文期刊名：ENTROPY

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000801395300001)】；

基金：This research was funded by the project on the Shanghai Action Plan of Technological Innovation (20DZ1201400, 22ZR1416500) and sponsored by Shanghai Sailing Program (20YF1410900).

语种：英文

外文关键词：chemical reaction optimization; opposition-based learning; shortest common supersequence; heuristic algorithm; NP-hard

摘要：As a non-deterministic polynomial hard (NP-hard) problem, the shortest common supersequence (SCS) problem is normally solved by heuristic or metaheuristic algorithms. One type of metaheuristic algorithms that has relatively good performance for solving SCS problems is the chemical reaction optimization (CRO) algorithm. Several CRO-based proposals exist; however, they face such problems as unstable molecular population quality, uneven distribution, and local optimum (premature) solutions. To overcome these problems, we propose a new approach for the search mechanism of CRO-based algorithms. It combines the opposition-based learning (OBL) mechanism with the previously studied improved chemical reaction optimization (IMCRO) algorithm. This upgraded version is dubbed OBLIMCRO. In its initialization phase, the opposite population is constructed from a random population based on OBL; then, the initial population is generated by selecting molecules with the lowest potential energy from the random and opposite populations. In the iterative phase, reaction operators create new molecules, where the final population update is performed. Experiments show that the average running time of OBLIMCRO is more than 50% less than the average running time of CRO_SCS and its baseline algorithm, IMCRO, for the desoxyribonucleic acid (DNA) and protein datasets.