Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para el problema SBPR (Sorting Permutations By Prefix Reversals)

Palacios López, Wilmer José (2024) Diseño de Algoritmos Heurísticos y Metaheurísticos eficientes para el problema SBPR (Sorting Permutations By Prefix Reversals). Doctoral thesis, Universidad Nacional Autónoma de Nicaragua, Managua.

	Text (Descargar PDF) 21189.pdf Download (12MB)
	Image cc.jpg Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (6kB)

Resumen

El ordenamiento de permutaciones por reversión de prefijos (SBPR) es un problema clásico de optimización combinatoria cuyo objetivo principal es ordenar una permutación de n elementos invirtiendo los bloques más a la izquierda (prefijos) de dicha permutación. Técnicamente, una permutación dada π debe transformarse en una permutación identidad llamada ι. De forma similar, podría compararse en
magnitud a una pila de tortitas que hay que reordenar con una espátula introduciéndola en cualquier punto e 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 hace inviable en términos prácticos la construcción de una solución óptima en tiempo polinómico o inferior.
De hecho, 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. En esta investigación se diseñaron e implementaron algoritmos
heurísticos y metaheurísticos, basados en los criterios propuestos por la literatura revisada. Además, se propuso una familia de metaheurísticas inspiradas en la vida
que han demostrado ser muy eficientes en la búsqueda de soluciones en grandes espacios de búsqueda. Los algoritmos utilizados durante la implementación de este trabajo de investigación fueron escritos con Python, utilizando la herramienta Google Colab. Además, se revisaron los conceptos básicos relacionados con la teoría moderna de permutaciones y sus métodos elementales de ordenación. La evaluación
de los algoritmos se realizó utilizando el conjunto de resultados proporcionados por la literatura de la comunidad científica en los últimos 10 años. Se mostraron las
ventajas y desventajas del uso de los diferentes métodos propuestos y, en última instancia, cuál de ellos resultará ser el más adecuado en función del contexto en el
que se sitúe el problema. Palabras clave: Algoritmos heurísticos, Algoritmos metaheurísticos, Optimización combinatoria, Ordenamiento de permutaciones

Item Type:	Thesis (Doctoral)
Información Adicional:	Tesis-(Doctor en Matemática aplicada)-Universidad Nacional Autónoma de Nicaragua(CUR-Matagalpa)solamente digital
Palabras Clave Informales:	Algoritmos heurísticos, Algoritmos metaheurísticos, Optimización combinatoria, Ordenamiento de permutaciones
Materias:	000 Generalidades > 005 Programación en computadoras 300 Ciencias sociales > 301 Sociología y antropología > 000 Generalidades > 005 Programación en computadoras 500 Ciencias naturales y matemáticas > 510 Matemáticas > 518.1 Algoritmos
Divisiones:	CENTRO UNIVERSITARIO REGIONAL DE MATAGALPA > Doctorado en Matemática Aplicada
Depositing User:	Lic. Cinthya Rojas
Date Deposited:	26 Sep 2024 20:08
Last Modified:	26 Sep 2024 20:08
URI:	http://repositorio.unan.edu.ni/id/eprint/21189

Downloads

Actions (login required)

View Item