{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T02:09:54Z","timestamp":1762049394526,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T00:00:00Z","timestamp":1651536000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Shanghai Action Plan of Technological Innovation","award":["20DZ1201400","22ZR1416500","20YF1410900"],"award-info":[{"award-number":["20DZ1201400","22ZR1416500","20YF1410900"]}]},{"name":"Shanghai Sailing Program","award":["20DZ1201400","22ZR1416500","20YF1410900"],"award-info":[{"award-number":["20DZ1201400","22ZR1416500","20YF1410900"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/e24050641","type":"journal-article","created":{"date-parts":[[2022,5,3]],"date-time":"2022-05-03T08:26:35Z","timestamp":1651566395000},"page":"641","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence Problem"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7062-4404","authenticated-orcid":false,"given":"Fei","family":"Luo","sequence":"first","affiliation":[{"name":"School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cheng","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0517-1231","authenticated-orcid":false,"given":"Joel","family":"Fuentes","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Technologies, Universidad del B\u00edo-B\u00edo, Chill\u00e1n 3780000, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weichao","family":"Ding","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,5,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","article-title":"The Shortest Common Supersequence Problem over Binary Alphabet is NP-Complete","volume":"16","author":"Ukkonen","year":"1981","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ning, K., Ng, H.K., and Leong, H.W. (2006, January 16\u201318). Finding Patterns in Biological Sequences by Longest Common Subsequencesand Shortest Common Supersequences. Proceedings of the Sixth IEEE Symposium on BioInformatics and BioEngineering (BIBE\u201906), Arlington, VA, USA.","DOI":"10.1109\/BIBE.2006.253315"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Garg, A., and Garg, D. (2014, January 24\u201327). Progressive alignment using Shortest Common Supersequence. Proceedings of the 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Delhi, India.","DOI":"10.1109\/ICACCI.2014.6968310"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/s40009-016-0441-5","article-title":"A Recursive Algorithm for Generalized Constraint SCS Problem","volume":"39","author":"Mangal","year":"2016","journal-title":"Natl. Acad. Sci. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF01075212","article-title":"Complexity of common subsequence and supersequence problems and related problems","volume":"25","author":"Timkovskii","year":"1989","journal-title":"Cybernetics"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0004-3702(92)90016-Q","article-title":"Theory and Algorithms for Plan Merging","volume":"57","author":"Foulser","year":"1992","journal-title":"Artif. Intell."},{"key":"ref_7","first-page":"180","article-title":"Solving Shortest Common Supersequence Problem Using Artificial Bee Colony Algorithm","volume":"2","author":"Jaradat","year":"2011","journal-title":"Int. J. ACM Jordan"},{"key":"ref_8","unstructured":"Rajendran, S., Rajendran, C., and Ziegler, H. (2010). An Ant-Colony Algorithm to Transform Jobshops into Flowshops: A Case of Shortest-Common-Supersequence Stringology Problem. Bio-Inspired Models of Network, Information, and Computing Systems, Proceedings of the 5th International ICST Conference, BIONETICS 2010, Boston, MA, USA, 1\u20133 December 2010, Springer. Revised Selected Papers."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/j.engappai.2011.08.006","article-title":"An enhanced beam search algorithm for the Shortest Common Supersequence Problem","volume":"25","author":"Mousavi","year":"2012","journal-title":"Eng. Appl. AI"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"S12","DOI":"10.1186\/1471-2105-7-S4-S12","article-title":"Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm","volume":"7","author":"Ning","year":"2006","journal-title":"BMC Bioinform."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.compbiolchem.2016.05.004","article-title":"Chemical reaction optimization for solving shortest common supersequence problem","volume":"64","author":"Saifullah","year":"2016","journal-title":"Comput. Biol. Chem."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"107327","DOI":"10.1016\/j.compbiolchem.2020.107327","article-title":"An improved chemical reaction optimization algorithm for solving the shortest common supersequence problem","volume":"88","author":"Luo","year":"2020","journal-title":"Comput. Biol. Chem."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.jesit.2016.12.007","article-title":"Optimal allocation of SVC and TCSC using quasi-oppositional chemical reaction optimization for solving multi-objective ORPD problem","volume":"5","author":"Dutta","year":"2018","journal-title":"J. Electr. Syst. Inf. Technol."},{"key":"ref_14","unstructured":"Tizhoosh, H. (2005, January 28\u201330). Opposition-Based Learning: A New Scheme for Machine Intelligence. Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC\u201906), Vienna, Austria."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","article-title":"The Complexity of Some Problems on Subsequences and Supersequences","volume":"25","author":"Maier","year":"1978","journal-title":"J. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s12293-012-0075-1","article-title":"Chemical Reaction Optimization: A tutorial\u2014(Invited paper)","volume":"4","author":"Lam","year":"2012","journal-title":"Memetic Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/s12204-018-1981-2","article-title":"A New Fusion Chemical Reaction Optimization Algorithm Based on Random Molecules for Multi-Rotor UAV Path Planning in Transmission Line Inspection","volume":"23","author":"Yang","year":"2018","journal-title":"J. Shanghai Jiaotong Univ. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/j.asoc.2015.06.036","article-title":"A hybrid algorithm based on particle swarm and chemical reaction optimization for multi-object problems","volume":"35","author":"Li","year":"2015","journal-title":"Appl. Soft Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Li, Z., Yuan, T., Yang, B., Jiang, S., and Xie, Y. (2017, January 29\u201331). EBCRO: Hybrid chemical reaction with employed bee operator. Proceedings of the 2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), Guilin, China.","DOI":"10.1109\/FSKD.2017.8393061"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"5118","DOI":"10.1166\/jctn.2017.6931","article-title":"Bat-Mutation Chemical Reaction Optimization Algorithm for Conflict Optimization Problem: Case of Bandwidth Utilization","volume":"14","author":"Ngam","year":"2017","journal-title":"J. Comput. Theor. Nanosci."},{"key":"ref_21","first-page":"1449","article-title":"Opposition-based learning in global harmony search algorithm","volume":"34","author":"Zhai","year":"2019","journal-title":"Control. Decis."},{"key":"ref_22","unstructured":"Fei, H. (2017). The Research of Dynamic Economic Dispatch Integrated with Wind Power System Based on Chemical Reaction Optimization Algorithm, Hunan University."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.compbiolchem.2014.08.007","article-title":"Investigating long range correlation in DNA sequences using significance tests of conditional mutual information","volume":"53","author":"Papapetrou","year":"2014","journal-title":"Comput. Biol. Chem."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/5\/641\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:05:33Z","timestamp":1760137533000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/5\/641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,3]]},"references-count":23,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,5]]}},"alternative-id":["e24050641"],"URL":"https:\/\/doi.org\/10.3390\/e24050641","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,5,3]]}}}