Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)

Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)

El ordenamiento de permutaciones por reversión de prefijos (SPBR) es un clásico problema de optimización combinatoria cuyo objetivo es ordenar una permutación de n elementos invirtiendo los bloques más a la izquierda (prefijos) de dicha permutación. En términos técnicos, se busca transformar una per...

Descripción completa

Detalles Bibliográficos
Autores principales: Palacios López, Wilmer José, Hernández Gómez, Fernando José
Formato: Online
Idioma:spa
Publicado: Revista Científica Tecnológica - ISSN: 2708-7093 2023
Acceso en línea:https://revistas.unan.edu.ni/index.php/ReVTec/article/view/3654
id RECIENTEC3654
record_format ojs
institution Universidad Nacional Autónoma de Nicaragua, UNAN-Managua
collection Revista Científica Tecnológica
language spa
format Online
author Palacios López, Wilmer José
Hernández Gómez, Fernando José
spellingShingle Palacios López, Wilmer José
Hernández Gómez, Fernando José
Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
author_facet Palacios López, Wilmer José
Hernández Gómez, Fernando José
author_sort Palacios López, Wilmer José
description El ordenamiento de permutaciones por reversión de prefijos (SPBR) es un clásico problema de optimización combinatoria cuyo objetivo es ordenar una permutación de n elementos invirtiendo los bloques más a la izquierda (prefijos) de dicha permutación. En términos técnicos, se busca transformar una permutación dada pi en una permutación identidad llamada i. Podría compararse, en magnitud, a una pila de tortitas que se debe reordenar con una espátula en cualquier punto, invirtiendo su orden para que, tras varias iteraciones, la pila quede ordenada. Sin embargo, desde 2012 se ha demostrado que este problema pertenece a la clase NP-Hard, lo que lo hace inviable en términos prácticos para la construcción de una solución óptima en tiempo polinómico o inferior. En los últimos años, la comunidad académica ha tratado de utilizar algoritmos heurísticos y metaheurísticos de aproximación que proporcionen mejores resultados y se acerquen al óptimo global. Durante el desarrollo de esta investigación se ha realizado y comparado el estado del arte del problema en estudio, se diseñarán e implementarán algoritmos heurísticos y metaheurísticos basados en criterios propuestos por la literatura revisada. Asimismo, se propondrá una familia de metaheurísticos inspiradas en la vida, cuyo rendimiento se espera que sea eficiente en la búsqueda de soluciones en grandes espacios de búsqueda. Para llevar a cabo la implementación de los algoritmos, se utilizará el lenguaje de programación Python, en combinación con la herramienta Google Colab, lo que permitirá un análisis rápido y eficiente de los algoritmos. Además, se revisaron los conceptos básicos relacionados con la teoría moderna de permutaciones y sus métodos elementales de ordenación. Se evaluaron distintos algoritmos heurísticos y metaheurísticos utilizando un conjunto de resultados obtenidos en la literatura científica de los últimos 10 años. Se compararon las ventajas y desventajas de cada método y se determinó cuál es el más adecuado en función del contexto del problema en cuestión.
title Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
title_short Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
title_full Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
title_fullStr Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
title_full_unstemmed Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals)
title_sort una revisión y clasificación de los algoritmos para el problema sbpr (sorting permutations by prefix reversals)
title_alt A review and classification of the algorithms for SBPR problem (Sorting Permutations By Prefix Reversals)
publisher Revista Científica Tecnológica - ISSN: 2708-7093
publishDate 2023
url https://revistas.unan.edu.ni/index.php/ReVTec/article/view/3654
work_keys_str_mv AT palacioslopezwilmerjose areviewandclassificationofthealgorithmsforsbprproblemsortingpermutationsbyprefixreversals
AT hernandezgomezfernandojose areviewandclassificationofthealgorithmsforsbprproblemsortingpermutationsbyprefixreversals
AT palacioslopezwilmerjose unarevisionyclasificaciondelosalgoritmosparaelproblemasbprsortingpermutationsbyprefixreversals
AT hernandezgomezfernandojose unarevisionyclasificaciondelosalgoritmosparaelproblemasbprsortingpermutationsbyprefixreversals
AT palacioslopezwilmerjose reviewandclassificationofthealgorithmsforsbprproblemsortingpermutationsbyprefixreversals
AT hernandezgomezfernandojose reviewandclassificationofthealgorithmsforsbprproblemsortingpermutationsbyprefixreversals
_version_ 1805403261820207104
spelling RECIENTEC36542024-04-30T16:39:08Z A review and classification of the algorithms for SBPR problem (Sorting Permutations By Prefix Reversals) Una revisión y clasificación de los algoritmos para el problema SBPR (Sorting Permutations By Prefix Reversals) Palacios López, Wilmer José Hernández Gómez, Fernando José Sorting permutations Heuristics algorithms Metaheuristics algorithms Combinatorial optimization Ordenamiento de permutaciones Algoritmos heurísticos Algoritmos metaheurísticos Optimización combinatoria The ordering of permutations by prefix reversal (SPBR) is a classical combinatorial optimization problem whose main objective is to order a permutation of n elements by reversing the leftmost blocks (prefixes) of that permutation. Technically, a given permutation  pi must be transformed into an identity permutation called i. Similarly, it could be compared in magnitude to a stack of pancakes that must be rearranged with a spatula by inserting at any point and reversing their order so that after several iterations the stack is ordered. However, since 2012 it has been shown that this problem belongs to the NP Hard class, which makes it infeasible in practical terms to construct an optimal solution in polynomial time or lower. In fact, in recent years, the academic community has been trying to use heuristic and metaheuristic approximation algorithms that provide better results approaching the global optimum. In this research, heuristic and metaheuristic algorithms were designed and implemented based on the criteria proposed by the reviewed literature. In addition, a family of life-inspired metaheuristics was proposed, which have proven to be very efficient in finding solutions in large search spaces. The algorithms used during the implementation of this research work were written with Python, using the Google Colab tool. In addition, the basic concepts related to modern permutation theory and its elementary sorting methods were reviewed. The evaluation of the algorithms was performed using the set of results provided by the scientific literature in the last 10 years. The advantages and disadvantages of the use of the different proposed methods were shown and, ultimately, it is shown which of them will prove to be the most appropriate depending on the context in which the problem is placed. El ordenamiento de permutaciones por reversión de prefijos (SPBR) es un clásico problema de optimización combinatoria cuyo objetivo es ordenar una permutación de n elementos invirtiendo los bloques más a la izquierda (prefijos) de dicha permutación. En términos técnicos, se busca transformar una permutación dada pi en una permutación identidad llamada i. Podría compararse, en magnitud, a una pila de tortitas que se debe reordenar con una espátula en cualquier punto, invirtiendo su orden para que, tras varias iteraciones, la pila quede ordenada. Sin embargo, desde 2012 se ha demostrado que este problema pertenece a la clase NP-Hard, lo que lo hace inviable en términos prácticos para la construcción de una solución óptima en tiempo polinómico o inferior. En los últimos años, la comunidad académica ha tratado de utilizar algoritmos heurísticos y metaheurísticos de aproximación que proporcionen mejores resultados y se acerquen al óptimo global. Durante el desarrollo de esta investigación se ha realizado y comparado el estado del arte del problema en estudio, se diseñarán e implementarán algoritmos heurísticos y metaheurísticos basados en criterios propuestos por la literatura revisada. Asimismo, se propondrá una familia de metaheurísticos inspiradas en la vida, cuyo rendimiento se espera que sea eficiente en la búsqueda de soluciones en grandes espacios de búsqueda. Para llevar a cabo la implementación de los algoritmos, se utilizará el lenguaje de programación Python, en combinación con la herramienta Google Colab, lo que permitirá un análisis rápido y eficiente de los algoritmos. Además, se revisaron los conceptos básicos relacionados con la teoría moderna de permutaciones y sus métodos elementales de ordenación. Se evaluaron distintos algoritmos heurísticos y metaheurísticos utilizando un conjunto de resultados obtenidos en la literatura científica de los últimos 10 años. Se compararon las ventajas y desventajas de cada método y se determinó cuál es el más adecuado en función del contexto del problema en cuestión. Revista Científica Tecnológica - ISSN: 2708-7093 2023-03-30 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Artículo revisado por pares application/pdf https://revistas.unan.edu.ni/index.php/ReVTec/article/view/3654 Revista Científica Tecnológica - ISSN: 2708-7093; Vol. 6 Núm. 1 (2023); 59-70 2708-7093 spa https://revistas.unan.edu.ni/index.php/ReVTec/article/view/3654/5937 https://creativecommons.org/licenses/by-nc-sa/4.0

Ejemplares similares