Publicación:
AN IMPROVED CHEMICAL REACTION OPTIMIZATION ALGORITHM FOR SOLVING THE SHORTEST COMMON SUPERSEQUENCE PROBLEM

Vista sencilla de ítem
dc.creatorJOEL ALEJANDRO FUENTES LÓPEZ
dc.date2020
dc.date.accessioned2025-01-10T15:15:45Z
dc.date.available2025-01-10T15:15:45Z
dc.date.issued2020
dc.description.abstractTHE 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.
dc.formatapplication/pdf
dc.identifier.doi10.1016/j.compbiolchem.2020.107327
dc.identifier.issn1476-928X
dc.identifier.issn1476-9271
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/11179
dc.languagespa
dc.publisherCOMPUTATIONAL BIOLOGY AND CHEMISTRY
dc.relation.uri10.1016/j.compbiolchem.2020.107327
dc.rightsPUBLICADA
dc.titleAN IMPROVED CHEMICAL REACTION OPTIMIZATION ALGORITHM FOR SOLVING THE SHORTEST COMMON SUPERSEQUENCE PROBLEM
dc.title.alternativeUN ALGORITMO MEJORADO DE OPTIMIZACIÓN DE REACCIONES QUÍMICAS PARA RESOLVER EL PROBLEMA DE SUPERSECUENCIA COMÚN MÁS CORTO
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE CIENCIAS DE LA COMPUTACION Y TECNOLOGIA DE LA INFORMACION.
ubb.SedeCHILLÁN
Archivos
Colecciones
Artículos científicos