Diseño de algoritmos Heuristicos y Metaheuristicos eficientes para el problema SBRR (Sorting Permutations by prefix Reversals)

Palacios Lopez, Wilmer Jose (2024) Diseño de algoritmos Heuristicos y Metaheuristicos eficientes para el problema SBRR (Sorting Permutations by prefix Reversals). Doctoral thesis, Universidad Nacional Autónoma de Nicaragua, Managua.

	Text (Descarga PDF) 21339.pdf Download (12MB)
	Image Licencia.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

Item Type:	Thesis (Doctoral)
Información Adicional:	Tesis-(Doctor en Matemática Aplicada)-Universidad Nacional Autónoma de Nicaragua Solamente en digital
Palabras Clave Informales:	Algoritmos heurísticos, Algoritmos metaheurísticos, Optimización combinatoria, Ordenamiento de permutaciones
Materias:	500 Ciencias naturales y matemáticas > 510 Matemáticas 500 Ciencias naturales y matemáticas > 510 Matemáticas > 518.1 Algoritmos 500 Ciencias naturales y matemáticas > 510 Matemáticas > 519 Probalidades y matemática aplicada
Divisiones:	CENTRO UNIVERSITARIO REGIONAL DE MATAGALPA > Doctorado en Matemática Aplicada
Depositing User:	Lic Angel Arauz
Date Deposited:	16 Jul 2024 21:43
Last Modified:	16 Jul 2024 21:43
URI:	http://repositorio.unan.edu.ni/id/eprint/21339

Downloads

Actions (login required)

View Item